View Full Version : Find nearest vertices fast without comparing all of them

09-04-2006, 12:24 AM

I have one polygonal object. Now I want to get all vertices that are specified distance away from another vertex of the same object or any world position. The vertices are not necessarily connected with an edge.

Do I realy need to check all vertices of this object, or is there any smart mel-function, that can find surrounding vertices fast?

For instance when I select vertices manualy with the mouse in a component mode I am sure that maya does not check all vertices if they are in the selection area but knows it quasi immediately...

Robert Bateman
09-04-2006, 04:16 AM
well, if by quasi immeditaley you mean - it checks all the vertices on a mesh before the user has a chance to notice, erm, then that's actually what it does..... (Rendering the components takes longer than a selection test of that sort).

When maya does a selection test, it first tests the objects in the scene via a bounding box test (notice the bounding box attributes on all transform nodes...). Having determined which objects, it then determines the actual component selection (which it does via a screen space test - i'm guessing with the selection buffer of openGL, or some other form of projected frustum test).

In the API, you can use MGlobal::selectFromScreen() to use maya's internal selection, i'm not entirely sure if there is a similar feature in mel.

As a tip though, if you are doing a radius test, it's faster to do a radius test by comparing the radius squared. It's also faster to transform the position into the local space of the mesh instead of forcing xform or other command to evaluate the world space vertex positions (lots of matrix transforms == very in-efficient).

$mesh = "pTorus1";
$locator = "locator1";
$radius = 2;
$radius2 = $radius*$radius;

// hack to get a point in local space - creates a new transform in same location,
// then parents under the mesh for a short while
$pos = `xform -q -ws -t $locator`;
$tempLocator = `createNode "transform"`;
setAttr ($tempLocator+".t") $pos[0] $pos[1] $pos[2];
parent -a $tempLocator $mesh ;
$pos = `xform -q -t $tempLocator`;

// select all verts on the mesh
select -r ($mesh + ".vrts
$verts = `ls -sl -fl`;

// clear selection list
select -clear;
string $newverts[];
for( $v in $verts )
$vert = `getAttr $v`;
float $x = $vert[0]-$pos[0];
float $y = $vert[1]-$pos[1];
float $z = $vert[2]-$pos[2];
float $dist = $x*$x + $y*$y + $z*$z;
$newverts[size($newverts)] = `substitute "vrts" $v "vtx"`;

// can't select vrts, though can select vtx - hence substitute used to get the
// correct name to select....

// select the verts
select -r $newverts;

// and clean up....
clear $newverts;
delete $tempLocator;

09-04-2006, 08:39 AM
Nope, with a straight forward approach you can't avoid checking all the vertices. This problem is the same as finding all numbers from an array of N numbers that are smaller then Y. Numbers in this array are distances to the concrete point and Y is the radius of the sphere. In this problem you can't avoid checking all of the distances, otherwise results might me incorrect.

To avoid this you might create some kind of cache for your mesh, a data structure that will be optimized to perform that kind of queries. Say, given a point in 3d space and a radius, return an array of all indices that are inside that sphere. Or simpler way: given a 3d point, cache your mesh. Then by varying the radius you'll get different output indices. All these are slightly complex and I recommend using them if you'll really have to do a lot of queries of that sort on the same mesh one after the other.

If you're using mel, you can use Polygon Selection Constraints to do the job for you. Just specify the distance constraint, enter the world point coordinates and radius and set it to "All and Next mode", it will select all the vertices that are inside that sphere. Then you just transform that to a Mel command. Don't forget to reset or restore the constraints after you're done with them :)

Hope it helps,

CGTalk Moderation
09-04-2006, 08:39 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.