Polygon Drawing Algorithm

[Dan East]

What are the fastest algorithms for drawing solid, filled polygons? Thanks.<br><br>Dan East

[Dan East]

Same thing for filled triangles.<br><br>Dan East

[MirekCz]

ehhh? aren't you repeating your question?:)<br>anyway probably the fastest way (or at least a very fast way which is very often used) is to:<br>1.sort your verticles by y (from low to high)<br>2.calculate deltas for left/right edges<br>3.starting from x1,y1 (sorted x1,y1 so it's the topmost verticle) you're going down your triangle one by line drawing pixels between left and right edge of your triangle (you don't precalculate those values into an array and draw from there as some ppls do, it's easier to implement but slower)<br><br>that's a very basic explanation, you can find a bunch of tutorials about it on www.gamedev.net for ex. It used to be a very often covered topic when software rendering was used a lot. If you want I can send you over some stuff (my poly filler and gourand shader and phantom's affine tmapper , all work with 320 screen width. don't remember about phantom's but my use 24:8 fixedpoint math (probably will go to 22:10 like phantom uses in his matrix stuff soon))<br>so if you have some questions feel free to ask, if my knowledge won't be enought Jacco will surelly know the answer:)

[Digby]

Dan,<br><br>This is covered in Graphics Gems and by Abrash in his Zen of Graphics Programming and reprinted in his later Black Book of Graphics Programming.  The text of Black Book is online in a number of places - here's one of them:<br><br><br><br>Have a look at chapters 38 and 39.<br><br><br>Mirek,<br>Those edge arrays can come in handy if you're rasterizing triangular strips and fans.<br><br>

[MirekCz]

Digby:but is it faster that way? I doubt it, as apart from calculating the deltas you're doing just an add to left and right array edge to get your new position. a perspective correct tmapper might be a problem here, but I guess it's still faster then loading all data from memory(and you have got to precalculate this edge anyway while it won't be used more then twice, so the basic problem is what's faster, calculating 2 times edge at runtime or precalculating an edge every frame it's used and read it 2 times from array at runtime - in a perfect case for your method)<br>as far as I have heard from your chats ARM cpu has got (at least)16 registers, so it should allow you to keep all data in them without using cache or anything, which fits "my" method very well.

[Digby]

You only cache the values for the edge that is shared.  You don't walk all the edges, saving all the values in an array, then go back and walk the array again to perform the fill.  The way it works is that you write to the array as you're stepping down the edge and performing the fill.  The next triangle can read from that array for the shared edge, and if it shares another edge with the next triangle, it caches the values as it steps down that edge.  You toggle the edge buffers between triangles similar to a flipping chain of frame buffers.<br><br>Is it faster?  To tell you the truth I don't know because I haven't implemented it both ways and measured the results. I'm doing perspective correct texture mapping and that requires a division operation for every pixel along that edge.  You did know that the ARM has no divide instruction, right?  One thing nice about the ARM though is those load/store multiple register instructions.  In one instruction you can read/write all the values saved in that array to/from registers.<br><br>Speaking of the ARM... You can use 14 of the 16 ARM registers.  The other two are the stack pointer and the program counter.  That might be enough registers for interpolating r, g, b but not for alpha, z, u, and v.  Unless I've missed something you'll need 2 additional values per interpolated value (for stepping in x and y).  You'll also need a pointer to the render target buffer, a pointer to the texture map buffer, and a register to pack r, g, and b into a 565 value (or to pack two pixels into a DWORD so you don't pay a write penalty), and throw in an extra register for performing alpha blending.  How many registers is that?  I've lost count.<br><br>

[MirekCz]

digby:"your" method won't be faster and it needs a lot of tweaking (preparing model etc) to work pretty well(precalculating to an array is surelly slower, so if you need to do it without a shared edge you're wasteing a lot of time)<br>anyway why don't you use quake-like trick to calculate perspective correct tmapping every 8/16-th pixel <br><br>

[Digby]

You still don't get it.  At a minimum, reading a value from the array is going to be much faster than performing the divide for each pixel along the edge.  I've also shown that you won't be able to fit all of the values necessary to walk an edge in the registers.  So you're saying that even though I have to read/write some of these to memory as you fill the triangle,  throwing away the values and having to recalculate them again is going to be faster?  I don't understand this logic.  Perhaps you can clear it up for me?<br><br>You would not do any of this edge cacheing if you weren't drawing a triangular strip of fan.  That would be silly.<br><br>I don't do the divide for every pixel along the span.  I skip by a value that is stored in the Registry (usually 8 pixels).<br><br>The method needs no tweaking however the 3D models do.  Modelling software can stripify meshes, there are also utilities (free) to do this.  It's not like this is some time-consuming processes to provide strips.  The artist just runs his software through the stripifier and they are done.<br><br>

[prj]

[simonjacobs]

[Digby]

[prj]

I can't see that one can code around the use of divs when doing a polygon filler or drawing lines for that matter. You'll always have to calc the deltas.<br><br>I know it's not optimal in the code above, because the delta is calculated for each line instead of just doing it once and then adding up each side. (I just realized that. What a dumb ass I have been...) Well.. thanks for opening my eyes... Last modification: paulrene - 01/09/02 at 15:32:09

[Zensunni]

paulrene: exactly, and if you are drawing triangle strips or fans, you can reuse that computed delta for the next triangle, thats what digby is trying to say<br><br>(i think, just back from the pub so don't blame me

[Phantom]

Here are some of my experiences with filling polygons:<br><br>- The triangle method is nice (drawing it in two halves without outline tables), but it doesn't allow drawing n-sided polygons. N-sided polygons are useful when you start clipping against a frustum, since that will typically change a triangle to a n-sided poly. You could triangulate that easily, but having a special case for n-sided polies is easier.<br><br>- If you draw a cube using triangles, you'll get bad distortion because of the lack of perspective texture mapping. This effect is far less if you render quads and calculate delta's for each scanline. Rendering a quad that way is more expensive than rendering tri's with constant slopes, but you save one edge (the diagonal), you can draw longer spans (twice as long on average) and the distortion is less. I like this method. <br><br>- Perspective correction is a disaster on the ARM. You can't do the u/z and v/z calculus using floating point, wich means you can't really use reciprocals (bad precision), and you can't do those divides in parallel with integer stuff (like you could do on the Pentium series). Perspective correction is going to be very slow. It might be better to use face subdivision like most engines do on the Playstation 1.<br><br>- The code at the start of this thread doesn't have subpixel accuracy. That's going to be VERY ugly when the triangle moves slowly.<br><br>Well I intend to spend some time tonight on a polygon rasterizer, I'll make sure it's well documented and fast. I have another coding night tomorrow, so you should have something useful before the weekend.<br><br>Later on I'll add bilinear filtering. As opposed to perspective correction, this is very well possible on the StrongARM (and MIPS/SH3).<br><br>- Jacco.

[PDAFantast]