OpenGL sutherland-hodgman polygon clipping algorithm in homogeneous coordinates (4D, CCS)
Asked Answered
N

2

1

I have two questions. (I marked 1, 2 below)

In OpenGl, the clipping is done by sutherland-hodgman. However, I wonder how to work sutherland-hodgman algorithm in homogeneous system (4D)

I made a situation. In VCS, there is a line, R= (0, 3, -2, 1), S = (0, 0, 1, 1) (End points of the line) And a frustum is right = 1, left = -1, near = 1, far = 3, top = 4, bottom = -4 Therefore, the projection matrix P is

1    0    0   0
0   1/4   0   0
0    0   -2  -3
0    0   -1   0 

If we calculate the line with the P, then the each end points is like that

R' = (0, 3/4, 1, 2), S' = (0, 0, -5, -1)

I know that perspective division should not be done now, because if we do perspective division, the clipping result is not correct.

  1. Here I am curious. What makes a correct clipping because we did not just do perspective division. What mathematical properties are here?

  2. How to calculate the clipping result in above situation?

(The fact that two intersections occur in the w-y coordinate system makes me confused. I thought the result line is one, not divided two parts)

Nels answered 6/2, 2017 at 5:26 Comment(8)
The only difference between clipping in clipping space is, that the cube one clips against has a size of w instead of 1. Everything else works completely similar.Pantsuit
Let me explain the algorithm of sutherland-hodgman using the above situation. 1.the end points will be calculated by x = -w (left), x = w (right), and the end points would not be changed because the two points are in clipping area 2. if the end points pass y = -w, y = w, then there are two intersection points. Let P' be the point between R' and S', so the P' equal to R + t(S- R). In this situation, the intersection points are t = 11/15, 5 /9Nels
But Why the line is going to be split into two parts here? Perhaps the reason for this is related to the reason for not doing perspective division, but I do not know why. Anyway, let's continue. 3. if the two parts (0 <= t <= 5/9), (11/15 <= t <= 1) pass the z = -w, z = w, then the result is 0 <= t <= 1/3, so the clipping is done correctly. (the second part is removed)Nels
The point is this. Why does clipping work properly because I have not done perspective division? (I understand in NDCS, the clipping result could be wrong. why the CCS clipping is correct?) I want to know the mathematical and fundamental reason.Nels
Which formula did you use to calculate the perspective matrix? according to here, the first entry is `2*n/(r-l) = -2/2 = -1. The element in the second row seems to also have the wrong sign. It is also very uncommon to have negative near and far plane values (and I actually don't know whether this is possible).Pantsuit
Your example seems rather unclear to me. What are 1-4? Which endpoint do you want to calculate in 1?Pantsuit
Oh, I edited the wrong information. The near = 1 and far = 3 sorry to confuse you.Nels
You mention 1-4. I don't know your meaning. Maybe the procedure? I just explained the my example how to clipped in CCS and the t = 1/3 is the result. t = 1/3. The line(R'S') is clipped and the result is R'P', P' = R' + 1/3(S'- R'). P' = (0,1/2, -1, 1). Consequently, we obtain a line R' = (0, 3/4, 1, 2) P' = (0,1/2, -1, 1). Next, the openGL will do perspective division. R' = (0, 3/8, 1/2, 1) P' = (0,1/2, -1, 1)Nels
P
4

I'm not quite sure whether you understood the sutherland-hodgman algorithm correctly (or at least I didn't get your example). Thus I will prove here, that it doesn't make any difference whether clipping happens before or after the perspective divide. The proof is only shown for one plane (clipping has to be done against all 6 planes), since applying multiple such clipping operations after each other makes not difference here.

Let's assume we have two points (as you described) R' and S' in clip space. And we have a clipping plane P given in hessian normal form [n, p] (if we take the left plane this is [1,0,0,1]).

If we would be calculating in pure 3d space (R^3), then checking whether a line crosses this plane would be done by calculating the signed distance of both points to the plane and checking if the sign is different. The signed distance for a point X = [x/w,y/w,z/w] is given by

D = dot(n, X) + p

Let's write down the actual equation we have (including the perspective divide):

d = n_x * x/w + n_y * y/w + n_z * z/w + p

In order to find the exact intersection point, we would, again in R^3 space, calculate for both points (A = R'/R'w, B = S'/S'w) the distance to the plane (da, db) and perform a linear interpolation (I will only write the equations for the x-coordinate here since y and z are working similar):

x = A_x * (1 - da/(da - db)) + A_y * (da/(da-db))
x = R'x/R'w * (1 - da/(da - db)) + S'x/S'w * (da/(da-db))

And w = 1 (since we interpolate between two points both having w = 1)

Now we already know from the previous discussion, that clipping has to happen before the perspective divide, thus we have to adapt this equation. This means, that for each point, the clipping cube has a different scaling w. Lt's see what happens when we try to perform the the same operations in P^3 (before the perspective divide):

First, we "revert" the perspective divide to get to X=[x,y,z,w] for which the distance to the plane is given by

d = n_x * x/w + n_y * y/w + n_z * z/w + p
d = (n_x * x + n_y * y + n_z * z) / w + p
d * w = n_x * x + n_y * y + n_z * z + p * w
d * w = dot([n, p], [x,y,z,w])
d * w = dot(P, X)

Since we are only interested in the sign of the whole calculation, which we haven't changed by our operations, we can compare the D*ws and get the same inside-out result as in R^3.

For the two points R' and S', the calculated distances in P^3 are dr = da * R'w and ds = db * S'w. When we now use the same interpolation equation as above but for R' and S' we get for x:

x' = R'x * (1 - (da * R'w)/(da * R'w - db * S'w)) + S'x * (da * R'w)/(da * R'w - db * S'w)

On the first view this looks rather different from the result we got in R^3, but since we are still in P^3 (thus x'), we still have to do the perspective divide on the result (this is allowed here, since the interpolated point will always be at the border of the view-frustum and thus dividing by w will not introduce any problems). The interpolated w component is given as:

w' = R'w * (1 - (da * R'w)/(da * R'w - db * S'w)) + S'w * (da * R'w)/(da * R'w - db * S'w)

And when calculating x/w we get

x = x' / w';
x = R'x/R'w * (1 - da/(da - db)) + S'x/S'w * (da/(da-db))

which is exactly the same result as when calculating everything in R^3.

Conclusion: The interpolation gives the same result, no matter if we perform the perspective divide first and interpolation afterwards or interpolating first and dividing then. But with the second variant we avoid the problem with points flipping from behind the viewer to the front since we are only dividing points that are guaranteed to be inside (or on the border) of the viewing frustum.

Pantsuit answered 6/2, 2017 at 14:25 Comment(5)
Thank you for your explanation. How to derive this equation x = A_x * (1 - da/(da - db)) + A_y * (da/(da-db))? If you don't mind, can you explain this?Nels
Also, I wonder why CCS clipping solve the problem of NDCS clipping. I know NDCS clipping can be wrong, but I cannot understand why CCS work well. The difference between is just perspective division. Is there any perspective division magic?Nels
There is no magic. Just the usual rules that apply to inequalities when multiplying or dividing by negative numbers. -w < x < w can be false while -1 < x/w < 1 is true. Try, for example, x=4 and w = -5. Then --5 = 5 < 4 < -5 is false while -1 < -4/5 < 1 is true.Pantsuit
Hmm.. I thought -1 < -4/5 < 1 is wrong because we divided negative number, so -1 > -4/5 > 1 is correct, and thus the equation is also false. Wrong?Nels
Exactly this is the problem. But that's nothing a program would do automatically. You would have to implement a lot of special cases which are unnecessary if you clip before the divide.Pantsuit
I
0

You speak of polygon clipping in a homogeneous system (4D) but from your question I assume that you actually mean homogeneous coordinates, which makes a lot more sense. (There are many possible homogenous systems.)

Ok, so you want to use "4D" coordinates, which are really "3D coordinates and a w term". The w term represents (projection transformations) the projective term that partially relates the screen-space coordinate to the original world space position. Assuming that you are NOT interested in projective space clipping, this term is not relevant.

I'm assuming this because the clipping box you describe is axis-aligned on planes in 3D. Even if it was rotated or scaled in 3D space, each of the planes would still be a 3D plane, the 4th coordinate always being '1'.

So how to clip:

clip line segment L against each of the planes of the clipping box, i.e. 6 clipping planes in total (you describe the normals of each clipping plane aptly), and see if any intersection point v is shared by the line and the tested plane P so that

  • v lies on the line segment (i.e. a t between 0 and 1)
  • v lies within the bounds of the plane P (i.e. the coordinate should not lie beyond any of the adjacent planes. Since you are using axis-aligned clipping planes, this is easy to check.)

Any of these intersections between a (3D + w) line and one of the 3D planes occurs in 3D, and intersection points have to be a 3D coordinates. You can extend each of these coordinates with a 4th w coordinate into a "4D" coordinate so that you can further transform them using 4x4 matrices for view and projection processing.

Invar answered 6/2, 2017 at 12:45 Comment(2)
Isn't he exactly interested in perspective space clipping? Clipping always has to happen before the perspective divide, so the homogeneous coordinate will not be 1 here.Pantsuit
The title of the poster mentions Clipping Space, so yes, no perspective divide. Jim Blinn in ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=67707 mentions projective space clipping where the clipping box becomes a pyramid. Intersections move in and out of the view frustum, and take a bit of extra care to be sensible. More on this was published microsoft.com/en-us/research/wp-content/uploads/1978/01/…Invar

© 2022 - 2024 — McMap. All rights reserved.