7269331
Quadric Surface Extraction by Variational Shape Approximation
Based on Lloyd iteration, we present a variational method for extracting general quadric surfaces from a 3D mesh surface. This work extends the previous variational methods that extract only planes or special types of quadrics, i.e., spheres and circular cylinders. Instead of using the exact L2 error metric, we use a new approximate L2 error metric to make our method more efficient for computing with general quadrics. Furthermore, a method based on graph cut is proposed to smooth irregular boundary curves between segmented regions, which greatly improves the final results.
181647
Geometric modeling with conical meshes and developable surfaces
In architectural freeform design, the relation between shape and fabrication poses new challenges and requires more sophistication from the underlying geometry. The new concept of conical meshes satisfies central requirements for this application: They are quadrilateral meshes with planar faces, and therefore particularly suitable for the design of freeform glass structures. Moreover, they possess a natural offsetting operation and provide a support structure orthogonal to the mesh. Being a discrete analogue of the network of principal curvature lines, they represent fundamental shape characteristics. We show how to optimize a quad mesh such that its faces become planar, or the mesh becomes even conical. Combining this perturbation with subdivision yields a powerful new modeling tool for all types of quad meshes with planar faces, making subdivision attractive for architecture design and providing an elegant way of modeling developable surfaces.
3170428
Fitting B-spline curves to point clouds by curvature-based squared distance minimization
Computing a curve to approximate data points is a problem encountered frequently in many applications in computer graphics, computer vision, CAD/CAM, and image processing. We present a novel and efficient method, called squared distance minimization (SDM), for computing a planar B-spline curve, closed or open, to approximate a target shape defined by a point cloud, that is, a set of unorganized, possibly noisy data points. We show that SDM significantly outperforms other optimization methods used currently in common practice of curve fitting. In SDM, a B-spline curve starts from some properly specified initial shape and converges towards the target shape through iterative quadratic minimization of the fitting error. Our contribution is the introduction of a new fitting error term, called the squared distance (SD) error term, defined by a curvature-based quadratic approximant of squared distances from data points to a fitting curve. The SD error term faithfully measures the geometric distance between a fitting curve and a target shape, thus leading to faster and more stable convergence than the point distance (PD) error term, which is commonly used in computer graphics and CAGD, and the tangent distance (TD) error term, which is often adopted in the computer vision community. To provide a theoretical explanation of the superior performance of SDM, we formulate the B-spline curve fitting problem as a nonlinear least squares problem and conclude that SDM is a quasi-Newton method which employs a curvature-based positive definite approximant to the true Hessian of the objective function. Furthermore, we show that the method based on the TD error term is a Gauss-Newton iteration, which is unstable for target shapes with high curvature variations, whereas optimization based on the PD error term is the alternating method that is known to have linear convergence.
772940
Fitting subdivision surfaces to unorganized point data using SDM
We study the reconstruction of smooth surfaces from point clouds. We use a new squared distance error term in optimization to fit a subdivision surface to a set of unorganized points, which defines a closed target surface of arbitrary topology. The resulting method is based on the framework of squared distance minimization (SDM) proposed by Pottmann et al. Specifically, with an initial subdivision surface having a coarse control mesh as input, we adjust the control points by optimizing an objective function through iterative minimization of a quadratic approximant of the squared distance function of the target shape. Our experiments show that the new method (SDM) converges much faster than the commonly used optimization method using the point distance error function, which is known to have only linear convergence. This observation is further supported by our recent result that SDM can be derived from the Newton method with necessary modifications to make the Hessian positive definite and the fact that the Newton method has quadratic convergence.
2900427
Reconstructing B-spline Curves from Point Clouds--A Tangential Flow Approach Using Least Squares Minimization
We present a novel algorithm based on least-squares minimization to approximate point cloud data in 2D plane with a smooth B-spline curve. The point cloud data may represent an open curve with self intersection and sharp corner. Unlike other existing methods, such as the moving least-squares method and the principle curve method, our algorithm does not need a thinning process. The idea of our algorithm is intuitive and simple - we make a B-spline curve grow along the tangential directions at its two end-points following local geometry of point clouds. Our algorithm generates appropriate control points of the fitting B-spline curve in the least squares sense. Although presented for the 2D case, our method can be extended in a straightforward manner to fitting data points by a B-spline curve in higher dimensions
2123278
Program optimization using indexed and recursive data structures
This paper describes a systematic method for optimizing recursive functions using both indexed and recursive data structures. The method is based on two critical ideas: first, determining a minimal input increment operation so as to compute a function on repeatedly incremented input; second, determining appropriate additional values to maintain in appropriate data structures, based on what values are needed in computation on an incremented input and how these values can be established and accessed. Once these two are determined, the method extends the original program to return the additional values, derives an incremental version of the extended program, and forms an optimized program that repeatedly calls the incremental program. The method can derive all dynamic programming algorithms found in standard algorithm textbooks. There are many previous methods for deriving efficient algorithms, but none is as simple, general, and systematic as ours.
10720584
Graph-Based Semi-Supervised Learning as a Generative Model
This paper proposes and develops a new graph-based semi-supervised learning method. Different from previous graph-based methods that are based on discriminative models, our method is essentially a generative model in that the class conditional probabilities are estimated by graph propagation and the class priors are estimated by linear regression. Experimental results on various datasets show that the proposed method is superior to existing graph-based semi-supervised learning methods, especially when the labeled subset alone proves insufficient to estimate meaningful class priors.
43519756
The Number of Loopless 4-Regular Maps on the Projective Plane
In this paper rooted loopless (near) 4-regular maps on surfaces such as the sphere and the projective plane are counted and exact formulae with up to three or four parameters for such maps are given. Several classical results on regular maps and one-faced maps are deduced.
9599152
A classification based similarity metric for 3D image retrieval
We present a principled method of obtaining a weighted similarity metric for 3D image retrieval, firmly rooted in Bayes decision theory. The basic idea is to determine a set of most discriminative features by evaluating how well they perform on the task of classifying images according to predefined semantic categories. We propose this indirect method as a rigorous way to solve the difficult feature selection problem that comes up in most content based image retrieval tasks. The method is applied to normal and pathological neuroradiological CT images, where we take advantage of the fact that normal human brains present an approximate bilateral symmetry which is often absent in pathological brains. The quantitative evaluation of the retrieval system shows promising results.
34486970
Simulation of miscible binary mixtures based on lattice Boltzmann method
Miscible fluid mixtures, like pouring honey into water, Coca Cola into strong wine, are common phenomena in our daily life. While two miscible fluids are mixed together, their appearances in terms of colors and shapes will change due to their mixing interaction. The interaction between the mixture components could be regarded as a combination of the diffusing process and demixing process. If the former dominates the interaction, it is miscible; otherwise, it is immiscible. The complex microscopic interplay between the mixture components makes the simulation highly challenging. So far, there have been some dedicated research in computer graphics dealing with immiscible mixtures, but few works have been done focusing on miscible mixtures. In this paper, for the first time, we introduce a two-fluid lattice Boltzmann method (LBM), called TFLBM, applied to miscible binary mixtures. Different from other similar methods, the viscous and diffusing properties of the fluid in our work are considered separately, so that the physical insight is exposed more clearly and rationally. In addition, the operation of LBM is mostly a linear local computation, and graphics processing unit (GPU) has been utilized to achieve real-time simulation. Copyright © 2006 John Wiley & Sons, Ltd.