.png){kind=icon}
返回
Analyzing bounding boxes for object intersection
.png){kind=icon}
OA
AI
DOI：10.1145/336414.336423.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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: alpha, an upper bound on the aspect ratio or elongatedness of each object; and sigma, an upper bound on the scale factor or size disparity between the largest and smallest objects. Letting K-o and K-b be the number of intersecting object pairs and bounding box pairs, respectively, we analyze a ratio measure of the bounding boxes' efficiency, rho = K-b/(n + K-o). The analysis proves that rho = O(alpha root sigma log(2)sigma) and rho = Omega(alpha root sigma). One important consequence is that if alpha and sigma are small constants (as is often the case in practice), then K-b = 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 intersecting pairs in a set of n convex polyhedra with constant alpha and sigma. The algorithm takes time O(nlog(d-1)n + K(o)log(d-1)n) for dimension d = 2, 3. This running time improves on the performance of previous algorithms, which make no assumptions about alpha and sigma.
Keyword:
algorithms
performance
theory
aspect ratio
bounding boxes
collision detection
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。