Introduction to geometric computing

Sherif Ghali Ph.D. (auth.)1848001142, 9781848001145

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.

Table of contents :
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