PDA

View Full Version : max distance within bounding box?


davegreenwood
04-07-2009, 08:55 PM
Hi all, I wonder if anyone can help me here. I'm trying to calculate the max distance from a random point within a bounding box to the extent of the bounding box. Obviously I can measure to all 8 corners and compare, but I wondered if there was a quicker way, either a command (kind of the opposite to closestPointOnMesh), or some clever math...

Thanks for any help.
Dave.

cbamber85
04-08-2009, 01:56 PM
Obviously I can measure to all 8 corners and compare
That is by far the most efficient way, and would only be a few lines of code. How easy do you want it!?

davegreenwood
04-09-2009, 01:41 PM
Well, it's not about how easy it is to do it, I'm just looking for the most efficient way to go about it. At present I'm using:

global proc float findMaxDist(string $obj, vector $V)
// find the maximum distance a point can travel in a bounding box
{
float $objBB[] = `xform -q -bb $obj`;

vector $BBmin1 = <<$objBB[0],$objBB[1],$objBB[2]>>;//first diagonal
vector $BBmax1 = <<$objBB[3],$objBB[4],$objBB[5]>>;
vector $BBmin2 = <<$objBB[3],$objBB[4],$objBB[2]>>;//second diagonal
vector $BBmax2 = <<$objBB[0],$objBB[1],$objBB[5]>>;

float $toMin1 = mag($V - $BBmin1);
float $toMax1 = mag($V - $BBmax1);
float $toMin2 = mag($V - $BBmin2);
float $toMax2 = mag($V - $BBmax2);

float $Len1;
float $Len2;

if ($toMin1>$toMax1){
$Len1 = $toMin1;
}else{
$Len1 = $toMax1;
}

if ($toMin2>$toMax2){
$Len2 = $toMin2;
}else{
$Len2 = $toMax2;
}

if ($Len1>$Len2){
return $Len1;
}else{
return $Len2;
}

}

which as you can see measures to a point 4 times and makes 3 comparisons to produce the result. It also uses mag command 4 times which is quite expensive....
None of this would be an issue, if I didn't have to call this procedure 10,000 times, but I do.
I'm just wondering if there is a better way?

Cheers
Dave.

cbamber85
04-09-2009, 02:03 PM
What you've written really isn't too taxing, the mag is slightly more intensive due to the square root in it, but it's mostly basic math operators. Of course looping it 10,000x would make a hell of a difference...

I think the problem really lies with you using MEL, it's a built-in scripting language, it's not designed for heavy computation. C++ would be OTT for what you're doing, but writing it in Python should give a dramatic performance increase.

If you do re-write it, can you post some timerX results? It would be interesting to see performance changes in a real-world test.

Robert Bateman
04-09-2009, 03:04 PM
Well, it's not about how easy it is to do it, I'm just looking for the most efficient way to go about it. At present I'm using:

Surely it should test all 8 points that make up the cube? Though i may have missed something obvious in your code there.

The only way to speed this up is to use a form of binary search, which requires 3 floating point tests to determine which is the furthest cube-point from the vector. Reduces the number of mag calls to 1 (at the expense of some jumps):

// not actually tested this...

global proc float findMaxDist(string $obj, vector $V)
// find the maximum distance a point can travel in a bounding box
{
float $objBB[] = `xform -q -bb $obj`;
$xmid = ($objBB[3] + $objBB[0])*0.5;
$ymid = ($objBB[4] + $objBB[1])*0.5;
$zmid = ($objBB[5] + $objBB[2])*0.5;

if($V.x > $xmid)
{
if($V.y > $ymid)
{
if($V.z > $zmid)
{
// point is in +x, +y, +z, therefore -x,-y,-z is furthest point
return mag(<<$objBB[0],$objBB[1],$objBB[2]>> - $V);
}
else
{
return mag(<<$objBB[0],$objBB[1],$objBB[5]>> - $V);
}
}
else
{
if($V.z > $zmid)
{
return mag(<<$objBB[0],$objBB[4],$objBB[2]>> - $V);
}
else
{
return mag(<<$objBB[0],$objBB[4],$objBB[5]>> - $V);
}
}
}
if($V.y > $ymid)
{
if($V.z > $zmid)
{
return mag(<<$objBB[3],$objBB[1],$objBB[2]>> - $V);
}
else
{
return mag(<<$objBB[3],$objBB[1],$objBB[5]>> - $V);
}
}
else
{
if($V.z > $zmid)
{
return mag(<<$objBB[3],$objBB[4],$objBB[2]>> - $V);
}
}
return mag(<<$objBB[3],$objBB[4],$objBB[5]>> - $V);
}


Alternatively, use a set of nodes:


//
// on the created locator, set (or connect) the min / max points for the bounding box.
// set (or connect) the test vevtor to the test var
// the distance attr will now hold the result.
//
{
$loc = `spaceLocator -p 0 0 0`;

// the output distance
addAttr -ln "distance" -at double $loc;

// setup input attr connections
addAttr -ln "min" -at double3 $loc;
addAttr -ln "minX" -at double -p min $loc;
addAttr -ln "minY" -at double -p min $loc;
addAttr -ln "minZ" -at double -p min $loc;

addAttr -ln "max" -at double3 $loc;
addAttr -ln "maxX" -at double -p max $loc;
addAttr -ln "maxY" -at double -p max $loc;
addAttr -ln "maxZ" -at double -p max $loc;

// setup input test point
addAttr -ln "test" -at double3 $loc;
addAttr -ln "testX" -at double -p test $loc;
addAttr -ln "testY" -at double -p test $loc;
addAttr -ln "testZ" -at double -p test $loc;

// connect to +- average
string $pma = `shadingNode -asUtility "plusMinusAverage"`;
connectAttr -f ($loc[0]+".min") ($pma+".input3D[0]");
connectAttr -f ($loc[0]+".max") ($pma+".input3D[1]");

// set to average
setAttr ($pma+".operation") 3;

string $con1 = `shadingNode -asUtility "condition"`;
string $con2 = `shadingNode -asUtility "condition"`;
string $con3 = `shadingNode -asUtility "condition"`;
setAttr ($con1+".operation") 2;
setAttr ($con2+".operation") 2;
setAttr ($con3+".operation") 2;

connectAttr -f ($loc[0]+".testX") ($con1+".firstTerm");
connectAttr -f ($loc[0]+".testY") ($con2+".firstTerm");
connectAttr -f ($loc[0]+".testZ") ($con3+".firstTerm");

connectAttr -f ($pma+".output3Dx") ($con1+".secondTerm");
connectAttr -f ($pma+".output3Dy") ($con2+".secondTerm");
connectAttr -f ($pma+".output3Dz") ($con3+".secondTerm");

connectAttr -f ($loc[0]+".minX") ($con1+".colorIfTrueR");
connectAttr -f ($loc[0]+".minY") ($con2+".colorIfTrueR");
connectAttr -f ($loc[0]+".minZ") ($con3+".colorIfTrueR");

connectAttr -f ($loc[0]+".maxX") ($con1+".colorIfFalseR");
connectAttr -f ($loc[0]+".maxY") ($con2+".colorIfFalseR");
connectAttr -f ($loc[0]+".maxZ") ($con3+".colorIfFalseR");

string $dis = `shadingNode -asUtility distanceBetween`;
setAttr ($dis+".point1") 0 0 0;
connectAttr -f ($con1+".outColorR") ($dis+".point2X");
connectAttr -f ($con2+".outColorR") ($dis+".point2Y");
connectAttr -f ($con3+".outColorR") ($dis+".point2Z");
connectAttr -f ($dis+".distance") ($loc[0]+".distance");
}


The fastest is really going to depend on where the data is coming from, and you'll have to benchmark that.

Robert Bateman
04-09-2009, 03:07 PM
C++ would be OTT for what you're doing

Not really. A simple node that took an input array of points, min/max bounding box points, and returned an array of floats of the max distances would be a relatively sane thing to do.

I think the problem really lies with you using MEL, it's a built-in scripting language, it's not designed for heavy computation.

Before you go writing mel off. Try the script again with the undo queue disabled, and make sure you're not using any print statements. You may find it orders of magnitude faster.

davegreenwood
04-09-2009, 05:32 PM
Surely it should test all 8 points that make up the cube? Though i may have missed something obvious in your code there.


Well, my theory on that is a point in a bounding box is in one symmetric half or the other, so then I check the two ends of the two longest diagonals...

ie. in a 2d triangle the furthest point from a point inside is one end of the hypotenuse.

I didn't check too carefully but it seems to work:)

Cheers
Dave

cbamber85
04-10-2009, 11:44 AM
make sure you're not using any print statements. You may find it orders of magnitude faster.
Yeah why is that? And have you noticed if sys.stdout.write(), MStatus:;error() or MGlobal::displayInfo() are any quicker? Or is it the Script Editor refreshing that's slow?

CGTalk Moderation
04-10-2009, 11:44 AM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.