Sharp feature lines provide critical structural information in 3D models and are essential for geometric processing. However, the performance of existing algorithms for extracting feature lines from point clouds remains sensitive to the quality of the input data. This paper introduces an algorithm specifically designed to extract feature lines from 3D point clouds. The algorithm calculates the winding number for each point and uses variations in this number within edge regions to identify feature points. These feature points are then mapped onto a cuboid structure to obtain key feature points and capture neighboring relationships. Finally, feature lines are fitted based on the connectivity of key feature points. Extensive experiments demonstrate that this algorithm not only accurately detects feature points on potential sharp edges, but also outperforms existing methods in extracting subtle feature lines and handling complex point clouds.

Vector graphics are widely used in areas such as logo design and digital painting, including both stroked and filled paths as primitives. GPU-based rendering for filled paths already has well-established solutions. Due to the complexity of stroked paths, existing methods often render them by approximating strokes with filled shapes. However, the performance of existing methods still leaves room for improvement. This paper designs a GPU-accelerated rendering algorithm along with a curvature-guided parallel adaptive subdivision method to accurately and efficiently render stroke areas. Additionally, we propose an efficient Newton iteration-based method for arc-length parameterization of quadratic curves, along with an error estimation technique. This enables a parallel rendering approach for dashed stroke styles and arc-length guided texture filling. Experimental results show that our method achieves average speedups of 3 . 4 × for rendering quadratic stroked paths and 2 . 5 × for rendering quadratic dashed strokes, compared to the best existing approaches.

The creation of computational agents capable of generating computer-aided design (CAD) models that rival those produced by professional designers is a pressing challenge in the field of computational design. The key obstacle is the need to generate a large number of realistic and diverse models while maintaining control over the output to a certain degree. Therefore, we propose a novel CAD model generation network called CADTrans which is based on a code tree-guided transformer framework to autoregressively generate CAD construction sequences. Firstly, three regularized discrete codebooks are extracted through vector quantized adversarial learning, with each codebook respectively representing the features of Loop, Profile, and Solid. Secondly, these codebooks are used to normalize a CAD construction sequence into a structured code tree representation which is then used to train a standard transformer network to reconstruct the code tree. Finally, the code tree is used as global information to guide the sketch-and-extrude method to recover the corresponding geometric information, thereby reconstructing the complete CAD model. Extensive experiments demonstrate that CADTrans achieves state-of-the-art performance, generating higher-quality, more varied, and complex models. Meanwhile, it provides more possibilities for CAD applications through its flexible control method, enabling users to quickly experiment with different design schemes, inspiring diverse design ideas and the generation of a wide variety of models or even inspiring models, thereby improving design efficiency and promoting creativity. The code is available at https://effieguoxufei.github.io/CADtrans/ .

We introduce RMAvatar, a novel human avatar representation with Gaussian splatting embedded on mesh to learn clothed avatar from a monocular video. We utilize the explicit mesh geometry to represent motion and shape of a virtual human and implicit appearance rendering with Gaussian Splatting. Our method consists of two main modules: Gaussian initialization module and Gaussian rectification module. We embed Gaussians into triangular faces and control their motion through the mesh, which ensures low-frequency motion and surface deformation of the avatar. Due to the limitations of LBS formula, the human skeleton is hard to control complex non-rigid transformations. We then design a pose-related Gaussian rectification module to learn fine-detailed non-rigid deformations, further improving the realism and expressiveness of the avatar. We conduct extensive experiments on public datasets, and RMAvatar shows state-of-the-art performance on both rendering quality and quantitative evaluations. Please see our project page at https://rm-avatar.github.io .

Portraits near the periphery of wide-angle photos often suffer conspicuous distortions. With the popularity of wide-angle lenses on mobile phones, portrait correction, which removes portrait distortion in wide-angle photos, has attracted widespread attention as a form of content-aware warping. Existing portrait correction methods for wide-angle photos using uniform quad meshes take a long time to optimize the correction. Most of them focus only on correcting facial distortions, leading to inconsistency between people's heads and bodies after correction. This study proposes an efficient method to remove portrait distortions in wide-angle perspective photos, based on a triangle mesh. We generate an adaptive mesh tailored to the image content with relatively few vertices. According to the characteristics of the triangle mesh, we tailor three smooth and intuitive energy terms for the human area, background area, and boundary to minimize portrait distortions. Our algorithm can easily be extended to allow further geometric constraints, such as line constraints. Experimental results show that our method is robust for photos with various fields of view. Comparisons to the state-of-the-art demonstrate that our method achieves significant improvements in optimization efficiency and consistency of heads and bodies.

We present an efficient approach to generating uniformly distributed resampling points of raw 3D point clouds. A key contribution for making such a resampling method both practical and efficient is the construction of the centroidal Voronoi tessellation on the given point cloud efficiently achieved by applying the proposed Anderson-accelerated Lloyd's method. The calculations involved in the method are mainly carried out over a group of locally approximated quadratic surfaces, instead of directly on the given point cloud, providing us a great advantage in filtering out the affection of distribution of original points on output results. Once the resampling points are initialized, the resampling quality can be improved progressively by optimizing resampling points and updating the local approximated surfaces. In addition, by restricting the movement of resampling points, we can deal with unclosed point clouds without any boundary detection. Our approach outperforms existing resampling methods in generating uniform results, and extensive experiments are conducted to demonstrate its efficacy.

Abstract Image triangulation methods, which decompose an image into a series of triangles, are fundamental in artistic creation and image processing. This paper introduces a novel framework that integrates cubic Bézier curves into image triangulation, enabling the precise reconstruction of curved image features. Our developed framework constructs a well‐structured curved triangle mesh, effectively preventing overlaps between curves. A refined energy function, grounded in differentiable rendering, establishes a direct link between mesh geometry and rendering effects and is instrumental in guiding the curved mesh generation. Additionally, we derive an explicit gradient formula with respect to mesh parameters, facilitating the adaptive and efficient optimization of these parameters to fully leverage the capabilities of cubic Bézier curves. Through experimental and comparative analyses with state‐of‐the‐art methods, our approach demonstrates a significant enhancement in both numerical accuracy and visual quality.

Feature lines play a pivotal role in the reconstruction of CAD models. Currently, there is a lack of a robust explicit reconstruction algorithm capable of achieving sharp feature reconstruction in point clouds with noise and non-uniformity. In this paper, we propose a feature-preserving CAD model surface reconstruction algorithm, named FACE. The algorithm initiates with preprocessing the point cloud through denoising and resampling steps, resulting in a high-quality point cloud that is devoid of noise and uniformly distributed. Then, it employs discrete optimal transport to detect feature regions and subsequently generates dense points along potential feature lines to enhance features. Finally, the advancing-front surface reconstruction method, based on normal vector directions, is applied to reconstruct the enhanced point cloud. Extensive experiments demonstrate that, for contaminated point clouds, this algorithm excels not only in reconstructing straight edges and corner points but also in handling curved edges and surfaces, surpassing existing methods.

Feature-preserving mesh reconstruction from point clouds is challenging. Implicit methods tend to fit smooth surfaces and cannot be used to reconstruct sharp features. Explicit reconstruction methods are sensitive to noise and only interpolate sharp features when points are distributed on feature lines. We propose a watertight surface reconstruction method based on optimal transport that can accurately reconstruct sharp features often present in CAD models. We formalize the surface reconstruction problem by minimizing the optimal transport cost between the point cloud and the reconstructed surface. The algorithm consists of initialization and refinement steps. In the initialization step, the convex hull of the point cloud is deformed under the guidance of a transport plan to obtain an initial approximate surface. Next, the mesh surface was optimized using operations including vertex relocation and edge collapses/flips to obtain feature-preserving results. Experiments demonstrate that our method can preserve sharp features while being robust to noise and missing data.

Volumetric data abounds in medical imaging and other fields. With the improved imaging quality and the increased resolution, volumetric datasets are getting so large that the existing tools have become inadequate for processing and analyzing the data. Here we consider the problem of computing tetrahedral meshes to represent large volumetric datasets with labeled multiple materials, which are often encountered in medical imaging or microscopy optical slice tomography. Such tetrahedral meshes are a more compact and expressive geometric representation so are in demand for efficient visualization and simulation of the data, which are impossible if the original large volumetric data are used directly due to the large memory requirement. Existing methods for meshing volumetric data are not scalable for handling large datasets due to their sheer demand on excessively large run-time memory or failure to produce a tet-mesh that preserves the multi-material structure of the original volumetric data. In this article we propose a novel approach, called Marching Windows, that uses a moving window and a disk-swap strategy to reduce the run-time memory footprint, devise a new scheme that guarantees to preserve the topological structure of the original dataset, and adopt an error-guided optimization technique to improve both geometric approximation error and mesh quality. Extensive experiments show that our method is capable of processing very large volumetric datasets beyond the capability of the existing methods and producing tetrahedral meshes of high quality.

Style transfer is a popular research topic in the field of computer vision. In 3D stylization, a mesh model is deformed to achieve a specific geometric style. We explore a general neural style transfer framework for 3D meshes that can transfer multiple geometric styles from other meshes to the current mesh. Our stylization network is based on a pre-trained MeshNet model, from which content representation and Gram-based style representation are extracted. By constraining the similarity in content and style representation between the generated mesh and two different meshes, our network can generate a deformed mesh with a specific style while maintaining the content of the original mesh. Experiments verify the robustness of the proposed network and show the effectiveness of stylizing multiple models with one dedicated style mesh. We also conduct ablation experiments to analyze the effectiveness of our network.

Abstract Image triangulation aims to generate an optimal partition with triangular elements to represent the given image. One bottleneck in ensuring approximation quality between the original image and a piecewise approximation over the triangulation is the inaccurate alignment of straight edges to the curved features. In this paper, we propose a novel variational method called curved optimal triangulation, where not all edges are straight segments, but may also be quadratic Bézier curves. The energy function is defined as the total approximation error determined by vertex locations, connectivity and bending of edges. The gradient formulas of this function are derived explicitly in closed form to optimize the energy function efficiently. We test our method on several models to demonstrate its efficacy and ability in preserving features. We also explore its applications in the automatic generation of stylization and Lowpoly images. With the same number of vertices, our curved optimal triangulation method generates more accurate and visually pleasing results compared with previous methods that only use straight segments.

Vector image representation methods that can faithfully reconstruct objects and color variations in a raster image are desired in many practical applications. This article presents triangular configuration B-spline (referred to as TCB-spline)-based vector graphics for raster image vectorization. Based on this new representation, an automatic raster image vectorization paradigm is proposed. The proposed framework first detects sharp curvilinear features in the image and constructs knot meshes based on the detected feature lines. It iteratively optimizes color and position of control points and updates the knot meshes. By using collinear knots at feature lines, both smooth and discontinuous color variations can be efficiently modeled by the same set of quadratic TCB-splines. A variational knot mesh generation method is designed to adaptively introduce knots and update their connectivity to satisfy the local reconstruction quality. Experiments and comparisons show that our framework outperforms the existing state-of-the-art methods in providing more faithful reconstruction results. In particular, our method is able to model undetected features and subtle or complicated color variations in-between features, which the previous methods cannot handle efficiently. Our vectorization representation also facilitates a variety of editing operations performed directly over vector images.

Video over-segmentation into supervoxels is an important pre-processing technique for many computer vision tasks. Videos are an order of magnitude larger than images. Most existing methods for generating supervovels are either memory- or time-inefficient, which limits their application in subsequent video processing tasks. In this paper, we present an anisotropic supervoxel method, which is memory-efficient and can be executed on the graphics processing unit (GPU). Therefore, our algorithm achieves good balance among segmentation quality, memory usage and processing time. In order to provide accurate segmentation for moving objects in video, we use the optical flow information to design a brand new non-Euclidean metric to calculate the anisotropic distances between seeds and voxels. To efficiently compute the anisotropic metric, we adjust the classic jump flooding algorithm (which is designed for parallel execution on the GPU) to generate anisotropic Voronoi tessellation in the combined color and spatio-temporal space. We evaluate our method and the representative supervoxel algorithms for their capability on segmentation performance, computation speed and memory efficiency. We also apply supervoxel results to the application of foreground propagation in videos to test the performance on solving practical problems. Experiments show that our algorithm is much faster than the existing methods, and achieves good balance on segmentation quality and efficiency.

Abstract Superpixel segmentation is a popular image pre‐processing technique in many computer vision applications. In this paper, we present a novel superpixel generation algorithm by agglomerative clustering with quadratic error minimization. We use a quadratic error metric (QEM) to measure the difference of spatial compactness and colour homogeneity between superpixels. Based on the quadratic function, we propose a bottom‐up greedy clustering algorithm to obtain higher quality superpixel segmentation. There are two steps in our algorithm: merging and swapping. First, we calculate the merging cost of two superpixels and iteratively merge the pair with the minimum cost until the termination condition is satisfied. Then, we optimize the boundary of superpixels by swapping pixels according to their swapping cost to improve the compactness. Due to the quadratic nature of the energy function, each of these atomic operations has only O(1) time complexity. We compare the new method with other state‐of‐the‐art superpixel generation algorithms on two datasets, and our algorithm demonstrates superior performance.

Superpixel generation, which is an essential step in many image processing applications, has attracted increasing attention from researchers. In this paper, we present an efficient flooding-based superpixel generation algorithm that generates compact and highly boundary adherent superpixels. In particular, by considering various superpixel properties, we measure the similarities between image pixels by proposing a new distance metric that combines various image features (e.g., colors, spatial locations, neighbor information, and texture features). To control the relative significance of these image features, we acquire the weights of image features (e.g., colors, texture features, and neighbor information of pixels) through a neural network. Then, the final superpixels are obtained through a greedy optimization that considers both the current superpixel and its neighboring superpixels. We perform extensive experiments on two datasets to verify the efficacy of our algorithm. The results show that our algorithm has considerable advantages over existing state-of-the-art methods, particularly regarding the compactness of the resulting superpixels.

Abstract Packing problems arise in a wide variety of practical applications. The basic problem is that of placing as many objects as possible in a non‐overlapping configuration within a given container. Problems involving irregular shapes are the most challenging cases. In this paper, we consider the most general forms of irregular shape packing problems in 3D space, where both the containers and the objects can be of any shapes, and free rotations of the objects are allowed. We propose a heuristic method for efficiently packing irregular objects by combining continuous optimization and combinatorial optimization. Starting from an initial placement of an appropriate number of objects, we optimize the positions and orientations of the objects using continuous optimization. In combinatorial optimization, we further reduce the gaps between objects by swapping and replacing the deployed objects and inserting new objects. We demonstrate the efficacy of our method with experiments and comparisons.

A new method is presented for producing photo collages that preserve content correlation of photos. We use deep learning techniques to find correlation among given photos to facilitate their embedding on the canvas, and develop an efficient combinatorial optimization technique to make correlated photos stay close to each other. To make efficient use of canvas space, our method first extracts salient regions of photos and packs only these salient regions. We allow the salient regions to have arbitrary shapes, therefore yielding informative, yet more compact collages than by other similar collage methods based on salient regions. We present extensive experimental results, user study results, and comparisons against the state-of-the-art methods to show the superiority of our method.

In this paper, we present a novel geometric method for efficiently and robustly computing intersections between a ray and a triangular Bézier patch defined over a triangular domain, called the hybrid clipping (HC) algorithm. If the ray pierces the patch only once, we locate the parametric value of the intersection to a smaller triangular domain, which is determined by pairs of lines and quadratic curves, by using a multi-degree reduction method. The triangular domain is iteratively clipped into a smaller one by combining a subdivision method, until the domain size reaches a prespecified threshold. When the ray intersects the patch more than once, Descartes’ rule of signs and a split step are required to isolate the intersection points. The algorithm can be proven to clip the triangular domain with a cubic convergence rate after an appropriate preprocessing procedure. The proposed algorithm has many attractive properties, such as the absence of an initial guess and insensitivity to small changes in coefficients of the original problem. Experiments have been conducted to illustrate the efficacy of our method in solving ray-triangular Bézier patch intersection problems.

This article presents a new method to optimally partition a geometric domain with capacity constraints on the partitioned regions. It is an important problem in many fields, ranging from engineering to economics. It is known that a capacity-constrained partition can be obtained as a power diagram with the squared L2 metric. We present a method with super-linear convergence for computing optimal partition with capacity constraints that outperforms the state-of-the-art in an order of magnitude. We demonstrate the efficiency of our method in the context of three different applications in computer graphics and geometric processing: displacement interpolation of function distribution, blue-noise point sampling, and optimal convex decomposition of 2D domains. Furthermore, the proposed method is extended to capacity-constrained optimal partition with respect to general cost functions beyond the squared Euclidean distance.

Mosaics are widely used for surface decoration to produce appealing visual effects. We present a method for synthesizing digital surface mosaics with irregularly shaped tiles, which are a type of tiles often used for mosaics design. Our method employs both continuous optimization and combinatorial optimization to improve tile arrangement. In the continuous optimization step, we iteratively partition the base surface into approximate Voronoi regions of the tiles and optimize the positions and orientations of the tiles to achieve a tight fit. Combination optimization performs tile permutation and replacement to further increase surface coverage and diversify tile selection. The alternative applications of these two optimization steps lead to rich combination of tiles and high surface coverage. We demonstrate the effectiveness of our solution with extensive experiments and comparisons.

Poisson disk sampling is an important problem in computer graphics and has a wide variety of applications in imaging, geometry, rendering, etc. In this paper, we propose a novel Poisson disk sampling algorithm based on disk packing. The key idea uses the observation that a relatively dense disk packing layout naturally satisfies the Poisson disk distribution property that each point is no closer to the others than a specified minimum distance, i.e., the Poisson disk radius. We use this property to propose a relaxation algorithm that achieves a good balance between the random and uniform properties needed for Poisson disk distributions. Our algorithm is easily adapted to image stippling by extending identical disk packing to unequal disks. Experimental results demonstrate the efficacy of our approaches.

Abstract We develop a novel isotropic remeshing method based onconstrained centroidal Delaunay mesh(CCDM), a generalization of centroidal patch triangulation from 2D to mesh surface. Our method starts with resampling an input mesh with a vertex distribution according to a user‐defined density function. The initial remeshing result is then progressively optimized by alternatively recovering the Delaunay mesh and moving each vertex to the centroid of its 1‐ring neighborhood. The key to making such simple iterations work is an efficient optimization framework that combines both local and global optimization methods. Our method is parameterization‐free, thus avoiding the metric distortion introduced by parameterization, and generating more well‐shaped triangles. Our method guarantees that the topology of surface is preserved without requiring geodesic information. We conduct various experiments to demonstrate the simplicity, efficacy, and robustness of the presented method.

This paper develops a novel surface fitting scheme for automatically reconstructing a genus-0 object into a continuous parametric spline surface. A key contribution for making such a fitting method both practical and accurate is our spherical generalization of the Delaunay configuration B-spline (DCB-spline), a new non-tensor-product spline. In this framework, we efficiently compute Delaunay configurations on sphere by the union of two planar Delaunay configurations. Also, we develop a hierarchical and adaptive method that progressively improves the fitting quality by new knot-insertion strategies guided by surface geometry and fitting error. Within our framework, a genus-0 model can be converted to a single spherical spline representation whose root mean square error is tightly bounded within a user-specified tolerance. The reconstructed continuous representation has many attractive properties such as global smoothness and no auxiliary knots. We conduct several experiments to demonstrate the efficacy of our new approach for reverse engineering and shape modeling.

Blue noise point sampling is one of the core algorithms in computer graphics. In this paper, we present a new and versatile variational framework for generating point distributions with high-quality blue noise characteristics while precisely adapting to given density functions. Different from previous approaches based on discrete settings of capacity-constrained Voronoi tessellation, we cast the blue noise sampling generation as a variational problem with continuous settings. Based on an accurate evaluation of the gradient of an energy function, an efficient optimization is developed which delivers significantly faster performance than the previous optimization-based methods. Our framework can easily be extended to generating blue noise point samples on manifold surfaces and for multi-class sampling. The optimization formulation also allows us to naturally deal with dynamic domains, such as deformable surfaces, and to yield blue noise samplings with temporal coherence. We present experimental results to validate the efficacy of our variational framework. Finally, we show a variety of applications of the proposed methods, including nonphotorealistic image stippling, color stippling, and blue noise sampling on deformable surfaces.

Fascinating and elegant shapes may be folded from a single planar sheet of material without stretching, tearing or cutting, if one incorporates curved folds into the design. We present an optimization-based computational framework for design and digital reconstruction of surfaces which can be produced by curved folding. Our work not only contributes to applications in architecture and industrial design, but it also provides a new way to study the complex and largely unexplored phenomena arising in curved folding.

This paper presents a novel parameterization method for a non-closed triangular mesh. For every flattened 1-ring neighbors, we choose a local coordinate frame, and the local geometry structure is represented as local parametric coordinates. Then the global optimal parametric coordinates are attained by aligning all the local parametric planes while preserving the local structure as much as possible. The boundary conditions are not necessary in our method, thus no high distortion appears around the boundary, and distortion is uniformly distributed over parametric domain. In addition, our method can operate directly on mesh surface which has holes without any preprocessing of surface partition. Furthermore, linear constraints are allowed in the parameterization in a least squares sense.

Abstract We present Easy Mesh Cutting, an intuitive and easy‐to‐use mesh cutout tool. Users can cut meaningful components from meshes by simply drawing freehand sketches on the mesh. Our system provides instant visual feedback to obtain the cutting results based on an improved region growing algorithm using a feature sensitive metric. The cutting boundary can be automatically optimized or easily edited by users. Extensive experimentation shows that our approach produces good cutting results while requiring little skill or effort from the user and provides a good user experience. Based on the easy mesh cutting framework, we introduce two applications including sketch‐based mesh editing and mesh merging for geometry processing. Categories and Subject Descriptors (according to ACM CCS): I.3.5 [Computer Graphics]: Geometric algorithms, languages, and systems