Main Site Links Resources Tutorials
News VB Gaming Code Downloads DirectX 7
Contact Webmaster VB Programming Product Reviews DirectX 8
  General Multimedia Articles DirectX 9
      Miscellaneous

Visibility Testing
Author : Jack Hoxley
Written : 14th March 2001
Contact : [Web] [Email]
Download : Graph_16.Zip [16 Kb]


Contents of this lesson:
1. Introduction
2. Vector Based Culling
3. Frustum Culling
4. Projection/Bounding Box Culling
5. Tips and Tricks


1. Introduction

By this point in the series you should be getting fairly familiar with 3D programming and the Direct3D interfaces; the chances are that you've also started your own little project, or begun thinking about it (if you like 3D that is). This section of "useful techniques" are articles that explain things that aren't necessarily part of Direct3D or it's interfaces, but may well be required when using them - or are made easier using them. Many of these tricks use the D3DX libraries maths functions to simplify things, but where relevent the actual technique behind them will be explained.

The first useful technique I want to cover is that of visibility testing. Someone once said (I dont know who): "The fastest polygons are the ones you dont draw", this should make perfect sense, we only have a finite amount of power to play with, and when you want your game to run at any sort of reasonable pace you'll always be juggling between what you can do and what you want to do. Despite the ever increasing power that 3D cards are providing we dont want to waste any time or resources that we dont need to, the simplest way is to reduce the number of objects or vertices that we are being sent to render. Whilst Direct3D will clip geometry to fit the screen it still does quite a lot of processing on hidden and/or offscreen geometry - geometry that it is quite likely the player will never see. To stop Direct3D wasting valuable time programmers employ a handful of tricks and algorithms to determine whether or not geometry should be rendered (based on it being on/off screen).

There are 100's of different methods for doing this, different ones will suit different worlds/game types - its up to you to choose the one you like the most or design a custom version based on multiple different methods. This article covers 3 types of culling (removal of geometry we dont want) methods, and then offers some tips and tricks for using these algorithms.


2. Vector Based Culling

This first method is an extremely simple one, and was designed by myself for use with "3D-World" (the final piece for this series), it may well have been documented and used before, but I didn't read up on it before hand. The major flaw with this algorithm is that it only suits very specific environments, landscapes particularly - buildings/indoors scenes as well, but other engine types will not always work so well using this technique.

The basis of this technique is the usage of a common 3D graphics formula, the Dot Product - this is covered again in Useful Techniques number 2, so I'll only skim through it here. The dot product of two vectors (that are normalised) will give us a value representative of the angle between them (The cosine to be precise). We can use this value to tell if a point is in front of the camera, and within a given degree of the camera's direction.

U•V = (U.X * V.X) + (U.Y * V.Y) + (U.Z * V.Z)
U•V = (U.X * V.X) + (U.Y * V.Y)

The Dot product formula for 3D vectors (top), and 2D vectors (Bottom). If the vectors are normalised (a length of 1) then the result will lie between -1 and +1. If we take the vector U to be the direction that the camera is facing (calculated using the Unit Circle Theorem) and V to be the vector from the camera to the point in question, we can calculate the angle, which will give us the results depicted below. Currently it's only in 2D, but that's partly because it's easier to show as a diagram.

All of the above vectors (represented by black lines) are compared with a vector going straight up - [0,1], a vector going the same direction gets a result of 1.0 - as shown, a vector going perpendicular to [0,1] will get a result of 0.0, and any vector between will get a value between 0.0 and 1.0. Any vector going in a direction away from [0,1] will get a negative value - also shown on the diagram.

Using this information it is going to be quite simple to construct a test that rejects any points that are behind it, or out of range given a reference value. When setting up your projection matrix you will have specified a FOV angle (usually in radians), if we convert this angle to a vector we can say any comparisons with a result less than this is NOT in view, and any comparisons with a result greater than this IS in view. To calculate the comparison value we can use a simple bit of trig maths - this can be done on paper before hand, once you have the values you can store them as a CONST value and use them forever after - they wont change. The most commonly used angles are 45, 60 and 90 degrees, the following diagram illustrates how we can work the dot product reference value out. If we take the view cone as a 2D triangle, where the known angle is half of the total view angle (two triangles will make up the whole cone), we can take a two known distances and either use trig to find the third, or use pythagorus's theorem:

The above triangles represent 45, 60 and 90 degree view angles, for simplicity I'm making the adjacent = to 1, and we want to find the opposite (labelled ?) - we will then have a 2D coordinate for the outer corner (not the 90 degree one) proportional to the origin (which is where the corner with the angle is). We can then normalise this vector, and then compare it with the vector for the adjacent, [1,0] to get the value we want. Here we go:

The length ?'d, using inverse tan will be:

45 Degree cone
Tan(22.5) = ? / 1
? = Tan(22.5)
? = 0.4142135624

60 Degree cone
Tan(30) = ? / 1
? = Tan(30)
? = 0.5773502692

90 Degree cone
Tan(45) = ? / 1
? = Tan(45)
? = 1

We now know the coordinates of the point:

45 Degrees : [1, 0.4142135624]
60 Degrees : [1, 0.5773502692]
90 Degrees : [1, 1]

if we normalise these vectors we get the direction from the origin to the point:

45 Degrees : [0.9238795325, 0.3826834324]
60 Degrees : [0.8660254038, 0.5]
90 Degrees : [0.7071067812, 0.7071067812]

If we now perform a 2D Dot product calculation on the adjacent vector ( [1,0] ) and the vectors listed above we'll get our reference value for each view angle, the results are:

45 Degrees : 0.923879325
60 Degrees : 0.8660254038
90 Degrees : 0.7071037812

You may notice that these value are just the X component of original vectors; this is simply because the adjacent vector, [1,0], doesn't alter the X component (multiply by 1) and the Y component is made to be 0 (multiply by 0) - resulting in the X component being the Dot product value.

You can store these values and use them whenever you like without recalculating them, and if you need a different angle you can quite easily re-write the above calculations to compensate. Also note that you may need to allow a little room when doing the culling, the 3D World final piece uses a 45 degree view angle, yet a dot product comparison figure of 0.865 and 0.845 (depending on what it's rendering) - originally it used 0.924, but based on observation it occasionally clipped points that it shouldn't have done - so I kept taking away a little bit until I decided it wasn't elminintating many triangles - it still does sometimes, but compared with the amount of excess triangles it draws I kept it as it is.

So we've come this far, and not a great deal has happened. We need to write some code that uses all these facts and bits of theory - a simple function that will take a set of points and return if it's visible or not.

Public Function CheckPointVisible(CamPos As D3DVECTOR2, CamAng As Single, DrawDepth As Single, _
      PointToTest As D3DVECTOR2, DPGreaterThan As Single) As Boolean
'//0. Any variables
    Dim vDir As D3DVECTOR2
    Dim vTmp As D3DVECTOR2
    Dim DOT As Single
    
'//1. Get vector from camera to point
    D3DXVec2Subtract vDir, PointToTest, CamPos
    
'//2. Normalise vector
    D3DXVec2Normalize vDir, vDir


'//3. get DOT product
    vTmp.X = UnitCircle(CInt(CamAng)).X
    vTmp.Y = UnitCircle(CInt(CamAng)).Y
    DOT = D3DXVec2Dot(vTmp, vDir)
    
'//4. Check against DPGreaterThan and distance check
    If DOT > DPGreaterThan Then
        'In the correct cone area
        If GetDist2D(PointToTest.X, PointToTest.Y, CamPos.X, CamPos.Y) <= DrawDepth Then
            'we're within the correct distance
            CheckPointVisible = True
        End If
    Else
        'if we're within DPGreaterThan - 0.165 and within 20m of camera we'll add it
                If DOT > (DPGreaterThan - 0.165) Then
                    If GetDist2D(PointToTest.X, PointToTest.Y, CamPos.X, CamPos.Y) <= 20 Then
                        CheckPointVisible = True
                    End If
                End If
    End If
End Function

Not too complicated really, First it gets the direction vector from the camera to the point in question, then it compares this to the vector defined by the angle the camera is pointing (we could also calculate this by using vAt-vEye from the view matrix). Next it performs the dot product calculation, it then takes the result and compares it with the reference value, if it passes it checks the distance, if it's within range then the point is visible - the functions returns true. If it fails it does an additional check where it's more lenient, and only passes it if it's very close to the camera - during testing I found that there were occasional anomalies close to the camera - this little bit of code solved it.

A couple of things to note about the above code:
1) It uses the D3DX library, whilst this is an article about Direct3D you can replace these calls with equivelent functions (should you be using a newer/older version of DirectX, or not using DirectX at all...)
2) It uses the standard GetDist2D() call - this is a simple function that returns the distance between two points in 2D space, and looks like:

Public Function GetDist2D(X1 As Single, Y1 As Single, X2 As Single, Y2 As Single) As Single
    GetDist2D = Sqr(Abs(((X1 - X2) * (X1 - X2)) + ((Y1 - Y2) * (Y1 - Y2))))
End Function

3) It uses the unit circle theorem, in this case it just reads from a lookup array of precalculated integer angles (0 to 360), If you haven't seen this before check out the maths article later on. Briefly though - the X and Y components can be calculated like so:

Public Function GetVectorFromAngle(Theta As Double) As D3DVECTOR2
    Theta = Theta * ((4 * Atn(1)) / 180) 'convert angle to radians
    GetVectorFromAngle.X = Cos(Theta)
    GetVectorFromAngle.Y = Sin(Theta)
End Function

Done!

Using the above function youcan now tell in 2D if a point is within a given angle, if you modify this it will tell you if the point is within a cone defined by the angle. This method is only really useful for landscape or planar worlds - where everything originates from the same (or similiar) height, like the insides of an office/building. When using height mapped worlds (for landscapes), you can test the center of every tile for visibility - the grid the map is based on is 2D (ignoring the Y/height dimension). For a working example of this wait for the (or go see if it's ready) 3D-World final piece.


3. Frustum Culling

Frustum culling is one of the more common techniques used - it's based in full 3D unlike the vector one above, and is fairly simple to implement, whilst not incredibly accurate it usually does the job adequately.

First off, what is the frustum? this is the area of 3D space that is projected onto the screen when you render a scene. It is defined by a series of planes, these planes are then used to reject geometry. The frustum is illustrated using the following diagram:


(My apologies for the appalling diagram!)

In the above diagram, the blue arrow shows where the camera is facing/looking, the smaller square is the near clipping plane (only vertices beyond this are accepted), the larger square is the far clipping plane (only vertices in front of this are accepted), and the 4 sides joining them up are the side clipping planes. the size and shape of this volume are defined by the viewport settings, projection matrix and the view matrix.

What we need to do is construct a set of 6 planes based on this shape, and suited to fit our world settings. The code for this is quite complicated, and is included in the DirectX8 SDK helper libraries, which is where this next piece of code comes from (I didn't write it is what I'm saying!):

'//Borrowed from the SDK's D3DUTIL module... Computes the clip planes for the view frustum...
Sub ComputeClipPlanes(veye As D3DVECTOR, vat As D3DVECTOR, vUp As D3DVECTOR, _
      fov As Single, front As Single, back As Single, aspect As Single)
    
    Dim vDir As D3DVECTOR
    Dim vright As D3DVECTOR
        
    Dim vFrontCenter As D3DVECTOR
    Dim vFrontUp As D3DVECTOR
    Dim vFrontRight As D3DVECTOR
    
    Dim vBackCenter As D3DVECTOR
    
    Dim vBackRight As D3DVECTOR
    Dim vbackLeft As D3DVECTOR
    
    Dim vBackRightTop As D3DVECTOR
    Dim vBackLeftTop As D3DVECTOR
    
    Dim vBackRightBot As D3DVECTOR
    Dim vBackLeftBot As D3DVECTOR
        
    Dim DX As Single
    Dim dY As Single
    
'Establish our basis vector
    D3DXVec3Subtract vDir, vat, veye
    D3DXVec3Normalize vDir, vDir
    D3DXVec3Normalize vUp, vUp
    D3DXVec3Cross vright, vDir, vUp
    
    DX = Tan(fov / 2) * back
    dY = DX * aspect
        
    '
    '
    '              /|  vbackleft (top,bot)
    '             / |
    '        vfront |
    '           /|  |
    '       eye ----|  vbackcenter
    '           \|  |
    '            \  |dx
    '             \ |
    '              \|  vbackright (top,bot)
    '
    '
    
    
    'compute vbackcenter

    D3DXVec3Scale vBackCenter, vDir, back
    D3DXVec3Add vBackCenter, vBackCenter, veye
    
       
'compute vbackright
    D3DXVec3Scale vBackRight, vright, DX
    D3DXVec3Add vBackRight, vBackCenter, vBackRight
    
    
'compute vbackleft
    D3DXVec3Scale vbackLeft, vright, -DX
    D3DXVec3Add vbackLeft, vBackCenter, vbackLeft
 
    'compute vbackrighttop

    D3DXVec3Scale vBackRightTop, vUp, dY
    D3DXVec3Add vBackRightTop, vBackRight, vBackRightTop
    
    
'compute vbacklefttop
    D3DXVec3Scale vBackLeftTop, vUp, dY
    D3DXVec3Add vBackLeftTop, vBackRight, vBackLeftTop
        
'compute vbackrightbot
    D3DXVec3Scale vBackRightBot, vUp, -dY
    D3DXVec3Add vBackRightBot, vBackRight, vBackRightBot
       
'compute vbackleftbot
    D3DXVec3Scale vBackLeftBot, vUp, -dY
    D3DXVec3Add vBackLeftBot, vBackRight, vBackLeftBot
    
        
    'compute vfrontcenter

    D3DXVec3Scale vFrontCenter, vDir, front
    D3DXVec3Add vFrontCenter, vFrontCenter, veye
 
'compute vfrontright
    D3DXVec3Scale vFrontRight, vright, DX
    D3DXVec3Add vFrontRight, vFrontCenter, vFrontRight
 
    'compute vfrontup
    D3DXVec3Scale vFrontUp, vUp, dY
    D3DXVec3Add vFrontUp, vFrontCenter, vFrontUp
    
    
'front plane
    D3DXPlaneFromPointNormal FrustumPlanes(0), veye, vDir
    
'back plane
    Dim vnegdir As D3DVECTOR
    D3DXVec3Scale vnegdir, vDir, -1
    D3DXPlaneFromPointNormal FrustumPlanes(1), vBackCenter, vnegdir
    
'right plane
    D3DXPlaneFromPoints FrustumPlanes(2), veye, vBackRightTop, vBackRightBot
    
'left plane
    D3DXPlaneFromPoints FrustumPlanes(3), veye, vBackLeftTop, vBackLeftBot
    
'top plane
    D3DXPlaneFromPoints FrustumPlanes(4), veye, vBackLeftTop, vBackRightTop
    
'bot plane
    D3DXPlaneFromPoints FrustumPlanes(5), veye, vBackRightBot, vBackLeftBot
    
End Sub

looks nasty doesn't it... you dont really need to understand it in order to use it - so dont worry about how it does things. In order to use this code you must have an array of 6 D3DPLANE objects, and you must call this function everytime you change the camera position (not everytime you want to check a points visibility). An example:

'//In the declarations section
Private FrustumPlanes(0 To 5) As D3DPLANE

'//When you move the camera around
ComputeClipPlanes camerafrom, CameraTo, MakeVector(0, 1, 0), PI / 4, 0, DrawDepth, 1

the ComputeClipPlanes( ) call uses the same parameters that you have done for your view and projection matrices.

Finally, after we have constructed the information that we need we have to be able to use it. The next piece of code (also from the SDK files) shows us how we can pass a sphere and it'll tell us if it's visible or not:

Private Function CheckSphere(Center As D3DVECTOR, Radius As Single) As Boolean
Dim TCenter As D3DVECTOR
Dim Matrix As D3DMATRIX, I As Long
Dim Dist As Single

D3DDevice.GetTransform D3DTS_WORLD, Matrix

D3DXVec3TransformCoord TCenter, Center, Matrix


For I = 0 To 5
    Dist = D3DXPlaneDotCoord(FrustumPlanes(I), TCenter)
        If Dist < -Radius Then
            CheckSphere = False 'not visible
        Exit Function
    End If
Next I
CheckSphere = True 'visible

End Function

In order to use this we pass the point in question as the Center parameter, and a radius of your choice as the second. The radius can be very small (0.00001 or something) if you only want to check the point, if you want to check a large area you can increase the radius. If any part of the sphere is visible then the function returns true.

The fact that it returns true for any of the sphere being visible is it's only downfall, but it only means that you need to be a little more careful when you're using the method. If you used an entire sphere for a model, and the model only occupied a small part of the sphere (yet it required a large radius) then you could get the situation where it renders the model - but it's not actually on screen. To solve this you would want to investigate using multiple spheres and correlating the results.


4. Projection/Bounding Box culling

This final method is my current favourite, I first read up on it in the Visual Weather Documentation, having since explored its usage I've decided it's a very easy to use, fast and very accurate as well - just what I like.

What we are trying to achieve with these algorithms is to rule out any unnecessary geometry that wont appear on screen, therefore, if we could find out where a point will be projected from 3D space into 2D space we would be able to tell if it's within the screen boundaries. Fairly simple really. We could then expand this to be using a bounding box method, where we choose a relevent size box that suits the model we're querying - we then work out if any/all of the 8 corners of the cube will be on the sceen, if any of them are then at least part of the model should be visible. If you wanted you could check every major vertex in the model, but for complicated models this would be quite slow - and start to eat away from the speed advantage that we're chasing.

Luckily for us, DirectX8, in the form of the D3DX helper library has a little function that allows us to give a 3D point and recieve the 2D coordinate for where it would be rendered on the frame buffer, it looks like this:

D3DXVec3Project( _ 
    VOut As D3DVECTOR, _ 
    V As D3DVECTOR, _ 
    Viewport As D3DVIEWPORT8, _ 
    Projection As D3DMATRIX, _ 
    View As D3DMATRIX, _ 
    World As D3DMATRIX)

It's fairly easy to use, the parameters required are:

VOut as D3DVECTOR - this holds the screen space coordinates for the point you want transformed, the first two components X and Y are what you'd expect, the Z component gives you the depth buffer value that the point would recieve (you can then tell if it's behind certain things, or beyond a certain distance).
V as D3DVECTOR - this is the point that we want to transform, bare in mind that this point will be pre-transformed by the world matrix first and therefore may not be exactly where you think it is.
ViewPort as D3DVIEWPORT8 - This describes the screen that its transforming to, this is simply a desciption of how the device is set up - resolution etc... you can retrieve the current viewport settings by calling D3DDevice.GetViewport and providing an empty D3DVIEWPORT8 structure
Projection as D3DMATRIX - This is the current projection matrix, it's important that this is accurate
View as D3DMATRIX - This is the current view matrix or camera setup - this is obviously important...
World as D3DMATRIX - This is the current world transformation state, your point will be transformed by this matrix before being projected onto the screen

If we pass the correct parameters, we'll be given a 2D coordinate that tells us where the point would appear if we were going to render it. On a side note, this method is extremely useful if you want names (in 2D) to be presented above a player (3D) in a game, or want text/health bars to follow a character/unit around.

Now we can get the 2D point, we need to know what to do with it, how we coordinate the rest of the data with a bounding box to tell if an area of 3D space is going to be visible. The following diagram will help explain all the possible situations:

Take the above representation of 9 bounding boxes, we're only interested in the vertices, not the lines - the lines are there just to make it easier to see. If we go through all of these cubes we can tell if they're in or out of the blue square, which represents the visible area of the screen (0-1024 and 0-768 for example), a cube is visible if any of the vertices is within the blue square - simple as that, a square is not visible if all of the vertices are outside the square. In the above diagram all but cube 7 are going to be partly visible. Unfortunately it's not going to be as simple as that, take the next diagram for example:

In this diagrame both of the triangles will of been rejected based on our previous rules - yet it's quite obvious that they are both going to be partly visible. To take this into account we need to know where off the screen the points are - are they to the left, to the right, above or below? only if all the vertices are to one of the extremes can we be certain that it's definately not a visible region. To sum things up the following list will be the rules for acceptance/rejection:

• if any of the vertices are within the screen area the box is PARTLY VISIBLE
• if all of the vertices are within the screen area the box is TOTALLY VISIBLE
• if all of the vertices are to a far extreme (up/down/left/right) then the box is TOTALLY INVISIBLE
• if all of the vertices are out of the screen area, but not in the same extreme the box is PARTLY VISIBLE
• if the above is true, but all the vertices are greater than the two adjacent extremes then the box is TOTALLY INVISIBLE

The above set of rules should work for 99.9% of cases, you may find the odd exception to the rule, if you do ammend the list and carry on...

We now want to generate a generic function that returns one of eight states, the reason for having lots of states will be seen later, where we need to know what sort of invisible we're talking about. The eight states are: Partly Visible, Totally Visible, Totally Invisible, To Screen Left, To Screen Right, To Screen Top, To Screen Bottom and To Screen Back. The code I've written for this is the following:

'## This function takes a 3D point and transforms it into screenspace,
'## it also checks against the depth buffer and screen boundaries, resulting
'## in either Totally visible or Partly visible return values.

Private Function ProjectionVisibilityTesting(Point3D As D3DVECTOR) As VisTest
'//0. Any variables
    Dim vRet As D3DVECTOR
    Dim VP As D3DVIEWPORT8
    
'//1. Collect the data
    D3DDevice.GetViewport VP
    D3DXVec3Project vRet, Point3D, VP, matProj, matView, matWorld
    
'//2. correlate data
    If vRet.X < VP.X Then
        ProjectionVisibilityTesting = TOSCREENLEFT
        Exit Function
        
    ElseIf vRet.X > VP.Width Then
        ProjectionVisibilityTesting = TOSCREENRIGHT
        Exit Function
        
    ElseIf vRet.Y < VP.Y Then
        ProjectionVisibilityTesting = TOSCREENTOP
        Exit Function
        
    ElseIf vRet.Y > VP.Height Then
        ProjectionVisibilityTesting = TOSCREENBOTTOM
        Exit Function
        
    ElseIf vRet.Z > VP.MaxZ Then
        ProjectionVisibilityTesting = TOSCREENBACK
        Exit Function
    
    ElseIf vRet.Z < VP.MinZ Then
        ProjectionVisibilityTesting = TOSCREENBOTTOM
        Exit Function
        
    Else
        ProjectionVisibilityTesting = TOTALLYVISIBLE
        Exit Function
        
    End If
    
End Function

this function can then be extended to take a 3D box, representing an area of space - and check if that's visible or not, it is this code that required the greater detail of invisibility flags - this function would not work properly without them. The great power of this part is that you can rule out vast areas of 3D space with only 6 calculations, if the corners of the box are all invisible, every point inside will also be invisible...

Private Function ProjectionVisibilityBoundingBox(BBox As Box3D) As VisTest
'//0. Any variables
    Dim Results(0 To 7) As VisTest
    
'//1. Perform tests
    Results(0) = ProjectionVisibilityTesting(BBox.Coord(0))
    Results(1) = ProjectionVisibilityTesting(BBox.Coord(1))
    Results(2) = ProjectionVisibilityTesting(BBox.Coord(2))
    Results(3) = ProjectionVisibilityTesting(BBox.Coord(3))
    Results(4) = ProjectionVisibilityTesting(BBox.Coord(4))
    Results(5) = ProjectionVisibilityTesting(BBox.Coord(5))
    Results(6) = ProjectionVisibilityTesting(BBox.Coord(6))
    Results(7) = ProjectionVisibilityTesting(BBox.Coord(7))
    
'//2. correlate the data
    
'//handle simplest cases first:
    If Results(0) = TOTALLYVISIBLE And Results(1) = TOTALLYVISIBLE And Results(2) = TOTALLYVISIBLE _ 
And Results(3) = TOTALLYVISIBLE And Results(4) = TOTALLYVISIBLE And Results(5) = TOTALLYVISIBLE _
And Results(6) = TOTALLYVISIBLE And Results(7) = TOTALLYVISIBLE Then
'if all of them are visible then return totally visible
        ProjectionVisibilityBoundingBox = TOTALLYVISIBLE
        Exit Function
        
    ElseIf Results(0) = TOTALLYVISIBLE Or Results(1) = TOTALLYVISIBLE Or Results(2) = TOTALLYVISIBLE _
Or Results(3) = TOTALLYVISIBLE Or Results(4) = TOTALLYVISIBLE Or Results(5) = TOTALLYVISIBLE _
Or Results(6) = TOTALLYVISIBLE Or Results(7) = TOTALLYVISIBLE Then
'if any of them are in the viewing area, return partially visible
        ProjectionVisibilityBoundingBox = PARTLYVISIBLE
        Exit Function
    End If
    
    
'//Handle the extremes/invisibility cases
    If Results(0) = TOSCREENBACK And Results(1) = TOSCREENBACK And Results(2) = TOSCREENBACK _
And Results(3) = TOSCREENBACK And Results(4) = TOSCREENBACK And Results(5) = TOSCREENBACK _
And Results(6) = TOSCREENBACK And Results(7) = TOSCREENBACK Then
'all of the points are beyond the back clipping plain
        ProjectionVisibilityBoundingBox = TOTALLYINVISIBLE
        Exit Function
        
    ElseIf Results(0) = TOSCREENLEFT And Results(1) = TOSCREENLEFT And Results(2) = TOSCREENLEFT _
And Results(3) = TOSCREENLEFT And Results(4) = TOSCREENLEFT And Results(5) = TOSCREENLEFT _
And Results(6) = TOSCREENLEFT And Results(7) = TOSCREENLEFT Then
'all of the points are to the left of the screen
        ProjectionVisibilityBoundingBox = TOTALLYINVISIBLE
        Exit Function
        
    ElseIf Results(0) = TOSCREENRIGHT And Results(1) = TOSCREENRIGHT And Results(2) = TOSCREENRIGHT _
And Results(3) = TOSCREENRIGHT And Results(4) = TOSCREENRIGHT And Results(5) = TOSCREENRIGHT _
And Results(6) = TOSCREENRIGHT And Results(7) = TOSCREENRIGHT Then
'all of the points are to the right of the screen
        ProjectionVisibilityBoundingBox = TOTALLYINVISIBLE
        Exit Function
        
    ElseIf Results(0) = TOSCREENTOP And Results(1) = TOSCREENTOP And Results(2) = TOSCREENTOP _
And Results(3) = TOSCREENTOP And Results(4) = TOSCREENTOP And Results(5) = TOSCREENTOP _
And Results(6) = TOSCREENTOP And Results(7) = TOSCREENTOP Then
'all of the points are off the top of the screen
        ProjectionVisibilityBoundingBox = TOTALLYINVISIBLE
        Exit Function
        
    ElseIf Results(0) = TOSCREENBOTTOM And Results(1) = TOSCREENBOTTOM And Results(2) = TOSCREENBOTTOM _
And Results(3) = TOSCREENBOTTOM And Results(4) = TOSCREENBOTTOM And Results(5) = TOSCREENBOTTOM _ 
And Results(6) = TOSCREENBOTTOM And Results(7) = TOSCREENBOTTOM Then
'all of the points are off the bottom of the screen...
        ProjectionVisibilityBoundingBox = TOTALLYINVISIBLE
        Exit Function
        
    End If
    
    '//Handle the tricky cases, where they occupy two extremes...
        'these have already been handled by the above logic system, currently it will only
        'flag invisibility if the tile has ALL vertices in the same extreme, therefore allowing those
        'boxes that occupy two extremes. It also handles the sub-case of this where it's in two extremes
        'AND out of range - this is also handled, in order to have this case the vertices must be beyond 2 extremes,
        'and it's already handled for 1 extreme - so there's no need to check for two.

    
End Function

We can now use these functions quite simply to render a tile (or not), the following code excerpt takes a 3D flat tile and checks it's visibility before rendering it:

box.Coord(0) = VertList(0).P
box.Coord(1) = VertList(1).P
box.Coord(2) = VertList(2).P
box.Coord(3) = VertList(3).P
box.Coord(4) = VertList(0).P 'because it's a flat tile, we make the cube flat...
box.Coord(5) = VertList(1).P
box.Coord(6) = VertList(2).P
box.Coord(7) = VertList(3).P
    
res = ProjectionVisibilityBoundingBox(box)
  
If res = PARTLYVISIBLE Or res = TOTALLYVISIBLE Then
    TileDrawn = True
    D3DDevice.DrawPrimitiveUP D3DPT_TRIANGLESTRIP, 2, VertList(0), Len(VertList(0))
End If

simple really!


5. Tips and Tricks

Now that you have 3 techniques under your belt I'll discuss some further uses for these techniques, and a few other simple tricks for reducing the amount of geometry you need to render. The following list is by no means a definative guide - just a starter, you can look up these ideas further, or combine and alter them to fit whatever you want to do...

  • LOD Algorithms. Level Of Detail algorithms can reduce the amount of geometry you need to render, or in the case of landscapes and wide open spaces can dramatically increase the visible distance. Think about it logically, the geometry in the distance will not be visible in quite the same detail as that in the foreground, so why render it in such a way. Reducing the texture detail and geometry density (vertex/triangle count) will allow you to draw things further away without using up large amounts of processing time. LOD algorithms can be quite complicated, but there are several good articles around.
  • Invisible Geometry. This is more likely to be a thing that you'll add to your level editor rather than do it in realtime. If you have your view locked to a certain position or have it restricted to certain areas then use this to your advantage - dont draw, or even consider drawing parts of a world that will never be visible. A good example of this would be the tops of mountains - if the camera will never get up high enough to see the top of a mountain there's no point even creating the mountain top - let alone checking it for visibility every frame. The same can go for rooms in a first-person environment, if the level designer puts a room, or some geometry that can never be seen by the camera/player remove it. Determining if a piece of geometry will be visible could be extremely difficult - so this method may or may not suit your game engine.
  • Unlit/dark geometry. Take the first person example again, if an entire room is unlit and completely dark in some cases you could get away without drawing any of it! this only works if there isn't anything behind that will become visible (sky/other parts of the level).
  • Bounding Box sectors. This was mentioned briefly in the projection culling section. If you have your level divided into large, regular sections, or you can design your world to be - testing against the bounding box of this area will let you know if the entire area is visible/invisible - in either case you know that there is no need to visibility-test anything inside the box as it's either all visible or all invisible. It gets a little more tricky when only part of the box is visible.
  • Quadtrees. These are an extremely popular technique for landscape engines and extend the bounding box theory. This algorithm can reduce the number of visibility tests by 80% in some cases, meaning that whilst not drawing any excess geometry you also reduce the number of calculations done to achieve this. There is a good article on www.gamedev.net about this.
  • BSP (Binary Space Partions) Tree. These tend to always be mentioned in terms of first person shooters, but they can be used for other game types as well. The principle behind them is very similiar to that of a quadtree. Check out GameDev.net or Gamasutra.com for articles about this technique

techniques do not need to be limited by anything in this article, designing a custom method that suits your game will often be much better than trying to twist your game to fit another algorithm. If you are at the planning stage of a game then designing the world to suit one of these algorithms could be a good idea though...


Hopefully you now have all of the information required to get started on optimising the rendering part of your game. Several of the ideas in section 5 could have been covered here, but it would have made for a massive article so I decided against it - in favour of pointing you to better dedicated articles.

As usual you can download the complete source from the top of the page.

DirectX 4 VB 2000 Jack Hoxley. All rights reserved.
Reproduction of this site and it's contents, in whole or in part, is prohibited,
except where explicitly stated otherwise.
Design by Mateo
Contact Webmaster