Re: [Algorithms] Raycasting - how fast does it get?

 Re: [Algorithms] Raycasting - how fast does it get? From: - 2007-10-31 19:28:09 ```Christer, > By using a van Emde Boas-type chunking of the tree, you can > ensure that you can traverse several levels (3, 4, perhaps even > 5) of the tree without ever leaving a cache line. (Section 13.4.1 > of my book outlines one way of doing this.) Can you provide a brief description of how that chunking works? For those who (like me) don't have your book handy... I've thought about clustering nodes before, that would save a high number of node offsets and reduce the size of the tree, but it would also constrain the construction because the layout of the nodes in the cluster is fixed. SAH trees usually contain many empty leafs, so regular (complete) clusters are rare. --=20 Ignacio Casta=F1o castano@... On 10/31/07, christer_ericson@... wrote: > > > Alen, > > > To ask it straight off... What would be the fastest way to check a ray > > against a polygon soup? The mesh is static, so any kind of > > precalculation could be ok (as long as the memory requirement is not > > ridiculous). The only required result is distance of nearest hit (or > > +inf if it's a miss) - don't even need to know which polygon was hit. > > For a tree-based hierarchy there are two things you need to > worry about: > > 1. The traversal cost of getting to where the data is, usually > the leaves > 2. The cost if intersecting the ray(s) against the polygons > stored in the leaves > > Optimizing both is all an exercise in caching. Like many have > implied already, a k-d tree gives you very small tree nodes > which allows you to pack many of them into a single cache line. > By using a van Emde Boas-type chunking of the tree, you can > ensure that you can traverse several levels (3, 4, perhaps even > 5) of the tree without ever leaving a cache line. (Section 13.4.1 > of my book outlines one way of doing this.) > > Once you're in a leaf you want your data to be linearized (thus > cache line friendly) and also SIMD-able. Usually data is not stored > in such a format, because you're likely using indices etc to reduce > storage. However, as ray queries are usually coherent over time you > can pull all data in and write it into a software cache, in a > SIMD-friendly and linearized format. Then, each time you visit a > leaf, you check if you already have the leaf in your software cache > and your tests are blisteringly fast. (I talk about this too, > in Section 13.5.) You'll have to experiment some to find out what > the appropriate number of polygons per leaf should be for your > particular application. > > So, short answer: your best bet is likely a cache-aware k-d tree > (van Emde Boas style) with cached linearization of the leaves. > > > Christer Ericson, Director of Tools and Technology > Sony Computer Entertainment, Santa Monica > http://realtimecollisiondetection.net/blog/ ```