# blast from the past: fastest possible polygon scanning

This topic is 5154 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I am working on a software renderer for a very limited platform, and I find myself having to make approximations that cause a lot of artifacts. I feel like I need to go back to the drawing board and redo my poly scanning algorithm. I'm sure this is a much discussed problem, so I was wondering what was out there. I am having trouble finding any specifics. Are there any good resources?

##### Share on other sites
google scan line rasterization, also look up fixed-point arithmatic for interpolating depth values if you're using a z-buffer, or bsp tree if you're using painter algorithm.

Tim

##### Share on other sites
I've done that. Everything's fixed point. We're not even doing depth sorting... the scenes are constrained such that the polys just need to be drawn in the order the renderer gets them. I need optimization at an even more basic level. I'm at the point where adding just 1 integer divide into the outer loop dips me below my floor of 15 fps. My inner loop is something like 19 lines of ASM with no stack access. I'm just stuck as to how to squeeze out more cycles here.

##### Share on other sites
can you post it? and explain the assembly if it's not obvious.. I don't remember needing an integer division there,it's been a while tho, I specialize in photorealistic stuff, where and why do you do the division?

##### Share on other sites
I can't really post it.

Right now, I'm using the "pure" start and end point of the triangle scanline to calculate texture coordinates, which causes ugly zipper aliasing. In order to correct this, the math I tried involves divides in the outer loop (per scanline per triangle). This pushes me past the performance limit. My ASM has no divides... simply steps along the scanline, grabs the right texel, and writes it to the buffer. There's not even any lighting. That's how basic this is.

The other approximation I'm making is always scanning to the left to avoid seams, which could be another source of aliasing.

It's a crummy renderer, but the performance limitations are driving me insane. I want to get a solid algorithm before I go crazy trying to ASM anything else.

##### Share on other sites
what do you mean by pure start and end point? you're not rounding or useing some sort of bresengham equivilant? if you have two triangels connected by edge there should be no aliasing what so ever. the usual convention is to start at the normal location and then end one pixel short of your true end pixel, in this way the next triangle that is connected to it, will fill in this line, and there will be no "z-aliasing". oh wait you're not using zbuffer are you? in that case the last triangle drawn will get the shared edge. anyway two questions

Quote:
 The other approximation I'm making is always scanning to the left to avoid seams

what do you mean, is this what I'm talking about above, because this is only required for z buffered systems, or if the order of drawing is constantly changing, then you'll get strobe effects?

Quote:
 Right now, I'm using the "pure" start and end point of the triangle scanline to calculate texture coordinates, which causes ugly zipper aliasing

please elaborate, there should be no aliasing whatsoever because where a triangle edge ends, another begins if the algorithm is properly coded, the right edge of one triangle will match up perfectly with the left edge of the adjacent triangle. I'm sorry explain in more baby term(specific) for me lol.

also, are you splitting triangles into two, a flat bottom and a flat top?? if so you should ensure that the slope along each edge is EXACTLY the same for the rendering of both the flat bottom and the flat top, and thus the bresenham error metric must not be zerod, when you start drawing the flat bottom triangle, the error metric for the side that is comon to both the top and bottom triangle should be the same as it was at the END of the drawing of the flat bottom triangle. if you don't do this, triangle edges will not exactly match up. I'm thinking that might be your problem. one thing is certian, it's deffinitly OK to round your 3 vertices to integer before you start drawing. because each adjacent triangle will be rounded in exactly the same way, it doesn't effect the quality of the edges. I'd suggest you familiarize yourself with the "midpoint" algorithm or the "bresenham" algorithm(I'm sure I didn't spell his name right lol) because the error metric don't involve division, the only division you should have would be in the calculation of the texture coordinates I'd think. why would this cause aliasing if the triangle edges matched up exactly as they should? perhaps you should clamp the last texture coordniate to it's proper value, perhaps this is a result of cumlitive precision loss from the addition of texture coorid accross the triangle.

Tim

##### Share on other sites
I guess you have already read Michael Abrash's Graphics Programming Black Book. But in case you haven't, then this is a _must_ read for you!

##### Share on other sites
I dont remember what I've done when I implemented my software renderer but I think you cannot avoid the minimum of a division per scan line during texture mapping. The z-depth can be double linearized but tex map not.

Take a look at Mesa 3D source code, probably the most complete software renderer.
It has a lot of asm implementations.
Also quake2 source code can interest you because it has different double software implementation in C and asm.

##### Share on other sites
Quote:
 Original post by blizzard999I dont remember what I've done when I implemented my software renderer but I think you cannot avoid the minimum of a division per scan line during texture mapping.

Nah, at least for affine mapping you only need one div per triangle to calculate the u/v gradients for interpolating across each scanline. They stay (theoretically) constant all the way down the triangle, so just interpolate the starting u/v as you move down the left edge, and use your same gradients every time.

flamurai, what kind of a CPU are you coding for? If it's ARM, here's the inner loop of an old texture mapper I did for the GBA

tritex_draw_loop:and r0, r3, r4, ASR #16   @ \_ u/v are 16-bit fixed. Shift and r1, r3, r5, ASR #16   @ /  down and mask with size.add r0, r0, r1, LSL r2    @ u + v*wldrb r0, [r12, r0]        @ Load texel (8-bit paletted)ldr r0, [r14, r0, LSL #1] @ Load the actual color from the palettestrh r0, [r10], #2        @ Write to dest, and incrementadd r4, r4, r6            @ u += duadd r5, r5, r7            @ v += dvcmp r10, r11              @ If dest < end pointer, loopblt tritex_draw_loop

10 instructions, and it could be even faster with a bit of loop unrolling and dynamic code.

##### Share on other sites
There's another method of polygone rasterization called 'half space' rendering. It still requires at least one divide for the dot product though.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 12
• 30
• 9
• 16
• 12