Re: [Algorithms] Clipping against OBBs

[<ro...@do...>]

Doug Chism  wrote:

>Does anyone know of any good code sources for fast clipping of
>lines/triangles against OBBs? I guess the idea would be to pull the planes
>out of the OBB and clip against them - something along that line of thought?
>If you are keeping track of the Center, Corner, Axes, Normalized Axes, and
>Half Size, whats the fastest way to get the 6 plane equations of the OBB
>from that ( or if cheaper/faster clipping approach available is there info
>on that? )
>

Not sure exactly what is your distinction between "Axes" and
"Normalized Axes", but let's suppose that by Normalized Axes you mean
the three mutually orthogonal unit vectors A1, A2, A3 that give the
orientation of the box, and you have these in world coordinates. These
vectors are also, of course, unit normals to the six faces of the box.
Similarly, "Center" means the world coordinate components of the
center point of the box.  And let w1, w2, w3 be the corresponding
half-widths.  Then the equations of the six face planes of the box are

	Ai dot P = (Ai dot Center) [+-] wi  
i=1,2,3.

where P= (x,y,z) gives the world coordinates of a general point on the
plane. 

Note that the vector Ai points to the outside of the box on the plane
you get with the + sign and -Ai points to the outside of the box on
the plane that you get with the - sign.

If you do not already have nice software clipping code for the
axis-aligned unit cube, or even if you do have it but "fast" is very
important,  then I would suggest  ignoring Nicholas Serres' suggestion
to transform the tri vertices to box coordinates.  Rather I would just
use a 3D Sutherland-Hodgman implementation for the triangle clipping.
You can find pseudo code for the 2D S-H in Foley et al. Generalization
to 3D is a pretty straightforward application of your elementary 3D
vector function library.  

S-H consists just of successively clipping all the edges of the
polygon against each of the face planes of the box, keeping track of
the fact that your clipped triangle can become a quadrilateral,
prntagon, or  hexagon in the process.  The pseudo code in Foley et al
should be clear enough on that part.

So how do you clip an edge against a plane? I take the trouble to
address this elementary geometry problem only because  there is a
possible optimization that doesn't exist for the general convex
clipping volume to which S-H applies.  This optimization results from
the fact that the clipping volume is a rectangular box, so the
clipping planes fall into three parallel pairs, 

 Letting V0, V1 be the position vectors of the endpoints of the edge,
and plugging the parametric expression for the line containing the
edge
 P = V0 + t(V1 - V0) 
into the equations for the two box faces perpendicular to the 1-axis,
then doing a little elementary vector algebra manipulation gives.

 tplus    = (A1 dot Center + w1 - A1 dot V0)/(A1 dot V1- A1 dot V0) 
 tminus = (A1 dot Center - w1  - A1 dot V0)/(A1 dot V1- A1 dot V0)

for the parameter values where the line crosses the two parallel
planes.  Note that the four  dot products and sums and differences to
be computed in the two expressions are the same (except for the sign
of w1), so they only have to be computed once for the two planes.
Moreover, if you are doing this for lots of triangles and edges, note
that A1 dot Center is just a property of the box and so the same for
all the triangles and edges.

Now you just have to compare tplus and tminus with 0 and 1 and each
other to get the edge as clipped by the two parallel planes:

First, it is easy to see that if 
 A1 dot (V1 - V0) = A dot V1 - A dot V0
 is positive, then tplus >= tminus, else tplus <= tminus.

Considering the case that 
 A1 dot (V1 - V0) 
is positive,  we have the possibilities:

tminus <= 0 < 1 <= tplus:  Edge lies entirely between the two planes,
so is not clipped.

tminus < tplus < 0 :   Edge lies entirely outside the box, so drop it.

1 < tminus < tplus:  Edge lies entirely outside the box, so drop it.

timinus < 0 <= tplus <= 1: Clipped edge is 
   [V0, V0+tplus(V1 - V0)]

0 <= tminus < tplus <= 1:  Clipped edge is
   [V0+tminus(V1-V0), V0+tplus(V1-V0)].

0<= tminus <=1 < tplus:  Clipped edge is
 [V0+tminus(V1-V0), V1].

I leave the case  that A1 dot (V1 - V0) is negative as an exercise for
the reader.   Same for understanding the meaning of the singular case
that this dot product is zero.

Take the result of the above clipping and clip that segment against
the two A2 planes, then iterate again for the two A3 planes. 

The same optimization can be worked into the full 3D S-H algorithm for
the triangle clipping.