Using an R+ tree or R* tree as a scene manager

Anything and everything that's related to OGRE or the wider graphics field that doesn't fit into the other forums.
Post Reply
grin.k1tt3n
Gnoblar
Posts: 2
Joined: Thu Jun 09, 2005 6:38 am

Using an R+ tree or R* tree as a scene manager

Post by grin.k1tt3n »

Anyone know why this has not been done? I haven't seen any discussion about it.

Was wondering if there was something inherently bad in using these trees for scene management/picking.

Bill
Gremlin
Posts: 167
Joined: Sun Sep 26, 2004 11:50 pm
Location: Arkansas

Post by Bill »

I was wondering the same thing. I just wrote a little Hilbert R tree bulk loader api to support drawing some online maps. It was a huge performance boost (5 secs to 0.02 secs). For less than 50 lines of code that's pretty great. I don't see why it wouldn't work for scene managment.

User avatar
Kentamanos
Minaton
Posts: 980
Joined: Sat Aug 07, 2004 12:08 am
Location: Dallas, TX

Post by Kentamanos »

I wasnt' familiar with them, but I quickly read a bit about them.

Can you explain a situation in which an R-tree is better than an octree?

Bill
Gremlin
Posts: 167
Joined: Sun Sep 26, 2004 11:50 pm
Location: Arkansas

Post by Bill »

Kentamanos wrote:Can you explain a situation in which an R-tree is better than an octree?
I'm no expert, but I'll take a stab at this.

Octrees work best when the stuff in the octree is distributed evenly across the space being indexed. However, that usually isn't the case. Stuff tends to be more in one place than another (e.g. there are more roads in the city then the country). In that case the octree is skewed and provides suboptimal performance. However where the octree is skewed you can build a balanced R-Tree. That means you can find your data with fewer node visits, which is really important when your data is really large and on the disk. So on real data R-trees tend to be faster.

On the other hand, in my experience, R-trees can yield more false positives. That's because R-trees search on the minimum bounding rectangle. So if the shape you're searching agianst is a large diamond (square rotated 45 degrees) 50% of the MBR will not be in the diamond and you will get a lot of hits not in your search area. While the quad/octree will compare objects down to the minimum cell size of the index and yield less false positives.

So it depends on the distribution of your data, the shape of the search area, and on how you can tolerate false positives.




Of course I could be completely wrong.

grin.k1tt3n
Gnoblar
Posts: 2
Joined: Thu Jun 09, 2005 6:38 am

Post by grin.k1tt3n »

Thanks for your comments

Post Reply