early culling

OpenGL
1

if a surface normal is readily available, early culling takes only 3 mults to evaluate if that surface is frontfacing.

some tests i’ve made show that opengl don’t perform early culling, here i mean face culling in object space.
in fact, opengl can’t just know if the normal i’m supplying is the normal to a face or the normal to a vertex…

i would be useful to have it at driver-level, with a function call like glEnable(GL_EARLY_CULL_FACE)

it think it shoud be inserted as another step into the opengl pipeline, to make it work also with display lists and vertex arrays.

Dolo//\ightY

2

Actually I believe it only uses the normals for lighting/coloration, and that it calculates on its own whether the front face is visible or not (by generating a none normalized vector).

But I agree in some cases where memory is not much of a concern but performance is, that there should be a way to provide an face normal and plane constant (like glFaceNormal3f and or glFacePlaneConstant), the plane constant will remove the necesity to subtract a polygon vertex from the camera position in world space, reducing the calculation from 3 subtracts and 3 multiplies, down to 3 multiplies and 1 add. A programmer can store face normals and plane constants instead of opengl calculating one… There are some things though in this state OpenGL that opengl would have to have, like an inverse matrix to transform the camera from camera space to world space to object space, in order to move the camera into the object space and use the precalculated normal and plane constant.

Its a good idea, but it is a tradeoff between memory and performance so it will not be used by everyone, it depends on how their scene graph is programmed. A scene graph could be built though that could utilize GL_EARLY_CULL_FACE when it finds it necesary, for example on a system where a lot of memory is avaible but performance is not great, a sort of balancing act.

3

face plane constant: what do you mean?
can you point me somewhere?

currently i perform early culling to build a vertex array, since i found it a bit faster than straight opengl, but i still wish to optimize it

the way i’d like to be implemented in opengl is in a transparent way: since you always know that the camera is always at the origin, you need just to evaluate the inverse of the current modelview matrix, and to transform the origin point with this matrix.

by now i simply transpose the current modelview though i think this way won’t correctly work for a scaled modelview.

rethinkin’ about it, i see effectively that early culling will be difficult (if not impossible due to performance drop) to implement for immediate mode.

however it can make a difference for batches like display lists or more probably for vertex arrays.

about face normals, i’ve read somewhere that can also be used for collision tests… maybe i’m wrong, i can’t recall where i read this.
early culling this way could be obtained for free.

Dolo//\ightY

4

The plane constant is part of the plane equation…

Normal * Vector + pc = 0

The * is a dot product so it can also be seen as…

Normal.xVector.x + Normal.yVector.y + Normal.z*Vector.z + pc = 0

The Normal points away from the plane, the pc is the plane constant and the Vector points to the camera, but to do this the camera needs to be set relative to one of the vertices of a face (a point on the plane), so you have to subtract one of vertices from the cameras transformed position in object space to get this vector, if you are not doing it you should be to get better results, you may be drawing more polygons then you need to. If we normalize the Vector pointing to the camera we can then retrieve the cosine value between the normal and vector…

cosine = Dot (Vector, Normalize (Camera - Vertex[1]);

If the cosine value is greater then or equal to 0 (less then 90 degrees between Vector and Normal) then the polygon/plane is facing the camera, if it is less then 0 (greater then 90 degrees) then the polygon/plane is facing away.

To eliminate the need for subtracting a vertex from the camera position (in object space), you can store the plane constant which can be calculated by…

pc = -Dot(Normal, Vector);

The idea here is to make negative the dot product of a Normal times a point on the plane which happens to be one of the vertices of the face.

Once we have the dot product we can then use this equation to find out which side the camera is of the polygon…

if( Dot(Vector, Normal) + pc >= 0)
//its facing
else
//its not facing

I hope this was not to complicated an explanation , I could not find a good source for this info, I learned it from the book by Brian Hook “Building a 3d game engine in C++”.

Another interesting thing to note on the topic of matrices. A matrix is simply an set of 3 vectors (each pointing in diffrent directions of the axi x, y, and z) and a position of origin. So a matrix set to identity is…

X_Axis (1,0,0,0)
Y_Axis (0,1,0,0)
Z_Axis (0,0,1,0)
Origin (0,0,0,1)

The numbers represent X,Y,Z,W. W sets whether the X,Y,Z are a point or a vector, so if you notice Origin is a point (1), while X_Axis and the others are vectors (0), this has to do with the fact that vectors are not supposed to be translated while points are supposed to be. Anyway if you think about it this way you can create a short cut equation to calculate an inverse Origin instead of the entire inverse matrix, and if your camera is always at Origin (in camera space) then you can simply do an inverse Origin to place the camera in object space. Anway its interesting stuff, it would still be nice to have this ability, this would make a performance diffrence where you have huge objects where perforance is lowered by the polygon density.

5

no problem, i got it
i’ll try it soon…

thanks

Dolo//\ightY

6

I was just looking for some fancy extensions and then I happened to find this:
http://oss.sgi.com/projects/ogl-sample/registry/EXT/cull_vertex.txt

This extension introduces a method for culling vertices in object space based on the value of the dot product between the normal at the vertex and a culling eye direction.

(Though, I think if we have precalculated plane equations for the faces, just checking if the eye point is behind the plane or not would be faster.)

7

I think that is already planned for in the OpenGL 1.2 specs. Check this link out http://www.rs6000.ibm.com/doc_link/en_US/a_doc_lib/libs/openglrf/glClipPlane.htm .

It seems to me that it would be used real nicely for frustum clipping. I just wish the IHV’s would start writing 1.2 drivers…

8

doesn’t opengl current cull using a clockwise system eg if the points of a triangle are in a clokwise order from the viewer then don’t cull if they are anti-clockwise e.g. the other way then cull

9

Originally posted by Bassman:
doesn’t opengl current cull using a clockwise system eg if the points of a triangle are in a clokwise order from the viewer then don’t cull if they are anti-clockwise e.g. the other way then cull

Yes, but the culling is done in view space, and what we want to do is early culling in object space, so that invisible primitives don’t get transformed at all.

10

i read specs about vertex culling extension, but i’m a bit confused: how can it cull away faces if it is based on vertex normals?

what i mean is that it works, ie it cull away some faces, but since it works on vertex normals (wich are only sometimes needed, and this can be a problem), it apply just a gross culling.

early culling instead works on face normals, and produces the same output as standard eye space culling.

however, i’ve also improved the way i evaluate the inverse matrix, and now it supports non uniform scaling, without costly operations like sqrt().

Dolo//\ightY