Loading...
Please wait, while we are loading the content...
Similar Documents
ECG IST-2000-26473 Effective Computational Geometry for Curves and Surfaces ECG Technical Report No . : ECG-TR-244208-01 Smooth-Surface Reconstruction in Near-Linear Time
| Content Provider | Semantic Scholar |
|---|---|
| Author | Funke, Stefan Ramos, Edgar A. |
| Copyright Year | 2008 |
| Abstract | A surface reconstruction algorithm takes as input a set of sa mple points from an unknown closed and smooth surface in 3-d space, and produces a piecewise linear approximation of the surface that contains the sample points. This problem ha s received considerable attention in computer graphics and more recently in computational geo metry. In the latter area, four different algorithms (by Amenta and Bern ‘98; Amenta, Choi, Dey and Leekha ‘00; Amenta, Choi and Kolluri ‘00; Boissonnat and Cazals ‘00) have been pr oposed. These algorithms have a correctness guarantee: if the sample is sufficiently dense t hen the output is a good approximation to the original surface. They have unfortunately a worst-ca e running time that is quadratic in the size of the input because they are based on the constructi on of 3-d Voronoi diagrams or Delaunay tetrahedrizations, which can have quadratic size . Even worse, according to recent work (Erickson ‘01), there are surfaces for which this is the case even when the sample set is “locally uniform” on the surface. In this paper, we describe a new algorithm that also has a correctness guarantee but whose worst-case running time is almost linear. In fact, the running time isO(n log n) wheren is the input size and this is optimal. As in some of the previou s algorithms, the piece-wise linear approximation produced by the new algorithm is a subset of the 3-d Delaunay tetrahedrization; however, this is obtain ed by computing only the relevant parts of the 3-d Delaunay structure. The algorithm first esti ma es for each sample point the surface normal and a parameter that is then used to “decimate ” the set of samples. The resulting subset of sample points is locally uniform and so a reconstru ction based on it can be computed using a simple and fast algorithm. In a last step, the decimat ed points are incorporated into the reconstruction. |
| File Format | PDF HTM / HTML |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
