Loading...
Please wait, while we are loading the content...
Similar Documents
Analyzing Bounding Boxes for Object Intersection SUBHASH SURI
| Content Provider | CiteSeerX |
|---|---|
| Author | Hubbard, Philip M. Hughes, John F. |
| Abstract | Heuristics that exploit bounding boxes are common in algorithms for rendering, modeling, and animation. While experience has shown that bounding boxes improve the performance of these algorithms in practice, the previous theoretical analysis has concluded that bounding boxes perform poorly in the worst case. This paper reconciles this discrepancy by analyzing intersections among n geometric objects in terms of two parameters: �, an upper bound on the aspect ratio or elongatedness of each object; and �, an upper bound on the scale factor or size disparity between the largest and smallest objects. Letting Ko and Kb be the number of intersecting object pairs and bounding box pairs, respectively, we analyze a ratio measure of the bounding boxes ’ efficiency, � � Kb � �n � Ko�. The analysis proves that � � O����log2� � and � �������. One important consequence is that if � and � are small constants (as is often the case in practice), then Kb � O�K o � � O�n�, so an algorithm that uses bounding boxes has time complexity proportional to the number of actual object intersections. This theoretical result validates the efficiency that bounding boxes have demonstrated in practice. Another consequence of our analysis is a proof of the output-sensitivity of an algorithm for reporting all |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Box Pair Size Disparity Actual Object Intersection Geometric Object Ratio Measure Object Intersection Subhash Suri Theoretical Result Bounding Box Aspect Ratio Upper Bound Smallest Object Small Constant Scale Factor Time Complexity Proportional Bounding Box Efficiency Important Consequence Previous Theoretical Analysis Object Pair |
| Content Type | Text |
| Resource Type | Article |
