# any algorthim idea?

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

## Recommended Posts

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

##### Share on other sites
You have invented the OctTree, a well known algoritm. =)

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

-me

##### Share on other sites
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?

##### Share on other sites
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?
>

##### Share on other sites
Quote:
 Original post by ibr_ozdemirand 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

##### Share on other sites
...and I'll toss in k-d trees... ;)

##### Share on other sites
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.

##### Share on other sites
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?

##### Share on other sites
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.

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633726
• Total Posts
3013570
×