Gamasutra: The Art & Business of Making Gamesspacer
Simple Intersection Tests For Games
View All     RSS
June 26, 2017
arrowPress Releases
June 26, 2017
Games Press
View All     RSS






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


 
Simple Intersection Tests For Games
by miguel gomez []

October 18, 1999 Article Start Previous Page 6 of 7 Next
 

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.


Article Start Previous Page 6 of 7 Next

Related Jobs

Bluehole
Bluehole — Seongnam si , Korea, South
[06.26.17]

Sr. Character Animator
Telltale Games
Telltale Games — San Rafael, California, United States
[06.25.17]

Associate Cinematic Artist
UBM Tech
UBM Tech — San Francisco, California, United States
[06.23.17]

General Manager, Game Developers Conference
Disruptor Beam
Disruptor Beam — FRAMINGHAM, Massachusetts, United States
[06.23.17]

Director, User Acquisition





Loading Comments

loader image