[Solved]: What is the difference between a R-tree and a BVH?

Problem Detail: 

I've just read about R-Trees:

The key idea of the data structure is to group nearby objects and represent them with their minimum bounding rectangle in the next higher level of the tree; the "R" in R-tree is for rectangle.

This seems to be a Bounding Volume Hierarchy (BVH) with axis-aligned bounding boxes (AABBs):

A bounding volume hierarchy (BVH) is a tree structure on a set of geometric objects. All geometric objects are wrapped in bounding volumes that form the leaf nodes of the tree. These nodes are then grouped as small sets and enclosed within larger bounding volumes. These, in turn, are also grouped and enclosed within other larger bounding volumes in a recursive fashion, eventually resulting in a tree structure with a single bounding volume at the top of the tree.

[...]

One of the most commonly used bounding volumes is an axis-aligned minimum bounding box.

Both allow overlapping nodes.

I've learned about BVHs in a Computer Graphics lecture and about R-trees by a professor who is mainly working on databases. So it might be that different communities developed the same datastructure independently.

Is there any difference between R-Trees and BVHs?

Asked By : Martin Thoma

Answered By : emab

Note that we want to be able to retrieve, for any query range, the points that are inside, or sometimes the points that are closest to that query range. That's why a bounding-volume hierarchy is useful.

However, bounding-volume hierarchy is a very general notion. When designing a bounding-volume hierarchy data structure in practice, it is extremely important to decide what kind of bounding volumes to use. The bounding volume can be any geometric shape: circle, hexagon, square, trangle or rectangle. It is important to keep this bounding volume very simple (we want it to be easy to store, rather than a complicated geometrical shape) and easy to fit other objects in (we don't want to waste a lot of free space in the bounding volume, as it can cause exhaustive search.

Quote from [1],

Below, I will first explain what a bounding-volume hierarchy is and how it is used. After that, I will explain what issues have to be addressed when designing a bounding-volume hierarchy. I will then focus on a particular class of bounding volume hierarchies, namely R-trees, and give an overview of our results on Rtrees.

R-tree is a class of BVH data structures that uses rectangles as bounding-volume. Rectangles are easy to store and they can cover other shapes easily. It is noted that R-tree is not the only class of BVH and there are other BVHs proposed using different shapes. Even among R-trees, there is a variety.

This data structure is important for different communities: computer graphics, computational geometry, database and others. All of them need to deal with situations where they need to query a set of geometrical objects (or vectors).

[1] Herman Johannes Haverkort, Results on geometric networks and data structures, 2004.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56337

 Ask a Question

 Download Related Notes/Documents