Hi all :)

I'm having this problem, which I must solve in order to have my occlusion culling working.

Suppose I have a sphere in VIEW_SPACE. I wanna project it and obtain the CLIP_space coordinates of its bounding box.



Right now I'm doing this:
- project the center to obtain clip space
- project radius to obtain the "radius in clip space"
- extend the center clip space coordinates on the left (by substracting the radius) and on the right (by adding it).

But as you can see from the image, it works as far as the sphere in somewhere in the centre of the frustum. When it moves on a side, this method leads to an offset error, which I colored in yellow in the image. This because in this case the nearer part of the sphere is no longer the part I compute by adding the radius.

How could I resolve this ???

THANKS !

This doesn't even work when the sphere is centered (think of a large sphere and you'll see why). If I understand correctly, you want to find an axis-aligned rectangle on the screen that contains the projection of the sphere. To find one of its right side (the others are similar), you need to find a vertical plane that passes through the camera and is tangent to the sphere. I believe you can reduce the problem to 2D, but you have to be careful as to what plane you use (it should contain the camera and the center of the sphere, and be "horizontal", but as if you were looking at the sphere directly, not in the direction of the screen; see this for some pictures that illustrate this difference). Let me know if you have trouble doing the Math.

There is a way to do this kind of thing using the polar plane, but I will need some time to remember it.

You hit the nail on the head !!

Quote:Original post by alvaro
This doesn't even work when the sphere is centered (think of a large sphere and you'll see why).

God, this is true, you're right ! :'(

Quote:
If I understand correctly, you want to find an axis-aligned rectangle on the screen that contains the projection of the sphere.

Yes, a camera alligned rectangle that encompasses the whole projected sphere.

Quote:
To find one of its right side (the others are similar), you need to find a vertical plane that passes through the camera and is tangent to the sphere.

Yes, this sounds correct. But I think I gotta do this for each edge of the rectangle. Isn't it slow ?

Quote:
I believe you can reduce the problem to 2D

I don't know what you meant with this. All I would want is a fast procedure, since I'm doing this, for example, for each light in the frustum for each frame :(

Quote:
, but you have to be careful as to what plane you use (it should contain the camera and the center of the sphere, and be "horizontal", but as if you were looking at the sphere directly, not in the direction of the screen; see this for some pictures that illustrate this difference). Let me know if you have trouble doing the Math.

There is a way to do this kind of thing using the polar plane, but I will need some time to remember it.

I read the article, yes, the problem I'm talking about if shown in figure 4. Though the article lacks of maths. I'm already using billboards in my engine, but honestly I've never thought about this problem.

Well, I'm trying to figure out the maths by myself, but if you happen to have two minutes, I would really appreciate your help ;)

thank you !

-NiG

I thought you can decompose the problem in 2D space, like in the figure of the first thread, because the four planes I'm searching are 'vertical' and 'horizontal' in respect to the view space.

Viewed from above, for example, you drop the Y component and the problem reduces in finding the intersection between a circle (centered somewhere) and a line passing through the origin.

Anyway, I'm having troubles with the math :(

Quote:Original post by NiGoea
Anyway, I'm having troubles with the math :(

Things would appear simpler if you look at the angles. Let us measure the angles from the vertical axis. Let:
1) alpha: the angle(s) between the vertical axis and the lines that are tangent to the circle.
2) beta: the angle between the vertical axis and the line through the center of the circle.
3) theta: the angle between the line tangent to the circle and the one that goes through the center of that circle.

We have two possibilities (in reality 3: if the circle contains the origin (the eye) there are no solutions):
1) alpha = beta + theta
2) alpha = beta - theta

Now, what are beta and theta?
Let c:(c_h,c_v) the center of the circle and r its radius. c_h: coordinate on the horizontal axis and c_v: coordinate on the vertical axis.
theta = arcsin(r/||c||) = arcsin(r/sqrt(c_h*c_h + c_v*c_v))
beta=arctg(c_h/c_v)//better use atan2(c_h,c_v)

We can notice that if r>||c|| there are no solutions because the viewpoint is inside the circle.

One of the most useful property of the projective space RP3 is that to any statement about incidence of points (planes) there is a corresponding dual statement about planes (points). A bounding box in clip space is defined by 4 half-spaces Xmin <= X, X <= Xmax, Ymin <= Y and Y <= Ymax. These half-planes are defined by the 4 tangent planes X - Xmin * W = 0, X - Xmax W = 0, Y - Ymin W = 0 and Y - Ymax W = 0. To find the parameters I will define the equation of the tangent planes to the sphere in clip space and then solve this equation to find Xmin, Xmax, Ymin and Ymax.

The equation of a quadric in the projective space RP3 is usually written in the form
(1) xT Q x = 0
where Q is a 4x4 symmetric matrix. This is invariant to projective transformation. Indeed, given a transformation A, the corresponding equation of the quadric in y = Ax is
(2) yT (A-T Q A-1) y = 0.

Two points x, y such that
(3) xT Q y = 0
are called conjugate which respect to the quadric (the points of the quadric are therefore the only points conjugate to themselves). The points conjugate to a point x build the polar plane of x which is the plane tangent to the quadric at x if x is a regular point of the surface. We describe a plane in RP3 by the homogeneous point u in (RP3)^* where the plane is given by the usual pairing <,> (the usual dot product)
(4) <u, x> = 0.
By (3) and (4), the equation of the polar plane is given by
u = Q x.
Thus by (2), the equation of the quadric in u is
uT (Q-T Q Q-1) u = 0,
(5) uT Q-T u = 0.

We now have all the ingredients to find the parameters Xmin, Xmax, Ymin and Ymax. We first have to find the equation of the quadric in clip space. To do it, we consider the transformation T which transforms the unit sphere to the sphere in view space and the projection P used to transform the view space to clip space. The matrix D = diag(1,1,1,-1) represents the unit sphere and using (1) and (2) we therefore obtain the equation
xT (P-T T-T D T-1 P-1) x = 0.
Using (5) we finally obtain the equation
uT (P-T T-T D T-1 P-1)-T u = 0,
uT (PT TT D-T T P) u = 0,
(6) uT (PT TT D T P) u = 0.
Let ri be the i-th columns of (P T), then the parameters Xmin and Xmax are the solutions of
(r1 + x r4)T D (r1 + x r4) = 0,
r1T D r1 + x (r1T D r4 + r4T D r1) + x2 (r4T D r4) = 0,
r1T D r1 + 2 x (r1T D r4) + x2 (r4T D r4) = 0
and the parameters Ymin and Ymax are the solutions of
(r2 + y r4)T D (r2 + y r4) = 0,
r2T D r2 + y (r2T D r4 + r4T D r2) + y2 (r4T D r4) = 0,
r2T D r2 + 2 y (r2T D r4) + y2 (r4T D r4) = 0,
To find the bounding box you therefore only need to solve two quadratic equation.

[Edited by - apatriarca on October 22, 2010 1:04:25 PM]

Hi, That's conceptually much more beautiful than te method I gave.

I'm having trouble understanding this:

Quote:Original post by apatriarca
uT (P-T T-T D T-1 P-1)-T u = 0,
uT (PT TT D-T T P) u = 0,

Shouldn't it be:
uT (P-T T-T D T-1 P-1)-T u = 0,
uT ((P-T T-T D T-1 P-1)T )-1 u = 0,
uT (P-T T-T DT T-1 P-1 )-1 u = 0,
uT ( P T D-T TT PT) u = 0 ?

I must add that -in the method you gave- one have to check if the sphere intersects the plane z=0 (in view space) because in this case the projection of the sphere on the screen would appear outside the bounding rectangle found i.e. that bounding rectangle should be clipped somehow. [smile]

Edit: corrected a typo

[Edited by - knighty on October 24, 2010 1:03:03 PM]

Quote:
Shouldn't it be:
uT (P-T T-T D T-1 P-1)-T u = 0,
uT ((P-T T-T D T-1 P-1)T )-1 u = 0,
uT (P-T T-T D T-1 P-1)-1 u = 0,
uT ( P T D-T TT PT) u = 0 ?

Yes, you are absolutely right.

Quote:I must add that -in the method you gave- one have to check if the sphere intersects the plane z=0 (in view space) because in this case the projection of the sphere on the screen would appear outside the bounding rectangle found i.e. that bounding rectangle should be clipped somehow.[smile]

I do not understand what you mean here.

Because if the sphere is partially behind the camera it will be transformed by the perspective matrix into an hyperboloid.

What I actually did't understood was how my method was different from other methods. I think this is a special case regardless of the method used to get the bounding box.