More Web Proxy on the site http://driver.im/

research-article

Coons BVH for freeform geometric models

Authors:

Seung-Hyun Yoon,

Gershon ElberAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 30, Issue 6

Pages 1 - 8

https://doi.org/10.1145/2070781.2024203

Published: 12 December 2011 Publication History

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.

Supplementary Material

JPG File (a169-kim.jpg)

Download
8.04 KB

AVI File (a169-kim.avi)

Download
67.98 MB

References

[1]

Akenine-Möller, T., Hains, E., Hoffman, N.: Real-Time Rendering, A. K. Peters, Natick, MA, 3rd Ed., 2008.

[2]

Cohen, E., Riesenfeld, R., and Elber, G.: Geometric Modeling with Splines: An Introduction, A. K. Peters, Natick, MA, 2001.

Digital 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.

[4]

Farin, G.: Curves and Surfaces for CAGD, 5th Ed., MorganKaufmann, San Francisco, CA, 2002.

Digital 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.

[6]

Gottschalk, S., Lin, M., Manocha, D.: OBB-tree: a hierarchical structure for rapid interference detection. Computer Graphics (SIGGRAPH 1996), 171--180, 1996.

Digital 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.

Digital Library

[8]

Guendelman, E., Bridson, R., Fedkiw, R.: Nonconvex Rigid Bodies with Stacking. Proc. of SIGGRAPH 03, Computer Graphics Annual Conference Series, 2003.

Digital Library

[9]

IRIT 10.0 User's Manual, Technion. http://www.cs.technion.ac.il/~irit.

[10]

James, D., Pai, D.: Bd-tree: output-sensitive collision detection for reduced deformable models. ACM Trans. on Graphics 23, 3, 393--398, 2004.

Digital Library

[11]

Johnson, D., Cohen, E.: A framework for efficient minimum distance computations. IEEE Int'l Conf. on Robotics and Automation, 3678--3684, 1998.

[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.

[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.

[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.

[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.

[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.

[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.

Digital Library

[18]

Samet, H.: Foundations of Multidimensional and Metric Data Structures, Morgan Kaufmann, San Francisco, CA, 2006.

Digital 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.

Digital 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.

[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.

Digital Library

[22]

Yoon, S.-E., Manocha, D.: Cache-efficient layouts of bounding volume hierarchies. Computer Graphics Forum 25, 3, 507--516, 2006.

[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.

Digital Library

Cited By

Schmidt PCampen MBorn JKobbelt L(2020)Inter-surface maps via constant-curvature metricsACM Transactions on Graphics10.1145/3386569.339239939:4Online publication date: 12-Aug-2020
https://doi.org/10.1145/3386569.3392399
Haynes BMazumdar AAlaghi ABalazinska MCeze LCheung A(2018)LightDBProceedings of the VLDB Endowment10.14778/3231751.323176811:10(1192-1205)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.14778/3231751.3231768
Kang YKyung MYoon SKim M(2018)Fast and robust Hausdorff distance computation from triangle mesh to quad mesh in near-zero casesComputer Aided Geometric Design10.1016/j.cagd.2018.03.01762(91-103)Online publication date: May-2018
https://doi.org/10.1016/j.cagd.2018.03.017
Show More Cited By

Index Terms

Coons BVH for freeform geometric models
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Coons BVH for freeform geometric models
SA '11: Proceedings of the 2011 SIGGRAPH Asia Conference

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 ...
Efficient Hausdorff Distance computation for freeform geometric models in close proximity

We present an interactive-speed algorithm for computing the Hausdorff Distance (HD) between two freeform geometric models represented with NURBS surfaces. The algorithm is based on an effective technique for matching a surface patch from one model to ...
A surface blending approach for displacement features on freeform surfaces

Embedding a number of displacement features into a base surface is common in industrial product design and modeling, where displaced surface regions are blended with the unmodified surface region. The cubic Hermite interpolant is usually adopted for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 30, Issue 6

December 2011

678 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2070781

Issue’s Table of Contents

Copyright © 2011 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 December 2011

Published in TOG Volume 30, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Israeli Ministry of Science
NRF Research

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
703
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)2

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Schmidt PCampen MBorn JKobbelt L(2020)Inter-surface maps via constant-curvature metricsACM Transactions on Graphics10.1145/3386569.339239939:4Online publication date: 12-Aug-2020
https://doi.org/10.1145/3386569.3392399
Haynes BMazumdar AAlaghi ABalazinska MCeze LCheung A(2018)LightDBProceedings of the VLDB Endowment10.14778/3231751.323176811:10(1192-1205)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.14778/3231751.3231768
Kang YKyung MYoon SKim M(2018)Fast and robust Hausdorff distance computation from triangle mesh to quad mesh in near-zero casesComputer Aided Geometric Design10.1016/j.cagd.2018.03.01762(91-103)Online publication date: May-2018
https://doi.org/10.1016/j.cagd.2018.03.017
Wang XZhou BWang ZZou DChen XZhao Q(2018)Efficiently consistent affinity propagation for 3D shapes co-segmentationThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-018-1538-234:6-8(997-1008)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s00371-018-1538-2
Zhang DHe FHan SZou LWu YChen Y(2017)An efficient approach to directly compute the exact Hausdorff distance for 3D point setsIntegrated Computer-Aided Engineering10.3233/ICA-17054424:3(261-277)Online publication date: 21-Jul-2017
https://doi.org/10.3233/ICA-170544
Koschier DBender JThuerey N(2017)Robust eXtended finite elements for complex cutting of deformablesACM Transactions on Graphics10.1145/3072959.307366636:4(1-13)Online publication date: 20-Jul-2017
https://dl.acm.org/doi/10.1145/3072959.3073666
Cosmo LRodolí EAlbarelli AMémoli FCremers D(2017)Consistent Partial Matching of Shape Collections via Sparse ModelingComputer Graphics Forum10.1111/cgf.1279636:1(209-221)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1111/cgf.12796
Xu KKim VHuang QKalogerakis E(2017)Data-Driven Shape Analysis and ProcessingComputer Graphics Forum10.1111/cgf.1279036:1(101-132)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1111/cgf.12790
Kang YPark JLee JShim MKim MThalmann NGavrilova MKomura TCordier FThalmann D(2016)Compact Modeling and Plausible Deformation of Human Lung Anatomy with Smooth SurfacesProceedings of the 29th International Conference on Computer Animation and Social Agents10.1145/2915926.2915938(21-28)Online publication date: 23-May-2016
https://dl.acm.org/doi/10.1145/2915926.2915938
Maron HDym NKezurer IKovalsky SLipman Y(2016)Point registration via efficient convex relaxationACM Transactions on Graphics10.1145/2897824.292591335:4(1-12)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.1145/2897824.2925913
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents