gdalgorithms-list

[Algorithms] finding an optimal OBB

[Charles B. <cb...@cb...>]

I'm sure there are lots of papers on this - any
good pointers?  I want to find the tightest
possible OBB for a collection of points.

--------------------------------------
Charles Bloom           www.cbloom.com

Re: [Algorithms] finding an optimal OBB

[Corrinne Y. <cor...@ho...>]

Your savior and mine, magic source code.
http://www.magic-software.com/MgcContainment.html
Thank you, Dave E. My Dave E. book is on its way, and am looking forward to
it.

The math here (Ron L. would have to correct me if I were wrong about this)
is better / more correct than most on-line tutorials, papers and algorithms.

Corrinne Yu




----- Original Message -----
From: "Charles Bloom" <cb...@cb...>
To: <gda...@li...>
Sent: Thursday, August 03, 2000 2:01 PM
Subject: [Algorithms] finding an optimal OBB


>
> I'm sure there are lots of papers on this - any
> good pointers?  I want to find the tightest
> possible OBB for a collection of points.
>
> --------------------------------------
> Charles Bloom           www.cbloom.com
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] finding an optimal OBB

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

Corrinne Yu  wrote:

>Your savior and mine, magic source code.
>http://www.magic-software.com/MgcContainment.html
>Thank you, Dave E. My Dave E. book is on its way, and am looking forward to
>it.
>
>The math here (Ron L. would have to correct me if I were wrong about this)
>is better / more correct than most on-line tutorials, papers and algorithms.
>

Indeed, Dave Eberly is an authority, his web site is authoritative and
has lots of good stuff. 

RE: [Algorithms] finding an optimal OBB

[Akbar A. <sye...@ea...>]

btw corrinne,
did you ever get an update from pixar?

peace.
akbar A.

"We want technology for the sake of the story, not for its own sake. When
you look back, say 10 years from now, current technology will seem quaint"
Pixars' Edwin Catmull.


-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of
Corrinne Yu
Sent: Thursday, August 10, 2000 8:47 AM
To: gda...@li...
Subject: Re: [Algorithms] finding an optimal OBB


Your savior and mine, magic source code.
http://www.magic-software.com/MgcContainment.html
Thank you, Dave E. My Dave E. book is on its way, and am looking forward to
it.

The math here (Ron L. would have to correct me if I were wrong about this)
is better / more correct than most on-line tutorials, papers and algorithms.

Corrinne Yu




----- Original Message -----
From: "Charles Bloom" <cb...@cb...>
To: <gda...@li...>
Sent: Thursday, August 03, 2000 2:01 PM
Subject: [Algorithms] finding an optimal OBB


>
> I'm sure there are lots of papers on this - any
> good pointers?  I want to find the tightest
> possible OBB for a collection of points.
>
> --------------------------------------
> Charles Bloom           www.cbloom.com
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list


_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] finding an optimal OBB

[Dave S. <Dav...@sd...>]

Yeah. Another $50 dollar book I need to buy
only for a reference.  I liked his old site
better.  :-(

I assume you read the paper on OBBTree's.
I don't have it with me or I'd give you the 
reference.

They talked about sampling the convex hull to
find a tighter fit bbox. 

I don't know what MgcContainment does, if that's
similar or not.

-DaveS


Corrinne Yu wrote:
> 
> Your savior and mine, magic source code.
> http://www.magic-software.com/MgcContainment.html
> Thank you, Dave E. My Dave E. book is on its way, and am looking forward to
> it.
> 
> The math here (Ron L. would have to correct me if I were wrong about this)
> is better / more correct than most on-line tutorials, papers and algorithms.
> 
> Corrinne Yu

[Algorithms] Clipping against OBBs

[Doug C. <dc...@d-...>]

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? )

Doug Chism

Re: [Algorithms] Clipping against OBBs

[Nicolas S. <nic...@ch...>]

I personally store OBBs as :
- center
- normalized axis
- half width

This is not the best choice for size, but althought I consider it gives the
best speed compromise for my applications of OBBs. Althought my primary
concern was culling against planes of the view frustrum and occluding
volumes, I was also using them for test purposes as you do.. There is a
pretty nice algorithm here
http://www.cs.unc.edu/~hoff/research/vfculler/boxplane.html. This deals with
testing an OBB against planes, so not your application, but I really like
his approach, and it might apply to your case too, so it's worth reading. I
used techniques based on this one very agressively and it is _really_
effective.

If you are interested in plane equation, you almost have it in that format;
axis being plane normals; you have (a,b,c) of ax+by+cz+d=0. I prefer to
store them with normalized axis because I consider it is the best compromise
for my different applciations of OBBs. But if you almost always work with
the planes of the obb, you might want to replace box center+half width with
"d" values. It might be less easier to use if your OBB is frequently
transformed.

But anyway, if you already have a functional software clipping pipeline, the
easiest way is to express your world coordinates in bbox coordinates (the
transformation is straightforward if you have obb axes). Using half
width/normalized axis makes you clip against (-half_width,+half_width).
Using "tweaked" (1 / half_width) non normalized axis makes you clip against
(-1,+1). The latests seems easier, especially if you already have a working
homogenous clipping pipeline. You just have to set w to 1, and care about
the (z<-w) issue (and not z<0 as usal)... It even allows you to use
extremely efficiently some buggy SIMD instructions that are not well suited
for classical frustrum clipping, but are perfectly suited for that.

If you do that, you will need to store extra information (which is basically
the inverse of the world->box space transformation previously stored) to be
able to transform your clipped results into viewport space (which is, I
suppose your final goal). As my code that did the clip was
ultra-experiental-debug-stuff, I did a brute force matrix inversion, and I
definitely don't recommend it!


----- Original Message -----
From: "Doug Chism" <dc...@d-...>
To: <gda...@li...>
Sent: Monday, August 14, 2000 10:20 PM
Subject: [Algorithms] Clipping against OBBs


> 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? )
>
> Doug Chism
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] Clipping against OBBs

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

Nicolas Serres  wrote:

>I personally store OBBs as :
>- center
>- normalized axis
>- half width
>
>.....
>If you are interested in plane equation, you almost have it in that format;
>axis being plane normals; you have (a,b,c) of ax+by+cz+d=0. I prefer to
>store them with normalized axis because I consider it is the best compromise
>for my different applciations of OBBs. But if you almost always work with
>the planes of the obb, you might want to replace box center+half width with
>"d" values.

Actually the "d" values of the equations of the planes of the box
faces are the negatives of the six values 
	(center dot normalized axis) [+-] half width
where there are three axes and three corresponding half widths,
assuming that you use "normalized axis" as the unit normal to each of
the two box faces perpendicular to it. 

> It might be less easier to use if your OBB is frequently
>transformed.
>
>But anyway, if you already have a functional software clipping pipeline, the
>easiest way is to express your world coordinates in bbox coordinates (the
>transformation is straightforward if you have obb axes). Using half
>width/normalized axis makes you clip against (-half_width,+half_width).
>Using "tweaked" (1 / half_width) non normalized axis makes you clip against
>(-1,+1). The latests seems easier, especially if you already have a working
>homogenous clipping pipeline. You just have to set w to 1, and care about
>the (z<-w) issue (and not z<0 as usal)... It even allows you to use
>extremely efficiently some buggy SIMD instructions that are not well suited
>for classical frustrum clipping, but are perfectly suited for that.
>
>If you do that, you will need to store extra information (which is basically
>the inverse of the world->box space transformation previously stored) to be
>able to transform your clipped results into viewport space (which is, I
>suppose your final goal). As my code that did the clip was
>ultra-experiental-debug-stuff, I did a brute force matrix inversion, and I
>definitely don't recommend it!
>

"Brute force"?? For inverting a matrix consisting of a rotation and
translation?  All you have to do is transpose a 3x3 and multiply a 3x3
by a 1x3.  Nothing to solve, and nothing I would call "brutish". 

Actually, when I do stuff like that in my code, I don't use matrices
at all, (and so have none to invert)  but just the functions of my
fast elementary vector algebra library.

For example, given a world coordinate vector V of a vertex, its 1-
component in box coordinates is just
	(V - box center) dot nomalized axis1
and similarly for the other two box coordinates of V.

Going the other way, given a point in box coordinates (B1, B2, B3),
its world x, y, z coordinates are the x, y, z coordinates of 

B1*normalized axis1 + B2*normalized axis2 + B3*normalized axis3 +
    box center.

where I am making the natural assumption that you have the normalized
axis vectors and box center in world coordinates.

Matrices are handy in some circumstances, especially when you have to
concatenate transformations,  and you do have to use them as arguments
to many 3D API calls, but don't get stuck in the rut of thinking you
HAVE to construct them and invert them and whatnot to effect EVERY
mapping that comes up in the computational geometry of your
application.  For lots of short, simple stuff, thinking in terms of
your elementary vector algebra library, which is much closer to the
geometric fundamentals,  is much better than thinking in matrices. You
end up doing exactly the same operations, but it is much easier to
figure out what those operations need to be when you keep the vector
geometric fundamentals in your mind, and just write them down in the
form of calls to your vector algebra library.

>----- Original Message -----
>From: "Doug Chism" <dc...@d-...>
>To: <gda...@li...>
>Sent: Monday, August 14, 2000 10:20 PM
>Subject: [Algorithms] Clipping against OBBs
>
>
>> 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? )
>>
>> Doug Chism
>>
>>
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

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.