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

research-article

Hierarchical hp-adaptive signed distance fields

Authors:

Jan BenderAuthors Info & Claims

SCA '16: Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation

Pages 189 - 198

Published: 11 July 2016 Publication History

Abstract

In this paper we propose a novel method to construct hierarchical hp-adaptive Signed Distance Fields (SDFs). We discretize the signed distance function of an input mesh using piecewise polynomials on an axis-aligned hexahedral grid. Besides spatial refinement based on octree subdivision to refine the cell size (h), we hierarchically increase each cell's polynomial degree (p) in order to construct a very accurate but memory-efficient representation. Presenting a novel criterion to decide whether to apply h- or p-refinement, we demonstrate that our method is able to construct more accurate SDFs at significantly lower memory consumption than previous approaches. Finally, we demonstrate the usage of our representation as collision detector for geometrically highly complex solid objects in the application area of physically-based simulation.

Supplementary Material

ZIP File (p189-koschier.zip)

Supplemental material.

Download
182.98 MB

References

[1]

{AFC*10} Allard J., Faure F., Courtecuisse H., Falipou F., Duriez C., Kry P. G.: Volume contact constraints at arbitrary resolution. ACM Transactions on Graphics 29, 4 (2010), 82:1--82:10. 3

Digital Library

[2]

{BA05} Bærentzen J. A., Aanæs H.: Signed distance computation using the angle weighted pseudonormal. IEEE Transactions on Visualization and Computer Graphics 11, 3 (2005), 243--253. 3

Digital Library

[3]

{Bae05} Baerentzen A. J.: Robust Generation of Signed Distance Fields from Triangle Meshes. International Workshop on Volume Graphics (2005), 167--239. 2

Digital Library

[4]

{Bær02} Bærentzen J. A.: Manipulation of volumetric solids with applications to sculpting. Phd thesis, Technical University of Denmark, 2002. 2

[5]

{Ben16} Bender J.: PositionBasedDynamics Library. https://github.com/InteractiveComputerGraphics/PositionBasedDynamics, 2016. 6

[6]

{BJ08} Barbič J., James D. L.: Six-DoF Haptic Rendering of Contact Between Geometrically Complex Reduced Deformable Models. IEEE Transactions on Haptics 1, 1 (2008), 39--52. 2

Digital Library

[7]

{BKCW14} Bender J., Koschier D., Charrier P., Weber D.: Position-Based Simulation of Continuous Materials. Computers & Graphics 44, 0 (2014), 1--10. 6

Digital Library

[8]

{BMF03} Bridson R., Marino S., Fedkiw R.: Simulation of clothing with folds and wrinkles. In ACM SIGGRAPH / Eurographics Symposium on Computer Animation (2003), Eurographics Association, pp. 28--36. 2

Digital Library

[9]

{CT11} Calakli F., Taubin G.: SSD: Smooth Signed Distance Surface Reconstruction. Computer Graphics Forum 30, 7 (2011), 1993--2002. 1

[10]

{DCB14} Deul C., Charrier P., Bender J.: Position-based rigid-body dynamics. Computer Animation and Virtual Worlds (2014). 6

[11]

{ED08} Erleben K., Dohlmann H.: Signed Distance Fields Using Single-Pass GPU Scan Conversion of Tetrahedra. In GPU Gems 3. Addison-Wesley Professional, 2008, ch. 34, pp. 741--763. 2

[12]

{FBAF08} Faure F., Barbier S., Allard J., Falipou F.: Image-based collision detection and response between arbitrary volume objects. In ACM SIGGRAPH / Eurographics Symposium on Computer Animation (2008), pp. 155--162. 3

Digital Library

[13]

{FP06} Frisken S. F., Perry R. N.: Designing with Distance Fields. In ACM SIGGRAPH Courses (2006), pp. 60--66. 1

Digital Library

[14]

{FPRJ00} Frisken S. F., Perry R. N., Rockwood A. P., Jones T. R.: Adaptively sampled distance fields: a general representation of shape for computer graphics. ACM Transactions on Graphics (2000), 249--254. 2

Digital Library

[15]

{FSG03} Fuhrmann A., Sobottka G., Gross C.: Distance Fields for Rapid Collision Detection in Physically Based Modeling. In Computer Graphics and Vision (2003), pp. 1--8. 2

[16]

{GSM*12} Glondu L., Schvartzman S. C., Marchal M., Dumont G., Otaduy M. A.: Efficient Collision Detection for Brittle Fracture. In ACM SIGGRAPH / Eurographics Symposium on Computer Animation (2012), pp. 285--294. 2

Digital Library

[17]

{HLC*01} Huang J., Li Y., Crawfis R., Lu S. C., Liou S. Y.: A complete distance field representation. In IEEE Visualization (2001), pp. 247--254. 2

Digital Library

[18]

{HNR*04} Huamin QU, Nan Zhang, Ran Shao, Kaufman A., Mueller K.: Feature preserving distance fields. In IEEE Symposium on Volume Visualization and Graphics (2004), pp. 39--46. 2

Digital Library

[19]

{Jam10} Jamriška O.: Interactive Ray Tracing of Distance Fields. In Central European Seminar on Computer Graphics (2010), vol. 2. 1

[20]

{JBS06} Jones M., Baerentzen J., Sramek M.: 3D distance fields: a survey of techniques and applications. IEEE Transactions on Visualization and Computer Graphics 12, 4 (2006), 581--599. 2

Digital Library

[21]

{JLSW02} Ju T., Losasso F., Schaefer S., Warren J.: Dual Contouring of Hermite Data. ACM Transactions on Graphics 21, 3 (2002), 339--346. 2

Digital Library

[22]

{Jon04} Jones M. W.: Distance field compression. Journal of WSCG 12, 2 (2004), 199--204. 3

[23]

{KSP07} Kaufman D. M., Sueda S., Pai D. K.: Contact trees: Adaptive Contact Sampling for Robust Dynamics. In ACM SIGGRAPH Sketches (2007). 2

Digital Library

[24]

{LK14} Liu F., Kim Y. J.: Exact and Adaptive Signed Distance Fields Computation for Rigid and Deformable Models on GPUs. IEEE Transactions on Visualization and Computer Graphics 20, 5 (2014), 714--725. 2

Digital Library

[25]

{MASS15} Mitchell N., Aanjaneya M., Setaluri R., Sifakis E.: Non-manifold Level Sets: A multivalued implicit surface representation with applications to self-collision processing. ACM Transactions on Graphics 34, 6 (2015), 247:1--247:9. 1, 3, 8

Digital Library

[26]

{MTS07} Moustakas K., Tzovaras D., Strintzis M. G.: SQ-Map: Efficient Layered Collision Detection and Haptic Rendering. IEEE Transactions on Visualization and Computer Graphics 13, 1 (2007), 80--93. 3

Digital Library

[27]

{Mus13} Museth K.: VDB: High-resolution Sparse Volumes with Dynamic Topology. ACM Transactions on Graphics 32, 3 (2013), 27:1--27:22. 2

Digital Library

[28]

{MZS*11} McAdams A., Zhu Y., Selle A., Empey M., Tamstorf R., Teran J., Sifakis E.: Efficient elasticity for character skinning with contact and collisions. ACM Transactions on Graphics 30, 4 (2011), 37:1--37:12. 2

Digital Library

[29]

{OJSL04} Otaduy M. A., Jain N., Sud A., Lin M. C.: Haptic display of interaction between textured models. In IEEE Visualization (2004), pp. 297--304. 3

Digital Library

[30]

{PF01} Perry R. N., Frisken S. F.: Kizamu: A System for Sculpting Digital Characters. In Computer Graphics and Interactive Techniques (2001), pp. 47--56. 2

Digital Library

[31]

{RP66} Rosenfeld A., Pfaltz J. L.: Sequential Operations in Digital Picture Processing. Journal of the ACM 13, 4 (1966), 471--494. 2

Digital Library

[32]

{SFP12} Sanchez M., Fryazinov O., Pasko A.: Efficient Evaluation of Continuous Signed Distance to a Polygonal Mesh. In Spring Conference on Computer Graphics (2012), pp. 101--108. 2, 3, 7

Digital Library

[33]

{WFP12} Wang B., Faure F., Pai D. K.: Adaptive image-based intersection volume. ACM Transactions on Graphics 31, 4 (2012), 97:1--97:9. 3

Digital Library

[34]

{WK03} Wu J., Kobbelt L.: Piecewise Linear Approximation of Signed Distance Fields. In Vision, Modeling and Visualization (2003), pp. 513--520. 3

[35]

{XB14a} Xu H., Barbič J.: Continuous Collision Detection Between Points and Signed Distance Fields. In Proceedings of Virtual Reality Interactions and Physical Simulations (VRIPhys) (2014). 2

[36]

{XB14b} Xu H., Barbič J.: Signed Distance Fields for Polygon Soup Meshes. In Graphics Interface (2014), pp. 1--7. 2

Digital Library

[37]

{XZB14} Xu H., Zhao Y., Barbič J.: Implict Multibody Penalty-based Distributed Contact. IEEE Transactions on Visualization and Computer Graphics 20, 9 (2014), 1266--1279. 2

Cited By

Macklin MErleben KMüller MChentanez NJeschke SCorse Z(2020)Local Optimization for Robust Signed Distance Field CollisionProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/33845383:1(1-17)Online publication date: 4-May-2020
https://dl.acm.org/doi/10.1145/3384538
Krayer BMüller S(2019)Generating signed distance fields on the GPU with ray mapsThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-019-01683-w35:6-8(961-971)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s00371-019-01683-w

Index Terms

Hierarchical hp-adaptive signed distance fields
1. Computing methodologies
  1. Computer graphics
    1. Animation

Recommendations

Signed distance fields for polygon soup meshes
GI '14: Proceedings of Graphics Interface 2014

Many meshes in computer animation practice are meant to approximate solid objects, but the provided triangular geometry is often unoriented, non-manifold or contains self-intersections, causing inside/outside of objects to be mathematically ill-defined. ...
Convolution Filtering of Continuous Signed Distance Fields for Polygonal Meshes

Signed distance fields obtained from polygonal meshes are commonly used in various applications. However, they can have C1 discontinuities causing creases to appear when applying operations such as blending or metamorphosis. The focus of this work is to ...
A double layer method for constructing signed distance fields from triangle meshes

A new algorithm is proposed for constructing signed distance fields (SDF) from triangle meshes. In our approach, both the internal and external distance fields for the triangle mesh are computed first. Then the desired SDF is computed directly from ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCA '16: Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation

July 2016

238 pages

ISBN:9783905674613

Conference Chairs:
Barbara Solenthaler
ETH Zurich, Switzerland
,
Matthias Teschner
University of Freiburg, Germany
,
Program Chairs:
Ladislav Kavan
University of Utah, USA
,
Chris Wojtan
IST Austria, Austria

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
EUROGRAPHICS: The European Association for Computer Graphics

Publisher

Eurographics Association

Goslar, Germany

Publication History

Published: 11 July 2016

Check for updates

Qualifiers

Research-article

Conference

SCA '16

Sponsor:

SIGGRAPH
EUROGRAPHICS

SCA '16: The ACM SIGGRAPH / Eurographics Symposium on Computer Animation

July 11 - 13, 2016

Zurich, Switzerland

Acceptance Rates

Overall Acceptance Rate 183 of 487 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
1
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Macklin MErleben KMüller MChentanez NJeschke SCorse Z(2020)Local Optimization for Robust Signed Distance Field CollisionProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/33845383:1(1-17)Online publication date: 4-May-2020
https://dl.acm.org/doi/10.1145/3384538
Krayer BMüller S(2019)Generating signed distance fields on the GPU with ray mapsThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-019-01683-w35:6-8(961-971)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s00371-019-01683-w

View Options

View options

Media

Figures

Other

Tables

View Table of Contents