• 3d-dda on a dynamic grid

    From Merlin Katz@21:1/5 to Erwin Coumans on Wed Dec 16 20:57:01 2020
    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.
    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.

    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!

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From mgarcia@21:1/5 to Merlin Katz on Wed Jan 6 09:33:14 2021
    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 (https://www.youtube.com/watch?v=SDS5gLSiLg0). It's even in the
    thumbnail of the video! GJK is great for testing intersections of
    expanded polygons.

    Merlin Katz wrote:
    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.
    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.
    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!

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)