last year I discovered a small graphics gem that allows efficient raycasting through a dynamic broadphase known as Baraffs 3d axis sweep and prune.
A well known algorithm to speed up raycasting was presented by Fujimoto [1]Basically a ray traverses a 3d axis aligned regular voxel grid (called seads) by visiting all voxels that the ray intersects with. It does this efficiently by maintaining the closest distances to every axis.
For dynamic scenes a 3d sweep and prune broadphase proposed by Baraff [2] is often used that sorts the aabb's of all objects in such a way that overlap can be reported incrementally.
Both incremental algorithm can be combined by observing that the broadphase is essentially a non-uniform voxel grid, where all endpoints represent the planes.
It is a sparce grid, in the sense that most voxels in this grid are empty. Just like the original 3d-dda algorithm, initially the starting location inside the broadphase has to be calculated (or cached) as well as the next closest plane for every of the 3 axis.
Traversing is similar to the original 3d-dda algorithm, the current closest axis will be crossed and if the voxel is non-empty a narrowphase raycast
will be performed. The distance for this axis is updated and the iteration repeats.
As an ending criterium, either the ray leaves the broadphase grid or the closest distance to the next axis along the ray is further then the current closest hit reported by the narrowphase.
Erwin Coumans
[1]Akira Fujimoto and Kansei Iwata, "Accelerated Ray Tracing", CG TOKYO 85, proceedings, 1985.
http://www.integra.co.jp/eng/ceo.htm
[2] D. Baraff and A. Witkin. Dynamic simulation of non-penetrating flexible bodies. Computer Graphics 26(2): 303-308, 1992. http://www.pixar.com/companyinfo/research/deb/
by the way:
The algorithm can be extended into an aabb cast by expanding all aabbs in
the broadphase by the extents of the aabb. This expanding can be done while traversing the ray and bookkeeping 2 closest planes for every axis (so 6 in total) where the 2 axis are the closest expanded min-endpoint and closest expanded max-endpoint.
On Thursday, February 6, 2003 at 5:33:06 AM UTC-5, Erwin Coumans wrote:
last year I discovered a small graphics gem that allows efficient raycasting >> through a dynamic broadphase known as Baraffs 3d axis sweep and prune.Hello!
A well known algorithm to speed up raycasting was presented by Fujimoto
[1]Basically a ray traverses a 3d axis aligned regular voxel grid (called
seads) by visiting all voxels that the ray intersects with. It does this
efficiently by maintaining the closest distances to every axis.
For dynamic scenes a 3d sweep and prune broadphase proposed by Baraff [2] is >> often used that sorts the aabb's of all objects in such a way that overlap >> can be reported incrementally.
Both incremental algorithm can be combined by observing that the broadphase >> is essentially a non-uniform voxel grid, where all endpoints represent the >> planes.
It is a sparce grid, in the sense that most voxels in this grid are empty. >> Just like the original 3d-dda algorithm, initially the starting location
inside the broadphase has to be calculated (or cached) as well as the next >> closest plane for every of the 3 axis.
Traversing is similar to the original 3d-dda algorithm, the current closest >> axis will be crossed and if the voxel is non-empty a narrowphase raycast
will be performed. The distance for this axis is updated and the iteration >> repeats.
As an ending criterium, either the ray leaves the broadphase grid or the
closest distance to the next axis along the ray is further then the current >> closest hit reported by the narrowphase.
Erwin Coumans
[1]Akira Fujimoto and Kansei Iwata, "Accelerated Ray Tracing", CG TOKYO 85, >> proceedings, 1985.
http://www.integra.co.jp/eng/ceo.htm
[2] D. Baraff and A. Witkin. Dynamic simulation of non-penetrating flexible >> bodies. Computer Graphics 26(2): 303-308, 1992.
http://www.pixar.com/companyinfo/research/deb/
by the way:
The algorithm can be extended into an aabb cast by expanding all aabbs in
the broadphase by the extents of the aabb. This expanding can be done while >> traversing the ray and bookkeeping 2 closest planes for every axis (so 6 in >> total) where the 2 axis are the closest expanded min-endpoint and closest
expanded max-endpoint.
I know there's a small chance of getting a reply 17 years later, but this was a
super useful explanation of ray casts in SAP, and I was just wondering if anyone
could elaborate on that last point on an aabb cast. I'm having trouble parsing
the description but I'm really curious.
Thanks!
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 113 |
Nodes: | 8 (1 / 7) |
Uptime: | 115:02:30 |
Calls: | 2,501 |
Files: | 8,685 |
Messages: | 1,922,174 |