The software rendering world

So in previous parts we have calculated the 2d coords and whether the polygon is facing towards us. That’s good, but we can’t draw a polygon without knowing which pixels are inside and which are outside…

For that, the usual way was to get the staring and ending point of each edge, and calculate a ratio on their differences.

Let’s take for example the edge from vertex 0 to vertex 1.

First we have to get the difference along X and Y axis:

• dx01 = xx1 - xx0
• dy01 = yy1 - yy0

Then, we calculate the ratio of them:

• dxdy01 = dx01 / dy01

And then, we can do a loop to calculate all the X coords for each Y:

• x[y] = xx0 + (y - yy0) * dxdy01

Which can be calculated by starting with:

• ex = xx0
• ey = yy0

and using a loop like this:

• x[ey] = ex
• ex = ex + dxdy01
• ey = ey + 1

But we have a big problem: each triangle has 3 sides, and each of them needs a division… is there any way to reduce that?

Lets recap… we start with the original formula:

• dxdy01 = (xx1 - xx0) / (yy1 - yy0)

And go back to using the original 3d values:

• dxdy01 = (x1/z1 - x0/z0) / (y1/z1 - y0/z0)

Then, we substitute for the intermediate values used on previous parts:

• dxdy01 = (zxz*www - xzz*www) / (zyz*www - yzz*www)

And we can push out and eliminate www:

• dxdy01 = (www*(zxz - xzz)) / (www*(zyz - yzz))
• dxdy01 = (zxz - xzz) / (zyz - yzz)

All fine and dandy, we can use that last formula as a template for the other edges (nice patterns on the letters hehe):

• dxdy01 = (zxz - xzz) / (zyz - yzz)
• dxdy02 = (zzx - xzz) / (zzy - yzz)
• dxdy12 = (zzx - zxz) / (zzy - zyz)

We first define some short hand terms:

• xxz = zxz - xzz
• xzx = zzx - xzz
• zxx = zzx - zxz
• yyz = zyz - yzz
• yzy = zzy - yzz
• zyy = zzy - zyz

And substitute:

• dxdy01 = xxz / yyz
• dxdy02 = xzx / yzy
• dxdy12 = zxx / zyy

We are very near the end!

First expand across all values:

• dxdy01 = xxz * yzy * zyy / (yyz * yzy * zyy)
• dxdy02 = yyz * xzx * zyy / (yyz * yzy * zyy)
• dxdy12 = yyz * yzy * zxx / (yyz * yzy * zyy)

And then factor the common divisor:

• ddd = 1.0 / (yyz * yzy * zyy)
• dxdy01 = xxz * yzy * zyy * ddd
• dxdy02 = yyz * xzx * zyy * ddd
• dxdy12 = yyz * yzy * zxx * ddd

Wow, the letter patterns are starting to hurt my head but it sure has its payoff: we are down from 6 to 2 divides per triangle!!!