6. Hidden face removal

6.1 Backface Culling

The idea of backface culling is simple: if a polygon is a backface (it's not facing the camera), there's no need to draw it. This can be checked by finding the z value of its normal and by examining its sign. This won't work if the faces haven't been defined right, so be careful (for example 3D Studio creates the correct type of faces; the vertices are in counterclockwise order). Here's a pseudo-backface-culler:
function backface(x1, y1, x2, y2, x3, y3)
dx1 = x3 - x1
dy1 = y3 - y1
dx2 = x3 - x2
dy2 = y3 - y2
; find the z value of the cross product
if ( ( dx1*(dy2-dy1)-(dx2-dx1)*dy1 ) > 0 )
return TRUE
else
return FALSE
endf

6.2 View Cone

View cone means the conical area that can be seen by looking at some direction. Here's a picture of a view cone:
(C = camera point, P = projection plane. The camera point is actually the watcher's eye, and the projection plane is the computer screen.) So there are five planes against which we must clip (or six planes if we want to use a back plane in a defined maximum range when using fog or light attenuation for example). If a polygon is not inside the cone, we can drop it out the calculations and save a great amount of processing time. If it's partly inside, we clip it against the cone and draw only the part which is inside. The more elegant (and faster) form of view cone uses 3D clipping to clip this kind of polygons but I recommend using graphical clipping in the polygon routine at first; it's far more straightforward to implement and it works, too (ok there's a problem with the z thing).

The thing is done by comparing the 2Dx, 2Dy, and z coordinates to the screen edges and by acting accordingly. Applying to the z coordinate, we don't draw the polygon if any of its vertices' z is less than zero; we can't draw or interpolate right a polygon like that. If your scene bugs with this, please read the following chapter. Pseudo:

if
(
EVERY vertex.z>0
and
SOME vertex.x at the range 0..MAX_X
and
SOME vertex.y at the range 0..MAX_Y
)
draw.

6.2.1 3D clipping

This is a bit trickier thing to implement. It's best if you're using n-sided polygons; a clipped triangle might become a quadrangle, and if you were using only triangles, you should create two triangles out of it. No good. Anyway, some pseudo to clip the z's (really not the one and only way to do the thing, try your own ways!):
; check the z's
every_z_out=true
every_z_in=true
for a=0 -> vertices_in_poly-1
if z[a]>1 ; or zero if this doesn't work with you
every_z_out=false
else
every_z_in=false
if (not every_z_out) and (not every_z_in)
clip z's
every_z_in=true
perform 2d transformations
...
if every_z_in
draw_using_graphical_clipping.
That's the main idea. Clipping can be performed by using the parametric equation of a line (((x0,y0,z0) = vertex 1 etc):
x = x0 + t*(x1-x0)
y = y0 + t*(y1-y0)
z = z0 + t*(z1-z0)
Z-clip: we define z=0.5 and calculate t:
z0 + t*(z1-z0) = 0.5
t = (0.5-z0) / (z1-z0)
This is placed into the equations of x and y:
x = x0 + (x1-x0)*(0.5-z0)/(z0-z1)
y = y0 + (y1-y0)*(0.5-z0)/(z0-z1)
z = 1
And these are the new coordinates of the vertex!

6.3 Portals

Portals are very simple and easy to understand and implement (at least the most primitive versions :) Using them, we can eliminate 70-80% of polys from our calculations and do it even before rotating anything (another story)!

Portals require the whole scene to consist of rooms. Each room has not only its own polygons but also invisible portal polygons in the holes (doors, windows, ...) through which one can see into another rooms. Portal polygons are handled just like any normal polygon. The difference between normal and portal polygons is that when a portal polygon should be drawn, we just move into the room it's pointing if it's seen. We continue like this until we're satisfied with the result. It's worth noticing that portal polygons which are too far away needen't to be handled either. Another point is that polygons in the next rooms can only be seen though the portal polygons of the preceding rooms.

There are many ways to implement portals. Some like the rooms consist of convex polygons and all polygons to be clipped against the portal polygons (SLOW!). There are numerous other ways, too, just find the best one for your purposes!

An interesting thing is that we can eliminate most rooms just by backface-culling the portal polygons; if the portal is a backface, the room it's pointing can't be seen!