

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 polygonsoup 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. 896904, 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 closedform solutions to the integral equations shown in (2) and (3); rather, they only provided analytical lineintegration solutions, with the final area integration being calculated as a numerical integration of the analytical lineintegration solutions for each triangle.
Moreover, unlike traditional MLS techniques for point sets, it is not straightforward to encompass whole trianglesoup 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 closedform 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 angleweighted pseudonormal vectors in [4].
For 3D case, we have found analytic solution for Equation (1) to (5) as follows:




4. Application
A. Facebased Weighted Average
From the analytic solutions (6) and (7), (1) can be represented as a facebased 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 implicitsurface 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, SungHo Lee and ChangHun Kim, "Analytic Solutions of Integral Moving Least Squares for Polygon Soups," IEEE Transactions on Visualization and Computer Graphics, Volume 17, Number 12, pp.

