Log In  

Cart #mupudeyowa-3 | 2019-05-21 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA

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.

P#64614 2019-05-20 11:40 ( Edited 2019-05-21 08:38)

@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 ;)

P#64619 2019-05-20 12:31 ( Edited 2019-05-20 12:40)

@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.

P#64621 2019-05-20 14:34 ( Edited 2019-05-20 14:42)

now I am blushing :]

12 tokens saved - line 24:

xl[y1],xr[y1]=min(xl[y1] or 32767,min(x1,x2)),max(xr[y1] or -32768,max(x1,x2))
P#64625 2019-05-20 19:17 ( Edited 2019-05-20 19:32)

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).

P#64626 2019-05-20 20:08 ( Edited 2019-05-20 20:12)

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.

P#64627 2019-05-20 20:40

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
        for y=y1,y2 do
            local d=y2-y1
            x_array[y]=flr(x1+(x2-x1)*(y-y1)/(d==0 and 1 or d))
    for y=ymin,ymax do
P#64628 2019-05-20 21:05

Neat. How's the performance compared to triangles?

P#64632 2019-05-20 23:27

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

P#64646 2019-05-21 05:16

@Xii it is slower than @p01 trifill by a a good margin (maybe faster for many sided polygons but for tris and quads, trifill is still the best option)

P#64647 2019-05-21 05:20

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.

P#64651 2019-05-21 08:37

This poly fill function is perfect for what I need. Would you mind if I use this in a small project of mine?

P#92952 2021-06-03 11:01

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/ )

P#92962 2021-06-03 15:17

[Please log in to post a comment]

Follow Lexaloffle:          
Generated 2022-12-01 13:28:25 | 0.082s | Q:33