mobile off
Physically-Based Simulation
Fluid Interaction
Ice and Snow
Shell Deformation
User Behavior Analysis
Sentiment Analysis
Outlier Detection
Automatic Player Behavior Analysis
Adaptive Agent Navigation
Crowd Simulation
Graphics Applications
Artificial Life
3D Geometry Processing
Real domain data visualization
Integral MLS Surface Model
SDF-based Geometry Synthesis
Point-based Geometry and Modeling
Texture Processing
Integral MLS Surface Model

1. Background

Building implicit surfaces from discrete geometry primitives that include point sets and polygon soups provides a useful tool for various applications. Shen and his colleagues [Shell et al. 2004, Shen 2007] have extended traditional MLS equations for point sets by integrating the discrete points of each triangle. The aim is to interpolate (i.e. extract implicit surfaces for) or approximate (i.e. envelop implicit surfaces for) signed distances by offset values from a query point to all of the discrete triangles.

Their equations are as follows:


where f(x)=0 is an implicit surface equation formed from a polygon-soup model with N discrete triangles; x is a query point; pk is a position on a triangle Tk; nk is the normal vector of Tk; b is a basis vector; and w(x, pk) is a weighting function. By adopting integrations, not conventional discrete sums for points on triangles, the authors succeeded in creating smooth surfaces without any artifacts caused by discontinuities.

C. Shen, J.F. O'Brien, and J.R. Shewchuk. "Interpolating and Approximating Implicit Surfaces from Polygon Soup," ACM Trans. Graph. vol. 23, no. 3, pp. 896-904, Aug 2004.
C. Shen, "Building Interpolating and Approximating Implicit Surfaces Using Moving Least Squares," PhD dissertation, Dept. of Electrical Engineering and Computer Science, University of California at Berkeley, 2007.

2. Problems in Shen et al.

Unfortunately, Shen and his colleagues did not provide closed-form solutions to the integral equations shown in (2) and (3); rather, they only provided analytical line-integration solutions, with the final area integration being calculated as a numerical integration of the analytical line-integration solutions for each triangle. Moreover, unlike traditional MLS techniques for point sets, it is not straightforward to encompass whole triangle-soup models in the approximation mode (i.e. ε≠0 in (5)). Although they did not mention the reasons, Shen and his colleagues found that the implicit surfaces created for f(x)=0 and ε≠0 enclose the models incompletely. This problem is illustrated in Figure A and B. To address this problem, they introduced an iterative routine to determine the parameters for each triangle, which inevitably involves considerable computation time.


3. Analytic Solution

Shen and his colleagues did not provide closed-form solutions of the 2D integrals in (2) and (3) for n=1 in (5). Instead, the original authors selected a hybrid approach that used both analytical line integrals and numerical techniques (see Section 5.3 for details). From our analysis, we note that the weighting function is cancelled out in many cases: we can make things simpler and achieve similar approximation effects, even for very large n. This implies that we have freedom in selecting weighting functions. The only two requirements for the functions are 1) a singularity near = 0 and 2) asymptotic features with respect to the axis = 0 (i.e. the weighting function approaches 0 for large.

In our paper, we present solutions to (5) for a specific 2D case, where n=1/2, and a specific 3D case, where n=3/4. Those parameters make the ak terms in (3) dimensionless, as will be shown. As discussed in Section 3.2.1 of our paper, the integral form of MLS is not suitable for approximation, particularly for concavities. We therefore confine our discussion to the interpolation case with ε=0. We note that part of the integral in (3) simplifies to an angle (radian) for 2D cases, and to a solid angle (steradian) for 3D cases. In addition, we prove that the surface normal vectors of the implicit surface c(x) = 0 in our configuration are exactly the same as the angle-weighted pseudo-normal vectors in [4]. For 3D case, we have found analytic solution for Equation (1) to (5) as follows:

4. Application

A. Face-based Weighted Average
From the analytic solutions (6) and (7), (1) can be represented as a face-based weighted sum of signed
distances from x to all triangle faces, i.e.:


B. Approximation without Iteration
From the observation that the function c(x) is a weighted sum of signed distances between x and each plane
including a triangle, as described in Section 5.1, we modify Equation (44) as follows to obtain implicit-surface
enveloping, even when ε=0:


Our approximation (i.e. enveloping) implicit surfaces are defined as follows:


where the offset h (h>0) values control the enveloping implicit isosurfaces.

Figure C shows typical results from our approximation method.


Fig. C. Approximation results

Table A summarizes the computation times for our method and Shen’s.


5. Related Publications

[1] Taejung Park, Sung-Ho Lee and Chang-Hun Kim, "Analytic Solutions of Integral Moving Least Squares for
Polygon Soups," IEEE Transactions on Visualization and Computer Graphics, Volume 17, Number 12, pp.