skip to main content
10.5555/1281991.1282017acmotherconferencesArticle/Chapter ViewAbstractPublication PagessgpConference Proceedingsconference-collections
Article

Generalized surface flows for mesh processing

Published: 04 July 2007 Publication History

Abstract

Geometric flows are ubiquitous in mesh processing. Curve and surface evolutions based on functional minimization have been used in the context of surface diffusion, denoising, shape optimization, minimal surfaces, and geodesic paths to mention a few. Such gradient flows are nearly always, yet often implicitly, based on the canonical Linner product of vector fields. In this paper, we point out that changing this inner product provides a simple, powerful, and untapped approach to extend current flows. We demonstrate the value of such a norm alteration for regularization and volume-preservation purposes and in the context of shape matching, where deformation priors (ranging from rigid motion to articulated motion) can be incorporated into a gradient flow to drastically improve results. Implementation details, including a differentiable approximation of the Hausdorff distance between irregular meshes, are presented.

References

[1]
{ACP02} Allen B., Curless B., Popović Z.: Articulated body deformation from range scan data. ACM Trans. on Graphics (SIGGRAPH) 21, 3 (2002), 612--619.
[2]
{ACP03} Allen B., Curless B., Popović Z.: The space of human body shapes: reconstruction and parameterization from range scans. ACM SIGGRAPH (2003), 587--594.
[3]
{ASK*05} Anguelov D., Srinivasan P., Koller D., Thrun S., Rodgers J., Davis J.: Scape: shape completion and animation of people. ACM Trans. on Graphics (SIGGRAPH) 24, 3 (Aug. 2005), 408--416.
[4]
{ASP*04} Anguelov D., Srinivasan P., Pang H.-C., Koller D., Thrun S., Davis J.: The correlated correspondence algorithm for unsupervised registration of nonrigid surfaces. In Advances in Neural Information Processing Systems (2004).
[5]
{BBC*94} Barret R., Berry M., Chan T., Demmel J., Donato J., Dongarra J., Eijkhout V., Pozo R., Romine C., van der Vonst H.: Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM, 1994.
[6]
{BBK07a} Bronstein A., Bronstein M., Kimmel R.: Calculus of non-rigid surfaces for geometry and texture manipulation. IEEE Trans. on Vis. and Comp. Graphics, to appear (2007).
[7]
{BBK07b} Bronstein A., Bronstein M., Kimmel R.: Joint intrinsic and extrinsic similarity for recognition of non-rigid shapes. Tech. Rep. CIS-2007-01, Dept. of CS, Technion, 2007.
[8]
{BM92} BESL P., McKay N.: A method for registration of 3D shapes. IEEE Transactions on PAMI 14, 2 (1992), 239--256.
[9]
{BR04} Brown B., Rusinkiewicz S.: Non-rigid range-scan alignment using thin-plate splines. Int. Symp. on 3D Data Processing, Visualization and Transmission (2004), 759--765.
[10]
{BS05} Bobenko A. I., Schröder P.: Discrete willmore flow. In Symp. on Geometry Processing (July 2005), pp. 101--110.
[11]
{BWK05} Bischoff S., Weyand T., Kobbelt L.: Snakes on triangle meshes. Bild. für die Medizin (2005), 208--212.
[12]
{CFK05} Charpiat G., Faugeras O., Keriven R.: Approximations of shape metrics and application to shape warping and empirical shape statistics. FoCM 5, 1 (2005), 1--58.
[13]
{CKPF05} Charpiat G., Keriven R., Pons J.-P., Faugeras O.: Designing spatially coherent minimizing flows for variational problems based on active contours. In International Conference on Computer Vision (2005), vol. 2, pp. 1403--1408.
[14]
{CKS97} Caselles V., Kimmel R., Sapiro G.: Geodesic active contours. IJCV 22, 1 (1997), 61--79.
[15]
{CM91} Chen Y., Medioni G.: Object modeling by registration of multiple range images. In IEEE Conference on Robotics and Automation (1991), vol. 3, pp. 2724--2729.
[16]
{CMP*06} Charpiat G., Maurel P., Pons J.-P., Keriven R., Faugeras O.: Generalized Gradients: Priors on Minimization Flows. Tech. Rep. 06--23, ENPC-CERTIS, march 2006.
[17]
{CR03} Chui H., Rangarajan A.: A new point matching algorithm for non-rigid registration. Computer Vision and Image Understanding 89, 2--3 (2003), 114--141.
[18]
{CSAD04} Cohen-Steiner D., Alliez P., Desbrun M.: Variational shape approximation. ACM Trans. on Graphics 23, 3 (2004), 905--914.
[19]
{DDCB00} Debunne G., Desbrun M., Cani M.-P., Barr A. H.: Adaptive simulation of soft bodies in real-time. In Computer Animation (May 2000), pp. 133--144.
[20]
{DGG03} Dey T., Giesen J., Goswami S.: Shape segmentation and matching with flow discretization. In Workshop on Algorithms and Data Structures (2003), pp. 25--36.
[21]
{DKS02} Dziuk G., Kuwert E., Schatzle R.: Evolution of elastic curves in Rn: Existence and computation. SIAM J. Math. Anal. 33, 5 (2002), 1228--1245.
[22]
{DMSB99} Desbrun M., Meyer M., Schröder P., Barr A.: Implicit fairing of irregular meshes using diffusion and curvature flow. ACM SIGGRAPH (1999), 317--324.
[23]
{DR04} Droske M., Rumpf M.: A Levelset Formulation for Willmore Flow. Interfaces & Free Boundaries 6 (2004), 361--378.
[24]
{DTB06} Diebel J. R., Thrun S., Brünig M.: A Bayesian method for probable surface reconstruction & decimation. ACM Trans. Graphics 25, 1 (2006), 39--59.
[25]
{EK03} Elad A., Kimmel R.: On bending invariant signatures for surfaces. IEEE Trans. on PAMI 25, 10 (2003), 1285--1295.
[26]
{FA96} Feldmar J., Ayache N.: Rigid, affine and locally affine registration of free-form surfaces. International Journal of Computer Vision 18, 2 (1996), 99--119.
[27]
{GH86} Gage M., Hamilton R.: The heat equation shrinking convex plane curves. Journal of Diff. Geo. 23 (1986), 69--96.
[28]
{GH97} Garland M., Heckbert P.: Surface simplification using quadric error metrics. ACM SIGGRAPH (1997), 209--216.
[29]
{GHDS03} Grinspun E., Hirani A. N., Desbrun M., Schröder P.: Discrete shells. In ACM SIGGRAPH Symp. on Computer Animation (2003), pp. 62--67.
[30]
{GMGP05} Gelfand N., Mitra N., Guibas L., Pottmann H.: Robust global registration. In Symp. on Geo. Processing (2005), pp. 197--206.
[31]
{KMP07} Kilian M., Mitra N. J., Pottmann H.: Geometric modeling in shape space. In ACM Transactions on Graphics (SIGGRAPH) (2007).
[32]
{Kob00} Kobbelt L.: Discrete fairing and variational subdivision for freeform surface design. The Visual Computer 16, 3--4 (2000), 142--158.
[33]
{KSMJ04} Klassen E., Srivastava A., Mio W., Joshi S. H.: Analysis of planar shapes using geodesic paths on shape spaces. IEEE Trans. on PAMI 26, 3 (2004), 372--383.
[34]
{MBWB02} Museth K., Breen D. E., Whitaker R. T., Barr A. H.: Level set surface editing operators. 330--338.
[35]
{MDSB02} Meyer M., Desbrun M., Schröder P., Barr A.: Discrete differential-geometry operators for 2-manifolds. In Proc. of Int. Workshop on Vis. and Math. (2002), pp. 52--58.
[36]
{MGPG04} Mitra N., Gelfand N., Pottmann H., Guibas L.: Registration of point cloud data from a geometric optimization perspective. Symp. on Geometry Processing (2004), 23--32.
[37]
{MM05} Michor P., Mumford D.: Riemannian geometries of space of plane curves, 2005. Preprint.
[38]
{OF03} Osher S., Fedkiw R.: Level Set Methods and Dynamic Implicit Surfaces, vol. 153 of Applied Mathematical Sciences. Springer-Verlag, New York, 2003.
[39]
{PKZ04} Peng J., Kristjansson D., Zorin D.: Interactive modeling of topologically complex geometric detail. ACM Trans. Graph. 23, 3 (2004), 635--643.
[40]
{PMG*05} Pauly M., Mitra N., Giesen J., Gross M., Guibas L.: Example-based 3D scan completion. Symposium on Geometry Processing (2005), 23--32.
[41]
{PMW05} Planitz B., Maeder A., Williams J.: The correspondence framework for 3D surface matching algorithms. Computer Vision and Image Understanding 97, 3 (2005), 347--383.
[42]
{PP93} Pinkall U., Polthier K.: Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2, 1 (1993), 15--36.
[43]
{RL01} Rusinkiewicz S., Levoy M.: Efficient variants of the ICP algorithm. Proc. 3DIM (2001), 145--152.
[44]
{Set99} Sethian J. A.: Level Set Methods and Fast Marching Methods, 2nd ed., vol. 3 of Monographs on Appl. Comput. Math. Cambridge University Press, Cambridge, 1999.
[45]
{SK04} Sheffer A., Kraevoy V.: Pyramid coordinates for morphing and deformation. In Int. Symp. on 3D Data Processing, Visualization and Transmission (2004), pp. 68--75.
[46]
{SKR*06} Stoll C., Karni Z., Rössl C., Yamauchi H., Seidel H.-P.: Template deformation for point cloud fitting. In Symposium on Point-Based Graphics (2006), pp. 27--35.
[47]
{SYM07} Sundaramoorthi G., Yezzi A., Mennucci A. C. G.: Sobolev active contours. IJCV 73, 3 (2007), 345--366.
[48]
{Tau95} Taubin G.: A signal processing approach to fair surface design. In Proc. of SIGGRAPH (Aug. 1995), pp. 351--358.
[49]
{XPB06} Xu G., Pan Q., Bajaj C. L.: Discrete surface modeling using partial differential equations. Computer Aided Geometric Design 23, 2 (2006), 125--145.
[50]
{YM05} Yezzi A., Mennucci A.: Conformal metrics and true "gradient flows" for curves. In International Conference on Computer Vision (2005), pp. 913--919.
[51]
{You99} Younes L.: Optimal matching between shapes via elastic deformations. Image & Vision Comp. 17, 5 (1999), 381--389.
[52]
{ZG04} Zelinka S., Garland M.: Similarity-based surface modelling using geodesic fans. Symposium on Geometry Processing (2004), 204--213.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences
SGP '07: Proceedings of the fifth Eurographics symposium on Geometry processing
July 2007
273 pages
ISBN:9783905673463

Sponsors

  • EUROGRAPHICS: The European Association for Computer Graphics

Publisher

Eurographics Association

Goslar, Germany

Publication History

Published: 04 July 2007

Check for updates

Qualifiers

  • Article

Conference

SGP '07
Sponsor:
  • EUROGRAPHICS
SGP '07: Geometry processing
July 4 - 6, 2007
Barcelona, Spain

Acceptance Rates

SGP '07 Paper Acceptance Rate 21 of 74 submissions, 28%;
Overall Acceptance Rate 64 of 240 submissions, 27%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 16 Feb 2025

Other Metrics

Citations

Cited By

View all

View Options

View options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media