🔒 Locked

Octree construction / clipping question

Started by eli_pulsifer Jan 25, 2000 at 1:00 PM 4 replies 1.3k views

Original Post

Jan 25, 2000 at 1:00 PM

Ok, if you have the time, this is my question. My engine is based on an Octree data structure. All polygons in my engine are triangles and they are inserted into the tree based on their center point. Currently, I am clipping every polygon in the tree to the Octree node bounding boxes. This seems to be a waste of time both in the construction of the tree and when rendering. Creating the tree causes the clipping of thousands of polygons, re triangulation of the clipped polygons and finally rendering of the additional polygons. I am toying with the idea of not clipping the polygons. Instead, if a polygon protrudes into another Octree node a link in that node back to the polygon in the node that actually contains the polygon. I would have to add a rendered flag to the polygons to make sure they don’t get rendered more than once, but I think this would be more efficient than my current method. Does anyone have any comments / suggestions on this?

logistix

Jan 25, 2000 at 5:41 PM

How small are your node octs?

That''s where you should adjust to get a low polycount. Also making the nodes too small will involve alot of other calculations along the way and could get to the point when you''re slower than just using NO structure.

eli_pulsifer

Jan 25, 2000 at 5:58 PM

Ok,
I can understand that, but then how do you sort the polygons in each node? Mini BSP''s? Maybe I don''t really need perfect front to back traversal. I guess I could modify by beam tree so it would not require perfect front to back traversal. This of course will slow down my visibility code however. I guess its just a question of which will give the best performance.

logistix

Jan 25, 2000 at 8:25 PM

Put the polys for each oct in a linked list and sort by Z. That is assuming you''re not using a hardware Z-buffer, are doing your own transforms, etc.

I apoligize if your doing a sofware renderer, but on the project I''m working on (using a quadtree) using a hardware Z buffer took off < 10% the framerate compared to doing absolutely nothing. Once you add all the algos and stuff it''s questionable as to how much better you can do than a hardware Z-buffer.

Still, quad/octrees rule when it comes to doing collision detection with the world.

eli_pulsifer

Jan 26, 2000 at 6:00 PM

Ok, I have a problem with:
"Put the polys for each oct in a linked list and sort by Z."

How is one supposed to sort by z-order? I don’t think this is possible. Given the fact that front to back z-order depends on the position and the direction the eye is looking. All the data in the octree is stored and sorted by world space coordinates, therefore sorting by world Z would be useless. There is no way sorting each oct that is visible every frame would work. In order to get front to back traversal relative to the eye, I need to use some type of data structure that provides a mechanism to traverse front to back from an arbitrary position in an arbitrary direction. This is the reason I'm using an Octree in the first place, among other reasons. So, I guess I'm back to the question, how do I sort the polys in each node. My only viable solution thus far is mini BSP's.

Edited by - eli_pulsifer on 1/26/00 6:03:17 PM

logistix

Jan 26, 2000 at 6:08 PM

To do that, you need to transform each poly yourself. You basically send a matrix down (or up) the tree, dump the transformed polys into a temp list, and then sort that by Z and render.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.