Hi ! I need to calculate AABB of intersection of convex hull (defined by set of planes) with AABB. Any elegant solution to solve this problem ? :) Thanks ! Petr

Convert the AABB to a convex hull, do a boolean intersection between the two and calculate the AABB of the product of that.

Thats the obvious one, if you don't so much care for "tightness" or accuracy, you could calculate the AABB of the hull and then calculate the intersection of the two AABBs.

Thanks Kwizatz,
I forgot to mention that AABB of intersection should be as tight as possible
(and possibly calculated as fast as possible)
What I am doing now is basically what you suggest - brute force calculation
of boolean intersection - but the "brute force" is not what I call elegant :)

I do following (and I don't like it)

1) convert AABB to polygons
2) clip polys from 1) by convex hull + calculate AABB of result
3) convert convex hull to polygons (ouch !)
4) clip polygons from 3) by AABB chull planes + calculate AABB of result
5) accumulate AABBs from 2) and 4)

Any improvements ?

Thanks !
P.

Yes,

Convert AABB to Planes.

IF you have the convex hull also as polygons (and hopefully have edge data not to duplicate operations on neighbor polygons):

Clip each edge of the hull with the AABB planes
Save the generated points
Calculate the AABB off the saved points which will include edge intersection with any of the planes if so as well as any edge points that ended up inside the AABB.

ELSE IF you only have a collection of planes:

add the planes of the AABB to the planes of the hull and threat it as a single hull, convert to points and calculate the AABB off of that collection of points.

Add suggestion 1)

What about situation when AABB is completely inside convex hull ? After clipping
I get nothing to calculate AABB of intersection volume from.

Add suggestion 2) (AABB + planes only is my case)

After adding planes from AABB to chull it can obviously form non convex volume.
I don't think I can calculate meaningful set of points from set of arbitray planes (and I don't get why it should represent points of convex volume representing intersection).

P.

Quote:Original post by born49
Add suggestion 1)

What about situation when AABB is completely inside convex hull ? After clipping
I get nothing to calculate AABB of intersection volume from.

No, you still should end with the 8 points of the AABB, remember that planes have infinite surface, so unless all points are on one side of the plane, at least one edge will intersect the plane.

If a all points are on the positive side of one of the planes, the 2 do not intersect, and thus there is no AABB.

Quote:Original post by born49
Add suggestion 2) (AABB + planes only is my case)

After adding planes from AABB to chull it can obviously form non convex volume.
I don't think I can calculate meaningful set of points from set of arbitray planes (and I don't get why it should represent points of convex volume representing intersection).

How would it form concave volumes? you have to think of planes as half spaces, imagine you have a huge cube, and the collection of planes for the convex hull, if you begin slicing the cube using the planes such that each new "cut" creates a new face on the cube, in the end you get the convex hull, now, what happens if you keep slicing away using the planes of the AABB? well, you get the intersection of both, that is, the volume common to both.

In order to then calculate the AABB of this intersection you only need the points (actually you only need the support points on the 6 directions of the axis), you don't really need polygon or edge information.


Solution 1 is really the same as solution 2, but is slightly more efficient since by already having edge information you have already "carved" the convex hull out of the huge cube, so you don't have to do it again.

[Edited by - Kwizatz on February 5, 2008 2:23:55 PM]

hey

I haven't properly read through this thread yet, but I think Separation Axis Theorem (SAT) may help :). It's an algo for convex polyhedron collision detection, and I think it's quite well known.

I can't really remember how it works and such, so I'll try dig up some articles/tutorials for ya. It's probably worth ya googling about it also.

Anyhows here is what I was quickly able to find...

N Tutorials - Collision Detection and Response: This looks very nice, although I've only had a quick look.

Here are a couple of threads on these forums I found while googling (although it's probably worth doing another search through the forums), separating axis theorem, and Axis Separation Theorem Troubles....

Finally this is a thread from another forum, see actionscript.org - Separation Axis Theorem.

Anyhows I hope this helps.

cyas