Advertisement Jump to content
Sign in to follow this  

The problem of begining to create OCTREE

This topic is 2835 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

Hello everyone.
As you can see in this picture i could get coordinates of polygons of model.


I'm going to create Octree but i don't know how to start.I'm using XNA framework in C#.My model has just a single mesh.I can access to it's boundingbox so its going to be my OCTree's root node now i want to know how to create children of root node?Im not interested in knowing about any codes just i want to know about the methods .
Thanks a lot.

Share this post

Link to post
Share on other sites
Thanks for your reply.
I'm going to send a ray from someplace to my model if it has been intersected with a triangle i want to change triangle's color.See picture please.


Can u help me with an algorithm to show me how can i create a simple OCTree for this single Mesh?Cause i think this model doesn't need a recursive algorithm.if you help me about this then i will change your algorithm for doing such a job for other complicated models.
Thanks a lot.

Share this post

Link to post
Share on other sites
There's a few different ways you can build an octree:

- Store objects in the 'smallest' node that fully contains them
- Split objects to node boundaries
- Push objects all the way down to the leaves and allow multiple leaves to reference the same object
- Use a 'loose' octree
- Maybe some other options I'm not thinking of

You'll also need to settle on the termination criterion or criteria (e.g. maximum depth, minimum node size, maximum objects referenced by a single node, etc.).

For the purpose of ray casting against a mesh, I'd probably go for option 1 or option 3. The process is recursive (but can be expressed iteratively, e.g. using a stack). For option 3, it might look something like this (off the top of my head, so no guarantee of correctness):

1. Compute bounding box of mesh
2. Compute minimum containing cube for bounding box (this will be the root node)
3. Build list of all faces
4. Split cube into 8 sub-cubes (these will be the child nodes of the current node)
5. Build 8 face lists (one for each child node) from face list (a single face may appear in more than one list)
6. Go to 4 (recursively) with each of the sub-lists and each of the child nodes (be sure to terminate when the termination criteria are reached)

That's not a very detailed description, but maybe it'll give you the general idea. There's also a variety of ways the data can be organized. For example, you can create the nodes/leaves dynamically and allow each node to reference its children directly. Or, you can use a 'flat' array and store all the nodes contiguously.

As for the actual ray casting, if you want to go for maximum efficiency, you can share intermediate results between triangles and re-use them where possible; however, this would likely not be worth the trouble (especially if the total number of triangles returned by the broad phase is small).

Of more importance is robustness. With a naive implementation, it's at least theoretically possible for rays to 'fall between the cracks' between adjacent triangles. In general, avoiding this problem involves being sure that the various intermediate values are computed in a uniform way between triangles. (That said, depending on your needs, a 'naive' implementation might be sufficient.)

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using, you agree to our community Guidelines, Terms of Use, and Privacy Policy. is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!