Schneider / Eberly Geometric Tools for Computer Graphics

1. Auflage 2002
ISBN: 978-0-08-047802-9
Verlag: Elsevier Science & Techn.
Format: EPUB
Kopierschutz: 6 - ePub Watermark

E-Book, Englisch, 1056 Seiten

Do you spend too much time creating the building blocks of your graphics applications or finding and correcting errors? Geometric Tools for Computer Graphics is an extensive, conveniently organized collection of proven solutions to fundamental problems that you'd rather not solve over and over again, including building primitives, distance calculation, approximation, containment, decomposition, intersection determination, separation, and more.

If you have a mathematics degree, this book will save you time and trouble. If you don't, it will help you achieve things you may feel are out of your reach. Inside, each problem is clearly stated and diagrammed, and the fully detailed solutions are presented in easy-to-understand pseudocode. You also get the mathematics and geometry background needed to make optimal use of the solutions, as well as an abundance of reference material contained in a series of appendices.

Features
Filled with robust, thoroughly tested solutions that will save you time and help you avoid costly errors.
Covers problems relevant for both 2D and 3D graphics programming.
Presents each problem and solution in stand-alone form allowing you the option of reading only those entries that matter to you.
Provides the math and geometry background you need to understand the solutions and put them to work.
Clearly diagrams each problem and presents solutions in easy-to-understand pseudocode.
Resources associated with the book are available at the companion Web site www.mkp.com/gtcg.* Filled with robust, thoroughly tested solutions that will save you time and help you avoid costly errors.
* Covers problems relevant for both 2D and 3D graphics programming.
* Presents each problem and solution in stand-alone form allowing you the option of reading only those entries that matter to you.
* Provides the math and geometry background you need to understand the solutions and put them to work.
* Clearly diagrams each problem and presents solutions in easy-to-understand pseudocode.
* Resources associated with the book are available at the companion Web site www.mkp.com/gtcg.

24 years of professional programming, primarily focused on modeling tools and geometric algorithms. Employers include Digital Equipment Corporation, Apple, Walt Disney Feature Animation, Digital Domain, and Industrial Light + Magic. Formed and lead groups specializing in these areas as well as in physics simulation.Film Credits: Oil & Vinegar, 102 Dalmatians, Disney's Magic Lamp, Mickey's Philharmagic, Reign of Fire, Kangaroo Jack, Chicken Little, Indiana Jones and the Kingdom of the Crystal Skull, Pirates of the Caribbean: Dead Man's Chest, Harry Potter and the Goblet of Fire.ACM Siggraph, IEEE.M.S. in Computer Science, University of Washington.

Autoren/Hrsg.

Schneider, Philip

Eberly, David H.

Inhaltsverzeichnis

1;1 Introduction;45
1.1;How to Use This Book;45
1.2;Issues of Numerical Computation;46
1.2.1;Low-Level Issues;46
1.2.2;High-Level Issues;48
1.3;A Summary of the Chapters;50
2;2 Matrices and Linear Systems;53
2.1;Introduction;53
2.1.1;Motivation;53
2.1.2;Organization;57
2.1.3;Notational Conventions;58
2.2;Tuples;58
2.2.1;Definition;59
2.2.2;Arithmetic Operations;60
2.3;Matrices;60
2.3.1;Notation and Terminology;61
2.3.2;Transposition;61
2.3.3;Arithmetic Operations;62
2.3.4;Matrix Multiplication;64
2.4;Linear Systems;68
2.4.1;Linear Equations;68
2.4.2;Linear Systems in Two Unknowns;70
2.4.3;General Linear Systems;73
2.4.4;Row Reductions, Echelon Form, and Rank;74
2.5;Square Matrices;76
2.5.1;Diagonal Matrices;76
2.5.2;Triangular Matrices;78
2.5.3;The Determinant;78
2.5.4;Inverse;82
2.6;Linear Spaces;85
2.6.1;Fields;85
2.6.2;Definition and Properties;86
2.6.3;Subspaces;87
2.6.4;Linear Combinations and Span;87
2.6.5;Linear Independence, Dimension, and Basis;88
2.7;Linear Mappings;89
2.7.1;Mappings in General;89
2.7.2;Linear Mappings;91
2.7.3;Matrix Representation of Linear Mappings;93
2.7.4;Cramer's Rule;94
2.8;Eigenvalues and Eigenvectors;96
2.9;Euclidean Space;98
2.9.1;Inner Product Spaces;98
2.9.2;Orthogonality and Orthonormal Sets;99
2.10;Least Squares;100
2.11;Recommended Reading;104
3;3 Vector Algebra;107
3.1;Vector Basics;107
3.1.1;Vector Equivalence;107
3.1.2;Vector Addition;108
3.1.3;Vector Subtraction;109
3.1.4;Vector Scaling;109
3.1.5;Properties of Vector Addition and Scalar Multiplication;110
3.2;Vector Space;113
3.2.1;Span;114
3.2.2;Linear Independence;115
3.2.3;Basis, Subspaces, and Dimension;115
3.2.4;Orientation;117
3.2.5;Change of Basis;119
3.2.6;Linear Transformations;120
3.3;Affine Spaces;124
3.3.1;Euclidean Geometry;128
3.3.2;Volume, the Determinant, and the Scalar Triple Product;138
3.3.3;Frames;140
3.4;Affine Transformations;142
3.4.1;Types of Affine Maps;147
3.4.2;Composition of Affine Maps;147
3.5;Barycentric Coordinates and Simplexes;148
3.5.1;Barycentric Coordinates and Subspaces;150
3.5.2;Affine Independence;150
4;4 Matrices, Vector Algebra, and Transformations;153
4.1;Introduction;153
4.2;Matrix Representation of Points and Vectors;154
4.3;Addition, Subtraction, and Multiplication;157
4.3.1;Vector Addition and Subtraction;157
4.3.2;Point and Vector Addition and Subtraction;158
4.3.3;Subtraction of Points;159
4.3.4;Scalar Multiplication;159
4.4;Products of Vectors;159
4.4.1;Dot Product;160
4.4.2;Cross Product;161
4.4.3;Tensor Product;164
4.4.4;The 'Perp' Operator and the ÏPerpÓ Dot Product;165
4.5;Matrix Representation of Affine Transformations;170
4.6;Change-of-Basis/Frame/Coordinate System;172
4.7;Vector Geometry of Affine Transformations;176
4.7.1;Notation;177
4.7.2;Translation;178
4.7.3;Rotation;180
4.7.4;Scaling;186
4.7.5;Reflection;192
4.7.6;Shearing;197
4.8;Projections;202
4.8.1;Orthographic;203
4.8.2;Oblique;204
4.8.3;Perspective;207
4.9;Transforming Normal Vectors;209
4.10;Recommended Reading;212
5;5 Geometric Primitives in 2D;215
5.1;Linear Components;215
5.1.1;Implicit Form;216
5.1.2;Parametric Form;217
5.1.3;Converting between Representations;218
5.2;Triangles;219
5.3;Rectangles;221
5.4;Polylines and Polygons;221
5.5;Quadratic Curves;225
5.5.1;Circles;227
5.5.2;Ellipses;227
5.6;Polynomial Curves;229
5.6.1;Bezier Curves;230
5.6.2;B-Spline Curves;230
5.6.3;NURBS Curves;232
6;6 Distance in 2D;233
6.1;Point to Linear Component;234
6.1.1;Point to Line;234
6.1.2;Point to Ray;235
6.1.3;Point to Segment;236
6.2;Point to Polyline;238
6.3;Point to Polygon;240
6.3.1;Point to Triangle;240
6.3.2;Point to Rectangle;255
6.3.3;Point to Orthogonal Frustum;257
6.3.4;Point to Convex Polygon;260
6.4;Point to Quadratic Curve;261
6.5;Point to Polynomial Curve;263
6.6;Linear Components;265
6.6.1;Line to Line;265
6.6.2;Line to Ray;266
6.6.3;Line to Segment;267
6.6.4;Ray to Ray;268
6.6.5;Ray to Segment;270
6.6.6;Segment to Segment;272
6.7;Linear Component to Polyline or Polygon;273
6.8;Linear Component to Quadratic Curve;275
6.9;Linear Component to Polynomial Curve;277
6.10;GJK Algorithm;277
6.10.1;Set Operations;278
6.10.2;Overview of the Algorithm;279
6.10.3;Alternatives to GJK;282
7;7 Intersection in 2D;285
7.1;Linear Components;285
7.2;Linear Components and Polylines;290
7.3;Linear Components and Quadratic Curves;290
7.3.1;Linear Components and General Quadratic Curves;291
7.3.2;Linear Components and Circular Components;291
7.4;Linear Components and Polynomial Curves;292
7.4.1;Algebraic Method;292
7.4.2;Polyline Approximation;294
7.4.3;Hierarchical Bounding;295
7.4.4;Monotone Decomposition;296
7.4.5;Rasterization;297
7.5;Quadratic Curves;299
7.5.1;General Quadratic Curves;299
7.5.2;Circular Components;301
7.5.3;Ellipses;302
7.6;Polynomial Curves;306
7.6.1;Algebraic Method;306
7.6.2;Polyline Approximation;306
7.6.3;Hierarchical Bounding;307
7.6.4;Rasterization;307
7.7;The Method of Separating Axes;309
7.7.1;Separation by Projection onto a Line;309
7.7.2;Separation of Stationary Convex Polygons;310
7.7.3;Separation of Moving Convex Polygons;317
7.7.4;Intersection Set for Stationary Convex Polygons;320
7.7.5;Contact Set for Moving Convex Polygons;321
8;8 Miscellaneous 2D Problems;329
8.1;Circle through Three Points;329
8.2;Circle Tangent to Three Lines;329
8.3;Line Tangent to a Circle at a Given Point;331
8.4;Line Tangent to a Circle through a Given Point;332
8.5;Lines Tangent to Two Circles;335
8.6;Circle through Two Points with a Given Radius;341
8.7;Circle through a Point and Tangent to a Line with a Given Radius;342
8.8;Circles Tangent to Two Lines with a Given Radius;346
8.9;Circles through a Point and Tangent to a Circle with a Given Radius;349
8.10;Circles Tangent to a Line and a Circle with a Given Radius;353
8.11;Circles Tangent to Two Circles with a Given Radius;358
8.12;Line Perpendicular to a Given Line through a Given Point;360
8.13;Line between and Equidistant to Two Points;361
8.14;Line Parallel to a Given Line at a Given Distance;362
8.15;Line Parallel to a Given Line at a Given Vertical ( Horizontal) Distance;364
8.16;Lines Tangent to a Given Circle and Normal to a Given Line;366
9;9 Geometric Primitives in 3D;369
9.1;Linear Components;369
9.2;Planar Components;370
9.2.1;Planes;370
9.2.2;Coordinate System Relative to a Plane;374
9.2.3;2D Objects in a Plane;375
9.3;Polymeshes, Polyhedra, and Polytopes;377
9.3.1;Vertex-Edge-Face Tables;381
9.3.2;Connected Meshes;384
9.3.3;Manifold Meshes;386
9.3.4;Closed Meshes;386
9.3.5;Consistent Ordering;387
9.3.6;Platonic Solids;390
9.4;Quadric Surfaces;395
9.4.1;Three Nonzero Eigenvalues;395
9.4.2;Two Nonzero Eigenvalues;396
9.4.3;One Nonzero Eigenvalue;396
9.5;Torus;399
9.6;Polynomial Curves;400
9.6.1;Bezier Curves;401
9.6.2;B-Spline Curves;401
9.6.3;NURBS Curves;402
9.7;Polynomial Surfaces;403
9.7.1;Bezier Surfaces;404
9.7.2;B-Spline Surfaces;406
9.7.3;NURBS Surfaces;408
10;10 Distance in 3D;409
10.1;Introduction;409
10.2;Point to Linear Component;409
10.2.1;Point to Ray or Line Segment;411
10.2.2;Point to Polyline;413
10.3;Point to Planar Component;418
10.3.1;Point to Plane;418
10.3.2;Point to Triangle;420
10.3.3;Point to Rectangle;426
10.3.4;Point to Polygon;429
10.3.5;Point to Circle or Disk;432
10.4;Point to Polyhedron;435
10.4.1;General Problem;435
10.4.2;Point to Oriented Bounding Box;438
10.4.3;Point to Orthogonal Frustum;441
10.5;Point to Quadric Surface;445
10.5.1;Point to General Quadric Surface;445
10.5.2;Point to Ellipsoid;447
10.6;Point to Polynomial Curve;449
10.7;Point to Polynomial Surface;451
10.8;Linear Components;453
10.8.1;Lines and Lines;453
10.8.2;Segment/Segment, Line/Ray, Line/Segment, Ray/ Ray, Ray/ Segment;456
10.8.3;Segment to Segment, Alternative Approach;470
10.9;Linear Component to Triangle, Rectangle, Tetrahedron, Oriented Box;477
10.9.1;Linear Component to Triangle;477
10.9.2;Linear Component to Rectangle;485
10.9.3;Linear Component to Tetrahedron;491
10.9.4;Linear Component to Oriented Bounding Box;494
10.10;Line to Quadric Surface;509
10.11;Line to Polynomial Surface;511
10.12;GJK Algorithm;512
10.13;Miscellaneous;513
10.13.1;Distance between Line and Planar Curve;513
10.13.2;Distance between Line and Planar Solid Object;515
10.13.3;Distance between Planar Curves;516
10.13.4;Geodesic Distance on Surfaces;521
11;11 Intersection in 3D;525
11.1;Linear Components and Planar Components;525
11.1.1;Linear Components and Planes;526
11.1.2;Linear Components and Triangles;529
11.1.3;Linear Components and Polygons;532
11.1.4;Linear Component and Disk;535
11.2;Linear Components and Polyhedra;537
11.3;Linear Components and Quadric Surfaces;542
11.3.1;General Quadric Surfaces;543
11.3.2;Linear Components and a Sphere;545
11.3.3;Linear Components and an Ellipsoid;548
11.3.4;Linear Components and Cylinders;551
11.3.5;Linear Components and a Cone;556
11.4;Linear Components and Polynomial Surfaces;563
11.4.1;Algebraic Surfaces;564
11.4.2;Free-Form Surfaces;565
11.5;Planar Components;573
11.5.1;Two Planes;573
11.5.2;Three Planes;576
11.5.3;Triangle and Plane;578
11.5.4;Triangle and Triangle;583
11.6;Planar Components and Polyhedra;587
11.6.1;Trimeshes;587
11.6.2;General Polyhedra;588
11.7;Planar Components and Quadric Surfaces;591
11.7.1;Plane and General Quadric Surface;591
11.7.2;Plane and Sphere;592
11.7.3;Plane and Cylinder;595
11.7.4;Plane and Cone;607
11.7.5;Triangle and Cone;627
11.8;Planar Components and Polynomial Surfaces;631
11.8.1;Hermite Curves;633
11.8.2;Geometry Definitions;634
11.8.3;Computing the Curves;635
11.8.4;The Algorithm;636
11.8.5;Implementation Notes;639
11.9;Quadric Surfaces;639
11.9.1;General Intersection;640
11.9.2;Ellipsoids;648
11.10;Polynomial Surfaces;652
11.10.1;Subdivision Methods;652
11.10.2;Lattice Evaluation;653
11.10.3;Analytic Methods;654
11.10.4;Marching Methods;654
11.11;The Method of Separating Axes;655
11.11.1;Separation of Stationary Convex Polyhedra;655
11.11.2;Separation of Moving Convex Polyhedra;659
11.11.3;Intersection Set for Stationary Convex Polyhedra;660
11.11.4;Contact Set for Moving Convex Polyhedra;660
11.12;Miscellaneous;668
11.12.1;Oriented Bounding Box and Orthogonal Frustum;668
11.12.2;Linear Component and Axis-Aligned Bounding Box;670
11.12.3;Linear Component and Oriented Bounding Box;674
11.12.4;Plane and Axis-Aligned Bounding Box;678
11.12.5;Plane and Oriented Bounding Box;679
11.12.6;Axis-Aligned Bounding Boxes;681
11.12.7;Oriented Bounding Boxes;683
11.12.8;Sphere and Axis-Aligned Bounding Box;688
11.12.9;Cylinders;690
11.12.10;Linear Component and Torus;703
12;12 Miscellaneous 3D Problems;707
12.1;Projection of a Point onto a Plane;707
12.2;Projection of a Vector onto a Plane;709
12.3;Angle between a Line and a Plane;710
12.4;Angle between Two Planes;711
12.5;Plane Normal to a Line and through a Given Point;711
12.6;Plane through Three Points;713
12.7;Angle between Two Lines;714
13;13 Computational Geometry Topics;717
13.1;Binary Space-Partitioning Trees in 2D;717
13.1.1;BSP Tree Representation of a Polygon;718
13.1.2;Minimum Splits versus Balanced Trees;724
13.1.3;Point in Polygon Using BSP Trees;727
13.1.4;Partitioning a Line Segment by a BSP Tree;728
13.2;Binary Space-Partitioning Trees in 3D;731
13.2.1;BSP Tree Representation of a Polyhedron;732
13.2.2;Minimum Splits versus Balanced Trees;734
13.2.3;Point in Polyhedron Using BSP Trees;735
13.2.4;Partitioning a Line Segment by a BSP Tree;736
13.2.5;Partitioning a Convex Polygon by a BSP Tree;738
13.3;Point in Polygon;739
13.3.1;Point in Triangle;739
13.3.2;Point in Convex Polygon;741
13.3.3;Point in General Polygon;744
13.3.4;Faster Point in General Polygon;750
13.3.5;A Grid Method;751
13.4;Point in Polyhedron;752
13.4.1;Point in Tetrahedron;752
13.4.2;Point in Convex Polyhedron;753
13.4.3;Point in General Polyhedron;755
13.5;Boolean Operations on Polygons;758
13.5.1;The Abstract Operations;759
13.5.2;The Two Primitive Operations;761
13.5.3;Boolean Operations Using BSP Trees;763
13.5.4;Other Algorithms;768
13.6;Boolean Operations on Polyhedra;770
13.6.1;Abstract Operations;770
13.6.2;Boolean Operations Using BSP Trees;771
13.7;Convex Hulls;773
13.7.1;Convex Hulls in 2D;773
13.7.2;Convex Hulls in 3D;788
13.7.3;Convex Hulls in Higher Dimensions;794
13.8;Delaunay Triangulation;800
13.8.1;Incremental Construction in 2D;801
13.8.2;Incremental Construction in General Dimensions;805
13.8.3;Construction by Convex Hull;810
13.9;Polygon Partitioning;811
13.9.1;Visibility Graph of a Simple Polygon;811
13.9.2;Triangulation;815
13.9.3;Triangulation by Horizontal Decomposition;819
13.9.4;Convex Partitioning;833
13.10;Circumscribed and Inscribed Balls;842
13.10.1;Circumscribed Ball;843
13.10.2;Inscribed Ball;845
13.11;Minimum Bounds for Point Sets;847
13.11.1;Minimum-Area Rectangle;847
13.11.2;Minimum-Volume Box;850
13.11.3;Minimum-Area Circle;851
13.11.4;Minimum-Volume Sphere;855
13.11.5;Miscellaneous;857
13.12;Area and Volume Measurements;860
13.12.1;Area of a 2D Polygon;860
13.12.2;Area of a 3D Polygon;864
13.12.3;Volume of a Polyhedron;868
14;Appendix A Numerical Methods;871
14.1;Solving Linear Systems;871
14.1.1;A.1.1 Special Case: Solving a Triangular System;872
14.1.2;A.1.2 Gaussian Elimination;873
14.2;Systems of Polynomials;876
14.2.1;A.2.1 Linear Equations in One Formal Variable;877
14.2.2;A.2.2 Any-Degree Equations in One Formal Variable;879
14.2.3;A.2.3 Any-Degree Equations in Any Formal Variables;881
14.3;Matrix Decompositions;891
14.3.1;A.3.1 Euler Angle Factorization;891
14.3.2;A.3.2 QR Decomposition;896
14.3.3;A.3.3 Eigendecomposition;897
14.3.4;A.3.4 Polar Decomposition;898
14.3.5;A.3.5 Singular Value Decomposition;901
14.4;Representations of 3D Rotations;901
14.4.1;A.4.1 Matrix Representation;901
14.4.2;A.4.2 Axis-Angle Representation;902
14.4.3;A.4.3 Quaternion Representation;904
14.4.4;A.4.4 Performance Issues;905
14.5;Root Finding;913
14.5.1;A.5.1 Methods in One Dimension;913
14.5.2;A.5.2 Methods in Many Dimensions;918
14.5.3;A.5.3 Stable Solution to Quadratic Equations;919
14.6;Minimization;920
14.6.1;A.6.1 Methods in One Dimension;920
14.6.2;A.6.2 Methods in Many Dimensions;921
14.6.3;A.6.3 Minimizing a Quadratic Form;924
14.6.4;A.6.4 Minimizing a Restricted Quadratic Form;924
14.7;Least Squares Fitting;926
14.7.1;A.7.1 Linear Fitting of Points;926
14.7.2;A.7.2 Linear Fitting of Points Using Orthogonal Regression;926
14.7.3;A.7.3 Planar Fitting of Points;928
14.7.4;A.7.4 Hyperplanar Fitting of Points Using Orthogonal Regression;928
14.7.5;A.7.5 Fitting a Circle to 2D Points;930
14.7.6;A.7.6 Fitting a Sphere to 3D Points;931
14.7.7;A.7.7 Fitting a Quadratic Curve to 2D Points;932
14.7.8;A.7.8 Fitting a Quadric Surface to 3D Points;933
14.8;Subdivision of Curves;933
14.8.1;A.8.1 Subdivision by Uniform Sampling;933
14.8.2;A.8.2 Subdivision by Arc Length;934
14.8.3;A.8.3 Subdivision by Midpoint Distance;935
14.8.4;A.8.4 Subdivision by Variation;936
14.9;Topics from Calculus;938
14.9.1;A.9.1 Level Sets;938
14.9.2;A.9.2 Minima and Maxima of Functions;942
14.9.3;A.9.3 Lagrange Multipliers;954
15;Appendix B Trigonometry;967
15.1;Introduction;967
15.1.1;B.1.1 Terminology;967
15.1.2;B.1.2 Angles;967
15.1.3;B.1.3 Conversion Examples;969
15.2;Trigonometric Functions;970
15.2.1;B.2.1 Definitions in Terms of Exponentials;974
15.2.2;B.2.2 Domains and Ranges;975
15.2.3;B.2.3 Graphs of Trigonometric Functions;975
15.2.4;B.2.4 Derivatives of Trigonometric Functions;975
15.2.5;B.2.5 Integration;978
15.3;Trigonometric Identities and Laws;978
15.3.1;B.3.1 Periodicity;979
15.3.2;B.3.2 Laws;980
15.3.3;B.3.3 Formulas;984
15.4;Inverse Trigonometric Functions;989
15.4.1;B.4.1 Defining arcsin and arccos in Terms of arctan;989
15.4.2;B.4.2 Domains and Ranges;989
15.4.3;B.4.3 Graphs;990
15.4.4;B.4.4 Derivatives;990
15.4.5;B.4.5 Integration;992
15.5;Further Reading;992
16;Appendix C Basic Formulas for Geometric Primitives;993
16.1;Introduction;993
16.2;Triangles;993
16.2.1;C.2.1 Symbols;993
16.2.2;C.2.2 Definitions;994
16.2.3;C.2.3 Right Triangles;996
16.2.4;C.2.4 Equilateral Triangle;997
16.2.5;C.2.5 General Triangle;997
16.3;Quadrilaterals;998
16.3.1;C.3.1 Square;998
16.3.2;C.3.2 Rectangle;998
16.3.3;C.3.3 Parallelogram;998
16.3.4;C.3.4 Rhombus;999
16.3.5;C.3.5 Trapezoid;999
16.3.6;C.3.6 General Quadrilateral;999
16.4;Circles;1000
16.4.1;C.4.1 Symbols;1000
16.4.2;C.4.2 Full Circle;1000
16.4.3;C.4.3 Sector of a Circle;1000
16.4.4;C.4.4 Segment of a Circle;1001
16.5;Polyhedra;1001
16.5.1;C.5.1 Symbols;1001
16.5.2;C.5.2 Box;1001
16.5.3;C.5.3 Prism;1002
16.5.4;C.5.4 Pyramid;1002
16.6;Cylinder;1002
16.7;Cone;1003
16.8;Spheres;1003
16.8.1;C.8.1 Segments;1003
16.8.2;C.8.2 Sector;1004
16.9;Torus;1004
17;Index;1004
17.1;A;1017
17.2;B;1018
17.3;C;1020
17.4;D;1023
17.5;E;1025
17.6;F;1026
17.7;G;1027
17.8;H;1028
17.9;I;1028
17.10;J–K;1030
17.11;L;1031
17.12;M;1033
17.13;N;1035
17.14;O;1036
17.15;P;1037
17.16;Q;1043
17.17;R;1044
17.18;S;1045
17.19;T;1048
17.20;U;1050
17.21;V;1050
17.22;W;1051
17.23;X;1051
17.24;Y;1051
17.25;Z;1051