So you think you can code... rendering polygons

Zro716

the fastest original code is Jamohyperturbopro's incenter-based triangle fill, and the fastest of all time is DadOfMrLog's modified version of that.

Edit: DadOfMrLog (aka TheLogFather) has just shared a new “hybrid” triangle filler that is curiously faster than the above two.

the question is, can we go even faster? *sanic intensifies*

in theory, we can.

let's start a new challenge similar to gtoal's sorting shootout, but this time we will test polygon rendering speeds against DOML's script. the goal is to find the technique that can render upwards of 1000 triangles the fastest.

to enter, just link to the project with your rendering algorithm ready to transfer and I will set up the competition from there.

Last edited by Zro716 (April 3, 2015 15:17:43)

MrSherlockHolmes

Sounds like a challenge! Not one I could take up, but I'd love to watch it progress

Zro716

I thought people would jump at this challenge by now.

let's set the criteria for now.

only render triangles – quads and other surfaces must be split into several triangles
must be able to render ANY triangle, not predefined ones
rendering speed must be at least 25 triangles at 30+ FPS minimum
don't worry about screen culling; have good faith that all triangles will be within the stage
all assets for rendering the triangles must be in one sprite. no help from other sprites.
submit final draft before April 1st; late applicants will not be accepted. no refunds either

Last edited by Zro716 (Feb. 17, 2015 19:42:41)

MoreGamesNow

Zro716 wrote:
sanic scanline intensifies

ftfy

On to seriousness: I would also impose a limit on triangle sizes as well. Small triangles will render more quickly than large ones.

Zro716

MoreGamesNow wrote:
On to seriousness: I would also impose a limit on triangle sizes as well. Small triangles will render more quickly than large ones.

I'll consider that point. for now, expect to render triangles of arbitrary size.

TheLogFather

I know I can get my current modification of Jamo's filler a little faster using a couple of tricks, but I'd certainly be really interested to see if anyone can find an alternative algorithm that's quicker (or even nearly so, since we might be able to improve it)…

For polygons more generally, I've had a bit of a go at making a fast quad-filler, based on finding the maximum in-circle that touches three sides, looking for the co-ords for where that just fits within at each of the four corners (there are three sets of co-ords, generally, since two of them are the same), and then drawing lines between them while moving out from there towards the corners in the same way as the tri-filler.

Unfortunately, there's quite some work involved in finding the best in-circle, and that ends up making it not quite as quick as just splitting into a pair of tris and filling those, which was a bit disappointing (and was why I still did it that way for my 3D terrain project, which is mainly filling quads).

I'd therefore also be very interested to know if anyone *can* find a way to fill a quad (let's not go any further for now) that is quicker than splitting into a pair of tris…

Last edited by TheLogFather (Feb. 16, 2015 16:18:10)

MegaApuTurkUltra

I dug up my old glitchy scanline triangle filler to see if it might work here - it can only fill about 30 triangles per second so nope :P. I might code something if I have time.

Penguin9090_new

My renderer
This can render 1000 triangle/second.

MegaApuTurkUltra

Penguin9090_new wrote:
My renderer
This can render 1000 triangle/second.

Zro, please add “your renderer must be able to render ANY on-screen triangle” to the rules

Zro716

MegaApuTurkUltra wrote:
Penguin9090_new wrote:
My renderer
This can render 1000 triangle/second.
Zro, please add “your renderer must be able to render ANY on-screen triangle” to the rules

got it

Penguin9090_new

MegaApuTurkUltra wrote:
Penguin9090_new wrote:
My renderer
This can render 1000 triangle/second.
Zro, please add “your renderer must be able to render ANY on-screen triangle” to the rules

updated renderer

MegaApuTurkUltra

Ugh Zro maybe you should just say, “Your triangle renderer must take a set of 3 cartesian two-dimensional coordinates as input, where no coordinate exceeds the project player bounds, and the coordinates are guaranteed to form a real triangle, and it must render the triangle formed by those points.”

TheLogFather

Penguin9090_new wrote:
updated renderer

Yeh, I kinda saw that change coming…

However, it's not really that hard to tweak it to make it general. At the moment it's capable of drawing any triangle that has one edge horizontal. All you have to do to make it general is to take an arbitrary triangle and split it into two such that the divider is horizontal. Then you can draw the top and bottom ones in just the way you are now (though you need to do a bit of maths with the three vertex co-ords supplied to find which vertex should have the horizontal split line, and get its length, and a bit more to get the appropriate lengths for the top and bottom tris).

Last edited by TheLogFather (Feb. 17, 2015 23:35:53)

Penguin9090_new

TheLogFather wrote:
Penguin9090_new wrote:
updated renderer
Yeh, I kinda saw that change coming…

However, it's not really that hard to tweak it to make it general. At the moment it's capable of drawing any triangle that has one edge horizontal. All you have to do to make it general is to take an arbitrary triangle and split it into two such that the divider is horizontal. Then you can draw the top and bottom ones in just the way you are now (though you need to do a bit of maths with the three vertex co-ords supplied to find which vertex should have the horizontal split line, and get its length, and a bit more to get the appropriate lengths for the top and bottom tris).

Too technical for me.

MegaApuTurkUltra

Finally got around to making this. It's not a winner by any means :P

http://scratch.mit.edu/projects/48561244/

It works by filling an inscribed circle, then going out 3 times from the incenter to the verticies and changing pen size accordingly. It also draws a border to make the edge smooth.

Last edited by MegaApuTurkUltra (Feb. 18, 2015 19:15:54)

gtoal

TheLogFather wrote:
I'd therefore also be very interested to know if anyone *can* find a way to fill a quad (let's not go any further for now) that is quicker than splitting into a pair of tris…

Yes, actually I've always believed that horizontally-aligned quads are a better primitive than triangles. Take any triangle whose base is horizontal. Stretch the sides apart so that it morphs into a quad with a horizontal top and bottom. The calculations to determine the x/y steps of the two sides are the same, the only difference is that the horizontal lines are longer. So triangles are a subset of quad.

if the triangle is not aligned on a horizontal base, take the point in the triangle that is not the highest or lowest point, and draw a horizontal line through it to bisect the triangle into two triangles with a horizontal base (or top). Problem reduces to the one above.

I'll code this up if I can. (I'm still over in the UK handling elderly parent health care issues, so not really up to having fun with Scratch, but there are a lot of quiet times sitting around and waiting in hospitals etc so I might be able to find some time to work on this…)

Graham

gtoal

MegaApuTurkUltra wrote:
Penguin9090_new wrote:
My renderer
This can render 1000 triangle/second.
Zro, please add “your renderer must be able to render ANY on-screen triangle” to the rules

So I infer that rendering *off-screen* triangles (or at least partially off-screen ones, ie clipping) is not a requirement?

Because that can make a big difference to efficiency…

G

MegaApuTurkUltra

gtoal wrote:
MegaApuTurkUltra wrote:
Penguin9090_new wrote:
My renderer
This can render 1000 triangle/second.
Zro, please add “your renderer must be able to render ANY on-screen triangle” to the rules

So I infer that rendering *off-screen* triangles (or at least partially off-screen ones, ie clipping) is not a requirement?

Because that can make a big difference to efficiency…

G

Zro716 wrote:
don't worry about screen culling; have good faith that all triangles will be within the stage

gtoal

Zro716 wrote:
to enter, just link to the project with your rendering algorithm ready to transfer and I will set up the competition from there.

OK, here's my first hack at this… http://scratch.mit.edu/projects/48571128/ it's basically filling with quads (axis-aligned triangles are a special case of axis-aligned quads. (the degenerate side being the apex of the triangle)) and the quads are drawn with parallel-stepping DDAs for each side and a horizontal line between them.

It could be implemented with Bresenham's in all-integer mode but I suspect that with Scratch's overhead, there's no benefit to be had.

G

Last edited by gtoal (Feb. 18, 2015 22:03:00)

gtoal

TheLogFather wrote:
However, it's not really that hard to tweak it to make it general. At the moment it's capable of drawing any triangle that has one edge horizontal. All you have to do to make it general is to take an arbitrary triangle and split it into two such that the divider is horizontal. Then you can draw the top and bottom ones in just the way you are now (though you need to do a bit of maths with the three vertex co-ords supplied to find which vertex should have the horizontal split line, and get its length, and a bit more to get the appropriate lengths for the top and bottom tris).

I did that in mine, but on looking at it I'm pretty sure there will be a *much* a cheaper test to y-order the three points. (I'm doing 6 a <= b <= c tests)

G

Last edited by gtoal (Feb. 18, 2015 22:18:16)

Discuss Scratch