Rimon Elias Digital Media A Problem-solving Approach for Computer Graphics Digital Media Rimon Elias Digital Media A Problem-solving Approach for Computer Graphics 123 RimonElias GermanUniversity inCairo Cairo Egypt ISBN 978-3-319-05136-9 ISBN 978-3-319-05137-6 (eBook) DOI 10.1007/978-3-319-05137-6 Springer ChamHeidelberg New YorkDordrecht London LibraryofCongressControlNumber:2014933528 (cid:2)SpringerInternationalPublishingSwitzerland2014 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionor informationstorageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilar methodology now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection with reviews or scholarly analysis or material supplied specifically for the purposeofbeingenteredandexecutedonacomputersystem,forexclusiveusebythepurchaserofthe work. Duplication of this publication or parts thereof is permitted only under the provisions of theCopyright Law of the Publisher’s location, in its current version, and permission for use must always be obtained from Springer. Permissions for use may be obtained through RightsLink at the CopyrightClearanceCenter.ViolationsareliabletoprosecutionundertherespectiveCopyrightLaw. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexempt fromtherelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. While the advice and information in this book are believed to be true and accurate at the date of publication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityfor anyerrorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,with respecttothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) To my family; my parents, my wife, and my daughters; Teodora and Eugenia Preface In the digital era, various media have received great attention in retrieving, dis- playing, manipulating, and communicating information. We may look at such digitalmediafromtwodistinctperspectives,scientificandartistic.Duetothegreat importanceofdigitalmedia,differentuniversity-levelprogramshavebeencreated toservesuchareasofemergingscienceandarts.Someoftheseprogramsstudythe engineering and scientific aspects of digital media, e.g., video processing, audio processing, computer-generated imagery, etc. Other programs are concerned with theartisticcreationsbuiltupontheadvancesinthisarea,e.g.,digitalphotography, video production, audio production, etc. Visual computingrepresents a section ofthe engineering and scientific aspects of digital media, where digital images become the core around which different fields of computer research are established. Such fields include computer vision, imageprocessing,computergraphics,andvisualization.Althoughdigitalimaging can be considered the greatest common divisor among those fields, essential dif- ferences are present among them. For instance, while computer graphics is the fieldconcernedwithrepresentingdescriptivedatathroughartificialdigitalimaging form,computervisionisthefieldconcernedwithextractingdescriptivedatafrom real-world digital images. Another closely related and important research field is image processing that is concerned with manipulation of digital images. Algo- rithms developed in this field may be used as preprocessing steps to enhance the outcome of a vision system. All the fields are connected to some extent. This book is concerned with the graphics part of visual computing. It handles the subject through explaining algorithms and concepts and providing plenty of solved problems. Our aim is that students understand and practice numeric problems. The target readers of this book are upper-division undergraduate stu- dents and other graduate students who did not take a computer graphics course before. The reader is expected to have a basic knowledge of mathematics and linear algebra (An appendix is provided at the end of the book). Since we talk about concepts and solving problems, no programming experience is needed to read the book. Cairo, Egypt, December 2013 Rimon Elias Ottawa, Canada vii Contents 1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Digital Media Engineering. . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Visual Computing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Computer Graphics. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3.1 Graphics Pipeline. . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 Book Contents. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4.1 Notations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 2D Graphics. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1 Lines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.1 Digital Differential Analyzer Algorithm . . . . . . . . . . 10 2.1.2 Bresenham’s Algorithm. . . . . . . . . . . . . . . . . . . . . . 13 2.1.3 The Midpoint Algorithm. . . . . . . . . . . . . . . . . . . . . 17 2.2 Circles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.1 Two-Way Symmetry Algorithm. . . . . . . . . . . . . . . . 22 2.2.2 Four-Way Symmetry Algorithm. . . . . . . . . . . . . . . . 24 2.2.3 Eight-Way Symmetry Algorithm . . . . . . . . . . . . . . . 26 2.2.4 The Midpoint Algorithm. . . . . . . . . . . . . . . . . . . . . 28 2.3 Polygons. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.3.1 Convexity Versus Concavity . . . . . . . . . . . . . . . . . . 32 2.4 Line Clipping. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.4.1 Cohen-Sutherland Algorithm . . . . . . . . . . . . . . . . . . 42 2.5 Polygon Clipping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.5.1 Weiler-Atherton Algorithm . . . . . . . . . . . . . . . . . . . 53 2.6 Problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3 Transformations in 2D Space . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.1 Translation in 2D Space . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.2 Rotation in 2D Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.2.1 General Rotation in 2D Space . . . . . . . . . . . . . . . . . 69 3.3 Scaling in 2D Space. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 3.3.1 General Scaling in 2D Space. . . . . . . . . . . . . . . . . . 75 ix x Contents 3.4 Reflection in 2D Space. . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 3.4.1 Reflection About the x-Axis . . . . . . . . . . . . . . . . . . 78 3.4.2 Reflection About the y-Axis . . . . . . . . . . . . . . . . . . 79 3.4.3 General Reflection in 2D Space. . . . . . . . . . . . . . . . 79 3.5 Shearing in 2D Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 3.5.1 Shearing Along the x-Axis. . . . . . . . . . . . . . . . . . . . 87 3.5.2 Shearing Along the y-Axis. . . . . . . . . . . . . . . . . . . . 88 3.5.3 General Shearing in 2D Space. . . . . . . . . . . . . . . . . 89 3.6 Composite Transformations. . . . . . . . . . . . . . . . . . . . . . . . . 92 3.7 Same-Type Transformations. . . . . . . . . . . . . . . . . . . . . . . . . 98 3.8 Inverse Matrices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 3.9 Axes Transformations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 3.9.1 Axes Translation . . . . . . . . . . . . . . . . . . . . . . . . . . 101 3.9.2 Axes Rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 3.9.3 Axes Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 3.9.4 Axes Reflection . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 3.10 Problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 4 3D Solid Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 4.1 Wireframes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 4.1.1 Wireframe Pros and Cons . . . . . . . . . . . . . . . . . . . . 115 4.2 Boundary Representations . . . . . . . . . . . . . . . . . . . . . . . . . . 116 4.2.1 Baumgart’s Winged-Edge Data Structure . . . . . . . . . 116 4.3 Constructive Solid Geometry. . . . . . . . . . . . . . . . . . . . . . . . 118 4.3.1 Boolean Operations. . . . . . . . . . . . . . . . . . . . . . . . . 118 4.3.2 CSG Expressions and Trees. . . . . . . . . . . . . . . . . . . 120 4.3.3 Regularized Boolean Operations. . . . . . . . . . . . . . . . 123 4.4 Spatial Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 4.4.1 Cell Decomposition . . . . . . . . . . . . . . . . . . . . . . . . 125 4.4.2 Spatial Enumeration . . . . . . . . . . . . . . . . . . . . . . . . 125 4.4.3 Quadtrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 4.4.4 Octrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 4.4.5 Bintrees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 4.4.6 Binary Space-Partitioning Trees. . . . . . . . . . . . . . . . 131 4.5 Sweep Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 4.5.1 Translational Sweeps . . . . . . . . . . . . . . . . . . . . . . . 134 4.5.2 Rotational Sweeps . . . . . . . . . . . . . . . . . . . . . . . . . 135 4.6 Polygonal Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 4.7 Problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 Contents xi 5 Transformations in 3D Space . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 5.1 Translation in 3D Space . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 5.2 Rotation in 3D Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 5.2.1 Rotation About the x-Axis. . . . . . . . . . . . . . . . . . . . 145 5.2.2 Rotation About the y-Axis. . . . . . . . . . . . . . . . . . . . 147 5.2.3 Rotation About the z-Axis. . . . . . . . . . . . . . . . . . . . 148 5.2.4 Properties of the Rotation Matrix. . . . . . . . . . . . . . . 149 5.2.5 General Rotation in 3D Space . . . . . . . . . . . . . . . . . 150 5.3 Scaling in 3D Space. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 5.3.1 General Scaling in 3D Space. . . . . . . . . . . . . . . . . . 170 5.4 Reflection in 3D Space. . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 5.4.1 Reflection About the xy-Plane . . . . . . . . . . . . . . . . . 172 5.4.2 Reflection About the yz-Plane . . . . . . . . . . . . . . . . . 173 5.4.3 Reflection About the zx-Plane . . . . . . . . . . . . . . . . . 174 5.4.4 General Reflection in 3D Space. . . . . . . . . . . . . . . . 175 5.5 Shearing in 3D Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 5.5.1 Shearing Relative to the x-Axis . . . . . . . . . . . . . . . . 180 5.5.2 Shearing Relative to the y-Axis . . . . . . . . . . . . . . . . 181 5.5.3 Shearing Relative to the z-Axis . . . . . . . . . . . . . . . . 182 5.5.4 General Shearing in 3D Space. . . . . . . . . . . . . . . . . 182 5.6 Composite 3D Transformations . . . . . . . . . . . . . . . . . . . . . . 185 5.7 Axes Transformations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 5.7.1 Axes Translation . . . . . . . . . . . . . . . . . . . . . . . . . . 187 5.7.2 Axes Rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 5.7.3 Axes Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 5.7.4 Axes Reflection . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 5.8 Problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 6 Curves. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 6.1 Curve Representations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 6.1.1 Explicit Representation. . . . . . . . . . . . . . . . . . . . . . 200 6.1.2 Implicit Representation. . . . . . . . . . . . . . . . . . . . . . 205 6.1.3 Parametric Representation. . . . . . . . . . . . . . . . . . . . 206 6.2 Approximating Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 6.2.1 Bézier Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 6.2.2 B-Spline Curves. . . . . . . . . . . . . . . . . . . . . . . . . . . 236 6.2.3 NURBS Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 6.3 Problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 7 Surfaces. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 7.1 Surface Representations. . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 7.2 Bézier Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 xii Contents 7.2.1 Linear Bézier Surfaces . . . . . . . . . . . . . . . . . . . . . . 297 7.2.2 Biquadratic Bézier Surfaces. . . . . . . . . . . . . . . . . . . 298 7.2.3 Bicubic Bézier Surfaces . . . . . . . . . . . . . . . . . . . . . 302 7.3 NURBS Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 7.3.1 Biquadratic NURBS Surfaces. . . . . . . . . . . . . . . . . . 305 7.3.2 Bicubic NURBS Surfaces . . . . . . . . . . . . . . . . . . . . 310 7.4 Problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 8 Projections. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 8.1 Projection Types. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 8.2 Planar Projections. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 8.3 Parallel Projections. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 8.3.1 Orthographic Projections. . . . . . . . . . . . . . . . . . . . . 321 8.3.2 Oblique Projections. . . . . . . . . . . . . . . . . . . . . . . . . 339 8.4 Perspective Projections . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 8.4.1 One-Point Perspective Projection . . . . . . . . . . . . . . . 347 8.4.2 Two-point Perspective Projection. . . . . . . . . . . . . . . 360 8.4.3 Three-Point Perspective Projection. . . . . . . . . . . . . . 368 8.5 Parallel/Perspective Comparison. . . . . . . . . . . . . . . . . . . . . . 379 8.6 Problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383 Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386 9 View Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387 9.1 View Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387 9.1.1 View Reference Coordinate System . . . . . . . . . . . . . 389 9.1.2 Coordinates Transformation. . . . . . . . . . . . . . . . . . . 391 9.2 View Volume. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399 9.2.1 Infinite View Volume. . . . . . . . . . . . . . . . . . . . . . . 400 9.2.2 Finite View Volume. . . . . . . . . . . . . . . . . . . . . . . . 409 9.3 Canonical View Volume. . . . . . . . . . . . . . . . . . . . . . . . . . . 413 9.4 Transformation to Canonical View Volume. . . . . . . . . . . . . . 416 9.4.1 Parallel Projection . . . . . . . . . . . . . . . . . . . . . . . . . 417 9.4.2 Perspective Projection. . . . . . . . . . . . . . . . . . . . . . . 431 9.5 3D Line Clipping. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439 9.5.1 Clipping Against Canonical View Volume . . . . . . . . 442 9.6 Projection of View Volume Contents . . . . . . . . . . . . . . . . . . 445 9.7 Perspective Normalization. . . . . . . . . . . . . . . . . . . . . . . . . . 446 9.8 Clipping in Homogeneous Coordinates . . . . . . . . . . . . . . . . . 452 9.9 Transforming into Device Coordinates . . . . . . . . . . . . . . . . . 452 9.10 Wrapping it up. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454 9.11 Problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459