Similarity Metrics for Bounding Volumes

by Mayur Patel

I was recently writing yet another bounding volume hierarchy.  As I usually do, I referred to my ACM SIGGRAPH 2007 poster, "Similarly Metrics for Bounding Volumes." Unfortunately, I found that the content of that poster is not available anywhere on the Internet.  Or, at least, I couldn't find it.

This blog post is a reconstitution of the content of the SIGGRAPH 2007 conference poster of the same title, assembled from the submission, supplementary materials and the poster itself. 

Introduction

Testing the similarity of bounding volumes is a common operation in geometry processing.  Often, the intersection or union of two bounding volumes is calculated as an intermediate step.  These intermediate volumes are then measured to produce a comparison metric.  Common metrics include distance, surface area, volume and overlap.

Here, we introduce new variations of these metrics, using a new intermediate calculation inspired by interval arithmetic.  We argue that the new technique offers better precision than calculating intersections or unions of bounding volumes because more detail is available over the entire range of inputs.

For example, imagine two boxes that animate from this relative position:

To this position:

The volume of the union of the bounding boxes clamps in the ranges where the larger volume contains the smaller one:

The Hausdorff distance metric would look similar to the volume of the union: it would clamp during the time that the larger box fully contains the smaller box.  Because of this, there isn’t much detailed information about “what is going on” during the time that the larger volume fully contains the smaller one.  

The volume of the intersection of the bounding volumes is even worse, in that it only provides information during the time that the volumes partially intersect.  When the larger contains the smaller, it clamps; and when the volumes do not intersect, it clamps:

While these measurements are sufficient to answer basic questions, they do not provide much fine detail over the entire range of the animation.  

New Methods

Regarding notation, we write a vector as $V$; its component in dimension $i$ is given with $v_i$.  An axis-aligned bounding box, $R_0$, has a minimum coordinate of $r_{0_{i-}}$ and a maximum coordinate of $r_{0_{i+}}$ in dimension $i$.

For our comparison metrics, we introduce two new vectors, $M$ and $N$, whose components are calculated as a function of two axis-aligned bounding boxes, $R_0$ and $R_1$:

$m_i$ = max( $r_{0_{i+}} - r_{1_{i-}}$, $r_{1_{i+}} - r_{0_{i-}}$ )

$n_i$ = min( $r_{0_{i+}} - r_{1_{i-}}$, $r_{1_{i+}} - r_{0_{i-}}$ )

These calculations are easily adapted for bounding spheres and other volume types.

Here is a visual which may help to illuminate how these measurements work.  In this case, we're showing the calculation in the vertical dimension:

Intuitively, $M$ varies with the edge length of the union between the two volumes.  When one volume fully contains the other; however, the edge length of the union would clamp to the larger of the volumes. With $M$, containment does not cause clamping; $M$ will continue to vary with the relative sizes and positions of the volumes.  This is why we say that $M$ has greater precision than the edge length of the union of the bounding volumes.

Similarly, $N$ varies with the edge length of the intersection of the two volumes.  As with $M$, containment does not cause $N$ to clamp.  Also, the components of $N$ do not clamp to zero when the inputs do not overlap.  Therefore, we say that $N$ has greater precision than the edge length of the intersection of the bounding volumes.

We are able to make several useful observations:

Edge Length Property: $( m_i + n_i ) = ( r_{0_{i+}} - r_{0_{i-}} ) + (  r_{1_{i+}} - r_{1_{i-}} )$

Overlap Property:  if $n_i < 0$ then $R_0$ and $R_1$ don’t overlap in dimension $i$.

Centers Property: if the intervals of $R_0$ and $R_1$ in dimension $i$ have equal midpoints, then $m_i = n_i$, otherwise $m_i > n_i$.

Volume Property: if both $R_0$ and $R_1$ have zero edge length and exist at the same coordinate in dimension $i$, then $m_i = 0$; otherwise $m_i > 0$.

New Metrics

From the properties listed in the previous section, it is clear that the corresponding components of $M$ and $N$ form intervals which describe the relative relationship between the input intervals.  To produce a scalar value suitable for comparison, these intervals must be collapsed.  We present several options:

Furthest (Minkowski) Distance Metric: $f_1(R_0, R_1, k) = (\sum_{i} {m_i}^k)^\frac{1}{k}$

Combined Surface Area Metric: $f_2(R_0, R_1) = \sum_{s}( \prod_{t \neq s} m_t )$

Combined Volume Metric: $f_3(R_0, R_1) = \prod_{i} m_i$

Shared Volume Metric: $f_4(R_0, R_1) = \sum_{i} n_i m_i$

Relative Proximity of Centers Metric: $f_5(R_0, R_1) = \sum_{i} \frac{n_i}{m_i + \epsilon}$ where $\epsilon$ is a very small positive value.

Absolute Proximity of Centers Metric: $f_6(R_0, R_1) = \sum_{i} n_i - m_i$

Below, we provide the graphs of several of the new metrics with respect to the animating boxes we used earlier.  Each metric has either a distinct maximum or a distinct minimum value.  At this time, the relative positioning of the two bounding volumes is “best.”  Furthermore, the metrics do not clamp in general, so they provide more detailed information about the relative positions and sizes of the two volumes across the entire range of time.

References

Aggarwal, C., et al. 2001. On the Surprising Behavior of Distance Metrics in High Dimensional Spaces. Proc. 8^th International Conference on Database Theory. 420-434.

Henrikson, Jeff. 1999. Completeness and Total Boundedness of the Hausdorff Metric. MIT Undergraduate Journal of Mathematics, 1. 69-80.

Levin, V. I. 2004. Ordering of Intervals and Optimization Problems with Interval Parameters. Cybernetics and Systems Analysis, 40, 3. 316-324.

Epilogue

In my testing, the Furthest Distance Metric presented in this post performs very well in R-trees, X-trees and similar spatial data structures.  When splitting a node, I use two O(N) passes through the elements.  In the first pass, I select two elements arbitrarily.  For the other elements, I compare each of their bounding volumes to the current pair's volumes.  If I find that the new candidate has a larger furthest-distance between itself and either of the incumbents when compared to the furthest-distance between the incumbents themselves, then the candidate replaces the appropriate incumbent.  Then, I proceed to compare the next element.  This results in a pair of elements that are reasonably far apart from one another.  For the second pass, I use the two elements found in the first pass and associate each of the other elements to the one that has the smallest furthest-distance to it.  This results in a partition of the elements into two collections, each of which can be inserted into a new node for the data structure.  An example of this can be found in my bounding volume hierarchy for Golang.