← Back to index

3D Software rasterizer. triangle clipping problem

Roman
#24220
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.
Edited by Roman on Reason: Initial post
Simon Anciaux
#24221
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.
Edited by Simon Anciaux on
Roman
#24223
Thanks for your answer. I appreciate that.
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
#24228
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).
Edited by Simon Anciaux on
Dawoodoz
#24238
ExTray2020
Thanks for your answer. I appreciate that.
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.
Edited by Dawoodoz on
Reply to Thread
← Back to index