level 3D data, understanding these issues is important. Finally, as sensors and applications continue to develop, the need for new representations and methods for compression and visualization mean this remains an active research area.

4.10 Further Reading

An introductory level text covering mathematics related to geometry processing is by Vince [72]. 3D representations in general are covered in some detail in the computer graphics textbooks of Watt [73] and Foley et al. [15]. A number of textbooks focus in more detail on specific representations. For example, meshes, geometry processing algorithms including error removal, mesh creation, smoothing, conversion and morphing are covered in detail in the textbook of Botsch et al. [10]. NURBS are described in detail in the textbook of Piegl and Tiller [53], subdivision surfaces are covered by Peters and Reif [50], implicit curves and surfaces are examined by Gomes et al. [19] and the textbook of Suetens [66] deals with volumetric representations in the context of medical imaging. A popular textbook describing techniques for visualization is by Post et al. [54].

4.11 Questions

1.Compare and contrast K -d point cloud structuring and octree structuring. When might one method be preferable over the other?

2.For each of the following methods and devices for 3D acquisition, explain what is the most suitable raw data representation. Justify your answer. You may need to research how each method operates.

•Time-of-flight camera.

•Multi-view stereo.

•Shape from shading.

•Structured light.

•MRI scanner (consider structural, functional and diffusion tensor modalities).

3.For a 3D imaging application of your choice, list the operations that would need to be applied to the data and use this to guide selection of an appropriate 3D representation. Explain any difficulties that may arise in converting to this representation from the raw data acquired in your chosen application.

4.What considerations are relevant when selecting a data structure for 3D meshes?

5.Describe an application in which lossy compression of 3D data is acceptable and an application in which only lossless compression is acceptable.

6.Explain three situations in which 3D data needs to be visualized. Each situation should employ a different visualization of the data.

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)