# DirectX/10.0/Direct3D/Frustum Culling

The three dimensional viewing area on the screen where everything is drawn to is called the viewing frustum.
Everything that is inside the frustum will be rendered to the screen by the video card. Everything that is outside of the frustum the video card will examine and then discard during the rendering process.
However the process of depending on the video card to cull for us can be expensive if we have large scenes. For example say we have a scene with 2000+ models that are 5,000 polygons each but only 10-20 are viewable at any given time. The video card has to examine every single triangle in all 2000 models to remove 1990 models from the scene just so we can draw 10 models. As you can see this is very inefficient.
How frustum culling solves our problem is that we can instead determine before rendering if a model is in our frustum or not. This saves us sending all the triangles to the video card and allows us to just send the triangles that need to be drawn. How we do this is that we put either a cube, a rectangle, or a sphere around each model and just calculate if that cube, rectangle, or sphere is viewable. The math to do that is usually only a couple lines of code which then removes the need to possibly test several thousand triangles.
To demonstrate how this works we will first create a scene with 25 randomly placed spheres. We will then rotate the camera manually to test culling of the spheres that are out of our view using the left and right arrow keys. We will also use a counter and display the number of spheres that are being drawn and not culled for confirmation. We will use code from several of the previous tutorials to create the scene.

## Framework

The frame work has mostly classes from several of the previous tutorials. We do have three new classes called FrustumClass, PositionClass, and ModelListClass. FrustumClass will encapsulate the frustum culling ability this tutorial is focused on.
ModelListClass will contain a list of the position and color information of the 25 spheres that will be randomly generated each time we run the program. PositionClass will handle the viewing rotation of the camera based on if the user is pressing the left or right arrow key.

## Frustumclass.h

The header file for the FrustumClass is fairly simple. The class doesn't require any initialization or shutdown. Each frame the ConstructFrustum function is called after the camera has first been rendered. The ConstructFrustum function uses the private m_planes to calculate and store the six planes of the view frustum based on the updated viewing location. From there we can call any of the four check functions to seen if either a point, cube, sphere, or rectangle are inside the viewing frustum or not.

## Frustumclass.cpp

ConstructFrustum is called every frame by the GraphicsClass. It passes in the depth of the screen, the projection matrix, and the view matrix. We then use these input variables to calculate the matrix of the view frustum at that frame. With the new frustum matrix we then calculate the six planes that form the view frustum.
CheckPoint checks if a single point is inside the viewing frustum. This is the most general of the four checking algorithms but can be very efficient if used correctly in the right situation over the other checking methods. It takes the point and checks to see if it is inside all six planes. If the point is inside all six then it returns true, otherwise it returns false if not.
CheckCube checks if any of the eight corner points of the cube are inside the viewing frustum. It only requires as input the center point of the cube and the radius, it uses those to calculate the 8 corner points of the cube. It then checks if any one of the corner points are inside all 6 planes of the viewing frustum. If it does find a point inside all six planes of the viewing frustum it returns true, otherwise it returns false.
CheckSphere checks if the radius of the sphere from the center point is inside all six planes of the viewing frustum. If it is outside any of them then the sphere cannot be seen and the function will return false. If it is inside all six the function returns true that the sphere can be seen.
CheckRectangle works the same as CheckCube except that that it takes as input the x radius, y radius, and z radius of the rectangle instead of just a single radius of a cube. It can then calculate the 8 corner points of the rectangle and do the frustum checks similar to the CheckCube function.

## Modellistclass.h

ModelListClass is a new class for maintaining information about all the models in the scene. For this tutorial it only maintains the size and color of the sphere models since we only have one model type. This class can be expanded to maintain all the different types of models in the scene and indexes to their ModelClass but I am keeping this tutorial simple for now.

## Modellistclass.cpp

The class constructor initializes the model information list to null.
First store the number of models that will be used and then create the list array of them using the ModelInfoType structure.
Seed the random number generator with the current time and then randomly generate the position of color of the models and store them in the list array.
The Shutdown function releases the model information list array.
GetModelCount returns the number of models that this class maintains information about.
The GetData function extracts the position and color of a sphere at the given input index location.

## Graphicsclass.h

The GraphicsClass for this tutorial includes a number of class we have used in the previous tutorials. It also includes the frustumclass.h and modellistclass.h header which are new.
Two of the new private class objects are the m_Frustum and m_ModelList.

## Graphicsclass.cpp

I will just cover the functions that have changed since the previous tutorials.
The class constructor initializes the private member variables to null.
We load a sphere model instead of a cube model for this tutorial.
Here we create the new ModelListClass object and have it create 25 randomly placed/colored sphere models.
Here we create the new FrustumClass object. It doesn't need any initialization since that is done every frame using the ConstructFrustum function.
We release the new FrustumClass and ModelListClass objects here in the Shutdown function.
The Frame function now takes in the rotation of the camera from the SystemClass that calls it. The position and rotation of the camera are then set so the view matrix can be properly updated in the Render function.
The major change to the Render function is that we now construct the viewing frustum each frame based on the updated viewing matrix. This construction has to occur each time the view matrix changes or the frustum culling checks we do will not be correct.
Now loop through all the models in the ModelListClass object.
Here is where we use the new FrustumClass object. We check if the sphere is viewable in the viewing frustum. If it can be seen we render it, if it cannot be seen we skip it and check the next one. This is where we will gain all the speed by using frustum culling.
We use the slightly modified TextClass to display how many spheres were actually rendered.
We can also infer for this number that the spheres that were not rendered were instead culled using the new FrustumClass object.

## Positionclass.h

To allow for camera movement by using the left and right arrow key in this tutorial we create a new class to calculate and maintain the position of the viewer. This class will only handle turning left and right for now but can be expanded to maintain all different movement changes. The movement also includes acceleration and deceleration to create a smooth camera effect.

## Positionclass.cpp

The class constructor initializes the private member variables to zero to start with.
The SetFrameTime function is used to set the frame speed in this class. PositionClass will use that frame time speed to calculate how fast the viewer should be moving and rotating. This function should always be called at the beginning of each frame before using this class to move the viewing position.
GetRotation returns the Y-axis rotation of the viewer. This is the only helper function we need for this tutorial but could be expanded to get more information about the location of the viewer.
The movement functions both work the same. Both functions are called each frame. The keydown input variable to each function indicates if the user is pressing the left key or the right key. If they are pressing the key then each frame the speed will accelerate until it hits a maximum. This way the camera speeds up similar to the acceleration in a vehicle creating the effect of smooth movement and high responsiveness. Likewise if the user releases the key and the keydown variable is false it will then smoothly slow down each frame until the speed hits zero. The speed is calculated against the frame time to ensure the movement speed remains the same regardless of the frame rate. Each function then uses some basic math to calculate the new position of the camera.

## Systemclass.h

The SystemClass has been modified to use the new PostionClass.

## Systemclass.cpp

I will cover just the functions that have changed in this class since the previous tutorials.
The new PositionClass object is initialized to null in the class constructor.
Create the new PositionClass object here. It doesn't require any initialization.
The PositionClass object is released here in the Shutdown function.
During each frame the PositionClass object is update with the frame time.
After the frame time update the PositionClass movement functions can be updated with the current state of the keyboard. The movement functions will update the position of the camera to the new location for this frame.
The new rotation of the camera is retrieved and sent to the Graphics::Frame function to update the camera position.

## Summary

Now you have seen how to cull objects. The only trick from here is determining whether a cube, rectangle, sphere, or clever use of a point is better for culling your different objects.

## To Do Exercises

1. Recompile and run the program. Use the left and right arrow key to move the camera and update the render count in the upper left corner.
2. Load the cube model instead and change the cull check to CheckCube.
3. Create some different models and test which of the culling checks works best for them.