|
Building a 3D Portal Engine - Issue 07 - 2D & 3D Clipping: Sutherland-Hodgeman by (12 February 1999) |
Return to The Archives |
Introduction
 |
|
I'm getting very positive feedback on my column, as well as some very constructive comments - Thanks! As I wrote to some of you, that sort of feedback is what keeps me going. :) Besides more elementary stuff like money... ;) Last week I promised to explain clipping. Specifically, Sutherland-Hogdeman clipping. When I say 'last week', I mean 'a long time ago', since I'm writing this column in bursts... :) By the time you read this, incredible cool stuff: the next few issues, are waiting already in the hands of Kurt Miller, the Site Guru of flipCode (Editor's Note: Yep, Jacco has been way ahead in writing this column since the first issue!). Rest assured that this kind of delays do not happen in the coding of my 3D engine, Focus, wich is kindly hosted by the same dude... Anyway. Sutherland-Hodgeman clipping allows you to draw graphics that are larger than the screen. In the old days when you used Pascal, or worse: Basic, a line would be drawn correctly, even if it was partially of-screen. Well, no-more. C++ is fast because it assumes that you know what you're doing. If you never cared why a line is drawn correctly when it's partially off-screen, you basically don't know what you're doing. The code is (in that case) doing things that you didn't know it did, and that's bad, because you could probably do it faster yourself. I'm trying to refrain from Microsoft-bashing here... :) Before I go into the details of 2D and 3D clipping, I first want to spend some words on what you can actually do with clipping. We got at this subject because the wire-cube was causing problems when it came too close, but solving that problem is just one application. If you implement the 3D version of the clipper, you can do lots of nifty things with it. At first, you'll probably want to use it to do Z=0 clipping: Objects that are very close will not just fall of the screen, they cause mayhem in the perspective formulas too. At the moment that Z (the depth of a vertex) changes sign, the screen coordinates will do the same, causing polygons to appear as random large nails on your screen. This can be solved by clipping the polygons against a plane, close to Z=0. Another cool thing to do with 3D clipping is an 'inside view' of an object: Define a plane that cuts an object in half, and you can see right in the internals of it. Nice for medical graphics. Or, for the guys who are desperately waiting for stuff related to portal engines, you can illuminate stuff with 3D clipping. Just define your light source as a set of planes, and make every polygon that is inside this volume brighter. Adding shadows this way is also possible, but that's less straight-forward. I promise I'll get back on that subject. 3D clipping is also important for true portal rendering: If you encounter a portal in your scene, you could make the view volume smaller, by calculating planes from the camera viewpoint to the edges of the portal. That way you can be sure that anything that is behind the portal is actually clipped against the portal, resulting in zero overdraw. More on that later too. OK, back to the actual implementation (well, close). Consider the following image:  In this picture, the screen is represented by a green rectangle. As you can see, the four-sided polygon is partially of-screen, at the top of the screen and at the right side. If we would clip appropriate portions off, we would be left with a six-sided polygon. This is quite easy to determine for a human being, but how do we explain this to the computer? Well, simple: Here's an algorithm for it. Imagine you have two tables with vertices. The first table contains four vertices, the original ones. The second table is going to contain the vertices of the clipped polygon. The clipping is done against a screen boundary at a time; let's start with the top. The polygon is processed per edge; each edge is then categorized: Where 'in' means in this case: Below the top boundary of the screen, and 'out' means above the top boundary. Per case, the following data is written in the second table: If you try this on a piece of paper, you'll see that after you did this for all four edges, the second table contains the vertices of the clipped polygon, in the correct order. Do this for all four screen boundaries; the input for the second boundary is the output of the first. This algorithm is the so-called Sutherland-Hodgeman clipping algorithm. One question remains: How do you determine the intersection point of an edge with a screen boundary? Well, simple: First determine the distance of the two vertices to the screen boundary. The signs of these values can be used to determine wich case should be applied. The amount of the edge that is 'out of screen' can be calculated with this formula:
So, if the first vertex is at screen coordinate (50, 10) and the second one is at (70, -20), the distances can be determined as follows:
Now this 'portion' can be used to determine the intersection point:
Where v1 is the first vertex, and v2 the second one. Thus:
Which is indeed the correct intersection point. To clip texture coordinates, you do exactly the same:
But now the first problem shows up. You are clipping U/V coordinates linearly, but texture coordinates aren't linear in screen space, due to perspective. This can be solved by performing the clipping in 3D. In that case, you should define your view window as a set of planes, starting at the camera viewpoint, and going through the screen edges: Basically a pyramid shape. Planes can be expressed with 'plane equations', of the form Ax+By+Cz=D (revert to the previous article (culling) if you want to know more about plane equations). Now the distances of vertices can simply be determined by filling in the 3D coordinates in this plane equation:
After you have applied 3D clipping to the polygons in your scene, you can be sure that you can draw them without problems in 2D space. That's all for now. If you have problems with this stuff, let me know. I'll be glad to explain a bit more. |