[Back]

S. Ohrhallinger, M. Wimmer, S. Mitchell:
"Curve Reconstruction with Many Fewer Samples";
Talk: Symposium on Geometry Processing, Berlin; 2016-06-20 - 2016-06-24; in: "Computer Graphics Forum", Computer Graphics Forum, 35/5 (2016), ISSN: 1467-8659; 167 - 176.

We consider the problem of sampling points from a collection of smooth curves in the plane, such that the Crust family of proximity-based reconstruction algorithms can rebuild the curves. Reconstruction requires a dense sampling of local features, i.e., parts of the curve that are close in Euclidean distance but far apart geodesically. We show that epsilon<0.47-sampling is sufficient for our proposed HNN-CRUST variant, improving upon the state-of-the-art requirement of epsilon<1/3-sampling. Thus we may reconstruct curves with many fewer samples. We also present a new sampling scheme that reduces the required density even further than epsilon<0.47-sampling. We achieve this by better controlling the spacing between geodesically consecutive points. Our novel sampling condition is based on the reach, the minimum local feature size along intervals between samples. This is mathematically closer to the reconstruction density requirements, particularly near sharp-angled features. We prove lower and upper bounds on reach rho-sampling density in terms of lfs epsilon-sampling and demonstrate that we typically reduce the required number of samples for reconstruction by more than half.

http://dx.doi.org/10.1111/cgf.12973

http://publik.tuwien.ac.at/files/publik_253368.pdf