On 03/03/2013 at 17:19, xxxxxxxx wrote:
Cinema 4D Version: R12
Platform: Windows ; Mac OSX ;
Language(s) : C++ ;
I have initial Bounding-Sphere tests for quick-out collision detection. I already have a robust and rather quick ray-triangle collider system for triangulated meshes based on Möller-Trumbore (modified to handle edge leaks). Just the two of these gets too slow as triangle counts mount. Now I need the dreaded space-partioning system to quickly prune triangles from the ray-triangle intersection test which should increase speed significantly and succumb more slowly to increasing triangle counts.
Since my ray-triangle intersections are done in object space, like C4D's GeRayCollider, an AABB-tree would be burdensome. That needs to be recomputed on not only data changes but also any matrix changes since they are oriented to the world axes (not to mention the expensive matrix multiplications!). An 'AABB-like' OBB-tree seems the best bet. By that, I don't mean the nasty, arbitrarily oriented boxes of a typical OBB-tree, just an AABB-tree that is oriented in object space for ray-triangle intersection tests. This would only need to be recomputed on data changes (matrix changes are irrelevant). Much more acceptable.
Where can I find comprehensive information on writing something like this (from tree creation (top-down or bottom-up), traversal, pruning, and then intersection testing)? It is very difficult to find algorithms, source, pseudo-code, or even papers since many dealing with AABB-trees are concentrating on ray-tracing for rendering. If they are dealing with collision detection, they get all vague or implement a very topic-specific solution. I will look at a couple of the seminal papers (Larsson et al), maybe an indepth search will find more information based upon them. Figured it would be best to get more direct answers instead of wasting days sifting through useless Google results and repetitive non-relevant material.