Hi, I’m implementing drag selection using collision detection.
To measure the performance of a CollisionTraverser, I measured the time complexity according to the number of “from” objects. I got the time complexity of O(N^{1.76}) where N is the number of “from” object, the “into” object is a pyramid (4 planes) and the “from” objects are spheres.
Due to the fact that I set the IntoCollideMask of spheres to zero bits, I think the collisions between spheres are not calculated, so why does the order of time complexity have a value of 1.76 close to the order of pairwise comparison (2)? Is this natural?
Hard to say. You can set notify-level-collide to spam or debug to see which checks are actually being performed, or open PStats to see the actual number of collision tests.
Should collision detection prove to be too slow for your needs, you might also want to look into a technique involving a shader that writes the index associated with specific vertices to a texture. All you need to do then is to iterate over its texels to see which vertices were rendered within a rectangular section of the screen.
In case you’re interested in implementing more sophisticated selection methods like lasso-selection, fence-selection, paint-selection or restricting selection to objects completely enclosed within the selection rectangle, then I can definitely recommend that technique.
You can find a working example in this post. Although that code deals with a point-cloud, the technique is applicable to GeomTriangles as well. The only requirement for your geometry is that its format contains an "index" column.
If this seems useful to you, I’d be happy to provide more info .
Are you trying to solve the 3-body problem (or the N-body problem)? I have implemented some proof of concept programs for calculating the interactions of many bodies in Panda3D, without using a physics engine. The computational complexity is realistically exponential in this case.
.