Project 4: Camera Transformations and Frustum Culling
CSE167 W06 

Overview
For this assignment you will complete an implementation for some basic orthonormal and perspective camera classes. The project is divided into two parts: In Part 1 you will complete code to generate some basic camera transformations, including the inverse camera "lookat" transform and the projection transforms for both the perspective and orthographic cameras. In Part 2 you'll calculate bounding volumes. In Part 3 you will complete code to implement basic bounding sphere frustum culling.
For this assignment, we've also included our solutions to projects 13 in a separate zip file.
Solutions: projsol13.zip
Files:matrix.h, matrix.cpp, vector.h, vector.cpp, core.h, light.h, light.cpp, geometry.h, geometry.cpp, geomtypes.h, geomtypes.cpp, objfile.h, objfile.cpp
We have also added some additional functionality to the scenegraph and renderer files, such as colors for ShapeNodes. You are free to use your own basecode from previous assignments, but be sure you have the updated (or include the updates from) scenegraph.h/.cpp, rednerer.h and openglrenderer.cpp files.
Base Code: proj4.zip
Files: openglrenderer.cpp, renderer.h, scenegraph.h, scenegraph.cpp, camera.h, camera.cpp, cullingsim.h, cullingsim.cpp, main.cpp.
You'll also need the teapot.obj file from Proj3.
For this assignment you will modify the following files: camera.cpp, geometry.cpp. We recommend coding this assignment in the order listed below.
The program should compile fully when executed for the first time. You shouldn't see anything that makes sense, perhaps a flashing teapot and some circular lines.
Due: Friday, February 10th
Part 1: Projection & Lookat Transformations
Begin by familiarizing yourself with the Camera class, found in camera.h. The Camera class is a base class for two other classes: PerspectiveCam and OrthographicCam, which implement a perspective camera and orthograhic camera, respectively. The functions you'll be completing are defined below:
In the Camera class:
 CalcInvLookAt  Calculate a inverse lookat transformation from the local variables available in the camera class. You'll need the Eye, Target, and Up vectors which are members of the Camera class. To accomplish this, first construct the lookat transformation. Check the lecture slides for the algorithm required. Next, you must invert this lookat transformation. Here's how:
 First, observe that a lookat transform is a rigid body transformation, and can be decomposed into the product of a Translation and a Rotation Matrix.
ax 
bx 
cx 
dx 

1 
0 
0 
dx 

ax 
bx 
cx 
0 
ay 
by 
cy 
dy 
= 
0 
1 
0 
dy 
* 
ay 
by 
cy 
0 
az 
bz 
cz 
dz 

0 
0 
1 
dz 

az 
bz 
cz 
0 
0 
0 
0 
1 

0 
0 
0 
1 

0 
0 
0 
1 
, so Lookat = T*R.
 To get the inverse, we can invert the two matrices separately and multiply them in reverse: LookatInv = Rinv * Tinv.
 This method works for matrices in general, such that if N = M1*M2*M3*...*Mn then Ninv = Mninv*M(n1)inv*...*M2inv*M1inv.
 The inverse of a translation matrix is just another translation matrix in the negative direction.
 The inverse of a pure rotation matrix (or any orthonormal matrix in general) is equal to its transpose.
In the PerspectiveCam class:
 CalcProjectionMatrix  Calculate the projection matrix for a perspective projection. You'll need the FOV (field of view) parameter, the aspect ratio (window width / window height), and the near and far clipping planes. We'll use this matrix in place of our typical call to gluPerspective call .
In the OrthographicCam class:
 CalcProjectionMatrix  Calculate the projection matrix for an orthographic projection. The OrthographicCam class makes some simplifications regarding this projection Matrix, making it slightly different than glOrtho. Typically, to create an orthographic projection matrix we need a left, right, bottom, and top parameter as well as the near and far clipping planes.
 The first assumption we make is that the projection is centered at the origin, meaning that left = right, and top = bottom. Consequently, instead of storing all four values, all we need now is a height and width parameter, where left = width/2 and right = width/2. Similarly, bottom = height and top = height.
 Next, because we like to always preserve the aspect ratio, we'll keep the height variable fixed, and calculate the width term a product of the height and the aspect ratio ( PixelWidth / PixelHeight, which are member variables found in the Camera class. You may assume these are already set correctly for you when the screen is resized). So now we only need to store a height and an aspect ratio, which is already stored in the base class.
After filling in the above functions, you should see a teapot model moving left to right with a crude (and inaccurate) bounding sphere. Note, if the program gives you an error like str==0, it may be that the "teapot.obj" file is not in the right directory. If you continue to experience difficulty getting this obj file to load, you may substitute the teapot model for a Cube in the cullingsim.cpp constructor. Do a search for "teapot.obj" and you'll find the single line you need to alter.
At this point, you may want to look at the many keystrokes implemented in this assignment. Check out the console of the project for a description.
Part 2: Bounding Volumes
Here you'll fill in code to calculate the bounding sphere of a Geometry model. Fill in the following function:
In the Geometry class:
 CalcBoundingSphere  You'll need to generate the center and the radius for the sphere that bounds all vertices in this model. To calculate the bounding sphere, you are free to use any method you choose. The one listed here is not necessarily the tightest fit, but will work for now. Here's how the algorithm works.
 1. Loop through all vertices and store the min and max coordinates for x, y, and z. You've essentially computed the bounding box. You'll have 6 parameters at the end. Take the average along each axis to find the center of your bounding sphere.
 To find the radius of your bounding sphere, first find the diagonal of the bounding box above. Use the 6 parameters to create the min and max Points of the box, then find the Vector between them. A simple Vector::Mag() will get you the distance of this diagonal. Half of the diagonal length is the radius of your bounding sphere.
When completed, the teapot should now have a much tighter and more accurate bounding sphere.
Part 3: Culling
Next, you'll implement the following functions that do some frustum culling:
In the PerspectiveCam and OrthographicCam class:
 CalcCullingInfo  This function gets called in the main.cpp file each time the camera properties are altered. You will not be required to call this function directly from within any of the functions you will write. There are two parts to this function:
 First, calcualte the eight points of the frustum in WORLD SPACE COORDINATES and store them in any order you like. But be consistent between classes, because you'll also be implementing the DrawFrustum command above. To calculate the frustum corners for the perspective matrix, some basic trigonometry should get you through it. Check out the lecture notes for a description of how each of the values FOV, aspect ratio, and the near and far clipping planes play a role. The corners for the orthographic camera should be straightforward, using similar techniques as in the projection matrix.
 Second, use the points to calculate the normal and d component for each of the six planes of the frustum. A simple cross product should get you the normal. The d component can be computed if you remember the following formula: d = p (dot) n where n is the normal of the plane and p is any point on that plane. You may find the Point3::ToVector() function useful when trying to take the dot product of a vector and a point
In the Camera class:
For the following functions, you may assume that CalcCullingInfo has already been called and that the planes and frustum points stored are correct.
 DrawFrustum  Using the eight corner Points of the frustum (calculated in Camera::CalcCullingInfo), draw the frustum in wireframe. The order of the points will be determined by how you implement the CalcCullingInfo routine above.
 Here's sample code for DrawFrustum. It assumes the following order about the frustmCorners, assuming you're looking from the Eye towards the Target.:
 0  Near Upper Right
 1  Near Upper Left
 2  Near Lower Left
 3  Near Lower Right
 4  Far Upper Right
 5  Far Upper Left
 6  Far Lower Left
 7  Far Lower Right
glColor3f(1,1,0);
glBegin(GL_LINE_LOOP);
glVertex3fv(&frustumCorners[0].x);
glVertex3fv(&frustumCorners[1].x);
glVertex3fv(&frustumCorners[2].x);
glVertex3fv(&frustumCorners[3].x);
glEnd();
glBegin(GL_LINE_LOOP);
glVertex3fv(&frustumCorners[4].x);
glVertex3fv(&frustumCorners[5].x);
glVertex3fv(&frustumCorners[6].x);
glVertex3fv(&frustumCorners[7].x);
glEnd();
glBegin(GL_LINES);
glVertex3fv(&frustumCorners[0].x);
glVertex3fv(&frustumCorners[4].x);
glVertex3fv(&frustumCorners[1].x);
glVertex3fv(&frustumCorners[5].x);
glVertex3fv(&frustumCorners[2].x);
glVertex3fv(&frustumCorners[6].x);
glVertex3fv(&frustumCorners[3].x);
glVertex3fv(&frustumCorners[7].x);
glEnd();
 TestBoundingSpherePlane  Test a bounding sphere against a plane and determine if it is on the same side as the normal, on the opposite side, or intersects with the plane. Detailed instructions on which values to return are indicated in the comment associated with the function in camera.cpp. When this function is implemented, the teapot should change color as it passes in front of and behind the plane. Green indicates it lies behind the plane; white indicates the sphere is in front; and yellow indicates if the sphere intersects the plane. The first screenshot below depicts what you should see at this point (with the camera moved over a bit using the 'd' keystroke). The 'z' button should alter between culling based on the the x,y,and z axis.
 CullBoundingSphere  Given a bounding sphere center and radius, determine if the sphere lies completely outside, completely inside, or intersects with the frustum. To do this, check the sphere against each of the six planes of the frustum (calculated in Camera::CalcCullingInfo). If the sphere lies completely in front of any of these planes, then the sphere can be culled. If it lies completely behind all of these planes, the sphere is completely enclosed by the frustum. Otherwise, the sphere either intersects or lies behind each plane. This last case indicates some clipping may be necessary, although we won't implement clipping in this assignment. You may (should) use Camera::TestBoundingSpherePlane that you implemented above.
When completed, use the 'x' key to switch between the teapot model and a camera culling simulation. You should see a frustum drawn in the center of the screen. Objects which enter the frustum turn yellow or green depending upon whether they intersect or lie completely in the frustum. The lower left corner shows a view from that culling camera. If implemented correctly, all spheres that appear whole should be green colored.
Additionally, you should be able to rotate the camera with FPS style controls. a and d rotate the camera left to right. w and s move the camera up and down. You can switch between perspective and orthographic culling cameras with the c key. Further, you can also adjust a few camera parameters, like the near clipping plane distance with n and m, or the field of view with f and g for a perspective camera . Below are screenshots from the solution:
Bells & Whistles
Here are a few bells and whistles to try out:
 Hierarchical Bounding Spheres, where each node in the scenegraph contains a bounding sphere enclosing of all its children.
 Tighter Bounding Sphere Algorithm
 Use Bounding Boxes for culling instead of Spheres.