Материал: [2.1] 3D Imaging, Analysis and Applications-Springer-Verlag London (2012)

4.12 Exercises

1.Derive an algorithm for extracting a list of edges from a triangular mesh stored in a vertex-face list. The complexity should be linear in the number of triangles.

2.Using a data structure of your choice, show how to compute a vertex normal for a triangular mesh. You should choose one of the methods described in Sect. 4.5.1 to compute the normals.

3.In Sect. 4.3.2.1, code is given for traversing the edges incident on a vertex in a halfedge structure. Provide similar code for traversing the faces incident on a vertex.

4.Describe how to implement the edge collapse operation in a halfedge structure. The collapsed edge and one of the vertices must be removed from the structure, edges incident on the deleted vertex must be altered so that they are incident on the retained vertex and finally any degenerate faces must be removed.

5.A sphere can be represented as a subdivision surface using the following rule. The base mesh is a polyhedron, in this case use an icosahedron. The subdivision rule divides each triangle into four smaller triangles by adding vertices halfway along each edge. The new vertices are translated such that their distance from the sphere center is equal to the radius of the sphere. Derive a rule for computing the number of edges, faces and vertices in the representation as a function of the number of iterative subdivisions. Now, using a triangle mesh data structure of your choice, derive a similar rule for computing the number of pointers required to store the representation at each level of iteration.

6.Using a mesh representation of your choice, show how to evaluate the quadric error metric at a vertex.

7.A mesh can be considered as a weighted graph, where edge weights correspond to Euclidean distance between the end nodes. Describe how to implement Dijkstra’s shortest path algorithm in order to achieve fast range searching over a mesh graph stored in a halfedge structure. Given a distance threshold over which to range search, what is the stopping criteria for this algorithm?

References

1.Alliez, P., Gotsman, C.: Recent advances in compression of 3d meshes. In: Dodgson, N., Floater, M., Sabin, M. (eds.) Advances in Multiresolution for Geometric Modeling, pp. 3–26. Springer, Berlin (2005)

2.Asberg, B., Blanco, G., Bose, P., Garcia-Lopez, J., Overmars, M., Toussaint, G., Wilfong, G., Zhu, B.: Feasibility of design in stereolithography. Algorithmica 19(1–2), 61–83 (1997)

3.Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM 18(9), 509–517 (1975)

4.de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications. Springer, Berlin (1997)

5.Biggs, N.: Algebraic Graph Theory. Cambridge University Press, Cambridge (1993)

6.Blanz, V., Vetter, T.: A morphable model for the synthesis of 3D faces. In: Proc. SIGGRAPH, pp. 187–194 (1999)

7.Bloomenthal, J.: Polygonization of implicit surfaces. Comput. Aided Geom. Des. 5(4), 341– 355 (1988)

8.Bloomenthal, J., Bajaj, C., Blinn, J., Cani-Gascuel, M.P., Rockwood, A., Wyvill, B., Wyvill, G. (eds.): Introduction to Implicit Surfaces. Morgan Kaufmann, San Mateo (1997)

9.Bloomenthal, J., Wyvill, B.: Interactive techniques for implicit modeling. In: Proc. Symposium on Interactive 3D Computer Graphics (1990)

10.Botsch, M., Kobbelt, L., Pauly, M., Alliez, P., Levy, B.: Polygon Mesh Processing. AK Peters/CRC Press, Wellesley/Boca Raton (2011)

11.Carr, J.C., Beatson, R.K., Cherrie, J.B., Mitchell, T.J., Fright, W.R., McCallum, B.C., Evans, T.R.: Reconstruction and representation of 3d objects with radial basis functions. In: Proc. SIGGRAPH, pp. 67–76 (2001)

12.Catmull, E., Clark, J.: Recursively generated b-spline surfaces on arbitrary topological meshes. Comput. Aided Des. 10(6), 350–355 (1978)

13.Doo, D., Sabin, M.: Behavior of recursive division surfaces near extraordinary points. Comput. Aided Des. 10(6), 356–360 (1978)

14.Farin, G.: Curves and Surfaces for CAGD: A Practical Guide. Morgan Kaufmann, San Mateo (2002)

15.Foley, J.D., van Dam, A., Feiner, S.K., Hughes, J.F.: Computer Graphics. Addison Wesley, Reading (1995)

16.Fuchs, H., Kedem, Z.M., Naylor, B.F.: On visible surface generation by a priori tree structures. ACM Comput. Graph., 124–133 (1980)

17.Garland, M.: Quadric-based polygonal surface simplification. Ph.D. thesis, Computer Science Department, Carnegie Mellon University (1999)

18.Garland, M., Heckbert, P.S.: Surface simplification using quadric error metrics. In: Proc. SIGGRAPH, pp. 209–216 (1997)

19.Gomes, A.J.P., Voiculescu, I., Jorge, J., Wyvill, B., Galbraith, C.: Implicit Curves and Surfaces: Mathematics, Data Structures and Algorithms. Springer, Berlin (2009)

20.Gu, X., Gortler, S., Hoppe, H.: Geometry images. ACM Trans. Graph. 21(3) (2002) (Proceedings of SIGGRAPH)

21.Hart, J.C.: Ray tracing implicit surfaces. In: SIGGRAPH Course Notes (1993)

22.Hartley, R., Zisserman, A.: Multiple View Geometry in Computer Vision. Cambridge University Press, Cambridge (2000)

23.Heckbert, P.S.: Survey of texture mapping. IEEE Comput. Graph. Appl. 6(11), 56–67 (1986)

24.Hoppe, H.: Efficient implementation of progressive meshes. Comput. Graph. 22(1), 27–36 (1998)

25.Jin, S., Lewis, R.R., West, D.: A comparison of algorithms for vertex normal computations. Vis. Comput. 21(1–2), 71–82 (2005)

26.Johnson, A., Spin-images: A representation for 3-d surface matching. Ph.D. thesis, Robotics Institute, Carnegie Mellon University (1997)

27.Karni, Z., Gotsman, C.: Spectral compression of mesh geometry. In: Proc. SIGGRAPH, pp. 279–286 (2000)

28.Kazhdan, M.: Reconstruction of solid models from oriented point sets. In: Proc. Eurographics Symposium on Geometry Processing (2005)

29.Keller, P.R., Keller, M.M.: Visual Cues: Practical Data Visualization. IEEE Comput. Soc., Los Alamitos (1993)

30.Kimmel, R., Sethian, J.A.: Computing geodesic paths on manifolds. Proc. Natl. Acad. Sci. 95(15), 8431–8435 (1998)

31.Kobbelt, L.: Interpolatory subdivision on open quadrilateral nets with arbitrary topology. Comput. Graph. Forum 15(3), 409–420 (1996)

32.Koenderink, J.J., van Doorn, A.J.: Surface shape and curvature scales. Image Vis. Comput. 10(8), 557–565 (1992)

33.Kutulakos, K.N., Seitz, S.M.: A theory of shape by space carving. Int. J. Comput. Vis. 38(3), 199–218 (2000)

34.Laidlaw, D.H., Trumbore, W.B., Hughes, J.F.: Constructive solid geometry for polyhedral objects. In: Proc. SIGGRAPH, pp. 161–170 (1986)

35.Lebeck, A.O.: Principles and Design of Mechanical Face Seals. Wiley-Interscience, New York (1991)

36.Leotta, M.J., Mundy, J.L.: Predicting high resolution image edges with a generic, adaptive, 3-d vehicle model. In: Proc. CVPR, pp. 1311–1318 (2009)

37.Levoy, M.: Display of surfaces from volume data. IEEE Comput. Graph. Appl. 8(3), 29–37 (1988)

38.Litke, N., Levin, A., Schröder, P.: Fitting subdivision surfaces. In: Proc. Conference on Visualization (2001)

39.Loop, C.: Smooth subdivision surfaces based on triangles. Master’s thesis, University of Utah (1987)

40.Lorensen, W.E., Cline, H.E.: Arching cubes: a high resolution 3d surface construction algorithm. Comput. Graph. 21(4) (1987)

41.Max, N.: Weights for computing vertex normals from facet normals. J. Graph. Tools 4(2), 1–6 (1999)

42.Meyer, M., Desbrun, M., Schröder, P., Barr, A.H.: Discrete differential-geometry operators for triangulated 2-manifolds. Vis. Math. 3(7), 35–57 (2002)

43.Muller, D.E., Preparata, F.P.: Finding the intersection of two convex polyhedra. Theor. Comput. Sci. 7, 217–236 (1978)

44.Murali, T.M., Funkhouser, T.A.: Consistent solid and boundary representations from arbitrary polygonal data. In: Proc. Symposium on Interactive 3D Graphics (1997)

45.Nehab, D., Rusinkiewicz, S., Davis, J.E., Ramamoorthi, R.: Efficiently combining positions and normals for precise 3D geometry. ACM Trans. Graph. 24(3), 536–543 (2005) (Proceedings of SIGGRAPH)

46.Nielson, G.M., Hagen, H., Müller, H.: Scientific Visualization: Overviews, Methodologies, and Techniques. IEEE Computer Society Press, New York (1997)

47.Pajarola, R., Rossignac, J.: Compressed progressive meshes. IEEE Trans. Vis. Comput. Graph. 6(1), 79–93 (2000)

48.Paysan, P., Knothe, R., Amberg, B., Romdhani, S., Vetter, T.: A 3D face model for pose and illumination invariant face recognition. In: Proc. IEEE Intl. Conf. on Advanced Video and Signal based Surveillance (2009)

49.Peng, J., Kim, C.S., Kuo, C.C.J.: Technologies for 3d mesh compression: a survey. J. Vis. Commun. Image Represent. 16(6), 688–733 (2005)

50.Peters, J., Reif, U.: Subdivision Surfaces. Springer, New York (2008)

51.Pharr, M., Humphreys, G.: Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann, San Mateo (2010)

52.Phillips, P.J., Flynn, P.J., Scruggs, T., Bowyer, K.W., Chang, J., Hoffman, K., Marques, J., Jaesik, M., Worek, W.: Overview of the face recognition grand challenge. In: Proc. CVPR, pp. 947–954 (2005)

53.Piegl, L., Tiller, W.: The NURBS Book. Springer, Berlin (1996)

54.Post, F.H., Nielson, G.M., Bonneau, G.P. (eds.): Data Visualization: The State of the Art. Springer, Berlin (2002)

55.Reddy, D., Agrawal, A., Chellappa, R.: Enforcing integrability by error correction using 1- minimization. In: Proc. CVPR (2009)

56.Rogers, D.F.: An Introduction to NURBS with Historical Perspective. Morgan Kaufmann, San Mateo (2001)

57.Rusinkiewicz, S., Levoy, M.: Qsplat: a multiresolution point rendering system for large meshes. In: Proc. SIGGRAPH, pp. 343–352 (2000)

58.Scharstein, D., Szeliski, R.: A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. Int. J. Comput. Vis. 47(1–3), 7–42 (2002)

59.Sheffer, A., Praun, E., Rose, K.: Mesh parameterization methods and their applications. Found. Trends Comput. Graph. Vis. 2(2), 105–171 (2006)

60.Shen, C., O’Brien, J.F., Shewchuk, J.R.: Interpolating and approximating implicit surfaces from polygon soup. In: Proc. SIGGRAPH, pp. 896–904 (2004)

61.Smith, C.: On vertex-vertex systems and their use in geometric and biological modeling. Ph.D. thesis, University of Calgary (2006)

62.Smith, N.B., Webb, A.: Introduction to Medical Imaging: Physics, Engineering and Clinical Applications. Cambridge University Press, Cambridge (2010)

63.Smith, R.C., Cheeseman, P.: On the representation and estimation of spatial uncertainty. Int. J. Robot. Res. 5(4), 56–68 (1986)

64.Stam, J.: Exact evaluation of Catmull–Clark subdivision surfaces at arbitrary parameter values. In: Proc. SIGGRAPH, pp. 395–404 (1998)

65.Stroud, I.: Boundary Representation Modeling Techniques. Springer, Berlin (2006)

66.Suetens, P.: Fundamentals of Medical Imaging. Cambridge University Press, Cambridge (2009)

67.Takeuchi, S., Kanai, T., Suzuki, H., Shimada, K., Kimura, F.: Subdivision surface fitting with QEM-based mesh simplification and reconstruction of approximated b-spline surfaces. In: Proc. Pacific Conference on Computer Graphics and Applications, pp. 202–212 (2000)

68.Taubin, G.: A signal processing approach to fair surface design. In: Proc. SIGGRAPH, pp. 351–358 (1995)

69.Taubin, G., Rossignac, J.: Geometric compression through topological surgery. ACM Trans. Graph. 17(2), 84–115 (1998)

70.Thürmer, G., Wüthrich, C.A.: Computing vertex normals from polygonal facets. J. Graph. Tools 3(1), 43–46 (1998)

71.Unwin, A., Theus, M., Hofmann, H.: Graphics of Large Datasets: Visualizing a Million. Springer, Berlin (2006)

72.Vince, J.A.: Mathematics for Computer Graphics. Springer, Berlin (2010)

73.Watt, A.: 3D Computer Graphics. Addison Wesley, Reading (1999)

74.Wikipedia: http://en.wikipedia.org/wiki/Catmull-Clark_subdivision_surface. Accessed 23rd January 2012

75.Wikipedia: http://en.wikipedia.org/wiki/Constructive_solid_geometry. Accessed 23rd January 2012

76.Wikipedia: http://en.wikipedia.org/wiki/K-d_tree. Accessed 23rd January 2012

77.Wikipedia: http://en.wikipedia.org/wiki/Loop_subdivision_surface. Accessed 23rd January 2012

78.Weiler, K.: Edge-based data structures for solid modeling in a curved surface environment. IEEE Comput. Graph. Appl. 5(1), 21–40 (1985)

79.Zienkiewicz, O.C., Taylor, R.L., Zhu, J.Z.: The Finite Element Method: Its Basis and Fundamentals. Butterworth-Heinemann, Stoneham (2005)

80.Zorin, D., Schröder, P., Sweldens, W.: Interpolating subdivision for meshes with arbitrary topology. In: Proc. SIGGRAPH, pp. 189–192 (1996)

Chapter 1

Introduction

Reinhard Koch, Nick Pears, and Yonghuai Liu

Abstract 3D Imaging, Analysis and Applications is a comprehensive textbook on 3D shape capture, 3D shape processing and how such capture and processing can be used. Eleven chapters cover a broad range of concepts, algorithms and applications and they are split into three parts, as follows: Part I, 3D Imaging and Shape Representation, presents techniques for capture, representation and visualization of 3D data; Part II, 3D Shape Analysis and Processing presents feature-based methods of analysis, registration and shape matching and, finally, Part III, 3D Imaging Applications presents application areas in 3D face recognition, remote sensing and medical imaging. This introduction provides the reader with historical and background information, such as that relating to the development of computer vision; in particular, the development of automated 3D imaging. It briefly discusses general depth estimation principles for 3D imaging, details a selection of seminal papers, sketches applications of 3D imaging and concludes with an outline of the book’s remaining chapters.

1.1 Introduction

Three-dimensional (3D) imaging seeks to capture the 3D structure of scenes and objects within our environment. The computed set of data points in 3D space is often accompanied by color-texture information in the form of a registered 2D image, typically obtained from standard digital image capture. Such 3D data, with or

R. Koch ( )

Institute of Computer Science, Christian-Albrechts-University of Kiel, Kiel, Germany e-mail: rk@informatik.uni-kiel.de

N. Pears

Department of Computer Science, University of York, Deramore Lane, York YO10 5GH, UK e-mail: nick.pears@york.ac.uk

Y. Liu

Department of Computer Science, Aberystwyth University, Aberystwyth, Ceredigion SY23 3DB, UK

e-mail: yyl@aber.ac.uk