Learning smooth objects by probing

ABSTRACT

This video considers the problem of discovering the boundary S of an unknown smooth object O. The discovery process consists of moving a point probing device in the free space around O so that it repeatedly comes in contact with S. We present a probing strategy for generating a sequence of sample points of S, from which a PL-approximation of S can be constructed, within any desired accuracy. This strategy can be applied in any dimension, although its output is guaranteed only for objects embedded in the plane or in 3-space. For pedagogical purpose, the video focuses on the planar case.

REFERENCES

• 1: P. Alevizos , J. D. Boissonnat , M. Yvinec, Non-convex contour reconstruction, Journal of Symbolic Computation, v.10 n.3-4, p.225-252, Sept./Oct. 1990 [doi>10.1016/S0747-7171(08)80063-6]
• 2: Jean-Daniel Boissonnat , Leonidas J. Guibas , Steve Oudot, Learning smooth objects by probing, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064124]
• 3: Jean-Daniel Boissonnat and Mariette Yvinec. Probing a scene of non-convex polyhedra. Algorithmica, 8:321--342, 1992.
• 4: The CGAL Library. Release 3.1 (http://www.cgal.org).
• 5: Richard Cole , Chee K. Yap, Shape from probing, Journal of Algorithms, v.8 n.1, p.19-38, March 1987 [doi>10.1016/0196-6774(87)90025-3]
• 6: M. Lindenbaum and A. M. Bruckstein. Blind approximation of planar convex sets. IEEE Trans. Robot. Autom., 10(4):517--529, August 1994.
• 7: Qt for X11. By Trolltech (http://www.trolltech.com/products/qt/x11.html).
• 8: T. J. Richardson. Approximation of planar convex sets from hyperplanes probes. Discrete and Computational Geometry, 18:151--177, 1997.
• 9: G. Rote, The convergence rate of the sandwich algorithm for approximating convex functions, Computing, v.48 n.3-4, p.337-361, 1992 [doi>10.1007/BF02238642]
• 10: Steven S. Skiena, Geometric reconstruction problems, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Theory

Keywords:
Delaunay refinement, blind surface approximation, interactive surface reconstruction, manifold learning, surface meshing