pouët.net

ooops, and now gopher makes me think about the painters algo (although I don´t understand your acii art hehe). Trace, how are you sorting your tris? Based on they center point or how?

iq:
o is empty space
- and / specify the plane

case one:

plane 1
-------------oooo
oooo------------- plane 2

correct draw order 1,2
zsort result 1,2
-> ok

case 2 (rotated):

oooooooo/ plane 2
oooo/oo/o
ooo/oo/oo
oo/oo/ooo
o/oo/oooo
/oooooooo
plane 1

correct draw order 1,2
zsort result 2,1
-> wrong

and afaik its not important what criteria you use to zsort the faces, you can always construct cases where the sorting will yield wrong order.

so, what is the solution? Is it possible to make the painter's algorithm robust (without global data structures)?

as long as you really have intersecting faces i'd say NO

if you have non intersecting faces sorting is possible, but not via center point or corner points criteria alone. i guess you additionally need some kind of projection to the view plane and 2d intersection tests to make it robust. but that will easily kill your runtime performance.

so ... using painters algorithm i'd say there's no way around a global data structure like bsp trees if you want to have it perform at least a bit

smash wrote about GPU Z buffer management:


Actually, if you switch on the polygon border antialias, you will notice that the Z-fighting intersection lines *are* antialiased. To my mind, that can be possible only if those lines are created as vector lines by polygon subdivision, maybe by the Z tile manager.

Trace: I failed to explain you what i mean with "tile-accelerators" used for rendering/ and Z sorting management issue, but believe me, it would suit your need quite fine: it's not medium-size things, it's more like superscallar subdivision using 16x16 sized tiles, you do a first polygon rendering pass to manage the tiles in software, then, you 're just free to draw polygons in the tiles to render the final screen, and as I said, it allows to manage the Z problems the way you need.

@gopher: I guess that's exactly the problem I'm trying to avoid by splitting the intersecting.

This is where I got the "idea" from:

http://blog.alternativaplatform.com/ru/files/2007/12/bspdemo.swf
http://blog.alternativaplatform.com/en/2007/12/20/dynamic-bsp
http://docs.alternativaplatform.com/display/TDEN/BSP-Tree

krabob: they are "antialiased" because z-testing is done at subpixel resolution when multisampling is enabled. the reason z-testing artifacts look different now than they did a few years ago is that rasterization precision has increased notably. z-values used to be interpolated at about the same precision they were stored in, by now it's significantly higher. hence the "stippling" artifacts even in very "flat" areas that are facing the camera almost directly.

krabob:

Your tile approach sound nice. I was thinking of that too. As long as you test complete tiles this is nice, but what are you doing when some polygons occupy only some pixels of a tile and have no per-pixel z-Buffer?

ryg: thanks for the information. Clever.

answer to rare:
the more simple is to allows pixels to be written more than once for tiles where there are little polygons parts, and sort the Z order of those polys at the tile level.
- in pure software, maybe switching to a Z buffer logic "by tiles" when needed, which only need a Tile-sized Z buffer, not used each times.
- or subdivise the tiles in 4 recursively. :) ->nasty
- or something else

@Krabob: Do you mean something like this?

http://lab.zupko.info/quadtree/
http://blog.zupko.info/?p=177

ryg


But wait a minute... isn't antialias isupposed to affect only polygon border pixels, not the whole pixels inside a polygon ? (I may be wrong)
so why should z-test multisampling be enabled for borders that doesn't exist as vector, such as Z-fighting intersections ?

No, I mean "this" managed at the 2D level on screen coordinates, after projection, not before at 3D level.

I mean subdivide your 2D final screen with something like a 40x30 grid of tile, then do 2 rendering pass after projection, the first to set data for the tiles (you Z eliminate and sort polys by tiles), the second pass you do the real rendering according to the tiles data. Inside a tile, you can manage rendering a 2D way.

Notice It's close to render n x n ordered screens, but it allows to manage some clipping differently

Actually I call that tile accelerator because that's was the dreamcast PowerVR way and term.

krabob: its not really that complicated.. :) multisampling gives you e.g. a 4x sized buffer (for msaa4x). the z test is done per multi sample, but the shader is only run once. the samples are then written individually depending on if they passed z.
at the end of rendering the buffer is resolved to its proper size (the pixel size you specified) by averaging the samples together.

there are some things to improve the speed of this - like higher level z cull, and compression on the render target and z buffer.

have you got a screenshot of these "z fighting intersections" though, because maybe im thinking of something else. :)

How would you sort polys by tiles?

ok, I knew multisampling is used for antialias, but I only thought multisampling were only used then for polygon borders, not the pixels inside polygons (wtf ? antialias has no use inside the poly, there's already bilinear/mip to smooth rendering there) . No matter, GPU methods may vary also...

You mean how do you know a tile manage a poly part ?
It would look like a classic polygon rendering on a mini screen, where final pixels are the tiles, and you create new vertex for each on the grid corners. the subdivision of the polygon is what is usually done for screen rectangle clipping (intersect a X and Y plane at each tile border). then for each tile that cross the poly, push some data in the tile, the tiles would have a little stack of polygons . It would be nice to reuse the new vertex created at the corners or at intersections from a tile to another.

then keep the Z data for each new vertex, use it to manage Z sort at a tile level.... As I said; I dig it...

Sound nice. Thanks for the explanations.

only you don't know beforehand which pixels belong to the polygon border, since that depends on the results of the z and stencil tests. say you have two triangles that intersect. one of them will get cut along the plane of the other triangle, effectively turning into a quadriliteral. the new "extra edge" never exists as geometry and the rasterizer stage wouldn't know about it.

similarly, imagine a complex (non-flat) surface formed by a bunch of triangles - a heightfield for example. now you draw a quad at "water level" on top of everything. parts of the quad will be above the heightfield and parts will be below, and that pattern can get arbitrarily complex, yet it's all resolved while drawing the inside of one "simple" triangle.

Ok now I get it about the multisample z test and antialias. thanks ryg and smash. I was mystified by some old rendering algos that were using border detection to do it.

trace: do you know how Papervision does it?

Not without some clever clipping, though. This illustrates the problem:



(You can do a similar thing with three triangles)

@texel: Papervision doesn't do it... yet. Well, you can use that Octree thing I just posted, which you can check the sources if you want.

Anyway, I guess I'll end up decompiling Alternativa's engine and try to implement it on my engine.

doom: right
i may correct myself then :)

if you have non intersecting and non mutual overlapping faces, sorting is possible, otherwise not