43-Issue 5

Permanent URI for this collection

https://diglib.eg.org/handle/10.2312/3607011

Browse

Now showing 1 - 17 of 17

1-Lipschitz Neural Distance Fields
(The Eurographics Association and John Wiley & Sons Ltd., 2024) Coiffier, Guillaume; Béthune, Louis; Hu, Ruizhen; Lefebvre, Sylvain
Neural implicit surfaces are a promising tool for geometry processing that represent a solid object as the zero level set of a neural network. Usually trained to approximate a signed distance function of the considered object, these methods exhibit great visual fidelity and quality near the surface, yet their properties tend to degrade with distance, making geometrical queries hard to perform without the help of complex range analysis techniques. Based on recent advancements in Lipschitz neural networks, we introduce a new method for approximating the signed distance function of a given object. As our neural function is made 1- Lipschitz by construction, it cannot overestimate the distance, which guarantees robustness even far from the surface. Moreover, the 1-Lipschitz constraint allows us to use a different loss function, called the hinge-Kantorovitch-Rubinstein loss, which pushes the gradient as close to unit-norm as possible, thus reducing computation costs in iterative queries. As this loss function only needs a rough estimate of occupancy to be optimized, this means that the true distance function need not to be known. We are therefore able to compute neural implicit representations of even bad quality geometry such as noisy point clouds or triangle soups. We demonstrate that our methods is able to approximate the distance function of any closed or open surfaces or curves in the plane or in space, while still allowing sphere tracing or closest point projections to be performed robustly.
Anisotropy and Cross Fields
(The Eurographics Association and John Wiley & Sons Ltd., 2024) Simons, Lance; Amenta, Nina; Hu, Ruizhen; Lefebvre, Sylvain
We consider a cross field, possibly with singular points of valence 3 or 5, in which all streamlines are finite, and either end on the boundary or form cycles. We show that we can always assign lengths to the two cross field directions to produce an anisotropic orthogonal frame field. There is a one-dimensional family of such length functions, and we optimize within this family so that the two lengths are everywhere as similar as possible. This gives a numerical bound on the minimal anisotropy of any quad mesh exactly following the input cross field. We also show how to remove some limit cycles.
Cascading Upper Bounds for Triangle Soup Pompeiu-Hausdorff Distance
(The Eurographics Association and John Wiley & Sons Ltd., 2024) Sacht, Leonardo; Jacobson, Alec; Hu, Ruizhen; Lefebvre, Sylvain
We propose a new method to accurately approximate the Pompeiu-Hausdorff distance from a triangle soup A to another triangle soup B up to a given tolerance. Based on lower and upper bound computations, we discard triangles from A that do not contain the maximizer of the distance to B and subdivide the others for further processing. In contrast to previous methods, we use four upper bounds instead of only one, three of which newly proposed by us. Many triangles are discarded using the simpler bounds, while the most difficult cases are dealt with by the other bounds. Exhaustive testing determines the best ordering of the four upper bounds. A collection of experiments shows that our method is faster than all previous accurate methods in the literature.
Coverage Axis++: Efficient Inner Point Selection for 3D Shape Skeletonization
(The Eurographics Association and John Wiley & Sons Ltd., 2024) Wang, Zimeng; Dou, Zhiyang; Xu, Rui; Lin, Cheng; Liu, Yuan; Long, Xiaoxiao; Xin, Shiqing; Komura, Taku; Yuan, Xiaoming; Wang, Wenping; Hu, Ruizhen; Lefebvre, Sylvain
We introduce Coverage Axis++, a novel and efficient approach to 3D shape skeletonization. The current state-of-the-art approaches for this task often rely on the watertightness of the input [LWS*15; PWG*19; PWG*19] or suffer from substantial computational costs [DLX*22; CD23], thereby limiting their practicality. To address this challenge, Coverage Axis++ proposes a heuristic algorithm to select skeletal points, offering a high-accuracy approximation of the Medial Axis Transform (MAT) while significantly mitigating computational intensity for various shape representations. We introduce a simple yet effective strategy that considers shape coverage, uniformity, and centrality to derive skeletal points. The selection procedure enforces consistency with the shape structure while favoring the dominant medial balls, which thus introduces a compact underlying shape representation in terms of MAT. As a result, Coverage Axis++ allows for skeletonization for various shape representations (e.g., water-tight meshes, triangle soups, point clouds), specification of the number of skeletal points, few hyperparameters, and highly efficient computation with improved reconstruction accuracy. Extensive experiments across a wide range of 3D shapes validate the efficiency and effectiveness of Coverage Axis++. Our codes are available at https://github.com/Frank-ZY-Dou/Coverage_Axis.
Cut-Cell Microstructures for Two-scale Structural Optimization
(The Eurographics Association and John Wiley & Sons Ltd., 2024) Tozoni, Davi Colli; Huang, Zizhou; Panozzo, Daniele; Zorin, Denis; Hu, Ruizhen; Lefebvre, Sylvain
Two-scale topology optimization, combined with the design of microstructure families with a broad range of effective material parameters, is widely used in many fabrication applications to achieve a target deformation behavior for a variety of objects. The main idea of this approach is to optimize the distribution of material properties in the object partitioned into relatively coarse cells, and then replace each cell with microstructure geometry that mimics these material properties. In this paper, we focus on adapting this approach to complex shapes in situations when preserving the shape's surface is essential. Our approach extends any regular (i.e. defined on a regular lattice grid) microstructure family to complex shapes, by enriching it with tiles adapted to the geometry of the cut-cell. We propose a fully automated and robust pipeline based on this approach, and we show that the performance of the regular microstructure family is only minimally affected by our extension while allowing its use on 2D and 3D shapes of high complexity.
Distance-Based Smoothing of Curves on Surface Meshes
(The Eurographics Association and John Wiley & Sons Ltd., 2024) Pawellek, Markus; Rössl, Christian; Lawonn, Kai; Hu, Ruizhen; Lefebvre, Sylvain
The smoothing of surface curves is an essential tool in mesh processing, important to applications that require segmenting and cutting surfaces such as surgical planning. Surface curves are typically designed by professionals to match certain surface features. For this reason, the smoothed curves should be close to the original and easily adjustable by the user in interactive tools. Previous methods achieve this desired behavior, e.g., by utilizing energy-minimizing splines or generalizations of Bézier splines, which require a significant number of control points and may not provide interactive frame rates or numerical stability. This paper presents a new algorithm for robust smoothing of discrete surface curves on triangular surface meshes. By using a scalar penalty potential as the fourth coordinate, the given surface mesh is embedded into the 4D Euclidean space. Our method is based on finding geodesics in this lifted surface, which are then projected back onto the original 3D surface. The benefits of this approach include guaranteed convergence and good approximation of the initial curve. We propose a family of penalty potentials with one single parameter for adjusting the trade-off between smoothness and similarity. The implementation of our method is straightforward as we rely on existing methods for computing geodesics and penalty fields. We evaluate our implementation and confirm its robustness and efficiency.
Entropy-driven Progressive Compression of 3D Point Clouds
(The Eurographics Association and John Wiley & Sons Ltd., 2024) Zampieri, Armand; Delarue, Guillaume; Bakr, Nachwa Abou; Alliez, Pierre; Hu, Ruizhen; Lefebvre, Sylvain
3D point clouds stand as one of the prevalent representations for 3D data, offering the advantage of closely aligning with sensing technologies and providing an unbiased representation of a measured physical scene. Progressive compression is required for real-world applications operating on networked infrastructures with restricted or variable bandwidth. We contribute a novel approach that leverages a recursive binary space partition, where the partitioning planes are not necessarily axis-aligned and optimized via an entropy criterion. The planes are encoded via a novel adaptive quantization method combined with prediction. The input 3D point cloud is encoded as an interlaced stream of partitioning planes and number of points in the cells of the partition. Compared to previous work, the added value is an improved rate-distortion performance, especially for very low bitrates. The latter are critical for interactive navigation of large 3D point clouds on heterogeneous networked infrastructures.
Integer-Sheet-Pump Quantization for Hexahedral Meshing
(The Eurographics Association and John Wiley & Sons Ltd., 2024) Brückler, Hendrik; Bommes, David; Campen, Marcel; Hu, Ruizhen; Lefebvre, Sylvain
Several state-of-the-art algorithms for semi-structured hexahedral meshing involve a so called quantization step to decide on the integer DoFs of the meshing problem, corresponding to the number of hexahedral elements to embed into certain regions of the domain. Existing reliable methods for quantization are based on solving a sequence of integer quadratic programs (IQP). Solving these in a timely and predictable manner with general-purpose solvers is a challenge, even more so in the open-source field. We present here an alternative robust and efficient quantization scheme that is instead based on solving a series of continuous linear programs (LP), for which solver availability and efficiency are not an issue. In our formulation, such LPs are used to determine where inflation or deflation of virtual hexahedral sheets are favorable. We compare our method to two implementations of the former IQP formulation (using a commercial and an open-source MIP solver, respectively), finding that (a) the solutions found by our method are near-optimal or optimal in most cases, (b) these solutions are found within a much more predictable time frame, and (c) the state of the art run time is outperformed, in the case of using the open-source solver by orders of magnitude.
KerGen: A Kernel Computation Algorithm for 3D Polygon Meshes
(The Eurographics Association and John Wiley & Sons Ltd., 2024) Asiler, Merve; Sahillioglu, Yusuf; Hu, Ruizhen; Lefebvre, Sylvain
We compute the kernel of a shape embedded in 3D as a polygon mesh, which is defined as the set of all points that have a clear line of sight to every point of the mesh. The KerGen algorithm, short for Kernel Generation, employs efficient plane-plane and line-plane intersections, alongside point classifications based on their positions relative to planes. This approach allows for the incremental addition of kernel vertices and edges to the resulting set in a simple and systematic way. The output is a polygon mesh that represents the surface of the kernel. Extensive comparisons with the existing methods, CGAL and Polyhedron Kernel, demonstrate the remarkable timing performance of our novel additive kernel computation method. Yet another advantage of our additive process is the availability of the partial kernel at any stage, making it useful for specific geometry processing applications such as star decomposition and castable shape reconstruction.
Mesh Parameterization Meets Intrinsic Triangulations
(The Eurographics Association and John Wiley & Sons Ltd., 2024) Akalin, Koray; Finnendahl, Ugo; Sorkine-Hornung, Olga; Alexa, Marc; Hu, Ruizhen; Lefebvre, Sylvain
A parameterization of a triangle mesh is a realization in the plane so that all triangles have positive signed area. Triangle mesh parameterizations are commonly computed by minimizing a distortion energy, measuring the distortions of the triangles as they are mapped into the parameter domain. It is assumed that the triangulation is fixed and the triangles are mapped affinely. We consider a more general setup and additionally optimize among the intrinsic triangulations of the piecewise linear input geometry. This means the distortion energy is computed for the same geometry, yet the space of possible parameterizations is enlarged. For minimizing the distortion energy, we suggest alternating between varying the parameter locations of the vertices and intrinsic flipping. We show that this process improves the mapping for different distortion energies at moderate additional cost. We also find intrinsic triangulations that are better starting points for the optimization of positions, offering a compromise between the full optimization approach and exploiting the additional freedom of intrinsic triangulations.
On Shape Design and Optimization of Gerotor Pumps
(The Eurographics Association and John Wiley & Sons Ltd., 2024) Pareja-Corcho, Juan C.; Barton, Michael; Pedrera-Busselo, Asier; Mejia-Parra, Daniel; Moreno, Aitor; Posada, Jorge; Hu, Ruizhen; Lefebvre, Sylvain
A gerotor pump is a two-piece mechanism where two rotational components, interior and exterior, engage each other via a rotational motion to transfer a fluid in a direction parallel to their rotational axes. A natural question arises on what shape of the gerotor is the optimal one in the sense of maximum fluid being pumped for a unit of time, given the constraint of a fixed material needed to manufacture the pump. As there is no closed-formula to answer this question, we propose a new algorithm to design and optimize the shape of gerotor pumps to be as efficient as possible. The proposed algorithm is based on a fast construction of the envelope of the interior component and subsequent optimization. We demonstrate our algorithm on a benchmark gerotor and show that the optimized solution increases the estimated flowrate by 16%. We also use our algorithm to study the effect of the number of teeth on the cavity area of a gerotor.
Optimized Dual-Volumes for Tetrahedral Meshes
(The Eurographics Association and John Wiley & Sons Ltd., 2024) Jacobson, Alec; Hu, Ruizhen; Lefebvre, Sylvain
Constructing well-behaved Laplacian and mass matrices is essential for tetrahedral mesh processing. Unfortunately, the de facto standard linear finite elements exhibit bias on tetrahedralized regular grids, motivating the development of finite-volume methods. In this paper, we place existing methods into a common construction, showing how their differences amount to the choice of simplex centers. These choices lead to satisfaction or breakdown of important properties: continuity with respect to vertex positions, positive semi-definiteness of the implied Dirichlet energy, positivity of the mass matrix, and unbiased-ness on regular grids. Based on this analysis, we propose a new method for constructing dual-volumes which explicitly satisfy all of these properties via convex optimization.
Reconstructing Curves from Sparse Samples on Riemannian Manifolds
(The Eurographics Association and John Wiley & Sons Ltd., 2024) Marin, Diana; Maggioli, Filippo; Melzi, Simone; Ohrhallinger, Stefan; Wimmer, Michael; Hu, Ruizhen; Lefebvre, Sylvain
Reconstructing 2D curves from sample points has long been a critical challenge in computer graphics, finding essential applications in vector graphics. The design and editing of curves on surfaces has only recently begun to receive attention, primarily relying on human assistance, and where not, limited by very strict sampling conditions. In this work, we formally improve on the state-of-the-art requirements and introduce an innovative algorithm capable of reconstructing closed curves directly on surfaces from a given sparse set of sample points. We extend and adapt a state-of-the-art planar curve reconstruction method to the realm of surfaces while dealing with the challenges arising from working on non-Euclidean domains. We demonstrate the robustness of our method by reconstructing multiple curves on various surface meshes. We explore novel potential applications of our approach, allowing for automated reconstruction of curves on Riemannian manifolds.
Search Me Knot, Render Me Knot: Embedding Search and Differentiable Rendering of Knots in 3D
(The Eurographics Association and John Wiley & Sons Ltd., 2024) Gangopadhyay, Aalok; Gupta, Paras; Sharma, Tarun; Singh, Prajwal; Raman, Shanmuganathan; Hu, Ruizhen; Lefebvre, Sylvain
We introduce the problem of knot-based inverse perceptual art. Given multiple target images and their corresponding viewing configurations, the objective is to find a 3D knot-based tubular structure whose appearance resembles the target images when viewed from the specified viewing configurations. To solve this problem, we first design a differentiable rendering algorithm for rendering tubular knots embedded in 3D for arbitrary perspective camera configurations. Utilizing this differentiable rendering algorithm, we search over the space of knot configurations to find the ideal knot embedding. We represent the knot embeddings via homeomorphisms of the desired template knot, where the weights of an invertible neural network parametrize the homeomorphisms. Our approach is fully differentiable, making it possible to find the ideal 3D tubular structure for the desired perceptual art using gradient-based optimization. We propose several loss functions that impose additional physical constraints, enforcing that the tube is free of self-intersection, lies within a predefined region in space, satisfies the physical bending limits of the tube material, and the material cost is within a specified budget. We demonstrate through results that our knot representation is highly expressive and gives impressive results even for challenging target images in both single-view and multiple-view constraints. Through extensive ablation study, we show that each proposed loss function effectively ensures physical realizability. We construct a real-world 3D-printed object to demonstrate the practical utility of our approach.
SGP 2024 CGF 43-5: Frontmatter
(The Eurographics Association and John Wiley & Sons Ltd., 2024) Hu, Ruizhen; Lefebvre, Sylvain; Hu, Ruizhen; Lefebvre, Sylvain
Stability for Inference with Persistent Homology Rank Functions
(The Eurographics Association and John Wiley & Sons Ltd., 2024) Wang, Qiquan; García-Redondo, Inés; Faugère, Pierre; Henselman-Petrusek, Gregory; Monod, Anthea; Hu, Ruizhen; Lefebvre, Sylvain
Persistent homology barcodes and diagrams are a cornerstone of topological data analysis that capture the ''shape'' of a wide range of complex data structures, such as point clouds, networks, and functions. However, their use in statistical settings is challenging due to their complex geometric structure. In this paper, we revisit the persistent homology rank function, which is mathematically equivalent to a barcode and persistence diagram, as a tool for statistics and machine learning. Rank functions, being functions, enable the direct application of the statistical theory of functional data analysis (FDA)-a domain of statistics adapted for data in the form of functions. A key challenge they present over barcodes in practice, however, is their lack of stability-a property that is crucial to validate their use as a faithful representation of the data and therefore a viable summary statistic. In this paper, we fill this gap by deriving two stability results for persistent homology rank functions under a suitable metric for FDA integration. We then study the performance of rank functions in functional inferential statistics and machine learning on real data applications, in both single and multiparameter persistent homology. We find that the use of persistent homology captured by rank functions offers a clear improvement over existing non-persistence-based approaches.
Winding Number Features for Vector Sketch Colorization
(The Eurographics Association and John Wiley & Sons Ltd., 2024) Scrivener, Daniel; Coldren, Ellis; Chien, Edward; Hu, Ruizhen; Lefebvre, Sylvain
Vector sketch software (e.g. Adobe Illustrator, Inkscape) and touch-interactive technologies have long aided artists in the creation of resolution-independent digital drawings that mimic the unconstrained nature of freehand sketches. However, artist intent behind stroke topology is often ambiguous, complicating traditional segmentation tasks such as coloring. For inspiration, we turn to the winding number, a classic geometric property of interest for binary segmentation in the presence of boundary data. Its direct application for multi-region segmentation poses two main challenges: (1) strokes may not be consistently oriented to best identify perceptually salient regions; (2) for interior strokes there is no ''correct'' orientation, as either choice better distinguishes one of two neighboring regions. Thus, we form a harmonic feature space from multiple winding number fields and perform segmentation via Voronoi/power diagrams in this domain. Our perspective allows both for automatic fill region detection and for a semi-automatic framework that naturally incorporates user hints and interactive sculpting of results, unlike competing automatic methods. Our method is agnostic to curve orientation and gracefully handles varying gap sizes in the sketch boundary, outperforming state-of-the-art colorization methods on these ''gappy'' inputs. Moreover, it inherits the ability of winding numbers to specify ''fuzzy'' boundaries, leading to simple strategies for color diffusion and single-parameter-driven growing and shrinking of regions.

Browse

Browsing 43-Issue 5 by Title

Results Per Page

Sort Options