Title:
    Initial Mesh Approximation from Scattered Range Data
 

Description

        Generally speaking, our project falls in  the field of surface reconstruction. The goal of surface reconstruction is to determine a simplicial surface M' that approximates an unknown surface M from a cloud of unorganized sample points assumed to lie on or near M. Our surface reconstruction algorithm is based on Hugues Hoppe's Siggraph'92 paper  "Surface Reconstruction from Unorganized Points"  and his PhD thesis with the same title. The uniqueness of his algorithm is that he  made relatively few assumptions on the input sample and tried to provide a robust solution to the unifying general surface reconstruction problem.

Algorithm overview

    Hoppe's approach consists of two stages. In the first stage we define a signed distance function f, which estimates the signed geometric distance to the unknown surface M. In the second stage we use a contouring algorithm to approximate zero set Z(f) by a simplicial surface. To define the signed distance function, we should associate an oriented plane with each of the data points --- tangent plane which serve as local linear approximations to the surface.

    The algorithm consists of the following steps:

    1) Tanget Plane Estimation
        The tangent plane is obtained by fitting a best approximating plane (Oi, Ni ) in the least square sense from the neighborhood of data point Pi. Here, normal Ni is obtained by SVD analysis.

    2) Consistent Tangent Plane Orientation
        The orientation of the tangent planes is determined by propagating the orientation at a starting point, by traversing the minimum spanning tree of the resulting weighted Riemannian graph.

    3) Signed Distance Function
        The signed distance f(p) from an arbitrary point to a known surface M is the distance between p and the closest point z in M, multiplied by 1 or -1, depending on which side of the surface p lies.

    4) Contouring Tracing
        We choose to implement a variation of Marching Cube algorithm( Wyvill's paper ) to extract an isosurface of the signed distance function.
 

Schedule

• May 5 --- May 12:        Make full understanding how the mesh generation algorithm works, and design the data structure(i.e, class definition, module decomposition, etc )
• May 12 --- May 19:      Finish major part of the coding.
• May 19 --- May 26:      Debugging and run the executable program on the test data files. If time permits, we want to do the improvement mentioned in Hoppe's paper, which he didn't implement, such as adaptively adjusting neighboring parameter k, culling of outliers , etc.
• May 26 --- May 28:      Prepare our project presentation.

    Use the same data files which Hoppe used as his test files, our program obtained exactly the same output, and also exposed the similar problems inherent in his
algorithm. Our conclusion is that if we can choose an appropriate parameter, we can
get very smooth and nice mesh of the unknown surface reconstructed.
 

                                    mechpart.4102.pts

                                    club71.16864.pts
 

                                    distcap.12745.pts
 

Other Links

• Presentation Slides ( 3dp.ppt )
• Open Inventor files for the surface reconstructed
• mechpart.iv
• club71.iv
• distcap.iv

• G. Wyvill, C. McPheeters, and B. Wyvill. Data structures for soft objects. The Visual Computer , 2(4):227-234, August 1986.