neilobremski
Experienced Member
In my previous post I explained the purpose and high level algorithm. This time I'm going to show you some almost-actual code written in a pseudo-C language. Let's get straight to it ...
Most importantly, realize that every variable is an integer; there are no floating-point values. Remember that we're dealing with fractions rather than funky decimal numbers. This is what allows us to get pixel perfect results no matter the resolution, assuming your integer variables are large enough to handle the dimensions! In my assembler implementation, up next, you'll see that I use single bytes that give a range of 0 - 255 instead of 16-bit or 32-bit variables, but the algorithm remains the same.
Next this is not optimized. I've tried to write the pseudo code so that it is clear and you could convert this into your language of choice without any problems. Something particular to C-style languages is the use of the percent sign for the modulus operation. When you see A % B it results in the remainder of the division of A by B. In assembler, as you'll see, the modulus and division are a single operation which greatly speeds things up (a division is already the slowest arithmetic you can do, so any speed up is greatly appreciated).
And finally, you must sort the points in vertically descending order which means the first scanline is at y1 and the last is at y3. Have at it!
Next up I show the actual X86 16-bit assembler which you can use for drawing pixel perfect triangles reasonably fast in CGA mode 4.
Code:
trifill(x1, y1, x2, y2, x3, y3, color) /* y coords must be sorted ascending */
{
YDistA = y2 - y1 + 1; /* slope of side A (1 to 2) */
if (x1 > x2) {
XDirA = -1;
XDistA = x1 - x2 + 1;
} else {
XDirA = 1;
XDistA = x2 - x1 + 1;
}
YDistB = y3 - y1 + 1; /* slope of side B (1 to 3) */
if (x1 > x3) {
XDirB = -1;
XDistB = x1 - x3 + 1;
} else {
XDirB = 1;
XDistB = x3 - x1 + 1;
}
XSideA = XSideB = x1;
ErrA = ErrB = 0;
Halves = 0;
do {
for (Scanline = y1; Scanline <= y2; Scanline++) {
XBeg = XSideA; /* scanline segment */
XEnd = XSideB;
if (XBeg < XEnd) {
swap(XBeg, XEnd);
}
ErrA += XDirA; /* step side A (1 to 2 / 2 to 3) */
StepA = ErrA / YDistA;
ErrA = ErrA % YDistA;
XSideA += StepA;
AdjSideA = XSideA + -XDirA; /* expand segment using side A */
if (StepA < 0 && AdjSideA < XBeg) {
XBeg = AdjSideA;
} else if (StepA > 0 && AdjSideA > XEnd) {
XEnd = AdjSideA;
}
ErrB += XDirB; /* step side B (1 to 3) */
StepB = ErrB / YDistB;
ErrB = ErrB % YDistB;
XSideB += StepB;
AdjSideB = XSideB + -XDirB; /* expand segment using side B */
if (StepB < 0 && AdjSideB < XBeg) {
XBeg = AdjSideB;
} else if (StepB > 0 && AdjSideB > XEnd) {
XEnd = AdjSideB;
}
draw_line_segment(XBeg, XEnd, Scanline, Color);
}
if (++Halves > 2) {
break;
}
YDistA = y3 - y2; /* reset side A (2 to 3) */
if (!YDistA) {
break;
}
if (x2 > x3) {
XDirA = -1;
XDistA = x2 - x3 + 1;
} else {
XDirA = 1;
XDistA = x3 - x2 + 1;
}
ErrA = XDistA % YDistA; /* prestep for overlapping scanline */
XSideA += XDistA / YDistA;
} while (1);
}Most importantly, realize that every variable is an integer; there are no floating-point values. Remember that we're dealing with fractions rather than funky decimal numbers. This is what allows us to get pixel perfect results no matter the resolution, assuming your integer variables are large enough to handle the dimensions! In my assembler implementation, up next, you'll see that I use single bytes that give a range of 0 - 255 instead of 16-bit or 32-bit variables, but the algorithm remains the same.
Next this is not optimized. I've tried to write the pseudo code so that it is clear and you could convert this into your language of choice without any problems. Something particular to C-style languages is the use of the percent sign for the modulus operation. When you see A % B it results in the remainder of the division of A by B. In assembler, as you'll see, the modulus and division are a single operation which greatly speeds things up (a division is already the slowest arithmetic you can do, so any speed up is greatly appreciated).
And finally, you must sort the points in vertically descending order which means the first scanline is at y1 and the last is at y3. Have at it!
Next up I show the actual X86 16-bit assembler which you can use for drawing pixel perfect triangles reasonably fast in CGA mode 4.