Polygon Drawing Algorithm

[PDAFantast]

[Digby]

[Phantom]

[simonjacobs]

You could use a lookup table for divides

[Phantom]

Ehm yes, I always do that on my PC, but on the iPaq, a lookup table for all 32bit numbers is slightly too large.

[simonjacobs]

I use a table for divides up to 256, I get a lot of them in my rendering code.

I also wonder if you can use a 256-entry lookup table to simulate a full 16.16 / 16.16 operation.

1/(a+b) = 1/[a(1+b/a)] = 1/a * 1/(1+b/a)

Say you are dividing by 534 = 256*2 + 22 and set a=22. Then you have:

x/534 = x/22 + x/(1+512/22)

or something. That might be rubbish, but it might work

I'm sure you should be able to get really fast 16.16 division with just a 256 entry lookup table and multiplications.

[PDAFantast]

[PDAFantast]

[Digby]

Oh I completely agree if you are working only in screen space you don't need to perform the divide along the edge.

You do have to do this if you are having to move from screen space to camera space and that is what I was referring to in my original post about caching the edge values so you don't have to do the divide twice.

Since I've had time to think about it, it's not the perf-win that I had originally imagined because the rasterizer doesn't draw the same pixel twice along abutting edges. The top-left fill convention guarantees that the right edge won't be drawn twice, hence there's not much being computed for one triangle that can be cached. I need to think about it some more before I write this off, but it's looking that way for now.

[PDAFantast]

[refractor]

[Digby]

[PDAFantast]

Cool stuff Refractor...

I liked the rsbmi replacement a lot, why haven't I thought of that one...

Unfortunately on GBA r12 is not temporary and I can't use it. And it's called both from Thumb and ARM assembly code.


Digby,
I think, you're not saving a a cycle at all, since you got
to save lr on stack to be able to pop it up on exit, so the memory write/reads takes out the gain in exterminating mov pc,lr.

I might be wrong, but the ARM7TDMI fetching timing of the GBA won't give you this advantage.

[Digby]