Gamasutra is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Gamasutra: The Art & Business of Making Gamesspacer
Simple Intersection Tests For Games
View All     RSS
May 19, 2019
arrowPress Releases
May 19, 2019
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

Dream Harvest
Dream Harvest — Brighton, England, United Kingdom
[05.18.19]

Technical Game Designer
Rockstar Games
Rockstar Games — Edinburgh, Scotland, United Kingdom
[05.17.19]

Facial Animator
Insomniac Games
Insomniac Games — Burbank, California, United States
[05.17.19]

Director, Art Management
DigiPen Institute of Technology
DigiPen Institute of Technology — Redmond, Washington, United States
[05.17.19]

Assistant Profesor





Loading Comments

loader image