Jump to content
  • Advertisement
Sign in to follow this  
ibr_ozdemir

any algorthim idea?

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

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 this post


Link to post
Share on other sites
Advertisement
You have invented the OctTree, a well known algoritm. =)

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

-me

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
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

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!