Roman
25 posts
ups
3D Software rasterizer. triangle clipping problem
Edited by Roman on Reason: Initial post
Hi. I have been trying to implement my own 3D software rasterizer. Right now I am implementing triangles clipping. I have already tried to do it, but I don’t understand much how to do it correctly. The problem is I get wrong triangles after clipping stage.
1)So, the first step is translation from view space into clip space(homogeneous space). All code is here https://pastebin.com/fA1vWdrk. I appreciate any help. Thanks in advance.
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16  triangle *Triangle = &gTriangles[TriangleIndex]; v3 V0 = Triangle->Vertex[0]; v3 V1 = Triangle->Vertex[1]; v3 V2 = Triangle->Vertex[2]; // NOTE(shvayko): Transform to clip space f32 FOV = 90.0f; // NOTE(shvayko): f32 n = 1.0f; // NOTE: Near plane f32 f = 15.0f; // NOTE: Far plane f32 AspectRatio = (f32)WINDOW_WIDTH / (f32)WINDOW_HEIGHT; v4 ClipV0,ClipV1,ClipV2; TransformIntoClipSpace(FOV,n,f,AspectRatio,V0,V1,V2, &ClipV0, &ClipV1, &ClipV2); 

2) Then in clip space I use something like Cohen–Sutherland algorithm.
First of all, I check if all 3 triangle's points outside canonical view volume, I will discard entire triangle.
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 // NOTE(shvayko): Count how much vertices have Z > NearPlane u32 VerticesInsideZRange = 0; v4 TestVertices[3] = {ClipV0,ClipV1,ClipV2}; for(u32 VertexIndex = 0; VertexIndex < 3; VertexIndex++) { v4 CurrentTestVertex = TestVertices[VertexIndex]; if(CurrentTestVertex.x > CurrentTestVertex.w) { ClipCode[VertexIndex] |= CLIPCODE_X_GREATER; } else if(CurrentTestVertex.x < -CurrentTestVertex.w) { ClipCode[VertexIndex] |= CLIPCODE_X_LOWER; } else { ClipCode[VertexIndex] |= CLIPCODE_X_INSIDE; } if(CurrentTestVertex.y > CurrentTestVertex.w) { ClipCode[VertexIndex] |= CLIPCODE_Y_GREATER; } else if(CurrentTestVertex.y < -CurrentTestVertex.w) { ClipCode[VertexIndex] |= CLIPCODE_Y_LOWER; } else { ClipCode[VertexIndex] |= CLIPCODE_Y_INSIDE; } if(CurrentTestVertex.z > CurrentTestVertex.w) { ClipCode[VertexIndex] |= CLIPCODE_Z_GREATER; } else if(CurrentTestVertex.z < -CurrentTestVertex.w) { ClipCode[VertexIndex] |= CLIPCODE_Z_LOWER; } else { ClipCode[VertexIndex] |= CLIPCODE_Z_INSIDE; VerticesInsideZRange++; } } // NOTE(shvayko):Check if all 3 points outside canonical volume if(IsTrivialReject(ClipCode,Clipping_CheckX) || IsTrivialReject(ClipCode,Clipping_CheckY) || IsTrivialReject(ClipCode,Clipping_CheckZ)) { // NOTE(shvayko): Go to the next polygon continue; } 

If there are vertices beyond near clipping plane(=1.0f), the next step will be clipping.If there are not vertices beyond near clipping plane then do perspective divide(Divide by W), then viewport transformation and rasterization. Maybe I am doing solving line equation wrong?

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140  // NOTE(shvayko):Check if any vertex lying beyond near plane if(IsBitSet(ClipCode[0],7) || IsBitSet(ClipCode[1],7) || IsBitSet(ClipCode[2],7)) { if(VerticesInsideZRange == 1) { // NOTE(shvayko): The simplest case where only one interior vertex. // Just interpolate each exterior vertex with interior vertex and that // will produce new vertices which will represent one new triangle. // NOTE(shvayko): TmpV0 - Interior vertex; TmpV1 - Exterior vertex; // TmpV2 - Exterior vertex v3 TmpV0,TmpV1,TmpV2; if(IsBitSet(ClipCode[0],8)) { TmpV0 = V0; TmpV1 = V1; TmpV2 = V2; } else if(IsBitSet(ClipCode[1],8)) { TmpV0 = V1; TmpV1 = V0; TmpV2 = V2; } else { TmpV0 = V2; TmpV1 = V0; TmpV2 = V1; } // NOTE(shvayko): Solve for t when z component is equal to near z // Pi(x,y,z) = P0(x,y,z) + (P1(x,y,z) - P0(x,y,z))*t // NOTE(shvayko): 1.0f is near plane Z // NOTE(shvayko): TmpV0 and TmpV2 f32 t = 1.0f-TmpV1.z / (TmpV0.z - TmpV1.z); f32 x = TmpV1.x + (TmpV0.x - TmpV1.x)*t; f32 y = TmpV1.y + (TmpV0.y - TmpV1.y)*t; f32 z = TmpV1.z + (TmpV0.z - TmpV1.z)*t; TmpV1 = v3f(x,y,1.1f); // NOTE(shvayko): TmpV0 and TmpV2 f32 t1 = 1.0f-TmpV2.z / (TmpV0.z - TmpV2.z); x = TmpV2.x + (TmpV0.x - TmpV2.x)*t1; y = TmpV2.y + (TmpV0.y - TmpV2.y)*t1; z = TmpV2.z + (TmpV0.z - TmpV2.z)*t1; TmpV2 = v3f(x,y,1.1f); // NOTE(shvayko): New triangle v3 NT0 = TmpV0; v3 NT1 = TmpV1; v3 NT2 = TmpV2; AddTriangle(NT0,NT1,NT2,Triangle->Color); } else if(VerticesInsideZRange == 2) { // NOTE(shvayko): The case where two interior vertex. // That case will produce 2 triangles // NOTE(shvayko): TmpV0 - Interior vertex; TmpV1 - Interior vertex; // TmpV2 - Exterior vertex v3 TmpV0,TmpV1,TmpV2; if(ClipCode[0] & CLIPCODE_Z_INSIDE) { TmpV0 = V0; if(ClipCode[1] & CLIPCODE_Z_INSIDE) { TmpV1 = V1; TmpV2 = V2; } else { TmpV1 = V2; TmpV2 = V1; } } else if(ClipCode[1] & CLIPCODE_Z_INSIDE) { TmpV0 = V1; TmpV1 = V2; TmpV2 = V0; } // NOTE(shvayko): Solve for t when z component is equal to near z // NOTE(shvayko): first created new vertex // NOTE(shvayko): 1.0f is near plane Z f32 t = 1.0f-TmpV2.z / (TmpV0.z - TmpV2.z); f32 X0i = TmpV2.x + (TmpV0.x - TmpV2.x)*t; f32 Y0i = TmpV2.y + (TmpV0.y - TmpV2.y)*t; f32 Z0i = TmpV2.z + (TmpV0.z - TmpV2.z)*t; // NOTE(shvayko): second created new vertex f32 t1 = 1.0f-TmpV2.z / (TmpV1.z - TmpV2.z); f32 X1i = TmpV2.x + (TmpV1.x - TmpV2.x)*t1; f32 Y1i = TmpV2.y + (TmpV1.y - TmpV2.y)*t1; f32 Z1i = TmpV2.z + (TmpV1.z - TmpV2.z)*t1; // NOTE(shvayko): Split into 2 triangles AddTriangle(TmpV0,v3f(X0i,Y0i,1.1f),TmpV1,Triangle->Color); AddTriangle(TmpV0,TmpV1,v3f(X1i,Y1i,1.1f),Triangle->Color); } else { assert(!"lol"); } } else { // NOTE(shvayko): All vertices is in Z range. Process without any clipping // NOTE(shvayko): Pespective divide. (Transforming from Clip Space into NDC space) v3 NdcV0,NdcV1,NdcV2; TransformHomogeneousToNDC(ClipV0,ClipV1,ClipV2,&NdcV0,&NdcV1,&NdcV2); // NOTE(shvayko):Viewport tranformation(Transforming from NDC space(-1.0f - 1.0f)) // to screen space(0 - Width, 0 - Height) v3 WinPV0,WinPV1,WinPV2; Viewport(NdcV0,NdcV1,NdcV2,&WinPV0,&WinPV1,&WinPV2,ClipV0.z,ClipV1.z,ClipV2.z); // NOTE(shvayko): Rasterization Stage DrawTriangle(Backbuffer,WinPV0,WinPV1,WinPV2, Triangle->Color); } 

Where am I wrong? All code is here https://pastebin.com/fA1vWdrk.
Simon Anciaux
1274 posts
3D Software rasterizer. triangle clipping problem
Edited by Simon Anciaux on
I've never done clipping manually, what follows may be wrong.

I think your computation of t is missing parenthesis.

 1 2 3 4 f32 t = 1.0f-TmpV1.z / (TmpV0.z - TmpV1.z); // Should be f32 t = (1.0f-TmpV1.z) / (TmpV0.z - TmpV1.z); 

After thinking about this, the formula probably needs to use w, instead of 1.0, because the near plane in clip space would be at -w so that when divided by w it return -1.

 1 2 f32 t = ( -w - TmpV1.z ) / ( TmpV0.z - TmpV1.z ); // But what is w ? 

While writing this post, I have a huge doubt that we can use the points like this. Those are homogeneous coordinates, so the "scale" of TmpV0 and TmpV1 aren't the same, meaning the w component isn't the same (only points with the same z value have the same w), I think.

To solve that we may need to convert to NDC space:

 1 2 3 4 5 v3 inside = v3( TmpV0.x / TmpV0.w, TmpV0.y / TmpV0.w, TmpV0.z / TmpV0.w ); v3 outside = v3( TmpV1.x / TmpV1.w, TmpV1.y / TmpV1.w, TmpV1.z / TmpV1.w ); // In ndc space, -1.0 is the near plane f32 t = ( -1.0f - outside.z ) / ( inside.z - outside.z ); v3 new_point_in_ndc = outside + ( inside - outside ) * t; 

But I'm not sure about any of this.
Roman
25 posts
ups
3D Software rasterizer. triangle clipping problem
A very dumb mistake with parentheses. Fixed it. it's working better now. Thank you.
I think you are right about that I cannot use vertices like that. Your way seems resonable but I need to give the AddTriangle function vertices in world's coordinates not in NDC. So I don't know how to approach that. May be you know how to translate ndc coordinates into world space? Also, I think I may change architecture of my rendering loop without adding new triangles in the end list. I just will render and transform my new constructed triangles right in place. By the way, can you suggest way to handle that?
Simon Anciaux
1274 posts
3D Software rasterizer. triangle clipping problem
Edited by Simon Anciaux on
I've never done it so I'm afraid I can't help you more. I know some people in the forums have done 3d software renderers, maybe one of them will stop by.

There is a chapter about clipping in this blog post Fabien Sanglard - Polygon Codec/Homogeneous clipping with some code.
They mention this paper James F. Blinn - CLIPPING USING HOMOGENEOUS COORDINATES.
And apparently the Real-Time Rendering book should have detailed information about every steps of the rendering pipeline (I haven't read it).
181 posts / 1 project
3D Software rasterizer. triangle clipping problem
Edited by Dawoodoz on
ExTray2020
A very dumb mistake with parentheses. Fixed it. it's working better now. Thank you.
I think you are right about that I cannot use vertices like that. Your way seems resonable but I need to give the AddTriangle function vertices in world's coordinates not in NDC. So I don't know how to approach that. May be you know how to translate ndc coordinates into world space? Also, I think I may change architecture of my rendering loop without adding new triangles in the end list. I just will render and transform my new constructed triangles right in place. By the way, can you suggest way to handle that?

You can always begin by converting to camera space by multiplying the object-to-world matrix with the world-to-camera matrix for each object being rendered. Then transform each vertex with the combined matrix and you have camera space without extra cost per vertex. Matrix multiplication order depends on if your matrices are inverted or not.

Object space: relative to model
World space: relative to world origin
Camera space: using current camera as the origin
Normalized space: relative to both camera and aspect ratio

Camera space is good for clipping using planes in a linear orthogonal space where you can still perform interpolation in a scale that make sense. The downside is having to carry around the clip frustum for specific canvas dimensions until your triangle is clipped.

You can name your matrices using both the source and destination coordinate system so that a_to_b * b_to_c = a_to_c, and it will be a simple task of type conversion without having to imagine anything complex.