Abstract:
We present a robust algorithm for estimating visibility from a given viewpoint for a point set containing concavities, non-uniformly spaced samples, and possibly corrupted with noise. Instead of performing an explicit surface reconstruction for the points set, visibility is computed based on a construction involving convex hull in a dual space, an idea inspired by the work of Katz et al. We derive theoretical bounds on the behavior of the method in the presence of noise and concavities, and use the derivations to develop a robust visibility estimation algorithm. In addition, computing visibility from a set of adaptively placed viewpoints allows us to generate locally consistent partial reconstructions. Using a graph based approximation algorithm we couple such reconstructions to extract globally consistent reconstructions. We test our method on a variety of 2D and 3D point sets of varying complexity and noise content.
Results:
| (Below) Curve reconstruction results for points sampled off apple, butterfly, crab, and dolphin models with different noise amounts and nonuniform sampling. For illustration, sample points are also shown in orange in corresponding insets. Medium-noise and high-noise correspond to uniform random perturbations in the normal direction respectively by 1% and 2% of the diagonal length of the original bounding boxes. | ||
| ||
| (Below) Surface reconstruction results on various models using Algorithm 2. (Left to right) A well-sampled kitten model, Igea face model with varying levels of detail, mother-and-child model having narrow features and large holes, fandisk model containing sharp feature curves and edges. Note that while state-of-the-art surface reconstruction methods can handle such inputs equally well or better, a visibility based surface reconstruction method is interesting as it links two apparently different problems in computer graphics and computational geometry. | ||
| ||
| (Below) Typical behavior of original HPR and robust HPR on raw scanned data from a given viewpoint (not shown), with the hidden points in pink and visible points in yellow. Notice that the boundary between visible and hidden regions is sharp with robust HPR, indicating few misclassifications. In absence of ground truth, we show the AMLS + cocone based reconstruction and use the surface for visibility computation (left column) for comparison. Notice the result also has misclassifications. We highlight some regions where original HPR clearly produces a large number of misclassifications. The scanner noise parameter is estimated using a calibration plane | ||
| ||
| (Below) Reconstruction results for point set from Igea model corrupted with uniform noise in normal direction of magnitude 1% of bounding box diagonal length. (Left to right) Surface reconstruction of original point set, of point set obtained by smoothing the corrupted point set using connectivity obtained from original HPR operator, and of point set obtained by smoothing the corrupted point set using connectivity obtained from proposed robust HPR operator. Both in the case of original HPR and robust HPR, we avoid pruning of long edges in the connectivity graphs based on thresholds and heuristics. Due to long incorrect connections, the middle model degrades due to smoothing. Interior or back facing triangles are in blue. | ||
| ||
Bibtex:
@article{mtsm_robustPointVisibility_smi_10,
title = "Visibility of noisy point cloud data",
journal = "Computers and Graphics",
author = "Ravish Mehra and Pushkar Tripathi and Alla Sheffer and Niloy J. Mitra",
volume = "In Press, Accepted Manuscript",
number = "",
pages = " - ",
year = "2010",
note = "",
url = "http://www.sciencedirect.com/science/article/B6TYG-4YMB660-1/2/eb083cf7f95ad4248c925f87e7348706",
}
|
|
