hi, i need your valuable opinions, i want to improve a environment algorithm : here is my algorithm idea : there are many boxes one within the other, and calculating according to camera position, direction and up. Calculate starts with biggest box (black one in the picture), *if the biggest box completely in the camera borders, its child boxes are not gonna claculate *if the biggest box completely out side of the camera borders, its child boxes are not gonna claculate *if the biggest boxes half part is in the camera borders, its child boxes are gonna calculate. and this 3 operation will be for each calculating boxes (one within the other) finally red marked boxes(in the second picture) triangles are gonna draw note:every triangles are gonna related own little box in the "map file" so there isnt gonna also calculating for triangles maybe i can use sphere (not boxes) because they have just one vertex (middle of the center) any different idea or already existing algorithm

You have invented the OctTree, a well known algoritm. =)

Google around for the algorithm implementation; but it is exactly as you describe.

-me

i wish people think that i'm a algorithm thief :(
anyway the best method is this, is there any different idea for "living triangle"

and sphere method is better right?

sorry i'm an "English Language Killer" :)

<
i wish people DONT think that i'm a algorithm thief :(
anyway the best method is this, is there any different idea for "living triangle"

and sphere method is better right?
>

Quote:Original post by ibr_ozdemir
and sphere method is better right?

No, because spheres do not tessellate. With spheres you either have overlap or you have gaps. OctTrees are always hierarchical rectangular shapes. You can test spheres against the tree but the tree should be represented rectangularly.

Other ideas for spatial partitioning are:
BSPTrees
QuadTrees (a 2D version of OctTree)
Portals (often used in conjunction with other things)

Read the Articles & Resources section of this site. There are many algorithms discussed.

-me

...and I'll toss in k-d trees... ;)

There are a large number of variables that go into spatial structure management.

Can you talk a bit about your environment requirements? How static is it? Does it have to be automatic, or can humans provide 'hints'? Are you concerned only with frustrum culling, or do you need other queries? Do your results (I assume polies?) need to be sorted, or or are you trying to cull batches of geometry?

I'd like to second the suggestion for looking at how kd trees fit your needs; they've fit ours very well.

i think i'm gonna do(if i can) differents calculates for differents states
for example:
*for static meshes (example whole map), its gonna one octree
*for dynamic objects, an octree that combined with object and the octree have objects rotation and approximate objects size

i can also use octree method for "progressive mesh" for my models right?

Yes, all the static geometry usually goes into one octtree, and dynamic objects can have their own bounding volumes. For dynamic objects, it could be better to use OBB (oriented bounding box) trees or sphere trees.

The geometry for collision detection is usually simpler than the geometry for rendering. For collision detection, an arm might just be one box. For rendering, the arm might have a more detailed model.