Sign in to follow this  
Jesse Dager

Normals Calculation and Z-Culling

Recommended Posts

Jesse Dager    619

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!

Share this post


Link to post
Share on other sites
Digitalfragment    1504

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.

Edited by Digitalfragment

Share this post


Link to post
Share on other sites
Jesse Dager    619

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]

Share this post


Link to post
Share on other sites

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.

Edited by Paradigm Shifter

Share this post


Link to post
Share on other sites
Jesse Dager    619

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:

http://youtu.be/SrlRKC_OfOU

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
Jesse Dager    619

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);
}
}
}

Share this post


Link to post
Share on other sites

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.

Edited by Paradigm Shifter

Share this post


Link to post
Share on other sites
Jesse Dager    619

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.

Share this post


Link to post
Share on other sites

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).

Share this post


Link to post
Share on other sites
Jesse Dager    619

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).

The screen is a Nokia screen. The lines are being rendered, but the pixels are slow to respond. The webcam just can't pick it up (if you look REALLY closely, it is almost visible biggrin.png ). Also, I meant to say the picture. The model renders just as it does in the first picture pretty much no matter what I try. 

Share this post


Link to post
Share on other sites

I can't tell what the model is supposed to look like. Draw a cube first, start simple (and don't backface cull the cube until you know you are drawing it correctly). You are eventually going to have to clip lines that are partially off screen as well, as the code stands at the moment you are going to end up culling an entire triangle if a single vertex is transformed outside of the screen bounds.

 

If any polygons cross the near clip plane you will get weird results as well, you need to clip the polygons against that as well as against the screen bounds. (EDIT: You can just cull any polygons which have negative projected z coordinates for any vertex for now).

 

EDIT2: Any polygons entirely behind the near clip plane are going to be wrong as well. Make sure the whole model is in front of the near clip plane.

Edited by Paradigm Shifter

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this