PDA

View Full Version : OpenGL clipping how is it done ?



nicolasbol
11-15-2009, 09:39 PM
Guys,

I've tried to Google this but I cannot figure out how it's done.
Let's take a real example and try to do everything by hand:

Here is a triangle on screen ( I know it looks like a quad but it looks like this because of the perspective and the third point is far on the side:

http://fabiensanglard.net/doomIphone/clipping.jpg


With the following matrix PVM:



Matrix pvm.
-----------------
-2.4651 0.0000 -2.6528 117.7031
0.0000 2.4142 0.0000 0.0000
-0.7399 0.0000 0.6876 -50.6078
-0.7325 0.0000 0.6807 -30.2037
-----------------



And the following triangle:



face[0] = [-130 , 50 , 200 , 1].
face[1] = [-100 , 0 , 200 , 1].
face[2] = [-100 , 0, -200 , 1].



We get the canonical Space coordinate:



canSpace[0] = [-92 , 121 , 183 , 201]
canSpace[1] = [-166 , 0 , 161 , 179]
canSpace[2] = [895 , 0 ,-114 ,-93]



After the W divide:



wdivide[0] = [-0.459 , 0.600 , 0.910 , 1.000].
wdivide[1] = [-0.928 , 0.000 , 0.898 , 1.000].
wdivide[2] = [-9.611 ,-0.000 , 1.226 ,1.000].



We move to unit cube (+1 and * 0.5 )



p1 unitCube[ 0.27 , 0.80 , 0.910133 , 1.00]
p2 unitCube[ 0.04 , 0.50 , 0.897879 , 1.00]
p3 unitCube[ -4.31 , 0.50 , 1.225966 ,1.00]



And finally the viewPort transform ( my iPhone screen is 320*480)




p1 screen[ x=86.52 , y=384.01, z=0.910133 ].
p2 screen[ x=11.48 , y=240.00, z=0.897879 ].
p3 screen[ x=-1377.83 ,y=240.00 , z=1.225966].



This triangle is partially on screen, 2 vertices are on screen with the third way off. I believe the hardware is generating two new vertices ( according to "real time rendering" book, this is done in unit cube space).

But I have no idea how it is done. Aynbody can enlight me on this one ?

Dark Photon
11-16-2009, 06:52 PM
I've tried to Google this but I cannot figure out how it's done. ...

This triangle is partially on screen, 2 vertices are on screen with the third way off. I believe the hardware is generating two new vertices ( according to "real time rendering" book, this is done in unit cube space).

But I have no idea how it is done. Aynbody can enlight me on this one ?

Google homogenous clipping. Also see Sutherland-Hodgman polygon clipping. GPU clipping takes place in 4D space (aptly named "clip coordinates") before the perspective divide.

I don't understand why you're calling clip coordinates "canonical space" coordinates. That's not an OpenGL term.

nicolasbol
11-17-2009, 07:15 AM
Hey photon,



I don't understand why you're calling clip coordinates "canonical space" coordinates. That's not an OpenGL term.


Thanks for correcting this.

I realize now that I asked the question very poorly. I knew of "Sutherland-Hodgman" but my problem is actually that the coordinate I'm getting in clipping space don't make sense for applying this algorythm:

For example the point far on the right ends up having a negative x value in Clipping Coordinate System. So I am not sure how to apply "Sutherland-Hodgman" in this context.

I've read a bit in Graphic Gems 2 (http://books.google.com/books?id=tQn2pILgt9wC&lpg=PA219&ots=ydyrNlnz4H&dq= homogenous%20clipping&pg=PA225#v=onepage&q=&f=fals e):

Figure 4 on page 225 show that it is related to the negative w component. The clipping equation are supposed to be changed but I do not understand how.

I was also thinking of just inverting x,y,z to reflect the invert pyramid structure of the projection but it may not make sense.

Or maybe use the region mapping here to get x and y coordinate right:
http://medialab.di.unipi.it/web/IUM/Waterloo/node51.html

Anyway, "homogenous clipping" is giving much better results, thanks ;) !

EDIT: So, after more reading, it seems that after the homogeneous division it is impossible to distinguish between points which were originally behind and in front of the eye. So part of the clipping should be done before the w divide.

Dark Photon
11-17-2009, 07:12 PM
EDIT: So, after more reading, it seems that after the homogeneous division it is impossible to distinguish between points which were originally behind and in front of the eye. So part of the clipping should be done before the w divide.
Not just part. All of it.

Besides the point you mentioned, remember that the perspective divide will cause blow-ups (divide by 0) at the plane of the eye. You've got to get rid of that.

To give you some insight on doing 4D clipping, keep in mind that after the perspective divide, where you're ending up (NDC) is the 2-unit cube:

-1 < x/w < 1
-1 < y/w < 1
-1 < z/w < 1

So, before the perspective divide (clip coordinates)...:

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

nicolasbol
11-18-2009, 08:30 PM
Wow, found a gem that really helped me to see clearer:

http://research.microsoft.com/pubs/73937/p245-blinn.pdf

It's CLIPPING USING HOMOGENEOUS COORDINATES, the famous paper by James F. Blinn Caltech/JPL and Martin E. Newell XEROX/PARC

nicolasbol
11-19-2009, 08:39 PM
I think I am getting close to a full algorithm:

Polygon comes in modelSpace.
Generate Clipping Space coordinate via pvm * vertices.
Then w (perspective) divide to be in 2-unit cube.

Check what is the state of the polygon against the 2-unit cube:

OUT: Discard
IN: No need to clip, calculate signed area ; >0 -> rasterizer, <0 discard (not facing)
INTERSEC: Need to clip.

Clipping is done in 4D, against clipping space coordinate.

In order to remove external line and have only internal lines, project any vertices with w < 0 into w=0 space:

This can be done by finding a vertice in the polygon with w > 0:

p1 x,y,z,w (with w < 0), the point to project into w=0
p2 x,y,z,w (with w > 0)

IntersectionPoint I = P1 + t( P2 - P1)

In W space, this give:

0 = w1 + t( w2 - w1) ;
t = w1 / (w1 / w2)

Transform any point with w < 0 with this formula.

Now that we have all points with w >= 0 we can clip against 4D planes.

For every 6 plans RIGHT,LEFT,TOP,BOTTOM,NEAR,FAR:

Classify all vertices in the polygon as "in" the visible half-space or "out".

Now for each edge in the polygon, check if the edge cross the plan.

If both vertices are in: inject into output stream.
If both vertices are out: discard
If edge intersect (in and out): clip against plan (find intersection in 4D) and inject previously in vertices and new vertice I in output stream.

Top plane intersection: t = ( w1 - y1) / (( w1 - y1) - ( w2 - y2) )
Bottom plane intersection: t = ( w1 + y1) / (( w1 + y1) - ( w2 + y2) )
Left plane intersection: t = ( w1 + x1) / (( w1 + x1) - ( w2 + x2) )
Right plane intersection: t = ( w1 - x1) / (( w1 - x1) - ( w2 - x2) )
Near plane intersection: t = ( w1 - z1) / (( w1 - z1) - ( w2 - z2) )
Far plane intersection: t = ( w1 + z1) / (( w1 + z1) - ( w2 + z2) )

The output result of the clipping against a plan is used as input for the other plan.

Then perform w divide on each vertices of the polygon and calculate the signed area: >0 ->rasterizer, <0 discard.

So far, it looks like it should work.

Kelvin
12-11-2009, 12:03 AM
Wow, found a gem that really helped me to see clearer:

http://research.microsoft.com/pubs/73937/p245-blinn.pdf

It's CLIPPING USING HOMOGENEOUS COORDINATES, the famous paper by James F. Blinn Caltech/JPL and Martin E. Newell XEROX/PARC

I'm saving that one -- but if you liked it, and still want more, I highly recommend:

"Jim Blinn's Corner: A Trip Down the Graphics Pipeline" (by James Blinn, naturally), that does an excellent job of discussing homogenous coordinate clipping in a compact but still accessible way, as well as a number of other topics.

ugluk
12-17-2009, 02:12 AM
What I always wondered is not how clipping is done, but what happens with the quads and other multisided-polygons that may come about because of it. Are they triangulated and sent further down the pipeline?

As I understand it, a scissor test could also reject a fragment belonging to a clipped region of a rendered polygon.

Frodak
12-17-2009, 03:13 PM
The OpenGL specification allows any polygons or quads to be triangulated; doesn't matter if it is clipped or not. I think almost all H/W decomposes polygons into triangles.

As for scissoring; I don't understand what you are saying. The NDC volume is mapped to the window as according to the viewport settings. No fragments are generated outside this region so there would be no fragments to scissor (at least for polygons, lines and points are different).