3D Clipping

Clipping is used to avoid drawing polygons that are outside the screen and also chop them so that it doesn't pass the screen. You'll be thinking why would we want to chop every polygon why not just take it out if its completely out? Well, what if a polygon was very long. If it passed the screen by 400 pixels, you would probably get an error. Chopping polygons isn't too hard. Simply define a plane, find the plane normal and do the dot product of that normal vector with any point and you will get the distance from the plane. Do the same with a second point and get the distance. Add up the distances and that will be your total distance. Then divide the first distance by the total distance and you'll get the ratio at which the line hits the clip plane.

Now that you have the ratio, use the parametric equation of a line to find the point at which it hits the plane.

Parametric equation:

X = (initial point.x) + (ratio) * (direction.x)
Y = (initial point.y) + (ratio) * (direction.y)
Z = (initial point.z) + (ratio) * (direction.z)

Sub in the numbers and you will get the new point. This part isn't too bad. The harder part is to add that new vertex into the polygon.

As you see, a new vertex was added because one of the vertex was clipped. To do this, you must insert that new vertex and move every vertex after that up one.

3D Rotations

To do 3D rotations, the equation is very similar to 2D rotations except a rotation is done for every plane. Since 3D has 3 planes, the rotation must be done three times. The x-y plane is called roll, y-z plane is called pitch, and the x-z plane is called yaw.

To understand roll, pitch, and yaw, picture this. When you move your head up and down is called pitch. Put your left ear on your left sholder and then right ear on your right sholder, that is roll. Move your head horizontally side to side, that is yaw. A game like doom and wolfenstein, would only use the yaw rotation since you cannot look up or down.

Here are the equations to rotate a 3D point:

x'=z*sin(yaw)+x*cos(yaw)
y'=y
z'=z*cos(yaw)-x*sin(yaw)

x"=x'
y"=y'*cos(pitch)-z'*sin(pitch)
z"=y'*sin(pitch)+z'*cos(pitch)

x"'=y"*sin(roll)+x"*cos(roll)
y"'=y"*cos(roll)-x"*sin(roll)
z"'=z"

If you like the matrix form better here are the matrices:

Matrix to rotate around x axis:

Matrix to rotate around y axis:

Matrix to rotate around z axis:

Note: When you calculate the cos and sin, the functions use radians. Therefore, you must convert from degrees to radians. The equation to convert degrees to radians is angle*PI/180.

You will experience some problems in your rotations if you keep the code as is is to rotate your points in all axis. The reason is, once you calculated the Z and X in the yaw rotation, you must use those new coordinates into your y rotation and z rotation.. and so on. To avoid this problem, I created some temporary variables that act as the new X, Y, and Z. These new X, Y, and Z variables are then used in the next rotations. Follow the ',","' used to differenciate from the original x,y,and z.

Perspective View

Perspective view is composed of two things: converting 3D coordinates into 2D coordinates (screen), and making the perspective view. To convert 3D to 2D, there is a simple equation:

X = x / z
Y = y / z

Where X, Y are your coordinates on the screen, and x,y,z is a 3D point.

The next part, making the perspective view. To explain this concept, look into a shiny door knob. See how your nose is 2x bigger than normal, and the rest of your face is smaller than normal. This is the fish eye concept. Having a fish eye view, is like an exaggerated perspective view. That is, things that are closer become bigger, and things that are farther become smaller. This concept is used to make 3D games look 3D and not flat. Although your screen is flat, perspective view creates a depth into your screen. To do this, you multiply the x and y by the width of your screen in pixels. That is if you are using 320x200 resolution, you would multiply it by 320, so your formula becomes:

X = 320 * x / z
Y = 320 * y / z

The reason why I choose the screen width is because it has to do with how far your face is from the screen. Have you ever tried while playing a 3D game to brind your head really close to the screen and really far from the screen? What you will notice is that the game does not look real anymore. It either looks fish eye (too close) or flat (too far). Using the screen width is a good ratio. That means your head is about a foot away from the screen, which is reasonably good.

Z-Sort

When you finally draw your polygons, they must be in an order from furthest to closest. If this isn't dont, your objects wont even look like they really are because the back faces are being drawn after the front faces. There are many ways to sort them. The easiest would be to take every center of every object and sort that and draw the objects in that order. But this isn't precise enough. So I took every face on every object and threw them into a huge array. Then I sort them. You might ask how would I determine which face belongs to which object after it is sorted? Well I developed a simple algorithm.

To identify which face I am looking at, I multiply the object number (that I'm currently looking at) with MAXFACES+1 (that is the maximum amount of faces a polygon can have) and add the face number. This means that if I'm looking at face 5 on object 3 and MAXFACES was 16 it would be 3*(16+1)+5 = 56.

So to find this face with 56 is the same but do the opposite. That is substract MAXFACES+1 until the number is smaller than MAXFACES+1 and that will give you the object you are looking at. then what is left is your face number.

This will sometimes cause some faces to be drawn in the wrong order. To go even further you can divide every face into smaller pieces and sort that. If this isn't precise enough, you can sort by pixels. This is the most precise way, but also the slowest.

Z-Buffering

Blasting your way to fame and glory in one of the latest 3-D computer games, it might not enter your mind that the world being presented to you on the computer sceen is not real -- but virtual -- and that every element therein is simulated.  The programmers went to great extremes making sure that you stopped correctly when you ran into a wall, that you fell when jumping from a height, and that closer objects correctly obscure objects in the distance.  The former two illusions are created by collision detection and physics simulation, respectively, whereas the latter is created through one of a number of visual surface determination (VSD) algorithms, which deal with the tricky problem of determining which parts of a world are visibile from a given viewpoint.

Computer games primarily use one of three VSD algorithms: BSP trees, depth sorting, and z-buffering.  BSP trees partition a scene according to the plane of polygons, enabling correct sorting of static polygons.  Depth sorting (of the traditional variety), sorts polygons according to their depth, displaying them in back to front order.  Z-buffering performs VSD at the pixel level, testing the depth of each pixel in every polygon against the depth of the pixel previously written to the same location.

BSP trees are good for static polygons, but are difficult to use in moving environments.  Depth sorting produces ugly artifacts which are difficult to resolve (obviously, just sorting polygons won't do any good if you have an array of overlapping or intersecting polygons).  In contrast to these algorithms, the z-buffer algorithm allows for dynamic scenes and overlapping, intersecting polygons.  The only disadvantage: in a software implementation, it consumes memory and processor time.

The Z-buffer algorithm interpolates z (or 1/z) coordinates across polygon rows as the polygons are being rasterized, and compares them to the z (or 1/z) values in a z-buffer.  If the new values are closer to the viewer than the old ones, than the old pixel is replaced and the new value is stored in the z-buffer.  Simple, elegant, but not exactly fast.

Today's hardware for 3D acceleration usually supports z-buffering in hardware.  This enables applications to gain all the luxuries of the z-buffer without the time-consuming overhead.

Since Z-buffering supports features like polygon intersection, if you're designing a game that will support Direct3D, QuickDraw 3D, or your own custom library that supports z-buffers, you can have your artists design scenes to take advantage of this fact.  For example, instead of using four polygons to create the letter 'X', you could use two.

If your target platform is unaccelerated, then you definitely want to provide your own z-bufferer.  The ones in Direct3D are just too slow to be of any use.  I recommend interpolating fixed-point numbers (integers that can represent real numbers) and using at the very least the clear reduction optimization, both documented in my book Cutting Edge 3-D Game Programming with C++.