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

article

Adaptive medial-axis approximation for sphere-tree construction

Authors:

Gareth Bradshaw,

Carol O'SullivanAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 23, Issue 1

Pages 1 - 26

https://doi.org/10.1145/966131.966132

Published: 01 January 2004 Publication History

Abstract

Hierarchical object representations play an important role in performing efficient collision handling. Many different geometric primitives have been used to construct these representations, which allow areas of interaction to be localized quickly. For time-critical algorithms, there are distinct advantages to using hierarchies of spheres, known as sphere-trees, for object representation. This article presents a novel algorithm for the construction of sphere-trees. The algorithm presented approximates objects, both convex and non-convex, with a higher degree of fit than existing algorithms. In the lower levels of the representations, there is almost an order of magnitude decrease in the number of spheres required to represent the objects to a given accuracy.

References

[1]

Blum, H. and Nagel, R. 1978. Shape description using weighted symmetric axis features. Patt. Rec. 10, 167--180.

[2]

Bradshaw, G. May 2002. Bounding volume hierarchies for level-of-detail collision handling. Ph.D. dissertation, Trinity College Dublin, Ireland.

[3]

Cohen, J., Lin, M., Manocha, D., and Ponamgi, M. 1995. I-COLLIDE: An interactive and exact collision detection system for large-scaled environments. In Proceedings of ACM Int. 3D Graphics Conference. ACM, New York, 189--196.

[4]

Dingliana, J. and O'Sullivan, C. 2000. Graceful degradation of collision handling in physically based animation. Computer Graphics Forum (Proceedings, Eurographics 2000) 19, 3, 239--247.

[5]

Garland, M. 1999. Quadric-based polygonal surface simplification. Ph.D. dissertation, Carnegie-Mellon University, Pittsburgh, Pa.

[6]

Gottschalk, S., Lin, M., and Manocha, D. 1996. OBB-Tree: A hierarchical structure for rapid interference detection. In Proceedings of ACM SIGGRAPH '96. ACM, New York, 171--180.

[7]

He, T. 1999. Fast collision detection using QuOSPO trees. In Proceedings of the 1999 Symposium on Interactive 3D graphics. 55--62.

[8]

Hubbard, P. 1995a. Collision detection for interactive graphics applications. IEEE Trans. Visual. Comput. Graph. 1, 3, 218--230.

[9]

Hubbard, P. 1995b. Collision detection for interactive graphics applications. Ph.D. dissertation. Dept. of Computer Science, Brown University, Providence, RI.

[10]

Hubbard, P. 1995c. Real-time collision detection and time-critical computing. In Workshop On Simulation and Interation in Virtual Environments.

[11]

Hubbard, P. 1996a. Approximating polyhedra with spheres for time-critical collision detection. ACM Trans. Graph. 15, 3, 179--210.

[12]

Hubbard, P. 1996b. Improving accuracy in a robust algorithm for three-dimensional Voronoi diagrams. J. Graph. Tools 1, 1, 33--47.

[13]

Klosowski, J., Held, M., Mitchell, J., Sowizral, H., and Zikan, K. 1998. Efficient collision detection using bounding volume hierarchies of k-DOPs. IEEE Trans. Vis. Comput. Graph. 4, 1, 21--36.

[14]

Krishnan, S., Gopi, M., Lin, M., Manocha, D., and Pattekar, A. 1998. Rapid and accurate contact determination between spline models using ShellTrees. In Proceedings of Eurographics '98. Vol. 17(3). 315--326.

[15]

Krishnan, S., Pattekar, A., Lin, M., and Manocha, D. 1998. Spherical shells: A higher order bounding volume for fast proximity queries. In Proceedings of the 1998 Workshop on the Algorithmic Foundations of Robotics. 122--136.

[16]

Larsen, E., Gottschalk, S., Lin, M., and Manocha, D. 1999. Fast proximity queries with swept sphere volumes. Tech. Rep. TR99-018, Dept. of Computer Science, University of North Carolina.

[17]

Moore, M. and Wilhelms, J. 1988. Collision detection and response for computer animation. Comput. Graph. 22 4, 289--298.

[18]

O'Sullivan, C. and Dingliana, J. 1999. Realtime collision detection and response using sphere-trees. In Proceedings of the Spring Conference on Computer Graphics. 83--92.

[19]

O'Sullivan, C. and Dingliana, J. 2001. Collisions and perception. ACM Trans. Graph. 20, 3, 151--168.

[20]

Palmer, I. and Grimsdale, R. 1995. Collision detection for animation using sphere-trees. Comput. Graph. For. 14, 2, 105--116.

[21]

Ponamgi, M., Manocha, D., and Lin, M. 1997. Incremental algorithms for collision detection between polygonal models. IEEE Trans. Vis. Comput. Graph. 2, 1, 51--64.

[22]

Quinlan, S. 1994. Efficient distance computation between non-convex objects. In Proceedings International Conference on Robotics and Automation. 3324--3329.

[23]

Ritter, J. 1990. An efficient bounding sphere. In Graphics Gems, A. S. Glassner, Ed. Academic Press, Orlando, Fla., 301--303.

[24]

Rusinkiewicz, S. and Levoy, M. 2000. QSplat: A multiresolution point rendering system for large meshes. In Proceedings of ACM SIGGRAPH 2000, K. Akeley, Ed. ACM Press/ACM SIGGRAPH/Addison Wesley Longman, 343--352.

[25]

Rusinkiewicz, S. and Levoy, M. 2001. Streaming QSplat: A viewer for networked visualization of large, dense models. 2001 Symposium on Interactive 3D Graphics.

[26]

van den Bergen, G. 1997. Efficient collision detection of complex deformable models using AABB trees. J. Graph. Tools 2, 4, 1--13.

[27]

Weltz, E. 1991. Smallest enclosing disks (balls and ellipsoids). In New Results and New Trends in Computer Science, H. Maurer, Ed. 359--370.

[28]

White, D. 2003. Smallest Enclosing Ball of Points/Balls.

[29]

Wilson, A., Larsen, E., Manocha, D., and Lin, M. 1998. IMMPACT: A system for interactive proximity queries on massive models. Tech. Rep. TR98-031, Dept. of Computer Science, University of North Carolina.

Cited By

Thomason WKingston ZKavraki L(2024)Motions in Microseconds via Vectorized Sampling-Based Planning2024 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA57147.2024.10611190(8749-8756)Online publication date: 13-May-2024
https://doi.org/10.1109/ICRA57147.2024.10611190
Zhao MYu GHe YBi H(2024)Haptic Interaction Method Based on Vision with Object Details2024 6th International Conference on Communications, Information System and Computer Engineering (CISCE)10.1109/CISCE62493.2024.10653048(895-901)Online publication date: 10-May-2024
https://doi.org/10.1109/CISCE62493.2024.10653048
Kröger MAgrawal SGalmarini S(2024)Generalized geometric pore size distribution code GPSD-3D for periodic systems composed of monodisperse spheresComputer Physics Communications10.1016/j.cpc.2024.109212301(109212)Online publication date: Aug-2024
https://doi.org/10.1016/j.cpc.2024.109212
Show More Cited By

Index Terms

Adaptive medial-axis approximation for sphere-tree construction
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Computer vision representations
        Hierarchical representations
  2. Computer graphics
    1. Animation
    2. Shape modeling
2. Software and its engineering
  1. Software notations and tools
    1. Development frameworks and environments
      1. Object oriented frameworks

Recommendations

Sphere-tree construction using dynamic medial axis approximation
SCA '02: Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation

Collision handling is very computationally expensive, especially in large scale interactive animations. Hierarchical object representations play an important role in performing efficient collision handling. Many different geometric primitives have been ...
Medial axis approximation and unstable flow complex
SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry

The medial axis of a shape is known to carry a lot of information about it. In particular a recent result of Lieutier establishes that every bounded open subset of Rⁿ has the same homotopy type as its medial axis. In this paper we provide an algorithm ...
Medial-axis-driven shape deformation with volume preservation

The medial axis is a natural skeleton for shapes. However, it is rarely used in the existing skeleton-based shape deformation techniques. In this paper, we propose a novel medial-axis-driven skin surface deformation algorithm with volume preservation ...

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 23, Issue 1

January 2004

96 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/966131

Issue’s Table of Contents

Copyright © 2004 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 2004

Published in TOG Volume 23, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

134
Total Citations
View Citations
2,041
Total Downloads

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

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Thomason WKingston ZKavraki L(2024)Motions in Microseconds via Vectorized Sampling-Based Planning2024 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA57147.2024.10611190(8749-8756)Online publication date: 13-May-2024
https://doi.org/10.1109/ICRA57147.2024.10611190
Zhao MYu GHe YBi H(2024)Haptic Interaction Method Based on Vision with Object Details2024 6th International Conference on Communications, Information System and Computer Engineering (CISCE)10.1109/CISCE62493.2024.10653048(895-901)Online publication date: 10-May-2024
https://doi.org/10.1109/CISCE62493.2024.10653048
Kröger MAgrawal SGalmarini S(2024)Generalized geometric pore size distribution code GPSD-3D for periodic systems composed of monodisperse spheresComputer Physics Communications10.1016/j.cpc.2024.109212301(109212)Online publication date: Aug-2024
https://doi.org/10.1016/j.cpc.2024.109212
Tang JWang JXie XZhou XYan WLi SYu HXin SXu J(2023)3D winding path modeling of overwrapped pressure vessels with novel mesh-based directional projection and normal adaptive convex helix algorithmsComposite Structures10.1016/j.compstruct.2023.117447323(117447)Online publication date: Nov-2023
https://doi.org/10.1016/j.compstruct.2023.117447
Yang RChen SXu GGao SZhou Y(2023)Metaballs-Based Real-Time Elastic Object Simulation via Projective DynamicsComputer-Aided Design and Computer Graphics10.1007/978-981-99-9666-7_15(215-234)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.1007/978-981-99-9666-7_15
Singer VSautter KLarese AWüchner RBletzinger K(2022)A partitioned material point method and discrete element method coupling schemeAdvanced Modeling and Simulation in Engineering Sciences10.1186/s40323-022-00229-59:1Online publication date: 16-Aug-2022
https://doi.org/10.1186/s40323-022-00229-5
Wei XLiu MLing ZSu H(2022)Approximate convex decomposition for 3D meshes with collision-aware concavity and tree searchACM Transactions on Graphics10.1145/3528223.353010341:4(1-18)Online publication date: 22-Jul-2022
https://dl.acm.org/doi/10.1145/3528223.3530103
Tong QWang QZhang YLiao XWei WZhang YXiao JWang D(2022)Configuration-Based Optimization for Virtual Hand Haptic SimulationIEEE Transactions on Haptics10.1109/TOH.2022.319662515:3(613-625)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1109/TOH.2022.3196625
Chiu JSleiman JMittal MFarshidian FHutter M(2022)A Collision-Free MPC for Whole-Body Dynamic Locomotion and Manipulation2022 International Conference on Robotics and Automation (ICRA)10.1109/ICRA46639.2022.9812280(4686-4693)Online publication date: 23-May-2022
https://dl.acm.org/doi/10.1109/ICRA46639.2022.9812280
Zhou MZhang X(2022)Fast Collision Checking for Dual-Arm Collaborative Robots Working in Close Proximity2022 International Conference on Robotics and Automation (ICRA)10.1109/ICRA46639.2022.9811857(243-249)Online publication date: 23-May-2022
https://dl.acm.org/doi/10.1109/ICRA46639.2022.9811857
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