Presently I build an oct tree data structure in my game so that I can use it for rendering and collision detection optimisation. Works well. I chose an oct tree because there will be dynamic, movable objects like doors and platforms in most of the levels, so I didn't want to have to construct a bsp tree every time a polygon in my scene changed. However, I am now faced with the predicament of having to render some alpha blended and non-alpha blended polygons, which in turn means I need to order them back-to-front. A BSP tree has a very elegant way of doing this, but the oct tree has no way to do this ingherently in its structure. I considered using a bsp tree but what happens if i want to add/remove stuff in real time? I cant rebuild the bsp every time as it would be inefficient.so how do most games/simulations support both dynamic scene data as well as blended polygons? Any thoughts woulds be helpful on how I should a)structure my scene data b)do efficient back to front ordering for alpha blending Thank you, --Neko

I was thinking about how I might go about this, maybe the steps would be:

1. Traverse the octree given the view frustum and obtain the list of leaves in the octree that werent culled
2. From the list of leaves obtained in (1), cull all of the polys in these leaves thgat arent in the view frustum into a polygon list
3. From the list of polygons obtained in (2), for each polygon, check the distance from the cameras location to the plane of the polygon. sort of all of these polygons using a radix sort from furthest to nearest. Discard any negative distance polygons since they are not visible from the camera (neg. means we are behind the polygons plane)

Thoughts? Is this a good way to do it? Or maybe it wuld be better to use a hybrid oct/bsp tree approach? I'd appreciate any feedback

--N

Hi.

This is just a thought, wich means that, since it's a though from me, there's a high percentage of it being wrong...

In the nodes of your octree, do you keep any information about it's neighbour nodes? If so... i think (not shure) that you can skip the sort phase... just build the list of leaves in the order of closest to the viewer position first. And then render them from last to front....

wolverine:

I think I sort of understand what you mean by storing neighboring information...you are saying that if I traverse the leaves in order I will get back the already sorted list. But One part I'm not sure on (maybe you or someone else can clear this up) is that although the leaves wuill be sorted back to front, what about the polygons in the leaves? so for example lets say I have 7 leaves in my oct tree after it's built, A-G Now lets say I do my get leaves traversal with the current frustum which returns {A, D, F} (F is furthest leaf from viewer, A is the leaf the view is in). Well, thats good but lets say A has 200 polys in it, D has 690 polys in it, F has 314 polys in it I know that all of D's 690 polys are in front of F's 314 polyus, but of I dont know the back to front within each group. At least I dont think I do. Thoughts? Is this explanation of the problem clear enough?

Yes... you got the idea i was saying right :). That helps in knowing that the correct processing order would be F-D-A in your example.

Unfortunately, that would only work on the cell level. Once we go inside the cell, we're kind of stuck, like you said. Inside of one cell, there's no direct way of knowing the correct render order, because it depends on the viewers position....
Perhaps by storing some sort of infomation per cell to help on deciding the order on the polygon level for that cell. But that can be sort of tricky for dynamic scenes.

ok, so it sounds like maybe what I should do is in the last step, where I have each leaf, find the distance from the viewers position to the plane of each polygon, then do a fast sort on them. Thanks for your help W! :)

--N