a question about fast backface culling

I am doing a research project on 3D graphics, and I need to clone the render pipeline. I am wondering how to do backface culling efficiently.

Think about I have 3 vertices in screen coordinate, if they are in count clockwise order, send them to rasterizer. If they are in clockwise order, throw them away. Then how can I determine their order quickly?

I know that I can get the two vectors of two edges and cross product them to get the normal, then dot product the normal with vector(0, 0, 1) and compare the result to 0, but I feel it is not that efficient. And if I am doing backface culling in a triangle strip, I even have to keep track the triangle’s order. Does anyone have a better solution of that?

[This message has been edited by Nil_z (edited 04-18-2001).]

Maybe I have not made myself clear in my post before, that I know the theory of backface culling. I only want to find a fast way to do it. And if I have the vertices in screen coordinate, I do not need to calculate the normal, I can determin wether to cull it by the vertex order: cull it if it is clockwise.

So, it there a way to determine the order of 3 vertices quickly?(actually, they are 2D vertices, since z is not used here)

[This message has been edited by Nil_z (edited 04-18-2001).]

do you even need to? If you use normals they may be the answer to your prayers. one dot product with the face normal and the camera direction vector should do the trick.

Why are you doing the culling in screen co-ords? surely culling them in 3D, prevents them being sent through the projection matrix?

As for the order, you define it. The function calls must appear in order…

3D graphics is never going to be computationally simple, thats why as much as possible is done in hardware

sorry missed the 2D bit, what order where the calls made in, work out that problem, get your answer. There’s no magical solution.

What I mainly want to do is to cull backface in a triangle strip, so I do not get the normal of those polygons directly. I need to calculate it per triangle. Then I send them to a hardware rasterizer. In those books, they said that culling backface will give you better performance, but I can not get a improved performance in my case, so I feel my method of culling backface is not fast enough. That’s why I post it here. Hope someone will give a hint.

[This message has been edited by Nil_z (edited 04-18-2001).]

http://ask.ii.uib.no/ebt-bin/nph-dweb/dynaweb/SGI_Developer/OpenGL_PG/@Generic__BookView;cs=fullhtml

About halfway down the page there is a formula for calculating the way a polygon is facing. I assume it is similar to the way OpenGL does it, seeing that it is in the Programming Guide.

I don’t understand the math, though .

j

sorry, the link do not work for me.
Oh, I forget the redbook! I find the formula, and I do not understand it either I will spend some time to study it, thanks J!

Your link didnt seem to work.

Anyway, there is also a method by which you can calculate the “area” if the triange. If the “area” is positive the triangle faces you. If “area” is negative, its back facing.

Sorry, I dont know the exact formula for calculating this as I have never used it, but I have seen it used somewhere (I think it was in one of the nvidia demos, but not sure which)

I know what the formular means now. It is equal to calculate 2 vectors of 2 edges of the triangle, then cross product them. We are back to the start point only this formula seems more straight forward.

>>What I mainly want to do is to cull backface in a triangle strip, so I<<

you cant do backface culling yourself for triangle strips , only for individual triangles. thing about removing a triangle in the middle of a strip.

I am working on a render pipeline for a piece of graphics hardware. If I want to cull a triangle in a strip, I just set a flag in the vertex data(the third vertex in a triangle), and the hardware will cull that single triangle for me

[This message has been edited by Nil_z (edited 04-18-2001).]

Well, the link works for me…

Must be a special link or something

I think most of you missed the point.

The question is:
>>Think about I have 3 vertices in screen coordinate, if they are in count clockwise order, send them to rasterizer. If they are in clockwise order, throw them away. Then how can I determine their order quickly? <<

If you already have a projection onto 2D (here xy-plane) The answer is to calculate the area of the triangle on that plane. This is done by adding the (signed) areas of the trapezoids built by the triangle edges and the x-axis. The sign of that gives the winding order.
No cross product, no 3D, only simple area calculations are necessary.

The formula should also be found somewhere in Foley and van Dam “Computer Graphics Principles and Practice”.

[This message has been edited by Relic (edited 04-19-2001).]

I would like to know more about the method Relic metioned, but I do not have the book Computer Graphics Principles and Practice. Can you give me some url?

Btw: which you think is faster? do culling in screen coordinate or in view coordinate?

[This message has been edited by Nil_z (edited 04-19-2001).]

I read the next question now:
>>What I mainly want to do is to cull backface in a triangle strip, <<

Simply forget it. Let OpenGL handle that it’s fully HW accelerated on T&L boards. Splitting triangle strips may cost more than the it’s worth.
Only gross view frustum culling should be done in software.

>>I would like to know more about the method Relic metioned, but I do not have the book Computer Graphics Principles and Practice. Can you give me some url?<<

It’s fairly simple. Take a piece of paper and draw xy-axis and a triangle. Draw vertical lines from each vertex to the x-axis you see skewed traprezoids which have one horizontal edge (the x-axis).
The algorithm is a for-loop over the vertices in the order you issued them. (I don’t have code at hand.) The x-difference between each two vertices of the triangle take care for the sign of the area of the trapezoid. The trapezoids outside the triangle become subtracted from the trapezoig including the triangle automatically.

Should be easy to figure out how that works now.

Originally posted by Relic:
[b]I think most of you missed the point.

If you already have a projection onto 2D (here xy-plane) The answer is to calculate the area of the triangle on that plane. This is done by adding the (signed) areas of the trapezoids built by the triangle edges and the x-axis. The sign of that gives the winding order.
No cross product, no 3D, only simple area calculations are necessary.

The formula should also be found somewhere in Foley and van Dam “Computer Graphics Principles and Practice”.
[/b]

Well, the length of the cross product of the edge vectors actually is the area of the paralellogram formed by those vectors, so testing the sign of that is just the same as testing the sign of the area of the triangle.

[This message has been edited by harsman (edited 04-19-2001).]

Yes, the mileage is probably identical if the cross product is special cased for z=0.

BTW, the algorithm with the trapezoids works for any numper of vertices as long as the polygon is planar and convex.
Hmm, I didn’t find it in Foley and van Dam now. I know I have a copy of the original somewhere…

hm… crosspoduct…

c.x = v0.y * v1.z - v1.y * v0.z
c.y = v0.z * v1.x - v1.z * v0.x
c.z = v0.x * v1.y - v1.y * v0.z

c.x and c.y are going to be 0 if v0 and v1 are 2dvecs ( means 2dvec = ( x, y, 0 ) in 3d )…

then c.z = v0.x * v1.y - v1.y * v0.z

and this now can be something nonzero… bigger if it is cw, smaller if ccw ( or other way around… )

dont think this takes too much time to calculate, does it?

bool cull( vec& v0, vec& v1, vec& v2 )
{
vec e0 = v1 - v0;
vec e1 = v2 - v0;
return e0.x * e1.y - e0.y * e1.x > 0 ? 1 : 0;
}

i have no answer if this culls now away cw or ccw, but it does on one thing

Aside from cross products, its possible to find CW and CCW by testing the XY positions in order. Simplisticly, from the 0 vertex, ‘left ( to v1 ) then below (to v2)’ or ‘right then above’ defines a CCW tri. I think that there are quite a few special cases to be handled, such as straight lines.

Leo

would the source code to a generic OpenGL implementation help?
(i asume there a pretty fast version of software backface culling in there)
should be usefull for the development of the rest of the pipeline to?
http://oss.sgi.com/projects/ogl-sample/

p.s. Nil_z get “Computer Graphics Principles and Practice” its been the standard book on coputer graphics for years. check your uni library if nessecery…