# Cases 3+4 in Depth Sort

```

Cases 3 and 4 for Depth Sort:

It is assumed that all of the following is done in the coordinate system after
performing all rotations scalings etc - i.e. after Npar.  In perspective case
we also have applied Mperpar following Nper in order to put us in a parallel
type situation.

Case 3: Test to see if Polygon P is entirely behind the plane of Q:

Step 1: Determine the plane of Q.  This needs to be done carefully and
consistently.  I proposed sometime back that polygons be defined by giving
their vertices v0, v1, ... in counterclockwise order.  This determines which
side of the polygon we are talking about - polygons are always treated for
simplicity as having only one side.  A fancier package might allow two-sided
polygons but would surely want two colors assigned, one for each side.

Let r1,r2,r3 be three consecutive vertices from Q that are not in a straight
line (usually v0,v1,v2 will work). If you take the cross product of r2-r1 with
r3-r2, the resulting vector will point up from the true face of the polygon
(i.e. it wont point the opposite way).  We will use this to define the normal,
N which is that cross product (normalized to a unit vector if you wish).  The
polygon plane then has the form:
Nx*x + Ny*y + Nz*z + D = 0

A better definition uses all the points of the polygon, not just three, and is
discussed in the book, but the key point here is to get the direction correct.

Back-face culling, the first step in Depth Sort, even before sorting, throws
away any polygon for which Nz points backwards - ie away from the viewer - in
other words for which Nz<=0.

Step 2: A plane (including the plane of Q) divides all of space into three
sets.
1) Set 1: the points with Nx*x + Ny*y + Nz*z + D = 0
These are the points in the plane
2) Set 2: the points with Nx*x + Ny*y + Nz*z + D < 0
These are the points entirely on one side of the plane
3) Set 3: the points with Nx*x + Ny*y + Nz*z + D > 0
These are the points on the other side of the plane

You need to think a little (or test) to see which of the above (set 2 or 3) are
the points behind the plane from the point of view of the viewer.  In our
standard configuration.  Certainly the point with x=0, y=0, z = -HUGE would be
way back, behind Q.  Putting z = -HUGE into Nx*x + Ny*y + Nz*z + D will give a
negative quantity -  -Nz*HUGE+D - negative since we know from back-face culling
that any remaining Q has Nz>0.  Therefore set 2 are the points behind Q.

Step 3: We now need to determine if polygon P is in Set 2.  To do this, we must
show that for every point x,y,z in P, Nx*x + Ny*y + Nz*z < 0.  Fortunately
it is enough to test each vertex of P.  It is easy to show that if every vertex
of P is behind Q, then so are all points in P.  So the final step is to run
over the vertices of P, substitute into the equation of Q and see if the result
is negative.  If the result is negative or 0 at every vertex then P is behind Q.

Case 4: Test to see if Polygon Q is entirely in front of the plane of P:

This goes the same way as case 3.  We just substitute each vertex of Q into the
equation of the plane of P, and if all results are >=0 then Q is in front of
the plane of P.
```

Previous   Next