Homogenous, Normalized Device Coords and clipping

OpenGL
1

Hi!
I’m implementing my own OpenGL library.
When I multiply vertex coordinates on modelview matrix and projection matrix I get homogenous coordinates, then if I divide them on w I get Normalized Device Coordinates (NDC).

If vertex coordinates(NDC) is inside clipping frustum it should be in [-1, 1] interval for x,y and z. Using this rule I implemented 3D Cohen-Sutherland algorithm.

But this approach do not work in some cases.

When I draw triangle in front of near plane, absolute value of NDC are more then one but they sometime have different signs and triangle is visible(it intersects clipping frustum) but it should not.

Example:

glViewport(0, 0, WIDTH, HEIGHT);

glMatrixMode(GL_PROJECTION);	
glLoadIdentity();		
gluPerspective(45.0f,(GLfloat)WIDTH/(GLfloat)HEIGHT, 5.0f , 10.0f);


    glBegin(GL_TRIANGLES);
    glVertex3f(0,   1,    0);
 	    glVertex3f(-1,  -1, - 4 );
    glVertex3f(1,   -1,   0);
    glEnd();

NDC:

x1 = 0 y1 = 2.4 z1 = -20
x2 = -0.2 y2 = -0.6 z2 = -2
x3 = 1.8 y3 = -2.4 z3 = -20

in front of near plane
clip all triangle

move
glTranslatef(0, 0, 0.5);

NDC:
x1 = 0 y1 = -4.8 z1 = 43
x2 = -0.5 y2 = -0.6 z2 = -2.7
x3 = -3.6 y3 = 4.8 z3 = 43
triangle intersect frustum and partialy visible

why z1 and z2 changed signs???

triangle is in front of near plane and invisible.
I get strange artifacts in my scene.
I thoroughly check my matrix math - it is Ok.

May be I do not understand how homogenous coordinates work?
Please help.

2

When I multiply vertex coordinates on modelview matrix and projection matrix I get homogenous coordinates, then if I divide them on w I get Normalized Device Coordinates (NDC).

When you apply the modelview and projection matrices to a vertex you get clip coordinates. This assumes that you are using homogeneous coordinates already, i.e. that your vertex has a fourth component (w) that is originally 1. If you divide by w after applying modelview and projection you get NDC, as you correctly point out.

If vertex coordinates(NDC) is inside clipping frustum it should be in [-1, 1] interval for x,y and z.

This is correct.

When I draw triangle in front of near plane, absolute value of NDC are more then one but they sometime have different signs and triangle is visible(it intersects clipping frustum) but it should not.

Example:

glViewport(0, 0, WIDTH, HEIGHT);

glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluPerspective(45.0f,(GLfloat)WIDTH/(GLfloat)HEIGHT, 5.0f , 10.0f);

glBegin(GL_TRIANGLES);
glVertex3f(0, 1, 0);
glVertex3f(-1, -1, - 4 );
glVertex3f(1, -1, 0);
glEnd();

NDC:

x1 = 0 y1 = 2.4 z1 = -20
x2 = -0.2 y2 = -0.6 z2 = -2
x3 = 1.8 y3 = -2.4 z3 = -20

in front of near plane

Your near and far plane are [5,10]. This triangle is not in front of near plane? It would seem corrent that this triangle gets clipped.

move
glTranslatef(0, 0, 0.5);

NDC:
x1 = 0 y1 = -4.8 z1 = 43
x2 = -0.5 y2 = -0.6 z2 = -2.7
x3 = -3.6 y3 = 4.8 z3 = 43
triangle intersect frustum and partialy visible

why z1 and z2 changed signs???

triangle is in front of near plane and invisible.

The triangle should not be partially visible, it would seem that all the vertices are still outside the frustum.

3

Yes. Though using the correct names for OpenGL spaces, this is better stated, when I multiply OBJECT-SPACE coordinates with the MODELVIEW and PROJECTION matrices, I get homogeneous CLIP-SPACE coordinates…

then if I divide them on w I get Normalized Device Coordinates (NDC).

Exactly.

If vertex coordinates(NDC) is inside clipping frustum it should be in [-1, 1] interval for x,y and z. Using this rule I implemented 3D Cohen-Sutherland algorithm.

But this approach do not work in some cases.

When I draw triangle in front of near plane, absolute value of NDC are more then one but they sometime have different signs and triangle is visible(it intersects clipping frustum) but it should not.

Yes, this problem is why it does not make sense to clip in NDC. Not to mention that if you have a poly that comes through with a z_eye=0, your divide-by-0 generates an infinity blow-up.

This is why OpenGL clips in (aptly-named) CLIP-SPACE, which is what you called homogeneous coordinates. If you clip here, then you don’t have to deal with infinity blow-ups and weird sign flips.

Why does your sign flip happen? For a perspective projection, w_clip = -z_eye. For objects in front of the eye, z_eye is negative, so w_clip yields a positive number, so the divide-by-w does not flip the sign of the coordinate. But for objects “behind” the eye, z_eye is positive and so w_clip is negative, so divide-by-w “does” flip the sign of the coordinate.

Just google for “homogeneous clipping” and you’ll get right to it. But essentially, whereas in NDC-SPACE you would have clipped to this:

-1 <= (x/w,y/w,z/w) <= 1

in CLIP-SPACE, you clip to this:

-w <= (x,y,z) <= w

4

Thank you for a good explanation of my problem!

5

And what to do with vertex with w = 0 (when others ! = 0)?

6

Clipped away by the near plane. Recall w_clip = -z_eye for perspective, so this is the case where something is at the same eye-space depth as the eyepoint.

7

Hi again!
You mentioned about this inequality -w <= (x,y,z) <= w.
May be I should use absolute value of w?
-|w| <= (x,y,z) <= |w|
Is it correct?

8

No, it isn’t. If clip space W is negative the vertex should be clipped.

9

Hi!

If W > 0 I find intersection of line with clipping frustum with the simple formula:

P_i = P1 + Aplha*(P2 - P1).

if line intersect right clip plane we have:
x_i = x1 + Alpha*(x2 - x1)
w_i = w1 + Alpha*(w2 - w1)

In the point of intersection x_i should be equal to w_i,
so we have equation:

x1 + Alpha*(x2 - x1) = w1 + Alpha*(w2 - w1)

from it I find Alpha and then w_i and x_i.

if W1 < 0 and W2 < 0 I ckip line.

But what should I do to find intersection point if W1 < 0 but W2 > 0?

Please help.

10

When W1 < 0 and W2 > 0:
If I will find intersection of line with w = 0 plane, how to transform point with w = 0 from homogeneous to image space?

11

I don’t think it makes any sense to talk about a w = 0 plane, or a w = anything plane. w is not an orthogonal dimension, it is the ratio of a distance along a ray. x, y, and z (in Cartesian space) define an orthogonal basis, but w is not like x, y, or z because it is a ratio of a distance of a point along the ray from (0, 0, 0) to a point (x, y, z). [See footnote.]

It does make sense to talk about a z = 0 plane, however. The z = 0 plane is the plane that the viewpoint lies on. Everything on the z = 0 plane should be clipped (because the z_near plane should have a value greater than zero, and it should be a value greater than zero because nothing on the z = 0 plane can be visible except at the viewpoint itself (which will have infinite projected size)).

I don’t see any point in calculating the intersection of a line with the z = 0 plane. I do see sense in calculating the intersection of a line with the z = z_near plane.

Footnote: The fact that the projection matrix typically stores z (or -z) in w (rather than the distance between (x, y, z) and (0, 0, 0)) is why the divide-by-z perspective projection is a distorted projection. But it’s fast, simple, and the distortion is not usually terribly objectionable and that’s why it’s used.

12

david_f_knight, thank you for thoroughly explanation.

“I do see sense in calculating the intersection of a line with the z = z_near plane.”

But how to calculate intersection point with z = z_near if signs of w are different? It may be when one point of line is behind of of the eye and second in front of the eye. Now I discard whole line in this case, but it is not correct.

if w > 0 I use -w <= (x,y,z) <= w for clipping
if w < 0 is it correct to use inequality w <= -(x,y,z) <= -w ?

13

You just do plane clipping in 4D space and it all works out. You’re not using the above inequality to select algorithm branches.

Concepts

Basic “3D” equation of a plane:

AX + BY + C*Z + D = 0

Now we plug in homogenous coordinates to convert it to 4D:

A*(x/w) + B*(y/w) + C*(z/w) + D = 0, aka
Ax + By + Cz + Dw = 0

So if we take the std 3D plane equation coefficients and multiply (dot product) by a homogenous 4D point, we’ve actually evaluated the plane equation just as we did in 3D by plugging in for X,Y,Z. If the result is 0, the point is on the plane. And if the result is not 0, then its sign determines which side of the plane it’s on.

Adopt one plane convention. Usually + = inside, - = outside.

Plane-Line Intersection

For Plane-Line intersection, look at the technique that Blinn outlines in Down the Graphics Pipeline, Chapter 13. Plug the parametric representation of the line:

p(t) = (p2-p1)*t + p1

into the 4D homogeneous plane equation:

Ax + By + Cz + Dw = 0

and solve for t:

               A*x + B*y + C*z + D*w    = 0
               [A,B,C,D] * [x,y,z,w]    = 0
               P * p(t)                 = 0       P = [A,B,C,D]
               P * [ (p2-p1)*t + p1 ]   = 0
               P * [(p2-p1)*t] + P * p1 = 0
               t = (-P * p1) / (P * p2 - P * p1))
               t = (-P * p1) / (P * p2 - P * p1))

If you find the t, plug it in to get the 4D intersection point. This Plane-Line intersection is then used by the next step.

Plane-Polygon Clipping

For clipping a polygon (set of ordered points) to a plane, you can use Sutherland-Hodgman or some other technique. You just clip the poly to a single plane in 4D, and store off the resulting clipped ordered edge points.

Plane-Frustum Clipping

Then clipping the polygon to all frustum planes is basically just looping over all planes and repeatedly calling the previous poly-clip-to-plane routine you wrote. The 6 4D clip planes being:

( -1, 0, 0, 1 ), // X = 1 (-x+w=0; X< 1 is inside)
( 1, 0, 0, 1 ), // X = -1 ( x+w=0; X>-1 is inside)
( 0,-1, 0, 1 ), // Y = 1 (-y+w=0; Y< 1 is inside)
( 0, 1, 0, 1 ), // Y = -1 ( y+w=0; Y>-1 is inside)
( 0, 0,-1, 1 ), // Z = 1 (-z+w=0; Z< 1 is inside)
( 0, 0, 1, 1 ) }; // Z = -1 ( z+w=0; Z>-1 is inside)

14

I was interested in this - do you know of any demo or paper that describes this? Could we do the correct distance ourselves manually in a vertex shader now?

15

No, I don’t know of any demo or paper that describes it, and you can’t fix the distortion in the vertex shader. The reason the vertex shader can’t fix it is that straight lines may need to be drawn curved (oddly enough). That means to avoid the distortion, all lines must be tessellated so that they can be drawn curved. In other words, you may be able to correct this distortion in the tessellation evaluation shader.

I can describe the distortion a bit for you, since it seems odd that straight lines should be drawn curved. Imagine a long fence of uniform height that runs perpendicular to the line of your view. Note that all Z coordinates of the fence will all be the same (since the fence is perpendicular to the line of your view, and we are assuming +X points to your right and +Y points up, just like in OpenGL’s eye coordinate space). With the divide by Z perspective projection, no matter how far away the fence goes to your right or to your left from your viewpoint, it will be drawn with a fixed height… even if the fence is light years long, it will be drawn at fixed, uniform height everywhere. Your own experience in the real world should tell you that in reality the further away an object is from your viewpoint, the smaller it will appear regardless of the angle it is from your line of vision. A fence light years away from your eye will in reality appear so small that not even the Hubble telescope could ever see it. In other words, with divide by Z perspective projection, perspective is a function of the angle an object is off the viewing axis, whereas in reality, true perspective is only a function of how far away an object is from the viewpoint and has nothing to do with the angle of view.

The reason this distortion is not usually a really huge problem is because it is a function of view angle. The narrower your view angle, the less of this off-axis distortion is drawn. However, if you try rendering a scene with a very wide view angle, the distortion is very pronounced. The distortion is also pronounced, even with narrower view angles, when you rotate the scene and notice that long rectangles as they approach perpendicularity to the line of view don’t “feel” right.

The reality is this distortion involves our perception. Our brains “know” a fence or a very tall building or a road or railroad tracks are straight, so even though our eyes see curved lines, our brains tell us we are seeing something straight and so we perceive them as straight (furthermore, it is an issue with off-axis angles, and we focus our attention at the center of our field of vision). But you can conduct simple tests to convince yourself this is true. You have to train yourself to be aware of your peripheral vision as you look straight ahead, perpendicular to something that really demonstrates the phenomenon like a long fence or a skyscraper (i.e., any rectangle with a really big aspect ratio).

However, even though our brains perceptually “correct” for the curved lines our eyes see, they actually require the correct visual input. If you look at a computer generated scene with the distortion, your eyes aren’t seeing the curved lines that they would see in the real world view of the same scene, and so when your brain “corrects” for the curved lines that aren’t there, things just feel a bit off.

Another issue about trying to correct for this distortion is that a scene should be viewed from the distance it was rendered for. That is, if you render a scene with a 30 degree field of view, and then place the monitor at a distance from your eye so that you are viewing your monitor with anything other than a 30 degree field of view, then there is a mismatch in perspectives. That is to say, it appears distorted. The greater the mismatch, the greater the distortion.

To really play around with this, you need to do fairly unusual things, such as project the rendered scene onto a dome (like a planetarium) or onto a circular screen (like in Disneyworld, I believe, and some other theme parks where the screen goes 360 degrees around you), or just render with a huge field of view, such as 180 degrees. If you use a divide by Z perspective projection and draw straight lines straight and then show them in the environment just described, you will see really terrible distortion and that the scenes are horribly unrealistic.

Edit: I should add that this off-axis distortion I’ve described is not restricted to huge aspect ratio rectangles that are perpendicular to the line of view. It really affects everything the further it is off the line of sight, especially the closer it is to the near plane. It’s just easier to recognize this distortion with such rectangles.

16

OK thanks, that was a good description.

17

Actually the division by z is the mathematically correct way to project from 3D on a 2D plane. Other formulas are needed if you want to project on other shapes, but usually a 2D plane is a pretty good approximation for a monitor.

The effect described above (things further away should look smaller, even if they have the same z coordinate) does exist because our eyes are (more or less) spherical and not planar, but you have to consider that the corners of the monitor are also further away from your eyes than the center (esp. if you have an infinite monitor), so theoretically you would have to compensate the distortion of the viewer, which exactly cancels out the proposed distortion on the screen.

18

mbentrup, most of what you wrote is true, but I have to nitpicking about the “exactly cancels out the proposed distortion on the screen” :
This is true only if the virtual FOV is the same as the real FOV, between your eye and the monitor, that means it is almost never the case. This more around 30° rather than 70°-90°. And it only works if the eye is exactly on the imaginary line going out of the center of the screen.

19

You’re right of course, but if you want to get a mathematically exact projection you’d do it by adjusting the FOV, not by changing the projection equations…

20

Indeed, but I do feel that sometimes you want to provide a large FOV on a (too small) flat screen, and “fish-eye effect” spherical projection has some strong points, such as less visible distortion. The bad point is the curved straight lines.

M.C. Escher intuitively found this solution too :
http://www.clowder.net/hop/persp/persp.html