Sign in to follow this  
Saeed.Masoumi

The problem of begining to create OCTREE

Recommended Posts

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

[img]http://www.4freeimagehost.com/resized/2449ca32a256.jpg[/img]

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
coderchris    304
Read about quadtree first: [url="http://en.wikipedia.org/wiki/Quadtree"]http://en.wikipedia.org/wiki/Quadtree[/url]

The octree is the same data structure, but has one more dimension.

Though I'm not sure what you plan to use an octree for with that model?

Share this post


Link to post
Share on other sites
Saeed.Masoumi    100
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.

[img]http://www.4freeimagehost.com/resized/8cf1d683dab0.jpg[/img]


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
jyk    2094
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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this