Archived

This topic is now archived and is closed to further replies.

Splitting poly's effectively in an octree

This topic is 5576 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Splitting polygons effectively in an octree Hi guys I’m looking for a way to split my polygons in my octree more effectively currently when I draw my nodes in my octree I get a little overdraw, this doesn’t hurt the framerate but it will be nice if I can split my polygons more effectively Here is how I do it at this stage I pass 3 points (single face) to my function and this function checks if at least 2 of the 3 points is in the node (node bound box), if so return true. if( (point[0].x >= (m_vCenter.x - width) && (point[0].x <= (m_vCenter.x + width))) && (point[0].y >= (m_vCenter.y - width) && (point[0].y <= (m_vCenter.y + width))) && (point[0].z >= (m_vCenter.z - width) && (point[0].z <= (m_vCenter.z + width))) && (point[1].x >= (m_vCenter.x - width) && (point[1].x <= (m_vCenter.x + width))) && (point[1].y >= (m_vCenter.y - width) && (point[1].y <= (m_vCenter.y + width))) && (point[1].z >= (m_vCenter.z - width) && (point[1].z <= (m_vCenter.z + width))) || (point[2].x >= (m_vCenter.x - width) && (point[2].x <= (m_vCenter.x + width))) && (point[2].y >= (m_vCenter.y - width) && (point[2].y <= (m_vCenter.y + width))) && (point[2].z >= (m_vCenter.z - width) && (point[2].z <= (m_vCenter.z + width)))) return true; return false; 'm_vCenter' is just the center vertex of my node and 'width' is the length to the side of the cube [edited by - Vlade0000 on September 8, 2002 8:36:23 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I wouldn''t encourage splitting the polygons. I did this once and in most cases you get double the amount of polygons per-node, not very nice.

Just put up with the relatively minimal overdraw... it won''t bite you.

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
I wouldn''t encourage splitting the polygons. I did this once and in most cases you get double the amount of polygons per-node, not very nice.

Just put up with the relatively minimal overdraw... it won''t bite you.


depends on the depth of the tree. If the tree is deep, dont split the poly''s. If not , split the poly''s. I found that rendering polygons slow down by the number of polygons, and not necessarily the size or the number of overlapping polygons.

Share this post


Link to post
Share on other sites
I''ve suggested this before, and implemented it myself in a dynamic oct-tree for a space shooter (where you can''t split a ship in two ) - simply store the distances that objects extend over the boundries of each node...
and set the parent nodes to the maximums of these (all the way up the tree).
Then when getting data from the tree, do your calculations with these values taken into account.

It increases memory usage a bit, but not much (surprisingly). And it''d be a lot less memory useage than splitting.

<-- smile :-)

Share this post


Link to post
Share on other sites
Ok...try this...

* When a node is created with a given size, expand the node bounding box by a small value (node_overlap_size) and store this bounding box as a second bound volume. Now iterate over all triangles and check for intersection with the bounding boxes as described below.
* If the triangle lies completely inside the original node bounding box, add this triangle to the node.
* If the triangle lies partially inside the original node bounding box, then check this triangle against the expanded node bounding box.
* If the triangle lies completely inside the expanded node bounding box, add this triangle to the node.
* Else if the triangle lies partially inside the expanded node bounding box, then split this triangle against the *original* bounding box and add the triangles inside the original bounding box to the node.
* While writing to the compiled tree, save only the original node bounding box.


I''m using this method for my octree, it reduces the overdraw and have optimum poly splits while compiling...the actual number of splits greatly depends on the nature of the level though. The parameter node_overlap_size should be adjusted so as to get optimum number of splits and tree depth.

I would like to hear from others who have implemented an Octree with poly splits and the specific techniques used to reduce the poly splits and overdraw.

Hope this helps!

Share this post


Link to post
Share on other sites
thanx aanand_420 and all the others

for the nature of my demo i require to split my polygons, i''m making an RollCage clone and i expect my tracks to be around 35 - 40000 faces, wouldn''t want to draw all those faces each frame hehe

i like the idea of the ''bound box overlap'' i''ll go try this - and its no hassle to implement

i am going to use my octree for collision detection as well, that is one of the main reasons that i want to split my polygons more effectively


thanx for all the help guys


http://www.freewebz.com/plastic/

Share this post


Link to post
Share on other sites