Simple Intersection Tests For Games
March 21, 2019
Press Releases
March 21, 2019
Games Press

If you enjoy reading this site, you might also want to check out these UBM Tech sites:

# Simple Intersection Tests For Games

[]

October 18, 1999 Page 6 of 7

An OBB-Line Segment Test

Testing a box and a line segment for intersection requires checking only six separating axes: the box's three principal axes, and the vector cross products of these axes with l, the line direction. Again, the vectors used for these tests do not have to be normalized, and these tests can be simplified by transforming the line segment into the box’s coordinate frame.

One application of this test is to see if a camera's line of sight is obscured. Testing every polygon in a scene could be prohibitively expensive, but if these polygons are stored in an AABB or an OBB tree, a box-segment test can quickly determine a potential set of polygons. A segment-polygon test can then be used to determine if any polygons in this subset are actually obscuring the line of sight.

The function in Listing 7 assumes the line segment has already been transformed to box space.

Listing 7.

#include "aabb.h"

const bool AABB_LineSegmentOverlap
(

const VECTOR& l, //line direction
const VECTOR& mid, //midpoint of the line
// segment
const SCALAR hl, //segment half-length
const AABB& b //box

)

{

/* ALGORITHM: Use the separating axis
theorem to see if the line segment
and the box overlap. A line
segment is a degenerate OBB. */

const VECTOR T = b.P - mid;
VECTOR v;
SCALAR r;

//do any of the principal axes
//form a separating axis?

if( fabs(T.x) > b.E.x + hl*fabs(l.x) )
return false;

if( fabs(T.y) > b.E.y + hl*fabs(l.y) )
return false;

if( fabs(T.z) > b.E.z + hl*fabs(l.z) )
return false;

/* NOTE: Since the separating axis is
perpendicular to the line in these
last four cases, the line does not
contribute to the projection. */

//l.cross(x-axis)?

r = b.E.y*fabs(l.z) + b.E.z*fabs(l.y);

if( fabs(T.y*l.z - T.z*l.y) > r )
return false;

//l.cross(y-axis)?

r = b.E.x*fabs(l.z) + b.E.z*fabs(l.x);

if( fabs(T.z*l.x - T.x*l.z) > r )
return false;

//l.cross(z-axis)?

r = b.E.x*fabs(l.y) + b.E.y*fabs(l.x);

if( fabs(T.x*l.y - T.y*l.x) > r )
return false;

return true;

}

OBB to AABB conversion

Converting an OBB to an AABB merely involves calculating the extents of the OBB along the x, y, and z-axes of its parent frame. For example the extent of the OBB along the x-axis is

The extents along the y and z-axes are calculated similarly.

Page 6 of 7

### Related Jobs

Giant Enemy Crab — Seattle, Washington, United States
[03.20.19]

Gameplay Engineer
Embodied Inc. — Pasadena, California, United States
[03.20.19]

Junior Scripter
FoxNExt Games — San Jose, California, United States
[03.20.19]

Producer
Retro Studios - Nintendo — Austin, Texas, United States
[03.20.19]

Art Director - RETRO Studios