Hello all,

For some time now, I have been writing a simple graphics library for a home-built game system built out of an AVR chip. I am using AVR c to develop the library. I have it displaying simple wireframe 3D primitives and models and moving them around (rotation is for another post). I want to create some sort of simple z-culling, but don't really know where to start. I heard that if you generate normals for each triangle in the shape and check if it's Z value is positive, you can determine if it gets rendered or not. Is this true? If so, how would I go about generating normals on a triangle using the simplest, least power-consuming way? If this isn't true, what is the simplest way to do Z-Culling?

Thank you all!

Z-Culling is culling objects that are obscured by depth. Culling triangles that are not facing towards the camera is typically instead done by checking the winding order of the triangles. I.e. triangles that when after projection to the screen, would have their vertices plotted either clockwise or counter-clockwise.

This can be done by checking for triangle A,B,C which side of line A,B point C falls:

float2 AB = (B-A);

float2 AC = (C-A);

float2 tangentAB = float2(AB.y, -AB.x);

bool frontFacing = dot(tangentAB , AC) >= 0;

If you want to cull by depth, you need to implement a depth buffer of some description.

Due to hardware limitations, I rewrote the equations so that they would work on the chip, however, it does not look right...

int projx1 = projectedx(x1, z1, FOV);
int projy1 = projectedy(y1, z1, FOV);
 
int projx2 = projectedx(x2, z2, FOV);
int projy2 = projectedy(y2, z2, FOV);
 
int projx3 = projectedx(x3, z3, FOV);
int projy3 = projectedy(y3, z3, FOV);
 
int a[2] = {projx1, projy1};
int b[2] = {projx2, projy2};
int c[2] = {projx3, projy3};
 
int a1[2] = {projx2 - projx1, projy2 - projy1};
int b1[2] = {projx3 - projx1, projy3 - projy1};
int tanab[2] = {TAN[a1[1]], TAN[0-a1[0]]};
//tangent tables are pre-generated
int projected;
if((tanab[0] * b1[0]) + (tanab[1] * b1[1]) >= 0){projected = 1;}else{projected = 0;}
if(projected == 1){
//draw triangle
}

This is the image it generates (a basic dodecahedron model that loads fine in wireframe mode)

The visible lines randomize as the object is translated about the screen...

[attachment=17103:ZCulling.png]

That's because you've added a call to TAN instead of using the variable tangentAB which has nothing to do with TAN (it's the 2d normal of an edge in screen space).

The formula for back face culling in screen space (i.e. after the polygons have been transformed into screen space) is this anyway (v1, v2, v3 verts of the triangle in screen space)

d1.x = v3.x - v1.x
d1.y = v3.y - v1.y
d2.x = v3.x - v2.x
d2.y = v3.y - v2.y

If you now calculate the crossproduct of these two vectors you'll get another vector. This vector points out of the polygon (it's called the polygon normal vector if you don't already know this). If the z-component of this vector is negative the polygon faces away from the camera and the polygon can be skipped. Complete Formula: z = (d1.x * d2.y) - (d1.y * d2.x)

If that culls the wrong polygons then cull if the z value calculated above is positive instead of negative.

EDIT: Note - you don't need to calculate the 3d cross product, all you are interested in is the z component of the cross product, so you only need to calculate d1, d2 and z.

I rewrote the equations as stated above, but I still have a problem (albiet not random clipping). Positive or negative I get the same result. One or two lines get clipped, but they flicker as I move the shape. After seeing this, I decided to render a simple triangle that can be translated. As I translate it, the Z value jumps all over the place. it starts at 50...

TRIANGLE STARTING COORDINATES:

v1: -5, 0, 0

v2: 0, 5, 0

v3: 0, 0, -5

Here is a video demonstrating the problem:

You need to use v1, v2 and v3 as the values after they have been transformed into screen space... are you doing that? Then you only use the x and y coordinate of the triangle in screen space (the v1.z, v2.x and v3.z values can be ignored, note that they aren't used in the equations from my post. The z coordinate would be used for z buffering though).

The calculated z value (d1.x * d2.y) - (d1.y * d2.x) will vary as the triangle rotates, it is proportional to the area of the polygon on screen.

When I rotate the triangle, the zculling seems to work just fine (outputs negative as it turns away and then doesn't render the triangle while the z value is negative) however, when I try to render ANY model or other shape, it just doesn't seem to work...

the pseudo code for my model loader is:

for(all the faces)

{

drawTriangle(face.x1, face.y1, face.z1, face.x2, face.y2, face.z2, face.x3, face.y3, face.z3, 0);

}

The function I am using the draw the triangles is:

void drawTriangle(int x1, int y1, int z1, int x2, int y2, int z2, int x3, int y3, int z3, int angle)
{
if(angle != 0){
float value=angle*3.14/180;
z1 = z1*(cos(value));
x1 = x1*(sin(value));
x2 = x2*(sin(value));
z2 = z2*(cos(value));
x3 = x3*(sin(value));
z3 = z3*(cos(value));
}
int projx1 = projectedx(x1, z1, FOV);
int projy1 = projectedy(y1, z1, FOV);
 
int projx2 = projectedx(x2, z2, FOV);
int projy2 = projectedy(y2, z2, FOV);
 
int projx3 = projectedx(x3, z3, FOV);
int projy3 = projectedy(y3, z3, FOV);
 
int a[2] = {projx1, projy1};
int b[2] = {projx2, projy2};
int c[2] = {projx3, projy3};
 
int a1[2] = {projx3 - projx1, projy3 - projy1};
int b1[2] = {projx3 - projx2, projy3 - projy2};
int z = (a1[0] * b1[1]) - (a1[1] * b1[0]);
char output[8];
itoa(z, output, 10);
LcdGotoXYFont(1,1);
LcdStr(FONT_1X, output);
if(z >= 0){
 
 
if(projx1 >= 0 && projx2 >= 0 && projy1 >= 0 && projy2 >= 0 && projx1 <= 84 && projy1 <= 48 && projx2 <= 84 && projy2 <= 48){
LcdLine( projx1, projx2, projy1, projy2, PIXEL_ON);
}
if(projx2 >= 0 && projx3 >= 0 && projy2 >= 0 && projy3 >= 0 && projx2 <= 84 && projy2 <= 48 && projx3 <= 84 && projy3 <= 48){
LcdLine(projx2, projx3, projy2, projy3, PIXEL_ON);
}
if(projx1 >= 0 && projx3 >= 0 && projy1 >= 0 && projy3 >= 0 && projx1 <= 84 && projy1 <= 48 && projx3 <= 84 && projy3 <= 48){
LcdLine(projx1, projx3, projy1, projy3, PIXEL_ON);
}
}
}

What does "doesn't work" mean? Are all the triangles consistent in their winding order (i.e. the 3 vertices are either clockwise or anticlockwise)?

What is angle supposed to be in your drawTriangle function? I was kind of expecting to see a rotation matrix, not a single angle... I suspect that may be your problem... what happens if you draw a cube in wireframe (ignore backface culling for now, concentrate on getting the world->screen transform correct). You want to see if the cube looks correct when it is rotating around each of its axes as well.

Ignore the angle function for now. It was just put in to test some things (notice that it isn't even being called with the model loading). "Doesn't work" means that there is no change from the way it was functioning in the video.

In the video it looks like 2 of the lines are disappearing? That must mean the screen bounds check is failing for 2 of the lines? Or is it just flickering and in reality all 3 lines are being drawn? What does projectedx and projectedy do? How are you translating the triangle?

You should print the screen coordinates of the triangle to the screen as well (i.e. (x1, y1), (x2, y2), (x3, y3)) - or set a breakpoint and have a look at them (if you can do that on the device you are using).