Backface culling method

In 3d one needs to cull back-facing triangles before the render process so as not to render triangles that will never be seen by the observer.

There a couple of ways you can do this and at various stages in the pipeline.

Dotting:
One way is to take the dot product of the triangle’s normal with the vector from the camera’s position (transformed into object space) to the polygon.
(this can be sped up a little by using the vector of the camera’s position to the mesh, then you don’t have to recalculate it for each triangle).

Winding:
this can only be done once all points in a triangle have been projected into screen space (x and y coordinates) and works by determining if the points are in a clockwise or counter-clockwise order.

Pros:
dotting can be done at an earlier stage thus potentially reducing the number of points that need to be projected in the projection stage.
winding is easy to implement and involves very few mathematical operations.

Cons
dotting is slower, well it seems to be in actionscript anyway.
winding, done at a later stage in the pipeline so it potentially misses an opportunity to cull early and save some operations at other stages.

Conclusion:
I have always opted for the winding method because of its ease and speed. Even though have to project EVERY point in your scene before hand, this has never proven to be an issue as projection of many thousands of points seems to be a very quick and easy task. (and I have tried using my own matrix classes, the inbuilt ones and even a pixel bender implementation….all of which laugh at such a task).

Sub-conclusion:
I still think there is room for improvement so time to invent some methods to help speed it up even more.

Result of sub-conclusion:
I was thinking about different ways to speed this up and had a thought while looking at the bounding box around my meshes. With any given mesh you can only ever see at most 3 of its 6 sides and a minimum of 1! So I figured if I could find a simple way to assign each triangle to one of those sides then maybe I could cull whole groups of triangles.

What resulted was a method run after a mesh is created to loop through each of the triangles and assign them an integer id (1, 2, 4, 8, 16, or 32 for bitwise usage later) based on which bounding box side they are most facing.

Then when it came to culling all I had to do was project the bounding box of the mesh, loop through its faces to check their visibility and build a bit mask. Once this is done I could loop through the triangles and before doing a winding check I could use a simple bitwise AND operation: if(triangle.id & mask) == 0), and if it passes that skip the winding check.

Now this worked but the speed up gained was sooooo small it was almost not worth my time πŸ™
This is because the current technique will only give the triangle the id of the BB side it is MOST facing, this does not guarantee it is not also facing another side, so it cannot be used to disregard triangles but only skip the winding check. (and only for on average 1/6th of the triangles).

I have tried dotting the face normals with the BB side normals to produce a broader cull but didn’t get it working πŸ™

Anyone else got any amazing ideas to help speed up a process that probably doesn’t actually need it?

edit:
here are some images of the culling produced by this method alone (without additional winding culling)

2 Responses to “Backface culling method”

  1. Anyone else got any amazing ideas to help speed up a process that probably doesn’t actually need it?

    Backface culling is pretty simple, as you described above, but the larger topic of hidden surface determination has lots of techniques that are more applicable to larger, more complex 3D scenes. For example, game levels often use pre-processing techniques like binary space partitions and portal rendering.

  2. bwhiting says:

    thanks for the linkskiis
    I’ve had a look at that kinda thing but normally they scare me so I have been focusing on a mesh level culling of triangles at the mo.

    It’s funny you should mention though as my next post was going to be on (and still probably will be) an idea I had for occlusion culling πŸ™‚

Leave a Reply