Sign in to follow this  
RPTD

AABB boundary of a round cone

Recommended Posts

I want to do some speed ups by dropping lights which are not visible on the screen using the OcclusionQuery extension in OpenGL. For this putting a light into an AABB seems to me the best approach. The problem I have now is how to obtain a correct AABB for a spot light. The spot light is a cone out of a sphere and hence has a round base not a flat one. I first tried checking all axes ( and their negative ) to be inside the cone and using this to create the AABB. This works as long as the cone always has one axis inside but otherwise fails. For this case I don't know how to do it. I first tried putting up an equation to solve by finding an equation for the rim of the cone ( | point - center | = radius, and, ( point - center ) dot spot_direction = cos( angle ) * radius ) but then I can't narrow it down to one point ( as the rule would be 'point.x is the smallest' which doesn't fit in an equation ). I thought then about using a SAT test using a plane moving from outside the cone ( distance > radius ) towards the cone. Problem there is that I am not sure how to correctly project the cone circle to the SAT axis ( it should still be a circle or already an ellipse? ). I assume the sat approach would be the fastest but so far I could not get it to work. Some help would be appreciated.

Share this post


Link to post
Share on other sites
What you probably want is a support function for the cone. Using this you could find the minimum and maximum projection along each cardinal axis (optimized of course due to the axis-alignment) and compute the AABB from these.

I think the support function can found in Gino van den Bergen's SOLID library, among other places. You might be able to download an older (free) version of this library.

The general idea is that the apex of the cone is the support point if the angle between the query axis and cone base plane is greater than the cone angle (the angle between the cone axis and its sides); if the query axis is parallel to the cone axis and directed toward the base, the support point is any point on the base; if the axis is perpendicular to the cone sides there are technically multiple support points, but this can be grouped with the last case, which is that the support point is on the edge of the cone base. To find this point, project the query axis onto the cone base plane and find the support point for the circle with respect to the projected axis (now a 2D problem).

Ok, that was a terrible explanation, but maybe it'll get you moving in the right direction. As for the apex of the cone being spherical, it seems that the apex case could be replaced with computing the support point of the apex sphere with respect to the query axis. That's just a guess though (although it seems reasonable).

This all sounds somewhat involved, but I imagine the actual implementation would be fairly efficient (especially since it's the cardinal axes we're interested in).

Share this post


Link to post
Share on other sites
Ok, just trying to get the hang on this. So in general if I don't happen to end up with the simple case I mentioned above ( axis inside cone ) then I need to project the axis onto the base plane and then intersect with the circle there, right? What about the orientation? So if I have a cone which is defined by a center, a direction, a radius and an opening angle I have theoretically an infinite number of base planes ( all coincidental but with different tangent direction ). Would this do us any harm ( I assume not but am not sure right now )?

Share this post


Link to post
Share on other sites
There's only one base plane, but I think I know what you mean - you're talking about establishing a coordinate system in which to solve the 2D circle support point problem.

Anyway, you don't need to. Here, I'll try to whip out some pseudo-code:
// We've already determined that the support point is on the
// cone base edge, so we know the following won't fail (specifically
// the normalization). First, we project 'v' (the query axis) onto the
// cone base plane (defined by the cone axis 'n'):
vector3 v_proj = v - dot(v,n) * n;

// Normalize it:
v_proj.normalize();

// Scale it by the cone base radius:
v_proj *= r;

// Let 'c' be the cone center, and 'h' be the half height. Now we can
// compute the support point:
p = c - n * h + v_proj;
That's just off the top of my head, but you might give it a try and see if it works.

Share this post


Link to post
Share on other sites
Let the cone have vertex C, unit-length axis A, and angle s which is measured from the cone axis to the cone wall. The cone cap is formed by a sphere with center C and radius r. The intersection of the cone and the sphere is a circle whose center is C+h*A, where h = r*cos(s). The radius of the circle is p = r*sin(s). Let U and V be unit-length vectors so that U, V, and A are mutually perpendicular. A parametric representation of this circle is
X(t) = (C+h*A) + d*(cos(t)*U + sin(t)*V)
for 0 <= t < 2*pi. I will come back to this formula later.

For a specified unit-length direction D, you want to compute the extreme point E on your "rounded cone" in the direction D. Cases:

1. E is on the spherical cap. This happens when the ray with origin C and direction D intersects the spherical cap, which occurs when Dot(D,A) >= cos(s). The extreme point is E = C + r*D in this case.

2. E = C. This occurs when the angle between D and A is at least (s + pi/2) radians. When the angle is exactly (s + pi/2), imagine the cone lying tangent to the plane containing C and having normal D. The cone is on the side of the plane to which -D points. The algebraic condition is Dot(D,A) <= cos(s + pi/2).

3. E is on the circle. This is the only other possibility, so the angle condition is cos(s + pi/2) < Dot(D,A) < cos(s).

The difficult case is the last one. You need to compute the extreme point E on a circle in the direction D. This point must be chosen to make the vector (E-C) as close as possible to the direction D. That is,you need to maximize
Dot(D,X(t)-C) = h*Dot(D,A) + d*(cos(t)*Dot(D,U) + sin(t)*Dot(D,V))

The term h*Dot(D,A) does not vary with the circle parameter t, so it is enough to maximize the last term. This happens when
(cos(t),sin(t)) = (Dot(D,U),Dot(D,V))/|(Dot(D,U),Dot(D,V))|
The extreme point is then
E = (C+h*A) + d*(Dot(D,U)*U + Dot(D,V)*V)/|(Dot(D,U),Dot(D,V))|
Notice that
Dot(D,U)*U + Dot(D,V)*V = (U*U^T + V*V^T)*D = (I - A*A^T)*D
where I is the identity matrix, the superscript T denotes tranpose, and
|(Dot(D,U),Dot(D,V))| = |(I - A*A^T)*D|
Although U and V were convenient for the mathematical construction, you do not actually have to compute them in a program. In summary, the extreme point on the circle is
E = (C+r*cos(s)*A) + r*sin(s)*(I - A*A^T)*D/|(I - A*A^T)*D|
which of course depends solely on the cone/sphere parameters and the direction D. You can choose D = (+-1,0,0), D = (0,+-1,0), and D = (0,0,+-1) for your axis-aligned bounding box construction.

Share this post


Link to post
Share on other sites
Aside from the fact that Wasting Time's answer is much more thorough than mine (I was pressed for time, for which I apologize) I should mention that I misread the original post, in that I interpreted the problem in terms of a flat base and a rounded apex. Re-reading your post and looking through Wasting Time's example I see that it was in fact a rounded base, not apex, that you had in mind, so my earlier responses (in addition to being somewhat rushed and unclear) don't apply.

Sorry about that.

Share this post


Link to post
Share on other sites
I tried to follow those equations but at the beginning something is looking odd to me. Let's take a cone which point somewhere in the Y-Z plane ( with Y pointing up and Z pointing into the screen ) and we want to test X. Case 1 does not hold true as is case two ( if I understand this right ). Hence we are up with case 3, picture:


You state in your first equation that we need to find the point E which has the property that the vector E-C is "closest" to D. This point would be "1" in my figure. But the point we are looking for is "2" which is not the closest to D but points "farthest" into the direction of D.

Somehow jyk looked more reasonable to me. In the end it does not matter if we are up with a round cone or a flat cone because of what Wasting Time said above. If case 1 applies then using the sphere to determine the farthest point is enough ( round cap case ). In all other cases only the circle interests us which is the same for a round or a flat base.

Share this post


Link to post
Share on other sites
Quote:
Original post by RPTD
You state in your first equation that we need to find the point E which has the property that the vector E-C is "closest" to D. This point would be "1" in my figure. But the point we are looking for is "2" which is not the closest to D but points "farthest" into the direction of D.


Yes, I used the wrong word. The maths is correct, though. Dot(D,X(t)-C) are the projections of the circle points onto the direction D. You want E to be that X(t) point that maximizes the projections ("farthest" along D).

Share this post


Link to post
Share on other sites
So far what goes for the first equation I get this:
Dot(D,X(t)-C) = h*Dot(D,A) + d*(cos(t)*Dot(D,U) + sin(t)*Dot(D,V))

But then I don't get it anymore. Why the second equation?
(cos(t),sin(t)) = (Dot(D,U),Dot(D,V))/|(Dot(D,U),Dot(D,V))|

dot(D,U) and dot(D,V) are scalar values along D. So why do they suddenly end up in a 2D coordinate system, more precisely the coordinate system of the circle? They are projections and no more part of the circle plane there ( hence comparing cos(t) and sin(t) beeing circle coordinates with projection scalars ).

Also this line I don't get:
Dot(D,U)*U + Dot(D,V)*V = (U*U^T + V*V^T)*D = (I - A*A^T)*D
I would like to understand what I implement and not just C&P.

EDIT: Hm... the boxes look a bit strange but maybe it is correct.

[Edited by - RPTD on October 10, 2006 4:38:04 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by RPTD
But then I don't get it anymore. Why the second equation?
(cos(t),sin(t)) = (Dot(D,U),Dot(D,V))/|(Dot(D,U),Dot(D,V))|

dot(D,U) and dot(D,V) are scalar values along D. So why do they suddenly end up in a 2D coordinate system, more precisely the coordinate system of the circle? They are projections and no more part of the circle plane there ( hence comparing cos(t) and sin(t) beeing circle coordinates with projection scalars ).


You are trying to maximize a function of the form f(t) = a*cos(t) + b*sin(t). You can write this as a dot product of two vectors: f(t) = Dot((a,b),(cos(t),sin(t)). To make the dot product as large as possible, you want to choose t so that (cos(t),sin(t)) is parallel to (a,b) and in the same direction as (a,b). Since (cos(t),sin(t)) is a unit-length vector, your only choice is (cos(t),sin(t)) = (a,b)/Length(a,b).

Quote:

Also this line I don't get:
Dot(D,U)*U + Dot(D,V)*V = (U*U^T + V*V^T)*D = (I - A*A^T)*D
I would like to understand what I implement and not just C&P.

EDIT: Hm... the boxes look a bit strange but maybe it is correct.


The set {U,V,A} is an orthonormal basis. Any vector Y can be written as Y = y0*U + y1*V + y2*A, where y0 = U^T*Y, y1 = V^T*Y, and y2 = A^T*Y, where W^T denotes the transpose of the column vector W. Then

Y = U*y0 + V*y1 + A*y2 = U*U^T*Y + V*V^T*Y + A*A^T*Y = (U*U^T + V*V^T + A*A^T)*Y

This equation is true for all Y, so it is necessary that U*U^T + V*V^T + A*A^T = I, the identity matrix. Subtract to get U*U^T + V*V^T = I - A*A^T.

Share this post


Link to post
Share on other sites
Forgive me if I'm completely wrong here, but isn't calculating a AABB from a cone with hemisphere (aka icecream), as simple as:

// position - cone tip
// direction - cone normal
// length - length of cone in direction of normal
// radius - radius of cone at base (radius of hemisphere)
float3 end = position + direction * length;
float3 min = end - radius;
float3 max = end + radius;
min = Min(min, position); // Minimum component-by-component of a float3
max = Max(max, position); // Maximum component-by-component of a float3

Share this post


Link to post
Share on other sites
Quote:
Original post by hogwash
float3 min = end - radius;
float3 max = end + radius;
I assume 'float3' is a 3D vector type? If so, the above expressions represent a subtraction of a scalar from a point, which doesn't make sense.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Quote:
Original post by hogwash
float3 min = end - radius;
float3 max = end + radius;
I assume 'float3' is a 3D vector type? If so, the above expressions represent a subtraction of a scalar from a point, which doesn't make sense.


Sorry for the confusion, I should have been more clear there. My math library has the above operators defined.

Change to:
float3 v3Radius(radius, radius, radius);
float3 min = end - v3Radius;
float3 max = end + v3Radius;

... for clarity.

Am I right?

Share this post


Link to post
Share on other sites
Quote:
Original post by hogwash
Quote:
Original post by jyk
Quote:
Original post by hogwash
float3 min = end - radius;
float3 max = end + radius;
I assume 'float3' is a 3D vector type? If so, the above expressions represent a subtraction of a scalar from a point, which doesn't make sense.


Sorry for the confusion, I should have been more clear there. My math library has the above operators defined.

Change to:
float3 v3Radius(radius, radius, radius);
float3 min = end - v3Radius;
float3 max = end + v3Radius;

... for clarity.

Am I right?
If your math library defines addition and subtraction between a vector and a scalar, then (IMO) you should fix your math library :)

As for the proposed algorithm, I'm pretty sure it will fail given certain parameters for the cone (e.g. a high radius-to-height ratio).

Share this post


Link to post
Share on other sites
Well that's obviously a matter of opinion ;-)

It doesn't adhere to mathematical semantics, but it saves having to construct a vector for the rhs value.

We are making games right? :-)

Share this post


Link to post
Share on other sites
Quote:
Original post by hogwash
Well that's obviously a matter of opinion ;-)
I suppose so :-)
Quote:
It doesn't adhere to mathematical semantics, but it saves having to construct a vector for the rhs value.
Hm :-| If you're referring to performance, it seems unlikely that you would encounter this particular case often enough in practice for it to make any difference. If you're referring to less typing, then you're saving a little effort at the expense of proper semantics, which doesn't seem like a good trade to me.
Quote:
We are making games right? :-)
Even in game programming I would say that expressiveness, correctness, and clarity of intent are more important than saving a few keystrokes or cycles here and there.

But as you said, it is a matter of opinion :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this