backface culling

[Stonemonkey]

Not a question but something I found interesting and may be relevent to hardware and software although not much use if you're using triangle lists or anything like that.
A lot of the time I do the backface culling by transforming the camera to object space and find a vector from the camera to a point on the triangle plane (one of the verts) then dot that with the tri normal.
After a bit of discussion I learned that it's possible to simply dot the camera coords with the triangle normal and compare the result with a pre computed value stored in the triangle struct.
The pre computed value is just found by calculating the dot of any of the triangle verts with the triangle normal.
Unfortunately this doesn't work if the object is scaled.
Don't know if anyone else'll find a use for that but I thought I'd post it anyway.

Cheers,
Fryer.

[rain_storm]

I always do it with cross-product of final 2D perspective co-ords for the tri. Is it faster to do it using dot-product before applying perspective?

[Stonemonkey]

It might depend on what you're doing, I've read some articles that say you're best to process all your vertices in one go before going on to draw the triangles but sometimes there can be quite a lot that needs to be done for each vertex such as would be the case for transforming camera and light coords to texture space for normal mapping and of course there's the divide for perspective.

This is some pseudo code for roughly what I have at the moment showing a couple of other things that I'm doing but doing the backface culling like this means the triangle can be rejected without touching any of the vertices.

Code: [Select]

//loop through all objects and do quick test to see if it might be within view of the camera
//and add to a list if it is possibly visible
//z-sort all objects in list from front to back


for object=list.first_object to list.last_object

  camera_o=camera transformed to object space


  do z-buffer occlusion test using bounding box around the object, the first pixel that's visible exits and returns a pass

  if z buffer occlusion=pass then


    triangle=object->first_triangle

    while (triangle<>0)

//backface culling
      if (triangle->nx * camera_o->x + triangle->ny * camera_o->y + triangle->nz * camera_o->z) > triangle->d then


        do_vertex_calculations //I have a flag in the vertex struct which is set to tell if it's already
                               //been computed for a previous triangle for this object.

        draw_triangle

        triangle=triangle->next_triangle

      else

//if there are several triangles on the same plane, if one fails backface culling then they all will
//and for example, if there are recesses within those several triangles such as windows then they
//can all be rejected too (unless the camera is capable of entering those recesses).

        triangle=triangle->next_triangle_group

      end if

    wend


  end if

next object


[ninogenio]

as always excellent stuff fryer! k+

i can see how this could give some good speed ups in some casses.

[Stonemonkey]

Thanks nino.

To take the triangle grouping thing a bit further, this image shows the sort of thing I'm meaning:



The triangles with the same colours are on the same plane, if that was one side of a building and the first triangle of the wall fails the backface test then they can all be rejected at once without any more tests (and without having to look up a single vertex). If however it passes then the outer wall and the centre window panels can be drawn.
The ingos that return into the windows though can be divided into other groups and if the light orange ones on the far right fail then the grey ones on the other windows must also fail and that can be repeated for the other inside sides of the windows.

One thing I've still to come up with is a way to loop through all the triangles that are on the same plane without doing the backface test for them all, just the first.

It does have fairly limited application though as it depends on the model containing triangles sitting on similar planes so I'm trying to do this with as little impact as possible for going through the list of triangles.

[rain_storm]

I see what you mean. grouping polys like this is a great idea and so simple and since they all lie on the same plane just one backface check is required the result will be the exact same along that infinite plane. no need to waste time, K up sm that will come in useful

Edit - sm I dont think this is as limited as it first appears it is perfect for axis aligned boxes but cylinder (tunnels) should also lend themselves nicely spheres of course will get messy

[Stonemonkey]

sm I dont think this is as limited as it first appears it is perfect for axis aligned boxes but cylinder (tunnels) should also lend themselves nicely spheres of course will get messy

I don't quite get what you mean.

[rain_storm]

If the cylinder is axis alligned than each column of polys will lie on the same plane you can still use this meathod to speed up all visibility checks. It just a matter of grouping them according to column test one then draw the rest if that one passes. so if the cylinder has only 16 sides but the length is many polys deep you only test each side

[Stonemonkey]

Ah right, yep. Another thing that just occured to me could be for stuff like internals in buildings when viewed through windows from the outside.

[hellfire]

The triangles with the same colours [...] can all be rejected at once without any more tests

On the other hand, given that your object is not completely inside the view-frustum, you need to do a frustum-test on each vertex anyways - which requires a dot-product for each (six) frustum-plane.
In that case it's cheaper to just transform (matrix*vector is basically 4 dot-products) the vertices to camera-space and all benefit from object-space backface-culling is already gone
Still, batching triangles of similar orientation is usually a good idea to reduce overdraw (see this paper - and this, too).

[Stonemonkey]

Thanks for the links but I don't really get what you're saying, even without the grouping of triangles each triangle can be tested with a single dot product without the need to do any transforms so if you had an object with 100 tris and 50 of them are visible to the camera then the other 50 can be rejected with a single dot product each and I only need to transform and shade the vertices of the visible tris.

With the grouping though, if a building had 4 walls made up of the image above then at least 2 of those walls could be rejected straight away with a total of 2 dot products (could be 3 walls rejected with only 3 dot products in some cases) and no need to transform any of the vertices that make up the walls or windows of those sides.

Another thing that I do is only do 3d clipping on the near plane, the rest is 2d clipping which is something that many wouldn't agree with but I have some calculations for accuracy of interpolation that the clipping fits into and is pretty much free.

Overdraw isn't really something I've considered much, object wise at least as I do sort objects front to back. The most I've done really is to order tris in such a way that external parts are drawn before internal (if only viewed from outside).

[hellfire]

You pointed out that you're doing backface-culling in object-space and only transform those vertices which actually belong to "visible" faces, thus saving transform & lighting for vertices on "invisible" faces.
However, if you need to perform clipping, it's again cheaper to do the clip-test on transformed vertices (where "vertex dot plane" becomes "x>z"). Given that ~50% of the faces get backface-culled, it's still faster to transform all vertices instead of testing only the "front-facing" vertices in object-space. So your optimization works best for geometry that doesn't need clipping.
But pulling most of the clipping to the 2D-side makes perfectly sense since it's basically free when doing subtexel-correction (hardware implementations do it the same way btw).
However, on limited hardware (the main field where software-rendering still comes in use) it's useful to have all polygons properly clipped and not wasting precious bits on an additional "guard-band"-area.

Given that faces are assembled from a shared pool of vertices (indexing), it usually makes sense to reorder faces & vertices to behave a bit more cache-friendly (since caches are small this means batching sets of locally connected faces together). You can also split those batches to create less intra-object-overdraw (no matter what direction you look from) - drawing objects front-to-back only reduces inter-object-overdraw.
That reordering is basically what d3dx' OptimizeMesh does for you.

[Stonemonkey]

ok, I think I see what you're getting at but I'm also assuming that there are more objects/triangles in a scene that won't require any clipping then there are that do.

[Jim]

From what you've been talking about there are two more things that spring to mind.
1) Using an invisible polygon to determine whether the interior of a room is visible is, a technique called Portals used a lot in Doom/Quake/Descent, etc.

2) When you group coplanar polys together for a visibility test, you can also say which polygons are not visible.  Interphase used a primitive technique like this to have a tree of visible polygons depending on just a few decision checks.  Taken to its logical conclusion, this ends you up at BSP trees.

Jim

[Stonemonkey]

Aha, thanks Jim.

1) That had occurred to me but I hadn't really looked into how I would fit it in.

2) OH NO! I'd also thought about BSP trees and don't want to go down that route, the thing about knowing which polys are not visible from knowing which are is something that had crossed my mind but not totally sure what to do with that idea but you have just given me something else to think about, I've only been thinking about a single list of polys that bits of can be missed out but it'd be possible without any changes to the code to have branches.