C++ triangle rasterization
I'm trying to fix this triangle rasterizer, but cannot make it work correctly. For some reason it only draws half of the triangles.
void DrawTriangle(Point2D p0, Point2D p1, Point2D p2)
{
Point2D Top, Middle, Bottom;
bool MiddleIsLeft;
if (p0.y < p1.y) // case: 1, 2, 5
{
if (p0.y < p2.y) // case: 1, 2
{
if (p1.y < p2.y) // case: 1
{
Top = p0;
Middle = p1;
Bottom = p2;
MiddleIsLeft = true;
}
else // case: 2
{
Top = p0;
Middle = p2;
Bottom = p1;
MiddleIsLeft = false;
}
}
else // case: 5
{
Top = p2;
Middle = p0;
Bottom = p1;
MiddleIsLeft = true;
}
}
else // case: 3, 4, 6
{
if (p0.y < p2.y) // case: 4
{
Top = p1;
Middle = p0;
Bottom = p2;
MiddleIsLeft = false;
}
else // case: 3, 6
{
if (p1.y < p2.y) // case: 3
{
Top = p1;
Middle = p2;
Bottom = p0;
MiddleIsLeft = true;
}
else // case 6
{
Top = p2;
Middle = p1;
Bottom = p0;
MiddleIsLeft = false;
}
}
}
float xLeft, xRight;
xLeft = xRight = Top.x;
float mLeft, mRight;
// Region 1
if(MiddleIsLeft)
{
mLeft = (Top.x - Middle.x) / (Top.y - Middle.y);
mRight = (Top.x - Bottom.x) / (Top.y - Bottom.y);
}
else
{
mLeft = (Top.x - Bottom.x) / (Top.y - Bottom.y);
mRight = (Middle.x - Top.x) / (Middle.y - Top.y);
}
int finalY;
float Tleft, Tright;
for (int y = ceil(Top.y); y < (int)Middle.y; y++)
{
Tleft=float(Top.y-y)/(Top.y-Middle.y);
Tright=float(Top.y-y)/(Top.y-Bottom.y);
for (int x = ceil(xLeft); x <= ceil(xRight) - 1 ; x++)
{
FrameBuffer::SetPixel(x, y, p0.r,p0.g,p0.b);
}
xLeft += mLeft;
xRight += mRight;
finalY = y;
}
// Region 2
if (MiddleIsLeft)
{
mLeft = (Bottom.x - Middle.x) / (Bottom.y - Middle.y);
}
else
{
mRight = (Middle.x - Bottom.x) / (Middle.y - Bottom.y);
}
for (int y = Middle.y; y <= ceil(Bottom.y) - 1; y++)
{
Tleft=float(Bottom.y-y)/(Bottom.y-Middle.y);
Tright=float(Top.y-y)/(Top.y-Bottom.y);
for (int x = ceil(xLeft); x <= ceil(xRight) - 1; x++)
{
FrameBuffer::SetPixel(x, y, p0.r,p0.g,p0.b);
}
xLeft += mLeft;
xRight += mRight;
}
}
Here is what happens when I use it to draw shapes.
When I disable the second region, all those weird triangles disappear.
The wireframe mode works perfect, so this eliminates all the other possibilities other than the triangle rasterizer.
Solution
I kind of got lost in your implementation, but here's what I do (I have a slightly more complex version for arbitrary convex polygons, not just triangles) and I think apart from the Bresenham's algorithm it's very simple (actually the algorithm is simple too):
#include <stddef.h>
#include <limits.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#define SCREEN_HEIGHT 22
#define SCREEN_WIDTH 78
// Simulated frame buffer
char Screen[SCREEN_HEIGHT][SCREEN_WIDTH];
void SetPixel(long x, long y, char color)
{
if ((x < 0) || (x >= SCREEN_WIDTH) ||
(y < 0) || (y >= SCREEN_HEIGHT))
{
return;
}
Screen[y][x] = color;
}
void Visualize(void)
{
long x, y;
for (y = 0; y < SCREEN_HEIGHT; y++)
{
for (x = 0; x < SCREEN_WIDTH; x++)
{
printf("%c", Screen[y][x]);
}
printf("\n");
}
}
typedef struct
{
long x, y;
unsigned char color;
} Point2D;
// min X and max X for every horizontal line within the triangle
long ContourX[SCREEN_HEIGHT][2];
#define ABS(x) ((x >= 0) ? x : -x)
// Scans a side of a triangle setting min X and max X in ContourX[][]
// (using the Bresenham's line drawing algorithm).
void ScanLine(long x1, long y1, long x2, long y2)
{
long sx, sy, dx1, dy1, dx2, dy2, x, y, m, n, k, cnt;
sx = x2 - x1;
sy = y2 - y1;
if (sx > 0) dx1 = 1;
else if (sx < 0) dx1 = -1;
else dx1 = 0;
if (sy > 0) dy1 = 1;
else if (sy < 0) dy1 = -1;
else dy1 = 0;
m = ABS(sx);
n = ABS(sy);
dx2 = dx1;
dy2 = 0;
if (m < n)
{
m = ABS(sy);
n = ABS(sx);
dx2 = 0;
dy2 = dy1;
}
x = x1; y = y1;
cnt = m + 1;
k = n / 2;
while (cnt--)
{
if ((y >= 0) && (y < SCREEN_HEIGHT))
{
if (x < ContourX[y][0]) ContourX[y][0] = x;
if (x > ContourX[y][1]) ContourX[y][1] = x;
}
k += n;
if (k < m)
{
x += dx2;
y += dy2;
}
else
{
k -= m;
x += dx1;
y += dy1;
}
}
}
void DrawTriangle(Point2D p0, Point2D p1, Point2D p2)
{
int y;
for (y = 0; y < SCREEN_HEIGHT; y++)
{
ContourX[y][0] = LONG_MAX; // min X
ContourX[y][1] = LONG_MIN; // max X
}
ScanLine(p0.x, p0.y, p1.x, p1.y);
ScanLine(p1.x, p1.y, p2.x, p2.y);
ScanLine(p2.x, p2.y, p0.x, p0.y);
for (y = 0; y < SCREEN_HEIGHT; y++)
{
if (ContourX[y][1] >= ContourX[y][0])
{
long x = ContourX[y][0];
long len = 1 + ContourX[y][1] - ContourX[y][0];
// Can draw a horizontal line instead of individual pixels here
while (len--)
{
SetPixel(x++, y, p0.color);
}
}
}
}
int main(void)
{
Point2D p0, p1, p2;
// clear the screen
memset(Screen, ' ', sizeof(Screen));
// generate random triangle coordinates
srand((unsigned)time(NULL));
p0.x = rand() % SCREEN_WIDTH;
p0.y = rand() % SCREEN_HEIGHT;
p1.x = rand() % SCREEN_WIDTH;
p1.y = rand() % SCREEN_HEIGHT;
p2.x = rand() % SCREEN_WIDTH;
p2.y = rand() % SCREEN_HEIGHT;
// draw the triangle
p0.color = '1';
DrawTriangle(p0, p1, p2);
// also draw the triangle's vertices
SetPixel(p0.x, p0.y, '*');
SetPixel(p1.x, p1.y, '*');
SetPixel(p2.x, p2.y, '*');
Visualize();
return 0;
}
Output:
*111111
1111111111111
111111111111111111
1111111111111111111111
111111111111111111111111111
11111111111111111111111111111111
111111111111111111111111111111111111
11111111111111111111111111111111111111111
111111111111111111111111111111111111111*
11111111111111111111111111111111111
1111111111111111111111111111111
111111111111111111111111111
11111111111111111111111
1111111111111111111
11111111111111
11111111111
1111111
1*
- Which number, 0 or 1, should I define the variabliable of loops for arrays from?
- The `write` syscall in C writes to an unexpected position
- Can I dup and change the buffer behaviour of the new fd without changing the old one?
- OpenCV Error: Sizes of input arguments do not match (The operation is neither 'array op array')
- how compiler works to evaluate sizeof operator in c
- Code Fragment: is this pure C?
- ‘struct' declared inside parameter list
- Can time(NULL) ever return failure?
- Format specifier in scanf for bool datatype in C
- What does %[^\n] mean in C?
- What does it mean by `-fno-signed-char, --signed-char` for gcc & clang?
- How can embedded systems be elegantly compatible with 32-bit and 64-bit timestamp content printing?
- Specifying size of enum type in C
- Graphical user interface Tutorial in C
- gcc arm optimizes away parameters before System Call
- ARM V7 inline assembly - moving a C variable into a register
- How to fix "pointer ‘old’ may be used after ‘realloc’ [-Wuse-after-free]" warning in C?
- Why is an empty integer array filled with seemingly garbage data in C?
- Confusion of virtual memory
- Variable address does not fall within the stack range in /proc/self/maps
- Why does carg(-0) return -pi?
- To the power of in C?
- How do you do exponentiation in C?
- Will this be a tail call or not?
- Calculating a catalan number in C
- Why is the '&' operator needed for an int variable but not for an array in C?
- populating an array at compile time in C
- Why is the initialization of this structure global variable wrong?
- Efficient linked list design for a C file manager
- Function with a malloc on a pointer declared in main()