Preface |
|
v | |
|
Part I Euclidean Geometry |
|
|
1 | (84) |
|
2D Computational Euclidean Geometry |
|
|
3 | (14) |
|
|
3 | (3) |
|
A Separate Type for Vectors |
|
|
6 | (3) |
|
Vector Normalization and Directions |
|
|
9 | (1) |
|
|
10 | (1) |
|
|
11 | (2) |
|
Vector Orthogonality and Linear Dependence |
|
|
13 | (4) |
|
|
17 | (10) |
|
|
17 | (1) |
|
|
18 | (3) |
|
|
21 | (1) |
|
|
22 | (1) |
|
The Geometry of the Euclidean Line E1 |
|
|
23 | (1) |
|
Immutability of Geometric Objects |
|
|
24 | (1) |
|
|
25 | (2) |
|
3D Computational Euclidean Geometry |
|
|
27 | (8) |
|
Points in Euclidean Space |
|
|
27 | (1) |
|
|
28 | (1) |
|
Vector Orthogonality and Linear Dependence |
|
|
28 | (1) |
|
|
29 | (1) |
|
|
30 | (1) |
|
Sidedness Predicates in 3D |
|
|
31 | (1) |
|
|
32 | (1) |
|
|
33 | (2) |
|
|
35 | (16) |
|
Affine Transformations in 2D |
|
|
35 | (3) |
|
Properties of Affine Transformations |
|
|
38 | (1) |
|
Composition of Affine Transformations |
|
|
39 | (1) |
|
Affine Transformation Objects |
|
|
40 | (1) |
|
|
41 | (1) |
|
|
42 | (2) |
|
Orthogonal Transformations |
|
|
44 | (2) |
|
Euler Angles and Rotation in Space |
|
|
46 | (1) |
|
|
47 | (1) |
|
Finding the Affine Mapping Given the Points |
|
|
47 | (1) |
|
|
48 | (3) |
|
|
51 | (10) |
|
|
51 | (1) |
|
Finding Line and Segment Intersections |
|
|
51 | (3) |
|
Clipping or Splitting a Segment |
|
|
54 | (3) |
|
Clipping or Splitting a Polygon |
|
|
57 | (2) |
|
|
59 | (2) |
|
Genericity in Geometric Computing |
|
|
61 | (8) |
|
A Generic Class for a Point |
|
|
61 | (1) |
|
|
62 | (2) |
|
Approach to Choosing the Number Type |
|
|
64 | (1) |
|
|
64 | (2) |
|
Repercussions from Changing the Number Type |
|
|
66 | (1) |
|
|
67 | (2) |
|
|
69 | (16) |
|
|
69 | (1) |
|
The Importance of Precision |
|
|
69 | (2) |
|
Examples of Precision Difficulties |
|
|
71 | (3) |
|
|
74 | (1) |
|
Bit-Level Reliability of Floating Point Numbers |
|
|
74 | (3) |
|
Solutions to Precision Problems |
|
|
77 | (3) |
|
Algebraic Vs. Synthetic Geometry |
|
|
80 | (1) |
|
|
81 | (1) |
|
|
81 | (4) |
|
Part II Non-Euclidean Geometries |
|
|
85 | (84) |
|
1D Computational Spherical Geometry |
|
|
87 | (6) |
|
|
87 | (1) |
|
|
88 | (1) |
|
|
88 | (1) |
|
Point-Segment Intersection |
|
|
89 | (1) |
|
Segment Intersection and Interpolation |
|
|
90 | (1) |
|
|
91 | (2) |
|
2D Computational Spherical Geometry |
|
|
93 | (8) |
|
Spherical Geometry Objects |
|
|
93 | (1) |
|
|
94 | (1) |
|
|
95 | (1) |
|
|
96 | (2) |
|
|
98 | (1) |
|
|
99 | (2) |
|
Rotations and Quaternions |
|
|
101 | (8) |
|
|
101 | (2) |
|
|
103 | (4) |
|
|
107 | (2) |
|
|
109 | (10) |
|
|
109 | (3) |
|
|
112 | (3) |
|
|
115 | (1) |
|
One-, Two-, and Three-Point Perspective |
|
|
116 | (1) |
|
|
117 | (2) |
|
Homogeneous Coordinates for Projective Geometry |
|
|
119 | (24) |
|
|
119 | (3) |
|
|
122 | (5) |
|
|
127 | (1) |
|
A Line in the Projective Space |
|
|
128 | (2) |
|
Transformations in the Projective Line |
|
|
130 | (1) |
|
Transformations in the Projective Plane |
|
|
131 | (3) |
|
Transformations in the Projective Space |
|
|
134 | (1) |
|
Canonical Projective Points |
|
|
135 | (1) |
|
|
136 | (5) |
|
|
141 | (2) |
|
|
143 | (6) |
|
Barycentric Coordinates in One Dimension |
|
|
143 | (2) |
|
Barycentric Coordinates in Two Dimensions |
|
|
145 | (1) |
|
|
146 | (3) |
|
Oriented Projective Geometry |
|
|
149 | (8) |
|
|
149 | (2) |
|
The Oriented Projective Line and Plane |
|
|
151 | (1) |
|
Oriented Projective Transformations |
|
|
152 | (3) |
|
Should One Collapse Geometric Libraries? |
|
|
155 | (1) |
|
|
155 | (1) |
|
|
156 | (1) |
|
Oriented Projective Intersections |
|
|
157 | (12) |
|
|
157 | (1) |
|
Clipping in Oriented Projective Spaces |
|
|
158 | (2) |
|
The Algebra of Intersections |
|
|
160 | (1) |
|
The Revised Graphics Pipeline |
|
|
161 | (2) |
|
Clipping or Splitting a Segment |
|
|
163 | (1) |
|
The Graphics Pipeline as a Function Object |
|
|
164 | (2) |
|
Characterizing the Four Geometries |
|
|
166 | (1) |
|
|
167 | (2) |
|
Part III Coordinate-Free Geometry |
|
|
169 | (22) |
|
Homogeneous Coordinates for Euclidean Geometry |
|
|
171 | (4) |
|
Homogeneous Coordinates for Efficiency |
|
|
171 | (1) |
|
Homogeneous Coordinates for Exactness |
|
|
172 | (1) |
|
|
172 | (1) |
|
|
172 | (1) |
|
Affine Transformation Objects |
|
|
173 | (1) |
|
Sorting Points on the Euclidean Line E1 |
|
|
174 | (1) |
|
|
174 | (1) |
|
Coordinate-Free Geometric Computing |
|
|
175 | (8) |
|
Stages of a Geometric System |
|
|
175 | (1) |
|
Dangers of the Lack of Coordinate Freedom |
|
|
176 | (1) |
|
Coordinate Freedom as Bug Deterrent |
|
|
177 | (1) |
|
Coordinate Freedom as a Force to a Cleaner Interface |
|
|
178 | (1) |
|
Coordinate Freedom in Practice |
|
|
179 | (2) |
|
|
181 | (2) |
|
|
183 | (8) |
|
|
183 | (1) |
|
|
184 | (1) |
|
Nested Typedefs for Name Commonality in CGAL |
|
|
185 | (1) |
|
Defining a New CGAL Kernel |
|
|
186 | (2) |
|
Using Pointers in a Geometric Kernel |
|
|
188 | (1) |
|
|
189 | (2) |
|
|
191 | (26) |
|
|
193 | (8) |
|
|
193 | (1) |
|
|
193 | (3) |
|
|
196 | (4) |
|
|
200 | (1) |
|
Polygon-Point Containment |
|
|
201 | (4) |
|
|
201 | (1) |
|
Convex Polygon-Point Containment |
|
|
201 | (1) |
|
Concave Polygon-Point Containment |
|
|
202 | (1) |
|
|
203 | (1) |
|
|
203 | (2) |
|
|
205 | (4) |
|
|
205 | (1) |
|
|
205 | (1) |
|
|
206 | (1) |
|
Gouraud and Phong Shading |
|
|
206 | (1) |
|
|
207 | (2) |
|
|
209 | (4) |
|
|
209 | (1) |
|
|
209 | (1) |
|
|
210 | (1) |
|
|
210 | (1) |
|
|
211 | (1) |
|
|
211 | (2) |
|
|
213 | (4) |
|
|
213 | (1) |
|
|
213 | (1) |
|
|
214 | (1) |
|
|
214 | (1) |
|
|
214 | (1) |
|
|
215 | (2) |
|
Part V Tree and Graph Drawing |
|
|
217 | (18) |
|
|
219 | (8) |
|
|
219 | (2) |
|
|
221 | (1) |
|
|
|
222 | (3) |
|
|
225 | (1) |
|
|
225 | (2) |
|
|
227 | (8) |
|
A Sparse Graph Implementation |
|
|
227 | (3) |
|
Barycentric Graph Drawing |
|
|
230 | (2) |
|
Force-Directed Graph Drawing |
|
|
232 | (1) |
|
|
232 | (3) |
|
Part VI Geometric and Solid Modeling |
|
|
235 | (50) |
|
|
237 | (8) |
|
|
237 | (1) |
|
|
238 | (2) |
|
|
240 | (2) |
|
|
242 | (1) |
|
|
242 | (1) |
|
|
243 | (2) |
|
The Halfedge Data Structure and Euler Operators |
|
|
245 | (10) |
|
|
245 | (1) |
|
|
246 | (2) |
|
|
248 | (3) |
|
Solids of Arbitrary Genus |
|
|
251 | (1) |
|
|
252 | (3) |
|
BSP Trees in Euclidean and Spherical Geometries |
|
|
255 | (10) |
|
Labeled-Leaf Binary Search Trees |
|
|
255 | (1) |
|
Operations on Segments in E1 |
|
|
256 | (2) |
|
Operations on Segments in S1 |
|
|
258 | (2) |
|
Operations on Convex Polygons in E2 |
|
|
260 | (2) |
|
|
262 | (3) |
|
Geometry-Free Geometric Computing |
|
|
265 | (12) |
|
|
265 | (1) |
|
|
266 | (2) |
|
Boolean Operations and Attribute Maintenance |
|
|
268 | (2) |
|
Subtree Construction in E2 |
|
|
270 | (1) |
|
|
270 | (1) |
|
Collecting the Convex Polytopes |
|
|
271 | (1) |
|
|
272 | (3) |
|
Developing for Multiple Geometries |
|
|
275 | (1) |
|
|
276 | (1) |
|
Constructive Solid Geometry |
|
|
277 | (8) |
|
|
277 | (1) |
|
|
277 | (2) |
|
|
279 | (1) |
|
|
279 | (1) |
|
|
280 | (1) |
|
|
280 | (2) |
|
|
282 | (3) |
|
Part VII Vector Visibility |
|
|
285 | (12) |
|
Visibility from Euclidean to Spherical Spaces |
|
|
287 | (6) |
|
Incorrectness of Sorting by Distance |
|
|
287 | (1) |
|
|
287 | (1) |
|
Data Structures for 2D Visibility |
|
|
288 | (1) |
|
|
288 | (1) |
|
Computing the Depth Order |
|
|
289 | (1) |
|
Reducing Visibility to Boolean Operations |
|
|
289 | (1) |
|
Example of Vector Visibility |
|
|
290 | (1) |
|
|
291 | (2) |
|
|
293 | (4) |
|
|
293 | (1) |
|
Constructing a DCEL Embedded on S2 |
|
|
294 | (1) |
|
|
295 | (2) |
|
|
297 | (34) |
|
A The PostScript Language |
|
|
299 | (10) |
|
|
299 | (1) |
|
A.2 Encapsulated PostScript |
|
|
300 | (1) |
|
A.3 Drawing Lines and Filling Polygonal Regions |
|
|
301 | (2) |
|
|
303 | (1) |
|
|
303 | (1) |
|
A.6 The Execution Stack and Function Definitions |
|
|
303 | (2) |
|
|
305 | (1) |
|
|
306 | (1) |
|
A.9 Writing a PostScript Class |
|
|
307 | (2) |
|
|
309 | (10) |
|
B.1 OpenGL Types and Functions |
|
|
309 | (1) |
|
|
310 | (1) |
|
|
311 | (1) |
|
|
312 | (1) |
|
|
313 | (1) |
|
|
314 | (1) |
|
B.7 The Pipeline and Transformations |
|
|
315 | (2) |
|
|
317 | (1) |
|
B.9 Encapsulating OpenGL Calls |
|
|
318 | (1) |
|
|
319 | (12) |
|
C.1 Introduction---Why GLOW? |
|
|
319 | (1) |
|
C.2 Window Creation and Drawing |
|
|
320 | (1) |
|
|
321 | (1) |
|
|
322 | (2) |
|
C.5 Modifying the Projection upon Window Resizing |
|
|
324 | (1) |
|
C.6 Widgets---Checkboxes and Buttons |
|
|
325 | (1) |
|
|
326 | (2) |
|
C.8 Displaying the Frame Rate |
|
|
328 | (1) |
|
C.9 Displaying the Frame Rate in a Widget |
|
|
329 | (1) |
|
|
329 | (2) |
Bibliography |
|
331 | (4) |
Index |
|
335 | |