Home » most efficient AABB vs Ray collision algorithms

most efficient AABB vs Ray collision algorithms

Solutons:


Andrew Woo, who along with John Amanatides developed the raymarching algorithm (DDA) used ubiquitously in raytracers, wrote “Fast Ray-Box Intersection” (alternative source here) which was published in Graphics Gems, 1990, pp. 395-396. Rather than being built specifically for integration through a grid (eg. a voxel volume) as DDA is (see zacharmarz’ answer), this algorithm is specifically suited to worlds that are not evenly subdivided, such as your typical polyhedra world found in most 3D games.

The approach provides support for 3D, and optionally does backface culling. The algorithm is derived from the same principles of integration used in DDAs, so it is very quick. More detail can be found in the original Graphics Gems volume (1990).

Many other approaches specifically for Ray-AABB to be found at realtimerendering.com.

EDIT: An alternative, branchless approach — which would be desirable on both GPU & CPU — may be found here. The actual code, including the max() on the return test, is available here.

What I have been using earlier in my raytracer:

// r.dir is unit direction vector of ray
dirfrac.x = 1.0f / r.dir.x;
dirfrac.y = 1.0f / r.dir.y;
dirfrac.z = 1.0f / r.dir.z;
// lb is the corner of AABB with minimal coordinates - left bottom, rt is maximal corner
// r.org is origin of ray
float t1 = (lb.x - r.org.x)*dirfrac.x;
float t2 = (rt.x - r.org.x)*dirfrac.x;
float t3 = (lb.y - r.org.y)*dirfrac.y;
float t4 = (rt.y - r.org.y)*dirfrac.y;
float t5 = (lb.z - r.org.z)*dirfrac.z;
float t6 = (rt.z - r.org.z)*dirfrac.z;

float tmin = max(max(min(t1, t2), min(t3, t4)), min(t5, t6));
float tmax = min(min(max(t1, t2), max(t3, t4)), max(t5, t6));

// if tmax < 0, ray (line) is intersecting AABB, but the whole AABB is behind us
if (tmax < 0)
{
    t = tmax;
    return false;
}

// if tmin > tmax, ray doesn't intersect AABB
if (tmin > tmax)
{
    t = tmax;
    return false;
}

t = tmin;
return true;

If this returns true, it’s intersecting, if it returns false, it’s not intersecting.

If you use the same ray many times, you can precompute dirfrac (only division in whole intersection test). And then it’s really fast. And you have also length of ray until intersection (stored in t).

Nobody described the algorithm here, but the Graphics Gems algorithm is simply:

  1. Using your ray’s direction vector, determine which 3 of the 6 candidate planes would be hit first. If your (unnormalized) ray direction vector is (-1, 1, -1), then the 3 planes that are possible to be hit are +x, -y, and +z.

  2. Of the 3 candidate planes, do find the t-value for the intersection for each. Accept the plane that gets the largest t value as being the plane that got hit, and check that the hit is within the box. The diagram in the text makes this clear:

enter image description here

My implementation:

bool AABB::intersects( const Ray& ray )
{
  // EZ cases: if the ray starts inside the box, or ends inside
  // the box, then it definitely hits the box.
  // I'm using this code for ray tracing with an octree,
  // so I needed rays that start and end within an
  // octree node to COUNT as hits.
  // You could modify this test to (ray starts inside and ends outside)
  // to qualify as a hit if you wanted to NOT count totally internal rays
  if( containsIn( ray.startPos ) || containsIn( ray.getEndPoint() ) )
    return true ; 

  // the algorithm says, find 3 t's,
  Vector t ;

  // LARGEST t is the only one we need to test if it's on the face.
  for( int i = 0 ; i < 3 ; i++ )
  {
    if( ray.direction.e[i] > 0 ) // CULL BACK FACE
      t.e[i] = ( min.e[i] - ray.startPos.e[i] ) / ray.direction.e[i] ;
    else
      t.e[i] = ( max.e[i] - ray.startPos.e[i] ) / ray.direction.e[i] ;
  }

  int mi = t.maxIndex() ;
  if( BetweenIn( t.e[mi], 0, ray.length ) )
  {
    Vector pt = ray.at( t.e[mi] ) ;

    // check it's in the box in other 2 dimensions
    int o1 = ( mi + 1 ) % 3 ; // i=0: o1=1, o2=2, i=1: o1=2,o2=0 etc.
    int o2 = ( mi + 2 ) % 3 ;

    return BetweenIn( pt.e[o1], min.e[o1], max.e[o1] ) &&
           BetweenIn( pt.e[o2], min.e[o2], max.e[o2] ) ;
  }

  return false ; // the ray did not hit the box.
}

Related Solutions

Why would anyone choose not to use the lowlatency kernel?

The different configurations, “generic”, “lowlatency” (as configured in Ubuntu), and RT (“real-time”), are all about balancing throughput versus latency. Generic kernels favour throughput over latency, the others favour latency over throughput. Thus users who...

How can I update all Snap packages?

sudo snap refresh Will do this. It is part of snapd 2.0.8, which landed 2016-06-13 in xenial-updates. snap refresh --list Only lists the updates without refreshing the packages. snap info <snap name> Can show which versions are available for a particular...

What does Controls.Add() do in c#? [closed]

Controls is an instance of Control.ControlCollection class, which represents a collection of Control objects, Inheritance hierarchy is System.Windows.Forms.Control.ControlCollection Note: The Add, Remove, and RemoveAt methods enable you to add and remove...

How can I change the date modified/created of a file?

As long as you are the owner of the file (or root), you can change the modification time of a file using the touch command: touch filename By default this will set the file's modification time to the current time, but there are a number of flags, such as the -d...

How to read dmesg from previous session? (dmesg.0)

Although a bit late for the OP... I use Fedora, but if your system uses journalctl then you can easily get the kernel messages (dmesg log) from prior shutdown/crash (in a dmesg -T format) through the following. Options: -k (dmesg) -b < boot_number > (How...

Get data on daily basis in laravel

You can use the existing Laravel cron job scheduling to fulfill your specific requirement. Please refer following Laravels official documentation https://laravel.com/docs/5.8/scheduling#scheduling-queued-jobs I'll show a simple example to get an idea about this...

Python speed testing – Time Difference – milliseconds

datetime.timedelta is just the difference between two datetimes ... so it's like a period of time, in days / seconds / microseconds >>> import datetime >>> a = datetime.datetime.now() >>> b = datetime.datetime.now() >>> c = b...

Discovering metadata about a PDF

One of the canonical tools for this is pdfinfo, which comes with xpdf, if I recall. Example output: [0 1017 17:10:17] ~/temp % pdfinfo test.pdf Creator: TeX Producer: pdfTeX-1.40.14 CreationDate: Sun May 18 09:53:06 2014 ModDate: Sun May 18 09:53:06 2014...

How can I search within the output buffer of a tmux shell?

copy mode search To search in the tmux history buffer for the current window, press Ctrl-b [ to enter copy mode. If you're using emacs key bindings (the default), press Ctrl-s then type the string to search for and press Enter. Press n to search for the same...

Often big numbers become negative

This image shows what you're looking for. In your case it's obviously larger numbers, but the principle stays the same. Examples of limits in java are: int: −2,147,483,648 to 2,147,483,647. long: -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 In the...

null pointer exception in java servlet [closed]

I got a "null pointer exception" fault in java servlet. Could someone tell me what happens? And how to avoid that? That happens when you're trying to access/invoke some reference which is actually null. SomeObject someObject = null; someObject.doSomething(); //...

How to set ulimits on service with systemd?

The mappings of systemd limits to ulimit Directive ulimit equivalent Unit LimitCPU= ulimit -t Seconds LimitFSIZE= ulimit -f Bytes LimitDATA= ulimit -d Bytes LimitSTACK= ulimit -s Bytes LimitCORE= ulimit -c Bytes LimitRSS= ulimit -m Bytes LimitNOFILE= ulimit -n...

Does compression option -z with rsync speed up backup

It's a general question. Does compression and decompression at endpoints improve the effective bandwidth of a link? The effective (perceived) bandwith of a link doing compression and decompression at endpoints is a function of: how fast you can compress (your...

How to pre-download items from a JSON list array in React JS?

You can insert <link rel="prefetch"> elements into the <head> of the page. This will tell the browser to go ahead and download the thing that it finds in the src property of that element so that it can be served from the cache if something else on...

C programming: Use of undeclared identifier [closed]

There are a lot of error in this program. In c programming, before using a variable, we must explicitly declare the type of data that it can store. So you must define the type of x and y to integer type (int x = 10,int y=12). The next thing is that you are...