BVH for fast collision detections
-
On 03/03/2013 at 17:19, xxxxxxxx wrote:
User Information:
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.
Thanks!
-
On 05/03/2013 at 13:51, xxxxxxxx wrote:
Howdy,
Have you looked at this book:
http://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323/ref=sr_1_1?s=books&ie=UTF8&qid=1362520214&sr=1-1&keywords=real+time+collision+detectionAdios,
Cactus Dan -
On 05/03/2013 at 14:51, xxxxxxxx wrote:
Yes. Actually, I looked at it years ago but never got around to purchasing it. Currently, I don't have the money to buy it. Quite an investment under the circumstances. A good investment but more than pocket change.
I finally found some code that I am modifying for my specific purposes. Unfortunately it makes use of the STL and am not sure if that will be a good idea. Might translate that stuff into GeDynamicArray (or GeAutoDynamicArray).
-
On 06/03/2013 at 00:46, xxxxxxxx wrote:
Real-Time Collision Detection is really great book.
Another nice source of information is this one:
www.geometrictools.comUsing STL in such time critical code is usually not good idea.
But really bad idea is using virtual tree nodes
-
On 06/03/2013 at 05:23, xxxxxxxx wrote:
No, not David Eberly!!!
He has done some amazing work but his source code is so interdependent to such a depth that it makes it very difficult to extract snippets and sections for use without digging down into tons of classes and such. And I'm not the only developer who has mentioned this.The code that I'm using as reference only uses the std::vector for triangles in the nodes or being passed around to the nodes (I haven't examined that part fully yet). If I can precompute the counts, I'll just allocate it for speed sakes. I also notice that there is not one single memory allocation check in the code - but this was written by a senior developer at NVidia. He even mentions that it is a down-and-dirty example and not a solution. So, I am going to be modifying and optimizing the heck out of it.