Introduction to Geometric Computing

The geometric ideas in computer science, mathematics, engineering, and physics have considerable overlap and students in each of these disciplines will eventually encounter geometric computing problems. The topic is traditionally taught in mathematics departments via geometry courses, and in computer science through computer graphics modules. This text isolates the fundamental topics affecting these disciplines and lies at the intersection of classical geometry and modern computing. The main theme of the book is the definition of coordinate-free geometric software layers for Euclidean, spherical, projective, and oriented-projective geometries. Results are derived from elementary linear algebra and many classical computer graphics problems (including the graphics pipeline) are recast in this new language. Also included is a novel treatment of classical geometric and solid modeling problems. The definition of geometric software layers promotes reuse, speeds up debugging, and prepares the ground for a thorough discussion of advanced topics. Start-up programs are provided for many programming exercises making this an invaluable book for computer science lecturers as well as software developers and researchers in the computer graphics industry. Front Matter....Pages i-xvii 2D Computational Euclidean Geometry....Pages 3-15 Geometric Predicates....Pages 17-25 3D Computational Euclidean Geometry....Pages 27-34 Affine Transformations....Pages 35-50 Affine Intersections....Pages 51-60 Genericity in Geometric Computing....Pages 61-68 Numerical Precision....Pages 69-83 1D Computational Spherical Geometry....Pages 87-92 2D Computational Spherical Geometry....Pages 93-100 Rotations and Quaternions....Pages 101-108 Projective Geometry....Pages 109-118 Homogeneous Coordinates for Projective Geometry....Pages 119-142 Barycentric Coordinates....Pages 143-147 Oriented Projective Geometry....Pages 149-156 Oriented Projective Intersections....Pages 157-168 Homogeneous Coordinates for Euclidean Geometry....Pages 171-174 Coordinate-Free Geometric Computing....Pages 175-181 Introduction to CGAL....Pages 183-190 Segment Scan Conversion....Pages 193-200 Polygon-Point Containment....Pages 201-204 Illumination and Shading....Pages 205-208 Raster-Based Visibility....Pages 209-212 Ray Tracing....Pages 213-215 Tree Drawing....Pages 219-226 Graph Drawing....Pages 227-234 Boundary Representations....Pages 237-244 The Halfedge Data Structure and Euler Operators....Pages 245-253 BSP Trees in Euclidean and Spherical Geometries....Pages 255-264 Geometry-Free Geometric Computing....Pages 265-276 Constructive Solid Geometry....Pages 277-283 Visibility from Euclidean to Spherical Spaces....Pages 287-291 Visibility in Space....Pages 293-295 Back Matter....Pages 299-340

Although geometry has been a flourishing discipline for millennia, most of it has seen either no practical applications or only esoteric ones. Computing is quickly making much of geometry intriguing not only for philosophers and mathematicians, but also for scientists and engineers. What is the core set of topics that a practitioner needs to study before embarking on the design and implementation of a geometric system in a specialized discipline? This book attempts to find the answer.

Every programmer tackling a geometric computing problem encounters design decisions that need to be solved. What may not be clear to individual programmers is that these design decisions have already been contemplated by others who have gone down some system design path only to discover (usually much later) that the design decisions that were made were lacking in some respect. This book reviews the geometric theory then applies it in an attempt to find that elusive “right” design.

Although geometry has been a flourishing discipline for millennia, most of it has seen either no practical applications or only esoteric ones. Computing is quickly making much of geometry intriguing not only for philosophers and mathematicians, but also for scientists and engineers. What is the core set of topics that a practitioner needs to study before embarking on the design and implementation of a geometric system in a specialized discipline? This book attempts to find the answer. Every programmer tackling a geometric computing problem encounters design decisions that need to be solved. What may not be clear to individual programmers is that these design decisions have already been contemplated by others who have gone down some system design path only to discover (usually much later) that the design decisions that were made were lacking in some respect. This book reviews the geometric theory then applies it in an attempt to find that elusive “right” design. "The geometric ideas in computer science, mathematics, engineering, and physics have considerable overlap and students in each of these disciplines will eventually encounter geometric computing problems. The topic is traditionally taught in mathematics departments via geometry courses, and in computer science through computer graphics modules. This text isolates the fundamental topics affecting these disciplines and lies at the intersection of classical geometry and modern computing." "Start-up programs are provided for many programming exercises making this an invaluable book for computer science lecturers as well as software developers and researchers in the computer graphics industry."--Jacket front-matter 2 fulltext01 17 fulltext02 30 fulltext03 39 fulltext04 47 fulltext05 63 fulltext06 73 fulltext07 81 fulltext08 96 fulltext09 102 fulltext10 110 fulltext11 118 fulltext12 128 fulltext13 152 fulltext14 157 fulltext15 165 fulltext16 177 fulltext17 181 fulltext18 188 fulltext19 196 fulltext20 204 fulltext21 208 fulltext22 212 fulltext23 216 fulltext24 219 fulltext25 227 fulltext26 235 fulltext27 243 fulltext28 252 fulltext29 262 fulltext30 274 fulltext31 281 fulltext32 286 fulltext33 289 Provides information on the mathematics and engineering that comprise computer graphics and computational geometry.