Archived

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

ThaUnknownProgga

Octrees, well really just a cubes question

Recommended Posts

I want to implement an octree because they look really useful. I''m having trouble figuring out how to define this whole cube thing. How can I define a cube such that it can be subdivided and all that recursively... Basically, can someone show me some code for proper octree cube stuff?

Share this post


Link to post
Share on other sites
Nate    122
Try this URL out http://silcon.silcon.com/~brink/papers/octrees.html

Nate Miller
http://nate.scuzz.yet

Share this post


Link to post
Share on other sites
The link didn''t really help me much. I understand the the concept of it all, i just don''t understand how to actually code it. So, do i first write a cubelet structure which contains 8 vertices and pointers to 8 children? If this is so, when i create the children i have to set their vertices. won''t this require 3 divisions per child creation, since i have to split the original cube''s edges in half? (3 being split the x distance, the y distance, and the z distance) That seems pretty bad, so is their a better way?

Now, i understand that if i''m doing this I have to stop recursing once i reach a certain point. If i''m using regular polygonal data, i can stop when a certain number of faces are in the cube. But if i''m doing something like the marching cubes algorithm, when would i stop then?

And since quadtrees are very similar to octrees, i thought i''d ask a question on them too: If i use a quadtree for a landscape, I don''t have to keep recursing. Do i just get it down to a certain size, check for visibility and render?

thanks in advance, and thanks right now to you nate!

Share this post


Link to post
Share on other sites
Nate    122
Here is another URL that might help : http://www.flipcode.com/tfiles/kurt.shtml. I am playing around with octress right now, hopefully I will have a demo sometime in the near future. Your octree structure should look something like this :

struct octreenode
{
octreenode *children[8];
vec3_t min;
vec3_t max;
}

That structure is incomplete, but it gives you the gist of what is going on. The children part of the structure are all of that cubes children, they are generated by subdividing the current cube into 8 smaller cubes. The subdivision is *really* simple, try working it out on paper. At the first URL I pasted there is source in his download section for an octree demo, I just took a look at it and it should help you out.

Nate Miller
http://nate.scuzzy.net

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
well yes you have to do 3 divisions. what''s the big deal? the hardest part is dividing the polys and that''s easy since the divisions are axis-aligned.
and youre sorely mistaken ThaUnknownProgga.. the whole point of the octree is to pre-calculate everything. you don''t do the cube/poly divisions during runtime, you store the bounding boxes for each leaf/node (or whatever you want to call them).
i think that''s where you were hung up, you thought you did the subdivision as you were rendering which you don''t. that would be slower than a car with no wheels!
the beauty of it is that upon traversing down the tree during rendering.. if you determine a leaf is not visible then all of it''s children aren''t either no matter what. gotta love the simple elagance of spatial subdivision algos.

Share this post


Link to post
Share on other sites