GEOMETRIC TOOLS FOR COMPUTER GRAPHICS
1 INTRODUCTION HOW TO USE THIS BOOK ISSUES OF NUMERICAL COMPUTATION LOW-LEVEL ISSUES HIGH-LEVEL ISSUES A SUMMARY OF THE CHAPTERS 2 MATRICES AND LINEAR SYSTEMS INTRODUCTION MOTIVATION ORGANIZATION NOTATIONAL CONVENTIONS TUPLES DEFINITION ARITHMETIC OPERATIONS MATRICES NOTATION AND TERMINOLOGY TRANSPOSITION MATRIX MULTIPLICATION LINEAR SYSTEMS LINEAR EQUATIONS LINEAR SYSTEMS IN TWO UNKNOWNS GENERAL LINEAR SYSTEMS ROW REDUCTIONS, ECHELON FORM, AND RANK SQUARE MATRICES DIAGONAL MATRICES TRIANGULAR MATRICES THE DETERMINANT INVERSE LINEAR SPACES FIELDS DEFINITION AND PROPERTIES SUBSPACES LINEAR COMBINATIONS AND SPAN LINEAR INDEPENDENCE, DIMENSION, AND BASIS LINEAR MAPPINGS MAPPINGS IN GENERAL MATRIX REPRESENTATION OF LINEAR MAPPINGS CRAMER’S RULE CONTENT EIGENVALUES AND EIGENVECTORS EUCLIDEAN SPACE INNER PRODUCT SPACES ORTHOGONALITY AND ORTHONORMAL SETS LEAST SQUARES RECOMMENDED READING 3 VECTOR ALGEBRA VECTOR BASICS VECTOR EQUIVALENCE VECTOR ADDITION VECTOR SUBTRACTION VECTOR SCALING PROPERTIES OF VECTOR ADDITION AND SCALAR MULTIPLICATION VECTOR SPACE SPAN LINEAR INDEPENDENCE BASIS, SUBSPACES, AND DIMENSION ORIENTATION CHANGE OF BASIS LINEAR TRANSFORMATIONS AFFINE SPACES EUCLIDEAN GEOMETRY VOLUME, THE DETERMINANT, AND THE SCALAR TRIPLE PRODUCT FRAMES AFFINE TRANSFORMATIONS TYPES OF AFFINE MAPS COMPOSITION OF AFFINE MAPS BARYCENTRIC COORDINATES AND SIMPLEXES BARYCENTRIC COORDINATES AND SUBSPACES AFFINE INDEPENDENCE 4 MATRICES, VECTOR ALGEBRA, AND TRANSFORMATIONS MATRIX REPRESENTATION OF POINTS AND VECTORS ADDITION, SUBTRACTION, AND MULTIPLICATION VECTOR ADDITION AND SUBTRACTION POINT AND VECTOR ADDITION AND SUBTRACTION SUBTRACTION OF POINTS SCALAR MULTIPLICATION PRODUCTS OF VECTORS DOT PRODUCT CROSS PRODUCT TENSOR PRODUCT THE ’PERP’ OPERATOR AND THE ?PERPÓ DOT PRODUCT MATRIX REPRESENTATION OF AFFINE TRANSFORMATIONS CHANGE-OF-BASIS/FRAME/COORDINATE SYSTEM VECTOR GEOMETRY OF AFFINE TRANSFORMATIONS NOTATION TRANSLATION ROTATION SCALING REFLECTION SHEARING PROJECTIONS ORTHOGRAPHIC OBLIQUE PERSPECTIVE TRANSFORMING NORMAL VECTORS 5 GEOMETRIC PRIMITIVES IN 2D LINEAR COMPONENTS IMPLICIT FORM PARAMETRIC FORM CONVERTING BETWEEN REPRESENTATIONS TRIANGLES RECTANGLES POLYLINES AND POLYGONS QUADRATIC CURVES CIRCLES ELLIPSES POLYNOMIAL CURVES BEZIER CURVES B-SPLINE CURVES NURBS CURVES 6 DISTANCE IN 2D POINT TO LINEAR COMPONENT POINT TO LINE POINT TO RAY POINT TO SEGMENT POINT TO POLYLINE POINT TO POLYGON POINT TO TRIANGLE POINT TO RECTANGLE POINT TO ORTHOGONAL FRUSTUM POINT TO CONVEX POLYGON POINT TO QUADRATIC CURVE POINT TO POLYNOMIAL CURVE LINE TO LINE LINE TO RAY LINE TO SEGMENT RAY TO RAY RAY TO SEGMENT SEGMENT TO SEGMENT LINEAR COMPONENT TO POLYLINE OR POLYGON LINEAR COMPONENT TO QUADRATIC CURVE LINEAR COMPONENT TO POLYNOMIAL CURVE GJK ALGORITHM SET OPERATIONS OVERVIEW OF THE ALGORITHM ALTERNATIVES TO GJK 7 INTERSECTION IN 2D LINEAR COMPONENTS AND POLYLINES LINEAR COMPONENTS AND QUADRATIC CURVES LINEAR COMPONENTS AND GENERAL QUADRATIC CURVES LINEAR COMPONENTS AND CIRCULAR COMPONENTS LINEAR COMPONENTS AND POLYNOMIAL CURVES ALGEBRAIC METHOD POLYLINE APPROXIMATION HIERARCHICAL BOUNDING MONOTONE DECOMPOSITION RASTERIZATION GENERAL QUADRATIC CURVES CIRCULAR COMPONENTS THE METHOD OF SEPARATING AXES SEPARATION BY PROJECTION ONTO A LINE SEPARATION OF STATIONARY CONVEX POLYGONS SEPARATION OF MOVING CONVEX POLYGONS INTERSECTION SET FOR STATIONARY CONVEX POLYGONS CONTACT SET FOR MOVING CONVEX POLYGONS 8 MISCELLANEOUS 2D PROBLEMS CIRCLE THROUGH THREE POINTS CIRCLE TANGENT TO THREE LINES LINE TANGENT TO A CIRCLE AT A GIVEN POINT LINE TANGENT TO A CIRCLE THROUGH A GIVEN POINT LINES TANGENT TO TWO CIRCLES CIRCLE THROUGH TWO POINTS WITH A GIVEN RADIUS CIRCLE THROUGH A POINT AND TANGENT TO A LINE WITH A GIVEN RADIUS CIRCLES TANGENT TO TWO LINES WITH A GIVEN RADIUS CIRCLES THROUGH A POINT AND TANGENT TO A CIRCLE WITH A GIVEN RADIUS CIRCLES TANGENT TO A LINE AND A CIRCLE WITH A GIVEN RADIUS CIRCLES TANGENT TO TWO CIRCLES WITH A GIVEN RADIUS LINE PERPENDICULAR TO A GIVEN LINE THROUGH A GIVEN POINT LINE BETWEEN AND EQUIDISTANT TO TWO POINTS LINE PARALLEL TO A GIVEN LINE AT A GIVEN DISTANCE LINE PARALLEL TO A GIVEN LINE AT A GIVEN VERTICAL ( HORIZONTAL) DISTANCE LINES TANGENT TO A GIVEN CIRCLE AND NORMAL TO A GIVEN LINE 9 GEOMETRIC PRIMITIVES IN 3D PLANAR COMPONENTS PLANES COORDINATE SYSTEM RELATIVE TO A PLANE 2D OBJECTS IN A PLANE POLYMESHES, POLYHEDRA, AND POLYTOPES VERTEX-EDGE-FACE TABLES CONNECTED MESHES MANIFOLD MESHES CLOSED MESHES CONSISTENT ORDERING PLATONIC SOLIDS QUADRIC SURFACES THREE NONZERO EIGENVALUES TWO NONZERO EIGENVALUES ONE NONZERO EIGENVALUE TORUS POLYNOMIAL SURFACES BEZIER SURFACES B-SPLINE SURFACES NURBS SURFACES 10 DISTANCE IN 3D POINT TO RAY OR LINE SEGMENT POINT TO PLANAR COMPONENT POINT TO PLANE POINT TO CIRCLE OR DISK POINT TO POLYHEDRON GENERAL PROBLEM POINT TO ORIENTED BOUNDING BOX POINT TO QUADRIC SURFACE POINT TO GENERAL QUADRIC SURFACE POINT TO ELLIPSOID POINT TO POLYNOMIAL SURFACE LINES AND LINES SEGMENT/SEGMENT, LINE/RAY, LINE/SEGMENT, RAY/ RAY, RAY/ SEGMENT SEGMENT TO SEGMENT, ALTERNATIVE APPROACH LINEAR COMPONENT TO TRIANGLE, RECTANGLE, TETRAHEDRON, ORIENTED BOX LINEAR COMPONENT TO TRIANGLE LINEAR COMPONENT TO RECTANGLE LINEAR COMPONENT TO TETRAHEDRON LINEAR COMPONENT TO ORIENTED BOUNDING BOX LINE TO QUADRIC SURFACE LINE TO POLYNOMIAL SURFACE MISCELLANEOUS DISTANCE BETWEEN LINE AND PLANAR CURVE DISTANCE BETWEEN LINE AND PLANAR SOLID OBJECT DISTANCE BETWEEN PLANAR CURVES GEODESIC DISTANCE ON SURFACES 11 INTERSECTION IN 3D LINEAR COMPONENTS AND PLANAR COMPONENTS LINEAR COMPONENTS AND PLANES LINEAR COMPONENTS AND TRIANGLES LINEAR COMPONENTS AND POLYGONS LINEAR COMPONENT AND DISK LINEAR COMPONENTS AND POLYHEDRA LINEAR COMPONENTS AND QUADRIC SURFACES GENERAL QUADRIC SURFACES LINEAR COMPONENTS AND A SPHERE LINEAR COMPONENTS AND AN ELLIPSOID LINEAR COMPONENTS AND CYLINDERS LINEAR COMPONENTS AND A CONE LINEAR COMPONENTS AND POLYNOMIAL SURFACES ALGEBRAIC SURFACES FREE-FORM SURFACES TWO PLANES THREE PLANES TRIANGLE AND PLANE TRIANGLE AND TRIANGLE PLANAR COMPONENTS AND POLYHEDRA TRIMESHES GENERAL POLYHEDRA PLANAR COMPONENTS AND QUADRIC SURFACES PLANE AND GENERAL QUADRIC SURFACE PLANE AND SPHERE PLANE AND CYLINDER PLANE AND CONE TRIANGLE AND CONE PLANAR COMPONENTS AND POLYNOMIAL SURFACES HERMITE CURVES GEOMETRY DEFINITIONS COMPUTING THE CURVES THE ALGORITHM IMPLEMENTATION NOTES GENERAL INTERSECTION ELLIPSOIDS SUBDIVISION METHODS LATTICE EVALUATION ANALYTIC METHODS MARCHING METHODS SEPARATION OF STATIONARY CONVEX POLYHEDRA SEPARATION OF MOVING CONVEX POLYHEDRA INTERSECTION SET FOR STATIONARY CONVEX POLYHEDRA CONTACT SET FOR MOVING CONVEX POLYHEDRA ORIENTED BOUNDING BOX AND ORTHOGONAL FRUSTUM LINEAR COMPONENT AND AXIS-ALIGNED BOUNDING BOX LINEAR COMPONENT AND ORIENTED BOUNDING BOX PLANE AND AXIS-ALIGNED BOUNDING BOX PLANE AND ORIENTED BOUNDING BOX AXIS-ALIGNED BOUNDING BOXES ORIENTED BOUNDING BOXES SPHERE AND AXIS-ALIGNED BOUNDING BOX CYLINDERS LINEAR COMPONENT AND TORUS 12 MISCELLANEOUS 3D PROBLEMS PROJECTION OF A POINT ONTO A PLANE PROJECTION OF A VECTOR ONTO A PLANE ANGLE BETWEEN A LINE AND A PLANE ANGLE BETWEEN TWO PLANES PLANE NORMAL TO A LINE AND THROUGH A GIVEN POINT PLANE THROUGH THREE POINTS ANGLE BETWEEN TWO LINES 13 COMPUTATIONAL GEOMETRY TOPICS BINARY SPACE-PARTITIONING TREES IN 2D BSP TREE REPRESENTATION OF A POLYGON MINIMUM SPLITS VERSUS BALANCED TREES POINT IN POLYGON USING BSP TREES PARTITIONING A LINE SEGMENT BY A BSP TREE BINARY SPACE-PARTITIONING TREES IN 3D BSP TREE REPRESENTATION OF A POLYHEDRON POINT IN POLYHEDRON USING BSP TREES PARTITIONING A CONVEX POLYGON BY A BSP TREE POINT IN POLYGON POINT IN TRIANGLE POINT IN CONVEX POLYGON POINT IN GENERAL POLYGON FASTER POINT IN GENERAL POLYGON A GRID METHOD POINT IN POLYHEDRON POINT IN TETRAHEDRON POINT IN CONVEX POLYHEDRON POINT IN GENERAL POLYHEDRON BOOLEAN OPERATIONS ON POLYGONS THE ABSTRACT OPERATIONS THE TWO PRIMITIVE OPERATIONS BOOLEAN OPERATIONS USING BSP TREES OTHER ALGORITHMS BOOLEAN OPERATIONS ON POLYHEDRA ABSTRACT OPERATIONS CONVEX HULLS CONVEX HULLS IN 2D CONVEX HULLS IN 3D CONVEX HULLS IN HIGHER DIMENSIONS DELAUNAY TRIANGULATION INCREMENTAL CONSTRUCTION IN 2D INCREMENTAL CONSTRUCTION IN GENERAL DIMENSIONS CONSTRUCTION BY CONVEX HULL POLYGON PARTITIONING VISIBILITY GRAPH OF A SIMPLE POLYGON TRIANGULATION TRIANGULATION BY HORIZONTAL DECOMPOSITION CONVEX PARTITIONING CIRCUMSCRIBED AND INSCRIBED BALLS CIRCUMSCRIBED BALL INSCRIBED BALL MINIMUM BOUNDS FOR POINT SETS MINIMUM-AREA RECTANGLE MINIMUM-VOLUME BOX MINIMUM-AREA CIRCLE MINIMUM-VOLUME SPHERE AREA AND VOLUME MEASUREMENTS AREA OF A 2D POLYGON AREA OF A 3D POLYGON VOLUME OF A POLYHEDRON C H A P T E R INTRODUCTION 1 1 HOW TO USE THIS BOOK THIS BOOK HAS MANY FACETS AN INITIAL GLANCE AT THE TABLE OF CONTENTS SHOWS THAT THE BOOK IS ABOUT TWO- AND THREE-DIMENSIONAL GEOMETRIC ALGORITHMS THAT ARE APPLICABLE IN COMPUTER GRAPHICS AND IN OTHER ?ELDS AS WELL THE SECTIONS HAVE BEEN ORGANIZED TO MAKE IT EASY TO LOCATE AN ALGORITHM OF INTEREST AND HAVE BEEN WRITTEN WITH THE GOAL OF MAKING THEM AS SELF-CONTAINED AS POSSIBLE IN THIS GUISE THE BOOK IS WELL SUITED AS A REFERENCE FOR THE EXPERIENCED PRACTITIONER WHO REQUIRES A SPECI?C ALGORITHM FOR THE APPLICATION AT HAND BUT THE BOOK IS MORE THAN JUST A REFERENCE A CAREFUL STUDY OF THE MATERIAL WILL REVEAL THAT MANY OF THE CONCEPTS USED TO ANALYZE A GEOMETRIC QUERY ARE COMMON TO MANY OF THE QUERIES FOR EXAMPLE, CONSIDER THE THREE-DIMENSIONAL GEOMETRIC QUERIES OF COMPUTING THE DISTANCE BETWEEN PAIRS OF OBJECTS THAT ARE POINTS, LINE SEGMENTS, TRIANGLES, RECTANGLES, TETRAHEDRA, OR BOXES THE QUERY FOR EACH PAIR OF OBJECTS CAN BE ANALYZED USING SPECI?C KNOWLEDGE ABOUT THE FORM OF THE OBJECT THE COMMON THEME THAT UNI?ES THE ANALYSIS OF THE QUERIES IS THAT THE OBJECTS CAN BE PARAMETERIZED BY ZERO (POINT), ONE (SEGMENT), TWO (TRIANGLE, RECTANGLE), OR THREE (TETRAHEDRA, BOX) PARAMETERS THE SQUARED DISTANCE BETWEEN ANY TWO POINTS, ONE FROM EACH OBJECT, IS A QUADRATIC POLYNOMIAL OF THE APPROPRIATE PARAMETERS THE SQUARED DISTANCE BETWEEN THE TWO OBJECTS IS THE MINIMUM OF THE QUADRATIC POLYNOMIAL A SEARCH OF THE DOMAIN OF THE FUNCTION WILL LEAD TO THE PARAMETERS THAT CORRESPOND TO THE CLOSEST POINTS ON THE OBJECTS AND, CONSEQUENTLY, THE MINIMUM SQUARED DISTANCE BETWEEN THE OBJECTS THIS IDEA OF SEARCHING THE PARAMETER DOMAIN IS THE FOUNDATION OF THE GJK DISTANCE ALGORITHM THAT IS USED FOR COMPUTING THE DISTANCE BETWEEN TWO CONVEX POLYHEDRA THE COMMON IDEAS IN THE VARIOUS QUERIES FORM THE BASIS FOR A SET OF ANALYTICAL TOOLS THAT ANY PRACTITIONER IN COMPUTER GRAPHICS SHOULD HAVE READILY AVAILABLE FOR SOLVING NEW PROBLEMS THUS, THIS BOOK IS ALSO WELL SUITED AS A LEARNING TOOL FOR SOMEONE WISHING