Winden homepage‎ > ‎

Reducing divisions for polygon mappers

Part 0: Calculating implicit equation edge values

Reducing divisions when trying to use implicit-equation triangle drawing is perfectly possible. Let’s see…

3d to 2d coordinates conversion:

  • X0 = x0/z0
  • Y0 = y0/z0
  • X1 = x1/z1
  • Y1 = y1/z1

The usual implicit equations are:

  • a0 = Y0 - Y1
  • b0 = X1 - X0
  • c0 = X0 * Y1 - X1 * Y0

So, the obvious approach is to first convert 3d to 2d and then use the 2d coords… but what if we used the 3d coords directly?… lets substitute a bit…

  • a0 = y0/z0 - y1/z1
  • b0 = x1/z1 - x0/z0
  • c0 = x0/z0 * y1/z1 - x1/z1 * y0/z0

… fill out missing factors while keeping the same value…

  • a0 = y0*z1/(z0*z1) - y1*z0/(z1*z0)
  • b0 = x1*z0/(z1*z0) - x0*z1/(z0*z1)
  • c0 = x0/z0 * y1/z1 - x1/z1 * y0/z0

… work a bit on c0…

  • a0 = y0*z1/(z0*z1) - y1*z0/(z1*z0)
  • b0 = x1*z0/(z1*z0) - x0*z1/(z0*z1)
  • c0 = x0*y1/(z0*z1) - x1*y0/(z1*z0)

… OMG!!! WE ARE DIVIDING ALWAYS BY THE SAME FACTOR!!!…

  • w0 = 1/z0*z1
  • a0 = w0 * (y0*z1 - y1*z0)
  • b0 = w0 * (x1*z0 - x0*z1)
  • c0 = w0 * (x0*y1 - x1*y0)

Let’s recall a bit… these (a,b,c) factors are per-edge and we don’t really need the value, just the sign… this means that we don’t have to care about the w factor, since it’s the same on every place!!! SO, reacalling a bit, to calc the edges for a poly, we just need to do:

  • a0 = y0*z1 - y1*z0
  • b0 = x1*z0 - x0*z1
  • c0 = x0*y1 - x1*y0
  • a1 = y1*z2 - y2*z1
  • b1 = x2*z1 - x1*z2
  • c1 = x1*y2 - x2*y1
  • a2 = y2*z0 - y0*z2
  • b2 = x0*z2 - x2*z0
  • c2 = x2*y0 - x0*y2

lo’ and behold… we need no stinking divides anywhere!!!

Part 1: Calculating 2d projections from 3d coordinates

It’s funny how it works… while watching the 4k compos from breakpoint 2008 I was talking with wisefox about trying to eliminate divisions from the polygon drawing setups…

To recap, let’s forget for a moment about texturing and just try to get which pixels are to be drawn and which are to be left untouched…

Input data is 3 vertexes in 3d:

  • x0, y0, z0
  • x1, y1, z1
  • x2, y2, z2

Next we have to transform from 3d to 2d, which takes at 3 divs and 6 muls:

  • w0 = 1.0 / z0
  • w1 = 1.0 / z1
  • w2 = 1.0 / z2
  • xx0 = x0 * w0
  • yy0 = y0 * w0
  • xx1 = x1 * w1
  • yy1 = y1 * w1
  • xx2 = x2 * w2
  • yy2 = y2 * w2

But we can be a bit sneaky about how we calculate the dividing:

  • xzz = x0 * z1 * z2
  • yzz = y0 * z1 * z2
  • zxz = z0 * x1 * z2
  • zyz = z0 * y1 * z2
  • zzx = z0 * z1 * x2
  • zzy = z0 * z1 * y2
  • zzz = z0 * z1 * z2
  • www = 1 / zzz
  • xx0 = xzz * www
  • yy0 = yzz * www
  • xx1 = zxz * www
  • yy1 = zyz * www
  • xx2 = zzx * www
  • yy2 = zzy * www

This form needs 1 divs and 20 muls… but there are a lot of common parts that can be factored, and end up with 1 divs and 13 muls.

So, if a div takes A cycles and a mul takes B cycles…

  • normal: 3*A + 6*B
  • new: A +  13 *B

We are carrying a lot of divs and muls so it is better to do all of this on the FPU to conserve some appearance of precision… on a 68060 a division takes 37 cycles and a multiplication 3 cycles, so lets count…

  • normal: 3*A + 6*B = 3*37 + 6*3 = 111 + 18 = 129 cycles
  • new: A + 13 * B = 37 + 39 = 76 cycles

The new method takes only 58% of the time of the original one!

Ok, so we have reduced the number of calculations for calculating the 2d projection… next time we can see how to reduce the time needed for the edge deltas!

Part 2: Calculating triangle area from 3d coordinates

After calculating the 3d to 2d projections, there are two parts of a mapper that need some common values: back face culling and calculating texture deltas.

Back face culling works by measuring the screen space “signed area” of a polygon: the same absolute value can be positive for front facing polygons and negative for back facing polygons.

That way when we detect this value as negative, we can simply stop drawing the polygon.

The classic formula using 2d coordinates is something like this:

  • area = (xx1-xx0) * (yy2-yy0) - (xx2-xx0) * (yy1-yy0)

We can substitute for the original 3d coordinates:

  • area = (x1/z1-x0/z0) * (y2/z2-y0/z0) - (x2/z2-x0/z0) * (y1/z1-y0/z0)

And make all parts have the same denominator:

  • xzz = x0 * z1 * z2
  • yzz = y0 * z1 * z2
  • zxz = z0 * x1 * z2
  • zyz = z0 * y1 * z2
  • zzx = z0 * z1 * x2
  • zzy = z0 * z1 * y2
  • zzz = z0 * z1 * z2
  • www = 1 / zzz
  • area = (zxz/zzz-xzz/zzz) * (zzy/zzz-yzz/zzz) - (zzx/zzz-xzz/zzz) * (zyz/zzz-yzz/zzz)

And try to push out the denominator zzz:

  • area = ((zxz-xzz)/zzz) * ((zzy-yzz)/zzz) - ((zzx-xzz)/zzz) * ((zyz-yzz)/zzz)
  • area = ((zxz-xzz) * (zzy-yzz)/(zzz*zzz)) - ((zzx-xzz) * (zyz-yzz)/(zzz*zzz))
  • area = ((zxz-xzz) * (zzy-yzz) - (zzx-xzz) * (zyz-yzz)) / (zzz*zzz)
  • area = ((zxz-xzz) * (zzy-yzz) - (zzx-xzz) * (zyz-yzz)) * (www*www)

There are 2 important things here:

  1. The divisor is zzz*zzz, which a number squared, so we are guaranteed that it is positive, so we are guaranteed that the sign for area is the same than the sign for the numerator. So, in real code, we can do the back face culling without any divisions since we just need the sign.
  2. That www is the same that we needed on the previous part, this means that we can calculate all the 3d-to-2d projections and screen area with just one divide… things are looking good! :)

Part 3: Calculating triangle edge deltas from 3d coordinates

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!!!

Part 4: Calculating texture deltas from 3d coordinates

So, we have figured out how to optimise a lot, but still are without any means to calculate texture deltas… lets try to do the calculations for linear texturing!

One of the basic formula for texture deltas is this one:

  • num = ((v1 - v0) * (yy2 - yy0) - (v2 - v0) * (yy1 - yy0))
  • den = ((xx1 - xx0) * (yy2 - yy0) - (xx2 - xx0) * (yy1 - yy0))
  • dvdx = num / den

As you can see, the patterns area similar to the calculations for the area, and in fact the denominator is the are itself, so lets substitute:

  • num = ((v1 - v0) * (yy2 - yy0) - (v2 - v0) * (yy1 - yy0))
  • area = ((zxz-xzz) * (zzy-yzz) - (zzx-xzz) * (zyz-yzz)) / (zzz*zzz)
  • dvdx = num / area

We need to correlate v0, v1 and v2 to the zzz divider which is being used all over the place, so we define this:

  • vzz = v0 * zzz
  • zvz = v1 * zzz
  • zzv = v2 * zzz

And we can substitute just like we did when calculating the area formula:

  • num1 = (zvz/zzz - vzz/zzz) * (zzy/zzz - yzz/zzz)
  • num2 = (zzv/zzz - vzz/zzz) * (zyz/zzz - yzz/zzz)
  • num = num1 - num2
  • area = ((zxz-xzz) * (zzy-yzz) - (zzx-xzz) * (zyz-yzz)) / (zzz*zzz)
  • dvdx = num / area

Push out the zzz divides:

  • num1 = (zvz - vzz) * (zzy - yzz)
  • num2 = (zzv - vzz) * (zyz - yzz)
  • num = (num1 - num2) / (zzz*zzz)
  • area = ((zxz-xzz) * (zzy-yzz) - (zzx-xzz) * (zyz-yzz)) / (zzz*zzz)
  • dvdx = num / area

And notice that both num and area are being divided by (zzz*zzz), so it can be eliminated:

  • num = (zvz-vzz) * (zzy-yzz) - (zzv-vzz) * (zyz-yzz)
  • area_non_www = (zxz-xzz) * (zzy-yzz) - (zzx-xzz) * (zyz-yzz)
  • dvdx = num / area_non_www

Extending this code to calculate perspective correct gradients is easy, by using these values for the starting points:

  • uzz = u0 * z1 * z2 (becomes u0/z0 when divided by zzz)
  • zuz = z0 * u1 * z2
  • zzu = z0 * z1 * u2
  • wzz = z1 * z2 (becomes 1/z0 when divided by zzz)
  • zwz = z0 * z2
  • zzw = z0 * z1

And these formula for the numerator on the deltas using the same principles as in other parts:

  • u_num = (zuz-uzz) * (zzy-yzz) - (zzu-uzz) * (zyz-yzz)
  • w_num = (zwz-wzz) * (zzy-yzz) - (zzw-wzz) * (zyz-yzz)

note: delta formulas taken from kalms/tbl page for texture gradients

Part 5: Chaining related divisions into a single one

I had a revelation today. It may not work, or be totally irrelevant, but that’s not important for me at the moment. The idea itself is cool, and that is worth writing about.

When doing perspective correct mapping, you have to interpolate u/z and 1/z horizontally and perform (u/z)/(1/z) every so often. That division is usually done in a pipelined manner so that we continue performing mapping while it is calculated, so in effect it may be “free”.

But we can also “accumulate” all these divisions and perform them in one go, reusing the same technique we used on the first part to compute the 3d-to-2d projections for the three triangle vertices.

Let’s play an example in a scanline that has 4 control points:

  • numerators: n0, n1, n2 ,n3
  • denominators: d0, d1, d2, d3

We can calculate the values we need in the old way:

  • u0 = n0 / d0
  • u1 = n1 / d1
  • u2 = n2 / d2
  • u3 = n3 / d3

But we can also factor out the divisions like this:

  • dddd = 1 / ( d0 * d1 * d2 * d3 )
  • nddd = n0 * d1 * d2 * d3
  • dndd = d0 * n1 * d2 * d3
  • ddnd = d0 * d1 * n2 * d3
  • dddn = d0 * d1 * d2 * n3
  • u0 = nddd * dddd
  • u1 = dndd * dddd
  • u2 = ddnd * dddd
  • u3 = dddn * dddd

The result, as usual, is trading divisions for many multiplies.

Now some parts of the audience will say “But I’m already pipelining my perspective divides with my texturing, what can I gain from this technique?”.

As I said at the start, you could gang all the usual divides you’d do in a scanline into just one, which would mean a lot of work into calculating all the different numerators. Other way would be to gang only 2 consecutive divides, which is easier on the code and be a very simple way to achieve 8 pixel steps instead of 16 pixel ones.

I feel there are a lot of things which can be improved by generalizing this technique.


Comments