MLS Projection- For Smoothing

For every point on the surface – do the following

  • Get a neighborhood - we are taking the n closest points- and using a KDTree data structure to make this faster. The kdtree is implemented by

(This is only in the smoothing step. In the hole filling step we are taking all points within a certain radius because, each time we add a point to the surface, the KD tree structure must also be updated- and I don’t have the code for this right now.)

  • If r the point we are interested in, let q be the projection of r on the local reference domain H (that we are yet to find). Then q can be written as q=r+nt, where t is the distance of the reference plane H from r and n its normal.
  • Now we want to solve for H (find n and t) in such a way that the following is minimized

To do this Powell minimization is used. The initial guess for Powell minimization is however obtained by putting t=0 and solving 4 to get initial n.

  • Once we get the local reference plane H, we create a local coordinate system with q as the origin, and n as the z axis. Now fit a bi-quadratic polynomial g

And evaluate this polynomial at (0,0) to give the desired MLS projection

MLS Projection- For Hole filling

While the above method was used for smoothing, for hole filling, I actually omitted the iterative process (using the iterative solver Powell minimization) of finding the local reference plane H. I used t=0 and n as obtained from weighted PCA- in fact this was the guess (initial estimate) in the smoothing step and the paper by Prof. Claudio.

Procedure:

For each new point in the parametric domain,

Select a neighborhood for the point. The neighborhood can be selected either by taking the n closest points or by taking all points within a certain radius. Right now, we are taking all points within a certain radius

  • Do a weighted PCA to find the best fit plane plane for this neighborhood. Now parameterize the point set (the point and its neighborhood) by projecting onto the PCA plane.
  • To these points fit a bi-quadratic polynomial surface (doing a moving least squares fit about this point).
  • Evaluate the surface we obtain at the parameter value corresponding to the point of interest.
  • This is the MLS projection onto the surface

Parameterization Techniques: (Chronological order)

We started with the idea of projecting everything onto a plane (perhaps least squares plane). However we cannot handle complex geometry if we do this.

Then we looked at floaters parameterization. (Floaters mesh less parameterization)

(

The floaters paper actually gives a way to find the boundary in the point cloud and parameterize it- but unfortunately I saw a different version of this paper earlier and only today I saw the version which gives this information.

Therefore we can directly parameterize a point cloud without the use of a mesh. And our method should work for any point cloud.

extracts from the paper

Floaters Meshless Parameterization:

Floaters Shape preserving weights: (described for a mesh in he original paper- he how however says this can be used in shape preserving parameterization too)

Take each point P and its neighbors and construct planar approximation using geodesic polar maps- the figure below (center and right figs) .

(Here i is the point under consideration and jks are the neighbors).
Harmonic Maps-

The weights between a pair of vertices is given by

About harmonic maps:

Where h is the parameter value of the ith point.

Mapping boundary – From paper- (Unfortunately, we did not read this too)

Floaters Vs Harmonic Maps

Good things about the harmonic Maps:

provably attempts to minimize metric distortion directly-

(Floaters method does not claim this)

Negative about harmonic maps:

It might result in flips- unlike floaters – In other words, we might have negative weights when we use the above equation to find weights between vertices.

When a negative weight occurs, it is replaced by a uniform spring constant. This is what we too do.

Least Squares Conformal Maps – (around 10 years after the harmonic maps paper appeared.)

  1. Minimizes distortion- Attempt to preserve angles- resulting parameterization is conformal in the least squares sense
  2. Guarantee that there are no flips
  3. Allow the border to freely move- this is actually an advantage and not a disadvantage (we can fix the boundary if we want to however)

I am not completely sure why we rejected this actually- but one of the reasons is probably- this preserves angles more effectively- so the distortion in triangle size we thought perhaps was a little more than harmonic maps from the cube image that we first parameterized. However I am not sure if this is true.

Geometric Stretch Minimization:

This is one thing we can do to improve our parameterization. This is independent of the initial parameterization and is just a technique to measure the distortion – so that we can change our parameterization according to the distortion at each triangle

Geometric stretch: A metric to penalize the under sampling of geometry

Here are some pictures to see the effect of stretch minimization from their paper

The picture on the left is the floaters parameterization (and texture mapping done using this parameterization). The right side is after they did a stretch minimization process. In the left picture, the ears have occupied a very small area in the parameterization.

Extract about stretch:

Expression for Geometric stretch:

Complete List of References:

REFERENCES:

[1]Marc Alexa, Johannes Behr, Daniel Cohen-Or, Shachar Fleishman, David Levin and Claudio T. Silva “Computing and Rendering Point Set Surfaces”, IEEE Transactions on Computer Graphics and Visulization V9, No.1 – 2003

[2]Elaine Cohen Richard F Riesenfeld Greshon Elber, “Geometric Modelling with Splines- An introduction”

[3]M. Eck, T. DeRose, T. Duchamp, H. Hoppe, M. Lounsbery, W. Stuetzle, “Multiresolution analysis of arbitrary meshes”, ACM SIGGRAPH 1995, pages 173-182.

[4]Eck, M., Hoppe, H. "Automatic reconstruction of B-spline surfaces of arbitrary topological type." SIGGRAPH '96. New Orleans, LA, USA, 4-9 Aug. 1996. p. 325-34.

[5]Eisert, P.; Steinbach, E.; Girod, B. ,”Automatic 3-D Model Synthesis from Measured Range Data”, Ieee Transactions On Circuits And Systems For Video Technology, Vol. 10,

[6]Shachar Fleishman, Marc Alexa, Daniel Cohen-Or and Claudio T. Silva, “Progressive Point Set Surfaces”. ACM TOG03 22(4) 997-1011-

[7]M. S. Floater, “Parametrization and smooth approximation of surface triangulations”, Comp. Aided Geom. Design 14 (1997), 231-250.

[8]M. S. Floater and K. Hormann, “Surface Parameterization: a Tutorial and Survey”, Advances on Multiresolution in Geometric Modelling, N. Dodgson, M. S. Floater, and M. Sabin (eds.), Springer-Verlag, Heidelberg.

[9]M. S. Floater and M. Reimers, “Meshless parameterization and surface reconstruction”, Comp. Aided Geom. Design 18 (2001), 77-92.

[10]Benjamin F. Gregorski, Bernd Hamann, Kenneth I. Joy , “Reconstruction of B-spline Surfaces from Scattered Data Points”, Computer Graphics International 2000. pp. 163-172. 2000.

[11]Guo, B.N., Surface Reconstruction: From Points to Splines, CAD(29), No. 4, April 1997, pp. 269-277. 9703BibRef

[12]H. Hoppe, T. DeRose, T. Duchamp, M. Halstead, H. Jin, J. McDonald, J. Scheweitzer, and W. Stuetzle, “Piecewise smooth surface reconstruction”, Proc. ACM SIGGRAPH, pp. 295-302, July 1994.

[13]H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, W. Stuetzle, “Surface reconstruction from unorganized points”, ACM SIGGRAPH 1992, pages 71-78.

[14]Andrei Khodakovsky, Nathan Litke and Peter Schröder, “Globally Smooth Parameterizations with Low Distortion”, SIGGRAPH 2003

[15]Venkat Krishnamurthy , Marc Levoy, Fitting smooth surfaces to dense polygon meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.313-324, August 1996

[16]Ohtake Y., Belyaev A., Alexa M., Turk G., Seidel H.-P., "Multi-level partition of unity implicits", ACM Transactions on Graphics (SIGGRAPH 03 Proceedings), vol. 22, No. 3, 2003, pp. 463-470

[17]Peter Lancaster and Kestutis Salkauskas, “Curve and Surface Fitting- An introduction”

[19]I.-K. Lee. “Curve reconstruction from unorganized points”, Computer Aided Geometric Design, 17(2):161--177, February 2000.

[20]Levin, D., “The approximation power of moving least-squares”, Math. Comp. 67 (1998) 1517-1531

[21]Lévy, Bruno and Petitjean, Sylvain and Ray Nicolas and Maillot,Jérome. “Least Squares Conformal Maps for Automatic Texture Atlas Generation” In Siggraph 2002. July 2002.

[22]N. Mitra, A. Nguyen, L. Guibas. ,“Estimating Surface Normals in Noisy Point Cloud Data”, Proc. 19th ACM Symp. Comput. Geometry (SoCG), pages 322-328, 2003. PDF file for this paper.

[23]I.K. Park, I.D. Yun, S.U. Lee, "Constructing NURBS Surface Model from Scattered and Unorganized Range Data", Proc. 2nd International Conference on 3-D Digital Imaging and Modeling . Ottawa, Canada, October 1999

[24]L. Szobonya and G. Renner, “Construction of curves and surfaces based on point clouds”,Computer and Automation Research Institute Budapest, Hungary

[25]Jianning Wang and Manuel M. Oliveira. “A Hole Filling Strategy for Reconstruction of Smooth Surfaces in Range Images”, XVI Brazilian Symposium on Computer Graphics and Image Processing. São Carlos, SP. October 12-15, 2003.