Abstract Creating floorplans lays the foundation for architectural design and scene modeling. We propose a novel framework for generating diverse high‐quality floorplans under predefined constraints. Central to our method is an iterative refinement process for optimizing the bounding boxes of rooms and the floorplan semantics image, which defines a vector floorplan together. Vector floorplans can be generated through a learning‐based refinement process. Our framework supports various constraints, such as floorplan boundaries, topological graphs, and bubble diagrams. Extensive experiments demonstrate that our method is superior to state‐of‐the‐art techniques, particularly in generating a wider variety of solutions that cater to various architectural needs.

Integrating artificial intelligence (AI) into computer-aided design (CAD) has shown the potential to transform design and manufacturing processes, enabling more efficient, intuitive, and intelligent workflows. In recent years, the application of AI to 3D CAD model generation tasks has gradually emerged. To better enable researchers to understand the current research status of the AI-based CAD generation field and to inspire them to conduct further research, this survey explores the role of AI in 3D CAD model generation tasks that utilize various representations and conditions, ranging from traditional machine learning to LLM-based approaches. Additionally, AI applications in other extended CAD areas are also touched upon in the survey. Finally, we analyze current progress, identify challenges and limitations faced by this field, and propose possible directions for future work.

We propose an efficient method to compute a small set of integer-constrained cone singularities, which induce a rotationally seamless conformal parameterization with low distortion. Since the problem only involves discrete variables, i.e., vertex-constrained positions, integer-constrained angles, and the number of cones, we alternately optimize these three types of variables to achieve tractable convergence. Central to high efficiency is an explicit construction algorithm that reduces the optimization problem scale to be slightly greater than the number of integer variables for determining the optimal angles with fixed positions and numbers, even for high-genus surfaces. In addition, we derive a new derivative formula that allows us to move the cones, effectively reducing distortion until convergence. Combined with other strategies, including repositioning and adding cones to decrease distortion, adaptively selecting a constrained number of integer variables for efficient optimization, and pairing cones to reduce the number, we quickly achieve a favorable tradeoff between the number of cones and the parameterization distortion. We demonstrate the effectiveness and practicability of our cones by using them to generate rotationally seamless and low-distortion parameterizations on a massive test data set. Our method demonstrates an order-of-magnitude speedup (30× faster on average) compared to state-of-the-art approaches while maintaining comparable cone numbers and parameterization distortion.

Biharmonic coordinates have become a powerful tool for cage-based deformation, owing to their inherent interpolation properties. However, their derivation for polynomial cages in 3D has remained unsolved. To address this, we propose closed-form expressions for polynomial 3D biharmonic coordinates and their derivatives when deformed from polygonal cages using the high-order boundary element method. Our primary contribution lies in the analytical derivation of the kernel integration using recursive differentiation techniques. Due to the enriched deformation space of biharmonic coordinates and the flexibility of polynomial cages, our method supports a broad range of deformations, as demonstrated through extensive experiments.

We propose a novel method to generate a small set of ruled surfaces that do not collide with the input shape for linear hot-wire rough machining. Central to our technique is a new observation: ruled surfaces constructed by vertical extrusion from planar smooth curves that approach the input shape's outer contour lines without collisions can effectively remove material during rough machining. Accordingly, we develop an iterative algorithm that alternates in each iteration between computing a viewpoint to determine an outer contour line and optimizing a smooth curve to approximate that contour line under the collision-free constraint. Specifically, a view selection approach based on a genetic algorithm is used to optimize the viewpoint for removing materials as much as possible, and an adaptive fitting algorithm is presented to find the constrained curves. The feasibility and practicability of our method are demonstrated through 10 physical examples. Compared with manual designs, our method obtains lower errors with the same number of cuts.

We propose closed-form Cauchy coordinates and their derivatives for 2D closed high-order input cages composed of arbitrary-order polynomial curves. Our coordinates facilitate the transformation of input polynomial curves into output curves of any desired polynomial order. Central to our derivation is the creative use of the residue theorem with the logarithmic function to obtain the integral of a rational polynomial required for extending the classical 2D Cauchy coordinates to high-order input cages. Our coordinates enable smooth cage-aware angle-preserving deformations, and the derivatives allow for point-to-point deformation. Moreover, our derivation can be extended to the input cages with rational polynomial curves. Through various 2D deformations, we demonstrate how users can intuitively manipulate Bézier control points to achieve desired deformations easily.

Abstract We propose a novel method to filter eigenvalues for projected Newton. Central to our method is blending the clamped and absolute eigenvalues to adaptively compute the modified Hessian matrix. To determine the blending coefficients, we rely on (1) a key observation and (2) an objective function descent constraint. The observation is that if the quadratic form defined by the Hessian matrix maps the descent direction to a negative real number, the decrease in the objective function is limited. The constraint is that our eigenvalue filtering leads to more reduction in objective function than the absolute eigenvalue filtering [CLL*24] in the case of second‐order Taylor approximation. Our eigenvalue blending is easy to implement and leads to fewer optimization iterations than the state‐of‐the‐art eigenvalue filtering methods.

Computing the Laplace–Beltrami operator on point clouds is essential for tasks such as smoothing and shape analysis. Unlike meshes, determining the Laplace–Beltrami operator on point clouds requires establishing neighbors for each point. However, traditional k -nearest neighbors (k-NN) methods for estimating local neighborhoods often introduce spurious connectivities that distort the manifold topology. We propose a novel approach that leverages persistent homology to refine the neighborhood graph by identifying and removing erroneous edges. Starting with an initial k-NN graph, we assign weights based on local tangent plane estimations and construct a Vietoris–Rips complex. Persistent homology is then employed to detect and eliminate spurious edges through a topological optimization process. This iterative refinement results in a more accurate neighborhood graph that better represents the underlying manifold, enabling precise discretization of the Laplace–Beltrami operator. Experimental results on various point cloud datasets demonstrate that our method outperforms traditional k-NN approaches by more accurately capturing the manifold topology and enhancing downstream computations such as spectral analysis.

We propose a novel partition method for reliable feature-aligned quadrangulation. The core insight of the partition is that smooth streamlines distant from singularities are more suitable as patch boundaries. This allows singularities to be enclosed within patches, resulting in straighter patch boundaries and reducing the distorting influence of singularities. Accordingly, we introduce a new patch quality control mechanism that keeps the patch boundaries inside regions with high field smoothness. Combined with other common metrics (e.g., aligning boundaries with field and feature lines), we develop a practical partition algorithm that first iteratively traces paths in field smoothness-controlled regions to form patches and then removes redundant paths to simplify the patch layout. We demonstrate the effectiveness and practicability of our partitions by using them to generate quality quad meshes on a massive test data set. Compared with state-of-the-art methods, our approach produces quad meshes with significantly enhanced quality while maintaining similar reliability, validating the core insight. Code and data for this paper are at https://github.com/AnderLiang/Field-Smoothness-Controlled-Quadrangulation.

We derive closed-form expressions of biharmonic coordinates for 2D high-order cages, enabling the transformation of the input polynomial curves into polynomial curves of any order. Central to our derivation is the use of the high-order boundary element method. We demonstrate the practicality and effectiveness of our method on various 2D deformations. In practice, users can easily manipulate the Bézier control points to perform the desired intuitive deformation, as the biharmonic coordinates provide an enriched deformation space and encourage the alignment between the boundary cage and its interior geometry.

We derive closed-form expressions for generalized winding numbers of rational parametric curves for robust containment queries. Given an oriented rational parametric curve and a query point, the generalized winding number can be reformulated to an integral of a rational polynomial. The key to computing the integral lies in using the residue theorem. Then, add up the contributions of each curve to obtain the generalized winding numbers of a set of rational parametric curves. Furthermore, the derivatives of generalized winding numbers are easily derived. Consequently, the expressions for generalized winding numbers are concise and computationally efficient, becoming faster than state-of-the-art methods. Moreover, the computational costs for various query points are almost the same.

We propose a novel method to generate developable approximations for triangular meshes. Instead of fitting the Gauss image using a geodesic circle in the local neighborhood, we apply a nonlinear dimensionality reduction method, called Isomap, to use a general curve on the sphere for fitting. This brings us a larger space to represent the Gauss image in the local neighborhood as a 1D structure. Specifically, each triangle is assigned a target normal after local fitting; then, we deform the mesh to approach the target normal globally. By iteratively performing fitting and deformation, we obtain the developable approximation. We demonstrate the feasibility and effectiveness of our method over various examples. Compared to the state-of-the-art methods, our results exhibit a higher fidelity to the input mesh while possessing more prominent and visually distinct undevelopable seam curves.

We propose a novel method to robustly and efficiently compute the maximum allowable step sizes so that the 3D high-order finite elements continuously preserve geometric validity when moving along the given directions with positive step sizes smaller than the computed ones. We transform the problem of finding the maximum allowable step sizes to one of solving roots of cubic polynomials. To use interval arithmetic to avoid numerical issues in cubic equation solving, we completely enumerate the roots of cubic polynomials and apply the interval version of the Newton-Raphson iteration. The effectiveness of our algorithm is demonstrated through extensive testing. Compared to the state-of-the-art method, our algorithm achieves higher efficiency.

We propose a novel method to generate high-quality triangular meshes with specified anisotropy. Central to our algorithm is to present metric-adapted embeddings for converting the anisotropic meshing problem to an isotropic meshing problem with constant density. Moreover, the orientation of the input Riemannian metric forms a field, enabling us to use field-based meshing techniques to improve regularity and penalize obtuse angles. To achieve such metric-adapted embeddings, we use the cone singularities , which are generated to adapt to the input Riemannian metric. We demonstrate the feasibility and effectiveness of our method over various models. Compared to other state-of-the-art methods, our method achieves higher quality on all metrics in most models.

Abstract We propose a novel method for generating symmetric piecewise developable approximations for shapes in approximately global reflectional or rotational symmetry. Given a shape and its symmetry constraint, the algorithm contains two crucial steps: (i) a symmetric deformation to achieve a nearly developable model and (ii) a symmetric segmentation aided by the deformed shape. The key to the deformation step is the use of the symmetric implicit neural representations of the shape and the deformation field. A new mesh extraction from the implicit function is introduced to construct a strictly symmetric mesh for the subsequent segmentation. The symmetry constraint is carefully integrated into the partition to achieve the symmetric piecewise developable approximation. We demonstrate the effectiveness of our algorithm over various meshes.

We propose a novel method to exactly and efficiently resolve intersections and self-intersections in triangle meshes. Our method contains two key components. First, we present a new concept of geometric predicates, called indirect offset predicates , to represent all intersection points through a new formulation and establish all necessary geometric predicates. Consequently, we reduce numerical errors in floating-point evaluations and improve the success rate of early stages of arithmetic filtering. Second, we develop localization and dimension reduction techniques for sorting, deduplicating, and locating the intersection points, thereby boosting efficiency and parallelism while maintaining accuracy. Rigorous testing confirms the robustness of our algorithm and consistency with previous methods. Comprehensive testing across diverse datasets further highlights the speed improvement achieved by our method, which is one order of magnitude faster than the state-of-the-art methods.

We propose a simple yet effective method to orient normals for point clouds. Central to our approach is a novel optimization objective function defined from global and local perspectives. Globally, we introduce a signed uncertainty function that distinguishes the inside and outside of the underlying surface. Moreover, benefiting from the statistics of our global term, we present a local orientation term instead of a global one. The optimization problem can be solved by the commonly used numerical optimization solver, such as L-BFGS. The capability and feasibility of our approach are demonstrated over various complex point clouds. We achieve higher practical robustness and normal quality than the state-of-the-art methods.

We propose a new structure called a higher-order shell, which is composed of a set of triangular prisms. Each triangular prism is enveloped by three Bézier triangles (top, middle, and bottom) and three side surfaces, each of which is trimmed from a bilinear surface. Moreover, we define a continuous vector field to smoothly and bijectively transfer attributes between two surfaces inside the shell. Since the higher-order shell has several hard construction constraints, we apply an interior-point strategy to robustly and automatically construct a high-order shell for an input mesh. Specifically, the strategy starts from a valid linear shell with a small thickness. Then, the shell is optimized until the specified thickness is reached, where explicit checks ensure that the constraints are always satisfied. We extensively test our method on more than 8300 models, demonstrating its robustness and performance. Compared to state-of-the-art methods, our bijective projection is smoother, and the space between the shell and input mesh is more uniform.

We propose a robust and automatic method to construct manifold cages for 3D triangular meshes. The cage contains hundreds of triangles to tightly enclose the input mesh without self-intersections. To generate such cages, our algorithm consists of two phases: (1) construct manifold cages satisfying the tightness, enclosing, and intersection-free requirements and (2) reduce mesh complexities and approximation errors without violating the enclosing and intersection-free requirements. To theoretically make the first stage have those properties, we combine the conformal tetrahedral meshing and tetrahedral mesh subdivision. The second step is a constrained remeshing process using explicit checks to ensure that the enclosing and intersection-free constraints are always satisfied. Both phases use a hybrid coordinate representation, i.e., rational numbers and floating point numbers, combined with exact arithmetic and floating point filtering techniques to guarantee the robustness of geometric predicates with a favorable speed. We extensively test our method on a data set of over 8500 models, demonstrating robustness and performance. Compared to other state-of-the-art methods, our method possesses much stronger robustness.

We propose a novel and automatic method to model shapes using a small set of discrete developable patches. Central to our approach is using implicit neural shape representation that makes our algorithm independent of tessellation and allows us to obtain the Gaussian curvature of each point analytically. With this powerful representation, we first deform the input shape to be an almost developable shape with clear and sparse salient feature curves. Then, we convert the deformed implicit field to a triangle mesh, which is further cut to disk topology along parts of the sparse feature curves. Finally, we achieve the resulting piecewise developable mesh by alternatingly optimizing discrete developability, enforcing manufacturability constraints, and merging patches. The feasibility and practicability of our method are demonstrated over various shapes. Compared to the state-of-the-art methods, our method achieves a better tradeoff between the number of developable patches and the approximation error.

We propose a practical method to construct sparse integer-constrained cone singularities with low distortion constraints for conformal parameterizations. Our solution for this combinatorial problem is a two-stage procedure that first enhances sparsity for generating an initialization and then optimizes to reduce the number of cones and the parameterization distortion. Central to the first stage is a progressive process to determine the combinatorial variables, i.e., numbers, locations, and angles of cones. The second stage iteratively conducts adaptive cone relocations and merges close cones for optimization. We extensively test our method on a data set containing 3885 models, demonstrating practical robustness and performance. Our method achieves fewer cone singularities and lower parameterization distortion than state-of-the-art methods.

Abstract We propose a novel image triangulation method to reduce the complexity of image triangulation under the color error‐bounded constraint and the triangle quality constraint. Meanwhile, we realize a variety of visual effects by supporting different types of triangles (e.g., linear or curved) and color approximation functions (e.g., constant, linear, or quadratic). To adapt to these discontinuous and combinatorial objectives and constraints, we formulate it as a constrained optimization problem that is solved by a series of tailored local remeshing operations. The feasibility and practicability of our method are demonstrated over various types of images, such as organisms, landscapes, portraits and cartoons. Compared to state‐of‐the‐art methods, our method generates far fewer triangles for the same color error or much smaller color errors using the same number of triangles.

Abstract We propose to use nonlinear shape functions represented as neural networks in numerical coarsening to achieve generalization capability as well as good accuracy. To overcome the challenge of generalization to different simulation scenarios, especially nonlinear materials under large deformations, our key idea is to replace the linear mapping between coarse and fine meshes adopted in previous works with a nonlinear one represented by neural networks. However, directly applying an end‐to‐end neural representation leads to poor performance due to over‐huge parameter space as well as failing to capture some intrinsic geometry properties of shape functions. Our solution is to embed geometry constraints as the prior knowledge in learning, which greatly improves training efficiency and inference robustness. With the trained neural shape functions, we can easily adopt numerical coarsening in the simulation of various hyperelastic models without any other preprocessing step required. The experiment results demonstrate the efficiency and generalization capability of our method over previous works.

We propose a novel method to compute globally injective parameterizations with arbitrary positional constraints on disk topology meshes. Central to this method is the use of a scaffold mesh that reduces the globally injective constraint to a locally flipfree condition. Hence, given an initial parameterized mesh containing flipped triangles and satisfying the positional constraints, we only need to remove the flips of a overall mesh consisting of the parameterized mesh and the scaffold mesh while always meeting positional constraints. To successfully apply this idea, we develop two key techniques. Firstly, an initialization method is used to generate a valid scaffold mesh and mitigate difficulties in eliminating flips. Secondly, edge-based remeshing is used to optimize the regularity of the scaffold mesh containing flips, thereby improving practical robustness. Compared to state-of-the-art methods, our method is much more robust. We demonstrate the capability and feasibility of our method on a large number of complex meshes.

We propose an efficient method to construct sparse cone singularities under distortion-bounded constraints for conformal parameterizations. Central to our algorithm is using the technique of shape derivatives to move cones for distortion reduction without changing the number of cones. In particular, the supernodal sparse Cholesky update significantly accelerates this movement process. To satisfy the distortion-bounded constraint, we alternately move cones and add cones. The capability and feasibility of our approach are demonstrated over a data set containing 3885 models. Compared with the state-of-the-art method, we achieve an average acceleration of 15 times and slightly fewer cones for the same amount of distortion.

We propose a novel method to compute high-quality piecewise developable approximations for triangular meshes. Central to our approach is an evolutionary genetic algorithm for optimizing the combinatorial and discontinuous fitness function, including the approximation error, the number of patches, the patch boundary length, and the penalty for small patches and narrow regions within patches. The genetic algorithm's operations (i.e., initialization, selection, mutation, and crossover) are explicitly designed to minimize the fitness function. The main challenge is evaluating the fitness function's approximation error as it requires developable patches, which are difficult or time-consuming to obtain. Resolving the challenge is based on a critical observation: the approximation error and the mapping distortion between an input surface and its developable approximation are positively correlated empirically. To efficiently measure distortion without explicitly generating developable shapes, we creatively use conformal mapping techniques. Then, we control the mapping distortion at a relatively low level to achieve high shape similarity in the genetic algorithm. The feasibility and effectiveness of our method are demonstrated over 240 complex examples. Compared with the state-of-the-art methods, our results have much smaller approximation errors, fewer patches, shorter patch boundaries, and fewer small patches and narrow regions.

Abstract We propose an interactive method to edit a discrete Chebyshev net, which is a quad mesh with edges of the same length. To ensure that the edited mesh is always a discrete Chebyshev net, the maximum difference of all edge lengths should be zero during the editing process. Hence, we formulate an objective function using ℓp‐norm (p > 2) to force the maximum length deviation to approach zero in practice. To optimize the nonlinear and non‐convex objective function interactively and efficiently, we develop a novel second‐order solver. The core of the solver is to construct a new convex majorizer for our objective function to achieve fast convergence. We present two acceleration strategies to further reduce the optimization time, including adaptive p change and adaptive variables reduction. A large number of experiments demonstrate the capability and feasibility of our method for interactively editing complex discrete Chebyshev nets.

Abstract We propose a novel method to generate a high‐order triangular mesh for an input 2D domain with two key characteristics: (1) the mesh precisely conforms to a set of input piecewise rational domain curves, and (2) the geometric map on each curved triangle is injective. Central to the algorithm is a new sufficient condition for placing control points of a rational Bézier triangle to guarantee that the conformance and injectivity constraints are theoretically satisfied. Taking advantage of this condition, we provide an explicit construct that robustly creates higher‐order 2D meshes satisfying the two characteristics. We demonstrate the robustness and effectiveness of our algorithm over a data set containing 2200 examples.

Abstract We propose a simple yet effective method to perform surface remeshing with hard constraints, such as bounding approximation errors and ensuring Delaunay conditions. The remeshing is formulated as a constrained optimization problem, where the variables contain the mesh connectivity and the mesh geometry. To solve it effectively, we adopt traditional local operations, including edge split, edge collapse, edge flip, and vertex relocation, to update the variables. Central to our method is an evolutionary vertex optimization algorithm, which is derivative‐free and robust. The feasibility and practicability of our method are demonstrated in two applications, including error‐bounded Delaunay mesh simplification and error‐bounded angle improvement with a given number of vertices, over many models. Compared to state‐of‐the‐art methods, our method achieves higher remeshing quality.

Abstract We propose a novel topology optimization method to efficiently minimize the maximum compliance for a high‐resolution model bearing uncertain external loads. Central to this approach is a modified power method that can quickly compute the maximum eigenvalue to evaluate the worst‐case compliance, enabling our method to be suitable for large‐scale topology optimization. After obtaining the worst‐case compliance, we use the adjoint variable method to perform the sensitivity analysis for updating the density variables. By iteratively computing the worst‐case compliance, performing the sensitivity analysis, and updating the density variables, our algorithm achieves the optimized models with high efficiency. The capability and feasibility of our approach are demonstrated over various large‐scale models. Typically, for a model of size 512×170×170 and 69934 loading nodes, our method took about 50 minutes on a desktop computer with an NVIDIA GTX 1080Ti graphics card with 11 GB memory.

We propose a novel method to generate sparse integer-constrained cone singularities with low distortion constraints for conformal parameterizations. Inspired by [Fang et al. 2021; Soliman et al. 2018], the cone computation is formulated as a constrained optimization problem, where the objective is the number of cones measured by the ℓ 0 -norm of Gaussian curvature of vertices, and the constraint is to restrict the cone angles to be multiples of π /2 and control the distortion while ensuring that the Yamabe equation holds. Besides, the holonomy angles for the non-contractible homology loops are additionally required to be multiples of π /2 for achieving rotationally seamless conformal parameterizations. The Douglas-Rachford (DR) splitting algorithm is used to solve this challenging optimization problem, and our success relies on two key components. First, replacing each integer constraint with the intersection of a box set and a sphere enables us to manage the subproblems in DR splitting update steps in the continuous domain. Second, a novel solver is developed to optimize the ℓ 0 -norm without any approximation. We demonstrate the effectiveness and feasibility of our algorithm on a data set containing 3885 models. Compared to state-of-the-art methods, our method achieves a better tradeoff between the number of cones and the parameterization distortion.

In the mirror cup and saucer art created by artists Yul Cho and Sang-Ha Cho, part of the saucer is directly visible to the viewer, while the other part of the saucer is occluded and can only be seen as a reflection through a mirror cup. Thus, viewers see an image directly on the saucer and another image on the mirror cup; however, the existing art design is limited to wavelike saucers. In this work, we propose a general computational framework for mirror cup and saucer art design. As input, we take from the user one image for the direct view, one image for the reflected view, and the base shape of the saucer. Our algorithm then generates a suitable saucer shape by deforming the input shape. We formulate this problem as a constrained optimization for the saucer surface. Our framework solves for the fine geometry details on the base shape along with its texture, such that when a mirror cup is placed on the saucer, the user-specified images are observed as direct and reflected views. Through extensive experiments, we demonstrate the effectiveness of our framework and the great design flexibility that it offers to users. We further validate the produced art pieces by fabricating the colored saucers using three-dimensional printing.

We propose a novel method to compute a piecewise mesh with a few developable patches and a small approximation error for an input triangular mesh. Our key observation is that a deformed mesh after enforcing discrete developability is easily partitioned into nearly developable patches. To obtain the nearly developable mesh, we present a new edge-oriented notion of discrete developability to define a developability-encouraged deformation energy, which is further optimized by the block nonlinear Gauss-Seidel method. The key to successfully applying this optimizer is three types of auxiliary variables. Then, a coarse-to-fine segmentation technique is developed to partition the deformed mesh into a small set of nearly discrete developable patches. Finally, we refine the segmented mesh to reduce the discrete Gaussian curvature while keeping the patches smooth and the approximation error small. In practice, our algorithm achieves a favorable tradeoff between the number of developable patches and the approximation error. We demonstrate the feasibility and practicability of our method over various examples, including seventeen physical manufacturing models with paper.

A geometric mapping establishes a correspondence between two domains. Since no real object has zero or negative volume, such a mapping is required to be inversion-free. Computing inversion-free mappings is a fundamental task in numerous computer graphics and geometric processing applications, such as deformation, texture mapping, mesh generation, and others. This task is usually formulated as a non-convex, nonlinear, constrained optimization problem. Various methods have been developed to solve this optimization problem. As well as being inversion-free, different applications have various further requirements. We expand the discussion in two directions to (i) problems imposing specific constraints and (ii) combinatorial problems. This report provides a systematic overview of inversion-free mapping construction, a detailed discussion of the construction methods, including their strengths and weaknesses, and a description of open problems in this research field.

In virtual reality (VR), the virtual scenes are pre-designed by creators. Our physical surroundings, however, comprise significantly varied sizes, layouts, and components. To bridge the gap and further enable natural navigation, recent solutions have been proposed to redirect users or recreate the virtual content. However, they suffer from either interrupted experience or distorted appearances. We present a novel VR-oriented algorithm that automatically restructures a given virtual scene for a user’s physical environment. Different from the previous methods, we introduce neither interrupted walking experience nor curved appearances. Instead, a perception-aware function optimizes our retargeting technique to preserve the fidelity of the virtual scene that appears in VR head-mounted displays. Besides geometric and topological properties, it emphasizes the unique first-person view perceptual factors in VR, such as dynamic visibility and objectwise relationships. We conduct both analytical experiments and subjective studies. The results demonstrate our system’s versatile capability and practicability for natural navigation in VR: It reduces the virtual space by 40% without statistical loss of perceptual identicality.

We propose a novel method to generate sparse cone singularities with bounded distortion constraints for conformal parameterizations. It is formulated as minimizing the ℓ 0 -norm of Gaussian curvature of vertices with hard constraints of bounding the distortion that is measured by the ℓ 2 -norm of the log conformal factor. We use the reweighted ℓ 1 -norm to approximate the ℓ 0 -norm and solve each convex weighted ℓ 1 minimization subproblem by the Douglas-Rachford (DR) splitting scheme. To quickly generate sparse cones, we modify DR splitting by weighting the ℓ 2 -norm of the proximal mapping to force the small Gaussian curvature to quickly approach zero. Accordingly, compared with the conventional DR splitting, the modified method performs one to two orders of magnitude faster. Besides, we perform variable substitution of log conformal factors to simplify the computation process for acceleration. Our algorithm is able to bound distortion to compute sparse cone singularities, so that the resulting conformal parameterizations achieve a favorable tradeoff between the area distortion and the number of cones. We demonstrate its effectiveness and feasibility on a large number of models.

We propose a novel method to model and fabricate shapes using a small set of specified discrete equivalence classes of triangles. The core of our modeling technique is a fabrication-error-driven remeshing algorithm. Given a triangle and a template triangle, which are coplanar and have one-to-one corresponding vertices, we define their similarity error from a manufacturing point of view as follows: the minimizer of the maximum of the three distances between the corresponding pair of vertices concerning a rigid transformation. To compute the similarity error, we convert it into an easy-to-compute form. Then, a greedy remeshing method is developed to optimize the topology and geometry of the input mesh to minimize the fabrication error defined as the maximum similarity error of all triangles. Besides, constraints are enforced to ensure the similarity between input and output shapes and the smoothness of the resulting shapes. Since the fabrication error has been considered during the modeling process, the fabrication process is easy to proceed. To assist users in performing fabrication using common materials and tools manually, we present a straightforward manufacturing solution. The feasibility and practicability of our method are demonstrated over various examples, including seven physical manufacturing models with only nine template triangles.

Low isometric distortion is often required for mesh parameterizations. A configuration of some vertices, where the distortion is concentrated, provides a way to mitigate isometric distortion, but determining the number and placement of these vertices is non-trivial. We call these vertices distortion points. We present a novel and automatic method to detect distortion points using a voting strategy. Our method integrates two components: candidate generation and candidate voting. Given a closed triangular mesh, we generate candidate distortion points by executing a three-step procedure repeatedly: (1) randomly cut an input to a disk topology; (2) compute a low conformal distortion parameterization; and (3) detect the distortion points. Finally, we count the candidate points and generate the final distortion points by voting. We demonstrate that our algorithm succeeds when employed on various closed meshes with a genus of zero or higher. The distortion points generated by our method are utilized in three applications, including planar parameterization, semi-automatic landmark correspondence, and isotropic remeshing. Compared to other state-of-the-art methods, our method demonstrates stronger practical robustness in distortion point detection.

Abstract We propose a computational and practical technique to allow home users to fabricate discrete Chebyshev nets for various 3D models. The success of our method relies on two key components. The first one is a novel and simple method to approximate discrete integrable, unit‐length, and angle‐bounded frame fields, used to model discrete Chebyshev nets. Central to our field generation process is an alternating algorithm that takes turns executing one pass to enforce integrability and another pass to approach unit length while bounding angles. The second is a practical fabrication specification. The discrete Chebyshev net is first partitioned into a set of patches to facilitate manufacturing. Then, each patch is assigned a specification on pulling, bend, and fold to fit the nets. We demonstrate the capability and feasibility of our method in various complex models.

Abstract As high‐precision 3D scanners become more and more widespread, it is easy to obtain very‐large‐scale meshes containing at least millions of vertices. However, processing these very‐large‐scale meshes is still a very challenging task due to memory limitations. This paper focuses on a fundamental geometric processing task, i.e., bijective parameterization construction. To this end, we present a spline‐enhanced method to compute bijective and low distortion parameterizations for very‐large‐scale disk topology meshes. Instead of computing descent directions using the mesh vertices as variables, we estimate descent directions for each vertex by optimizing a proxy energy defined in spline spaces. Since the spline functions contain a small set of control points, it significantly decreases memory requirement. Besides, a divide‐and‐conquer method is proposed to obtain bijective initializations, and a submesh‐based optimization strategy is developed to reduce distortion further. The capability and feasibility of our method are demonstrated over various complex models. Compared to the existing methods for bijective parameterizations of very‐large‐scale meshes, our method exhibits better scalability and requires much less memory.

Abstract We present a novel method to construct short cuts for parameterizations with low isometric distortion. The algorithm contains two steps: (i) detect feature points, where the distortion is usually concentrated; and (ii) construct a cut by connecting the detected feature points. Central to each step is a greedy method. After generating a redundant feature point set, a greedy filtering process is performed to identify the feature points required for low isometric distortion parameterizations. This filtering process discards the feature points that are useless for distortion reduction while still enabling us to obtain low isometric distortion. Next, we formulate the process of connecting the detected feature points as a Steiner tree problem. To find an approximate solution, we first successively and greedily produce a collection of auxiliary points. Then, a cut is constructed by connecting the feature points and auxiliary points. In the 26,299 test cases in which an exact solution to the Steiner tree problem is available, the length of the cut obtained by our method is on average 0.17% longer than optimal. Compared to state‐of‐the‐art cut construction methods, our method is one order of magnitude faster and generates shorter cuts while achieving similar isometric distortion.

We propose a novel method to efficiently compute bijective parameterizations with low distortion on disk topology meshes. Our method relies on a second-order solver. To design an efficient solver, we develop two key techniques. First, we propose a coarse shell to substantially reduce the number of collision constraints that are used to guarantee overlap-free boundaries. During the optimization process, the shell ensures the Hessian matrix with a fixed nonzero structure and a low density, thereby significantly accelerating the optimization. The second is a triangle inequality-based barrier function that effectively ensures non-intersecting boundaries. Our barrier function is C ∞ inside the locally supported region and its convex second-order approximation is able to be analytically obtained. Compared to state-of-the-art methods for optimizing bijective parameterizations, our method exhibits better scalability and is about six times faster. The performance of our bijective parameterization algorithm is comparable to state-of-the-art methods of locally flip-free parameterizations. A large number of experimental results have shown the capability and feasibility of our method.

We present a novel method to construct compatible surface meshes with bounded approximation errors. Given two oriented and topologically equivalent surfaces and a sparse set of corresponding landmarks, our method contains two steps: (1) generate compatible meshes with bounded approximation errors and (2) reduce mesh complexity while ensuring that approximation errors are always bounded. Central to the first step is a parameterization-based remeshing technique, which is capable of isotropically remeshing the input surfaces to be compatible and error-bounded. By iteratively performing a novel edge-based compatible remeshing and increasing the compatible target edge lengths, the second step effectively reduces mesh complexity while explicitly maintaining compatibility, regularity, and bounding approximation errors. Tests on various pairs of complex models demonstrate the efficacy and practicability of our method for constructing high-quality compatible meshes with bounded approximation errors.

Abstract In this paper, we present a practically robust method for computing foldover‐free volumetric mappings with hard linear constraints. Central to this approach is a projection algorithm that monotonically and efficiently decreases the distance from the mapping to the bounded conformal distortion mapping space. After projection, the conformal distortion of the updated mapping tends to be below the given bound, thereby significantly reducing foldovers. Since it is non‐trivial to define an optimal bound, we introduce a practical conformal distortion bound generation scheme to facilitate subsequent projections. By iteratively generating conformal distortion bounds and trying to project mappings into bounded conformal distortion spaces monotonically, our algorithm achieves high‐quality foldover‐free volumetric mappings with strong practical robustness and high efficiency. Compared with existing methods, our method computes mesh‐based and meshless volumetric mappings with no prescribed conformal distortion bounds. We demonstrate the efficacy and efficiency of our method through a variety of geometric processing tasks.

Abstract We present a novel method to compute bijective PolyCube‐maps with low isometric distortion. Given a surface and its pre‐axis‐aligned shape that is not an exact PolyCube shape, the algorithm contains two steps: (i) construct a PolyCube shape to approximate the pre‐axis‐aligned shape; and (ii) generate a bijective, low isometric distortion mapping between the constructed PolyCube shape and the input surface. The PolyCube construction is formulated as a constrained optimization problem, where the objective is the number of corners in the constructed PolyCube, and the constraint is to bound the approximation error between the constructed PolyCube and the input pre‐axis‐aligned shape while ensuring topological validity. A novel erasing‐and‐filling solver is proposed to solve this challenging problem. Centeral to the algorithm for computing bijective PolyCube‐maps is a quad mesh optimization process that projects the constructed PolyCube onto the input surface with high‐quality quads. We demonstrate the efficacy of our algorithm on a data set containing 300 closed meshes. Compared to state‐of‐the‐art methods, our method achieves higher practical robustness and lower mapping distortion.

We propose a novel technique to provide multiuser real walking experiences with physical interactions in virtual reality (VR) applications. In our system, multiple users walk freely while navigating a large virtual environment within a smaller physical workspace. These users can interact with other real users or physical props in the same physical locations. The key of our method is a redirected smooth mapping that incorporates the redirected walking technique to warp the input virtual scene with small bends and low distance distortion. Users possess a wide field of view to explore the mapped virtual environment while being redirected in the real workspace. To keep multiple users away from the overlaps of the mapped virtual scenes, we present an automatic collision avoidance technique based on dynamic virtual avatars. These avatars naturally appear, move, and disappear, producing as little influence as possible on users’ walking experiences. We evaluate our multiuser real walking system through formative user studies, and demonstrate the capability and practicability of our technique in two multiuser applications.

We present a novel algorithm to refine an input atlas with bounded packing efficiency. Central to this method is the use of the axis-aligned structure that converts the general polygon packing problem to a rectangle packing problem, which is easier to achieve high packing efficiency. Given a parameterized mesh with no flipped triangles, we propose a new angle-driven deformation strategy to transform it into a set of axis-aligned charts, which can be decomposed into rectangles by the motorcycle graph algorithm. Since motorcycle graphs are not unique, we select the one balancing the trade-off between the packing efficiency and chart boundary length, while maintaining bounded packing efficiency. The axis-aligned chart often contains greater distortion than the input, so we try to reduce the distortion while bounding the packing efficiency and retaining bijection. We demonstrate the efficacy of our method on a data set containing over five thousand complex models. For all models, our method is able to produce packed atlases with bounded packing efficiency; for example, when the packing efficiency bound is set to 80%, we elongate the boundary length by an average of 78.7% and increase the distortion by an average of 0.0533%. Compared to state-of-the-art methods, our method is much faster and achieves greater packing efficiency.

Some artists peel citrus fruits into a variety of elegant 2D shapes, depicting animals, plants, and cartoons. It is a creative art form, called Citrus Peeling Art. This art form follows the conservation principle, i.e., each shape must be created using one entire peel. Central to this art is finding optimal cut lines so that the citruses can be cut and unfolded into the desired shapes. However, it is extremely difficult for users to imagine and generate cuts for their desired shapes. To this end, we present a computational method for citrus peeling art designs. Our key insight is that instead of solving the difficult cut generation problem, we map a designed input shape onto a citrus in an attempt to cover the entire citrus and use the mapped boundary to generate the cut paths. Sometimes, a mapped shape is unable to completely cover a citrus. Consequently, we have developed five customized ways of interaction that are used to rectify the input shape so that it is suitable for citrus peeling art. The mapping process and user interactions are iteratively conducted to satisfy a user's design intentions. A large number of experiments, including a formative user study, demonstrate the capability and practicability of our method for peeling art design and construction.

We propose a novel data-driven technique for automatically and efficiently generating floor plans for residential buildings with given boundaries. Central to this method is a two-stage approach that imitates the human design process by locating rooms first and then walls while adapting to the input building boundary. Based on observations of the presence of the living room in almost all floor plans, our designed learning network begins with positioning a living room and continues by iteratively generating other rooms. Then, walls are first determined by an encoder-decoder network, and then they are refined to vector representations using dedicated rules. To effectively train our networks, we construct RPLAN - a manually collected large-scale densely annotated dataset of floor plans from real residential buildings. Intensive experiments, including formative user studies and comparisons, are conducted to illustrate the feasibility and efficacy of our proposed approach. By comparing the plausibility of different floor plans, we have observed that our method substantially outperforms existing methods, and in many cases our floor plans are comparable to human-created ones.

Compatible remeshing provides meshes with common connectivity structures. The existing compatible remeshing methods usually suffer from high computational cost or poor quality. In this paper, we present a fast method for computing compatible meshes with high quality. Given two closed, oriented, and topologically equivalent surfaces and a sparse set of corresponding landmarks, we first compute a bijective inter-surface mapping, from which compatible meshes are generated. We then improve the remeshing quality by using a volume-enhanced optimization. In contrast to previous work, our method designs a fast volume-enhanced improvement procedure that directly reduces the isometric distortion of the map between the compatible meshes. Our method also tries to preserve the shapes of the input meshes by projecting the vertices of the compatible meshes onto the input surfaces. Central to this approach is the use of the monotone preconditioned conjugate gradient method, which minimizes the energies effectively and efficiently. Compared with state-of-the-art methods, our method performs about one order of magnitude faster with better remeshing quality. We demonstrate the efficiency and efficacy of our method using various model pairs.

We propose a novel approach, calledProgressive Parameterizations, to compute foldover-free parameterizations with low isometric distortion on disk topology meshes. Instead of using the input mesh as a reference to define the objective function, we introduce a progressive reference that contains bounded distortion to the parameterized mesh and is as close as possible to the input mesh. After optimizing the bounded distortion energy between the progressive reference and the parameterized mesh, the parameterized mesh easily approaches the progressive reference, thereby also coming close to the input. By iteratively generating the progressive reference and optimizing the bounded distortion energy to update the parameterized mesh, our algorithm achieves high-quality parameterizations with strong practical reliability and high efficiency. We have demonstrated that our algorithm succeeds on a massive test data set containing over 20712 complex disk topology meshes. Compared to the state-of-the-art methods, our method has achieved higher computational efficiency and practical reliability.

Computing spherical parameterizations for genus-zero closed surfaces is a fundamental task for geometric processing and computer graphics. Existing methods usually suffer from a lack of practical robustness or poor quality. In this paper, we present a practically robust method to compute high-quality spherical parameterizations with bijection and low isometric distortion. Our method is based on the hierarchical scheme containing mesh decimation and parameterization refinement. The practical robustness of our method relies on two novel techniques. The first one is a flat-to-extrusive decimation strategy, which contains two decimation error metrics to alleviate the difficulty of further mesh refinement. The second is a flexible group refinement technique that consists of flexible vertex insertion and efficient volumetric distortion minimization to control the maximum distortion. We convert the task of volumetric distortion minimization to one of tetrahedral mesh improvement to make the vertices distribute uniformly for efficient refinement. Compared with state-of-the-art methods, our method is more practically robust and possesses better mapping qualities. We demonstrate the efficacy of our method in spherical parameterization computations on a data set containing over five thousand complex models.

Virtual reality applications prefer real walking to provide highly immersive presence than other locomotive methods. Mapping-based techniques are very effective for supporting real walking in small physical workspaces while exploring large virtual scenes. However, the existing methods for computing real walking maps suffer from poor quality due to distortion. In this paper, we present a novel divide-and-conquer method, called Smooth Assembly Mapping (SAM), to compute real walking maps with low isometric distortion for large-scale virtual scenes. First, the input virtual scene is decomposed into a set of smaller local patches. Then, a group of local patches is mapped together into a real workspace by minimizing a low isometric distortion energy with smoothness constraints between the adjacent patches. All local patches are mapped and assembled one by one to obtain a complete map. Finally, a global optimization is adopted to further reduce the distortion throughout the entire map. Our method easily handles teleportation technique by computing maps of individual regions and assembling them with teleporter conformity constraints. A large number of experiments, including formative user studies and comparisons, have shown that our method succeeds in generating high-quality real walking maps from large-scale virtual scenes to small real workspaces and is demonstrably superior to state-of-the-art methods.

Abstract PolyCubes provide compact representations for closed complex shapes and are essential to many computer graphics applications. Existing automatic PolyCube construction methods usually suffer from poor quality or time‐consuming computation. In this paper, we provide a highly efficient method to compute volumetric PolyCube‐maps. Given an input tetrahedral mesh, we utilize two novel normal‐driven volumetric deformation schemes and a polycube‐allowable mesh segmentation to drive the input to a volumetric PolyCube structure. Our method can robustly generate foldover‐free and low‐distortion PolyCube‐maps in practice, and provide a flexible control on the number of corners of Polycubes. Compared with state‐of‐the‐art methods, our method is at least one order of magnitude faster and has better mapping qualities. We demonstrate the efficiency and efficacy of our method in PolyCube construction and all‐hexahedral meshing on various complex models.

We present a novel method, called Simplex Assembly , to compute inversion-free mappings with low or bounded distortion on simplicial meshes. Our method involves two steps: simplex disassembly and simplex assembly. Given a simplicial mesh and its initial piecewise affine mapping, we project the affine transformation associated with each simplex into the inversion-free and distortion-bounded space. The projection disassembles the input mesh into disjoint simplices. The disjoint simplices are then assembled to recover the original connectivity by minimizing the mapping distortion and the difference of the disjoint vertices with respect to the piecewise affine transformations, while the piecewise affine mapping is restricted inside the feasible space. Due to the use of affine transformations as variables, our method explicitly guarantees that no inverted simplex occurs, and that the mapping distortion is below the bound during the optimization. Compared with existing methods, our method is robust to an initialization with many inverted elements and positional constraints. We demonstrate the efficiency and robustness of our method through a variety of geometric processing tasks.

Computing locally injective mappings with low distortion in an efficient way is a fundamental task in computer graphics. By revisiting the well-known MIPS (Most-Isometric ParameterizationS) method, we introduce an advanced MIPS method that inherits the local injectivity of MIPS, achieves as low as possible distortions compared to the state-of-the-art locally injective mapping techniques, and performs one to two orders of magnitude faster in computing a mesh-based mapping. The success of our method relies on two key components. The first one is an enhanced MIPS energy function that penalizes the maximal distortion significantly and distributes the distortion evenly over the domain for both mesh-based and meshless mappings. The second is a use of the inexact block coordinate descent method in mesh-based mapping in a way that efficiently minimizes the distortion with the capability not to be trapped early by the local minimum. We demonstrate the capability and superiority of our method in various applications including mesh parameterization, mesh-based and meshless deformation, and mesh improvement.

3D geometric features constitute rich details of polygonal meshes. Their analysis and editing can lead to vivid appearance of shapes and better understanding of the underlying geometry for shape processing and analysis. Traditional mesh smoothing techniques mainly focus on noise filtering and they cannot distinguish different scales of features well, even mixing them up. We present an efficient method to process different scale geometric features based on a novel rolling-guidance normal filter. Given a 3D mesh, our method iteratively applies a joint bilateral filter to face normals at a specified scale, which empirically smooths small-scale geometric features while preserving large-scale features. Our method recovers the mesh from the filtered face normals by a modified Poisson-based gradient deformation that yields better surface quality than existing methods. We demonstrate the effectiveness and superiority of our method on a series of geometry processing tasks, including geometry texture removal and enhancement, coating transfer, mesh segmentation and level-of-detail meshing.

We present a novel method to generate high-quality simplicial meshes with specified anisotropy. Given a surface or volumetric domain equipped with a Riemannian metric that encodes the desired anisotropy, we transform the problem to one of functional approximation. We construct a convex function over each mesh simplex whose Hessian locally matches the Riemannian metric, and iteratively adapt vertex positions and mesh connectivity to minimize the difference between the target convex functions and their piecewise-linear interpolation over the mesh. Our method generalizes optimal Delaunay triangulation and leads to a simple and efficient algorithm. We demonstrate its quality and speed compared to state-of-the-art methods on a variety of domains and metrics.