pouët.net

Go to bottom

bsp tree 3d subdivision

category: general [glöplog]
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?
added on the 2009-02-11 13:30:16 by iq iq
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.
added on the 2009-02-11 13:54:42 by gopher gopher
so, what is the solution? Is it possible to make the painter's algorithm robust (without global data structures)?
added on the 2009-02-11 14:13:01 by iq iq
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

added on the 2009-02-11 14:22:39 by gopher gopher
smash wrote about GPU Z buffer management:
Quote:
probably the reason zfighting got less of a problem was that we got 24 bit z instead of 16 .. :)


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.

added on the 2009-02-11 14:25:50 by krabob krabob
@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
added on the 2009-02-11 14:53:56 by mrdoob mrdoob
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.
added on the 2009-02-11 15:27:46 by ryg ryg
krabob:
Quote:

- If you got "Z fighting" with 2 polygons inside a tile, you can manage the polygon/polygon space intersection there, draw the polygons that complete the tiles, and do not process any pixel 2 times !

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?
added on the 2009-02-11 15:35:57 by raer raer
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
added on the 2009-02-11 16:16:57 by krabob krabob
@Krabob: Do you mean something like this?

http://lab.zupko.info/quadtree/
http://blog.zupko.info/?p=177
added on the 2009-02-11 16:31:26 by mrdoob mrdoob
ryg
Quote:
krabob: they are "antialiased" because z-testing is done at subpixel resolution when multisampling is enabled.


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 ?
added on the 2009-02-11 16:32:55 by krabob krabob
Quote:
@Krabob: Do you mean something like this?


No, I mean "this" managed at the 2D level on screen coordinates, after projection, not before at 3D level.
added on the 2009-02-11 16:34:49 by krabob krabob
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.
added on the 2009-02-11 16:40:37 by krabob krabob
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. :)
added on the 2009-02-11 16:42:43 by smash smash
How would you sort polys by tiles?
added on the 2009-02-11 16:58:19 by raer raer
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...
added on the 2009-02-11 17:04:20 by krabob krabob
Quote:
How would you sort polys by tiles?

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...
added on the 2009-02-11 17:23:08 by krabob krabob
Sound nice. Thanks for the explanations.
added on the 2009-02-11 17:27:23 by raer raer
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.
added on the 2009-02-11 17:30:15 by ryg ryg
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.
added on the 2009-02-11 17:50:47 by krabob krabob
trace: do you know how Papervision does it?
added on the 2009-02-11 19:52:20 by texel texel
Quote:
if you have non intersecting faces sorting is possible, but not via center point or corner points criteria alone


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

BB Image

(You can do a similar thing with three triangles)
added on the 2009-02-11 20:02:16 by doomdoom doomdoom
@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.
added on the 2009-02-11 20:33:31 by mrdoob mrdoob
Anyway, I guess I'll end up decompiling Alternativa's engine and try to implement it on my engine.
added on the 2009-02-11 20:34:18 by mrdoob mrdoob
doom: right
i may correct myself then :)

if you have non intersecting and non mutual overlapping faces, sorting is possible, otherwise not
added on the 2009-02-12 00:02:43 by gopher gopher

login

Go to top