Shape segmentation using local slippage analysis

ABSTRACT

We propose a method for segmentation of 3D scanned shapes into simple geometric parts. Given an input point cloud, our method computes a set of components which possess one or more slippable motions: rigid motions which, when applied to a shape, slide the transformed version against the stationary version without forming any gaps. Slippable shapes include rotationally and translationally symmetrical shapes such as planes, spheres, and cylinders, which are often found as components of scanned mechanical parts. We show how to determine the slippable motions of a given shape by computing eigenvalues of a certain symmetric matrix derived from the points and normals of the shape. Our algorithm then discovers slippable components in the input data by computing local slippage signatures at a set of points of the input and iteratively aggregating regions with matching slippable motions. We demonstrate the performance of our algorithm for reverse engineering surfaces of mechanical parts.

REFERENCES

• 1: Marc Alexa, Linear combination of transformations, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 2: Ioana M. Boier-Martin, Domain decomposition for multiresolution analysis, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 3: {BMV01} Benko P., Martin R., Varady T.: Algorithms for reverse engineering boundary representation models. Computer Aided Design 33, 11 (2001).
• 4: {CM91} Chen Y., Medioni G.: Object modeling by registration of multiple range images. In Proc. IEEE Conf. on Robotics and Automation (1991).
• 5: {ELZ02} Edelsbrunner H., Letscher D., Zomorodian A.: Topological persistence and simplification. Discrete Comput. Geom. 28 (2002), 511--533.
• 6: {GIRL03} Gelfand N., Ikemoto L., Rusinkiewicz S., Levoy M.: Geometrically stable sampling for the ICP algorithm. In Proc. Intl. Conf. on 3D Imaging and Modeling (2003).
• 7: Michael Garland , Andrew Willmott , Paul S. Heckbert, Hierarchical face clustering on polygonal surfaces, Proceedings of the 2001 symposium on Interactive 3D graphics, p.49-58, March 2001 [doi>10.1145/364338.364345]
• 8: Venkat Krishnamurthy , Marc Levoy, Fitting smooth surfaces to dense polygon meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.313-324, August 1996 [doi>10.1145/237170.237270]
• 9: {KT03} Katz S., Tal A.: Hierarchical mesh decomposition using fuzzy clustering and cuts. In Proc. SIGGRAPH (2003).
• 10: Bruno Lévy , Sylvain Petitjean , Nicolas Ray , Jérome Maillot, Least squares conformal maps for automatic texture atlas generation, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 11: {MNG04} Mitra N., Nguyen A., Guibas L.: Estimating surface normals in noisy point cloud data. In International Journal of Computational Geometry and Applications (2004). To Appear.
• 12: {PHOW04} Pottmann H., Hofer M., Odehnal B., Wallner J.: Line geometry for 3D shape understanding and reconstruction. In ECCV (2004).
• 13: F. C. Park , Bahram Ravani, Smooth invariant interpolation of rotations, ACM Transactions on Graphics (TOG), v.16 n.3, p.277-295, July 1997 [doi>10.1145/256157.256160]
• 14: H. Pottmann , T. Randrup, Rotational and helical surface approximation for reverse engineering, Computing, v.60 n.4, p.307-322, 1998 [doi>10.1007/BF02684378]
• 15: {PW01} Pottmann H., Wallner J.: Computational Line Geometry. Springer Verlag, 2001.
• 16: {RL01} Rusinkiewicz S., Levoy M.: Efficient variants of the ICP algorithm. In Proc. Intl. Conf. on 3D Imaging and Modeling (2001).
• 17: Nickolas S. Sapidis , Paul J. Besl, Direct construction of polynomial surfaces from dense range images through region growing, ACM Transactions on Graphics (TOG), v.14 n.2, p.171-200, April 1995 [doi>10.1145/221659.221672]
• 18: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 19: {Sri03} Srinivasan V.: Theory of Dimensioning. Marcel Dekker, 2003.
• 20: Pedro V. Sander , John Snyder , Steven J. Gortler , Hugues Hoppe, Texture mapping progressive meshes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.409-416, August 2001 [doi>10.1145/383259.383307]
• 21: {VMC97} Varady T., Martin R., Cox J.: Reverse engineering of geometric models - an introduction. Computer-Aided Design 29, 4 (1997).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Algorithms