Search Results

Now showing 1 - 10 of 17
  • Item
    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.
  • Item
    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.
  • Item
    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.
  • Item
    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.
  • Item
    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.
  • Item
    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.
  • Item
    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.
  • Item
    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.
  • Item
    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.
  • Item
    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.