flipcode - Back Projections

Back Projections
by (16 September 1999)

Introduction

Ok people, here is your article about 3D frustum construction. Enjoy and don't forget to floss twice daily!

We'll start with some definitions of the concepts used. Everything here is really basic 3D, so it should be clear to everyone. We need to define our projection:

Projection in a 3D engine can be defined differently. We'll use the simplest formula known to man(no FOV) for this example. Anyone with grade 11 math skills can apply this to his engine so lets get started.

Projection

Let HalfRes=half the applicable(x or y) screen resolution

Then:


   p(x, z)=(x/z+1)*HalfRes

   ok, so far so good. Now,

          -1
   p(x, z)  =(x*z)/HalfRes-z

What this is is the inverse of the projection formula. FYI, an inverse function is the same as an inverse transform. Might as well have built a projection matrix and found its inverse, but i hate typing matrices in a text file:) By now you're asking what the hell does this has to do with clipping. Getting to that. Lets state the question clearly: we need to find a plane that defines an edge of our FOV. Stating that question differently is that if the projection is applied to all the points lying on the plane, these points will define an edge of the screen. You are all thinking nasty differential equations and such, but i didnt write this as a form of cruel and unusual punishment. There is a simpler way to do it. I'm assuming you guys can build a plane out of 3 points, so just a refresher:


   N=(P2-P1)x(P3-P2) / |(P2-P1)x(P3-P2)|

   where "x" indicates a cross product.

   q=N.P1

   where "." indicates a dot product.

Since we are all smart and we know that a triangle defines a plane, all we need is to find 3 points on that plane. These points all have one thing in common: they all project into a line! You see what i'm getting at here? If we inverted our projection formula we can work backwards. Take 3 points lying on the edge in 2D and backproject them. Let me elaborate:

We want to find the plane defining the edge of the screen where x=0, and y can be anything. We take for that purpose 3 points:


   P1=(0, 1)   P2=(0, 2)   P3=(0,3)

Now we take p(x, z) with the z component equaling anything. One restriction, none of the z's can equal each other, or we get a 3D line instead of a plane. That would be bad. So:


   P1'=p(x  , z)
          p1

   P2'=p(x  , z)
          p2

   P3'=p(x  , z)
          p3

What we have now is 3 points defining our plane! Voila. Here's a nice little pseudo-code example:


typedef struct {
   double x, y, z;
   } CVert;

// Assume 800x600 resolution
#define HalfResX   400
#define HalfResY   300

void BackProject(CVert* Vert)
{
   Vert->x=((Vert->x*Vert->z)/HalfResX-Vert->z);
   Vert->y=((Vert->y*Vert->z)/HalfResY-Vert->z);
}

void BuildPlanes()
{
   CVert *V1, *V2, *V3;

   V1=new CVert;   V2=new CVert;   V3=new CVert;

   // Build left plane
   V1->x=0;   V1->y=0;   V1->z=10;
   V2->x=0;   V2->y=10;  V2->z=20;
   V3->x=0;   V3->y=20;  V3->z=30;
   
   BackProject(V1);   BackProject(V2);   BackProject(V3);
   AddToFrusrum(BuildPlane(V1, V2, V3));   // AddToFrusrum adds the plane passed in
                                           // to the current clipping frusrum
                                           // BuildPlane builds a plane from 3 points

   // Rinse and repeat

   free(V1);   free(V2);   free(V3);
}

If you're feeling real slow tonight(like me), here's a table of how to build the planes assuming the origin is in the lower-left corner of the screen:

Left plane: x=0, y and z arbitrary
Right plane: x=ResX, x and z arbitrary
Top plane: y=ResY, x and z arbitrary
Bottom plane: y=0, x and z arbitrary
Hither(near) plane: z=0, x and y arbitrary

NOTE! All values stated as arbitrary have to be unique for each one of the 3 points(say 3 unique y's/x's) NOTE! It is unadvisable to have z=0 for the hither plane, as you will have nasty "divide by zero" errors. z=0.02 should work well enough(all depends on your scale)

There are of course several more obvious ways to build the hither plane. I used it here for completeness only. Also, this frusrum exists is CAMERA space, not world space. In order to transform it into world space you will need to take the current view matrix, invert it, and apply it to the three points. In our pseudo-code:


   BackProject(V1);   BackProject(V2);   BackProject(V3);

   CameraToWorld(V1); CameraToWorld(V2); CameraToWorld(V3); // Camera to world transforms a
                                                            // point from camera to world
                                                            // coordinate systems(duh)

   AddToFrusrum(BuildPlane(V1, V2, V3)); // AddToFrusrum adds the plane passed in to the
                                         // current clipping frusrum
                                         // BuildPlane builds a plane from 3 points</font>

I'm too lazy to write the actual code for CameraToWorld, so i'll just quickly explain. Say WorldToCamera rotates a point about the 3 axes(Pitch, Yaw, Roll), and then translates by the camera position. Then CameraToWorld will translate the point by -(camera position) and then rotate backwards along the 3 axes(-Pitch, -Yaw, -Roll). You get the idea.

Also, the surgeon general advises that cutting and pasting this code may be bad for the health of your 3D engine. I'm not really sure if i even got the syntax right, hope i did. However the description of the method is quite accurate and you should have no problems implementing it.

Thassit people! Enjoy

- Raven(Eugene Eisenstein)
email:ravemail10@hotmail.com