3d-dda on a dynamic grid

mgarcia

2021-01-05 22:33:14 UTC

dandymcgee replied (https://www.youtube.com/user/dandymcgee)
They're talking about one of David Barraff's papers on sweep-and-prune
algorithms the OP is just saying that if you want to cast an AABB
instead of a ray, then you simply add the min and max extents of the
AABB you want to sweep across the ray to each overlap check
this is an extremely common technique for continuous collision
detection, or for expanding the bounds of your broadphase to capture
dynamic objects within the limits of their movement for the given frame
at the time of that post (2003) it was hardly novel, and it's certainly
not now either. there's really nothing special being said
(the original papers by David Barraff are, however, somewhat novel and
special to my knowledge, as they're extremely widely cited and many
future developments have been based on them)
In fact, this exact technique (albeit in a slightly different context,
as it's not a sweep-and-prune algorithm) was touched upon by Casey in
the video I posted directly above your post

It's even in the
thumbnail of the video! GJK is great for testing intersections of
expanded polygons.

Post by Merlin Katz

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/
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.

Hello!
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!