“Coons BVH for freeform geometric models”
Conference:
Type(s):
Title:
- Coons BVH for freeform geometric models
Session/Category Title: Shape & Vector Representations
Presenter(s)/Author(s):
Abstract:
We present a compact representation for the bounding volume hierarchy (BVH) of freeform NURBS surfaces using Coons patches. Following the Coons construction, each subpatch can be bounded very efficiently using the bilinear surface determined by the four corners. The BVH of freeform surfaces is represented as a hierarchy of Coons patch approximation until the difference is reduced to within a given error bound. Each leaf node contains a single Coons patch, where a detailed BVH for the patch can be represented very compactly using two lists (containing curve approximation errors) of length proportional only to the height of the BVH. We demonstrate the effectiveness of our compact BVH representation using several experimental results from real-time applications in collision detection and minimum distance computation for freeform models.
References:
1. Akenine-Möller, T., Hains, E., Hoffman, N.: Real-Time Rendering, A. K. Peters, Natick, MA, 3rd Ed., 2008.Google Scholar
2. Cohen, E., Riesenfeld, R., and Elber, G.: Geometric Modeling with Splines: An Introduction, A. K. Peters, Natick, MA, 2001. Google ScholarDigital Library
3. Coons, S.: Surfaces for Computer-Aided Design, Technical report, MIT, 1964. Available as AD 663 504 from the National Technical Information Service, Springfield, VA, 22161.Google Scholar
4. Farin, G.: Curves and Surfaces for CAGD, 5th Ed., MorganKaufmann, San Francisco, CA, 2002. Google ScholarDigital Library
5. Gilbert, E., Johnson, D., Keerthi, S.: A fast procedure for computing the distance between complex objects in three-dimensional space. IEEE Trans. Robot. Automat. 4, 2, 193–203, 1988.Google Scholar
6. Gottschalk, S., Lin, M., Manocha, D.: OBB-tree: a hierarchical structure for rapid interference detection. Computer Graphics (SIGGRAPH 1996), 171–180, 1996. Google ScholarDigital Library
7. Govindaraju, N., Redon, S., Lin, M., Manocha, D.: Cullide: interactive collision detection between complex models in large environments using graphics hardware. Proc. Eurographics/SIGGRAPH Graphics Hardware Workshop, pp. 25–32, 2003. Google ScholarDigital Library
8. Guendelman, E., Bridson, R., Fedkiw, R.: Nonconvex Rigid Bodies with Stacking. Proc. of SIGGRAPH 03, Computer Graphics Annual Conference Series, 2003. Google ScholarDigital Library
9. IRIT 10.0 User’s Manual, Technion. http://www.cs.technion.ac.il/~irit.Google Scholar
10. James, D., Pai, D.: Bd-tree: output-sensitive collision detection for reduced deformable models. ACM Trans. on Graphics 23, 3, 393–398, 2004. Google ScholarDigital Library
11. Johnson, D., Cohen, E.: A framework for efficient minimum distance computations. IEEE Int’l Conf. on Robotics and Automation, 3678–3684, 1998.Google Scholar
12. Kim, D., Heo, J.-P., Huh, J., Kim, J., Yoon, S.-E.: HPCCD: Hybrid parallel continuous collision detection using CPUs and GPUs. (Proc. of Pacific Graphics 2009), Computer Graphics Forum 28, 7, 1791–1800, 2009.Google Scholar
13. Krishnan, S., Gopi, M., Lin, M., Manocha, D., Pattekar, A.: Rapid and accurate contact determination between spline models using ShellTrees. Computer Graphics Forum 17, 3, 315–326, 1998.Google ScholarCross Ref
14. Larsen, E., Gottschalk, S., Lin, M. C., Manocha, D.: Fast proximity queries using swept sphere volumes. Technical Report TR99-018, Dept. of Computer Science, UNC, 1999.Google Scholar
15. Lin, M. C., Gottschalk, S.: Collision detection between geometric models: A survey. Proc. of IMA Conference on Mathematics of Surfaces, pp. 37–56, 1998.Google Scholar
16. Lin, M. C., Manocha, D.: Collision and proximity queries. Handbook of Discrete and Computational Geometry, 2nd Ed., J. E. Goodman and J. O’Rourke, Eds., Chapman & Hall/CRC, pp. 787–807, 2004.Google Scholar
17. Redon, S., Kim, Y., Lin, M., Manocha, D.: Fast continuous collision detection for articulated models. Proc. ACM Symp. on Solid Modeling and Applications, pp. 145–156, 2004. Google ScholarDigital Library
18. Samet, H.: Foundations of Multidimensional and Metric Data Structures, Morgan Kaufmann, San Francisco, CA, 2006. Google ScholarDigital Library
19. Tang, M., Curtis, S., Yoon, S.-E., Manocha, D.: Interactive continuous collision detection between deformable models using connectivity-based culling. SPM ’08: Proc. of ACM Symp. on Solid and Physical Modeling, Stony Brook, New York, pp. 25–36, 2008. Google ScholarDigital Library
20. Teschner, M., Kimmerle, S., Heidelberger, B., Zachmann, G., Raghupathi, L., Fuhrmann, A., Cani, M.-P., Faure, F., Magnenat-Thalmann, N., Strasser, W., Volino, P.: Collision detection for deformable objects. Computer Graphics Forum 24, 1, 61–81, 2005.Google ScholarCross Ref
21. van den Bergen, G.: A fast and robust GJK implementation for collision detection of convex objects. Journal of Graphics Tools 4, 2, 7–25, 1999. Google ScholarDigital Library
22. Yoon, S.-E., Manocha, D.: Cache-efficient layouts of bounding volume hierarchies. Computer Graphics Forum 25, 3, 507–516, 2006.Google ScholarCross Ref
23. Zhang, X., Kim, Y.: Interactive collision detection for deformable models using streaming AABBs. IEEE Trans. on Visualization and Computer Graphics 13, 2, 318–329, 2007. Google ScholarDigital Library
