@proceedings{60447, editor = {{Andres, Bjoern and Campen, Marcel and Sedlmair, Michael}}, isbn = {{978-3-03868-161-8}}, publisher = {{Eurographics Association}}, title = {{{26th International Symposium on Vision, Modeling, and Visualization, VMV 2021, Virtual Event / Technische Universität Dresden, Germany, September 27-28, 2021}}}, year = {{2021}}, } @article{60377, abstract = {{We present a guaranteed quality mesh generation algorithm for the curvilinear triangulation of planar domains with piecewise polynomial boundary. The resulting mesh consists of higher-order triangular elements which are not only regular (i.e., with injective geometric map) but respect strict bounds on quality measures like scaled Jacobian and MIPS distortion. This also implies that the curved triangles' inner angles are bounded from above and below. These are key quality criteria, for instance, in the field of finite element analysis. The domain boundary is reproduced exactly, without geometric approximation error. The central idea is to transform the curvilinear meshing problem into a linear meshing problem via a carefully constructed transformation of bounded distortion, enabling us to leverage key results on guaranteed-quality straight-edge triangulation. The transformation is based on a simple yet general construction and observations about convergence properties of curves under subdivision. Our algorithm can handle arbitrary polynomial order, arbitrarily sharp corners, feature and interface curves, and can be executed using rational arithmetic for strict reliability.}}, author = {{Mandad, Manish and Campen, Marcel}}, issn = {{0730-0301}}, journal = {{ACM Transactions on Graphics}}, number = {{4}}, pages = {{1--14}}, publisher = {{Association for Computing Machinery (ACM)}}, title = {{{Guaranteed-quality higher-order triangular meshing of 2D domains}}}, doi = {{10.1145/3450626.3459673}}, volume = {{40}}, year = {{2021}}, } @article{60378, abstract = {{We describe an efficient algorithm to compute a discrete metric with prescribed Gaussian curvature at all interior vertices and prescribed geodesic curvature along the boundary of a mesh. The metric is (discretely) conformally equivalent to the input metric. Its construction is based on theory developed in [Gu et al. 2018b] and [Springborn 2020], relying on results on hyperbolic ideal Delaunay triangulations. Generality is achieved by considering the surface's intrinsic triangulation as a degree of freedom, and particular attention is paid to the proper treatment of surface boundaries. While via a double cover approach the case with boundary can be reduced to the case without boundary quite naturally, the implied symmetry of the setting causes additional challenges related to stable Delaunay-critical configurations that we address explicitly. We furthermore explore the numerical limits of the approach and derive continuous maps from the discrete metrics.}}, author = {{Campen, Marcel and Capouellez, Ryan and Shen, Hanxiao and Zhu, Leyi and Panozzo, Daniele and Zorin, Denis}}, issn = {{0730-0301}}, journal = {{ACM Transactions on Graphics}}, number = {{6}}, pages = {{1--16}}, publisher = {{Association for Computing Machinery (ACM)}}, title = {{{Efficient and robust discrete conformal equivalence with boundary}}}, doi = {{10.1145/3478513.3480557}}, volume = {{40}}, year = {{2021}}, } @article{60376, abstract = {{AbstractA homeomorphism between two surfaces not only defines a (continuous and bijective) geometric correspondence of points but also (by implication) an identification of topological features, i.e. handles and tunnels, and how the map twists around them. However, in practice, surface maps are often encoded via sparse correspondences or fuzzy representations that merely approximate a homeomorphism and are therefore inherently ambiguous about map topology. In this work, we show a way to infer topological information from an imperfect input map between two shapes. In particular, we compute a homology map, a linear map that transports homology classes of cycles from one surface to the other, subject to a global consistency constraint. Our inference robustly handles imperfect (e.g., partial, sparse, fuzzy, noisy, outlier‐ridden, non‐injective) input maps and is guaranteed to produce homology maps that are compatible with true homeomorphisms between the input shapes. Homology maps inferred by our method can be directly used to transfer homological information between shapes, or serve as foundation for the construction of a proper homeomorphism guided by the input map, e.g., via compatible surface decomposition.}}, author = {{Born, Janis and Schmidt, Patrick and Campen, Marcel and Kobbelt, Leif}}, issn = {{0167-7055}}, journal = {{Computer Graphics Forum}}, number = {{5}}, pages = {{193--204}}, publisher = {{Wiley}}, title = {{{Surface Map Homology Inference}}}, doi = {{10.1111/cgf.14367}}, volume = {{40}}, year = {{2021}}, } @article{60374, abstract = {{AbstractWe present a robust and fast method for the creation of conforming quad layouts on surfaces. Our algorithm is based on the quantization of a T‐mesh, i.e. an assignment of integer lengths to the sides of a non‐conforming rectangular partition of the surface. This representation has the benefit of being able to encode an infinite number of layout connectivity options in a finite manner, which guarantees that a valid layout can always be found. We carefully construct the T‐mesh from a given seamless parametrization such that the algorithm can provide guarantees on the results' quality. In particular, the user can specify a bound on the angular deviation of layout edges from prescribed directions. We solve an integer linear program (ILP) to find a coarse quad layout adhering to that maximal deviation. Our algorithm is guaranteed to yield a conforming quad layout free of T‐junctions together with bounded angle distortion. Our results show that the presented method is fast, reliable, and achieves high quality layouts.}}, author = {{Lyon, Max and Campen, Marcel and Kobbelt, Leif}}, issn = {{0167-7055}}, journal = {{Computer Graphics Forum}}, number = {{2}}, pages = {{305--314}}, publisher = {{Wiley}}, title = {{{Quad Layouts via Constrained T‐Mesh Quantization}}}, doi = {{10.1111/cgf.142634}}, volume = {{40}}, year = {{2021}}, } @article{60375, abstract = {{AbstractA common approach to automatic quad layout generation on surfaces is to, in a first stage, decide on the positioning of irregular layout vertices, followed by finding sensible layout edges connecting these vertices and partitioning the surface into quadrilateral patches in a second stage. While this two‐step approach reduces the problem's complexity, this separation also limits the result quality. In the worst case, the set of layout vertices fixed in the first stage without consideration of the second may not even permit a valid quad layout. We propose an algorithm for the creation of quad layouts in which the initial layout vertices can be adjusted in the second stage. Whenever beneficial for layout quality or even validity, these vertices may be moved within a prescribed radius or even be removed. Our algorithm is based on a robust quantization strategy, turning a continuous T‐mesh structure into a discrete layout. We show the effectiveness of our algorithm on a variety of inputs.}}, author = {{Lyon, Max and Campen, Marcel and Kobbelt, Leif}}, issn = {{0167-7055}}, journal = {{Computer Graphics Forum}}, number = {{5}}, pages = {{169--180}}, publisher = {{Wiley}}, title = {{{Simpler Quad Layouts using Relaxed Singularities}}}, doi = {{10.1111/cgf.14365}}, volume = {{40}}, year = {{2021}}, } @article{60386, abstract = {{We propose a novel approach to represent maps between two discrete surfaces of the same genus and to minimize intrinsic mapping distortion. Our maps are well-defined at every surface point and are guaranteed to be continuous bijections (surface homeomorphisms). As a key feature of our approach, only the images of vertices need to be represented explicitly, since the images of all other points (on edges or in faces) are properly defined implicitly. This definition is via unique geodesics in metrics of constant Gaussian curvature. Our method is built upon the fact that such metrics exist on surfaces of arbitrary topology, without the need for any cuts or cones (as asserted by the uniformization theorem). Depending on the surfaces' genus, these metrics exhibit one of the three classical geometries: Euclidean, spherical or hyperbolic. Our formulation handles constructions in all three geometries in a unified way. In addition, by considering not only the vertex images but also the discrete metric as degrees of freedom, our formulation enables us to simultaneously optimize the images of these vertices and images of all other points.}}, author = {{Schmidt, Patrick and Campen, Marcel and Born, Janis and Kobbelt, Leif}}, issn = {{0730-0301}}, journal = {{ACM Transactions on Graphics}}, number = {{4}}, publisher = {{Association for Computing Machinery (ACM)}}, title = {{{Inter-surface maps via constant-curvature metrics}}}, doi = {{10.1145/3386569.3392399}}, volume = {{39}}, year = {{2020}}, } @article{60385, abstract = {{We present a mesh generation algorithm for the curvilinear triangulation of planar domains with piecewise polynomial boundary. The resulting mesh consists of regular, injective higher-order triangular elements and precisely conforms with the domain's curved boundary. No smoothness requirements are imposed on the boundary. Prescribed piecewise polynomial curves in the interior, like material interfaces or feature curves, can be taken into account for precise interpolation by the resulting mesh's edges as well. In its core, the algorithm is based on a novel explicit construction of guaranteed injective Bézier triangles with certain edge curves and edge parametrizations prescribed. Due to the use of only rational arithmetic, the algorithm can optionally be performed using exact number types in practice, so as to provide robustness guarantees.}}, author = {{Mandad, Manish and Campen, Marcel}}, issn = {{0730-0301}}, journal = {{ACM Transactions on Graphics}}, number = {{4}}, publisher = {{Association for Computing Machinery (ACM)}}, title = {{{Bézier guarding}}}, doi = {{10.1145/3386569.3392372}}, volume = {{39}}, year = {{2020}}, } @article{60383, abstract = {{AbstractThe problem of seamless parametrization of surfaces is of interest in the context of structured quadrilateral mesh generation and spline‐based surface approximation. It has been tackled by a variety of approaches, commonly relying on continuous numerical optimization to ultimately obtain suitable parameter domains. We present a general combinatorial seamless parameter domain construction, free from the potential numerical issues inherent to continuous optimization techniques in practice. The domains are constructed as abstract polygonal complexes which can be embedded in a discrete planar grid space, as unions of unit squares. We ensure that the domain structure matches any prescribed parametrization singularities (cones) and satisfies seamlessness conditions. Surfaces of arbitrary genus are supported. Once a domain suitable for a given surface is constructed, a seamless and locally injective parametrization over this domain can be obtained using existing planar disk mapping techniques, making recourse to Tutte's classical embedding theorem.}}, author = {{Zhou, Jiaran and Tu, Changhe and Zorin, Denis and Campen, Marcel}}, issn = {{0167-7055}}, journal = {{Computer Graphics Forum}}, number = {{2}}, pages = {{179--190}}, publisher = {{Wiley}}, title = {{{Combinatorial Construction of Seamless Parameter Domains}}}, doi = {{10.1111/cgf.13922}}, volume = {{39}}, year = {{2020}}, } @article{60382, author = {{Mandad, Manish and Campen, Marcel}}, issn = {{0010-4485}}, journal = {{Computer-Aided Design}}, publisher = {{Elsevier BV}}, title = {{{Efficient piecewise higher-order parametrization of discrete surfaces with local and global injectivity}}}, doi = {{10.1016/j.cad.2020.102862}}, volume = {{127}}, year = {{2020}}, } @article{60388, abstract = {{AbstractIn the field of global surface parametrization a recent focus has been on so‐called seamless parametrization. This term refers to parametrization approaches which, while using an atlas of charts to enable the handling of surfaces of arbitrary topology, relate the parametrization across the cuts between charts via transition functions from special classes of transformations. This effectively makes the cuts invisible to applications which are invariant to these specific transformations in some sense. In actual implementations of these parametrization approaches, however, these restrictions are obeyed only approximately; errors stem from the tolerances of numerical solvers employed and, ultimately, from the limited accuracy of floating point arithmetic. In practice, robustness issues arise from these flaws in the seamlessness of a parametrization, no matter how small. We present a robust global algorithm that turns a given approximately seamless parametrization into an exactly seamless one ‐ that still is representable by standard floating point numbers. It supports common practically relevant additional constraints regarding boundary and feature curve alignment or isocurve connectivity, and ensures that these are likewise fulfilled exactly. This allows subsequent algorithms to operate robustly on the resulting truly seamless parametrization. We believe that the core of our method will furthermore be of benefit in a broader range of applications involving linearly constrained numerical optimization.}}, author = {{Mandad, Manish and Campen, Marcel}}, issn = {{0167-7055}}, journal = {{Computer Graphics Forum}}, number = {{2}}, pages = {{135--145}}, publisher = {{Wiley}}, title = {{{Exact Constraint Satisfaction for Truly Seamless Parametrization}}}, doi = {{10.1111/cgf.13625}}, volume = {{38}}, year = {{2019}}, } @article{60390, abstract = {{ The problem of discrete surface parametrization, i.e. mapping a mesh to a planar domain, has been investigated extensively. We address the more general problem of mapping between surfaces. In particular, we provide a formulation that yields a map between two disk-topology meshes, which is continuous and injective by construction and which locally minimizes intrinsic distortion. A common approach is to express such a map as the composition of two maps via a simple intermediate domain such as the plane, and to independently optimize the individual maps. However, even if both individual maps are of minimal distortion, there is potentially high distortion in the composed map. In contrast to many previous works, we minimize distortion in an end-to-end manner, directly optimizing the quality of the composed map. This setting poses additional challenges due to the discrete nature of both the source and the target domain. We propose a formulation that, despite the combinatorial aspects of the problem, allows for a purely continuous optimization. Further, our approach addresses the non-smooth nature of discrete distortion measures in this context which hinders straightforward application of off-the-shelf optimization techniques. We demonstrate that, despite the challenges inherent to the more involved setting, discrete surface-to-surface maps can be optimized effectively. }}, author = {{Schmidt, Patrick and Born, Janis and Campen, Marcel and Kobbelt, Leif}}, issn = {{0730-0301}}, journal = {{ACM Transactions on Graphics}}, number = {{6}}, pages = {{1--15}}, publisher = {{Association for Computing Machinery (ACM)}}, title = {{{Distortion-minimizing injective maps between surfaces}}}, doi = {{10.1145/3355089.3356519}}, volume = {{38}}, year = {{2019}}, } @article{60389, abstract = {{The generation of quad meshes based on surface parametrization techniques has proven to be a versatile approach. These techniques quantize an initial seamless parametrization so as to obtain an integer grid map implying a pure quad mesh. State-of-the-art methods following this approach have to assume that the surface to be meshed either has no boundary, or has a boundary which the resulting mesh is supposed to be aligned to. In a variety of applications this is not desirable and non-boundary-aligned meshes or grid-parametrizations are preferred. We thus present a technique to robustly generate integer grid maps which are either boundary-aligned, non-boundary-aligned, or partially boundary-aligned, just as required by different applications. We thereby generalize previous work to this broader setting. This enables the reliable generation of trimmed quad meshes with partial elements along the boundary, preferable in various scenarios, from tiled texturing over design and modeling to fabrication and architecture, due to fewer constraints and hence higher overall mesh quality and other benefits in terms of aesthetics and flexibility.}}, author = {{Lyon, Max and Campen, Marcel and Bommes, David and Kobbelt, Leif}}, issn = {{0730-0301}}, journal = {{ACM Transactions on Graphics}}, number = {{4}}, pages = {{1--14}}, publisher = {{Association for Computing Machinery (ACM)}}, title = {{{Parametrization quantization with free boundaries for trimmed quad meshing}}}, doi = {{10.1145/3306346.3323019}}, volume = {{38}}, year = {{2019}}, } @article{60384, abstract = {{Seamless global parametrization of surfaces is a key operation in geometry processing, e.g., for high-quality quad mesh generation. A common approach is to prescribe the parametric domain structure, in particular, the locations of parametrization singularities (cones), and solve a non-convex optimization problem minimizing a distortion measure, with local injectivity imposed through either constraints or barrier terms. In both cases, an initial valid parametrization is essential to serve as a feasible starting point for obtaining an optimized solution. While convexified versions of the constraints eliminate this initialization requirement, they narrow the range of solutions, causing some problem instances that actually do have a solution to become infeasible. We demonstrate that for arbitrary given sets of topologically admissible parametric cones with prescribed curvature, a global seamless parametrization always exists (with the exception of one well-known case). Importantly, our proof is constructive and directly leads to a general algorithm for computing such parametrizations. Most distinctively, this algorithm is bootstrapped with a convex optimization problem (solving for a conformal map), in tandem with a simple linear equation system (determining a seamless modification of this map). This initial map can then serve as a valid starting point and be optimized for low distortion using existing injectivity preserving methods.}}, author = {{Campen, Marcel and Shen, Hanxiao and Zhou, Jiaran and Zorin, Denis}}, issn = {{0730-0301}}, journal = {{ACM Transactions on Graphics}}, number = {{1}}, pages = {{1--19}}, publisher = {{Association for Computing Machinery (ACM)}}, title = {{{Seamless Parametrization with Arbitrary Cones for Arbitrary Genus}}}, doi = {{10.1145/3360511}}, volume = {{39}}, year = {{2019}}, } @inproceedings{60448, author = {{Lim, Isaak and Dielen, Alexander and Campen, Marcel and Kobbelt, Leif}}, booktitle = {{Computer Vision - ECCV 2018 Workshops - Munich, Germany, September 8-14, 2018, Proceedings, Part III}}, editor = {{Leal-Taixé, Laura and Roth, Stefan}}, pages = {{349–362}}, publisher = {{Springer}}, title = {{{A Simple Approach to Intrinsic Correspondence Learning on Unstructured 3D Meshes}}}, doi = {{10.1007/978-3-030-11015-4_26}}, volume = {{11131}}, year = {{2018}}, } @article{60391, author = {{Zhou, Jiaran and Campen, Marcel and Zorin, Denis and Tu, Changhe and Silva, Claudio T.}}, issn = {{0167-8396}}, journal = {{Computer Aided Geometric Design}}, pages = {{3--15}}, publisher = {{Elsevier BV}}, title = {{{Quadrangulation of non-rigid objects using deformation metrics}}}, doi = {{10.1016/j.cagd.2018.03.003}}, volume = {{62}}, year = {{2018}}, } @article{60399, abstract = {{A variety of techniques were proposed to model smooth surfaces based on tensor product splines (e.g. subdivision surfaces, free-form splines, T-splines). Conversion of an input surface into such a representation is commonly achieved by constructing a global seamless parametrization, possibly aligned to a guiding cross-field (e.g. of principal curvature directions), and using this parametrization as domain to construct the spline-based surface. One major fundamental difficulty in designing robust algorithms for this task is the fact that for common types, e.g. subdivision surfaces (requiring a conforming domain mesh) or T-spline surfaces (requiring a globally consistent knot interval assignment) reliably obtaining a suitable parametrization that has the same topological structure as the guiding field poses a major challenge. Even worse, not all fields do admit suitable parametrizations, and no concise conditions are known as to which fields do. We present a class of surface constructions (T-splines with halfedge knots ) and a class of parametrizations ( seamless similarity maps ) that are, in a sense, a perfect match for the task: for any given guiding field structure, a compatible parametrization of this kind exists and a smooth piecewise rational surface with exactly the same structure as the input field can be constructed from it. As a byproduct, this enables full control over extraordinary points. The construction is backward compatible with classical NURBS. We present efficient algorithms for building discrete conformal similarity maps and associated T-meshes and T-spline surfaces. }}, author = {{Campen, Marcel and Zorin, Denis}}, issn = {{0730-0301}}, journal = {{ACM Transactions on Graphics}}, number = {{4}}, pages = {{1--16}}, publisher = {{Association for Computing Machinery (ACM)}}, title = {{{Similarity maps and field-guided T-splines}}}, doi = {{10.1145/3072959.3073647}}, volume = {{36}}, year = {{2017}}, } @article{60398, abstract = {{AbstractThe efficient and practical representation and processing of geometrically or topologically complex shapes often demands a partitioning into simpler patches. Possibilities range from unstructured arrangements of arbitrarily shaped patches on the one end, to highly structured conforming networks of all‐quadrilateral patches on the other end of the spectrum. Due to its regularity, this latter extreme of conforming partitions with quadrilateral patches, called quad layouts, is most beneficial in many application scenarios, for instance enabling the use of tensor‐product representations based on splines or Bézier patches, grid‐based multi‐resolution techniques and discrete pixel‐based map representations. However, this type of partition is also most complicated to create due to the strict inherent structural restrictions. Traditionally often performed manually in a tedious and demanding process, research in computer graphics and geometry processing has led to a number of computer‐assisted, semi‐automatic, as well as fully automatic approaches to address this problem more efficiently. This survey provides a detailed discussion of this range of methods, treats their strengths and weaknesses and outlines open problems in this field of research.}}, author = {{Campen, Marcel}}, issn = {{0167-7055}}, journal = {{Computer Graphics Forum}}, number = {{8}}, pages = {{567--588}}, publisher = {{Wiley}}, title = {{{Partitioning Surfaces Into Quadrilateral Patches: A Survey}}}, doi = {{10.1111/cgf.13153}}, volume = {{36}}, year = {{2017}}, } @unpublished{60406, abstract = {{An algorithm for the computation of global discrete conformal parametrizations with prescribed global holonomy signatures for triangle meshes was recently described in [Campen and Zorin 2017]. In this paper we provide a detailed analysis of convergence and correctness of this algorithm. We generalize and extend ideas of [Springborn et al. 2008] to show a connection of the algorithm to Newton's algorithm applied to solving the system of constraints on angles in the parametric domain, and demonstrate that this system can be obtained as a gradient of a convex energy.}}, author = {{Campen, Marcel and Zorin, Denis}}, booktitle = {{arXiv:1705.02422}}, title = {{{On Discrete Conformal Seamless Similarity Maps}}}, year = {{2017}}, } @article{60397, author = {{Campen, Marcel}}, issn = {{0272-1716}}, journal = {{IEEE Computer Graphics and Applications}}, number = {{3}}, pages = {{88--95}}, publisher = {{Institute of Electrical and Electronics Engineers (IEEE)}}, title = {{{Tiling the Bunny: Quad Layouts for Efficient 3D Geometry Representation}}}, doi = {{10.1109/mcg.2017.35}}, volume = {{37}}, year = {{2017}}, }