PDA

View Full Version : Clipping triangles in clip space



urquidio
01-27-2007, 06:39 AM
Hi,

I'm working on a software implementation of
opengl and have a question about clipping
triangles.

from what i understand, you can perform the
clipping in clip space by comparing a point
to its w component, e.g.

-w < x < w
-w < y < w
-w < z < w

tells you the point is inside the clip space
if w is positive.

But when i have a triangle that i have
transformed by the projection matrix, the three
vertices will each have different w's. in fact,
their w terms will be equal to the negative of
their original z.

So how do you clip the triangle against the
side of the bounding box if all the w's are
different? which w do you use to set up the
bounding box? i don't understand how to have
different volumes for each point. how do
you clip the edges of the triangle then?

and if you normalize, to get them all
the same, what is the point of this "clip" space
then? after all, every book on the subject
seems to indicate that clipping occurs before
the perspective divide!

thanks for your help in advance!

Flavious
01-27-2007, 07:34 AM
Here's some source code: http://wwwx.cs.unc.edu/~sud/courses/236/a5/softgl_homoclip_smooth.cpp

You might also search for the Sutherland-Hodgman clipping algorithm and Homogeneous polygon clipping in general.

Hope it helps...

Cheers

cass
01-27-2007, 09:14 AM
If you just consider the 1D homogeneous case of (x,w), it's easier to visualize what you're doing.

In this case, you have a 2D plot with x on the horizontal axis and w on the vertical.

The clipping half-spaces are x LEQUAL w, which is everything on or to the left of a diagonal line of slope=1 going through the origin, and x GEQUAL -w, which is everything on or to the right of a diagonal line of slope=-1 also going through the origin.

Now imagine a line segment with endpoints p0 = (x0, w0) and p1 = (x1, w1), where p0 is inside the clip volume and p1 is outside. What you want to do is find the point along the line segment where it intersects the clip plane.

If we assume that the segment is clipped by the x LEQUAL w plane, then there is a point along the line segment that satisfies the plane equation x - w = 0, or {1, -1} when we write just the coefficients (as is typical in OpenGL).

First we compute the signed distance between each point and the plane (just a dot product).

d0 = dot(p0, clip_plane)
d1 = dot(p1, clip_plane)

Then, the lerp factor "a" for the point where distance is zero is

a = d0 / (d0-d1)

regardless of the sign of d0 and d1.

We use "a" to compute the new clipped vertex pc = (xc, yc, zc, wc) as

pc = (1-a) * p0 + a * p1

This new point will lie on the x=w line.
That is, xc == wc.

Does that make sense?

Cass

...ugh, I had to use LEQUAL and GEQUAL because the board rejects the symbols as illegal html tags. :(

[edit: fix lerp equation]
[edit2: fix graph description in paragraph 3]

Flavious
01-27-2007, 09:27 AM
Or if you look at it another way, parametrically, for example with your p0 and p1, and x for left/right:

xc = -/+ wc

or

p0.x + (p1.x - p0.x) * a = -/+ (p0.w + (p1.w - p0.w) * a)

and solve for a.

Same thing... :)

Cheers

cass
01-27-2007, 10:37 AM
Agreed, Flavious.

I actually wrote it down that way first, and changed it to the other because computing the clip distance first makes it clearer how things work for arbitrary clip planes.

Flavious
01-27-2007, 12:06 PM
I actually prefer the geometry you posted, Cass (give me the geometry every time :) ). I only added the other bit to hopefully explain what the linked code I posted is doing.

urquidio
01-30-2007, 09:41 AM
Thanks for your replies. They were very helpful. I was able to implement the clipping in clip-space as you describe.

However, I seem to be running in to a little problem when the triangles have points that are behind the viewer. in these cases, my w has a negative term. this means that my clip test is now wc < xc < -wc, correct? but the "left" plane is still xc = -wc and the right plane is still wc = xc, correct? So i believe that i don't need to change my equations that set xc = wc for the right plane and xc = -wc for the left plane when wc is negative. is this correct?

I think i'm thinking about this correctly, but for some reason i'm getting an incorrect output.

I thought i would simplify things by multiplying by a -1 if w was negative - to make w always positive - but this doesn't work. it seems that the points behind the viewer turn into points in front of the viewer and so i end up getting a portion of the triangle getting mapped to the screen even though it should be completely behind me... So we can't just flip the sign of the transformed point before clipping, correct?

what sort of issues should i be watching out for that could be causing problems with clipping with -w?

thanks

cass
02-01-2007, 09:52 AM
Cases where wc < 0 are guaranteed to fail the inequality because -wc < wc can never be true for negative wc, so no xc can be between them.

You shouldn't be doing any sign flipping of terms.

If you think about it, the "unclipped" part is where a V shape that starts at the origin on the 2D xw graph and goes up, so negative wc will always be clipped away.