pouët.net

Here I go once again with a question for my 3d engine adventures.

First thing, take a look at this:

http://mrdoob.com/lab/pv3d/ball_ao/

As you'll see, there are some z-sorting issues. This is because with Actionscript you can only draw polygons using painters algo. It's basically software rendering, so there is no OpenGL taking care of the polygon intersections.

As far as I know, the best solution for this is use bsp tree spatial subdivision (for static objects). That will increase considerably the amount of polygons, but, as the polygons get sliced by the others, they should z-sort perfectly.

Here I have two options...

First one is to find a script that could do this for me, for blender preferably. But I can't seem to find anything.

The other option is to wrap my mind about it and implement it on my engine, which sounds scary. Although it would let reset the bsp tree at any point.

Any tips?

mrdoob is the master of puppets! thumb up

trace, if the polygons does not intersect, do you algorthm work fine?

If that is the case, I suggest you to process the faces before sending to actionscript. If it is an off-line precalc, it doesn't matter if it is slow or not, so it doesn't matter if you use bsp or not...

Doing it in actionscript without bsp would be very slow for a big number of faces (it would be even for native code for big meshes), and implementing a bsp for that sounds like a long process...

I would just try it offline, with a brute force method, and then I will do slowly the algorithm in action script with a bsp... but I just feel pain to think in doing the second part :P

Well, you can't precompute any sort order in this case, as the object is rotating : the order in which you should draw the faces changes constantly...

If you're going to stick with this rotating object and are not looking for a general solution, you could precompute the face order based on the rotation angle... And then store the changes only...

Also, I'm having the impression that your object can be sorted without going through anything complicated. Just drawing each tower level by level in camera view back to front order should work... Now, of course, if all you have is a "collection of triangles", then you'll have to do it the hard way ;)

I think I didn't explain myself very well. What I'm asking for is if anyone has had any experience subdividing a mesh using bsptree subdivision. Whether if it's using a 3d package script found on the net, or implementing the code on their engine.

The example I show was just that, an example. I'm looking for a solution for any mesh, something to subdivide it and then be able to use simple painter z-sorting (without pixel access, just polygon).

It looks like the object is closed and there are no intersections, so your sorting algorithm is probably not working correctly.

No slow...

But no, sorry.

Too slow :)

wtf?

creating any bsp isnt that hard.
the hard part is to make a well balanced tree so that the traversal will be fast.

basically you need to do the following:

1. create a bsp node
2. select any face in your mesh and extract the plane equation from it
3. use dot products to determine which of the remaining faces are on which side of the plane and store them in the respective branch of the node. if you encounter faces intersectiong your plane you need to split them and sort in each part accordingly
4. go to 1. until a maximum tree depth is reached or no faces left to sort in

this scheme works no matter which faces you choose as split planes while building the tree. but obviously its better to choose planes which result in ~ the same amount of faces placed in each following branch

to draw the stuff you simply process the tree and draw the faces in backside nodes first, then the face(s) in the current node, then the faces in the frontside node (relative to your viewpoint)

gopher: I wouldn't say well balanced - as a tree it can have any form without affecting performance. The thing is to minimize the number of splits (and thereby resulting polygons), which is a NPC problem.

gopher: I wouldn't say well balanced - as a tree it can have any form without affecting performance. The thing is to minimize the number of splits (and thereby resulting polygons), which is a NPC problem.

wtf, pretty sure I only submitted once..

psycho: :)

i think balancing the tree will affect performance, since you can reject large chunks of nodes/faces quite easily with less iterations in the tree (assuming you are located inside the bsp volume ).

for the given case beeing outside the volume and always needing to traverse all nodes anyway i would second your point.

code a software rendering engine using Z buffer, or even better, a tile accelerator software engine, and manage the Z buffer at tile corners, then special Z management inside tiles, if needed.

@gopher: Yes, the idea goes along these lines, but in fact I don't think the resulting tree is actually needed, what it's needed in this case is to split the planes of the mesh so the resulting mesh doesn't have any z-sorting problem like on the example.

@Krabob: Pixel access with Actionscript is very slow. So no.

bsp trees were used to sort triangles in back to front quickly.

What you need trace has nothing to do with bsp-trees a priori. What you need is to detect triangle to triangle intersections in your mesh and solve them by splitting the tris into new tris. Once no polygon intersects any other polygon in the mesh, you z-based sorting should work and the simple painter's algorithm will give you the correct pop-free image.

Yeah, that's it. But I though it had a relation to bsp tree subdivision as it's more or less how bsp works, isn't it?

I may recode some software thingies these times, and I'm really digging software "tile accelerators": I'm used with software engines with no zbuffers (amiga experience), I know the test per pixel and buffer access costs,
but software "tile accelerators" will cut down drawing speed a lot:

if you got many polygon that asks to be rendered on one tile and finnaly the closest fill the whole tile, you don't have to render the other ones first.

You test Z for the corners, then in most cases, you just do classic interpolation inside the tile, with no Z tests and no per pixel Z buffer !

- 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 !

I guess that's what the GPU are doing, and it explains why the Z-fighting cut - lines artifact radically changed since around 2002.

In a demo, you could precalc a map, indexed on time, saying which lines intersect to speed up things. I think this was suggested tp me be by Blazer/Andromeda a million years ago. For free rotation, a map indexed on some angular representation of your object would do it -- but the cool thing is to think about the triangulation this induces on the "angle space" !

@Krabob: I think you're talking about medium-size resolutions. Will your method work fast at 1920x1200? Also, bear in mind that in actionscript you use the flash api to draw the triangles, you have no access to the pixels. Well, you do, but it's very slow. Doing a pixel based raster is fine for 320x200 in flash, but not fot 1920x1200, so you depend of flash graphics api.

@Iq: Any idea of where to start looking for how to split the triangles?

iq: pure z-sorting wont help even with intersection free triangles

simple example: 2 parallel planes quite close to each other but slightly offset (assume z direction and viewing direction going up)

1 ------
------ 2

2
/
/ /
/ /
/
1

draw order for painters algorithm needs to be 1,2 for case one and 1,2 for case two.
now zsorting would give 1,2 for case one, but 2,1 for case two (which is wrong).

damn reformating ...

-------------oooo
oooo-------------

oooooooo/
ooooooo/o
ooo/oo/oo
oo/oo/ooo
o/ooooooo
/oooooooo

trace, bsp tress are just barely related to your problem imho.

It's not that you didn't manage to explain what your problem was (Texel got it too -the three of us are spaniards, hm..- and gave the right answer). Problem is that you already proposed a (imho wrong) bsp tree solution in the title of the thread, and therefore the answers you got were into instructing you on bsp trees, and not in solving your problem.

krabob: most gpus arent doing tile-based rendering, they just raster everything, butthey use a hierarchical / tile based representation of z for zcull.
probably the reason zfighting got less of a problem was that we got 24 bit z instead of 16 .. :)