pouët.net

We've used some kind of sorted polygons (not quite painter's algorithm) with heavy pre-calc to reduce overdraw. There's not really much memory in the GBA, and EWRAM is slow, so z-buffering is pretty much out of the question IMO. s-buffers have a too big overhead on intersection and data-structure managment in total - we did some tests with it, only to find that it only made stuff slower in our scenes. c-buffers is a very good candidate, IMO.

And yes, I've tried filling polygons directly to tilemaps, and it works like a charm - but it is a bit slower than traditional scan-conversion if you only look at filling a single polygon, at least the way I do it. My "next gba engine" (that I haven't worked on for almost 6 moths :P) does that, mainly because it allows for some quite cool occlusion culling without pre-calcing. Reducing the amount of pre-calc stuffs makes demo development easier, as it's easier to change stuff.

we used span-buffers here, but they turned out to give few benefit with small to medium amounts of overdraw (as such).
for more complex scenes better try to determine visibility on a higher level.

The problem is that it still needs front-to-back sorting/polygon splitting to work, but it needs much less memory (1 bit per pixel, 5k for the GBA). You could load the occlusion information for 32 pixels at a time and bitshift your way through it...
They're also good for overlays, cause you won't draw stuff behind them.


true. But you can be sure not to fill a single unnecessary pixel, so you can do more complex stuff per-pixel and you don't need to sort anything.
I just like them, cause they're elegant ;)

Is sorting polygon really that awful? :)
Keep in mind that there's usually good frame to frame correlation, so something like an insertion sort should give good results.

Uhm, for most scenes, that is.

*Noodles every idea down and implements it*

Same here ;)
This is maybe one of the few threads on pouet that have some valuable information for me :)
...and one of the few that survived the dreaded boing-ball-pouetization.


Meaning re-sort the polys from the previous and save the swap/copy operations?

rarefluid: Something like that. The idea is to have a sorting algorithm that scales and performs well when you have almost correctly sorted data already.

straight insertion sort is great.

*giggles*

or just do a straight radix sort for guaranteed linear performance. or go all ps1 and use ordering tables! or some of the other umpteen algorithms that are linear-time for already sorted data!

straight insertion with binary search?

Or, don't bother with sorting at all. Call it art.

I support Doom's suggestion. Hide your laziness by calling it design, that's what all the elites does.

that's known as the Nosfesort ;)

I miss this thread :(

a-b-c-d-e-f-g-h-i-buffer... buffer that's it...

I'm at it again. :)

I added perspective-correct texture mapping to the renderer and ran into this strange problem that I interpolated u/z, v/z and 1/z correctly, but still had affine mapping. The problem was that I divided z/w in the perspective transformation step, and thus got values that weren't really different. That screwed up the interpolation because of precision.

I re-read rygs reply above... To clarify: In the perspective-division step I'd do:

wTemp = w;
w = 1/z;
x /= wTemp ; y /= wTemp ; z /= wTemp ;

and then pass the vertex on?

You should really interpolate u/w, v/w and 1/w, not z. And I don't see why you assign z to w...

"and not z" = "and not the z counter-parts"

...if you're doing it right, it actually works... ;)
Thanks kusma!

I got a new idea for a GBA occlusion culling algorithm loosely based on Triage Masks after reading through this. My renderer uses the halfspace approach with 8x8 tiles. In 240x160 it get 600 tiles:

- sort front to back
- split polygons if intersecting
- set up:
unsigned char tiles[600]; //contains tile information. init to 0. 0-253 == tile semi-filled. look up in masks-array, 254 == tile empty. 255 = tile completely filled.
unsigned char maskIndex = 0; //next number in masking array.
int64_t masks[254]; //1Bpp 8x8 mask array for storing pixel masks.
- clear tiles array to 254 (all tiles empty)
- when rendering a tile, first check if:
already filled --> skip
still empty --> just render
semi-filled --> get mask, render only pixels not covered already
- after rendering, write to tiles and mask array:
if now completely filled, grab last tile mask and insert it into this position. adjust entry in tiles array. write 255 to tile array
if now semi-filled, and mask in array with mask of pixels written. insert into mask array if not in it already.

Theoretically this should create zero overdraw and checks should be quite fast. There should be enough masks for semi-filled tiles (~40%) available.

It can't handle transparent surfaces though. Any hints on how transparent surfaces can be handled without a z-Buffer? I know I could just use painters algorithm, but some form of occlusion culling would be nice...

uhm. again:

ah. fuck it.