← Back to index

Using vectors to create triangles

Jesse Coyle
#4189
Hello everybody, I've been slow in my projects but on one particular note, I've had a bug that I can't find, and it must be squashed like always.

I've been using vectors to determine the points of a triangle of which to draw, I have seen a good bit of the basis part of the series and have done a min max rectangle to limit the portion of the screen to check pixels if they are inside the three vector points.

I've done several methods, checking which side the point is on relative to every vector, I've done a Barycentric method, and a couple others. The one I'm currently using seems fit as it doesn't care if the points go clockwise or counter-clockwise.

The bug comes in when it creates a weird monstrosity triangle like the one
[attachment=43]triangles.png[/attachment]. The purple squares are centered on the point where a vector point is at.

These are the three vectors that are represented by the purple squares
1
2
3
v2 test_v1 = {100, 100};
v2 test_v2 = {150, 100};
v2 test_v3 = {125, 150};


This is a method of seeing if a point is within three vector points.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
inline bool32
IsInTriangle(v2 p, v2 p0, v2 p1, v2 p2)
{
   bool32 result = false;
   
   v2 temp0 = p2 - p0;
   v2 temp1 = p1 - p0;
   v2 temp2 = p - p0;
   
   float dot00 = Dot(temp0, temp0);
   float dot01 = Dot(temp0, temp1);
   float dot02 = Dot(temp0, temp2);
   float dot11 = Dot(temp1, temp1);
   float dot12 = Dot(temp1, temp2);
   
   float inv = 1 / (dot00 * dot11 - dot01 * dot01);
   float u = (dot11 * dot02 - dot01 * dot12) * inv;
   float v = (dot00 * dot12 - dot01 * dot02) * inv;
   
   result = (u >= 0) && (v >= 0) && (u + v < 1);
   
   return result;
}


and then the triangle rendering function that writes the pixel data to the pixel buffer
 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
local void
TestRender(Game_Screen_Buffer *buffer, v2 p0 , v2 p1, v2 p2,
           uint8 r, uint8 g, uint8 b, uint8 a = 255)
{
   float inner_min_x = Min(p0.x, p1.x);
   float inner_max_x = Max(p0.x, p1.x);
   float inner_min_y = Min(p0.y, p1.y);
   float inner_max_y = Max(p0.y, p1.y);
   float min_x = Min(inner_min_x, p2.x);
   float max_x = Max(inner_max_x, p2.x);
   float min_y = Min(inner_min_y, p2.y);
   float max_y = Max(inner_max_y, p2.y);
   
   if(min_x < 0.0f)
   {
      min_x = 0.0f;
   }
   if(min_y < 0.0f)
   {
      min_y = 0.0f;
   }
   if(max_x > buffer->width)
   {
      max_x = (float)buffer->width;
   }
   if(max_y > buffer->height)
   {
      max_y = (float)buffer->height;
   }
   
   #if 1
   Rectangle(buffer, (int32)p0.x - 3, (int32)p0.y - 3, 6, 6, 255, 0, 255);
   Rectangle(buffer, (int32)p1.x - 3, (int32)p1.y - 3, 6, 6, 255, 0, 255);
   Rectangle(buffer, (int32)p2.x - 3, (int32)p2.y - 3, 6, 6, 255, 0, 255);
   #else
   Rectangle(buffer, (int32)min_x - 3, (int32)min_y - 3, 6, 6, 255, 255, 0);
   Rectangle(buffer, (int32)min_x - 3, (int32)max_y - 3, 6, 6, 255, 255, 0);
   Rectangle(buffer, (int32)max_x - 3, (int32)min_y - 3, 6, 6, 255, 255, 0);
   Rectangle(buffer, (int32)max_x - 3, (int32)max_y - 3, 6, 6, 255, 255, 0);
   #endif
   
   uint32 blue = (uint32)b;
   uint32 green = (uint32)g;
   uint32 red = (uint32)r;
   uint32 alpha = (uint32)a;
   uint32 color = ((alpha << 24) | (red << 16) | (green << 8) | blue);
   
   uint8 *pitch = ((uint8 *)buffer->memory +
                   (int32)min_x * buffer->bytes_per_pixel +
                   (int32)min_y * buffer->pitch);
   for(float y = min_y;
       y < max_y;
       ++y)
   {
      uint32 *pixel = (uint32 *)pitch;
      for(float x = min_x;
          x < max_x;
          ++x)
      {
         if(IsInTriangle(V2(x, y), p0, p1, p2))
         {
            *pixel++ = color;
         }
      }
      pitch += buffer->pitch;
   }
}


I'm not really sure whats going on honestly, I think I might have screwed up the dot products somehow, but they all look okay to me, though Any method that's worked produces the same problem so maybe It has to do with getting pixels in the pixel buffer?
Jesse Coyle
#4190
Oh sweet taco bell geezus... Screw it everyone! It was the pixel buffer...

changed
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
for(float y = min_y;
       y < max_y;
       ++y)
   {
      uint32 *pixel = (uint32 *)pitch;
      for(float x = min_x;
          x < max_x;
          ++x)
      {
         if(IsInTriangle(V2(x, y), p0, p1, p2))
         {
            *pixel++ = color;
         }
      }
      pitch += buffer->pitch;
   }

to
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
for(float y = min_y;
       y < max_y;
       ++y)
   {
      uint32 *pixel = (uint32 *)pitch;
      for(float x = min_x;
          x < max_x;
          ++x)
      {
         if(IsInTriangle(V2(x, y), p0, p1, p2))
         {
            *pixel++ = color;
         }
         else
         {
            *pixel++;
         }
      }
      pitch += buffer->pitch;
   }


Forgot that if the condition fails you have to still move along the columns, I guess all I needed was a wookie to talk to.

[attachment=44]triangles_solution.png[/attachment]

There goes 5 hours of my life...
Andrew Bromage
#4192
Zilarrezko
I guess all I needed was a wookie to talk to.

I'm going to quote from The Practice of Programming by Kernighan and Pike. (C and Go, what a combination.)

On fixing bugs:

[An] effective technique is to explain your code to someone else. This will often cause you to explain the bug to yourself. Sometimes it takes no more than a few sentences, followed by an embarrassed “Never mind; I see what’s wrong. Sorry to bother you.” This works remarkably well; you can even use non-programmers as listeners. One university computer center kept a teddy bear near the help desk. Students with mysterious bugs were required to explain them to the teddy bear before they could speak to a human counsellor.

Many professional programmers keep some kind of toy at their desk for precisely this purpose. I have a Toy Story three-eyed alien. Anyone who has watched Chronaldragon's stream has seen his dragon. Casey, of course, doesn't need one for HMH, because he's explaining everything to the audience.
Jesse Coyle
#4193
I've heard ducks. But I thought the google wookie was the most famous one.

I bet sometimes when Casey is coding on his own, and runs into a bug. Instead of talking to his owl he instead acts as if he's explaining to window's devs how his code works and why it is better than what window's devs would have come up with, or just companies in general.
Reply to Thread
← Back to index