[SOLVED] Polygon Culling in NDC Space and in Window Space

[Key-Real]

Hi,

I'm writing a software renderer.

I need to cull n-gon in WindowSpace.

for a Triangle the Formula is:

Code: Pascal  [Select][+][-]

1. function v3dPolyBackface(p: v3dPoly): boolean;
2. var
3.      ax, ay, bx, by, cz : longint;
4. begin
5.     ax:= p.v[0].prjX - p.v[1].prjX;
6.     ay:= p.v[0].prjY - p.v[1].prjY;
7.     bx:= p.v[0].prjX - p.v[2].prjX;
8.     by:= p.v[0].prjY - p.v[2].prjY;
9.  
10.     cz:= (ax * by - ay * bx) div 2;
11.  
12.     if cz >= 0 then
13.                 result:= true else result:= false;
14. end;
15.  

how to Cull an n-gon?

[Eugene Loza]

I may be wrong, but as far as I know n-gons (even quads) need to be triangulated for that. There are several different ways to triangulage an n-gon though, but eventually it should be done.

[wp]

To be honest, I don't know the EXACT definition of an "n-gon".

• If it is defined as a convex polygon you could simply select any three consecutive points and apply your v3dPolyBackFace() function.
• Not sure about concave polygons. Maybe calculate your function for all consecutive three points, starting with the first point, and add the sign of the results.
• If a self-intersecting polygon is allowed, my geometric feeling tells me that "inner" and "outer" faces cannot be determined because the orientation of the points changes along the polygon.

BTW, your function has this code at the end:

Code: Pascal  [Select][+][-]

1.     cz:= (ax * by - ay * bx) div 2;
2.     if cz >= 0 then
3.                 result:= true else result:= false;

When cz >= 0 then its double value is >= as well --> you can skip the div 2.

And why can cz be equal to zero? This means that the triangle area is zero, i.e you have three collinear points. I don't know whether such a degenerate triangle should be considered by your application at all. You probably should check only against >0.

[Key-Real]

Yes, it is a simple convex Polygon, it has 4 Vertex.

By applying the function to the 0,1 and 2nd Vertex, leads to skipping some polygons(see image).
By applying the function to the 1,2 and 3rd Vertex to those Polygons, they are drawn correct, but not the rest.
I think some vertex are merged to each other.
I'm trying to solve this by computing the culling on 4 Vertexes.


and yes, "div 2" and ">=" are not needed.

[wp]

By applying the function to the 0,1 and 2nd Vertex, leads to skipping some polygons(see image).

You mean something like the black triangle in the center? This would mean that your renderer is working with triangles. Why do you need the culling value for quads then?

[Key-Real]

No, I work with Polygons.

It is a simple convex Polygon, it has 4 Vertex.

I think some vertex are merged to each other.

[wp]

I think some vertex are merged to each other.

Of course, if you happen to pick two coincident points in this calculation the resulting cx will be zero, and the cull value will become false (if you check for > 0) I think when this happens with points #0,#1,#2 you must proceed with #1,#2,#3 or #2,#3,#0 or even #3,#0,#1 until you find a nonzero value. But keep the order of points, always preceed in counter-clockwise (or clockwise) direction when selecting points for the triangle test.

[Key-Real]

can you pls rewrite this function for working with n-vertex?

number of vertex is p.numVertex

[wp]

I don't know your type declarations, so I'll use my own. Untested:

Code: Pascal  [Select][+][-]

1. type
2.   TPolygon = array of TPoint;
3.  
4. function IsBackFace(p: TPolygon): Boolean;
5. var
6.   i, j, k: Integer;
7.   a, b: TPoint;
8.   numPts: Integer;
9.   j1, j2, j3: Integer;
10. begin
11.   numPts := Length(p);
12.   i := 0;
13.   while i < numPts do
14.   begin
15.     j := (i + 1) mod numPts;
16.     k := (i + 2) mod numPts;
17.     a := p[i] - p[j];
18.     b := p[j] - p[k];
19.     c := a.x * b.y - a.y * b.x;
20.     if c <> 0 then break;
21.     inc(i);
22.   end;
23.   Result := c > 0;
24. end;

   
Since I don't know the order of the points you might have to negate the result, i.e. define Result := c < 0.

And, of course, I assume, that the polygon is convex.

[Key-Real]

unfortunately this didn't work

the polygon is valid, otherwise it would be discarded by the rasterizer.

I send you the engine to test with.

to compile go to ./v3d-code/src and look at ./l
if you under linux running this script should compile out of the box.

of course it works under windows and mac also

this function is ./v3d-code/src/v3dCode/v3d.Render.pas line 85;

[Key-Real]

and if the model comes nearly to the viewer this polygon is rendered properly

[wp]

One possible problem: my procedure is for 2d vectors but your polygons are built by 3d vectors.

Read wikipedia (https://en.wikipedia.org/wiki/Back-face_culling)
"One method of implementing back-face culling is by discarding all triangles where the dot product of their surface normal and the camera-to-triangle vector is greater than or equal to zero

    ( V0 − P ) ⋅ N ≥ 0

where P is the view point, V0 is the first vertex of a triangle and N is its normal, defined as a cross product of two vectors representing sides of the triangle adjacent to V0

    N = (V1 − V0) × (V2 − V0) "

The dot product and the cross-product can be calculated by your v3dDot and v3dCross, respectively, in the v3d.Math unit

You may notice that here we have the >= 0 again. But now I think it is justified. Zero value here means that the normal vector is perpendicular to the viewing vector - and such a triangle needs not be rendered because you see it only from its side.

[Key-Real]

This works in NDC space:

Code: Pascal  [Select][+][-]

1. function v3dPolyBackface(p: v3dPoly): boolean;
2. var
3.      d : single;
4.      n : v3dVector;
5.      i : longint;
6. begin
7.  
8.     n:=aVector(0, 0, 0, 1);
9.  
10.     for i:= 0 to p.numVertex - 2 do begin
11.         n:= n + v3dCross(p.v[i].v, p.v[i + 1].v);
12.     end;
13.     n:= n + v3dCross(p.v[p.numVertex - 1].v, p.v[0].v);
14.  
15.     d:= v3dDot(p.v[0].v, n);
16.  
17.     if d > 0 then
18.         result:= true else result:= false;
19. end;
20.  

p.v[vertexNum].v   is the vector of the Vertex



This works in WindowSpace:

Code: Pascal  [Select][+][-]

1. function v3dPolyBackface(p: v3dPoly): boolean;
2. var
3.      d : longint;
4.      i : longint;
5. begin
6.  
7.         d:=0;
8.  
9.         for i:= 0 to p.numVertex - 2 do begin
10.                 d:= d + (p.v[i].prjX * p.v[i + 1].prjY - p.v[i].prjY * p.v[i + 1].prjX);
11.         end;
12.         d:= d + (p.v[p.numVertex - 1].prjX * p.v[0].prjY - p.v[p.numVertex - 1].prjY * p.v[0].prjX);
13.  
14.  
15.         if d > 0 then
16.                 result:= true else result:= false;
17.  
18. end;
19.  

p.v[vertexNum].prjX and p.v[vertexNum].prjY are the projected coordinates in WindowSpace

[wp]

Just out of curiosity: Is it a recommended procedure to add the normal vertical of the quad's triangles? Shouldn't the normal vectors be normalized to unit length for this? Probably not, otherwise the second procedure in the projection plane would not work.

[Key-Real]

Normalization is just "scaling", this would not affect the sign.