Update 3: Added a 148 token version.

Update 2: Now down to 157 tokens.

Update 1: With improvements from @freds

This is a token optimized version of the polygon drawing routine I originally used in Pico Tennis. I've managed to get it down to 173 tokens, which I'd like to think is comparable to p01's 163 token trifill routine.

Obviously it's going to depend on your needs for which method you use. If you only need to draw triangles then you'll want to use the trifill method, but this allows you to draw shapes with any arbitrary number of vertices.

The only catch with this method is that it only allows your shape to be concave on a single axis.

If anyone has any alternative methods or optimizations please let us know.

@paranoidcactus you can reverse this test:

not xl[y1] and xmin or min(xl[y1],xmin |

to save the ‘not’ (2 tokens)

+

is the flr needed when stepping on y?

+

no 0-128 clipping on y during rendering? you are assuming a lot from your clients ;)

@freds thank you. I'm always impressed that you manage to come through with good improvements.

I actually had y clipping in a previous version but because of the way the original implementation worked it was tracking the min and max y for the vertices instead of pixels. With the way it's working now it's as simple as setting the initial min and max values at the start of the function. Though they need to be set to -1 and 129 otherwise if the polygon is completely off the top or bottom of the screen the loop at the end that does the rectfill will still execute at least once and draw a single pixel in the corner of the screen.

The '-' also costs a token (and runtime cost I think) - replace it with a hex or binary literal. Nowadays these are easy to obtain by feeding the decimal value into tostr(value, true).

Wow, with those changes it gets it down to 157 tokens. Although you'd need to take it up to 158 if you want to be able to pass a color value into the function.

I don't have time to check this properly right now because I need to go to work, but I think the y1==y2 conditional is only there to protect against a divide by zero. It may be possible to remove it completely by doing something like this:

function draw_polygon(points) local xl,xr,ymin,ymax={},{},129,0xffff for k,v in pairs(points) do local p2=points[k%#points+1] local x1,y1,x2,y2,x_array=v.x,flr(v.y),p2.x,flr(p2.y),xr if y1>y2 then x_array,y1,y2,x1,x2=xl,y2,y1,x2,x1 end for y=y1,y2 do local d=y2-y1 x_array[y]=flr(x1+(x2-x1)*(y-y1)/(d==0 and 1 or d)) end ymin,ymax=min(y1,ymin),max(y2,ymax) end for y=ymin,ymax do rectfill(xl[y],y,xr[y],y,8) end end |

@paranoidcactus the y2-y1 diff is *constant*...no need to compute it within the inner loop!!

I've just double checked that change I suggested and it works fine simple shapes like the hexagon in this sample, but if the polygon has more than 2 vertices on the same y coordinate it causes rendering artifacts. It looked particularly bad when I tried to use it in the game I'm working on right now.

That said I've had another play with it and come up with an approach that retains the min/max testing for the x values, but puts them inside the inner loop. Although it'll cause a bit more of a performance hit, it brings it down to 148 tokens and handles non-convex shapes in a nicer way.

The license is creative commons by-nc-sa meaning attribute author, non commercial, share alike (more info: https://creativecommons.org/licenses/by-nc-sa/4.0/ )

[Please log in to post a comment]