Log In  

Cart #53994 | 2018-07-07 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA
34

I am still very new to PICO-8 and saw a few games rendered with polygons.
This lead me to the Trifill Thunderdome benchmark by Musurca.

One thing this benchmark didn't show was the number of tokens for each method which is an important detail considering the limitations of the platform.

Also, I wrote two triangle rasterizers in 163 and 335 tokens respectively which perform pretty decently. They might be an acceptable alternative to ElectricGryphon's super fast triangle rasterizer if you need an extra 2-400 tokens. If you don't, by all mean use his. It is the fastest one I found, and by a good margin!

Update 20180706: Added the possibility to switch rasterizer and turn the test triangle with the arrow keys. This allows to compare rasterizers at a normal pace. Updated EG's rasterizer to the latest he posted in the previous thread and added the one from Gryphon 3D Engine Library v2 only modified to use normal color() and fillp().

Update 20180708: Added a fill pattern and a toggle for the results and control wireframe.

Hope this helps,

P#53941 2018-07-04 16:42 ( Edited 2018-07-08 17:39)

Looks like some of the new rasterizers have severe artifacts on edges.
@p01 are these yours?

P#53947 2018-07-05 02:59 ( Edited 2018-07-05 06:59)

That would be the one by @creamdog. It uses memset(screenAddress, col * 17, scanlineWidth) which can only set an even number of pixels. Hence the half resolution horizontally and the artifacts.

The triangle you see spinning after the benchmark uses my 335 tokens rasterizer.

P#53949 2018-07-05 04:23 ( Edited 2018-07-05 08:23)

Nice work! I haven't looked at the code yet, but that's a mighty optimization effort right there. (Twice!)

edit: I added some code to switch between renderers on the result screen, there seems to be something not quite right with at least one of the algorithms. (Pretty sure I set things up right, maybe not?)

z changes the renderer, x pauses the rotation, up changes the colour.
You might want to extend this to modify the vertices as well if you're hunting for artefacts.


add this part after the tests array definition, around line 620

functioninfo={}
add(functioninfo, { tests[1], solid_trifill_v3, "solid_trifill_v3" } )
add(functioninfo, { tests[2], function(...) local v={...} musurca_triangle({v[1],v[2]},{v[3],v[4]},{v[5],v[6]},v[7]) end, "musurca_triangle" } )
add(functioninfo, { tests[3], creamdog_tri, "creamdog_tri" } )
add(functioninfo, { tests[4], p01_triangle_335, "p01_triangle_335" } )
add(functioninfo, { tests[5], function(...) gfx_draw({...}) end, "gfx_draw" } )
add(functioninfo, { tests[6], steptri, "steptri" } )
add(functioninfo, { tests[7], p01_triangle_163, "p01_triangle_163" } )

replace everything from ::loop_showing_results:: onwards with this

local method,col,pausetime,paused=3,0,0,false
::loop_showing_results::
cls(1)

local u=t()/8
if btnp(5) then
 if (not paused) pausetime=u
 paused=not paused
end
if (paused) u=pausetime

if (btnp(2)) col=(col+1)%16
local r=80+32*cos(u*1.7)
if btnp(4)  then
 method=(method+1)%#functioninfo
end
local fn=functioninfo[method+1]
fn[2](64+r*cos(u),64+r*sin(u),64+r*cos(u+.33),64+r*sin(u+.33),64+r*cos(u+.67),64+r*sin(u+.67),col)

--zebra = 0
for i=0,#tests do print_result(i) end
print(fn[1].author.."-"..fn[3],0,122,7)
flip()
goto loop_showing_results

P#53956 2018-07-05 11:44 ( Edited 2018-07-07 02:04)

THANKS!

Excellent idea to try the different rasterizers after the benchmark.

I tried this last night and saw some have wild bugs. I updated EG's rasterizer to the last one he posted in the previous thread, and the one from the Gryphon 3D librarry v2 and now my "big" rasterizer comes ahead :U

P#53963 2018-07-06 08:17 ( Edited 2018-07-06 13:48)

Another nice addition would be an overlay of the demo triangle using plain lines (dunno, switch on/off using button).
Not all rasterizers are drawing the triangle at the same place!!

EDIT: just did the test, and @p01 are fast and accurate. Nice job!

...
tests[method_index].fn(1)
-- "native" pico triangle/lines
if btn(4) then
 for i=0,2 do
    local p0,p1=2*i+1,(2*(i+1))%6+1
    line(f[p0],f[p0+1],f[p1],f[p1+1],8)
 end
end
P#53968 2018-07-06 13:00 ( Edited 2018-07-06 17:13)

Thanks. Great idea. I also added a fill pattern to make sure the different rasterizers can draw shaded triangles.

P#53995 2018-07-07 19:45 ( Edited 2018-07-07 23:45)
1

Hi, @p01
I'm developing a 3D modeling tool with a small specification for PICO-8.
I would like to post on the BBS using your awesome trifill code.

P#74559 2020-04-08 10:52 ( Edited 2020-04-08 10:54)
1

That's the idea ;)
Go right ahead an use this code if it helps your project.

This modeler looks neat!

P#74561 2020-04-08 11:09
1

Thank you!
I've posted a production!

https://www.lexaloffle.com/bbs/?tid=37287

P#74564 2020-04-08 13:43
9

I created a trifill() for my project.
I'd like to share it because it has a different loop than the other code.
Thank you so much for posting this place!

[UPDATE:20230908(1)]

Taking a cue from @Spaz48's idea, we sped up the trifill() code, reduced the cost of tokens, and drew the last 1px!

"_HV", "_TCLIP", "_LOW".
Each code was even more extreme in its results, but more selective.

[UPDATE:20230908(2)]

The last 1px was not to be drawn in a near-horizontal triangle.( _HV )

[UPDATE:20230909(3)]

Return to the beginning how to sort vertices,
and Changed the process to one that does not use the API.( _HVB )

"_HVB" 272token(top clipping & H-V processing branch & Minimize API & Sort well used at the Beginning.)

function pelogen_tri_hvb(l,t,c,m,r,b,col)
    color(col)
    local a=rectfill
    ::_w_::
    if(t>m)l,t,c,m=c,m,l,t
    if(m>b)c,m,r,b=r,b,c,m
    if(t>m)l,t,c,m=c,m,l,t

    local q,p=l,c
    if (q<c) q=c
    if (q<r) q=r
    if (p>l) p=l
    if (p>r) p=r
    if b-t>q-p then
        l,t,c,m,r,b,col=t,l,m,c,b,r
        goto _w_
    end

    local e,j,i=l,(r-l)/(b-t)
    while m do
        i=(c-l)/(m-t)
        local f=m\1-1
        f=f>127 and 127 or f
        if(t<0)t,l,e=0,l-i*t,b and e-j*t or e
        if col then
            for t=t\1,f do
                a(l,t,e,t)
                l=i+l
                e=j+e
            end
        else
            for t=t\1,f do
                a(t,l,t,e)
                l=i+l
                e=j+e
            end
        end
        l,t,m,c,b=c,m,b,r
    end
    if i<8 and i>-8 then
        if col then
            pset(r,t)
        else
            pset(t,r)
        end
    end
end

"_TCLIP" 140 token(Enable top clipping only)

function pelogen_tri_tclip(l,t,c,m,r,b,col)
    color(col)
    local a=rectfill
    while t>m or m>b do
        l,t,c,m=c,m,l,t
        while m>b do
            c,m,r,b=r,b,c,m
        end
    end
    local e,j=l,(r-l)/(b-t)
    while m do
        local i=(c-l)/(m-t)
        if(t<0)t,l,e=0,l-i*t,b and e-j*t or e
        for t=flr(t),min(flr(m)-1,127) do
            a(l,t,e,t)
            l+=i
            e+=j
        end
        l,t,m,c,b=c,m,b,r
    end
    pset(r,t)
end

"_LOW" 113 token(minfy-code! Non top clipping)

function pelogen_tri_low(l,t,c,m,r,b,col)
    color(col)
    while t>m or m>b do
        l,t,c,m=c,m,l,t
        while m>b do
            c,m,r,b=r,b,c,m
        end
    end
    local e,j=l,(r-l)/(b-t)
    while m do
        local i=(c-l)/(m-t)
        for t=flr(t),min(flr(m)-1,127) do
            rectfill(l,t,e,t)
            l+=i
            e+=j
        end
        l,t,m,c,b=c,m,b,r
    end
    pset(r,t)
end


Cart #pelogen_tri_bench-1 | 2023-09-09 | Code ▽ | Embed ▽ | No License
9

Previous Code 1

"_HV" 229 token(top clipping & H-V processing branch)

function pelogen_tri_hv(l,t,c,m,r,b,col)
    color(col)
    local a=rectfill
    ::_w_::
    while t>m or m>b do
        l,t,c,m=c,m,l,t
        while m>b do
            c,m,r,b=r,b,c,m
        end
        if b-t>max(max(l,c),r)-min(min(l,c),r) then
            l,t,c,m,r,b,col=t,l,m,c,b,r
            goto _w_
        end
    end
    local e,j,i=l,(r-l)/(b-t)
    while m do
        i=(c-l)/(m-t)
        local f=min(flr(m)-1,127)
        if(t<0)t,l,e=0,l-i*t,b and e-j*t or e
        if col then
            for t=flr(t),f do
                a(l,t,e,t)
                l=i+l
                e=j+e
            end
        else
            for t=flr(t),f do
                a(t,l,t,e)
                l=i+l
                e=j+e
            end
        end
        l,t,m,c,b=c,m,b,r
    end
    if abs(i)<8 then
        if col then
            pset(r,t)
        else
            pset(t,r)
        end
    end
end

Previous Code 2

308 token(top clipping & V-H processing branch)

function pelogen_tri_308(v1,v2,v3,col)
color(col)
local l,c,r,t,m,b=pelogen_sort(v1,v2,v3,2)
if abs(r-l)>abs(b-t) then
v1,v2,v3=l,t,0
local j=(r-l)/(b-t)
while t~=b do
local i=(c-l)/(m-t)
if(t<0) t,l,v1,v3=0,l-i*t,v1-j*(t-v3),m
for t=t,min(m-1,127) do
rectfill(l,t,v1,t)
l+=i
v1+=j
end
c,l,t,m=r,c,m,b
end
else
l,c,r,t,m,b=pelogen_sort(v1,v2,v3,1)
v1,v2,v3=l,t,0
local j=(b-t)/(r-l)
while l~=r do
local i=(m-t)/(c-l)
if(l<0) l,t,v2,v3=0,t-i*l,v2-j*(l-v3),c
for l=l,min(c-1,127) do
rectfill(l,t,l,v2)
t+=i
v2+=j
end
m,t,l,c=b,m,c,r
end
end
end
function pelogen_sort(v1,v2,v3,v)
if(v1[v]>v2[v]) v1,v2=v2,v1
if(v1[v]>v3[v]) v1,v3=v3,v1
if(v2[v]>v3[v]) v3,v2=v2,v3
return flr(v1[1]),flr(v2[1]),v3[1],flr(v1[2]),flr(v2[2]),v3[2]
end

176 token(Enable top clipping only)

function pelogen_tri_176(v1,v2,v3,col)
color(col)
if(v1[2]>v2[2]) v1,v2=v2,v1
if(v1[2]>v3[2]) v1,v3=v3,v1
if(v2[2]>v3[2]) v3,v2=v2,v3
local l,c,r,t,m,b=v1[1],v2[1],v3[1],flr(v1[2]),flr(v2[2]),v3[2]
local i,j,k,r=(c-l)/(m-t),(r-l)/(b-t),(r-c)/(b-m),l
while t~=b do
if(t<0)t,l,r=0,l-i*t,v1 and r-j*t or r
for t=t,min(m-1,127) do
rectfill(l,t,r,t)
r+=j
l+=i
end
l,t,m,i,v1=c,m,b,k
end
end

129 token(minfy-code! Non top clipping) [UPDATE:20221118]

function pelogen_tri_129(l,t,c,m,r,b,col)
color(col)
if(t>m) l,t,c,m=c,m,l,t
if(t>b) l,t,r,b=r,b,l,t
if(m>b) c,m,r,b=r,b,c,m
local i,j,k,r=(c-l)/(m-t),(r-l)/(b-t),(r-c)/(b-m),l
while t~=b do
for t=flr(t),min(flr(m)-1,127) do
rectfill(l,t,r,t)
l+=i
r+=j
end
l,t,m,i=c,m,b,k
end
end

Previous Code 3

134 token(minfy-code! Non top clipping)

function pelogen_tri_134(l,t,c,m,r,b,col)
color(col)
if(t>m) l,t,c,m=c,m,l,t
if(t>b) l,t,r,b=r,b,l,t
if(m>b) c,m,r,b=r,b,c,m
t,m=flr(t),flr(m)
local i,j,k,r=(c-l)/(m-t),(r-l)/(b-t),(r-c)/(b-m),l
while t~=b do
for t=t,min(m-1,127) do
rectfill(l,t,r,t)
r+=j
l+=i
end
l,t,m,i=c,m,b,k
end
end

The random result is fixed by srand(4).

P#75530 2020-04-28 00:03 ( Edited 2023-09-09 14:08)
1

Here's my 143 token take on a triangle fill.

--@Domino_Marama

function domino_tri(x0,y0,x1,y1,x2,y2,col)
 color(col)
 if(y1<y0)x0,x1,y0,y1=x1,x0,y1,y0
 if(y2<y0)x0,x2,y0,y2=x2,x0,y2,y0
 if(y2<y1)x1,x2,y1,y2=x2,x1,y2,y1
 if(y0!=y1) x0,col=trapa(y0,y1,x0,x0,(x1-x0)/(y1-y0),(x2-x0)/(y2-y0))
 if(y1!=y2) trapa(y1,y2,x1,x0,(x2-x1)/(y2-y1),col)
end

function trapa(y1,y2,lx,rx,dl,dr)
 for y=y1,min(y2,128) do
  rectfill(lx,y,rx,y)
  lx+=dl
  rx+=dr
 end
 return rx-dr,dr
end
P#88908 2021-03-13 00:52 ( Edited 2021-03-13 14:52)

i made my own tri function : https://www.lexaloffle.com/bbs/?tid=49930

P#119767 2022-10-28 14:02
4

Cart #azure_trifillr4-2 | 2023-09-06 | Code ▽ | Embed ▽ | No License
4

Felt like throwing my hat into the ring. Here's my trifill func, and a revised test cart with mine and a couple others from the thread added.

EDIT: Realized the a var was technically redundant, shaved a few more tokens, now 122 and 134! Slightly less legible, though..

EDIT 2: Further optimizations! Avg tris/sec is up by somewhere in the range of 400-500, all for no extra tokens in the faster ver (found a small token optim to make up for it) and for only 3 extra tokens in the lower token ver! Now it's punching pretty close to the big leagues, managing nearly 5000 tris/sec, at the same tiny size it's always been!

Faster ver. (134 tokens)

-- azure48 triangle fill, faster
function azufasttri(x1,y1,x2,y2,x3,y3,c)
 local r = rectfill
    for i = 0, 1 do
        if(y1>y2)x1,y1,x2,y2 = x2,y2,x1,y1
        if(y2>y3)x2,y2,x3,y3 = x3,y3,x2,y2
    end
    local da = (x2-x1)/(y2-y1)
    local db = (x3-x1)/(y3-y1)
    local b = x1
    color(c)
    for i = y1, y2 do
        r(x1, i, b, i)
        x1 = da+x1
        b = db+b
    end
    da=(x2-x3)/(y2-y3)
    for i = y2, y3 do
        r(x2, i, b, i)
        x2 = da+x2
        b = db+b
    end
    pset(x3,y3)
end

Token saving ver. (125 tokens) (Ver in "old vers" is slower but slightly smaller, if you need 3 more tokens)

-- azure48 triangle fill, lowest tokens
function azulowtri(x1, y1, x2, y2, x3, y3, c)
  local r = rectfill
  for i = 0, 1 do
      if(y1>y2)x1,y1,x2,y2 = x2,y2,x1,y1
      if(y2>y3)x2,y2,x3,y3 = x3,y3,x2,y2
  end
  local b,da,db = x1,(x2-x1)/(y2-y1),(x3-x1)/(y3-y1)
  color(c)
  for o = 0,1 do
      for i = y1, y2 do
          r(x1, i, b, i)
          x1 = da+x1
          b = db+b
      end
      x1 = x2
      da=(x2-x3)/(y2-y3)
      y1=y2 y2=y3
  end
 pset(x3,y3)
end

The trick ended up being to abuse a really nuanced little feature of p8's cycle counter. Functions, being variables under the hood like any other, take 2 cycles to look up (on top of their other costs) same as looking up global variables. This, of course, applies to the built in global funcs too. Local variables however, don't charge anything to look up.

..So if you're using a func a ton for something, what's to stop you from redefining it as a local so that you can avoid those 2 look up cycles per call? Nothing, not even a special exception for the builtins!

This little trick could optimize a ton of things outside of triangles, and it'd make pretty much every other tri algo in the cart faster at the cost of those 3 extra tokens to redefine it. If I feel like it later, I might try to apply it to all of the others just for the sake of fair comparison.

Moreover.. as a trick I think it's balanced. You have to always eat those extra tokens if you want the speedup. That is to say, zep please don't patch this lmao

Old vers:


Token saving ver. (122 tokens)

-- azure48 triangle fill, lowest tokens
function azulowtri(x1, y1, x2, y2, x3, y3, c)
    for i = 0, 1 do
        if(y1>y2)x1,y1,x2,y2 = x2,y2,x1,y1
        if(y2>y3)x2,y2,x3,y3 = x3,y3,x2,y2
    end
    local b,da,db = x1,(x2-x1)/(y2-y1),(x3-x1)/(y3-y1)
    color(c)
    for o = 0,1 do
        for i = y1, y2 do
            rectfill(x1, i, b, i)
            x1 = da+x1
            b = db+b
        end
        x1 = x2
        da=(x2-x3)/(y2-y3)
        y1=y2 y2=y3
    end
 pset(x3,y3)
end

Slightly faster ver. (134 tokens)

-- azure48 triangle fill, slightly faster
function azufasttri(x1,y1,x2,y2,x3,y3,c)
    for i = 0, 1 do
        if(y1>y2)x1,y1,x2,y2 = x2,y2,x1,y1
        if(y2>y3)x2,y2,x3,y3 = x3,y3,x2,y2
    end
    local da = (x2-x1)/(y2-y1)
    local db = (x3-x1)/(y3-y1)
    local b = x1
    color(c)
    for i = y1, y2 do
        rectfill(x1, i, b, i)
        x1 = da+x1
        b = db+b
    end
    x1 = x2
    da=(x2-x3)/(y2-y3)
    for i = y2, y3 do
        rectfill(x1, i, b, i)
        x1 = da+x1
        b = db+b
    end
    pset(x3,y3)
end

Old old vers:

-- azure48 triangle fill, lowest tokens (127 tokens)
function azulowtri(x1, y1, x2, y2, x3, y3, c)
    for i = 0, 1 do
        if(y1>y2)x1,y1,x2,y2 = x2,y2,x1,y1
        if(y2>y3)x2,y2,x3,y3 = x3,y3,x2,y2
    end
    local da = (x2-x1)/(y2-y1)
    local db = (x3-x1)/(y3-y1)
    local a = x1
    local b = x1
    color(c)
    for o = 0,1 do
        for i = y1, y2 do
            rectfill(a, i, b, i)
            a = da+a
            b = db+b
        end
        a = x2
        da=(x2-x3)/(y2-y3)
        y1=y2 y2=y3
    end
 pset(x3,y3)
end
-- azure48 triangle fill, slightly faster (137 tokens)
function azufasttri(x1,y1,x2,y2,x3,y3,c)
    for i = 0, 1 do
        if(y1>y2)x1,y1,x2,y2 = x2,y2,x1,y1
        if(y2>y3)x2,y2,x3,y3 = x3,y3,x2,y2
    end
    local da = (x2-x1)/(y2-y1)
    local db = (x3-x1)/(y3-y1)
    local a = x1
    local b = x1
    color(c)
    for i = y1, y2 do
        rectfill(a, i, b, i)
        a = da+a
        b = db+b
    end
    a = x2
    da=(x2-x3)/(y2-y3)
    for i = y2, y3 do
        rectfill(a, i, b, i)
        a = da+a
        b = db+b
    end
    pset(x3,y3)
end

They may not be the fastest, but I've made the lowest token count func with performance around above! average compared to the others. Using the kinda silly statistic of tokens per tri per sec, the lower token ver is the best bang for buck out of all of them! The actual test cart has commented vers, if you feel like picking them apart.

(Feel free to use these for whatever, just credit me somewhere as Azure48, preferably leave "azu" in the func name.)

P#131612 2023-07-04 05:10 ( Edited 2023-09-07 00:25)

well done! - can be further optimized:

local a,b,da,db=x1,x2,…
…
for … do
  rectfill(…)
  a+=da
  b+=db
end
P#131619 2023-07-04 08:41 ( Edited 2023-07-04 08:41)

Fascinating, I never even thought about using ... like that, I'll have to toy with that some tomorrow.
However, the choice to use a=a+da over a+=da was intentional. It's faster.. sometimes, including this. Assignment operators used to be a macro p8 did and thus was a free token save, but recent versions of p8 have replaced it with a real implementation. In my testing, it seems that the new "real" ones are more expensive for some reason, unfortunately.. but only sometimes? You should be able to edit the cart and see for yourself that it preforms worse with +=. Perhaps it's a bug, I'm really not sure.

P#131625 2023-07-04 10:09 ( Edited 2023-07-04 10:14)

+= being slower is a bug (already reported)

P#131636 2023-07-04 15:14

Yeah, makes sense. I keep fairly on top of p8 changelogs, so I'll just edit the post whenever that's fixed. As for the other thing, now that I'm not so sleepy i realize you were just using ... to skip over bits you didn't want to type out, my tired brain read that as you using it as an iterator and etc.
The variable defs not being all in one line was intentional too, that's also faster, though the difference is a lot more negligible there. It is 3 tokens less.. I guess I ought to use it in the token reduced ver, fair enough.

P#131646 2023-07-04 20:42
2

@Spaz48
I was particularly interested in this swap code.

    for i = 0, 1 do
        if(y1>y2)x1,y1,x2,y2 = x2,y2,x1,y1
        if(y2>y3)x2,y2,x3,y3 = x3,y3,x2,y2
    end

It reduces one line that was set in stone in exchange for taking an extra step.

Also, the pset() fills in the missing edge at the bottom of the triangle. It is truly the finishing touch.

(These are things I had given up on and seem to have more potential!)

P#131666 2023-07-05 07:02
1

(Bump, I have made major progress with my func that I believe is worth seeing. I did so by editing my earlier post, bc I thought that'd bump since I updated the cart, but I guess that's only how it works for the OP.)

P#134005 2023-09-07 00:29
1

@shiftalow 6500 tris/sec! Incredible, I didn't think that'd even be possible, and still so competitively small.. I had already started thinking about ways to get that last ~500 tris to catch up to p01.. but then you blow me out of the water by managing +~1000-1500. Insane. I'm going to have to try to beat that, of course.. :3

P#134033 2023-09-07 19:33 ( Edited 2023-09-07 19:42)
2

@Spaz48 I could not believe it myself!
So I re-tested it, reflected it on the modeling cart, and carefully looked at the stability.
And I want to apologize for that. In my post edit, I mistakenly compared it with your old code...!
I have now resubmitted my cart.

P.S. We may need to note the characteristics of art that arise when pressure is applied.

P#134040 2023-09-08 07:41
1

@shiftalow Ah, that bug popped up pretty early but I was pretty sure i squashed it.. i'm pretty sure it's caused by p8's fixed point numbers lacking precision.. I have some ideas on how to speed things up that might also get rid of that, but I'm not entirely sure.

P#134045 2023-09-08 08:05
1

https://www.lexaloffle.com/bbs/?pid=75530#p

I have updated the fast type trifill!
pelogen_tri_hvb() [272token, 7200 tris/sec].

P#134093 2023-09-09 14:06

[Please log in to post a comment]

Follow Lexaloffle:          
Generated 2024-03-28 19:47:45 | 0.050s | Q:56