PDA

View Full Version : API:MMeshIntersector speed? or alternatives?


steph24
09-10-2010, 03:49 PM
Hi !


I solved my problem before by MEL but for the last step it would be so slow so i decided to write it in API.

the problem is: tree branches.I've got two group a mainBranch Group(5700 object) and a subBranch Group(250 000 object). I need to select the closest mainBranch to the subBranch.vtx[0].
In Mel it is ok for lower counts(for ex. 2000 and 5700) but for this 250000 subBranch it would took ages.
I managed to write a plugin but it seems that the MMeshIntersector::create function is so slow that it is the same as the solution in MEL.

my code is like:

MItSelectionList iter(subBranch);
for ( ; !iter.isDone(); iter.next() )
{
//code for getting the vtx[0] position of the sub branch
MItSelectionList iterSec(mainBranch);

for ( ; !iterSec.isDone(); iterSec.next() )
{

// I create the intersector here
.........
.........
status = intersector.create( node, matrix );
if ( status )
{
.....
status = intersector.getClosestPoint( point, pointInfo );
.............

}

}
}

The intersector create function is in the second loop so it will called 250000 times ....
Am I in totaly wrong way to solve this problem? is there any faster solution to find the closest point of all the 5700 object and compare them? now this solution is the same speed as to create in MEL a nearestPoint node and use it's data to compare them.

thanks in advance

S.

scroll-lock
09-10-2010, 11:56 PM
to my knowledge the MMeshIntersector is the fastest method for finding "closestPoint". ( I have done speed tests with the normal closestPoint() function in the MFnMesh class ? If I remember correctly as I`m not infront of Maya and the MMeshIntersector and the MeshIntersector algorithm is times faster.) Make sure you are not constructing the intersector INSIDE the loop as it seems you are doing in your code. The create method creates the traversal tree, which is slow, but once it is build it's very fast to traverse it.

steph24
09-11-2010, 11:33 AM
Thanks for the reply, I'm a beginner in programming so maybe I misunderstood how MMeshIntersector is working.
If i understand well with the create function it build an octree for the object to intersect with, and that is "measured" with the given point.But I have a lot of object and as i see just one object can be pass to create an intersector, that's why I tought to put the creation function inside the loop.
Is there a way to give all the object to MMeshIntersector::create?

thanks again

S.

Hirni_NG
09-11-2010, 12:57 PM
As far as I can see you are out of luck using Maya internal routines. The reason for that is because you have 250k single objects and you need to build an octree with .create for every single one of them for every traversal.

If it works, you can build all necessary octrees once before the loop, though I do not know if this fits into your RAM because 250k octrees is alot. Within the loop you then only have to do the closestPoint traversal. This would already cut down extremely on the calculation cost on the expense of memory and you can even do that multithreaded.

Another way would be to build your own little acceleration structure. The simplest would be to record the closest point you already have and check the distance of a bounding box of any object following in the iteration to check if there is even the possibility of a closer point being in that object so you avoid building an octree. This can cut down the redundant octree building by at least 80%.

A more sophisticated approach would be to build a bounding volume hierarchy from the objects bounding boxes, then you only have to build one octree for every closestpoint traversal which would be close to the optimum.

scroll-lock
09-11-2010, 07:25 PM
Sorry I must have misunderstood that you had so many objects to operate on. And yes, the creating of the octree is slow process that's why your algorithm takes so much time. And you have to create one octree for every object, it's impossible otherwise. The methods that Hirni_NG recommended will work better in your situation then.

Robert Bateman
09-13-2010, 09:06 AM
Sorry I must have misunderstood that you had so many objects to operate on. And yes, the creating of the octree is slow process that's why your algorithm takes so much time. And you have to create one octree for every object, it's impossible otherwise. The methods that Hirni_NG recommended will work better in your situation then.

Nonsense.

The DAG in Maya is an AABB-tree, so you already have a way of performing aggressive culling for thousands of objects in the scene (as proven by maya's selection mechanism). Simply use an MItDag object to traverse the scene, and skip the children (prune) when the world space bounds of the object is too far from the point you wish to test. Having found the relevant bounds (which relate to a specific MDagPath), it's then a case of performing the intersection on the few remaining objects (which will probably be quicker without the MMeshIntersector - but you may want to test that).

A more sophisticated approach would be to build a bounding volume hierarchy from the objects bounding boxes, then you only have to build one octree for every closestpoint traversal which would be close to the optimum.
Or save yourself the effort and use the BVH tree that maya already provides....

Hirni_NG
09-13-2010, 10:56 AM
Using the DAG hierarchy is a good idea, though it does not necessarily reflect the spatial correlation of the objects, but there is a good chance. Also, if one does not have a hierachy, one ends up checking every bounding box anyway. So any self-rolled spatial acceleration structure would still be faster.

The easiest approach would be to test for the bounding boxes including childs, throwing out any children from the iteration if the test is false. This should be implementable in a few lines of code.

There is also the possibility to merge all objects into one, tagging each poly with the object ID to allow the reconstruction of the object. This optimizes the traversal, but there has to be a lot of traversal to make up for the long building time of both merged object and octreel.

Robert Bateman
09-13-2010, 11:56 AM
So any self-rolled spatial acceleration structure would still be faster.

If, and only if, the scene is static. In every other case using your own structure will be slower.

The easiest approach would be to test for the bounding boxes including childs, throwing out any children from the iteration if the test is false. This should be implementable in a few lines of code.

Simply use an MItDag object to traverse the scene, and skip the children (prune) when the world space bounds of the object is too far from the point you wish to test. Having found the relevant bounds (which relate to a specific MDagPath), it's then a case of performing the intersection on the few remaining objects

Hirni_NG
09-13-2010, 12:37 PM
If, and only if, the scene is static. In every other case using your own structure will be slower.

It depends on the data and the coherence in it. If there is no DAG hierarchy, there is nothing to work with. It also depends on the number of traversals performed. For a high number of traversals, a rebuild of the acceleration structure can be faster even in the fully dynamic case.

Though this is certainly overshooting for the given problem, one does not need to necessarily rebuild the structure, there are loose and irregular dynamic octrees as well bvh and kd-tree algorithms that avoid rebuilding the complete structure as done by some raytracers and collision libraries.

CGTalk Moderation
09-13-2010, 12:37 PM
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.