Lecture notes on Computer Graphics for Engineers

1

DRAFT CVEN 6837 LECTURE NOTES:

COMPUTER GRAPHICS for ENGINEERS

c
VICTOR E. SAOUMA, 1991

Dept. of Civil Environmental and Architectural Engineering University of Colorado, Boulder, CO 80309-0428

March 6, 2000

2

Contents I

GEOMETRIC MODELING

13

1 HOMOGENEOUS TRANSFORMATIONS 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Needs for Transformation . . . . . . . . . . . . . . . . . . . . 1.1.2 Homogeneous Coordinates . . . . . . . . . . . . . . . . . . . . 1.1.3 Homogeneous Transformations . . . . . . . . . . . . . . . . . 1.1.4 Types of Transformations . . . . . . . . . . . . . . . . . . . . 1.2 2-D Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 GKS Supported . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1.1 Translation . . . . . . . . . . . . . . . . . . . . . . . 1.2.1.2 Scaling . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1.3 Rotation . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Other Transformations . . . . . . . . . . . . . . . . . . . . . . 1.2.2.1 Reflection . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2.2 Shear . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.3 Composite Transformations . . . . . . . . . . . . . . . . . . . 1.2.3.1 Scaling Relative to a Fixed Point . . . . . . . . . . . 1.2.3.2 Rotation about an Arbitrary Point . . . . . . . . . . 1.3 3-D Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Translation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.3 Rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.4 Reflection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.5 Shear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Coordinate vs Geometric Transformation . . . . . . . . . . . . . . . 1.4.1 Coordinate Transformation . . . . . . . . . . . . . . . . . . . 1.4.2 Coordinate vs Geometric Transformation . . . . . . . . . . . 1.4.3 Equivalent Geometric Transformation in Different Coordinate 1.5 Efficiency Considerations . . . . . . . . . . . . . . . . . . . . . . . . 1.5.1 Matrix Operations . . . . . . . . . . . . . . . . . . . . . . . . 1.5.2 Dynamic Rotation . . . . . . . . . . . . . . . . . . . . . . . . 1.5.3 Block Transfers in Raster Devices . . . . . . . . . . . . . . . 3

15 . . . . 15 . . . . 15 . . . . 15 . . . . 15 . . . . 16 . . . . 17 . . . . 17 . . . . 17 . . . . 18 . . . . 19 . . . . 19 . . . . 19 . . . . 21 . . . . 22 . . . . 22 . . . . 23 . . . . 23 . . . . 23 . . . . 24 . . . . 24 . . . . 24 . . . . 25 . . . . 25 . . . . 25 . . . . 27 Systems 27 . . . . 27 . . . . 27 . . . . 28 . . . . 28

CONTENTS

4 2 3D ANALYTIC GEOMETRY for COMPUTER GRAPHICS 2.1 Parameteric Representation . . . . . . . . . . . . . . . . . . . . . 2.2 Some Useful Relations . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Angle Between Two Direction Vectors . . . . . . . . . . . 2.2.2 Definition of a Line . . . . . . . . . . . . . . . . . . . . . . 2.2.2.1 Example . . . . . . . . . . . . . . . . . . . . . . 2.2.3 Definition of a Plane . . . . . . . . . . . . . . . . . . . . . 2.2.4 Intersection of a Line and a Plane . . . . . . . . . . . . . 2.2.5 Distance from a Point and a Plane . . . . . . . . . . . . . 2.2.5.1 Example . . . . . . . . . . . . . . . . . . . . . . 2.2.6 Intersection of Two Lines . . . . . . . . . . . . . . . . . . 2.2.6.1 Example 1 . . . . . . . . . . . . . . . . . . . . . 2.2.6.2 Example 2 . . . . . . . . . . . . . . . . . . . . . 2.2.7 Shortest Distance Between Two Lines . . . . . . . . . . . 2.2.7.1 Non-Parallel Case . . . . . . . . . . . . . . . . . 2.2.7.1.1 Example . . . . . . . . . . . . . . . . . 2.2.7.2 Parallel Lines . . . . . . . . . . . . . . . . . . . . 2.2.7.2.1 Example . . . . . . . . . . . . . . . . . 2.2.8 Plane Through Three Non-Collinear Points . . . . . . . . 2.2.8.1 Example . . . . . . . . . . . . . . . . . . . . . . 2.2.9 Point Of Intersection of Three Planes . . . . . . . . . . . 2.2.9.1 Example . . . . . . . . . . . . . . . . . . . . . . 2.2.10 Line Intersection of Two Planes . . . . . . . . . . . . . . . 2.2.10.1 Example . . . . . . . . . . . . . . . . . . . . . . 2.3 Data Representation of 3D Objects . . . . . . . . . . . . . . . . . 2.3.1 Geometrical . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1.1 Explicit Polygon Mesh . . . . . . . . . . . . . . 2.3.1.2 Explicit Edge Mesh . . . . . . . . . . . . . . . . 2.3.2 Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 THREE DIMENSIONAL PROJECTIONS 3.1 Introduction . . . . . . . . . . . . . . . . . . . 3.1.1 Definition . . . . . . . . . . . . . . . . 3.1.2 Historical Background . . . . . . . . . 3.1.3 Projections and Graphics Standards . 3.1.4 Types of Projections . . . . . . . . . . 3.2 Planar Geometric Projections, Definitions . . 3.2.1 Perspective Projections . . . . . . . . 3.2.1.1 Characteristics . . . . . . . . 3.2.1.2 Categories . . . . . . . . . . 3.2.2 Parallel Projections . . . . . . . . . . 3.2.2.1 Categories . . . . . . . . . . 3.2.2.2 Characteristics . . . . . . . . 3.3 Mathematics of Planar Geometric Projections 3.3.1 Perspective Projection . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

31 31 32 34 34 34 34 34 35 35 36 36 36 36 36 37 37 38 38 38 38 39 39 40 40 40 41 41 42

. . . . . . . . . . . . . .

43 43 43 43 44 44 44 45 45 46 46 47 48 49 49

CONTENTS

5

3.3.2

3.4

3.5

3.6

Parallel Projection . . . . . . . . . . . . . . . . . . . . . 3.3.2.1 Orthographic . . . . . . . . . . . . . . . . . . . 3.3.2.2 Oblique . . . . . . . . . . . . . . . . . . . . . . 3.3.2.2.1 Cavalier . . . . . . . . . . . . . . . . . 3.3.2.2.2 Cabinet . . . . . . . . . . . . . . . . . Simple 3D Viewing . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Observer’s Coordinate System . . . . . . . . . . . . . . 3.4.2 Fortran Implementation of a Simple 3D Viewing . . . . 3.4.3 Subroutine Description . . . . . . . . . . . . . . . . . . . 3.4.3.1 Common Data . . . . . . . . . . . . . . . . . . 3.4.3.2 Tree Structure . . . . . . . . . . . . . . . . . . Arbitrary 3-D Viewing Definition . . . . . . . . . . . . . . . . . 3.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3.5.2 Viewing Coordinate System . . . . . . . . . . . . . . . . 3.5.3 Projection Characteristics . . . . . . . . . . . . . . . . . 3.5.4 View Volume . . . . . . . . . . . . . . . . . . . . . . . . 3.5.4.1 Projection Window . . . . . . . . . . . . . . . 3.5.4.2 View Volume Bounds, or Clipping Planes . . . 3.5.4.3 Canonical Viewing Volume . . . . . . . . . . . 3.5.4.4 Clipping Against a Canonical View Volume . . Implementation of Arbitrary 3D Viewing Operations . . . . . . 3.6.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6.2 Generalized Normalization Transformations Npar & Nper 3.6.2.1 Parallel Projection . . . . . . . . . . . . . . . . 3.6.2.2 Perspective Projection . . . . . . . . . . . . . .

4 CURVES and SURFACE 4.1 Introduction . . . . . . . . . . . . . . . 4.2 Parametric Cubic Curves . . . . . . . 4.2.1 Geometric Constraints . . . . . 4.2.1.1 Piece-wise Linear . . 4.2.1.2 Cubic Generalization 4.2.2 Classification of Curves . . . . 4.2.3 Hermite Form . . . . . . . . . . 4.2.4 Bezier Form . . . . . . . . . . . 4.2.5 B-Splines . . . . . . . . . . . . 4.2.5.1 Non-Periodic Form . . 4.2.5.1.1 Quadratic . . 4.2.5.1.2 Cubic . . . . 4.2.5.2 Periodic Form . . . . 4.3 Parametric Surfaces . . . . . . . . . . 4.3.1 Bilinear Patch . . . . . . . . . 4.3.2 Coons Patches . . . . . . . . . 4.3.3 Hermite Patches . . . . . . . . 4.3.3.1 Example . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

50 50 51 52 52 52 52 55 55 55 57 57 57 59 60 60 60 61 62 62 64 64 65 66 66

. . . . . . . . . . . . . . . . . .

67 67 68 68 68 68 69 70 71 75 75 75 77 78 78 78 79 80 81

CONTENTS

6 4.3.4 4.3.5

Bezier Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B-Spline Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 FRACTALS 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Fractal-Geometry . . . . . . . . . . . . . . . . . . . . . 5.2.1 Types of Geometric Fractals . . . . . . . . . . . 5.2.1.1 Natural Fractals . . . . . . . . . . . . 5.2.1.2 Artificial Fractals . . . . . . . . . . . 5.2.1.3 Random Fractals . . . . . . . . . . . . 5.2.1.3.1 Fractal Lines . . . . . . . . . 5.2.1.3.2 Fractal Surfaces . . . . . . . 5.2.2 Theoretical Considerations . . . . . . . . . . . 5.2.2.1 Fractal Dimension . . . . . . . . . . . 5.2.2.2 Fractal versus Topological Dimensions 5.2.2.3 Fractal Definition . . . . . . . . . . . 5.2.3 Numerical Determination of Fractal Dimension 5.2.3.1 Box Method . . . . . . . . . . . . . . 5.2.3.2 Ruler’s Method . . . . . . . . . . . . 5.2.3.3 Comments . . . . . . . . . . . . . . . 5.3 Fractal-Algebra . . . . . . . . . . . . . . . . . . . . . . 5.3.1 The Julia Set . . . . . . . . . . . . . . . . . . . 5.3.1.1 Definition . . . . . . . . . . . . . . . . 5.3.1.2 Computer Implementation . . . . . . 5.3.2 The Mandelbrot Set . . . . . . . . . . . . . . . 5.3.2.1 Definition . . . . . . . . . . . . . . . . 5.3.2.2 Computer Implementation . . . . . . 5.3.3 Observations . . . . . . . . . . . . . . . . . . . 5.4 Applications . . . . . . . . . . . . . . . . . . . . . . . .

II

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

RENDERING

6 LIGHT & COLOR 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Color Descriptions . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.1 RGB and CMY . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.2 HSV and HLS . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Interpolating in Color Space . . . . . . . . . . . . . . . . . . . . . . 6.3.1 Distinguishable Number of Colors . . . . . . . . . . . . . . 6.3.2 Display of Light Intensities . . . . . . . . . . . . . . . . . . 6.3.2.1 Color Displays . . . . . . . . . . . . . . . . . . . . 6.3.2.2 Monochrome Displays: Half-Tone Approximations

82 82 85 85 86 86 86 86 87 87 88 88 88 89 89 90 90 90 91 91 91 91 94 95 95 96 96 97

99

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

101 101 102 103 104 105 106 106 106 106

CONTENTS

7

7 ILLUMINATION, SURFACE SHADING, & RENDERING 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Illumination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2.2 Surface Properties . . . . . . . . . . . . . . . . . . . . . . . 7.2.3 Illumination . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2.3.1 Types of Light Sources . . . . . . . . . . . . . . . 7.2.3.2 Light Reflection . . . . . . . . . . . . . . . . . . . 7.2.4 Illumination Models . . . . . . . . . . . . . . . . . . . . . . 7.2.4.1 Diffuse Reflections . . . . . . . . . . . . . . . . . . 7.2.4.1.1 Lambertian Model . . . . . . . . . . . . . 7.2.4.1.2 Modification for Ambient light . . . . . . 7.2.4.1.3 Light Source Attenuation . . . . . . . . . 7.2.4.1.4 Colored Lights and Surfaces . . . . . . . 7.2.4.1.5 Atmospheric Attenuation, Depth Cueing 7.2.4.2 Specular Reflection . . . . . . . . . . . . . . . . . 7.2.4.3 Complete Illumination Model . . . . . . . . . . . . 7.3 Surface or Polygon Shading . . . . . . . . . . . . . . . . . . . . . . 7.3.1 Constant or Flat Shading . . . . . . . . . . . . . . . . . . . 7.3.1.0.1 Mach Band Effects . . . . . . . . . . . . . 7.3.2 Gouraud or Intensity Interpolation Shading . . . . . . . . . 7.3.3 Phong or Normal Interpolation Shading . . . . . . . . . . . 7.4 Rendering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4.1 Shadows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4.2 Transparency . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4.3 Texture Mapping . . . . . . . . . . . . . . . . . . . . . . . . 8 RAY TRACING (UNEDITED) 8.1 Introduction . . . . . . . . . . . 8.2 Algorithm . . . . . . . . . . . . 8.3 Perspective . . . . . . . . . . . 8.4 Shading Models . . . . . . . . . 8.5 Anti aliasing . . . . . . . . . . 8.6 Texture . . . . . . . . . . . . . 8.7 Summary . . . . . . . . . . . . 8.8 References . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

9 HIDDEN LINES/SURFACES REMOVAL 9.1 Object Definition . . . . . . . . . . . . . . . 9.1.1 Polygonal Mesh . . . . . . . . . . . . 9.1.1.1 Explicit Polygon Mesh . . 9.1.1.2 Explicit Edge Mesh . . . . 9.1.1.3 Attributes . . . . . . . . . 9.1.2 General Polyhedron . . . . . . . . . 9.1.3 Convex Polyhedron . . . . . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . .

109 109 109 109 110 110 110 110 111 111 111 111 112 112 113 113 114 114 114 115 115 115 116 116 117 117

. . . . . . . .

119 119 120 121 124 125 125 126 126

. . . . . . .

129 129 130 130 131 131 132 133

CONTENTS

8 9.2 9.3 9.4

9.5

9.6 9.7

Types of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 Simplifying Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 Object Space Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 9.4.1 Back-Face Removal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 9.4.2 Robert’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 9.4.2.1 Assumptions: . . . . . . . . . . . . . . . . . . . . . . . . . . 134 9.4.2.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 9.4.2.2.1 Preprocessing . . . . . . . . . . . . . . . . . . . . 135 9.4.2.2.1.1 Example 1: Volume Matrix . . . . . . . . . 136 9.4.2.2.1.2 Example 2: Plane Equation . . . . . . . . . 137 9.4.2.2.2 Self Hidden Plane Removal . . . . . . . . . . . . . 138 9.4.2.2.2.1 Example 3: Self Hidden Planes . . . . . . . 138 9.4.2.2.2.2 Example 4: Self Hidden Plane Following Viewing Transformation . . . . . . . . . . . . . . 139 9.4.2.2.3 Self Hidden Line Removal . . . . . . . . . . . . . . 140 9.4.2.2.4 Removal of Lines Hidden by Other Volumes, New Contact Lines . . . . . . . . . . . . . . . . . . . . 140 9.4.2.2.4.1 Example 5: Parametric Plane . . . . . . . . 144 9.4.2.2.4.2 Example 6: Testing A Line Against a Volume146 Image Space Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 9.5.1 Depth Buffer Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 146 9.5.1.1 Z Buffer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 9.5.1.2 Scan Line Algorithm . . . . . . . . . . . . . . . . . . . . . . 147 9.5.2 Screen Subdivision Method . . . . . . . . . . . . . . . . . . . . . . . 147 9.5.2.1 Warnock Algorithm . . . . . . . . . . . . . . . . . . . . . . 147 9.5.2.2 Weiler-Atherton Algorithm . . . . . . . . . . . . . . . . . . 149 Object-Image Algorithm: Depth Sorting or Painter’s Algorithm . . . . . . . 149 Source Listing for Z-Buffer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

10 BIBLIOGRAPHY

161

List of Figures 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9

2-D Translation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-D Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2-D Rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Reflection with respect to the x axis . . . . . . . . . . . . . . . . . . . . . . Reflection with respect to the y axis . . . . . . . . . . . . . . . . . . . . . . Reflection with respect to the z axis . . . . . . . . . . . . . . . . . . . . . . Shear Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Scaling With Respect to a Fixed Point . . . . . . . . . . . . . . . . . . . . . Conversion of a Coordinate System from Right-handed System to Left-handed System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.10 Shearing of a Unit Cube . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.11 Geometric vs Coordinate Transformation . . . . . . . . . . . . . . . . . . . 1.12 Equivalent Geometric Transformation . . . . . . . . . . . . . . . . . . . . .

17 18 19 20 20 21 21 22

3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16

Perspective Projection . . . . . . . . . . . . . . . . . . . . . . . . One and Two Point Perspective Projections of a Cube . . . . . . Parallel Projection . . . . . . . . . . . . . . . . . . . . . . . . . . Three Orthographic Projections . . . . . . . . . . . . . . . . . . . Isometric Projection . . . . . . . . . . . . . . . . . . . . . . . . . Oblique Projection . . . . . . . . . . . . . . . . . . . . . . . . . . Cavalier Projection . . . . . . . . . . . . . . . . . . . . . . . . . . Cabinet Projection . . . . . . . . . . . . . . . . . . . . . . . . . . Perspective Projection . . . . . . . . . . . . . . . . . . . . . . . . Oblique Projection . . . . . . . . . . . . . . . . . . . . . . . . . . Observer’s Coordinate System . . . . . . . . . . . . . . . . . . . . View Reference Point and View Plane Normal Definition . . . . . u-v-VPN, or xv , yv , zv Coordinate System . . . . . . . . . . . . . Projection Window Definition . . . . . . . . . . . . . . . . . . . . Semi-Infinite Pyramid View Volume for a Perspective Projection Infinite Parallelepiped View Volume for a Parallel Projection . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

45 46 46 47 47 48 48 48 49 51 53 59 60 61 61 62

4.1 4.2 4.3 4.4 4.5

Control Points for Interpolation or Approximation . . Family of Hermite Parametric Curves . . . . . . . . . Bezier Curve and Its Four Control Points . . . . . . . Bezier’s Blending Curves for a Cubical Approximation Non-Periodic Quadratic B-Splines . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

68 72 72 75 76

9

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

25 26 27 28

LIST OF FIGURES

10 4.6 4.7 4.8

Open and Closed Periodic B-Splines . . . . . . . . . . . . . . . . . . . . . . Coons Patch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example of a Parametric Cubic Patch . . . . . . . . . . . . . . . . . . . . .

78 79 81

5.1 5.2 5.3 5.4 5.5

Artificial Fractal: Triadic Koch Curve Fractal Dimension definition . . . . . . Example of Fractal Dimension of 2 . . Basin of an attractive fixed point . . . Basin of an attractive cycle of period 3

. . . . .

87 88 90 92 93

6.1 6.2

Value and Saturation Plane for a given Hue in the HSV Model . . . . . . . 2 by 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

105 107

8.1 8.2 8.3 8.4 8.5 8.6 8.7 8.8

Reflection, refraction of rays . . . . . . . . Trace tree. . . . . . . . . . . . . . . . . . . Simple ray tracing algorithm . . . . . . . Perspective projection. . . . . . . . . . . . Perspective projection with predetermined Vectors in the Phong shading model. . . . Anti aliasing of a pixel. . . . . . . . . . . Ray tracing algorithm with texture . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

120 121 122 123 124 125 125 127

9.1 9.2 9.3 9.4 9.5 9.6 9.7 9.8 9.9 9.10 9.11 9.12

Two Adjacent Polygons . . . . . . . . . . . . . . . . . . . . Back Face Removal . . . . . . . . . . . . . . . . . . . . . . . Example of a Volume Matrix . . . . . . . . . . . . . . . . . Example of a Plane Equation . . . . . . . . . . . . . . . . . Example of Self Hidden Planes . . . . . . . . . . . . . . . . Example of Self Hidden Planes for a Rotated Volume . . . . Multiple Convex Volumes . . . . . . . . . . . . . . . . . . . Example of a Parametric Plane . . . . . . . . . . . . . . . . Example of a Testing an Edge against a Volume . . . . . . Warnock Algorithm Subdivisions . . . . . . . . . . . . . . . Quadtree Data Structure for Warnock’s Algorithm . . . . . Relationships Among Polygons for the Warnock Algorithm

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

130 134 136 137 139 139 141 145 145 148 148 149

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . . . . . . . . . . . . . . . . . . . . . viewport . . . . . . . . . . . . . . . . . .

. . . . .

. . . . . . . .

. . . . .

. . . . . . . .

. . . . .

. . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

List of Tables 3.1

Cohen-Sutherland Clipping Algorithm . . . . . . . . . . . . . . . . . . . . .

63

5.1 5.2 5.3

Fractal Dimension Definition . . . . . . . . . . . . . . . . . . . . . . . . . . Some c and Windows for the Julia Set . . . . . . . . . . . . . . . . . . . . . Some Windows into the Mandelbrot Set . . . . . . . . . . . . . . . . . . . .

89 95 97

6.1 6.2 6.3 6.4

Visible Spectrum . RGB Table . . . . CMY Table . . . . Differences between

9.1 9.2 9.3 9.4

Explicit Polygon Mesh Data Base . Explicit Edge Mesh Data Base . . Extended Explicit Edge Mesh Data 5 Common Polyhedrons . . . . . .

. . . . . . . . . . . . . . . . . . RGB and

. . . . . . . . . . . . . . . . . . . . . . . . CMY models . . . . . . . . Base . . . . .

11

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

101 103 103 104

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

130 131 132 132

12

LIST OF TABLES

Part I

GEOMETRIC MODELING

13

Chapter 1

HOMOGENEOUS TRANSFORMATIONS 1.1

Introduction

Most of this material is adapted from Chapter 5 of Foley and Van Dam Computer Graphics, 2nd Edition.

1.1.1

Needs for Transformation

With the procedure of displaying output primitives, we create a variety of pictures (typically stored within segments). Often those primitives have to be transformed because: 1. Similar (but not identical) ones are to be also generated, thus it is computationally more efficient to copy those segments into new ones after proper transformation. 2. For three dimensional viewing, a 3-D object is to be mapped into a 2-D display through a series of transformations.

1.1.2

Homogeneous Coordinates

In homogeneous coordinates, point P (x, y) is represented as P (W.x, W.y, W ) for any scale factor W = 0. Thus, given a homogeneous coordinate representation for P (X, Y, W ), we can find the X Y and y = W . In general 2D cartesian coordinate representation for the point as x = W W = 1., however in some cases (to be discussed in the next chapter) it is equal to d (for perspective projections). It is thus apparent that there is an infinite number of homogeneous coordinates for any point ([9, 6, 3] = [12, 8, 4] = [3, 2, 1] all represent the same point P(3,2)). Similarly three dimensional point P (x, y, z) is represented as P (W x, W.y, W.z, W ) Homogeneous coordinates are used internally by GKS and PHIGS.

1.1.3

Homogeneous Transformations

In all cases a viewing transformation can always be decomposed into a combination of three fundamental ones (or components): 15

CHAPTER 1. HOMOGENEOUS TRANSFORMATIONS

16 1. Scaling 2. Rotation 3. Translation

The first two transformations can be expressed through a matrix operation, in which the new vector is equal to the previous one times a matrix (2x2 for 2-D, and 3x3 for 3-D). The last operation can only be represented through a vector addition. Thus in order to: 1. “Streamline” the transformation operations into a single matrix multiplication, and thus be able to concatenate various transformations into a single one, 2. Take advantage of specialized micro-processors for matrix multiplications, 3. Efficiently undo transformations after they have been performed. we use a Homogeneous transformation along with homogeneous coordinates. In general a transformation can be written as:    x
     y
   z
      

1

or:

   

=

T11 T21 T31 T41

T12 T22 T32 T42

T13 T23 T33 T43

T14 T24 T34 T44

   x       y     z       

(1.1)

1

P
= TR.P

(1.2)

It is apparent that a homogeneous transformation can be uniquely defined by a square matrix, the inverse of which can always be defined. Thus to undo a transformation, we would simply have to apply its inverse matrix. Note that in some references, the transformation matrix is defined as: 

 

  x , y , 1 = [x, y, 1]  


T11
T21
T31
T41


T12
T22
T32
T42


T13
T23
T33
T43


T14
T24
T34
T44

    

(1.3)

This formulation will result in transformation matrices which are the transpose of the one used in these notes.

1.1.4

Types of Transformations

There are two similar ways of perceiving transformations: 1. Geometric Transformations in which an object is transformed into a new position within the same original coordinate system. 2. Coordinate Transformation in which an object defined in one coordinate system is transformed into another coordinate system. Note that the origin of the first coordinate system is known with respect to the second one. In the following sections, we shall concentrate on geometric transformations, and the relationship between coordinate and geometric transformations will be discussed later.

1.2. 2-D TRANSFORMATION

17

Figure 1.1: 2-D Translation

1.2

2-D Transformation

In discussing 2-D transformations within the context of GKS and PHIGS, we should note that both standards: 1. Provide a function to evaluate an initial transformation matrix for the three fundamental operations. 2. Provide a function to accumulate or concatenate two different transformations. 3. Can accept a user defined transformation matrix. 4. Store only the first two columns of the transformation matrix (a vector with 6 rows). We shall thus start by considering the three fundamental transformations supported by GKS and PHIGS (which would simply “build” the transformation matrix).

1.2.1

GKS Supported

Through the EVALUATE TRANSFORMATION MATRIX operation GKS can build a matrix for the operations discussed in the following subsections, and through the ACCUMULATE TRANSFORMATION MATRIX a transformation matrix is concatenated with another one through matrix multiplication. Note that the operations are associated with segment (GKS) or structure (PHIGS) transformations. 1.2.1.1

Translation

An output primitive can be translated along the x and y axis by Tx and Ty respectively, Fig. 1.1.

CHAPTER 1. HOMOGENEOUS TRANSFORMATIONS

18

Figure 1.2: 2-D Scaling  
  x  





1 0 tx   x  
y =  0 1 ty  y    1   0 0 1  1 

Note that:

 



  

(1.4)

 





1 0 tx1 1 0 tx2 1 0 tx1 + tx2        0 1 ty1  ·  0 1 ty2  =  0 1 ty1 + ty2  0 0 1 0 0 1 0 0 1 

and that:

or

1.2.1.2

 





(1.5)



1 0 tx1 1 0 −tx1 1 0 0        0 1 ty1  ·  0 1 −ty1  =  0 1 0  0 0 1 0 0 1 0 0 1

(1.6)

T(−tx , −ty ) = T−1 (tx , ty )

(1.7)

Scaling

An object can be scaled by sx and sy with respect to the origin, Fig. 1.2.  
  x  





sx 0 0   x  
y =  0 sy 0  y    1   0 0 1  1 or P
= S(sx , sy ).P Note that: 

 





  

(1.8)

 



sx1 0 0 sx2 0 0 sx1 .sx2 0 0       0 sy1 .sy2 0   0 sy1 0  ·  0 sy2 0  =  0 0 1 0 0 1 0 0 1

(1.9)

1.2. 2-D TRANSFORMATION

19

Figure 1.3: 2-D Rotation Where the scaling is with respect to the origin. If scaling is to be performed with respect to another point, than a translation must first be performed. Finally, it should be noted that S( s1x , s1y ) = S−1 (sx , sy ) 1.2.1.3

(1.10)

Rotation

An object can be rotated with respect to the z axis by an angle θ (positive counterclockwise), Fig. 1.3, through the following transformation:  
  x  





cos θ − sin θ 0   x  
y =  sin θ cos θ 0  y    1   0 0 1  1

    

(1.11)

Again, it should be noted that: R(−θ) = R−1 (θ)

1.2.2

(1.12)

Other Transformations

Both GKS and PHIGS provide the means of automatically generating the transformation matrices associated with the three fundamental transformations, there are some additional ones which can be of general interest. 1.2.2.1

Reflection

A reflection is a transformation which produces a mirror image of an object relative to an axis of reflection. There are three possible axis of reflections: 1. X axis

CHAPTER 1. HOMOGENEOUS TRANSFORMATIONS

20

Figure 1.4: Reflection with respect to the x axis

Figure 1.5: Reflection with respect to the y axis 2. Y axis 3. Z axis (reflection with respect to the origin) X-Axis Reflection with respect to the x axis is shown in Fig. 1.4.  
  x  







1 0 0    x    y
=  0 −1 0  y     1   0 0 1  1  Y-Axis Reflection with respect to the y axis is shown in Fig. 1.5.

(1.13)

1.2. 2-D TRANSFORMATION

21

Figure 1.6: Reflection with respect to the z axis

Figure 1.7: Shear Transformation  
  x  







−1 0 0    x   
y = 0 1 0  y      1  0 0 1  1 

(1.14)

Z-Axis Reflection with respect to the z axis is shown in Fig. 1.6.  
  x  







−1 0 0    x    y
=  0 −1 0  y     1   0 0 1  1  1.2.2.2

Shear

This transformation produces a shape distortion, Fig. 1.7:

(1.15)

CHAPTER 1. HOMOGENEOUS TRANSFORMATIONS

22

Figure 1.8: Scaling With Respect to a Fixed Point with respect to the x axis:  
  x  





1 a 0   x  
y = 0 1 0  y    1   0 0 1  1

    

(1.16)

or with respect to the y axis:  
  x  





1 0 0   x  
y = b 1 0  y    1   0 0 1  1

1.2.3

    

(1.17)

Composite Transformations

Any sequence of transformations can be represented as a composite transformation by calculating the product of the individual transformation matrices. Forming products of transformation matrices is called concatenation or composition of matrices. Note that in general those operations are NOT commutatives. Following is one example of composite transformations. 1.2.3.1

Scaling Relative to a Fixed Point

If an object is to be scaled relative to a fixed point P (xp , yp ) by sx and sy , then this operation can be performed through the following sequence, Fig. 1.8: 1. Translate such that P is at the origin: 



1 0 −xp    0 1 −yp  0 0 1

(1.18)

1.3. 3-D TRANSFORMATION

23

2. Scaling





sx 0 0    0 sy 0  0 0 1 3. Translate back



(1.19)



1 0 xp    0 1 yp  0 0 1

(1.20)

When concatenated those operations will yield the following transformation matrix: 



sx 0 −xp (1 − sx )    0 sy −yp (1 − sy )  0 0 1 1.2.3.2

(1.21)

Rotation about an Arbitrary Point

Rotation about an arbitrary point P1 is achieved by: 1) Translate such that P is at the origin, 2) Rotate, and 3) Translate back. This would yield the following transformation matrix: 

 

 



1 0 xp cos θ − sin θ 0 1 0 −xp       (1.22) T (xp , yp ) · R(θ) · T (−xp , −yp ) =  0 1 yp  ·  sin θ cos θ 0  ·  0 1 −y p  0 0 1 0 0 1 0 0 1 



cos θ − sin θ xp (1 − cosθ) + yp sinθ   =  sin θ cos θ yp (1 − cosθ) − xp sinθ  0 0 1

1.3

3-D Transformation

The representation of 2-D transformations as 3x3 matrices has a parallel for 3-D transformations, which are represented as 4x4 matrices.

1.3.1

Translation

Translation of an object in 3-D by tx , ty , and tz , is achieved through:    

T =

1 0 0 0

0 1 0 0



0 tx 0 ty    1 tz  0 1

(1.23)

CHAPTER 1. HOMOGENEOUS TRANSFORMATIONS

24

1.3.2

Scaling

Scaling of an object in 3-D by sx , sy , and sz , is achieved through:    

S=

sx 0 0 0 sy 0 0 0 sz 0 0 0

0 0 0 1

    

(1.24)

Where the scaling is with respect to the origin. If scaling is to be performed with respect to another point, than a translation must first be performed.

1.3.3

Rotation

X-Axis Rotation about the x-axis in 3-D by an angle θ,    

RX = 

1 0 0 0 cos θ − sin θ 0 sin θ cos θ 0 0 0

0 0 0 1

    

(1.25)

Y-Axis Rotation about the y-axis in 3-D by an angle θ,    

RY = 

cos θ 0 − sin θ 0

0 sin θ 0 1 0 0 0 cos θ 0 0 0 1

    

(1.26)

Z-Axis Rotation about the z-axis in 3-D by an angle θ,    

RZ = 

1.3.4

cos θ − sin θ sin θ cos θ 0 0 0 0

0 0 1 0

0 0 0 1

    

(1.27)

Reflection

This class of transformations produces coordinate reflections about a specified reflection plane. Three-dimensional reflection matrices are set up similarly to those for two dimensions. A particularly useful reflection matrix, is the one which transforms a right handed coordinate system to a left handed one (needed later for three dimensional viewing transformations), Fig. 1.9.    x
     y
   z
      

1

   

=

1 0 0 0

0 0 0 1 0 0 0 −1 0 0 0 1

   x       y     z       

1

(1.28)

1.4. COORDINATE VS GEOMETRIC TRANSFORMATION

25

Figure 1.9: Conversion of a Coordinate System from Right-handed System to Left-handed System

1.3.5

Shear

Just as in two-dimensional coordinate systems, various shears can be defined in three dimension. In the following example, Fig. 1.10:    

SH = 

1 0 0 0

0 shx 1 shy 0 1 0 0

0 0 0 1

    

(1.29)

produces a z-axis shear. Its effect is to alter the x and y coordinate values by an amount that is proportional to their z value, while z is left unchanged.

1.4 1.4.1

Coordinate vs Geometric Transformation Coordinate Transformation

So far we have discussed transformations within a given fixed coordinate system. Thus the coordinate system remains fixed, and the object is transformed with respect to the origin. An alternative and equivalent way of considering this problem is to look at it as a set of coordinate transformation. This approach is more adequate when multiple objects are each defined in their own coordinate systems and there is a need to integrate them into a single graphical display (as will be the case with PHIGS where individual object may have their own modeling coordinate system). Let us define an arbitrary point P (i) in coordinate system i. The same point in coordinate system j will be denoted by P (j) , and we will define the coordinate transformation that converts P from P (j) to P (i) as CTi←j . Thus we have: P (i) = CTi←j · P (j)

(1.30)

CHAPTER 1. HOMOGENEOUS TRANSFORMATIONS

26

Figure 1.10: Shearing of a Unit Cube By extension, we could have: P (i) = CTi←j · CTj←k · P (k)

(1.31)

CTi←k = CTi←j · CTj←k

(1.32)

or For instance, if coordinate system j has its origin at O(7,3) with respect to coordinate system i, and if xj makes an angle of π/2 with respect to xi , and finally if the unit vector of j is half the unit vector in i, then : CTi←j = T (7, 3) · R(π/2) · S(1/2, 1/2)

(1.33)

yielding: 

CTi←j

 

 



1 0 7 0 −1 0 1/2 0 0       =  0 1 3  ·  1 0 0  ·  0 1/2 0  0 0 1 0 0 1 0 0 1 







(1.34)

0 −1/2 7   0 3  =  1/2 0 0 1 and we have:







0 −1/2 7     6    4    = 0 3  2 5  1/2     0 0 1  1   1 

(1.35)

−1 = (T (7, 3) · R(π/2) · S(1/2, 1/2))−1 CTj←i = CTi←j

(1.36)

Finally we note that:

= S(2, 2) · R(−π/2) · T (−7, −3)

1.5. EFFICIENCY CONSIDERATIONS

27

Figure 1.11: Geometric vs Coordinate Transformation

1.4.2

Coordinate vs Geometric Transformation

With reference to Fig. 1.11, we have a house defined in coordinate system i, and we would like to have its control point at the origin. This can be achieved by either: 1. A Geometric transformation of T (−xp , −yp ) within a fixed coordinate system. 2. A Coordinate transformation from xi − y i to xj − y j with the house remaining fixed. This is accomplished through CTj←i = T (−xp , −yp ). We note that CTi←j = T (−xp , −yp )−1 = T (xp , yp ).

1.4.3

Equivalent Geometric Transformation in Different Coordinate Systems

Given a geometric transformation Qi in i which transforms P into P
(P
= Qi .P ), we seek to determine the equivalent one Qj in j, Fig. 1.12. which transforms P into P
. Qj · P j Q · CTj←i P j

i

= CTj←i · Qi · P i

(1.37)

= CTj←i · Q · P

(1.38)

i

i

−1 Qj = CTj←i · Qi · CTj←i

1.5 1.5.1

(1.39)

Efficiency Considerations Matrix Operations

The most general 2D transformation can be written as:  
  x  





rs11 rs12 tx   x  
y =  rs21 rs22 ty  y    1   0 0 1  1

    

(1.40)

CHAPTER 1. HOMOGENEOUS TRANSFORMATIONS

28

Figure 1.12: Equivalent Geometric Transformation Note that the rs terms account for rotation and scaling, while the t terms account for translation only. This matrix operation requires 9 multiplications and 4 additions. On the other hand, if the special form of the matrix is recognized: x
= rs11 .x + rs21 .y + tx y




= rs12 .x + rs22 .y + ty

(1.41) (1.42)

then only 4 multiplications, and 4 additions would be required. Some customized hardware microprocessors take advantage of this reduction in the number of operations.

1.5.2

Dynamic Rotation

In some applications where an object is to be continuously rotated (to simulate dynamic appearance) the rotation operation will require four multiplications (with trigonometric functions which are computationally expensive) and two additions. This can be improved by recognizing that because θ is small (we are creating successive displays in which an output primitive is being rotated by a small amount) then cos θ  1, and sin θ  θ, thus we would have: x
= x − yθ


y = xθ + y

(1.43) (1.44)

Note that this will not only reduce the number of operations, but would also avoid the evaluation of the trigonometric functions (usually done through a Taylor’s expansion, thus very slow).

1.5.3

Block Transfers in Raster Devices

In raster displays the picture is stored by setting bits in the frame buffer. Thus some simple transformations can be carried out by simply manipulating portions of the frame buffer.

1.5. EFFICIENCY CONSIDERATIONS

29

This will result in very few arithmetic operations, and is thus a very efficient method. Some of the available operations include: 1. Transfer of a block. 2. Transfer and rotation (by 90 degrees increment) of blocks. 3. Boolean operations with previous content of the newly addressed portion of the frame buffer. Block transfers (also known as bit-block transfers) form the basis of many animation (and games) implementations. Note that Bit-Block transfer is not supported by neither GKS nor PHIGS

30

CHAPTER 1. HOMOGENEOUS TRANSFORMATIONS

Chapter 2

3D ANALYTIC GEOMETRY for COMPUTER GRAPHICS In this chapter we shall briefly review some basic concepts of analytic geometry which can be of direct practical usefulness in Computer Graphics. In some cases, traditional formulations, to which we may have been too accustomed, are altered by more appropriate ones for a computational (rather than algebraic) environment. With one initial exception, we shall consider three dimensional cases, of which the two dimensional one is a special case.

2.1

Parameteric Representation

The mathematical representation of any curve (or surface) can be: 1. Non-Parametric if we have a direct relationship between all the coordinates of any point along the curve (or inside the surface). This is the approach with which we are most familiar, and is usually most appropriate for algebraic manipulation, but unappropriate in a computational environment. Again non-parametric representation can be: (a) Explicit y = f (x). For example in 2D there can be only one value of y for each value of x, i.e.  (2.1) y = 1 − x2 for one quadrant of a circle. (b) Implicit f (x, y) = 0 which can represent multi-valued expressions (such as a circle) but the determination of a point on a segment would require the solution of an algebraic equation, i.e. x2 + y 2 − R 2 = 0

(2.2)

2. Parametric form in which each coordinate is a function of one (for curves) or two (for surfaces) parameters. 31

32

CHAPTER 2. 3D ANALYTIC GEOMETRY FOR COMPUTER GRAPHICS (a) Lines: The parametric equation of a line passing through P1 and P2 is given by: (1 − t)P1 + tP2 (2.3) If 0 ≤ t ≤ 1, than the point lies on the line somewhere between P1 and P2 . (b) Curves: x = f (t)

y = g(t)

z = h(t)

(2.4)

For instance, the parametric equation of a unit circle is: 

P (t) =



cos t sin t

(2.5)

Alternative forms include: 

P (t) = 

P (t) = 

P (t) =

1−t2 1+t2

2t 1+t2



t (1 − t2 )1/2

(2.6) 

0.43t3 − 1.466t2 + 0.036t + 1 −0.43t3 − 0.177t2 + 1.607t

(2.7) 

(2.8)

This last equation is an approximation. (c) Surface: x = f (t, u)

y = g(t, u)

z = h(t, u)

(2.9)

Following is an example of the parametric definition of a spherical surface in which two parameters must be used: x(t, u) = r. sin(πt). cos(2πu)

(2.10)

y(t, u) = r. sin(πt). sin(2πu)

(2.11)

z(t, u) = r. cos(πt)

(2.12)

The main disadvantage of the parametric representation is that coordinates are not directly computed as in the explicit case. As it can be seen there is usually more than one possible parametric representation of a curve, and the equations are usually normalized such that the parameters vary between 0. and 1. In computer graphics parametric representation is almost exclusively used.

2.2

Some Useful Relations

In computer graphics, it is often necessary to evaluate certain simple relations between points, lines, and surfaces. In the following section we shall list some of the most important ones. Those relations are written for the most part as vector operations. Thus it is understood that given p1 ≡ (x1 , y1 , z1 ) and p2 ≡ (x2 , y2 , z2 ), we can define a

2.2. SOME USEFUL RELATIONS

33

1. scalar multiple k of p1 by multiplying its three individual co-ordinates by k, or kp ≡ (k · x1 , k · y1 , k · z1 )

(2.13)

2. vector sum of p1 + p2 is calculated by adding the three respective coordinates: p1 + p2 = (x1 + x2 , y1 + y2 , z1 + z2 )

(2.14)

3. dot product (or scalar product) of two vectors p and q as the scalar: p · q = (x1 , y1 , z1 ) · (x2 , y2 , z2 ) = x1 · x2 + y1 · y2 + z1 · z2

(2.15)

4. Norm of a vector is defined as: |p| =



x2 + y 2 + z 2

(2.16)

5. cross product defined as: n=p×q

(2.17)

where the components of the n vectors can be found from the partial determinants of:   i j k   (2.18)  px py pz  qx qy qz that is:

  p  nx =  y  qy

pz qz

    

(2.19)

or n x = py · q z − q y · pz Similarly,

  p  ny = −  x  qx

pz qz

    

(2.20)

(2.21)

or ny = −px · qz − qx · pz   p  nz =  x  qx

 px   qy 

(2.22) (2.23)

or n z = px · q y − q x · py Note that vector n is normal to both p and q.

(2.24)

34

2.2.1

CHAPTER 2. 3D ANALYTIC GEOMETRY FOR COMPUTER GRAPHICS

Angle Between Two Direction Vectors

If p and q are two unit vectors, and θ is the angle between them, then we have cos θ = p · q, or in the general case when p and q are not unit vectors, we have: θ = cos−1



p |p|

·

q |q|



(2.25)

Thus if p and q are mutually perpendicular directions, we have p · q = 0.

2.2.2

Definition of a Line

A line is defined in terms of a point b through which the line is known to pass, and a direction d: P(t) = b + td (2.26) Note that P ≡ (x, y, z) 2.2.2.1

Example

Describe the line joining (5, 6, 8) to (4, 7, 12) P(t) = (5, 6, 8) + t(4 − 5, 7 − 6, 12 − 8)

(2.27)

P(t) = (5, 6, 8) + t(−1, 1, 4)

(2.28)

Note that the direction cosines are given by 1 4 −1 (√ , √ , √ ) 18 18 18

2.2.3

(2.29)

Definition of a Plane

In a three dimensional space, a plane can be defined by an arbitrary point a and the plane ˙ normal nThus any arbitrary line on the plane connecting point a and an arbitrary point P ˙ must be normal to nThus: n · (P − a) = 0 (2.30) or n · P =  k

(2.31)

n·a

2.2.4

Intersection of a Line and a Plane

Given the line b + td and the plane n · P = k we have to find the value of t (assuming that one exists) for which: (2.32) n ·(b + td) = k 

 P



2.2. SOME USEFUL RELATIONS

35

or after substitution: k−n·b n·d

t=

(2.33)

assuming n · d = 0 (otherwise the line and the plane are parallel, and there is an infinite number of solutions).

2.2.5

Distance from a Point and a Plane

The distance of a point p1 from a plane n · P = k is equal to the distance between p1 and p2 where p2 is the nearest point on the plane, the normal through which must pass by p1 . This normal can be written as p1 + tn and the t value which defines p2 is found from Eq. 2.33 (with b = p1 and d = n) to be: k − n · p1 n·n

t=

(2.34)

The distance is finally given by: d = |p2 − p1 | = | p1 + tn − p1 | = |tn| = t|n| 





p2

(2.35)

Finally when substituting with Eq. 2.35 we get: d= 2.2.5.1

|k−n·p1 | |n|

(2.36)

Example

Find the point of intersection of the line joining (1, 2, 3) to (−1, 0, 2) with the plane (0, −2, 1)· P = 5, and also find the distance of the plane from the origin. p1 ≡ (1, 2, 3) (2.37) bp2 ≡ (−1, 0, 2) n ≡ (0, −2, 1) d ≡ (−1, 0, 2) − (1, 2, 3) ≡ (−2, −2, −1) n · d = ((0)(−2) + (−2)(−2) + (1)(−1)) = 3 n · p1 = ((0)(1) + (−2)(2) + (1)(3)) = −1 Thus the t value of the point of intersection is k



n·p1

  

5 − (−1) =2 3 

(2.38)

n·d

and the point vector√is (1, 2, 3) + 2(−2, −2, −1) ≡ (−3, −2, 1) and the distance from the 5 = √55 = 5. origin is |n|

36

2.2.6

CHAPTER 2. 3D ANALYTIC GEOMETRY FOR COMPUTER GRAPHICS

Intersection of Two Lines

Given two lines: b1 + td1 and b2 + sd2 their intersection exists only if they are coplanar and not parallel. Thus the coordinates of their point of intersection can be found by satisfying the following (three) equations: b1 + td1 = b2 + sd2

(2.39)

Note that we have three equations with 2 unknowns(s and t). Thus one of the equation is linearly dependent of the two others, a consequence of the constraint that both lines must be coplanar. 2.2.6.1

Example 1

Find the point of intersection (if any) of: (1, 1, 1) + s(2, 1, 3) with (0, 0, 1) + t(−1, 1, 1) 1 + 2s = 0 − t

(2.40)

1+s=0+t

(2.41)

1 + 3s = 1 + t

(2.42)

Solving for s and t from the first two equations, we obtain s = −2/3 and t = 1/3. Those values are incompatible with the third equation, thus the two lines do not intersect. 2.2.6.2

Example 2

Find the point of intersection (if any) of (2, 3, 4) + s(1, 1, 1) with (−2, −3, −4) + t(1, 2, 3). 2 + s = −2 + t

(2.43)

3 + s = −3 + 2t

(2.44)

4 + s = −4 + 3t

(2.45)

Solving for s and t from the first two equations, we obtain s = −2 and t = 2, those values are compatible with the last equation, thus the point of intersection is: (2, 3, 4) + (−2)(1, 1, 1) = (0, 1, 2)

2.2.7

(2.46)

Shortest Distance Between Two Lines

As previously mentioned, if two lines are either parallel or co-planar, then there exists a minimum distance between them. 2.2.7.1

Non-Parallel Case

Assuming the two lines to be a + tc and b + sd, the minimum distance between them must be measured along a line which is perpendicular to both of them, therefore this line must be parallel to the direction defined by l ≡ c × d. Thus each of those two lines can

2.2. SOME USEFUL RELATIONS

37

define a (separate) plane with normal l. Furthermore, since we know points a and b we can uniquely define those two planes as: l · (P − a) = 0 ⇒ l · P =  l·a

(2.47)

k

l · (P − b) = 0

(2.48)

Obviously those two planes are parallel, and the required minimum distance between them is equal to the distance between an arbitrary point on one plane, say b to the other one. Such a formula has already been previously defined in Eq. 2.36, and upon substitution would yield: 

k





l

l=n

  

d=

p1

   

| (c × d) ·a − (c × d) · b | |c × d|

(2.49)

   l=n

or d= 2.2.7.1.1 t(1, 2, 3).

Example

|(c×d)·(a−b)| |c×d|

(2.50)

Find the minimum distance between (1, 0, 0)+s(1, 1, 1) and (0, 0, 0)+ a ≡ (1, 0, 0) b ≡ (0, 0, 0) (a − b) = (1, 0, 0) c ≡ (1, 1, 1) d ≡ (1, 2, 3) c × d ≡ (1, −2, 1) 1 |(1, −2, 1) · (1, 0, 0)| =√ d = |(1, −2, 1)| 6

2.2.7.2

Parallel Lines

If the two lines are coplanar and nonparallel, then the previous equation would yield a zero distance because the lines must intersect. Now assuming a + tc and b + sd to be parallel, both lines are normal to the same plane. Taking the plane containing a with normal c (parallel to d): c · (P − a) = 0 (2.51) we simply find the point of intersection, e, of the line b+sd with this plane and the required distance is (from Eq. 2.33) |a − e|, with: e = b + sd

(2.52)

where k



−c·b s= c·a c·d

(2.53)

CHAPTER 2. 3D ANALYTIC GEOMETRY FOR COMPUTER GRAPHICS

38 2.2.7.2.1 t(2, 2, 2).

Example

Find the minimum distance between (2, 4, 0)+s(1, 1, 1) and (−2, −1, 0)+

a ≡ (2, 4, 0) c ≡ (1, 1, 1) b ≡ (−2, −1, 0) d ≡ (2, 2, 2) c × d = (0, 0, 0)RightarrowThe lines are parallel(d = 2c) c·d = 6 a − b = (4, 5, 0) 3 (1, 1, 1) · (4, 5, 0) = t = 6 2 3 e = (−2, −1, 0) + (2, 2, 2) = (1, 2, 3) 2 a − e = (2, 4, 0) − (1, 2, 3) = (1, 2, −3) √ √ 1 + 4 + 9 = 14 |a − e| =

2.2.8

Plane Through Three Non-Collinear Points

Given three non-collinear points p1 , p2 , and p3 , then the two vectors p2 − p1 and p3 − p2 are two lines which fully define the plane. Thus the normal to the plane is n ≡ (p2 − p1 ) × (p3 − p2 )

(2.54)

Thus the equation of the plane can be written as: ((p2 − p1 ) × (p3 − p2 )) · (P − p1 ) = 0

(2.55)

Note that those three points define a triangle which appears to be clockwise from one side, and counter-clockwise from the other. The above equation is defined in such a manner that the normal direction points towards that side of the plane from which the triangle appears in a counter-clockwise orientation (assuming a right handed coordinate system is used). 2.2.8.1

Example

Define the plane which goes through the following three points: (0, 1, 1), (1, 2, 3), (−2, 3, 1).

2.2.9

(((1, 2, 3) − (0, 1, 1)) × ((−2, 3, 1) − (1, 2, 3))) · ((x, y, z) − (0, 1, 1)) = 0

(2.56)

(−6, −2, 4) · P = 2

(2.57)

Point Of Intersection of Three Planes

Given three planes defined by: n1 · P = k1

(2.58)

2.2. SOME USEFUL RELATIONS

39 n2 · P = k2

(2.59)

n3 · P = k3

(2.60) (2.61)

where ni ≡ (ni1 , ni2 , ni3 ) we can rewrite those equations as:  



 n1x n1y n1z  x   y  n2x n2y n2z  ·   z n3x n3y n3z

    

    k1  

=

k

2   k   3

(2.62)

Solving for P we obtain:     x  

 −1    k1  



n1x n1y n1z   =  n2x n2y n2z  y    z  n3x n3y n3z

·

k

2   k   3

(2.63)

Thus a 3 by 3 matrix has to be inverted. 2.2.9.1

Example

Find the point of intersection of the three planes:



(0, 1, 1) · P = 2

(2.64)

(1, 2, 3) · P = 4

(2.65)

(1, 1, 1) · P = 0

(2.66)

 







   0 1 1  x   2     = y 4  1 2 3 ·      1 1 1 z   0 

(2.67)

Solving, we obtain P = (−2, 0, 2).

2.2.10

Line Intersection of Two Planes

Given the following two planes: p · P ≡ (p1 , p2 , p3 ) · P = k1

(2.68)

q · P ≡ (q1 , q2 , q3 ) · P = k2

(2.69)

and assuming the planes to be non-parallel, p = sq for any value of s. The line of intersection must be perpendicular to the normals of the two planes (p and q). Thus the direction of this line must be d ≡ p × q and it can be written as b + td where b is any point on the line. Then we have to find a point which is along the intersection of those two planes as the direction has been determined from d. This point can be found at the intersection of those two planes with a third one which normal is given by p × q. Finally, we still need a

CHAPTER 2. 3D ANALYTIC GEOMETRY FOR COMPUTER GRAPHICS

40

value for k3 , since any value will do we take it to be equal to 0 assuming the third plane to go through the origin. Thus b is given (from Eq. 2.63) by:  −1    k1  



p1 p2 p3   q1 q2 q3 b=  p2 · q 3 − p3 · q 2 p3 · q 1 − p1 · q 3 p1 · q 2 − p2 · q 1 2.2.10.1

·

k

2   0  

(2.70)

Example

Find the line of intersection between the following two planes: (0, 1, 1) · P = 2

(2.71)

(1, 2, 3) · P = 2

(2.72)

p = (0, 1, 1)

(2.73)

q = (1, 2, 3)

(2.74)

p × q = (1, 1, −1) 

0 1 1   b =  1 2 3  1 1 −1



=

(2.76)



−5 2 1 1   4 −11  3 −1 1 −1

(2.77)

    x  

y

  z  

2.3

(2.75)

−1



=



 −5 2 1  2 1  4 −11 2    3  −1 1 −1 0

    

    −2  

=

2

  0  

Data Representation of 3D Objects

Data representation of 3D objects can be decomposed into two distinct parts: 1. Geometrical. 2. Attributes.

2.3.1

Geometrical

By extension to the 2D case, a 3D object can be mathematically defined as: 1. Explicit polygon mesh. 2. Explicit edge mesh.

(2.78)

2.3. DATA REPRESENTATION OF 3D OBJECTS 2.3.1.1

41

Explicit Polygon Mesh

In an explicit polygon definintion, the: 1. Object is first defined in terms of Facets, usually (but not necessarily) assumed to be planar polygon. The facet indices defining a 3D solid, can be stored in a one dimensional array. 2. Facets are in turn defined by their Vertices. As a facet may have a variable number of vertices, the most efficient storage scheme for this data-base is through a linear list of three arrays. (a) First a large array of integers, IFAC(1...MAXIF), contains the list of indices of vertices of all the facets, appended one after the other. MAXIF is the size of the array, and is thus the maximum number of total indices to vertices which can be stored. (b) A pointer array ISTART(I...MAXF) which points to the cell in IFAC preceding the first vertex of facet I, thus ISTART(1)=0. (c) An array ISIZ(1...MAXF) which stores the number of vertices on the boundary of facet I.1 Thus the indices of the vertices of facet I are given in the ordered values IFAC(ISTART(I)+1), IFAC(ISTART(I)+2), ...., IFAC(ISTART(I)+ISIZ(I)). Finally an integer variable LAST indicates the position within IFAC of the last vertex of the last facet. 3. Vertices are finally defined in terms of their coordinates. Each of the 3 cartesian coordinates of the vertices can be stored in a one dimensional array. The advantage of this data representation is that it makes it very easy to alter the coordinates of one vertex, delete add and alter individual polygons. The main disadvantage is that if all the polygons sharing a specified edge or vertex are to be found, then all the polygons must be searched. Futhermore most edges are drawn twice. 2.3.1.2

Explicit Edge Mesh

This is an alternative representation which overcomes most of the disadvantages of the preceding one which uses three arrays: 1. The first array stores all the vertices (3) coordinates. 2. The second array stores all the edges in the mesh. 3. The thirs array stores all the edges of individual polygons. 1

Note that entries of this array can be indirectly recovered from the previous one.

CHAPTER 2. 3D ANALYTIC GEOMETRY FOR COMPUTER GRAPHICS

42

2.3.2

Attributes

Each facet may have different attributes. Those attributes can be: 1. Color, usually determined to account for shading. 2. Order of display, useful in the “painter’s” algorithm for hidden surface removal.

Chapter 3

THREE DIMENSIONAL PROJECTIONS 3.1 3.1.1

Introduction Definition

A transformation from an N dimensional space into N-1 is called projection.

3.1.2

Historical Background

For centuries, painters, designers, drafters, cartographers, architects, and engineers have tried to come to terms with the difficulties and constraints imposed by the problem of representing a three-dimensional object or scene into a two dimensional medium for their painting, drawings, maps, plans, or computer display. The history of projective geometry as a practical science can be traced back as far as 2150 B.C. to a floor plan view of a building carved on a stone table, which is part of a statue of King Gudea of the city of Lagash in Mesopotamia. The Egyptians, although displaying no sense of perspective in their art, must have also used plan views of their engineering and architecture. Later architects in the greek antiquity displayed some sort knowledge of perspective. But this was an applied science, and Greek mathematicians took a dim view of applied science; thus while the Greeks devoted much effort to an axiomatic development of Euclidian geometry, projective geometry remained a collection of rules of thumb used by artists, architects, and builders. The major contribution of the Romans came in around 14 B.C. with the publication of De Architectural by Vitruvius; However it would eventually take 1200 years until the beginning of the Italian Renaissance for projective geometry, in the form of perspective, to flourish through the efforts of Brunelleschi, Alberti, and Da Vinci (who wrote a Treatise on Painting in which he stressed the importance of the scientific method and mathematical principles). In the early sixteenth century, the German artist and Mathematician D¨ urrer traveled to Italy to learn perspective and succeeded in improving on what he learned (through his numerous well known etching work). In the seventeenth century Desargues and his student Pascal initiated a systematic study of perspective. This study contributed largely to the development of synthetic projective geometry but was 43

CHAPTER 3. THREE DIMENSIONAL PROJECTIONS

44

overshadowed at the time by the invention of Cartesian coordinates by Descartes and the related study of Euclidian geometry. From an Engineering approach, it is a french military Engineers Monge (1746-1818) who is the “father” of descriptive geometry. He first suggested to replace the lengthy calculations with graphical constructions in his book An Introduction to Perspective and Projective Geometry. At first his methods were rejected by his superiors, but later accepted and considered as “military secret” for a number of years. Finally it was Poncelet who in the nineteenth century started the systematic axiomatic study of projective geometry. While many books, and treatises have been written on this subject, they deal with graphical representations which are not particularly suited for mathematical modeling on a computer.

3.1.3

Projections and Graphics Standards

Two conflicting approaches are possible for the implementation of three dimensional projections in computer graphics: • A simple set of viewing parameter definition, but which may be inefficient (simple alteration of some parameters will require the complete regeneration of the display). • A relatively complex set of viewing parameters, but which lends itself to a very efficient usage of computer resources. The second approach was selected by CORE and then by GKS3D and PHIGS. Note that eventhough “standard” GKS is 2D, this limitation does not prevent the display of 3-D objects provided the application program includes a set of procedures for the selected projections.

3.1.4

Types of Projections

A projection transforms a point in a coordinate system of dimension n into one in a coordinate system of dimension less than n. In our case we are projecting a point from 3D space to 2D space. In general projection is achieved by defining projectors (linear or curvilinear projection rays) emanating from a center of projection, passing through each point (or vertex) of an object, and intersecting a projection plane (planar or curved). If the projectors are straight, and the projection plane is planar, then we have a planar geometric projection. As in swch a projection lines are preserved, we need to transform only endpoints of each line. Note that in cartography, nonplanar and nongeometric projections are extensively used.

3.2

Planar Geometric Projections, Definitions

Planar geometric projections, used almost exclusively in computer graphics for the display of 3D objects, can be subdivided into 2 categories: Perspective and Parallel.

3.2. PLANAR GEOMETRIC PROJECTIONS, DEFINITIONS

45

Figure 3.1: Perspective Projection

3.2.1

Perspective Projections

In a perspective projection, the distance between the center of projection to the projection plane is “finite”, Fig. 3.1. Thus a perspective projection is uniquely characterized by: 1. Center of Projection, COP. 2. Projection Plane, or Projection Plane Normal, PPN. Perspective projections are used primarily for “realistic” displays of objects and is thus the projection used by painters, and artists (engineers use the parallel projection for reasons discussed below). 3.2.1.1

Characteristics

Following are some of the characteristics of the perspective transformation: 1. Realism of projection as it is very similar to the human visual system. 2. Perspective foreshortening causes the size of an object to vary inversely with the distance from the center of projection. 3. Topological Distortion, as a result of the above, distances are not correctly transformed, angles are not preserved (except those on planes parallel to the projection plane), and parallel lines do not project as parallel ones (with the same exception as for angles). 4. View Confusion: If the center of projection is between the object and the plane of projection, than the object is projected upside down and backward (as in a photographic camera) 5. Vanishing Points Projections of lines that are not parallel to the projection plane appear to meet at some point on the view plane (best example is the illusion that railroad tracks meet at a point on the horizon). Each set of projected parallel lines will have its own vanishing point.

CHAPTER 3. THREE DIMENSIONAL PROJECTIONS

46

Figure 3.2: One and Two Point Perspective Projections of a Cube

Figure 3.3: Parallel Projection 3.2.1.2

Categories

Perspective projections are categorized in terms of the number of principal vanishing points. The number of principal vanishing points is equal to the number of principal axis intersected by the projection plane. Thus for a cube (which sides are parallel to the three principal axis), there is one principal vanishing point if the projection plane is normal to the z axis, there would be two if the plane intersected two axis. The one point perspective is seldom used, while the two point perspective is commonly used for architectural, engineering, and advertising drawings, with the vertical lines projecting as parallel and hence not converging, Fig. 3.2. Three point perspective are seldom used, as they are hard to construct and do not add much “realism” beyond the one provided by the two point.

3.2.2

Parallel Projections

In a parallel projection, the center of projection is at infinity, Fig. 3.3. Thus a perspective projection is uniquely characterized by: 1. Direction of (parallel) Projection (DOP). 2. Projection Plane, or projection plane normal (PPN). Parallel projections are primarily used by engineers and drafters to create working drawings of an object which preserve its scale and shape. The complete representation of these details often requires two or more projections of the object into different planes.

3.2. PLANAR GEOMETRIC PROJECTIONS, DEFINITIONS

47

Figure 3.4: Three Orthographic Projections

Figure 3.5: Isometric Projection 3.2.2.1

Categories

While perspective projections are categorized only by their number of principal vanishing points, there are numerous combinations of parallel projections. 1. Orthographic The direction of projection is parallel to the projection plane normal, (PPN is  to DOP), thus only one face of the object can be shown at a time. (a) Multiview The projection plane is parallel to a principal plane. i. Three views of the object from the side, front, and top, Fig. 3.4. ii. Auxiliary views iii. Sectional views cut through the object. (b) Axonometric The projection plane is not parallel to a principal plane, thus more than one face of the object can be shown. i. Isometric The direction of projection makes equal angles with all three principal axis, Fig. 3.5. There are eight possible positions for the projection plane, one in each octant. All three principal axes are foreshortened equally so that relative proportions are maintained, this is usually not the case in general for axonometric projections. ii. Dimetric The direction of projection makes equal angles with two principal axis. iii. Trimetric The direction of projection makes unequal angles with the three principal axis.

CHAPTER 3. THREE DIMENSIONAL PROJECTIONS

48

Figure 3.6: Oblique Projection

Figure 3.7: Cavalier Projection 2. Oblique The direction of projection is not parallel to the projection plane normal. (a) General Fig. 3.6. (b) Cavalier The direction of projection is chosen so that there is no foreshortening of lines perpendicular to the x-y plane (DOP − P P N = 45 deg), Fig. 3.7. (c) Cabinet The direction of projection is chosen so that lines perpendicular to the x-y planes are foreshortened by half their length (DOP − P P N = cot−1 12 ), Fig. 3.8 3.2.2.2

Characteristics

A parallel projection preserves relative dimensions of objects, but does not always yield realistic representation of the appearance of a 3D object. As such it is primarily used for

Figure 3.8: Cabinet Projection

3.3. MATHEMATICS OF PLANAR GEOMETRIC PROJECTIONS

49

Figure 3.9: Perspective Projection engineering drawings.

3.3

Mathematics of Planar Geometric Projections

Having qualitatively defined the various types of projections, it is essential that each one of them be mathematically defined. For simplicity, the following will be assumed: 1. The Plane projection normal is along the z axis of the world coordinate system (that is the projection plane is parallel to the x-y plane). 2. Perspective Projections: (a) Projection plane is at a distance d along the z axis. (b) Center of projection is at the origin. 3. Parallel Projections: Projection plane is at z = 0. Thus points with large values of z are further from the viewer. A simple transformation matrix can transform objects from left to right handed systems. 4. Each one of the projections will be characterized by a homogeneous transformation matrix. 5. For a generalization of the projection (into arbitrary PPN), this homogeneous matrix could be concatenate with others to define an arbitrary 3D view, this will be the object of a separate section.

3.3.1

Perspective Projection

Assuming the PPN to be along the z axis, and the PP to be at z = d, Fig. 3.9 we seek to project point P (x, y, z) into P
(xp , yp , d). Coordinates of P’ can be obtained from: xp d yp d

= =

x x ⇒ xp = z z/d y y ⇒ yp = z z/d

(3.1) (3.2)

CHAPTER 3. THREE DIMENSIONAL PROJECTIONS

50

This can be written in homogeneous coordinate system as follows:    xp      y   p

 zp   

1

   

 x   z/d      y  

=

z/d

 d       

=

 x h     ywh

    

zh     w

   

w

1

1

(3.3)

(note that here w = dz ). Thus:   xh   

    



 yh  = Mper · P =     z h      w 

Note that in some references the PP is at z
this will yield a matrix Mper  1  0 
Mper =  0 0

1 0 0 0



0 0 0  x     1 0 0  y  0 1 0  z   0 1d 0  1

    

(3.4)

   

= 0 with the center of projection at z = −d, 

0 0 0 1 0 0    0 0 0  0 1d 1

(3.5)

This can be obtained by the following transformations:
= T (0, 0, −d).Mper .T (0, 0, d) Mper

(3.6)

Note how concisely can this transformation be mathematically defined using homogeneous coordinates and transformation. In this exampl for the first time we have used a value of W different than 1.

3.3.2 3.3.2.1

Parallel Projection Orthographic

The orthographic projection into the plane at z = 0 is straightforward: xp = x

(3.7)

yp = y

(3.8)

zp = 0

(3.9)

which can be expressed by the following projection matrix:   xh    y h

    

 zh       

w

=

   xp      y   p

 zp       

1

   

= Morth · P = 

1 0 0 0

0 1 0 0

0 0 0 0

0 0 0 1

   x       y     z       

1

(3.10)

3.3. MATHEMATICS OF PLANAR GEOMETRIC PROJECTIONS

51

Figure 3.10: Oblique Projection 3.3.2.2

Oblique

With reference to Fig. 3.10, we seek to project a point P (x, y, z) into P
(xp , yp , 0) xp = x + L cos Φ

(3.11)

yp = y + L sin Φ

(3.12)

Using Φ = 30 or 45 deg we obtain a display of front, side, and top faces. Note that L is a function of z, and can be obtained from: tan α =

1 z = L L1

(3.13)

or L = z · L1

(3.14)

where L1 is an arbitrary length of the projection line from P(x,y,1) to P’(x,y,0) (that is z=1). Thus the oblique transformation can now be rewritten as: xp = x + z(L1 cos Φ)

(3.15)

yp = y + z(L1 sin Φ)

(3.16)

Finally this transformation can be expressed in homogeneous coordinate system as:   xh   

    

   xp      y  



 yh  p = = Mobl .P =   zh      z p         1   1 

1 0 0 0

0 L1 cos Φ 1 L1 sin Φ 0 0 0 0

0 0 0 1

   x       y     z       

(3.17)

1

Note that L1 is an arbitrary value selected by the user. If L1 is taken as zero (thus α = 90 deg) we recover the orthographic projection defined earlier. It should be noted that this oblique projection has a structure similar to that of a z axis shear matrix. In fact the effect of this projection is to shear planes of constant z and project them onto the view plane. The x and y values within each plane of constant z value are shifted by an amount proportional to the z value. Following are two commonly used angles for the oblique projection.

CHAPTER 3. THREE DIMENSIONAL PROJECTIONS

52 3.3.2.2.1

  xh       

3.3.2.2.2

If tan α = 1 (L1 = 1), that is α = 45 deg then we have:

Cavalier

yh zh 1

        

=

   xp      y   p

 zp   

1

   

   

= Mcav .P = 

1 0 0 0

0 cos Φ 0 1 sin Φ 0 0 0 0 0 0 1

   x     y       z       

(3.18)

1

Cabinet If tan α = 2 (L1 = 12 ), that is α = 63.4 deg then we have:   xh    y h

    

 zh       

=

1

   xp      y   p

 zp       

   

= Mcab .P = 

1

1 0 0 0

0 1 0 0

1 2 cos Φ 1 2 sin Φ

0 0

0 0 0 1

   x       y     z       

(3.19)

1

This projection causes lines perpendicular to the viewing surface to be projected at one half their length, and this makes it appear more realistic than the cavalier projection.

3.4

Simple 3D Viewing

The display of three dimensional objects into two dimensional screens will now be addressed by a simple implementation. This implementation is quite simple to understand and implement, however it does not have the versatility and power that the next one will have. This second complex transformation, adopted by PHIGS and GKS3D, will be discussed in the next section. The representation of the object can be performed through the following sequence: 1. Select a world coordinate system. 2. Mathematically define the object. 3. Evaluate the transformation matrix which will: (a) Enable the display of the object from a User’s specified location, along a certain light of sight. (b) Select a given projection, i.e. perspective, parallel. 4. Multiply the column vectors holding the vertices coordinates by the transformation matrix. 5. Display the object.

3.4.1

Observer’s Coordinate System

The object originally defined in the world coordinate system will be observed, Fig. 3.11: 1. From position (EX, EY, EZ) in world coordinate space. This represent the coordinates of the eye.

3.4. SIMPLE 3D VIEWING

53

Figure 3.11: Observer’s Coordinate System 2. Along a direction (DX, DY , DZ). If we are looking at the origin, then DX = −EX, DY = −EY , and DZ = −EZ. 3. With an upright position, i.e the vertical direction is maintained. This assumption has also been called maintaining the vertical. This would constitute the definition of an Observer Coordinate System (OC) which has: 1. The eye as the origin. 2. Direction of view along the negative z axis.1 We shall thus examine the matrix which transforms an object from its original world coordinate system WC to the observer coordinate system, OC. This operation will be performed through the following steps: 1. The coordinate origin is first translated to the point E so that the axis of rotation now passes through the origin. This is done through the following transformation:    

T =

1 0 0 0

0 1 0 0



0 −EX 0 −EY    1 −EZ  0 1

(3.20)

2. The coordinate axis is then rotated about the z axis by an angle α = tan−1 the following transformation:    

RZ = 

cos α − sin α sin α cos α 0 0 0 0

0 0 1 0

0 0 0 1

−DY −DX

by

    

(3.21)

1 A left handed coordinate system would have been more appropriate in this case, as it would maintain a satisfactory x-y system (x horizontal, y vertical), and we will be looking along the positive z axis.

CHAPTER 3. THREE DIMENSIONAL PROJECTIONS

54 which is equivalent to:



RZ =

−DX −DY 0 0 DY −DX 0 0 0 0 a 0 0 0 0 a

1   a

    

(3.22)

where: a2 = DX 2 + DY 2 . 3. The axes are finally rotated about the y axis by an angle β = tan−1 following transformation:    

RY = 

cos β 0 − sin β 0

0 sin β 0 1 0 0 0 cos β 0 0 0 1

a −DZ

by the

    

(3.23)

which is equivalent to: 

RY =

1   b



−DZ 0 −a 0 0 b 0 0    a 0 −DZ 0  0 0 0 b

(3.24)

where b2 = a2 + DZ 2 = DX 2 + DY 2 + DZ 2 . 4. The combination of those three transformations: RY · RZ · T transforms the z axis of the WC into the z axis of the OC. We should note that such a realignment of the z axis could have been achieved through a different pair of rotations. At this point all we have achieved was to align the z axis along the proper direction. However the performed transformations might have “screwed” our viewing coordinates2 and induced spurious torques. As such, and following our earlier assumption, we will have to reorient the y axis (through a rotation about the Z axis) in such a way that it will be vertical (y axis remain vertical). It can be shown that this is achieved through a rotation with respect to the z axis:  ∗ = RZ

1   e

d −c 0 0 c d 0 0 0 0 e 0 0 0 0 e

    

(3.25)

where: d = −b · DX, c = DY · DZ, and e2 = p2 + q 2 . 5. So far we have: 2

As an illustration to “parasitic” twisting which might occur during a series of rotation consider the following experiment. Hold your right arm stiff with the palm facing your body, then lift it to the right of your shoulder, then bring it directly in front of you (at this point the palm faces the floor), and finally bring it back down. You will note that through those three rotations, your arm has twisted, as your palm is now aligned with your body

3.4. SIMPLE 3D VIEWING

55

(a) Located the origin of the new coordinate system at the location of the eye. (b) Aligned the z axis with the viewing direction. (c) Maintained the vertical. ∗ · R · R · T . Without This was achieved through the following transformations RZ Y Z saying anything about the type of projection desired. It is thus at this final stage that we shall select the projection type P r, and concatenate it with our previous transformations resulting in: ∗ ·R ·R ·T M3D = P r · RZ Y Z

3.4.2

(3.26)

Fortran Implementation of a Simple 3D Viewing

Following is a description of a fortran implementation of a simple 3D viewing program (with shading) written by Stephen Weihe, and stored in /bechtel/users/faculty/saouma/Graphics/Samples/3dview.

3.4.3 appli init3d menu3d scceno scmm scdist scvpoi sdisma sdpoly sdsdat sdvdat sextra sreado sscale sscol sshade ssupr stripo sview svupdr vsp vspdam

3.4.3.1 wkid wtype

Subroutine Description controls graphics actions in main menu graphics initialization for vsp, messages and menus creates menus computes centroids and normals of each facet computes matrix multiplication computes distance of centroid to eye-point computes 2D display coordinates computes display matrix (transformation matrix) display of object including light source and located point display of current light coordinates in message area display of current eye-coordinates in message area extracts 3D coordinates of a located point reads object data from external file scales object data to [-1,1] computes colors for facets controls graphics actions in shade menu (light source) shade (light source) update due to relative movement generates coordinate axis controls graphics actions in view menu (eye-point) view (eye) point update due to relative movement control routine for vsp interface between predam and vsp

Common Data workstation identifier workstation type

56 iinp nfdim nvdim ncdim maxcol nfile xo yo zo x y z xn yn zn minint maxint npoi ncon ndis ncol index xwcmin xwcmax ywcmin ywcmax stranx strany stranz scalpa xe ye ze vflag iwflag xd yd zd vmat xv yv xvl yvl xl yl

CHAPTER 3. THREE DIMENSIONAL PROJECTIONS workstation indentifier (input) dimension (max. number) of facets dimension (max. number) of verticies dimension (max. number) of connectivity entries max. number of colors number of input files to be read original x-coordinates (changed!) original y-coordinates (changed!) original z-coordinates (changed!) x-coordinate of centroid of facet y-coordinate of centroid of facet z-coordinate of centroid of facet x-component of normal vector of facet y-component of normal vector of facet z-component of normal vector of facet minimum of color intensity (unscaled) maximum of color intensity (unscaled) pointer for facet into connectivity connectivity order of display of facets color of facet index of facet, determining principal color minimum x-world-coordinate for display maximum x-world-coordinate for display minimum y-world-coordinate for display maximum y-world-coordinate for display scale data: translation in x-direction scale data: translation in y-direction scale data: translation in z-direction scale data: scale factor x-coordinate of eye-point y-coordinate of eye-point z-coordinate of eye-point 0: parallel 1: perspective 0: wire frame 1: shaded image x-component of view direction vector y-component of view direction vector z-component of view direction vector transformation matrix from 3D to 2D x-coordinate for 2D-view y-coordinate for 2D-view x-coordinate for light source for 2D-view y-coordinate for light source for 2D-view x-coordinate for light source in 3D y-coordinate for light source in 3D

3.5. ARBITRARY 3-D VIEWING DEFINITION zl ndispo ndisx ndisy ieunit kolor

z-coordinate for light source in 3D point number of located point x-coordinate of located point in 2D-view y-coordinate of located point in 2D-view unit for error/debug file principal color for shading [0.,6.]

3.4.3.2

Tree Structure

MAIN

--SREADO --FINISH --CURMOD |-SINIT --COLOR --HSVRGB | |-MENU |-APPLI --SSCALE | |-STRIPO | |-SCCENO | |-SSCOL | |-SCDIST | |-SDISMA --SCMM | |-SCVPOI | |-SDPOLY --COLOR ...see | |-SVIEW --SDVDAT | | |-SVUPDR | | |-SSCOL | | |-SCDIST | | |-SDISMA ...see | | |-SCVPOI | | |-SDPOLY ...see | |-SSHADE --SDSDAT | | |-SSUPDR | | |-SSCOL | | |-SCDIST | | |-SDISMA ...see | | |-SCVPOI | | |-SDPOLY ...see | |-COLOR ...see above... |-FINISH ...see above...

3.5 3.5.1

57

above...

above... above...

above... above...

Arbitrary 3-D Viewing Definition Introduction

In our previous discussion of projections, we have assumed: 1. PPN along the z axis for both the perspective and parallel projections.

CHAPTER 3. THREE DIMENSIONAL PROJECTIONS

58

2. A center of projection located at the origin for the perspective projection, and projection plane at a distance d along the +ve z axis. 3. A projection plane at z=0 for the parallel projection. In this section we shall first define a generalized set of viewing coordinate systems, and then we shall see how 3D objects could be viewed throught this framework. This viewing coordinate system is the one originally used by CORE and then adopted by GKS3D, and PHIGS. In each case, we shall see how those projections can be combined with simple transformations in order to achieve a completely arbitrary 3D viewing. Generating a view of a 3D object is analogous to photographing it. We can walk around the object and take a picture at any angle, at various distances, with different camera orientation, and different lenses. Whatever appears in the viewfinder will be projected onto the flat film surface. It is this basic and fundamental idea, called the synthetic camera that was incorporated originally in CORE and which was subsequently adopted by both GKS3D and PHIGS. In this approach we will be asking the user to specify: 1. Viewing Coordinate System defined in terms of: (a) View Plane, defined itself in terms of: i. View Reference Point (VRP), i.e eye’s or camera’s position ii. View Plane Normal (VPN), i.e direction of viewing (b) View Up (VUP), i.e orientation of head or camera 2. Type of projection, and its characteristics: (a) Center of Projection (COP) for perspective projections. (b) Direction of Projection (DOP) for parallel projections. 3. View Volume: (a) Projection window defined in terms of the viewing coordinate system. (b) View volume bounds for: i. Perspective ii. Parallel (c) Truncated View Volumes Note that this approach can be considered to be an extension or generalization of the preceding approach.

3.5. ARBITRARY 3-D VIEWING DEFINITION

59

Figure 3.12: View Reference Point and View Plane Normal Definition

3.5.2

Viewing Coordinate System

In order to use the previously defined homogeneous transformation matrices for projection, and in light of the assumptions used for their definition, we have to define a local viewing coordinate system. This (xv , yv , zv ) coordinate system (also referred to as u − v − VPN in CORE) will be the one used for the projection which would take place along its z axis. The viewing coordinate system will be uniquely defined in terms of: 1. View Plane: First an arbitrary view plane on which the projection will take place is to be uniquely defined. Note that the view plane is the CORE term for what was earlier defined as the projection plane. We can think of it as the thin film inside a camera which has already been located and oriented for a shot. The view plane will be defined in terms of: (a) View Reference Point (VRP) The first step in the definition of the view plane (or projection plane) is to define an arbitrary point in that plane in world coordinate system, this point will be called the view reference point, VRP(xvrp , yvrp , zvrp ) and will be the origin of the viewing coordinate system. (b) View Plane Normal (VPN) As an infinite number of planes can cross a point, the view plane will be uniquely defined in the second step by specifying the view plane normal vector. This vector, VPN(xvpn , yvpn , zvpn ) (in world coordinates) will define the z axis used in the viewing coordinate system to be introduced later. Note that only the direction of this vector is relevant, its length can be arbitrary, Fig.3.12. 2. View Up (VUP): As there can be an infinite number of x-y coordinate systems on the view plane, all orthogonal to the VPN, a unique viewing coordinate system definition would require an additional information, this will be provided by the view up vector defined below. The view up, VUP(xvup , yvup , zvup ) vector, defined in world coordinate system, gives the direction of the “up” vector. It is the projection of this vector onto the view plane which will determine the v (or yv ) direction. Its choice is dictated by the “rotation” of the camera (or of your neck!). In most cases it is along the z direction of the world coordinate system, Fig. 3.13.

CHAPTER 3. THREE DIMENSIONAL PROJECTIONS

60

Figure 3.13: u-v-VPN, or xv , yv , zv Coordinate System

3.5.3

Projection Characteristics

Perspective: For perspective projections, the Center of Projection (COP) is defined in world coordinates relative to the view reference point (VRP). Parallel: For parallel projections, the Direction of Projection (DOP) is defined in world coordinates.

3.5.4

View Volume

By analogy to the window defined in 2D, with respect to which all objects outside it were clipped (not displayed), a view volume must be defined in 3D. Only those objects within the view volume will be displayed. An example of a view volume may be the interior room of a building mathematically defined. The view volume definition is defined in the following order: 1. Projection window on the view plane using the viewing coordinate system. 2. clipping planes for the front and back. Once the viewing volume has been defined, than it can be normalized into a Canonical viewing volume to facilitate the clipping operations. 3.5.4.1

Projection Window

In the camera analogy, the focal length of the camera used is an important factor which determines how much of the scene is caught on the film, or how much should the camera “zoom” into the object. In three-dimensional viewing, a projection window is used for the same effect. The window is defined with respect to the viewing coordinate system (or u-v-VPN) system, Fig. 3.14. Note that this is probably the “trickiest” aspect of the viewing parameter definitions, as we can relatively easily define a center of projection or direction of projection, a view plane, but their relationship to the window in terms of the final display is not evident. As such it is not unusual that numerous “trial and errors” are attempted prior to a satisfactory display.

3.5. ARBITRARY 3-D VIEWING DEFINITION

61

Figure 3.14: Projection Window Definition

Figure 3.15: Semi-Infinite Pyramid View Volume for a Perspective Projection 3.5.4.2

View Volume Bounds, or Clipping Planes

For perspective projections, very distant points from the view plane will appear as indistinguishable spots, on a plotter the pen may wear through the paper, while on a CRT the phosphor may “burn”, while objects very close to the view plane may extend through the window as a set of disjointed structures. Furthermore, there are cases in which we may want to limit the number of output primitives projected onto the plane for clarity (For instance we may want to display all objects inside a room, but not those in the adjacent one). Thus we may want to clip the view volume by two planes: 1. Front Clipping Plane or hither plane. 2. Back Clipping Plane or yon plane. which are parallel to the view plane and are defined by F and B respectively which is their distance with respect to the view plane. Perspective: The view volume bounds of a perspective projection is a semi-infinite pyramid with apex at the center of projection (COP) and sides passing through the window, Fig. 3.15. Points behind the COP are not included in the view volume and are not projected. Parallel: The view volume bounds of a parallel projection is a infinite parallelepiped with sides parallel to the direction of projection (DOP), Fig. 3.16.

CHAPTER 3. THREE DIMENSIONAL PROJECTIONS

62

Figure 3.16: Infinite Parallelepiped View Volume for a Parallel Projection 3.5.4.3

Canonical Viewing Volume

In order to perform the appropriate clipping, we should seek the intersection of the object with the 6 (4 in 2D) planes that define the view volume. Thus we should compute the intersection of each line with each of the planes. The large number of calculations required for this process is extremely CPU intensive. This process can be greatly accelerated by normalizing the viewing volume into a canonical viewing volume defined as such: • Parallel Projection:

• Perspective Projection:

x = 0; x = 1

(3.27)

y = 0; y = 1

(3.28)

z = 0; z = 1

(3.29)

x = z; x = −z

(3.30)

y = z; y = −z

(3.31)

z = zmin ; z = 1

(3.32)

Clipping is generally done in hardware, or if it is done in software it would usually be programmed in assembler. 3.5.4.4

Clipping Against a Canonical View Volume

We have previously seen that the normalization transformation will map an arbitrary 3D view volume into a canonical one, unit cube for parallel projection, and truncated right pyramid for perspective projection. We shall thus discuss the numerical procedure by which clipping can be efficiently performed. The most commonly used algorithm for clipping is the one by Cohen-Sutherland where 6 bits are assigned to each point according to table 3.1, where a bit is true (1) when the appropriate condition is satisfied. Entirely Visible Line: A line is entirely visible if both endpoints have a code of all zero. Entirely Invisible Line: A line is entirely invisible if corresponding bits of two endpoints are both true (1), i.e: 011001 and 010010 where the line is entirely below the view volume (the second bit in this case).

3.5. ARBITRARY 3-D VIEWING DEFINITION

Bit number 1 2 3 4 5 6

Point Location Above view volume Below view volume Right of view volume Left of view volume Behind of view volume In front of view volume

63

Parallel yv > 1. yv < 0. xv > 1. xv < 0. zv > 1. zv < 0.

Perspective yv > zv yv < −zv xv > zv xv < −zv zv > 1. zv < zmin

Table 3.1: Cohen-Sutherland Clipping Algorithm

Partially Visible Line, Parallel and Perspective: If the two previous tests fail, then the line is partially visible and up to six intersections may have to be calculated, one for the intersection of the line with each plane. The intersection calculation is most efficiently performed if the parametric representation of the line connecting P1 (x1 , y1 , z1 ) and P2 (x2 , y2 , z2 ) is used. Any point Pv (xv , yv , zv ) along the line can be expressed by: xv = (x2 − x1 ).t + x1

(3.33)

yv = (y2 − y1 ).t + y1

(3.34)

zv = (z2 − z1 ).t + z1

(3.35)

If t varies between 0 and 1, then the three equations would give the coordinates of all points. We will consider the following two cases: 1. Parallel Projection In a parallel projection to calculate the intersection of a line with the top of the unit cube, we replace yv with 1 and solve for t: t=

1 − y1 y2 − y1

(3.36)

If t is outside the interval [0 − 1], the intersection is outside the cube. Otherwise, t will be substituted into the equations for xv and zv giving: xv =

(1 − y1 )(x2 − x1 ) + x1 (y2 − y1 )

(3.37)

zv =

(1 − y1 )(z2 − z1 ) + z1 (y2 − y1 )

(3.38)

2. Perspective Projection

CHAPTER 3. THREE DIMENSIONAL PROJECTIONS

64

In a perspective projection to calculate the intersection of a line with the sloping planes is also simple, if we consider the yv = zv plane, we have: (y2 − y1 ).t + y1 = (z2 − z1 ).t + z1

(3.39)

solving for t we obtain: t=

z1 − y1 (y2 − y1 ) − (z2 − z1 )

(3.40)

substituting t into xv and yv would give: xv =

(x2 − x1 )(z1 − y1 ) + x1 (y2 − y1 ) − (z2 − z1 )

(3.41)

yv =

(y2 − y1 )(z1 − y1 ) + y1 (y2 − y1 ) − (z2 − z1 )

(3.42)

Note the following: (a) This operation has to be performed for each point (thus twice for a line). (b) After each intersection calculation, update the coordinates of the point, and reset the appropriate bit to 0. (c) intersection calculation has to be repeated until all bit codes are 0. (d) In some cases a binary search (which does not require multiplications) is implemented to determine the intersection of a line with a plane.

3.6

Implementation of Arbitrary 3D Viewing Operations

In the previous sections we have defined the two planar geometric projections, and have established a framework for arbitrary 3D viewing in terms of defined parameters. In this section we shall see how this can be algorithmically implemented in a computer program through a series of simple operations. The transformation of an object defined in its world coordinate for display on a particular device is achieved through what has been commonly referred to as a viewing pipeline which performs essentially two tasks: viewing transformation, and clipping. We shall first review the 2D case, and then discuss the 3D one.

3.6.1

Overview

2D Viewing Transformation and Clipping In 2-D the view data base consists solely of: 1. Window (defined in WC). 2. Viewport (defined in NDC). and the viewing pipeline consists in: 1. Clipping.

3.6. IMPLEMENTATION OF ARBITRARY 3D VIEWING OPERATIONS

65

2. Mapping window to viewport. 3. Image Transformation (optional) Note that in GKS, step 2 is defined through the normalization transformation, step 1 by GKS itself, and step 3 through segment transformation. 3D Viewing Transformation and Clipping In 3-D the view data base is more complex, and consists of the following previously defined viewing parameters: 1. Viewing Coordinate System, defined in terms of: (a) View Reference Point (VRP). (b) View Plane Normal (VPN). (c) View Up (VUP). 2. Window in the viewing coordinate system. 3. Plane clipping. 4. Direction of Projection (DOP) if parallel. 5. Center of Projection (COP) if perspective. The viewing operation, or viewing pipeline, consists of: 1. Normalizing Transformation, Npar or Nper to transform an object defined in its original 3D WC system to a canonical view volume. 2. Clipping against canonical view volume. Note this operation may clipp points which have already been transformed. However the clipping operation is much more efficiently performed for a canonical view volume. By now the object will be defined in 3D clipped viewing coordinates. 3. Transformation of the view volume into 3D viewport, the object is now defined in 3D NDC. 4. Optional Image transformation (rotation, scaling, and translation). 5. Projection onto the view plane. 6. Transformation into 2D DC system.

3.6.2

Generalized Normalization Transformations Npar & Nper

Up to this point we have been defining various concepts regarding the viewing operation. By now we are finally in a position to derive all the formulas necessary to implement the complete viewing operation in a manner suitable for computer graphics implementation. This will be defined in terms of a final normalizing transformation N .

CHAPTER 3. THREE DIMENSIONAL PROJECTIONS

66 3.6.2.1

Parallel Projection

For the sake of generality we shall consider an oblique projection. The series of transformations to determine Npar is: 1. Translate the VRP to the origin. 2. Rotate the View Reference Coordinate such that the VPN becomes the positive zv axis, u the xv , and v the yv axis by: (a) Rotating around the y axis Ry (θ). (b) Rotating around the x axis Rx (φ). 3. Rotate so that the projection of VUP onto the view plane becomes the y axis (Rz (α)) coordinates 4. Shear so that all the planes defining the view volume become normal to axes of the viewing coordinate system (or direction of projection becomes parallel to the z axis 5. Translate and scale the view volume into the unit cube. Note that in PHIGS, steps 1 and 2 define the view orientation matrix, while 5 and 6 define the view-mapping matrix. 3.6.2.2

Perspective Projection

For the perspective projection, we seek the normalization matrix Nper which: 1. Translate the center of projection (VRP) to the origin. 2. Rotate axis so that the positive z axis is aligned with the VPN. 3. Rotate so that the y axis is aligned with the projection of VUP into the view plane. 4. Translate such that the COP is at the origin 5. Shear the view volume so that its center line becomes the z axis. 6. Scale the view volume into a truncated canonical right pyramid defined by 6 planes.

Chapter 4

CURVES and SURFACE 4.1

Introduction

Geometric modelling is a subdiscipline of computer graphics which addresses the mathematical definition of objects for graphical display. There are many advantages in using a mathematical representation of objects: 1. A mathematical representation is precise and properties such as length, slope, size, radius of curvatures, center of gravity, and surfaces can be readily computed. 2. A mathematical representation can be compactly stored in a computer (as opposed to a set of digitized data). 3. Mathematically defined objects can be displayed through various different viewing parameters. In the previous lectures we concentrated on the display of simple (i.e. lines and planar polygons) curves and surfaces. In this lecture we shall focus our attention on the methodology used to approximate complex objects by mathematically defined curves or surfaces. Thus the problem confronting us can be stated as follows: “Given a set of arbitrary points defined by the user, how can we mathematically describe a smooth curve (or surface) which passes through (or close to) them”, Fig. 4.1. This mathematical representation can be: Analytic through Interpolation between control points. In this approach, polynomial of order n, is used to interpolate between n + 1 points. While this methods yields a curve which passes through all the points, it often results in unacceptable interpolation due to the oscillatory nature of high (4 and above) order polynomials. Synthetic through Approximation between the points. This approach will enable the designer to freely adjust a “visually attractive” curve by exploring various alternative shapes. While low order polynomial or trigonometric curves obtained through least square approximation may be used when few points are desired, in Computer Graphics Geometric Design (CGGD), piecewise cubic polynomial curves are often used. Cubic polynomial are used because they provide a compromise between flexibility (both 67

CHAPTER 4. CURVES AND SURFACE

68

Figure 4.1: Control Points for Interpolation or Approximation C 0 and C 1 continuity can be ensured at both ends), simplicity, and computational requirements. In general geometric modelling can be subdivided into the treatment of curves (1D), surfaces (2D) and volumes (3D). Volumes can be treated as closed surfaces or as solids. In this lecture we shall concentrate on curves and surfaces only. Solid modelling is a subfield of geometric modelling which defines objects in terms of solid primitives (i.e. cube, cone, sphere, etc.) and through their various boolean operation (i.e. intersection, addition, subtraction of various primitives) and will not be covered. Available tools for solid modelling include PATRAN and AUTO-TROL.

4.2 4.2.1 4.2.1.1

Parametric Cubic Curves Geometric Constraints Piece-wise Linear

Given 2 points P 1 and P 2 , we can define a line connecting them through 2 geometric constrains which impose a C 0 continuity at the end points. In parametric form, this becomes: x(t) = G1x (1 − t) + G2x t y(t) = G1y (1 − t) + G2y t z(t) = G1z (1 − t) + G2z t

(4.1)

where G1x = Px1 , G2x = Px2 , G1y = Py1 , G2y = Py2 and G1z = Pz1 , G2z = Pz2 4.2.1.2

Cubic Generalization

The piece-wise linear approximation for curves can be generalized to cubic approximation in terms of generalized geometric constraints.

4.2. PARAMETRIC CUBIC CURVES

69

First, let us consider the cubic polynomial which defines a curve  segment parametrically. The equation of a line then becomes: Q(t) = x(t) y(t) z(t) or: x(t) = ax .t3 + bx .t2 + cx .t + dx

(4.2)

3

2

(4.3)

3

2

(4.4)

y(t) = ay .t + by .t + cy .t + dx z(t) = az .t + bz .t + cz .t + dx This can be rewritten as: 

Q(t) =



x(t) y(t) z(t)

where

!

T= and

   

C=

t3 t2 t 1

=T·C

(4.5)

"

(4.6) 

ax ay az bx by bz    cx cy cz  dx dy dz

(4.7)

Since determination of the polynomial coefficients depends on geometric constraints, we rewrite C = M · G where M is a 4 × 4 basis matrix (to be determined) and G is the geometry vector of geometric constraints. Hence we can rewrite Q(t) as: 

Q(t) =



x(t) y(t) z(t)

= T  · M ·G

(4.8)

B

or:  !

Q(t) =

t3 t2 t 1

"   

m11 m21 m31 m41

m12 m22 m32 m42

m13 m23 m33 m43

m14 m24 m34 m44

    

G1x G2x G3x G4x

G1y G2y G3y G4y

G1z G2z G3z G4z

    

(4.9)

x(t) = (t3 m11 + t2 m21 + tm31 + m41 )G1x + (t3 m12 + t2 m22 + tm32 + m42 )G2x + (t3 m13 + t2 m23 + tm33 + m43 )G3x + (t3 m14 + t2 m24 + tm34 + m44 )G4x (4.10) and we refer to T · M as B or blending function.

4.2.2

Classification of Curves

Having decided that a cubic parametric representation of a curve is desirable, the next question is how can we determine the parameters, and under which conditions. We shall very briefly discuss three forms: 1. Hermite which defines the end points and tangents of a curve.

CHAPTER 4. CURVES AND SURFACE

70

2. Bezier which defines the position of the curve’s endpoints and uses two other ones (usually not on the curve) to indirectly define the endpoint tangents. 3. B-Spline which approximates the endpoints rather than matching them, thus enabling a C 2 continuity (i.e. continuity of first and second derivatives). Finally it can be shown that each one of the above can be written as: P (t) =

#i=n i=0

Pi Bi,n (t)

(4.11)

where Bi,n is the blending function, and Pi are the n points used for the polynomial boundary conditions.

4.2.3

Hermite Form

In the hermite form, we seek to ensure both C 0 and C 1 continuity at each end of a segment. Hence, given two points P1 , and P4 (note that we use the subscripts 1 and 4 for compatibility with subsequent forms) and their respective tangents R1 and R4 , we define the Hermite Geometric Vector as:    P1      P   4 (4.12) GH =  R1       R4  (where GH has three components Ghx , Ghy , Ghz ). The objective now is to determine the twelve coefficients: ax , bx , cx , dx , ay , by , cy , dy , az , bz , cz , dz , such that: x(0) = P1x , x(1) = P4x , x
(0) = R1x , x
(1) = R4x , recall that the parameter t varies from 0 to 1. From Eq. 4.8: x(t) = T · MH · GHx !

=

t3

t2

t 1

"

(4.13) MH · GHx

(4.14)

Now we can write the first two constraints as: 

x(0) = P1x =



x(1) = P4x =



0 0 0 1 1 1 1 1



MH · GHx

(4.15)

MH · GHx

(4.16)

The other two constraints can be found through appropriate differentiation of Eq. 4.14 yielding:   (4.17) x
(t) = 3t2 2t 1 0 MH · GHx Hence the last two constraints would give: x
(0) = R1x = x
(1) = R4x =

 



0 0 1 0 3 2 1 0



MH · GHx

(4.18)

MH · GHx

(4.19)

4.2. PARAMETRIC CUBIC CURVES

71

Finally grouping all four constraints:     

P1x P4x R1x R4x





     = GHx =   

0 1 0 3

0 1 0 2

0 1 1 1

1 1 0 0

    MH · Ghx 

(4.20)

Thus MH must be the inverse of the 4 × 4 matrix in the preceding equation, or:    

MH = 

0 1 0 3

0 1 0 2

0 1 1 1

1 1 0 0

−1    

   

=



2 −2 1 1 −3 3 −2 −1    0 0 1 0  1 0 0 0

(4.21)

Note that MH is unique, and can be used to determine any point along the segment: 



x(t) y(t) z(t)

Q(t) =

= T · MH · GH

(4.22)

or  

Q(t) =



x(t) y(t) z(t)

!

=

t3 t2 t 1

"   



 2 −2 1 1 P1    P −3 3 −2 −1   4  R 0 0 1 0  1    R4 1 0 0 0

        

(4.23)

Expanding T · MH we obtain BH , the Hermite blending function, which is the weight of each element in the geometry vector: Q(t) = T · MH · GH = BH · GH = (2t3 − 3t2 + 1)P1 + (−2t3 + 3t2 )P4 + (t3 − 2t2 + t)R1 + (t3 − t2 )R4

(4.24)

or: !

Q(t) =

(2t3 − 3t2 + 1) (−2t3 + 3t2 ) (t3 − 2t2 + t) (t3 − t2 )

   P1  P " 4

    

 R1       

(4.25)

R4

Figure 4.2 shows various curves having the same endpoints but different tangents.

4.2.4

Bezier Form

A major drawback of the hermite form is that the designer does not always have an intuitive feel for a derivative direction, while he/she can easily specify endpoints. Bezier (a french Engineer at Renault) has proposed an alternative approach to describe a curve which allows for much greater feel for the relation between input and output. Thus the engineer can readily use his “artistic” intuition, rather than a cool mathematical definition. Hence the

72

CHAPTER 4. CURVES AND SURFACE

Figure 4.2: Family of Hermite Parametric Curves

Figure 4.3: Bezier Curve and Its Four Control Points

4.2. PARAMETRIC CUBIC CURVES

73

Bezier form is to CGGD what the HSV representation is to color definition (as opposed to Hermite and RGB). The Bezier curve can be easily defined in terms of a four points convex polygon as shown in Fig. 4.3: • The curve goes through the two endpoints P1 and P4 . • The tangents at those points is given by P1 → P2 and P3 → P4 respectively. • The curve is also contained within the convex hull of the defining polygon, i.e., within the largest convex polygon obtainable with the defining polygon vertices. • The curve is invariant under an affine transformation. Note that this concept can easily be extended to nth order polynomial approximation defined in terms of n+1 points. However in general it is found more appropriate to use many short cubical segments rather than a longer one of higher order. Using the previous notation, we can now define a Bezier geometric Vector:    

GB = 

P1 P2 P3 P4

    

(4.26)

The tangents R1 and R4 of the Hermite form have the following relationship1 to the four Bezier points P1 , P2 , P3 , P4 : R1 = 3(P2 − P1 ) = P
(1)

(4.27)




R4 = 3(P4 − P3 ) = P (4)

(4.28)

Thus we can define a matrix MH←B which relates the Bezier to the Hermite geometry vectors:      P1 1 0 0 0 P1  P   0 0 0 1  P      2  (4.29) GH =  4  =     R1   −3 3 0 0   P3  R4 P4 0 0 −3 3   



   



GH

MH←B

GB

Since we are after MB , we rewrite Eq. 4.22 as: Q(t) = T · MH (MH←B · GB ) = T · (MH · MH←B ) ·GB = T · MB · GB 



GH







(4.30)



MB

and MB = MH · MH←B   2 −2 1 1 1 0 0  −3 3 −2 −1   0 0 0   =    0 0 1 0   −3 3 0 1 0 0 0 0 0 −3 1

This will be proved later in Eq. 4.39.

0 1 0 3





    =  



−1 3 −3 1 3 −6 3 0    (4.31) −3 3 0 0  1 0 0 0

74

CHAPTER 4. CURVES AND SURFACE

or:



Q(t) = T · MB · GB =

!

t3 t2 t 1

"   



−1 3 −3 1  P1    P 3 −6 3 0   2  P −3 3 0 0    3 1 0 0 0  P4

        

(4.32)

Finally, with Q(t) = T · MB · GB or x(t) = T.MB .Gb,x

(4.33)

y(t) = T.MB .Gb,y

(4.34)

z(t) = T.MB .Gb,z

(4.35)

and with proper substitution we obtain: Q(t) = (1 − t)3 P1 + 3t(1 − t)2 P2 + 3t2 (1 − t)P3 + t3 P4 or: !

Q(t) =

(1 − t)3 3t(1 − t)2 3t2 (1 − t) t3

   P1     P   " 2

 P3       

(4.36)

(4.37)

P4

Let us now prove Eq. 4.27 and 4.28. First we take the parametric derivative of Eq. 4.37:      P1      P  2
2 2 2 (4.38) Q (t) = −3(t − 1) 3(3t − 4t + 1) −3t(3t − 2) 3t  P3       P4  which is now evaluated at t = 0 and t = 1: $

P
(0) P
(1)

%

&

=

−3 3 0 0

  P1    '   0 0  P2  −3 3    P3     

(4.39)

P4

which is identical to Eq. 4.29. Fig. 4.4 shows the four blending curves used in the construction of a cubical spline (four control points). It can be shown that Eq. 4.36 is a special case of the general equations (known as the Bezier/Bernstein Blending functions): Q(t) =

i=n (

Bi,n (t)Pi

(4.40)

i=1

Bi,n (t) = C(n, i)ti−1 (1 − t)n−i (n − 1)! C(n, i) = (i − 1)!(n − i)!

(4.41) (4.42)

In the previous derivations we have assumed n = 4 Finally, it should be noted that if many points are defined, two approaches are possible:

4.2. PARAMETRIC CUBIC CURVES

75

Figure 4.4: Bezier’s Blending Curves for a Cubical Approximation 1. Single high order Bezier form (for instance 4 points would yield a cubic curve, and 6 a fifth order one). Because of the global nature of the blending functions, a change in one vertex is felt throughout the entire curve, thus eliminating the ability to produce local changes within a curve. 2. Blended (or Piece-wise) cubic segments, defined by four (for the first segment) or three (for each subsequent segment) points. The first segment will have 2 knots and 2 control points. Subsequent ones will have only one knot and two control points. Thus moving one knot, only affects locally the curve. Note that by specifying two control points to be collinear with the intermediary knot, C 1 continuity is assured across segments.

4.2.5

B-Splines

We now focus on generating a curve consisting of various segments where the two continuity conditions on a segment come from the adjacent ones. Thus control points are shared by adjacent segments. The curves are generated by multiplying an approximation function (in terms of t) with a matrix containing a subset of adjacent control points. Depending on the boundary conditions, i.e., control points at the beginning and end, are defined we have: 1) Nonperiodic and 2) periodic forms 4.2.5.1 4.2.5.1.1

Non-Periodic Form Quadratic Given a series of points, the nonperiodic quadratic form will:

• Define three special segments, Fig. 4.5, one for:

CHAPTER 4. CURVES AND SURFACE

76

Figure 4.5: Non-Periodic Quadratic B-Splines 1. Beginning segment: 

P1 (t) =

(1 − t)2

−3t2 +4t 2

t2 2

    P1  

P

2    P  3

(4.43)

It can be shown that the first segment starts at the knot P1 (0) = P1 and goes 3 to knot P1 (1) = P2 +P 2 2. Central segment 

(1−t)2 2

Pi (t) =

−2t2 +2t+1 2

t2 2



  

Pi   Pi+1     P i+2

(4.44)

where 0 ≤ t ≤ 1 and 2 ≤ i ≤ n − 3. Through proper substitution with t = 0 and i+1 i+2 and ends at Pi+1 +P t = 1, it can be shown that the curve starts at Pi +P 2 2

3. Last segment is the same as Eq. 4.43 where t has been replaced by (1 − t) and the order of the terms in the row matrix is reversed: 

Pn−2 (t) =

(1−t)2 2

−3t2 +2t+1 2

t2

    Pn−2    

Pn−1  Pn 

(4.45)

• By differentiating Eq. 4.44 for the central segment, we obtain: P
i (t) =



t − 1 −2t + 1 t

  



Pi   Pi+1    Pi+2 

(4.46)

hence the slope at t = 1 for the ith segment is P
i (1) = −Pi+1 + Pi+2 which is the same as P
i+1 (0). Thus we do have continuity of slopes.

4.2. PARAMETRIC CUBIC CURVES

77

• Alteration of one knot, would result in local changes of 4 segments. 4.2.5.1.2 Cubic By extension to the quadratic form, the cubic B-spline uses four control points to define each segment, and an additional order of continuity (C 2 ) makes the curve even smoother. However this is achieved at the expense of two special segments at the beginning and two special segments at the end. Hence n control points will produce n − 3 segments joined by n − 4 knots. • Define 2 beginning, one central and 3 end special segments: 1. Beginning segment: (a) First segment: !

(1 − t)3

P1 (t) =

21t3 −54t2 +36t 12

−11t3 +18t2 12

   P1      " P 

t3 6

2

 P3       

(4.47)

P4

which connects knot P1 (0) = P1 to knot P1 (1) = (b) Second segment: !

P2 (t) =

(1−t)3 4

7t3 −15t2 +3t+7 12

P2 4

−3t3 +3t2 +3t+1 6

+

t3 6

7P3 12

P4 6 .

+

   P2      " P  3

  P4      

(4.48)

P5

P4 P3 2P4 P5 3 which connects knot P2 (0) = P42 + 7P 12 + 6 . to knot P2 (1) = 6 + 3 + 6 . which is the transition between the first and a central segment

2. Central segment !

Pi (t) =

(1−t)3 6

3t3 −6t2 +4 6

−3t3 +3t2 +3t+1 6

   Pi  P " 3 i+1 t 6  P i+2   

Pi+3

    

(4.49)

   

where 0 ≤ t ≤ 1 and 3 ≤ i ≤ n − 5. Through proper substitution with t = 0 and and ends at t = 1, it can be shown that the curve starts at P6i + 2P3i+1 + Pi+2 6 Pi+1 2Pi+2 Pi+3 + + . 6 3 6 3. Last segments: (a) Next to last segment !

Pn−4 (t) =

(1−t)3 6

3t3 −6t2 +4 6

−7t3 +6t2 +6t+2 12

t3 4

   Pn−4  P " n−3

    

 Pn−2       

Pn−1

(4.50)

CHAPTER 4. CURVES AND SURFACE

78 (b) Last segment !

Pn−3 (t) =

(1−t)3 6

11t3 −15t2 −3t+7 12

−7t3 +3t2 +3t+1 4

t3

   Pn−3  "

    

Pn−2   Pn−1      Pn 

For the last two equations, the last three knots are located at: 2Pn−3 Pn−3 n−2 + Pn−2 + 7P12 + Pn−1 3 6 ), ( 6 4 ), and Pn .

(4.51) +

( Pn−4 6

• If two or more control points are coincidents, then the curve is “pulled” close to this point. 4.2.5.2

Periodic Form

Because the nonperiodic form used special segments at the end, the resulting curve coincided with the first and last points. Alternatively the periodic form can be used with only the central segments. For Open B-splines n control points will produce n − 2 segments, while for closed curves, the number of control points is equal to the number of segments, Fig. 4.6

Figure 4.6: Open and Closed Periodic B-Splines

4.3

Parametric Surfaces

4.3.1

Bilinear Patch

Given four points in space, a bilinear patch or surface can be obtained through linear interpolation between them: P(s, t) = (1 − s)(1 − t)P(0, 0) + s(1 − t)P(1, 0) + (1 − s)tP(0, 1) + stP(1, 1)

(4.52)

4.3. PARAMETRIC SURFACES

79

or 

P(s, t) =

(1 − s)(1 − t) s(1 − t) (1 − s)t st

   P(0, 0)  

P(1, 0)

    

(4.53)

 P(0, 1)       

P(1, 1)

As with linear curves, this simple bi-linear formulation does not provide enough flexibility in defining curved surfaces, unless a very large number of patches are used.

4.3.2

Coons Patches

An extension of the bi-linear patche is the Coons patch where a surface is defined through linear interpolation between four arbitrary curves which bound the surface. With reference to Fig. 4.7 we would have:

Figure 4.7: Coons Patch 

P(s, t) =

(1 − t) s t (1 − s)

   P(s, 0)  

P(1, t)

    

 P(s, 1)   

   

P(0, t)



(1 − s)(1 − t) s(1 − t) (1 − s)t st

−

(4.54)

   P(0, 0)  

P(1, 0)

    

(4.55)

 P(0, 1)       

P(1, 1)

which can be rewritten as: 

P(s, t) =

(1 − s) s 1







−P(0, 0) −P(0, 1) P(0, t)   (1 − t)   t  −P(1, 0) −P(1, 1) P(1, t)    P(s, 0) P(s, 1) 0 1

= [Q(s)][Bc (s, t)][Q(t)] where 0 ≤ s ≤ 1 and 0 ≤ t ≤ 1 and Q is the blending matrix.

    

(4.56) (4.57)

CHAPTER 4. CURVES AND SURFACE

80

4.3.3

Hermite Patches

As with cubic parametric segments in which we could specify both location and slope at each end, cubic patches would be defined in terms of location and all the position derivatives:    

[BH ] = 

= Ps (s, t) and where ∂P(s,t) ∂s contains:

P(0, 0) P(0, 1) Pt (0, 0) Pt (0, 1) P(1, 0) P(1, 1) Pt (1, 0) Pt (1, 1) Ps (0, 0) Ps (0, 1) Pst (0, 0) Pst (0, 1) Ps (1, 0) Ps (1, 1) Pst (1, 0) Pst (1, 1) ∂Ps (s,t) ∂t

    

(4.58)

= Pst (s, t). [BH ], the geometric coefficient matrix

• 4 end points • 8 parametric slopes • 4 twist vectors Note that [BH ] is to Hermite surfaces wht GH was for Hermite curves. Rewriting Eq. 4.57 with the subscript H instead of c we have: P(s, t) = [Q(s)][BH (s, t)][Q(t)] or alternatively: 

  Q1 (t)   



Q1 (s) Q2 (s) Q3 (s) Q4 (s)

P(s, t) =

(4.59)

[BH ]

Q2 (t)

    

(4.60)

 Q3 (t)       

Q4 (t)

where Q as well as Q
are given by Eq. 4.25. We should recall that this was the Equation for the Hermite form in terms of end points and tangents, just as in this case. Similarly, we would have: Ps (s, t) = [Q
(s)][BH (s, t)][Q(t)]

(4.61)

Pt (s, t) = [Q(s)][BH (s, t)][Q (t)]

(4.62)




where Q(s) and its derivative are obtained from Eq. 4.25: 

[Q(s)] = 
 Q (s)



=

2s3 − 3s2 + 1 −2s3 + 3s2 s3 − 2s2 + s s3 − s2 6s2 − 6s −6s2 + 6s 3s2 − 4s + 1 3s2 − 2s





(4.63) (4.64) (4.65)

Similarly:

!

[Q(t)] = 
 Q (t)

=



2t3 − 3t2 + 1 −2t3 + 3t2 t3 − 2t2 + t t3 − t2 6t2 − 6t −6t2 + 6t 3t2 − 4t + 1 3t2 − 2t



"

(4.66) (4.67) (4.68)

4.3. PARAMETRIC SURFACES 4.3.3.1

81

Example

A flat rectangular patch lies in the x − y plane as shown in Fig. 4.8. We seek to obtain the

Figure 4.8: Example of a Parametric Cubic Patch coordinates of P( 13 , 13 ). First, we need to define the [BH ] matrix: 1. The upper left part is composed of the vertices coordinates, and thus does not present any difficulty. 2. Since the edges are straight, the parametric derivatives would simply be given by the difference in end point coordinates. Let us consider the term Pt (1, 1), this is the derivative of P with respect to t, thus we would be looking at the difference in coordinates between P(1, 1) and P(1, 0), or Px (1, 1) − Px (1, 0) = 2, Py (1, 1) − Py (1, 0) = 0, and Pz (1, 1) − Pz (1, 0) = 0. 3. The twist vector would in turn be equal to the difference in slopes between the corresponding corners This would yield:

   

[BH ] = 

(1, 2, 0) (2, 2, 0) (1, 1, 0) (3, 1, 0) (0, −1, 0) (1, −1, 0) (0, −1, 0) (1, −1, 0)

(1, 0, 0) (2, 0, 0) (1, 0, 0) (1, 0, 0)

(1, 0, 0) (2, 0, 0) (1, 0, 0) (1, 0, 0)

    

(4.69)

Substituting Eq. 4.63 and 4.66 into Eq. 4.60 for which the x component of [BH ] from the preceding Equation is used, we obtain: 

1 1 Px ( , ) = 3 3 =

 1   20 7 4 −2  2  27

13 = 1.444 9

1 1 0 0

2 3 1 1

1 2 1 1

1 2 1 1

   20       7     4       

(4.70)

−2

(4.71)

CHAPTER 4. CURVES AND SURFACE

82 and



1 1 Py ( , ) = 3 3 =

4.3.4

 1   20 7 4 −2   272

2 2 0 1 1 0 −1 −1 0 −1 −1 0

0 0 0 0

   20     7       4       

(4.72)

−2

5 = 1.667 3

(4.73)

Bezier Surfaces

As with the Hermite form of curves, we recognize that evaluation of [BH ] is far from intuitive (specially for the slopes and the tangents), and a more natural way would be to express them indirectly through control points as was done with the Bezier curve. Hence, the Bezier patch is easier to use because the control points themselves are used to approximate the location of the desired surface. Once again, the patch corners will be defined by the mnots, while the slopes and twists will be indirectly determined from the other control points (the patch does not go through them). Hence, by analogy to what we had for Hermite surface, we start with: P(s, t) = [Q(s)][BB ][Q(t)]

(4.74)

where [Q(s)] and [Q(t)] are given by Eq. 4.37 (with the appropriate substitutions for s and t) , or: 

P(s, t) =

(1 − s)3 3s(1 − s)2 3s2 (1 − s) s3

and [BB ] is given by:

   

[BB ] = 

4.3.5

P11 P21 P31 P41

P12 P22 P32 P42

P13 P23 P33 P43

  (1 − t)3    2



[BB ]

P14 P24 P34 P44

    

3t(1 − t)  3t2 (1 − t)        t3

(4.75)

    

(4.76)

B-Spline Surfaces

Again B-spline, periodic and nonperiodic, surfaces could be developed in an analogous manner to B-spline curves in the general form: P(s, t) = [Q(s)][BS ][Q(t)] For simplicity, we shall focus on the quadratic B-splines, and we would have: 1. Edge Patch:

(4.77)

4.3. PARAMETRIC SURFACES

83

(a) Leading patch (s = 0 or t = 0), (similar to Eq. 4.43 for beginning quadratic B-spline curve): 

Q(s) =

(1 − s)2

−3s2 +4s 2

(1−s)2 2

−3s2 +2s+1 2

s2 2



(4.78)

(b) Edge patch (u = 1 or v = 1): 

Qn (s) =

s2



(4.79)

where the trailing is n in the s direction. 2. Central patch, [Q(s)] would be given by Eq. 4.44, or: 

Q(s) =

(1−s)2 2

−2s2 +2s+1 2

s2 2



(1−t)2 2

−2t2 +2t+1 2

t2 2



(4.80)

[BS ] = [BC S ], where the subscript C refers to central, would be given by: 

Pi,j  C P [BS ] =  i+1,j Pi+2,j



Pi,j+1 Pi,j+2  Pi+1,j+1 Pi+1,j+2  Pi+2,j+1 Pi+2,j+2

and would be defined by 9 control points. Finally, the B-pline cubic patch could be similarly derived.

(4.81)

84

CHAPTER 4. CURVES AND SURFACE

Chapter 5

FRACTALS In 1953 I realized that the straight line leads to the downfall of mankind. But the straight line has become an absolute tyranny. The straight line is something cowardly drawn with a rule, without thought or feeling; it is the line which does not exist in nature. And that line is the rotten foundation of our doomed civilization. Even if there are places where it is recognized that this line is rapidly leading to perdition, its course continues to be plotted.... Any design undertaken with the straight line will be stillborn. Friedensreich Hundertwasser

5.1

Introduction

Fractals are self similar objects. That is, their appearance is not radically altered when viewed under a magnifying glass of arbitrary power. The Flatirons provide a good example. From Table Mesa, they appear as huge jagged rocks. Upon donning our hiking boots and taking a closer look, we notice that they are made up of large jagged boulders which are in turn made up of smaller jagged rocks, and so on. Thus it could be said that any part would mimic the whole. Thus coastlines, clouds, rivers, tree structures are all examples of natural objects which have a “fractal complexity”. On the other hand, most, if not all, man made objects seem to be “linear”. To further illustrate this point, let us examine the complexities associated with measuring a fractal curve such as a coast line. The length can be measured through a straight ruler of variable length and from topographical maps of various scales. As we decrease the size of the ruler, the total length increases due to our ability to account for ever smaller detailed variation in the coast line. At the limit with an infinitesimally small ruler we would have an infinite length. Thus the obvious question is what is the true length, and is there a measure which characterizes the “roughness” of the curve? Thus, as is apparent, classical Euclidian geometry is totally inadequate to explain the complexity of fractals. It was this fact that inspired Benoit Mandelbrot, a Polish born, French mathematician, US Professor to invent a new type of geometry-fractal geometry. It is interesting to note that while Mandelbrot has been an IBM research staff for many years (trying to understand the random nature of disk drive failures among other things) 85

CHAPTER 5. FRACTALS

86

his work on fractals goes back many years, and it was not until recent years, probably with the advent and explosion of computer graphic, that people have started to take note of his work. In 1974 he was appointed an IBM fellow, in 1984 a professor at Harvard, and lately at Yale. Mandelbrot coined the term fractal and the most important set in fractal geometry bears his name. Fractals will be discussed from two distinct approaches: 1. Fractal-Algebra. 2. Fractal-Geometry. In both cases we have an iterative process which yield self-similar objects.

5.2 5.2.1 5.2.1.1

Fractal-Geometry Types of Geometric Fractals Natural Fractals

Let us start our discussion with the following observations: 1. Most man-made objects usually have either flat or smoothly curved surfaces. Those surfaces can be mathematically described within Euclidian geometry methods. Thus we do have not only C 0 but also C 1 continuity (i.e the derivative is uniquely defined at each point. 2. On the other hand, most objects in nature (such as rivers, mountains, or clouds) and phenomena (such as stock market fluctuations, earthquake occurrences) are irregular, fragmented, and discontinuous. 3. Most natural objects seem to exhibit some sort of self-similarity. The coast line along the continent, when viewed from a satellite, an airplane, a few feet, or a few inches from the water appear to be similarly “rugged”. Thus one can not uniquely define the derivative of the curve describing the coast-line. On the basis of these simple observation, it is evident that a non-euclidian geometry may provide a better mathematical model for numerous “capricious” and chaotic natural phenomenas. 5.2.1.2

Artificial Fractals

Putting aside Euclidian geometry, we seek to define new objects geometrically and iteratively. As the geometrical construction will be repeated ad-nauseam, we will by definition have the same “roughness” at various scales, or more precisely, we will have a unique fractal dimension. Geometric fractals are defined in terms of:

5.2. FRACTAL-GEOMETRY

87

Initiator q ✔ ✔ ✔❚ 1/3✔ ✔ ❚ ✔ ✔ ❚ q✔ ✔ ❚ ✔ ❚

✔❚ ✔ ❚

q

❚ ❚ ✔ ✔

✔❚ ✔ ❚

q

1/3

Fractal generator (1st generation)

✔ ✔ ❚ ❚

✔❚ ✔ ❚

q

1/3

Fractal figure (2nd generation)

q

Length of subparts (r)

1/3

Figure 5.1: Artificial Fractal: Triadic Koch Curve 1. An Initiator which represents the initial object. This is analogous to z0 in fractal algebra. 2. A generator. This is a transformation function F which generates the next level of detail for the object. This is analogous to our function f (z; c) in fractal algebra. Thus we seek to construct an object by repeatedly applying the transformation F on an object P. Thus we have: (5.1) Pk+1 = F(Pk ) Examples of fractal curve generation is shown in Fig. 5.1. In this example we start with a straight line of length equal to one. This will be refereed to as the curve of order zero. We subsequently take out the middle third of the straight line and replace it with two lines of equal length meeting at a 60 degrees angle. We have just obtained the curve of level 1. We then repeat this operation for each of the four segments, resulting into the curve of level two which now has 16 segments. This curve is the triadic von Koch curve or simply the Koch curve. 5.2.1.3

Random Fractals

5.2.1.3.1 Fractal Lines Fractal lines can easily be generated recursively along a segment connecting P1 and P2 . First the line segment connecting P1 and P2 is drawn, then the midside point is shifted by a random amount h, and the shifted point is then connected to the original end-points. This process is then iteratively applied to all sub-segments. Note that the mean of the random distribution must be 0 and the mean of the displacement amount (abs(h)) must be

CHAPTER 5. FRACTALS

88

Figure 5.2: Fractal Dimension definition proportional to the distance between the 2 endpoints of the current segment (thus the local “roughness” is indeed independent of the scale). 5.2.1.3.2 Fractal Surfaces Fractal surfaces are generated in a similar manner as fractal lines. For triangular elements each one is subdivided into three smaller ones by connecting offsets of the centroid (as previously defined) to the three nodes. For rectangular elements, each quadrant is decomposed into 4 subelements by assigning 5 random heights to the midside nodes and to the centroid.

5.2.2 5.2.2.1

Theoretical Considerations Fractal Dimension

In Euclidian geometry, concepts of topological dimensions are well defined as integer numbers, 0 to 3 for points, lines, surfaces, and volumes. In this section, we shall introduce a different definition for the dimension of a curve, which we shall call the fractal dimension. With reference to the previous example, we note that at each step the number of line segments is increased by a factor of 4, and that the length of each new line segment generated is 13 the length of line segments in the previous curve. This increases the the total length of the fractal curve by 43 at each step. Thus as more details are added (through this iterative process) the total length tends to infinity. For instance, with reference to Fig. 5.2 we have the results tabulated in Table 5.1, and

5.2. FRACTAL-GEOMETRY

89

Step 1 2 3

N 1 4 16

S 1 1 3 1 9

s 1 3 9

L 1 4 3 16 9

Table 5.1: Fractal Dimension Definition

the fractal dimension is defined by: D=

ln N ln s

(5.2)

Where N is the number of subdivisions at each step, and S is the scaling factor, and s = An alternative form of this equation is: N = sD

1 S.

(5.3)

In our previous example, we subdivided line segments into 4 parts, thus N = 4, and we 4 used S = 1/3 or s = 3. This would give a fractal dimension of D = ln ln 3 = 1.2619. 5.2.2.2

Fractal versus Topological Dimensions

Note that the Euclidian definition of dimension, or topological dimension, is recovered if we subdivided a line into equal parts without changing its length, N = s; in this case D = 1. If we have a surface which we subdivided into N equal parts without changing its area, N = s12 then the dimension of the surface is 2. As a pathological case which illustrates the difference between topological and fractal dimension, let us consider the following object. 1. Start with a unit straight line from A to B. 2. Replace AB by two segments AC and CB such that the angle ACB is equal to π/2, thus the length of segments AC and CB is √12 . 3. Repeat this operation for each subsequent sub-segment. After a few iterations we obtain Fig. 5.3. For this curve, we have N = 2 subdivisions, the scaling factor is S = √12 , and s = √ f rac1S = 2. Thus the fractal dimension is D = lnlnNs = lnln√22 = 1lnln22 = 2. Thus this 2

curve while having a topological dimension of 1, has a fractal dimension of 2!. Curves with fractal dimensions equal to 2 are called space filing curves, and given enough iterations, each point in the plane will be crossed by the curve. 5.2.2.3

Fractal Definition

Mandelbrot, in 1982 offered the following tentative definition of a fractal:

CHAPTER 5. FRACTALS

90

Figure 5.3: Example of Fractal Dimension of 2 A fractal is by definition a set for which the Hausdorff-Besicovitch dimension strictly exceeds the topological dimension. Alternatively it can be said that a fractal is a set of points whose fractional dimension is strictly bigger than its topological one. From the above, we define fractals as Point sets, curves, and surfaces which have a fractal dimension greater than their topological dimension.

5.2.3 5.2.3.1

Numerical Determination of Fractal Dimension Box Method

The essence of this method consists in superimposing grids of various cell sizes on top of the profile. The number of grid cells being intersected by the profile N is then plotted on a log-log scale with respect to the inverse of the grid cell size s = S1 . If a linear relationship is found, then the object is said to be fractal within the specified range, and the fractal dimension will be the slope of the line. 5.2.3.2

Ruler’s Method

In the ruler method a divider (i.e. ruler) of given length r is used to determine the total length of the curve. Note that no fractional measures can be taken. Thus for a given ruler length, the curve length L is given by SN where N is an integer. This operation is repeated for ruler of smaller and smaller size S, and the fractal dimension will then be given by:

5.3. FRACTAL-ALGEBRA

91

N = sD 1 N = ( )D S 1 D S · N = S · ( )    S  L

S 1−D

ln L = (1 − D) ln S 5.2.3.3

(5.4)

Comments

The simplicity of those two methods can be misleading. When programmed, it is found that different simple assumptions could yield different values of D. Hence proper evaluation of the fractal dimension of a random curve is a challenge, and has been reported to be at best within ±.o2

5.3

Fractal-Algebra

We now algebraically define a class of function which boundaries are fractals through the following iterative functions: zn+1 = f (zn ) = zn2 + c

(5.5)

where both z and c are complex numbers. The long-term behavior in this sequence provides information which will allow us to draw fractal images. That these feedback processes actually produce self-similar objects was established during the First World War by two french mathematicians, Gaston Julia and Pierre Fatou. However, it was not until 1980 that Mandelbrot, working for IBM, used a computer to actually draw these fractal images. In this iterative approach we have the following two possibilities: 1. Keep c constant, and iterate on z. 2. Select a value of z, and vary c. The first approach would yield the Julia set, while the second one would yield the Mandelbrot set. Strictly speaking none of those sets is fractal, however there respective boundaries are fractals. Each one of those two sets will be discussed separately, and then their computer implementation will be outlined.

5.3.1 5.3.1.1

The Julia Set Definition

In the Julia set, c is kept constant, while we iterate on z. Note that the c value is taken from the Mandelbrot cell (hence to each point in the Mandelbrot set corresponds a Julia

92

CHAPTER 5. FRACTALS

Figure 5.4: Basin of an attractive fixed point set) and the x and y axis correspond to the real and Immaginary parts of z respectively. Z0 is often taken as 0. The simple, yet powerful iterative method calls for the following observations: 1. For c = 0, the behavior of the iterative process is easily characterized: (a) If z0 is chosen so that |z0 | < 1, the sequence converges to zero. Zero is said to be an attractive point, and the set |z| < 1 (the interior of the unit circle) is called the basin of attraction of the attractive point 0. (b) If |zo | > 1, the sequence “blows up”, i.e. the iterates keep getting larger. Thus infinity is an attractive point and the exterior of the unit circle is its basin of attraction. (c) If |zo | = 1, the iterates stay along the unit circle. Notice that the unit circle separates the two basins of attraction. We may think of this as the two attractors competing for points in the C-plane. Graphically, we would have a unit circle in the complex plane which separates the two basins of attraction, each one associated with its own point of attraction. 2. If we change c to a different value, say c = −.12375 + .56508i, It is still true that there are two attractors, and one of them is at infinity. However, the border between the two basins of attraction is no longer a circle, but rather a fractally deformed circle Fig. 5.4.

5.3. FRACTAL-ALGEBRA

93

Figure 5.5: Basin of an attractive cycle of period 3 3. For a new choice of c, say c = −.12 + .74i, the Julia set is no longer a deformed circle, but rather an infinite number of connected deformed circles. The interior of this set is no longer attracted to a single point, but rather to a set of three points in cycle. zk = f (zk+2 , c) zk+1 =

f (zk , c)

zk+2 = f (zk+1 , c)

(5.6) (5.7) (5.8)

The other attractor is still at infinity, Fig. 5.5. 4. If we take z = 1 + i, then there is only one basin of attraction no matter what we choose for z0 , and the attractor is at infinity. 5. One of the peculiar things about the boundary, is that it is self-similar. If we look at any one of the corners or the bays, we notice that the same shape is found at another place in another size. Boundaries of this kind have been known in mathematics as Julia sets. 6. A feature of the Julia sets is that they carry incredibly complex dynamics. On the boundary the process is as chaotic as can be. 7. The chaotic process can be further highlighted if we were to color code the number of iterations it takes for each point (or pixel) to reach its point of attraction.

CHAPTER 5. FRACTALS

94 5.3.1.2

Computer Implementation

Decomposing the process: zk+1 = zk2 + c √ where zk = xk + iyk and c = p + iq (i = −1), we obtain:

(5.9)

xk+1 = x2k − yk2 + p

(5.10)

yk+1 =

(5.11)

2xk yk + q

The goal is to determine the number of iterations it takes to reach an attractor. Since infinity is always an attractor, we select it as the attractor. Thus we shall color code each value of z according to the number of iterations it took to reach infinity. Note that c is constant in the Julia set. Assuming the display monitor to have a resolution of a × b, and that we have Ncol + 1 colors which can be displayed mathematically (including black), numbered from 0 (black) to Ncol , we will: 1. Global Initialization (a) Select a parameter c. Table 5.2 provides some “interesting set of values”. (b) Select xmin = ymin = −1.5 and xmax = ymax = 1.5. (c) Select a “finite” value for the infinite radius R∞ = 100. (d) Set ∆x = (e) Set ∆y =

xmax −xmin . a−1 ymax −ymin . b−1

2. For Each Pixel defined by (px , py ) with 0 ≤ px ≤ a − 1 and 0 ≤ py ≤ b − 1 (a) Initialize by setting x0 = xmin + px · ∆x, and y0 = ymin + py · ∆y, and k = 0. (b) Iterate by calculating xk+1 and yk+1 from Eq. 5.10 and 5.11, and increase the counter k by 1. (c) Evaluate by calculating: rk2 = x2k + yk2

(5.12)

if: • rk > R∞ (point has been attracted by the attractor at infinity) then choose color k and go to the next pixel. • k = Ncol (point was not attracted to infinity within Ncol iterations) then select color 0 (black) and go to the next pixel. • rk ≤ R∞ and k < Ncol , go back to the previous iteration step to iterate again. Note the following: 1. It may help to have Ncol to be large (say 200). If this exceeds the number of available color, then we can define them in a periodic manner.

5.3. FRACTAL-ALGEBRA

95

2. Computational time can be reduced by 2 if symmetry is accounted for (x, y) and (−x, −y). 3. If xmin and xmax are altered, a blow-up may result. 4. Upon conclusion, all pixels which have not converged to infinity will be black. 5. The black domain includes the other attractor(s). 6. For this domain to be also colored, we must first determine the attractor. 7. To determine the second attractor, we can monitor the point (0,0) for a while and observe where it goes. 8. Note that we may not have a single attractor, but a cycle of them. 9. An “interesting” set of c values along with corresponding windows to observe the Julia set is given in table 5.2.

Re c -0.12375 -0.12 0.481762 -0.39054 0.27334 -1.25 -0.11 0.11031 0 -0.194 -0.15652 -0.74543 0.32 -0.12375 -.39054 -0.11

Im c 0.56508 0.74 -0.531657 -0.58679 0.00742 0 0.6557 -0.67037 1 0.6557 1.03225 0.11301 0.043 0.56508 -0.58679 0.67

xmin -1.8 -1.4 -1.5 -1.5 -1.3 -1.8 -1.5 -1.5 -.5 -1.5 -1.7 -1.8 -2. -2. -1.5 -2.

xmax 1.8 1.4 1.5 1.5 1.3 1.8 1.5 1.5 1.5 1.5 1.7 1.8 2. 2. 1.5 2.

ymin -1.8 -1.4 -1.5 -1.5 -1.3 -1.8 -1.5 -1.5 -.5 -1.5 -1.7 -1.8 -1.5 -1.5 -1.5 -1.5

ymax 1.8 1.4 1.5 1.5 1.3 1.8 1.5 1.5 1.5 1.5 1.7 1.8 1.5 1.5 1.5 1.5

Table 5.2: Some c and Windows for the Julia Set

5.3.2 5.3.2.1

The Mandelbrot Set Definition

Now that the julia set has been defined, we have seen how different structures can be generated with different “seed” values of c. More generally we can have:

CHAPTER 5. FRACTALS

96

1. Connected structures if c is taken from a special set M, which is the Mandelbrot’s set. 2. An infinitely broken structure if c does not belong to the set M. Therefore the boundary of M is of particular interest. Assuming a path which starts inside M and terminates outside of it. As we vary c along this path, the associated Julia set will experience a very dramatic qualitative change as c crosses the boundary of M; as if subjected to an explosion. In a sense this boundary delineates some kind of a mathematical phase transition for the Julia set of f (z) = z 2 + c. For choices of c outside the set, infinity is the only attractor, and hence there is no Julia set. if c is chosen from within the set, there are two attractors (one at infinity, the other is either a point or a cycle). The “bud” from which c is chosen determines the period of the attractive cycle. As a rule of thumb, choices of c near the boundary of the Mandelbrot set yield more complex (and hence more interesting) Julia sets. Note that the Mandelbrot set, contrarily to the Julia set, is not self similar. Hence to each point in the Mandelbrot set corresponds a Julia set, and the x and y axis correspond to the real and immaginary parts of c with z0 often taken as 0. 5.3.2.2

Computer Implementation

The Mandelbrot set is a picture of parameter space (c-space). It divides the complex plane into two regions: those values of c which have Julia sets, and those which don’t. A theorem tells us that for the choice f (z; c) = z 2 + c, it suffices to check only the critical point z0 = 0. This means that for a fixed value of c, if we choose z0 = 0 and iterate, then infinity is the only attractor (i.e. there is no Julia set) if and only if rk , Eq. 5.12, approaches infinity. And so to draw the Mandelbrot set, we divide the complex plane into a grid: one value of c for every pixel on the screen. For every pixel, iterate z 2 + c with the initial point z0 = 0. If rk approaches R∞ , turn the pixel on. If rk does not get larger than R∞ within a certain number of iterations Ncol , we assume the point is converging to an attractor (possibly a cycle) other than infinity, and hence leave that pixel turned off. Spectacular color graphics are produced by counting the number of iterations it takes for point to blow up (if indeed it does) and use that counter as an index in a color table. Good results can be obtained with a reasonably small choice of R∞ , say R∞ = 4.0, and for Ncolor = 50. If z0 = 0 we obtain the canonical version of the Mandelbrot set. If z = 0 then we always get a deformed version of the Mandelbrot set. Table 5.3 lists some “interesting” ranges of values for c.

5.3.3

Observations

Although the procedures outlined above are quite simple, they are quite expensive computationally. Thus you want to store your data in a file (with a resolution of 768 x 768, producing the Mandelbrot set on a workstation may require about over 20 minutes of CPU time). Also, even though we are producing integers (which correspond to color indices), it is more economical in terms of disk space to store these as characters, and then reconvert them into integers when drawing. To give an example, a resolution of 768 x 768 requires

5.4. APPLICATIONS

Re c Min -2.25 -0.19920 -0.95 -0.713 -0.75104 -0.74758 -0.746541 -0.74591 -0.745538 -0.745468 -0.7454356 -0.7454301 -1.254024

97

Re c Max 0.75 -0.12954 -0.88333 -1.764 -0.7408 -0.74624 -0.746378 -0.74448 -0.745054 -0.745385 -0.7454215 -0.7454289 -1.252861

Im c Min -1.5 1.01480 0.23333 0. 0.10511 0.10671 0.107574 0.11196 0.112881 0.112979 0.1130037 0.1130076 0.046252

Im c Max 1.5 1.06707 0.3 0.013 0.11536 0.10779 0.107678 0.11339 0.113236 0.113039 0.1130139 0.1130085 0.047125

Table 5.3: Some Windows into the Mandelbrot Set

588,824 bytes of space when stored as characters. Storing the same data as integers will almost triple this value. Interesting results are obtained by zooming in on portions of a fractal to observe its self-similarity. However, the computations involved when this is done are more delicate, and so we may have to increase the values of R∞ and/or Ncolor . The computations for a given pixel are independent of those elsewhere. Thus computation of fractals using iterative methods are ideal candidates for vectorized parallel super-computing. For a “beautiful” dynamic simulation, imagine that we draw a line from a point inside the Mandelbrot set to another one outside it. And for each point we determine the corresponding Julia set, and take a frame (or picture) of it. This process is repeated. As we are about to cross the Mandelbrot set, the associated Julia set shrinks to a fragile skeleton enclosing no area whatsoever. And finally as c passes beyond the boundary, the corresponding Julia set explodes into fractal dust. Unfortunately, this process can be computationally very expensive.

5.4

Applications

Fractal geometry is more than just a means to draw pretty pictures. The mathematics underlying all of this is neither trivial nor insignificant. It has stirred up a minor revolution in applied mathematics. This is largely due to the fact that fractal geometry provides an entirely new way of looking at chaotic phenomena. Mandelbrot is a great visionary, but some do not consider him a great mathematician by traditional standards. Consequently, most of his work must now be made rigorous, so that it may be used in practical applications. This field goes by several names; dynamical systems, chaotic theory, non-linear dynamics, fractal geometry, Hausdorff measure. As fractals are becoming better understood, the

CHAPTER 5. FRACTALS

98

results are spilling over into such areas as theoretical physics, genetics, engineering, economics, numerical analysis, and computer generated art, among others. Following are some examples: 1. Newton’s Method: Newton’s method is an iterative zero-finding algorithm. It is widely used in engineering in the context of solving optimization (max/min) problems (remember critical points occur at the zeroes of the derivative). Computer graphics and fractal geometry have given numerical analysts new insight into how Newton’s method works and how it may be more intelligently applied. 2. Rendering: We are now producing computer generated films in which fractals play a key role in rendering realistic images of mountains, lightning bolts, coastlines, clouds, waves, and so on. 3. Modeling: Traditionally, engineers have had to make simplifying assumptions to guarantee that the functions describing the problem in question are smooth (i.e. differentiable). Unfortunately, this also means that some accuracy is lost in the model. In order to obtain more accuracy, it is necessary to add more equations to the model (an extreme example of this occurs at NCAR, where certain atmospheric models involve more than 10,000 equations). This obviously increases the expense and difficulty of the ensuing computation. Many mathematicians believe that fractal analysis will provide an alternative way to approach problems in which chaos is involved. It is our hope that the “fractal point of view” will simplify the models for chaotic phenomena (e.g. weather systems, particle physics, quantum theory, catastrophe theory, etc.), and thus improve our ability to describe and analyze these chaotic systems. 4. Image Processing: Using fractals, complex digitized images have been compacted into substantially smaller data files. Those images can then be reconstructed using inverse algorithms. This process has tremendous applications in satellite photography. 5. Physiology: Blood vessels (from the large aorta to the tiny capillaries) must branch throughout the entire body (in most tissue, no cell is ever more than three or four cells away from a blood vessel). However, blood is physiologically expensive, and so these vessels must be distributed in an economical way. It is believed that a fractal-type distribution achieves this maximum economy (consider how thoroughly a complicated Julia set ”fills” the plane, even though it is made only of tiny ”straight’ lines). 6. Engineering: In Engineering there has been many applications of fractal geometry: (a) Seismology: Location of oil field. (b) Geology: to characterize rock faults, and possibly predict earthquakes. (c) Fracture Mechanics: Fractal dimensions have been correlated to fracture toughness of metals and concrete (by the author).

Part II

RENDERING

99

Chapter 6

LIGHT & COLOR 6.1

Introduction

A proper understanding of color is essential to properly understand how rendering in general, and shading in particular (discussed in the following chapter) are achieved. Color can be an immensely complex subject that deals with both physics and physiology, thus this chapter will limit itself to the introduction of the most fundamental and relevant aspects of light and color as they relate to computer graphics. But first let us review some of the most fundamental physical and physiological principles governing light and color: 1. The human visual system interprets electromagnetic energy with wavelengths between 400 and 700 nanometers (nano = 10−9 ) as visible light, Table 1. Color Violet Blue Cyan Green Yellow Orange Red

Wave-Length Nano-meter 400 450 500 550 600 650 700

Table 6.1: Visible Spectrum

2. The electromagnetic energy of a particular wavelength has no color. It is the eye-brain combination that interprets the physical phenomena as the sensation of color. 3. When the perceived light contains all the visible wavelengths with approximately equal weights, the light source is achromatic and would appear as either white, black or gray. 101

CHAPTER 6. LIGHT & COLOR

102

4. When perceived light contains wavelengths in arbitrary unequal amounts, its color is chromatic. 5. The amount of energy present at each wavelength is represented by the spectral energy density distribution P (λ). (a) Black would have a uniform and low spectral density (SD) (b) White will have a uniform and high SD (c) Laser light will have a very narrow SD 6. The tristimulus theory of color mixing is based on the assumption that three types of color sensing cones (about 6 to 7 million of them, each connected to a nerve cell) exist in the central portion of the retina (the fovea which is about 0.25 millimeter in diameter). One type of cone is most sensitive to wavelengths near the middle of the visible light range which the brain-eye visual system converts into the sensation called green. The other two types are most sensitive to long and short wavelengths near the upper and lower ends of the visible light range, which are interpreted as red and blue respectively. If all three sets of cones sense equal radiance levels (energy per unit time), the result is interpreted as white light. 7. Surrounding the fovea are the rods, about 75 to 150 million. Many of them are connected to a single nerve cell, and are most sensitive to low levels of light. 8. Light is characterized by: (a) Radiance: is the total amount of energy (watts) that is generated by the light (electromagnetic) source and is proportional to the integral of the area under the SD. (b) Since not all wavelengths excite the human eye equally (some colors appear to be brighter than other given the same radiance) we denote by Luminance the perceived energy which particularly excite the sensors. Luminance is measured in lumens and is the intensity of the light. Luminance is proportional to the area integral of the area under the SD weighted by a luminous efficiency function. (c) Brightness: is the most subjective measure and is associated with self-luminous objects. to measure. 9. The dominant wavelength specifies the hue of the color. 10. Light is perceived either directly from a source or indirectly through reflection.

6.2

Color Descriptions

Through psychophysical experiments, it has been shown that light can be treated as vectors in a three dimensional space. There are many possible ways of characterizing color, or more specifically color spaces: 1. RGB and CMY.

6.2. COLOR DESCRIPTIONS

103

2. HSV and HLS. 3. CIE. We shall discuss the first two pairs, whereas the last one, which stands for Commission Internationale de l’Eclairage as defined in 1931, is not of major importance in computer graphics.

6.2.1

RGB and CMY

The most widely used primary colors are the red green and blue. While they are not the only possible color base, they constitute an appropriate one as those colors are not only widely separated on the spectrum, but they have a corresponding sensitive sensor in the eye. Thus colors can be defined as: 1. A wavelength in the electromagnetic spectrum (such as yellow at about 600nm). 2. A combination of some primary colors. Those colors may be: • Actual colors found in the spectrum (yellow is a mixture of red and green). • Colors not found in the spectrum such as magenta (the only way to produce it is through a proper combination of blue and and red). Thus we sense or perceive this color through the eye/brain by determining the radiances of its fundamental components. There are two primary color mixing systems of importance in computer graphics: the RGB (red, green, blue) additive color system, Table 6.2, and the CMY (cyan, magenta, yellow) substractive model, Table 6.3.

RED GREEN BLUE

RED RED

GREEN YELLOW GREEN

BLUE MAGENTA CYAN BLUE

Table 6.2: RGB Table

MAGENTA YELLOW CYAN

MAGENTA MAGENTA

YELLOW RED YELLOW

CYAN BLUE GREEN CYAN

Table 6.3: CMY Table In each system an arbitrary color can be defined by its luminance components along the three axis. Those values are usually normalized from 0. to 1. The fundamental differences between the RGB and CMY models, Table 6.4, are:

CHAPTER 6. LIGHT & COLOR

104

RGB CMY

addititive subtractive

direct reflected

CRT copying

black monitor white paper

Table 6.4: Differences between RGB and CMY models

1. The RGB model is additive, while the CMY model is subtractive. • An additive model is one in which the light sources are directly added one another. Examples of additive lights are the electroluminance created by a CRT or TV monitor, direct light, projectors. In an additive model cyan is blue plus green. • A subtractive model is one in which some colors present in a light source are absorbed (or subtracted) following reflection from a surface. In a subtractive model cyan is white from which we have subtracted red (leaving blue and green). Similarly a surface painted with cyan, yellow, and magenta absorbs red green and blue and therefore is black. • From the above it is evident that in most of our surrounding, we are (inconsciensouly) using the CMY model in which colors are defined by the way they reflect white light (or more correctly they absorb their complement). 2. The RGB model is thus best used to quantify direct light, such as the one generated in a black CRT monitor, while the CMY model is best for reflected light, such as the the way white light is reflected from a white paper which might contain a copy of the CRT screen. In the RGB model, a color C can be expressed as: C = r.R + g.G + b.B

(6.1)

where r, g, and b are the respective amounts of red green and blue normalized luminance. The CMY to RGB conversion is quite simple: 



C M

6.2.2

Y



=



1 1 1

−





R G B

(6.2)

HSV and HLS

While the RGB and the CMY system are most convenient for purely technical reasons (e.g. display and printer hardware respectively), they do not easily relate to our human intuitive (and artistic) perception of color. For example, given a pure pigment, an artist would add white to obtain a tint, black to obtain a shade, and both to obtain a tone of the color. The following triangular representation is for a single color. By arranging triangles for each pure color around a central black-white axis, a useful subjective three dimensional representation of color is obtained. A useful implementation of this basic subjective model is the HSV (Hue, Saturation, Value) color solid. If the RGB color cube is projected onto a plane along the diagonal

6.3. INTERPOLATING IN COLOR SPACE

105

white 1.

0.

<-Saturation-> |--------- pure color | / V | / a | / l |tones/ u | / shades e | / | / | / |/ black

Figure 6.1: Value and Saturation Plane for a given Hue in the HSV Model looking from white to black, a hexagon is formed, with the pure RGB primaries and their complements at each vertex Fig. 6.1. This model corresponds to the way artists form their colors. The pure pigments are given for V = 1., and S = 1. Tints are formed by adding white (i.e. decreasing S). Shades are formed by adding black ( i.e decreasing V 6), and tones are obtained by decreasing both S and V . An extension of the HSV is the HLS (hue, lightness, saturation) double hexagon model. In the HLS model (adopted by Tektronix) the RGB color cube is projected to yield a double hexagon with lightness (value) along the axis from black=0 at one apex to white=1 at another. Saturation is given by radial distance from the central axis. Here the fully saturated primary colors and their complements occur at S = 1, and H is undefined when S = 0. Conversion from RGB, CYN, HSV, and HLS can easily be achieved through simple algorithms.

6.3

Interpolating in Color Space

Color interpolation is necessary in many cases. A primary example is for color shading (to differentiate among different shades of a color or among various intensities of scalar quantities such as temperature or stress). If the conversion from one color model to another transforms a straight line (representing the interpolation path) in one color model into a straight line in the other color model, the interpolation results in both models will be the same. This is the case between the RGB/CMY and HSV/HLS models. However, a straight line in the RGB model does not in general transform into a straight line in either the HSV or HSL models. Which model should be used then for transformation? If the traditional results from additive colors are desired (note that interpolation is basically an additive process), then RGB is preferred to HLS or HSV. If, on the other hand, the objective is to interpolate between two colors of fixed hue (or saturation) and to maintain the fixed saturation (or

CHAPTER 6. LIGHT & COLOR

106

hue) for all interpolated colors (such as in shading), then HSV or HLS is preferable. In both cases straight line interpolation are usually used.

6.3.1

Distinguishable Number of Colors

Prior to color interpolation, it is useful to keep in mind the actual number of colors that the human eye can distinguish. It is on the basis of this that we could qualify the “accuracy” of the interpolated colors. The human eye can distinguish approximately 128 different hues and about 130 different tints (or saturation levels S). For each of the hue values a different number of shades (or value V ) can be perceived. About 16 different shades can be perceived in the blue end of the spectrum, while 23 could be detected in the yellow. This translates into approximately 128(H) · 130(S) · 23(V ) = 382, 720 different colors. In most applications 128 H, 8 S, and 15 V are satisfactory, thus yielding 16, 384 colors. This number of colors would require 14 bit planes (214 = 16, 384).

6.3.2 6.3.2.1

Display of Light Intensities Color Displays

A major question is how many intensities are needed to “faithfully” (that is the transition from one level to the other should not be perceived by the human eye) reproduce a continuous tone monochromatic picture. Experience indicate that a value in most cases 64 or 128 are enough. Having identified the number of intensities needed, the next question is what should be their distribution? A priori we would be tempted to linearly distribute them between the two extremes (white and black). But since the eye is more sensitive to ratios of intensity levels rather than their absolute values, a logarithmic distribution should be selected: I3 In I2 = = ... = =r (6.3) I1 I2 In−1 (6.4) I0 = I0 , I1 = r.I0 , I2 = r.I1 , .....I255 = r 255 ∗ I0 1/255

therefore r = I10 In other applications a simpler linear intensity distribution is assumed. Having determined the intensity associated with each polygon, the question is how to translate it into a color. For illumination models, a primary color (or hue) is first selected and different saturations associated with light intensity are defined in the color table. Then to each color shade is assigned a saturation of a color or hue (Hue and Saturations are discussed in the following section on color). Thus with 8 user definable colors, only 8 different shades can be displayed. Should the intensities of each polygon not be related to light, then different colors could but used. 6.3.2.2

Monochrome Displays: Half-Tone Approximations

If an output device needs to display more color intensities then supported color, than halftoning techniques can be used. A typical example is the half-tone approximation used in

6.3. INTERPOLATING IN COLOR SPACE

+-+-+ | | | +-+-+ | | | +-+-+ 0

+-+-+ |O| | +-+-+ | | | +-+-+ 1

+-+-+ |O| | +-+-+ | |O| +-+-+ 2

+-+-+ |O|O| +-+-+ | |O| +-+-+ 3

107

+-+-+ |O|O| +-+-+ |O|O| +-+-+ 4

Figure 6.2: 2 by 2 monochrome displays (news-papers pictures). An achromatic light is colorless, and its only attribute is intensity. It is useful to associate a scalar with the intensity, defining 0 as black, and 1 as white. A black and white (or monochrome) monitor can produce different levels of gray at a single pixel position (recall bit planes!). Line printer, pen plotters and electrostatic plotters produce only two levels: white and black. Half-tone techniques allow such inherently bi-level devices to produce additional intensity levels. Since our device is only bi-level, intensity can be rendered only by taking advantage of the spatial integration performed by the eye. If we view a very small area (say a .02 × .02 inch square) from a normal viewing distance, the eye will integrate fine detail within the small area and record only the overall intensity of the area. This phenomena is used in printing black and white photos in newspapers. Each small resolution unit is imprinted with a circle of black ink whose area is proportional to the blackness (1-intensity) of the area in the original photo. Newspaper halftones use a resolution of 60 to 80 dots per inch (DPI), while magazine and books halftones uses up to 150 dots per inch. Graphics output devices can approximate the variable area dots of halftone reproduction. For example a 2 × 2 pixel area of a bi-level display can be used to produce five different intensity levels at the price of cutting the spatial resolution in half. Thus a picture can be displayed on a 512 × 512 bi-level display using a 2 × 2 pattern with a spatial resolution of 256 × 256. In general, an n × n group of bi-level pixels can provide n2 + 1 intensity levels, Fig. 6.2. One possible pattern for the 3x3 case is given by: 



7 9 5    2 1 4  6 3 8

(6.5)

where all cells whose values are less than or equal to the intensity are set to on. Care should be exercised in generating “isotropic” distribution of the cells, e.g. in a 3 by 3 cells we should avoid having the second row entirely on. We are thus trading spatial resolution for intensity resolution, and the spatial versus intensity resolution trade-off is limited by our visual acuity (about one minute of arc in normal light). Finally halftone approximation is not limited to bi-level displays. If we have a display with two bits per pixel and hence a four intensity levels, the halftone technique can be used to increase further the number of intensity levels. If we use a 2 × 2 pattern, we have a

108

CHAPTER 6. LIGHT & COLOR

total of 4 pixels, each of which can take on three values beside black, allowing us to display 4 × 3 + 1 = 13 intensities.

Chapter 7

ILLUMINATION, SURFACE SHADING, & RENDERING 7.1

Introduction

Surface shading is essential for “realistic” rendering of: 1. The display of three dimensional objects illuminated by light. In this case shading is defined by the light reflected by the surface. 2. Display of mathematical scalar quantities, within an object, as a result of a simulation analysis. It thus constitutes an alternative to contour line representation of mathematical results. In this case shading is associated with a scalar quantity associated with each polygon surface. In this chapter we shall first discuss various illumination models, and then we shall discuss surface shading.

7.2

Illumination

7.2.1

Introduction

Three dimensional display of mathematically defined objects in terms of polygons, can be performed by: 1. Wire frame; 2. Wire frame with hidden lines removed; 3. Shaded surfaces for single color: (a) Constant shading; (b) Intensity interpolation shading (Gouraud); (c) Normal-Vector interpolation shading (Phong); 109

CHAPTER 7. ILLUMINATION, SURFACE SHADING, & RENDERING

110

4. Shaded surfaces for the three fundamental colors; Depending on the conflicting requirements of “realistic” rendering, and computational expense, one of the above model would have to be selected. For shading to be implemented, hidden lines/surfaces need not be necessarily removed if the Painter’s algorithm is adopted. Thus all visible (or invisible) surfaces can be shaded for increased realistic display. This will take into account: 1. Surface properties. 2. The illumination falling into it. 3. The illumination model adopted.

7.2.2

Surface Properties

The principal surface property is its reflectance, which determines how much the incident light is reflected. A black surface absorbs most of the incoming light, thus its reflectivity is approximately zero, while a white surface would have a reflectivity close to unity. Most objects reflect some colors of light better than others. Thus if we suppose that an object has a high coefficient of reflection for red light and a low value for the others and is illuminated by white light (which has equal amounts of all colors), then the red portion of the light will be reflected while the others are mostly absorbed. The object will look red. In fact it is this mechanism which gives objects their colors. If a surface is textured or has a pattern painted on it, the reflectance will vary with position on the surface. Another surface property that plays a role in shaded pictures is transparency which is a measure of the light transmitted through it.

7.2.3

Illumination

7.2.3.1

Types of Light Sources

There are two types of light sources: 1. Light-emitting sources. (a) Ambient (Distributed) source (i.e. nearby neon light). (b) Point source (i.e. sun, lamp bulb). 2. Light-reflecting sources. 7.2.3.2

Light Reflection

When a surface is illuminated, it will reflect light through a: 1. Diffuse reflection for both point and ambient lights. 2. Specular reflection if point light is dominant. Finally the illumination of an object may be partially blocked due to shadows.

7.2. ILLUMINATION

7.2.4

111

Illumination Models

When light energy falls on a surface, it can be absorbed, reflected, or transmitted. Some of the light energy incident on a surface is absorbed and converted to heat (black surfaces). The rest is either reflected or transmitted. It is the reflected or transmitted light that makes an object visible. If all the incident light energy is absorbed, the object is invisible. The object is then called a black body. The amount of energy transmitted, reflected, or absorbed depends on the wavelength of the light. If the intensity of the incident light is reduced nearly equally for all wavelengths, then an object illuminated with white light would appear as gray. The character of the light reflected from the surface of an object depends on the composition, direction, and geometry of the light source, the surface orientation, and the surface properties of the object. The light reflected from an object is either: diffusely, or specularly reflected. 7.2.4.1

Diffuse Reflections

7.2.4.1.1 Lambertian Model Diffusely reflected light is scattered equally in all directions, so that the surfaces appear to have the same brightness from all viewing angles. Hence the position of the observer is unimportant. Lambert’s cosine law governs the reflection of light from a point source by a perfect diffuser. It states that the intensity of light reflected from a perfect diffuser is proportional to the cosine of the angle between the light direction and the normal to the surface: Ird = Ii .Kd . cos θ

(7.1)

where 0 ≤ θ ≤ π/2 Ird is the reflected intensity, Ii is the incident intensity from a point light source, Kd is the diffuse reflection coefficient or reflectivity of the surface ( 0 ≤ Kd ≤ 1.) and is a function of both the surface and the light wavelength (thus there would be three different ones for red, green and blue). Highly reflective surfaces have a reflectivity close to unity. θ is the angle between the light direction and the surface normal. Note that for angles greater than π/2., the light is behind the object. 7.2.4.1.2 Modification for Ambient light Objects rendered with a simple Lambertian diffuse reflection illumination model appear to have a dull matte surface. Because a point light source is assumed, objects that receive no light directly from the source appear black. For example a sphere shaded with this model will be brightest at the point on the surface between the center of the sphere and the light source, and will be completely dark on the half of the surface hidden from the light. In reality real scene objects also receive light scattered back to them from the surroundings. This ambient light represents a distributed light source. Because the computational requirements for a distributed light source are very large, computer graphics illumination treat it as a constant diffuse term and linearly combine it with the lambertian distribution. Thus the above law is modified as: Ird = Ia .Ka + Ii .Kd . cos θ

(7.2)

112

CHAPTER 7. ILLUMINATION, SURFACE SHADING, & RENDERING

Where Ia is the incident ambient light intensity and Ka is the ambient reflection coefficient, it is a material property which ranges from 0 to 1. It is selected based on empirical convenience and does not directly correspond to any physical property of the surface. 7.2.4.1.3 Light Source Attenuation If two surfaces are parallel, thus having the same normal direction, then they would have the same reflected intensity irrespective of their distance d from the view-point. This can be corrected by recognizing the fact that light energy falls off as the inverse square of the distance it travels from the source to the surface and back to the eye at the viewpoint. As such the above model has to be modified. In practice it is found that more realistic results can be obtained by simply using a linear attenuation law: Ird = Ia .Ka + fatt .Ii .Kd . cos θ where fatt should be proportional to

1 . d2L

fatt = max(

(7.3)

In practice fatt is often taken as: 1 , 1) c1 + c2 dL + c3 d2L

(7.4)

where c1 , c2 , and c3 are user defined coefficients This modification has the effect of illuminating the object closest to the viewpoint with the full intensity of the point light source, and all objects farther from the viewpoint at lower intensities. 7.2.4.1.4 Colored Lights and Surfaces So far only monochromatic lights and surface were described. For the general case of colored light and surfaces, the diffuse object color is defined in terms of its three color components (RGB). Hence the illuminating light’s components (I R , I G , and I B ) are reflected in proportion to KOR , KOG , and KOB respectively where OR , OG , and OB define the object’s diffuse RGB components. This would yield: Ird,R = IaR Ka OR + fatt IiR Kd OR cosθ

(7.5)

Ird,G Ird,B

(7.6)

= IaG Ka OG = IaB Ka OB

+ fatt IiG Kd OG cosθ + fatt IiB Kd OB cosθ

(7.7)

Note that we still have one single coefficient to control ambient and diffuse reflections. ALternatively we could have: Ird,R = IaR KaR + fatt IiR KdR Rcosθ Ird,G Ird,B

= IaG KaG = IaB KaB

+ fatt IiG KdG cosθ + fatt IiB KdB cosθ

(7.8) (7.9) (7.10)

Note that in theory we should have: Ird,λ = Iaλ Ka Oλ + fatt Iiλ Kd Oλ cosθ

(7.11)

7.2. ILLUMINATION

113

7.2.4.1.5 Atmospheric Attenuation, Depth Cueing In addition to light source attenuation (from light source to object), we may have atmospheric attenuation or depth cueing from the object to the viewer and includes a shift in color due to the atmosphere. Hence if the original intensity is given by Iλ , a shift toward Idcλ (or depth cue for λ) in linear proportion to the distance from a front and back depth cue planes will occur: Iλ
= s0 Iλ + (1 − s0 )Idcλ

(7.12)

s0 is obtained through linear interpolation between sb at zb (usually 0) and sf at zf (usually 1) on the basis of z which is between zb and zf . 7.2.4.2

Specular Reflection

A picture that uses diffuse shading alone does not look very realistic, largely because changing the orientation of a surface does not change its shade. Thus, for example, a sphere will have uniform shade throughout and will be perceptually indistinguishable from a disk. Because perfectly diffuse illumination rarely occurs in natural scene, observers are unaccustomed to its properties. Some diffuse contribution is evident in nearly all natural scenes, however, diffuse shading can not be used by itself. Shading contributions from specific light sources will cause the shade of a surface to vary as its orientation with respect to the light source changes, and will include specular reflection effects. Specular reflection is observed on any shiny surface. Illuminate an apple with a bright light: the highlight is caused by specular reflection, while the light reflected from the rest of the apple is caused by diffuse reflection. Also we should note that at the highlight, the apple appears not to be red, but rather white, which is the color of the incident light. Now if we move our head we notice how the highlight also moves. This is because shiny surfaces reflect light unequally in different directions: on a perfectly shiny surface (such as a mirror), light is reflected only in the direction for which the angles of incidence and reflection are equal. This means that the viewer can see specularly reflected light from only one angle α. However for nonperfect reflectors the intensity of the reflected light falls off sharply as α increases. Because of the complex physical characteristics of specularly reflected light, an empirical model due to Bui-Tuong Phong is usually used for simple illumination models: Irs = Iθ .w(θ, λ). cosn α

(7.13)

where w(θ, λ), the reflectance curve, gives the ratio of the specularly reflected light to the incident light as a function of the incidence angle θ and the wavelength λ. Here n is a power that approximates the spatial distribution of the specularly reflected light. Large values of n yield focused spatial distribution characteristic of metals and other shiny surfaces, while small values of n yield more distributed results characteristic of nonmetallic surfaces, e.g. paper, for a mirror n would be infinite. The reflectance coefficient w(θ, λ) is a function of the angle of incidence and is set to a constant Ks the material’s specular reflection coefficient. If light from several sources falls on a point, the above model should be applied to calculate reflected energy contributions from each one of them. If an object is in the shadow of one or more light sources, contributions from those sources are not added into the total energy coming from the point.

CHAPTER 7. ILLUMINATION, SURFACE SHADING, & RENDERING

114 7.2.4.3

Complete Illumination Model

Summing the contribution from diffuse (ambient and incident) and specular reflection yields the following illumination model: Ird,λ = Iaλ Ka Oλ + fatt Iiλ [Kd Oλ cosθ + Ks cosn α]

(7.14)

+ (1 − s0 )Idcλ

(7.15)

 Ird,λ

=

s0 Ird,λ

Recalling the formula for the dot product of two vectors: cos θ = n.L

(7.16)

where n and L are the unit vectors in the surface normal and light source directions, respectively. cos α = R.S (7.17) where R and S are the unit vectors for the reflected ray and line of sight directions, respectively.

7.3

Surface or Polygon Shading

There are three basic ways to shade objects defined by polygon meshes. In order of increasing complexity, they are: constant shading, intensity interpolation shading, and normalvector interpolation shading. In each case, any of the shading models from the previous section can be used. Recall that color shading would involve three equations rather than one. Furthermore, it should be noted that shading should not only be associated with light (i.e. light intensity on a given polygon) only but could also be associated with other scalar quantities averaged over an entire polygon such as temperature, pressure, energy. In this case the light intensity of each polygon would be computed from an appropriate analysis program (such as finite element, finite difference).

7.3.1

Constant or Flat Shading

This is by far the simplest model which assign a constant shade to the entire polygon as determined from its centroid. Hence this model assumes that: 1. The light source is at infinity, so n.L is constant across the polygon face. 2. The viewer is at infinity, so n.S is constant across the polygon face. 3. The polygon represents the actual surface being modeled, and is not an approximation to a curved surface. it should be noted that this is the only shading method which can easily be accommodate by GKS or PHIGS without taking advantage of their possible extensions. This model would result in shading discontinuities across polygon edges and give a “facetted” model.

7.3. SURFACE OR POLYGON SHADING

115

7.3.1.0.1 Mach Band Effects A major problem with flat shading is the discontinuity between adjacent polygon which is accentuated by mach band effects. Mach bands are responsible for local intensity perception to be different than the actual one. This is caused by lateral inhibition of the eye’s receptors, that is the more light a receptor receives, the more that receptor will inhibit the response of the adjacent receptor (the inhibition is inversely proportional to the distance between receptors). This problem is solved through Gouraud or Phong shading.

7.3.2

Gouraud or Intensity Interpolation Shading

This model eliminates intensity discontinuities by a four steps process. 1. Determine surface normals. 2. Average surface normals of all polygonal facets sharing a vertex to obtain a uniquely defined vertex normal. Note that if an edge is actually meant to be displayed (such as the joint between the wing and the body of a plane), then two vertex normals, one for each side of the edge must be determined separately. 3. On the basis of the vertex normals define the vertex intensities with any desired shading model. 4. Shade each polygon by linear interpolation of vertex intensities along each edge and then between edges along each scan lines. This shading method can not be explicitly done through GKS or PHIGS, but is often provided as an extension to the graphics standards and is performed at a very low level or in hardware. Some limitations of Gouraud shading include: 1. Total flattening of wavelike surfaces as the average normals of the ridges and the valleys are parallel hence yielding equal intensities. This problem can be solved by introducing additional edges between the valley and the ridge. 2. Poor highlighting from specular reflection. 3. Irregular shading of concave polygons.

7.3.3

Phong or Normal Interpolation Shading

This expensive shading algorithm solves many of the problems associated with Gouraud’s shading. It gives a better local approximation to the surface curvature and hence a better rendering of the surface. In particular, specular highlights appear more realistic. The algorithm is as follows: 1. Determine surface normals. 2. Average surface normals of all polygonal facets sharing a vertex to obtain a uniquely defined vertex normal.

CHAPTER 7. ILLUMINATION, SURFACE SHADING, & RENDERING

116

3. Using a bilinear interpolation scheme, determine the surface normal at each pixel, see Figure. 4. On the basis of this surface normal, determine the local intensity at this pixel.

7.4

Rendering

While shading is crucial for rendering of three dimensional objects, a more complete rendering model would have to account for: 1. Shadows 2. Transparency 3. Texture Mapping Each one of those effects will be briefly discussed below, while a powerful solution to these problems, ray tracing, will be separetly discussed in the following chapter.

7.4.1

Shadows

Even with accurate color tones and shading, when the overall image to be constructed is a scene containing many objects then the eye expects something more: shadows. Shadows help to breathe life into a scene because they depict relationships between objects; their nearness to each other, and relative sizes. They help to resolve visual ambiguities that shaded images alone cannot. When the observer’s position is coincident with the light source, no shadows are seen. As the positions of the observer and the light source separate, shadows appear. Shadows contribute considerably to the realism of the scene by increasing depth perception. Shadows are also important in simulation. For example, a specific area of interest may be invisible because it is in shadow. Further, shadows significantly influence heating, air conditioning, and solar power calculations for building and spacecraft design applications, as well as in other application areas. Observation shows that a shadow consists of two parts, an umbra and a penumbra. The central dense, black, sharply defined shadow area is the umbra. The lighter area surrounding the umbra is called the penumbra. The point light sources generally used in computer graphics generate only umbra shadows. For distributed light sources of finite dimensions both umbra and penumbra shadows result. While light is totally excluded from the umbra shadow, the penumbra receives light from the distributed light source. Because of the computational expense, only the shadow umbra generated by a point light source is generally considered. The computational expense of the shadow calculations also depends on the location of the light source. A light source at infinity is easiest, since an orthographic projection can be used to determine the shadows. A light source at a finite distance, but outside the field of view, is somewhat more difficult because a perspective projection is required. The most difficult case is a light source located within the field of view. Here the space must be divided into sectors and the shadows found in each sector separetly.

7.4. RENDERING

117

Fundamentally, to add shadows to a scene the hidden surface problem must be solved twice: once for the position of each light source and once for the observer’s eyepoint. Thus, it is a two-step process. This is illustrated in the accompanying figure where we have a single light source at infinity located above, in front, and to the left of the block. The scene is viewed from in front, above, and to the right of the block. There are two types of shadows: 1) self-shadows, and 2) projected shadows. Self-shadows result when the object itself prevents light from reaching some if tis planes, e.g. the right hand plane of the block. They are analogous to self-hidden planes and are found the same way. Self-shadowed planes are self hidden planes when the scene is viewed from the position of the light source. A projected shadow results when an intervening object prevents light from reaching another object in the scene. The shadow on the base plane is such an example. Projected shadows are found by projecting all non-self-hidden planes into the scene from the position of the light source. The intersections of the projected plane and all other planes in the scene are found. These polygons are tagged as shadow polygons and added to the data structure. The number of polygons added to the data structure can be reduced by finding the silhouette of each object and projecting it instead of each individual plane. After the shadows have been added to the data structure, the structure is processed normally from the observer’s position to obtain the desired view. Note that multiple views may be obtained without recalculating the shadows. The shadows depend upon the position of the light source and not on that of the observer. Finally a number of hidden line algorithms have been modified to simultaneously account for shadows.

7.4.2

Transparency

Prior illumination and hidden line/surface algorithms have considered only opaque surfaces or objects. Not all objects are opaque, some transmit light. When light passes from one medium to another, e.g. air to water, the light ray is reflected and bent by refraction. Transparent materials such as glass or water will cause specular transmittance. Diffuse transmission occurs through translucent materials such as frosted glass, rays passing through them are jumbled by surface irregularities. Little work with diffuse transmission of light has been done, but specular transmission has been modeled in several ways. The simplest one is to ignore refraction, so that light rays are not bent as they pass through the surface. This means that whatever is visible on the line of sight passing through a transparent surface is also geometrically located on that line of sight. With refraction, the geometrical and optical lines of sight are different. Again several hidden surface algorithms can be adapted to model unrefracted transmission of light.

7.4.3

Texture Mapping

All the algorithms described so far are for planar, bicubic or at least mathematically defined smooth and uniform surfaces. This should be contrasted with the fact that there are two types of surface detail: color and texture. Color detail is applied to smooth surface without appearing to change the geometry of the surface, while texture detail gives the appearance of a roughened surface. Two distinct aspects of texture may be considered:

118

CHAPTER 7. ILLUMINATION, SURFACE SHADING, & RENDERING

1. Addition of a separately specified pattern to a smooth surface (such as a company logo on a surface). The pattern may be a digitized image. After the pattern is added, the surface still appears smooth, this is basically a mapping function. 2. Perturbation of the surface to provide the appearance of roughness (such as for an orange). Some of the techniques used to add roughness involve local perturbations of the surface normals. Recent work uses fractal surfaces. æ

Chapter 8

RAY TRACING (UNEDITED)

Morten Hermanrud

8.1

Introduction

Ray Tracing is a method to generate very realistic pixel based pictures. It incorporates reflection from objects, refraction, transparency, shadows, hidden surface and anti aliasing. This is because it implements a global illumination modell. A global illumination modell is a shading modell such as constant or Phong shading which is extended to take into account light reflected from other objects in the system. Basically one follows the rays of light in a world coordinate system, but because infinite many rays leaves a light source and very few of them hit the eye, one prefers to trace the light rays that hit the eye backwards in the system. The algorithm is completely independent of the object representation, since the generation is reduced to a ray/object intersection test, and is thus independent of the illumination modell. This simplifies the implementation of such features as texture, object hierarchy and different color models. On the other hand, the ray tracing algorithm is extremely CPU expensive, in a typical generation of a picture with a resolution of 1024 x 1024 and a trace depth of 5, we would need to 1024×1024×25 = 32 million intersection tests. For an ordinary object hierarchy with 10-20 objects we would need to do 320-640 million object/ray intersection tests. As each test usually consists of three matrix multiplications and one calculation of the parameters in a second degree function ( for a sphere) we can find that we need to do approximately 48-96 billion float calculations! Therefore one tries to optimise the algorithm and implement it on parallel, distributed or vector processors as the tracing of each ray is independent of the others. This also makes the algorithm attractive for VLSI implementations. The first implementation was by MAGI (Goldstein 71). This used the ray tracing only as a hidden surface algorithm, i.e., it did not implement a global illumination model. Later Kay (Kay 79) and Whitted (Whitted 79) implemented ray tracing with a global illumination model. Whitted’s approach is the most general and is still used in modified versions. 119

CHAPTER 8. RAY TRACING (UNEDITED)

120 ✻N

I

❅ ❅ η1 ❅ ❘ ❅ η2 ❆

N is the normal vector of the surface

✒R

I is the incomming ray vector R is the reflected ray vector

❆ ❆ T  ❆

T is the refracted ray vector η1 , η2 is the Snell constants for the medias Figure 8.1: Reflection, refraction of rays

8.2

Algorithm

The heart of a ray tracing system is of course the tracer. This routine is responsible for reflecting and refracting rays. When a light ray intersects with an object a part of it will be reflected off the surface and a part will be refracted through the object by optic laws. (figure 8.1) To reflect a ray one uses the fact that I,N,R all defines the same plane, where I is the incomming ray, N is the normal vector of the surface and R is the reflected ray, and that the angle between I and N, and the angle between N and R are equal. Then we get : R = I + 2dN

(8.1)

d = −N·I > 0

(8.2)

where

To calculate T which is the rafracted ray, one uses Snells law and the fact that I,N,T all lie in a plane. This results in : T = ηI − (c − ηd)N

(8.3)

)

c=

1 − η 2 (1 − d2 ) η=

η1 η2

d = −N·I

(8.4) (8.5) (8.6)

Both I, N, R and T are unit vectors and η is the relative index of refraction. The algorithm traverses a binary tree called the trace tree (figure 8.2), with a predefined depth and sums up the colors at the nodes. The result of traversing this tree is Is , the light reflected from other objects, and It the light transmitted through the object. The simplest method to start the ray trace is to generate one ray for each pixel on the screen, and use them as starting point for the trace algorithm. The rays generated can be paralell for a non perspective projection or generated specificly for perspective projection as discussed below.

8.3. PERSPECTIVE

121

Main intersection

It is light reflected from other objects Is is light transmitted through the object

✟◗ ◗ I ✟✟ I s ◗ t ✟✟ ◗ ✟ ✟ ◗

Reflect intersection

Refract intersection ✟◗ ✟✟Is ◗ ◗ It ✟ ✟ ◗ ✟ ✟ ◗

Reflect intersection

Refract intersection

Figure 8.2: Trace tree. The basic algorithm described in figure 8.3 is the heart of the ray tracing system. This routine handles the traversal of the trace tree and returning of the global components of the illumination modell, Is and It . The routine intersection called in the algorithm calculates and returns the nearest intersection between the ray and the objects with its the normal vector. The routines reflect and refract only calculates the new vectors to trace, and illuminate is the implementation of the global illumination model. The depth variable decides the height of the trace tree, i.e. how many reflections within reflections we get. The depth to use depends on several things such as screen resolution and color resolution, but is usually between 3 and 10. One should use as low as possible, as the number of intersection tests is 2depth .

8.3

Perspective

As mentioned earlier we generate parallel rays for each pixel on the screen but for a perspective projection this will not work. By simple geometry (figure 8.4) we get the ray vector in the eye coordinate system to be (wx , wy , d, 0). This has to be transformed to the world coordinate system by the inverse of the eye transformation, which is represented by a 4×4 transformation matrix E : R = (wx , wy , d, 0) ∗ E −1

(8.7)

where d is the distance to the screen and wx , wy are normalized screen coordinates, ie −1≤wx , wy ≤1

(8.8)

CHAPTER 8. RAY TRACING (UNEDITED)

122

void trace(objects,ray,color,depth) *objects; object hierarchy light ray *ray; *color; color type int depth; { object hierarchy *object hit; color type reflect col,refract col; light ray reflect,refract; /* Test for intersection between */ /* object hierarchy and ray */ object hit = intersection(objects,ray); /* if we got an intersection and not reached */ /* the max depth of the ray tree, do recursive call */ if(object hit != NULL && depth ¿ 0) { /* Trace the reflected ray */ reflect(object hit,&reflect); trace(objects,reflect,reflect col,depth-1); /* Trace the refracted ray */ if(refract(object hit,ray,refract)) trace(objects,refract,&refract col,depth-1); else no color(&refract col); /* Calculate the color of the point intersected */ illuminate(object hit,color,reflect col,refract col,ray); } else /* The ray didn’t intersect anything, ie no color */ no color(color); }

Figure 8.3: Simple ray tracing algorithm

8.3. PERSPECTIVE

123

Eye coordinate system ✻

Ye screen

❅ ❅ ❅ ❅ ❅ ❅ ❅ Pv ❅ ❅ ❅ ❅ ❅ ❘ ❅

Ze

Xe

❅ ❅ ❅ ❅ ❅

Zw

✻ ❅

✠ ❅ ❅

Ye

❅ ❅ ❅ ❅ Pi ❅ ❅ ❘ ❅

Xw

Yw

Pi Point of interest

✻

Pv Point of view

1 wy

World coordinate system

❅ ❅ ❅ (wx , wy , d)❅ ❅ ❅ ❅

wx , wy Normalized screen coordinates

R d

✲

Ze

d perspective factor/distance to screen R ray to trace E eye transformation (Xe , Ye , Ze ) eye coordinate system

-1

(Xw , Yw , Zw ) world coordinate system R = (wx , wy , d)·E −1

Figure 8.4: Perspective projection.

CHAPTER 8. RAY TRACING (UNEDITED)

124

Ye

✻

Ysmax wy ✲

d

Ze

R

R = (wx ·Xsmax , wy ·Ysmax , d)×E −1 Where d is the distance between Pv and Pi . Figure 8.5: Perspective projection with predetermined viewport The ray to trace is composed of the vector R starting in the point Pv . By choosing d we also decide the size of the picture we generate. Perhaps a better approach is to choose the size of the viewport and location of the eye and calculate d from this. By figure 8.5 we get that R = (wx ·Xsmax , wy ·Ysmax , d)×E −1

(8.9)

where Xsmax , Ysmax is the size of the view port, d is the distance between point of view and point of interest and wx , wy are normalized screen coordinates, ie −1≤wx , wy ≤1

8.4

(8.10)

Shading Models

The ray tracing algorithm is independent of the illumination model used, the only restriction is that one must be able to add up the colors in the trace tree. The most commonly used models are variations of the Phong (Foley 7?) or Cook & Torrance (Cook 81) shading models. The Phong shading model needs some extensions if one wants to implement it as a global illumination model (figure 8.6). I = ka Ia + kd

( j

Ij (N·Lj ) + ks

(

Ij (V·Rj ) + kt It + kso Is

(8.11)

j

The two last parts of the expression (It , Is ), are the transparent color and the reflection of other objects defined when traversing the trace tree. kt determines how transparent an object is and kso determines how mirror like an object is.

8.5. ANTI ALIASING N is the normal vector of the surface

N

L❅ I

125

✻

✒R ❅ ✯V ❅ ✟✟ ✟ ❅✟

L is the light vector R is the reflected light vector V is the view vector Figure 8.6: Vectors in the Phong shading model.

Figure 8.7: Anti aliasing of a pixel.

8.5

Anti aliasing

As mentioned earlier it is very easy to implement other graphics algorithms in a ray tracing system. To implement anti aliasing one only needs to trace more rays. A simple approach is simply to trace the corners of a pixel and average them. This approach might not work when we are handling small objects or texture. A better way is to trace all four corners, compare the values, if they differ too much we subdivide the pixel and trace the new corners, until we have colors within an acceptable range. At last we average the colors with weight on the area they cover. This gives additional overhead, instead of tracing nx ∗ ny rays we have to trace at least (nx + 1)(ny + 1) rays.

8.6

Texture

Another common extension is to add surface textures, as normal vector texture and color texture. Normal vector texture is a way of implementing objects with rough surfaces or

CHAPTER 8. RAY TRACING (UNEDITED)

126

with patterns on their surface. The color texture is to vary the colors on a surface. To implement them in the algorithm we add two statements (figure 8.8). Notice that the normal texture has to be done before the recursive calls so that the reflection and refraction are calculated correctly. The normal texture is implemented as small additions in the normal vector (Blinn 78) N=N+D

(8.12)

where N is a unit vector, and D is the variation vector : D = (Fu (N×Pv ) − Fv (N×Pu ))

(8.13)

where Pu , Pv are the partial derivative of the surface function and Fu , Fv are the partial derivatives of the bump function. This function is a representation of the roughness or pattern we want to map onto the surface. The bump function is usually implemented as an array from which we interpolate the values based on a local coordinate system on the object’s surface u, v. These values are numerically deviated to give Fu , Fv . Much of the same approach is used for color texture. We set the color of a point to be for f(u,v). The function f(u,v) can be anything from an array, mapping a raster image to a surface or for example a step function to map a chessboard on the surface. One could also do texture on the surface with ks and n in a Phong shading, but since this is exactly the same algorithm as color shading it is not discussed here.

8.7

Summary

Ray tracing is an attractive method of generating pictures since it is easy to implement auxiliary routines and because of the realism of the final product, but it has its disadvantages, mainly by being extremely CPU intensive. This can be compensated for by parallel processing and math processors but it will still use considerable amounts of CPU time to generate a picture until there is a VLSI implemetation.

8.8

References

1. Mandelbrot, B., ”The fractal geometry of nature” 2. Foley, F.D., and Van Dam, A., ”Fundamentals of interactive computer graphics” 3. Rogers, D.F., ”Procedural elements of computer graphics” 4. Goldstein, R.A., and Nabel, R., ”3-D visual simulation,”, Simulation pp. 25-31, Jan 1971 5. Kay, D. “Transparency refraction and ray tracing for computer synthesized images”, Computer Graphics, Vol. 13, pp. 158-164 (1979) 6. Whitted, J.T., ”An improved illumination model for shaded display” CACM, Vol. 23, pp. 343-349 (Proc. SIGGRAPH 79)

8.8. REFERENCES

127

void trace(objects,ray,color,depth) *objects; object hierarchy *ray; light ray *color; color type int depth; { object hierarchy *object hit; color type reflect col,refract col; light ray reflect,refract; /* Test for intersection between */ /* object hierarchy and ray */ object hit = intersection(objects,ray); /* if we got an intersection and not reached */ /* the max depth of the ray tree, do recursive call */ if(object hit != NULL && depth ¿ 0) { /* Do the normal texture */ normal texture(object hit); /* Trace the reflected ray */ reflect(object hit,&reflect); trace(objects,reflect,reflect col,depth-1); /* Trace the refracted ray */ if(refract(object hit,ray,refract)) trace(objects,refract,&refract col,depth-1); else no color(&refract col); /* Do the color texture */ color texture(object hit); /* Calculate the color of the point intersected */ illuminate(object hit,color,reflect col,refract col,ray); } else /* The ray didn’t intersect anything, ie no color */ no color(color); }

Figure 8.8: Ray tracing algorithm with texture

128

CHAPTER 8. RAY TRACING (UNEDITED)

7. Blinn, J.F., ”Simulation of Wrinkled Surfaces” Computer Graphics 12 (August 1978) 286-292 8. Carey, R.J., Greenberg, D.P., ”Texture for realistic image synthesis” Computer & Graphics, Vol. 9, No. 2, pp. 129-138, 1985 9. Kaufman, A., Azan, S., ”Texure synthesis techniques for computer graphics”, Computer & Graphics, Vol. 9, No. 2, pp. 139-145, 1985 10. Cook, R.L., and Torrance, K.E., ”A reflectance model for computer graphics”, Computer Graphics, Vol. 15, No. 3, 1981 11. Blinn, J.F., ”Models of light reflection for computer synthesized pictures”, Computer Graphics 11(2), pp. 192-198, July 1977 12. Bouville, C., Burg, R., Dubois, J.L., Marchal, L., ”Generating high quality pictures by ray tracing”, Computer Graphics forum 4(1985) 87-99 13. Heckbert, P.S., Hanrahan, P., ”Beam tracing polygonal objects.” Computer Graphics, Vol 18, No. 3, July 1984 14. Kajuja, J.T., ”Ray tracing parametric patches,” Computer Graphics, Vol. 16 No. 3, July 1982 15. Kajuja, J.T., ”Ray tracing procedurally defined objects”, Computer Graphics, Vol. 17, No. 3, July 1983

Chapter 9

HIDDEN LINES/SURFACES REMOVAL Hidden line/surface removal (one of the most difficult problem in computer graphics) is an attempt to determine the lines, edges, surfaces, or volumes that are visible or invisible to an observer located at a specific point in space.

9.1

Object Definition

There are many ways to describe three-dimensional objects in a data-base. Most algorithms operate on objects which are made up only of flat faces, i.e. planar polygons usually defined in terms of connectivity and 3D “nodal” coordinates. Also each face or polygon may be assigned a color, transparency, reflectance, texture or other properties (to be described in subsequent lecture on rendering). The data base may also be hierarchical. Some algorithms need to know which surfaces meet at a particular edge, others make use of grouping of faces or clusters while others treat faces as if they were disjoint. The difficulty of building environment models for the algorithms increase with the amount of such topological information required by the algorithm, but the algorithm may profit immensely from the quicker reference that such additional information provide. In the following lecture we shall concentrate on algorithms which simply require the definition of its planar polygons in its data base. Finally while economy requires that the number of such faces be minimized, quality of representation requires that the approximation remains faithful. Data representation of 3D objects can be decomposed into two distinct parts: 1. Geometrical. 2. Attributes. The 3D object can as a first approximation be defined as a polygonal mesh and then generalized as a polyhedron. Polygonal mesh definition can be through: 1. Explicit polygon mesh. 2. Explicit edge mesh. 129

CHAPTER 9. HIDDEN LINES/SURFACES REMOVAL

130

9.1.1

Polygonal Mesh

With reference to Fig. 9.1, we can have:

Figure 9.1: Two Adjacent Polygons

9.1.1.1

Explicit Polygon Mesh

An explicit polygon definition requires two lists, Table 9.1

Vertex List V1 x1 , y1 , z1 V2 x2 , y2 , z2 V3 x3 , y3 , z3 V4 x4 , y4 , z4 V5 x5 , y5 , z5 V6 x6 , y6 , z6 Polygon List P1 V1 , V2 , V5 , V4 P2 V6 , V5 , V2 , V3 Table 9.1: Explicit Polygon Mesh Data Base

Vertex list which contains the 3 coordinates of each vertex Polygon list which contains pointers to all the vertices of each polygon listed in a counterclockwise manner. The advantage of this data representation is that it makes it very easy to alter the coordinates of one vertex, delete add and alter individual polygons. The main disadvantage

9.1. OBJECT DEFINITION

131

is that if all the polygons sharing a specified edge or vertex are to be found, then all the polygons must be searched, and most edges are drawn twice. 9.1.1.2

Explicit Edge Mesh

This is an alternative representation which overcomes most of the disadvantages of the preceding one which uses three structures, Table 9.2:

V1 V2 V3 V4 V5 V6 E1 E2 E3 E4 E5 E6 E7 P1 P2

Vertex List x1 , y1 , z1 x2 , y2 , z2 x3 , y3 , z3 x4 , y4 , z4 x5 , y5 , z5 x6 , y6 , z6 Edge List V1 , V4 V1 , V2 V4 , V5 V5 , V6 V5 , V2 V3 , V2 V3 , V6 Polygon List E1 , E2 , E5 , E3 E6 , E7 , E4 , E5

Table 9.2: Explicit Edge Mesh Data Base

1. Vertex list, as above 2. Edge list of two pointers into the vertex list 3. Polygon list of pointers into the edge list Those lists could be expanded to include, Table 9.3 1. Pointers into the polygon list in the edge list (this facilitates retrieval of common edges among polygons) 2. Pointers into edges in the vertex list 9.1.1.3

Attributes

Each polygon or facet may have different attributes. Those attributes can be:

132

CHAPTER 9. HIDDEN LINES/SURFACES REMOVAL

V1 V2 V3 V4 V5 V6 E1 E2 E3 E4 E5 E6 E7

Vertex List x1 , y1 , z1 E1 , E2 x2 , y2 , z2 E2 , E5 , E6 x3 , y3 , z3 E6 , E7 x4 , y4 , z4 E1 , E3 x5 , y5 , z5 E3 , E4 , E5 x6 , y6 , z6 E4 , E7 Edge List V1 , V4 P1 V1 , V2 P1 V4 , V5 P1 V5 , V6 P2 V5 , V2 P1 , P2 V3 , V2 P2 V3 , V6 P2

Table 9.3: Extended Explicit Edge Mesh Data Base

1. Color, usually determined to account for shading. 2. Order of display, useful in the “painter’s” algorithm for hidden surface removal.

9.1.2

General Polyhedron

A polyhedron is a connected mesh of simple polygons such that every edge is shared by exactly two faces. Polyhedron are composed of vertices V , faces F , and edges E, and Euler’s formula states that for any polyhedron: V +F = 2+E

(9.1)

Five of the most common polyhedrons are listed in table 9.4

Polyhedron Tetrahedron Hexahedron Octahedron Icosahedron Dodecahedron

V 4 8 6 12 20

F 4 6 8 20 12

E 6 12 12 30 30

Table 9.4: 5 Common Polyhedrons

9.2. TYPES OF ALGORITHMS

9.1.3

133

Convex Polyhedron

In a convex polyhedron, each facet is either entirely visible, or entirely invisible. Hence the backface removal algorithm would also remove all hidden surfaces.

9.2

Types of Algorithms

There are two general approaches to the hidden line/surface removal problem: Object space algorithms implemented in world coordinates with a very high numerical accuracy resulting in an image with high resolution which can easily be enlarged many times without substantial deterioration of the resolution. Note that these algorithms are more suited for vector devices and HLR. Image space algorithms implemented in device coordinate systems with only enough precision to match the resolution of the display screen used. These algorithms simply calculate an intensity for each of the 250,000 to 1 million pixels of the screen. These algorithms are more suited for HSR and raster devices. This difference in approach produces a corresponding difference in performance: The cost of the object-space algorithm grows as a function of the complexity of the environment, while the cost of image-space algorithms is limited by the resolution of the graphical display, independently from the complexity of the object.

9.3

Simplifying Assumptions

Throughout this chapter, we shall assume that: 1. Object has already been transformed into a viewing coordinate system. 2. Polygons are specified in a counterclockwise manner as viewed from the outside of the object. 3. With each polygon or facet is associated an intensity (or color) which may be the result of a shading algorithms. 4. All polygons are convex.

9.4 9.4.1

Object Space Algorithms Back-Face Removal

This is by far the simplest algorithm as it removes all the facets which face away from the viewer. As mentioned earlier for convex polyhedron, it would automatically eliminate all the hidden lines, Fig. 9.2. Back faces have normals which point away from the viewer; if the plane is defined by: Ax + By + Cz + D = 0

(9.2)

CHAPTER 9. HIDDEN LINES/SURFACES REMOVAL

134

Figure 9.2: Back Face Removal then based on the earlier assumptions, it is evident that the z component of the plane normal is C. Thus if C ≥ 0 in the left handed coordinate system, and we are looking at the object from a VRP at the origin, then this would be a back face, and could be eliminated all together.

9.4.2

Robert’s Algorithm

Robert’s algorithm for hidden line was one of the first for hidden line removal. Computational requirements increase with the square of the number of objects. This cost, along with the advent of raster displays which operate in image space has lead to a loss in interest in this algorithm. However it is a mathematically “elegant” algorithm, simple and most importantly it uses some concepts which are used by other algorithms. 9.4.2.1

Assumptions:

First the main assumption: 1. The display is defined in terms of a number of convex volumes (thus concave volumes would have to be subdivided into convex ones); 2. Each volume is defined in terms of planar surfaces, or polygons (at least four); 3. Each polygon is defined in terms of its edges, (thus Volume → Polygons → Edge) 4. The object has already been transformed, and is to be viewed from a point on the z axis looking toward the origin (i.e. in the 0, 0, -1 direction). 9.4.2.2

Algorithm

The strategy followed by Roberts algorithm consists in the following:

9.4. OBJECT SPACE ALGORITHMS

135

1. Treat each volume separately and eliminate self-hidden (back-faces) planes and self hidden lines. 2. Treat each edge (or line segment) separately, eliminate those which are entirely hidden by one or more other volumes. 3. Identify those lines which are entirely visible. 4. For each of the remaining edge, construct its junction lines. 5. Construct new edges if there is inter-penetration of two volumes. Following are the algorithm details. 9.4.2.2.1

Preprocessing

1. First we need to mathematically define the convex volumes in terms of intersecting planes. The equation of a plane in 3D can be written as: ax + by + cz + d = 0

(9.3)

[ x y z 1 ]{ a b c d }T = 0

(9.4)

or A convex volume can now be defined in terms of its n planes:    

[V ] = 

a1 a2 b1 b2 c1 c2 d1 d2

··· ··· ··· ···

an bn cn dn

     = P1 

P2 · · · Pn



(9.5)

where each column represents a single plane. 2. In order to obtain the 4 coefficients a, b, c, d of a plane equation (stored in one column of [V ] we need to have three points P1 , P2 and P3 with known coordinates (note that 3 and not 4 points are needed as the equation can be normalized by setting d = 1). Thus the plane coefficients can be found from: 



x1 y1 z1   a   b  x2 y2 z2   x3 y3 z3  c

    

    −1  

=

−1

  −1  

(9.6)

or [X] {C} = {D}

(9.7)

3. Using homogeneous coordinate systems, a point S would have the following coordinates:   (9.8) [S] = x y z 1

CHAPTER 9. HIDDEN LINES/SURFACES REMOVAL

136

4. If S is on the plane then [S] · {P } = 0. 5. If the points defining a plane, or a face of the volume are not planar (i.e. the four or more points do not exactly lie on the same plane), then we can still get a best fit approximation for an “almost planar polygon”. 6. The planar equation are set up such that if S is inside the volume then [S] · {P } > 0, and if [S] is outside the volume, then [S] · {P } ≤ 0. This can be obtained by testing a point known to be inside the volume (such as a diagonal to two opposite “corners”), and if need be multiply all the coefficients of a given column (corresponding to a plane) by -1.

9.4.2.2.1.1 Example 1: Volume Matrix Given an origin centered unit cube of edge length equal to 1, Fig. 9.3, the six planes are defined by: x1 = 12 , x2 = − 12 y3 = 12 ,

Figure 9.3: Example of a Volume Matrix y4 = − 12 z5 = 12 , z6 = − 12 The equation of the right hand plane is x = volume matrix would then be given by:    

[V ] = 

1 0 0 − 12

1 0 0 1 2

0 1 0 − 12

0 1 0 1 2

0 0 1 − 12

0 0 1 1 2

1 2





  = 

   

or x + 0y + 0z −

2 0 0 −1

2 0 0 2 0 0 1 −1

1 2

= 0 The complete

0 0 2 0 0 2 1 −1

0 0 2 1

    

(9.9)

The volume must now be tested against a point S inside it to make sure that the sign of each plane is correct (the dot product of S.P (where P is a column of V) must be greater than zero, otherwise the plane equation should be multiplied by −1. Let us consider a point   1 1 1 [S] = 4 4 4 1 = 1 1 1 4 Taking the dot product of this point with V would

9.4. OBJECT SPACE ALGORITHMS

137

yield:



[S] · [V ] =



1 1 1 4 

=

   · 

2 0 0 −1

2 0 0 2 0 0 1 −1

−2 6 −2 6 −2 6

0 0 2 0 0 2 1 −1



0 0 2 1

    

(9.10)

Thus equations of the first, third and fifth planes are incorrect, and should be multiplied by -1:   −2 2 0 0 0 0  0 0 −2 2 0 0    (9.11) [V ] =    0 0 0 0 −2 2  1 1 1 1 1 1 9.4.2.2.1.2 Example 2: Plane Equation Given a quadrilateral planar polygon described by the four vertices, Fig. 9.4:

Figure 9.4: Example of a Plane Equation 

[V ] =



V1 V2 V3 V4

Using the first three vertices will give: 







1 0 0 1   =  0 1 0 −1  0 0 1 −1







  1 0 0   −1    a    = b −1  0 1 0      1 −1 1  c   −1 

which gives:

    a  



 −1    −1  

1 0 0   = 0 1 0  b    c  1 −1 1

−1

  −1  

(9.12)

(9.13)

    −1  

=

−1

  −1  

(9.14)

CHAPTER 9. HIDDEN LINES/SURFACES REMOVAL

138

Hence the equation of the plane is −x − y − z + 1 = 0 or x + y + z − 1 = 0. We can check if the origin is inside or outside this plane by simply taking: 

0 0 0 1

   1     1    

·

 1       

= −1.

(9.15)

−1

Hence, the origin is outside the defined plane. 9.4.2.2.2 Self Hidden Plane Removal Now that the data base is entirely defined, we shall perform the most simple and elementary tasks, that is start by eliminating all the self hidden planes, or back faces. Those are planes which are “unquestionably” hidden by other ones from the same volume. 1. Recall that the eye is at infinity on the +z axis looking toward the -ve z, thus the   view direction in homogeneous coordinates is given by [E] = 0 0 −1 0 . Note that [E] is also the coordinates of a point at infinity on the negative z axis. 2. The argument goes as follows, if we test point [E] against each of the planes constituting [V ], then if the dot product is negative, the point is “behind” this face. As we are dealing with closed and convex volumes, this tells us that the face itself must be “obscured” or “covered” by other ones laying between it and the “front” face”. Mathematically this is achieved by performing the following product: [E].[V ] = [ E · P1 E · P2 · · · E · Pn ]

(9.16)

where n is the number of planes in volume [V]. If [E] · {Vi } is negative, then plane i is self hidden, if [E] · {Vi } is zero then plane i is parallel to the direction of viewing. 3. Note that removing self hidden planes would mean that if the polygon is to be internally color filled (on a raster device, or hatched on a vector device) this operation need not be performed. However it does not ensure us that its edges (as opposed to its interior) do not have to be displayed. 9.4.2.2.2.1 Example 3: Self Hidden Planes Considering the  unit cube of  example 1, and the eye position on the positive z axis at infinity [E] = 0 0 1 0 , hence 

the view direction, Fig. 9.5, is given by: [Ed ] = product [Ed ] · [V ]: 

[Ed ] · [V ] =





= Hence, it is apparent that:

0 0 −1 0

   · 



0 0 −1 0 . We now take the dot

−2 0 0 1

0 0 0 0 2 −2



2 0 0 0 0 0 −2 2 0 0 0 0 0 −2 2 1 1 1 1 1

    

(9.17)

9.4. OBJECT SPACE ALGORITHMS

139

Figure 9.5: Example of Self Hidden Planes • Planes 1 to 4 are all parallel to the direction of view • Plane 6 is self hidden • Plane 5 is visible

9.4.2.2.2.2 Example 4: Self Hidden Plane Following Viewing Transformation Again considering the unit cube, we now rotate it by 45o about the y axis, Fig. 9.6. Recalling that the transformation matrix for a rotation with respect to the y axis is given

Figure 9.6: Example of Self Hidden Planes for a Rotated Volume

CHAPTER 9. HIDDEN LINES/SURFACES REMOVAL

140 by:



cos θ 0 − sin θ 0

  

RY = 

we have for θ = 450 :



0 sin θ 0 1 0 0 0 cos θ 0 0 0 1

√1 2

√1 2

0 1 0 0

 0   − √1

RY = 

2

0

0 0 0 1

0 √1 2

0

    

(9.18)

    

(9.19)

and the transformed volume matrix [V T ] would be given by: 

√1 2

 0   − √1

[V T ] = [RY ][V ] = 

2



0

− √22  0 

=  

√2 2

1

0 1 0 0

√1 2

0 √1 2

0

√2 2

0 − √22 1



0 0 0 1

   

−2 0 0 1

2 0 0 0 0 0 −2 2 0 0 0 0 0 −2 2 1 1 1 1 1

0 − √22 2 0 0 − √22 1 1

0 −2 0 1

√2 0 2

    



   √2 0 

0

(9.20)

2

1

Finally, looking at the transformed volume from the same point as in Example 3, we get: 

− √22    0  0 0 −1 0 ·  √2 [Ed ] · [V T ] = 



=

2

1 − √22

√2 2

0 0

√2 2

√2 2

0 − √22 1

− √22



0 −2 0 1

0 − √22 2 0 0 − √22 1 1

√2 0 2

0 √2 0 2

    

1 (9.21)

Hence, the first and sixth planes (corresponding to the left and rear planes in V) are now self hidden. 9.4.2.2.3 Self Hidden Line Removal Removing a self hidden planes, does not mean that all its edges are invisible. An obvious test to remove self hidden lines is to check whether they are common to two self hidden planes, Fig. 9.7. 9.4.2.2.4 Removal of Lines Hidden by Other Volumes, New Contact Lines Having removed the self hidden lines and planes, we could stop here if we had only one volume. However if we have more than one volume than each of the remaining edges can be potentially hidden by any of the remaining volumes (except the one to which it belongs). Such a “hiding” can be caused by: 1. Partial penetration of one volume into another one.

9.4. OBJECT SPACE ALGORITHMS

141

Figure 9.7: Multiple Convex Volumes 2. A volume partially “covering” or hiding another one behind it. Thus we shall loop on all the volumes, and for each volume loop on each of its non selfhidden edges, and for each of those we should loop on all the volumes (except current one), to solve our problem. The computational effort involved in this task can be substantially V representing its highest z value reduced if we recognize the fact that for a volume with Zmax E (closest point to the eye), and for an edge with Zmin (representing its lowest z coordinate, or E V > Zmax then there is no way that the volume can farthest point from the eye), then if Zmin hide this edge (in other word the edge or line is entirely “in front” of the volume), thus this edge volume comparison can altogether be eliminated. Similar comparison could be made for the x and y coordinates (that is a line entirely to the left/right, below/above a volume) for further elimination of volumes which can potentially hide an edge. Having eliminated some edge volume combinations, it remains to treat those cases where penetration (of a line into a volume) occurs. Following are more details explanation: V , X V , Y V , Y V , Z V , and Z V . 1. For each volume determine its Xmin max min max max min V , where the first entry is the volume with minimum 2. Sort the volumes in terms of Zmax V , that is starting from minus infinity and moving toward the eye. Zmax

3. For each non self-hidden edge, test it against all other volumes in the display. We shall refer to the volume to which this particular edge belongs as the test object, and the volume against which it is compared the test volume, 4. Compare each edge only with test volumes with lower test priority (as determined from the sorting performed in 2), i.e. with volumes with a higher Zmax which can potentially hide the edge or the test object. 5. For each one of the above, perform a bounding box test. That is make sure that the test object is not entirely to the left/right, above/below the test volume. Mathematically this means:

CHAPTER 9. HIDDEN LINES/SURFACES REMOVAL

142 TEST VOLUME On which we are currently looping Xmin Xmax Ymin Ymax

Comparaison

> < > <

TEST OBJECT fixed volume to which current edge belongs Xmax Xmin Ymax Ymin

Test volume is entirely to the right to the left above below

6. If the test volume can not hide the test object, move to the next one, and go back to 5, otherwise go to 7. 7. Next we have to check if those two volumes are entirely separate and disjoints or whether there is some interpenetration. This is done by running some penetration tests: (a) If Zmax of test object is less than Zmin of test volume penetration is not possible (test volume is in front of test object), move to the next test. (b) If Zmax of test object is greater than Zmax of test volume, then the test object may penetrate the front face of the test volume. Set the visible penetration flag for a later usage, and place the penetrating volume on the penetration list. (c) If Xmax of test object is greater than Xmax of test volume, then the test object may penetrate the side of the test volume. Set the visible penetration flag for a later usage, and place the penetrating volume on the penetration list. (d) If Ymax of test object is greater than Ymax of test volume, then the test object may penetrate the top or bottom of the test volume. Set the visible penetration flag for a later usage, and place the penetrating volume on the penetration list. Note: (a) Having checked if an edge is penetrating a volume, or whether it is simply hidden by a volume, and knowing that this edge is not entirely invisible, it remains to determine which portion of this line is visible, and which is not. In order to facilitate such a task mathematically, let us define the parametric equation of the line: (9.22) P (t) = P1 + (P2 − P1 )t where0 ≤ t < 1 (t = 0 at P1 , and t = 1 at P2 ). Our objective is to determine the range of values in t for which the line is hidden. The above parametric line equation can be rewritten as: v = s + dt (9.23) where v is the position vector of the line, s is the starting point, and d is the direction of the line. We shall now define a plane containing this line and the eye located at g. In this plane a line connecting the eye to any point along v is given by: Q(α, t) = u = v + gα = s + dt + gα

(9.24)

9.4. OBJECT SPACE ALGORITHMS

143

with 0 ≤ t < 1, and α ≥ 0. Note that α is positive because we are only considering points between the eye and the edge. Thus a given value of t yields a point on the line, and a given value of α yield a points on the line connecting this point to the eye. Thus the pair of α and t defines any point on the plane. (b) Recall from above that for a point Q(α, t) to be inside or hidden by a volume [V ] or transformed volume (in the most general case) [V T ], their dot products must be positive. Mathematically this means: h = u.[V T ] = Q(α, t).[V T ] = s.[V T ] + td.[V T ] + αg.[V T ] > 0

(9.25)

if each component of h is nonnegative, for a given set of α and t, then the line is hidden by the volume [V T ]. Defining: p = s.[V T ]

(9.26)

q = d.[V T ]

(9.27)

w = g.[V T ]

(9.28) (9.29)

then the above condition for hidden line can be restated as: hj = pj + t.qj + α.wj > 0

(9.30)

and 1 ≤ j ≤ n is the face number defining volume [V T ]. Clearly we are interested in the case in which the line starts to become invisible, or when hj = 0, for this value the point of the line lies on the plane. Thus we should set hj = 0 for each plane j of [V T ]. This would yield a series of equations in both α and t, all of which must be satisfied. Note that we have an overdetermined system with only two unknowns (t and α) and at least 4 equations. When solved in pair, the set of solutions is searched in order to extract the two of utmost importance tminmax , and tmaxmin . Thus the line would be hidden for: 0 ≤ tmaxmin < t < tminmax ≤ 1.

(9.31)

NOTE: The confusing double subscript indicates that we may have different pairs of solutions associated with different values of α. The first subscript (i.e. max in tmaxmin , or min in tminmax ) refers to the one among the various sets, and the second refers to a value within a set. 8. Back to our algorithm, we shall now determine s and d for the edge, and compute p, q, and w for each plane of the test volume. 9. Test for total visibility of a line by checking if both its ends lie between the eyepoint and a visible plane. It can be shown that a line is totally visible if:

CHAPTER 9. HIDDEN LINES/SURFACES REMOVAL

144

wj ≤ 0

(9.32)

pj ≤ 0

(9.33)

pj + q j ≤ 0

(9.34)

If a line is totally visible, skip to the next edge in the test object, otherwise go to 10. 10. Form the hj equation and solve simultaneously in pairs including t = 0, and t = 1 boundaries. If the visible penetration flag is set, then include the case α = 0 boundary. Save the penetrating points. Otherwise ignore the α = 0 boundary. 11. For each t, α solution, check that 0 ≤ t ≤ 1, and that α is greater or equal to zero, and that hj is larger than zero for all planes. Only if those conditions are met find tmaxmin and tminmax . 12. Calculate the visible line segments and save for testing against lower priority volumes. 13. Next we shall look into “new” edges caused by the junction or interpenetration of two volumes. This is to be performed only if the penetration flag has been set, otherwise move to the display routine. 14. Form possible junction edges by connecting all penetrating points for the two penetrating volumes. 15. Test all junction edges against both penetrating volumes for visibility. 16. Test the surviving visible junction edges against all volumes in the scene for visibility. Save the visible segments. 17. Display the remaining visible edges which survived, or where generated by the preceding steps. 9.4.2.2.4.1 Example 5: Parametric Plane Consider the line connecting P1 (−2, 0, −2) and P2 (2, 0, 2) viewed as before from a positive z infinity point, Fig. 9.8. In homogeneous coordinates we would have: P1 (−2, 0, −2, 1) and P2 (2, 0, −2, 1), and 

P (t) = v = s + dt =

−2 0 −2 1 

Since the eyepoint vector is given byg = 

Q(α, t) = s + dt + gα =

−2 0 −2 1

1 2

we get Q(α, t) =

2 0 −2 1 .







4 0 0 0

t

(9.35)

we obtain:



+

and α = 3 we get Q(α, t) = 



+ 

0 0 1 0



4 0 0 0 

For example if t =





t+



0 0 1 0

α (9.36)



0 0 1 0 , and for t = 1 and α = 0

9.4. OBJECT SPACE ALGORITHMS

Figure 9.8: Example of a Parametric Plane

Figure 9.9: Example of a Testing an Edge against a Volume

145

CHAPTER 9. HIDDEN LINES/SURFACES REMOVAL

146

9.4.2.2.4.2 Example 6: Testing A Line Against a Volume Finally, let us test the line connecting P1 (−2, 0, −2, 1) and P2 (2, 0, −2, 1) from Example 5, with the unit cube of example 1. This line is partially hidden as shown in Fig. 9.9 we have: 

s = d = g =

[V ]

  

−2 0 −2 1



(9.37)



4 0 0 0

(9.38)



0 0 1 0 −2 2 0 0 0 0 0 −2 2 0 0 0 0 0 −2 2 1 1 1 1 1 1

 0  =   0

(9.39)

    

(9.40)

computing p, q, and w would yield: p = s · [V ] = q = d · [V ] = w = g · [V ] =

  

5 −3 1 1 5 3 −8 8 0 0 0 0 0 0 0 0 −2 2

  

(9.41) (9.42) (9.43)

where each column corresponds to a plane for which we have to test: hj = pj +tqj +αwj > 0 yielding: 5 − 8t > 0 −3 + 8t > 0 1 > 0 1 > 0 5 − 2α > 0 −3 + 2α > 0

(9.44)

The third and fourth equation simply state that the conditions is alaways satisfied, as the line is always inside or between the top and bottom surfaces of the cube. By setting the other four equations to zero, would yield: t = 58 , t = 38 , α = 52 , and α = 32 and tmaxmin = 38 and tminmax = 58 , thus the line is hidden for 38 < t < 58

9.5 9.5.1 9.5.1.1

Image Space Algorithms Depth Buffer Methods Z Buffer

In this commonly used algorithm, we test the visibility of each surface one point at a time. Thus for each pixel position on the view plane, we scan all the facets encompassing it, and determine the one with the smallest zv value. Hence two buffers are required for each pixel: 1. Depth buffer which stores the smallest z value for each pixel

9.5. IMAGE SPACE ALGORITHMS

147

2. Refresh buffer which stores the correspondingly intensity value Note that while this method is very simple to implement, specially with a cannonical view volume (depth ranges from 0. to 1.), it requires a very large memory. A typical highresolution graphics display with 1000 × 1000 pixels would require a buffer of one million four bytes (or 32 bits) numbers! Hence all pixels are initialized with a depth of 1., and the points closest to the viewer would have the smallest depth. Note that if the plane is defined by Ax + By + Cz + D = 0, then the depth value for any point in the plane is given by: z=

−Ax − By − D C

(9.45)

and for any scan line the x and y increments are always 1, thus z
=

−A(x + 1) − By − D C

or z
= z −

A C

(9.46)

(9.47)

A is a constant for each plane, succeeding depth values for points along a scan line Since C can efficiently be determined. Similarly

z

= z +

B C

(9.48)

for y

= y − 1 9.5.1.2

Scan Line Algorithm

The scan line algorithm is identical to the z-buffer algorithm, except that one scan line at a time is processed, hence a much smaller buffer would be needed.

9.5.2

Screen Subdivision Method

These methods are conceptually similar to the z buffer one, except that they require smaller buffers at the expense of greater number of calculations. The essence of the method is Divide and Conquer and consists of subdividing viewing areas into smaller and smaller rectangles until each small area is the projection of part of a single visible surface or no surface at all. 9.5.2.1

Warnock Algorithm

In this method the window is continuously subdivided into four equal squares. Subdivision would have to stop when the resolution of the display device is reached. Thus for 1024 by 1024 raster displays at most 10 subdivisions are needed (210 = 1024). Following each subdivision, it is determined whether the window must be further subdivided or entirely color filled by a certain intensity. Considering the two polygons of Fig. 9.10 we refer to the subdivisions of level 1 as 2a, 2b, 2c, and 2d for the lower left, left right, upper left, and upper right quadrant respectively.

148

CHAPTER 9. HIDDEN LINES/SURFACES REMOVAL

Figure 9.10: Warnock Algorithm Subdivisions If a subdivision is empty, it is displayed with the background intensity, if not it is further subdivided. This subdivision process yields a subwindow structure called a quadtree, Fig. 9.11. Note that if two or more polygons overlap, then a z sort is performed, and the

Figure 9.11: Quadtree Data Structure for Warnock’s Algorithm polygon with the highest value controls. Finally, it should be noted that for anti-aliasing, the subdivision is carried one extra level below the pixel size and an average is taken of the four sub-pixel intensity values. A simplification of the above algorithm defines the relationship between widow and polygon area, Fig. 9.12: 1. Surrounding: the polygon completely surrounds the area 2. Intersecting: the polygon intersects the area 3. Contained: the polygon is completely contained within the area

9.6. OBJECT-IMAGE ALGORITHM: DEPTH SORTING OR PAINTER’S ALGORITHM149

Figure 9.12: Relationships Among Polygons for the Warnock Algorithm 4. Disjoint: the polygon and the area are completely disjoint The area will not have to be further subdivided if: 1. All the polygons are disjoint from the area, then the area is color filled with the background color. 2. There is only one intersecting or contained polygon. In this case the area is first filled with the background color, and then the part of the polygon contained is scanconverted. 3. There is only one surrounding polygon, and no intersecting or contained polygons. Then the are is color filled with the one of the surrounding polygon 4. There are one or more intersecting, contained, or surrounding polygon. However one surrounding polygon is in front of all the others. Then the area would be color filled with the one of that polygon. If none of the above are satisfied, then further subdivision would be required. 9.5.2.2

Weiler-Atherton Algorithm

The Weiler-Atherton algorithm is a generalization of Warnock’s algorithm. In this method, subdivision is not along rectangular boundaries, but rather along polygonal ones. Thus the number of subdivision is minimized at the expense of additional computation.

9.6

Object-Image Algorithm: Depth Sorting or Painter’s Algorithm

The Painter’s algorithm draws its name from the manner in which oil painting is created. The painter starts by painting the background, then superimposes on it the foreground part without having to “erase” any part.

CHAPTER 9. HIDDEN LINES/SURFACES REMOVAL

150

By analogy, this algorithm starts by sorting all the faces in decreasing order of depth (as computed at the centroid), then “paints” or display the facets from back to front. On a raster display each successive facet will overwrite the previous one. Since facets are sorted on the basis of distances taken from their centroid, this algorithm does not always yield satisfactory results (such as for interpenetrating faces, or relatively large facets). Note that this very simple and efficient algorithm operates in Object space for sorting, and image space for rendering. Furthermore, there can be cases where some polygons are inter-related in such a manner that the resulting display is not entirely correct. Finally, the painter’s algorithm can not be used to generate hard-copy plots of the image. ============================================================

9.7

Source Listing for Z-Buffer

Written by Fred Tracey, WES, UNEDITED MAIN

--SELECTD |-USTART |-SHADE |-UBACKG |-FRAME |-PAINT | |-UBELL |-UPAUSE |-UEND

--FLINE --COLOR |-GCSPEN

SUBROUTINE ========== MAIN

FLINE FRAME PAINT

CALLS ===== ------------------>SELECTD |->USTART |->SHADE |->UBACKG |->FRAME |->PAINT |->UBELL |->UPAUSE |->UEND

------------------>FLINE ------------------>COLOR |->GCSPEN

9.7. SOURCE LISTING FOR Z-BUFFER

151

SHADE THIS SUBROUTINE ===============

CALLED BY ==========

FLINE

<---------------|FRAME

FRAME

<---------------|MAIN

PAINT

<---------------|MAIN

SHADE

<---------------|MAIN

SUBROUTINE ==========

COMMON BLOCK(S) ===============

MAIN

------------------>QGCS |->ZBUFF |->POLYG

FLINE

------------------>ZBUFF

FRAME

------------------>QGCS |->POLYG

PAINT

------------------>ZBUFF

SHADE

------------------>POLYG

COMMON BLOCK ============ POLYG

REFERENCED BY ============= <----------------|FRAME |MAIN |SHADE

QGCS

<----------------|FRAME |MAIN

ZBUFF

<----------------|FLINE |MAIN |PAINT

The following subroutines have been called by other subroutines but are not defined and appear (in the order they were called) as follows :

CHAPTER 9. HIDDEN LINES/SURFACES REMOVAL

152 SELECTD USTART UBACKG COLOR GCSPEN UBELL UPAUSE UEND

COMMON /QGCS/ XMIN, YMIN, ZMIN, SFX, SFY, SFZ, XBORDR, YBORDR COMMON /ZBUFF/ IZBUF(640, 25) COMMON /POLYG/ X(100), Y(100), Z(100), XB(100), YB(100), & ZB(100), NPTS, IYMIN, IYMAX, ICOLOR DIMENSION JCOLOR(12) CHARACTER ANAME * 4, FILNAM * 10 DATA JCOLOR /7, 15, 4, 12, 2, 10, 3, 11, 5, 13, 9, 9/ C C C

GET FILES. PRINT*, ’INPUT FILE NAME?’ READ 10, FILNAM 10 FORMAT(A10) OPEN (2, FILE=FILNAM, STATUS=’OLD’, IOSTAT=ISTAT) OPEN (4, FORM=’BINARY’)

C C C

INITIALIZE GRAPHICS. CALL SELECTD CALL USTART

C C C

DEFINE SCALING DATA.

SCALE TO RASTER UNITS.

XMIN = 1.E20 YMIN = XMIN ZMIN = XMIN XMAX = - XMIN YMAX = - XMIN ZMAX = - XMIN XBORDR = 0. YBORDR = 0. ISMAX = 2 C 60 READ (2, 70, END=120) ANAME, NPTS 70 FORMAT(1X, A4, I5) READ (2, 80) (X(J), Y(J), Z(J), J = 1, NPTS)

9.7. SOURCE LISTING FOR Z-BUFFER

153

80 FORMAT(9F8.0) DO 100 J = 1, NPTS XMIN = AMIN1(X(J), XMIN) XMAX = AMAX1(X(J), XMAX) YMIN = AMIN1(Y(J), YMIN) YMAX = AMAX1(Y(J), YMAX) ZMIN = AMIN1(Z(J), ZMIN) ZMAX = AMAX1(Z(J), ZMAX) 100 CONTINUE GO TO 60 120 XYMAX = AMAX1(XMAX-XMIN, YMAX-YMIN) * 1.01 SFX = (640. - XBORDR) / XYMAX SFY = (350. - YBORDR) / XYMAX SFZ = 9000. / (ZMAX - ZMIN) C C C

READ THE DATA. REWIND 2 REWIND 4 150 READ (2, 70, END=165) ANAME, NPTS IC = 2 IF (ANAME.EQ.’S1 ’) IC = 0 IF (ANAME.EQ.’S3 ’) IC = 0 IF (ANAME.EQ.’S2 ’) IC = 1 IF (ANAME.EQ.’S4 ’) IC = 1 IF (ANAME.EQ.’S5 ’) IC = 3 IF (ANAME.EQ.’S6 ’) IC = 3 IF (ANAME.EQ.’WATE’) IC = 5 READ (2, 80) (X(J), Y(J), Z(J), J = 1, NPTS)

C C C

COMPUTE THE COLOR. CALL SHADE(ISMAX, ISHADE) IF (ISHADE.LT.0) GO TO 150 ICOLOR = JCOLOR(IC * 2 + ISHADE)

C C C C

SCALE THE (X, Y) COORDINATES TO RASTER UNITS. THE MINIMUM AND MAXIMUM Y RASTER UNIT. IYMIN = 10000 IYMAX = 0 DO 160 I = 1, NPTS IX = (X(I) - XMIN) * SFX + XBORDR + 1.5 XB(I) = IX IY = (Y(I) - YMIN) * SFY + YBORDR + 1.5

ALSO, COMPUTE

CHAPTER 9. HIDDEN LINES/SURFACES REMOVAL

154

YB(I) = IY IZ = (Z(I) - ZMIN) * SFZ + .5 ZB(I) = IZ IYMIN = MIN0(IYMIN, IY) IYMAX = MAX0(IYMAX, IY) 160 CONTINUE C C C

WRITE THE RESULTS TO A SCRATCH FILE. WRITE (4) NPTS, (XB(I), YB(I), ZB(I), I = 1, NPTS), & IYMIN, IYMAX, ICOLOR GO TO 150

C C C

DO 25 ROWS AT A TIME. 165 CALL UBACKG(’BLUE’) IY1 = 1 IY2 = 25 IOFF = 0

C 170 REWIND 4 C C C

PAINT EACH POLYGON. DO 190 I = 1, 640 DO 180 J = 1, 25 IZBUF(I, J) = 0 180 CONTINUE 190 CONTINUE

C C C

READ THE RESULTS FROM THE SCRATCH FILE. 200 READ (4, END=220) NPTS, (XB(I), YB(I), ZB(I), I = 1, NPTS), & IYMIN, IYMAX, ICOLOR

C C C

FILL THE FRAME BUFFER. IF ((IY1.GT.IYMAX).OR.(IY2.LT.IYMIN)) GO TO 200 JY1 = IYMIN IF (IY1.GT.IYMIN) JY1 = IY1 JY2 = IYMAX IF (IY2.LT.IYMAX) JY2 = IY2 CALL FRAME(JY1, JY2, IOFF) GO TO 200

9.7. SOURCE LISTING FOR Z-BUFFER C C C

PAINT THE BUFFER. 220 CALL PAINT(1, 640, IY1, IY2, IOFF)

C IY1 = IY1 + 25 IF (IY1.GT.349) GO TO 310 IY2 = IY2 + 25 IF (IY2.GT.349) IY2 = 349 IOFF = IOFF + 25 GO TO 170 C 310 CALL UBELL CALL UPAUSE CALL UEND CLOSE (2) CLOSE (4) STOP END SUBROUTINE FLINE(IX1, IX2, IY, Z1, SLZ, ICOLOR) C C C C C C

THIS SUBROUTINE DOES THE Z BUFFER COMPUTATION FOR THE LINE (IX1, IY, Z1) - (IX2, IY, Z1 + SLZ * X).

COMMON /ZBUFF/ IZBUF(640, 25) C IF (IX1.LT.IX2) THEN ZST = Z1 KX1 = IX1 KX2 = IX2 SL = SLZ ELSE ZST = FLOAT(IX2 - IX1) * SLZ + Z1 KX1 = IX2 KX2 = IX1 SL = - SLZ ENDIF C C = - 1. DO 100 IX = KX1, KX2 C = C + 1. IZ = C * SL + ZST + .5

155

CHAPTER 9. HIDDEN LINES/SURFACES REMOVAL

156

IZ1 = MOD(IZBUF(IX, IY), 10000) IF (IZ.GE.IZ1) IZBUF(IX, IY) = ICOLOR * 10000 + IZ 100 CONTINUE C RETURN END SUBROUTINE FRAME(JY1, JY2, IOFF) C C C C C C

THIS SUBROUTINE PLACES THE POLYGON DEFINED BY THE SET OF (X, Y, Z) COORDINATES INTO A Z BUFFER.

COMMON /QGCS/ XMIN, YMIN, ZMIN, SFX, SFY, SFZ, XBORDR, YBORDR COMMON /POLYG/ X(100), Y(100), Z(100), XB(100), YB(100), & ZB(100), NPTS, IYMIN, IYMAX, ICOLOR DIMENSION XS(10), ZS(10) C C C

CONSIDER EACH HORIZONTAL RASTER LINE. DO 700 N = JY1, JY2

C YN = N NN = N - IOFF NOS = 0 C C C

GET INTERSECTIONS FROM THE POLYGON AND THE LINE Y = YN. DO 500 I = 1, NPTS

C C C

TEST ONE LINE SEGMENT AT A TIME. IP1 = I + 1 IF (IP1.GT.NPTS) IP1 = 1 X1 = XB(I) Y1 = YB(I) Z1 = ZB(I) X2 = XB(IP1) Y2 = YB(IP1) Z2 = ZB(IP1)

C C C C C

CHECK FOR A HORIZONTAL LINE. PLOT IT IF IT IS ON THE CURRENT RASTER LINE; OTHERWISE, GO TO THE NEXT LINE SEGMENT.

9.7. SOURCE LISTING FOR Z-BUFFER IF (Y1.NE.Y2) GO TO 200 IF ((Y1.NE.YN).OR.(X1.EQ.X2)) GO TO 500 IX1 = X1 IX2 = X2 SLZ = (Z2 - Z1) / (X2 - X1) CALL FLINE(IX1, IX2, NN, Z1, SLZ, ICOLOR) GO TO 500 C C C C C C

COMPUTE S. IF 0 < S < 1, AN INTERSECTION EXISTS, SO KEEP THE INTERSECTION POINT. PARALLEL LINES CAUSE A PROBLEM. TO COMPENSATE FOR THIS, KEEP S = 1 INTERSECTION POINTS IF Y1 > Y2 AND KEEP S = 0 INTERSECTION POINTS IF Y1 < Y2. 200 S = (YN - Y1) / (Y2 - Y1) IF ((S.LT.0.).OR.(S.GT.1.)) GO TO 500 IF ((Y1.LT.Y2).AND.(S.EQ.0.)) GO TO 500 IF ((Y1.GT.Y2).AND.(S.EQ.1.)) GO TO 500 IXNEW = (X2 - X1) * S + X1 + .5 XNEW = IXNEW IZNEW = (Z2 - Z1) * S + Z1 + .5 ZNEW = IZNEW

C C C

KEEP THE NEW X VALUES IN ASCENDING ORDER. NOS = NOS + 1 XS(NOS) = XNEW ZS(NOS) = ZNEW IF (NOS.EQ.1) GO TO 500 JL = NOS - 1 DO 300 J = 1, JL JJ = NOS - J JJP1 = JJ + 1 IF (XS(JJP1).GE.XS(JJ)) GO TO 500 XX = XS(JJP1) XS(JJP1) = XS(JJ) XS(JJ) = XX ZZ = ZS(JJP1) ZS(JJP1) = ZS(JJ) ZS(JJ) = ZZ 300 CONTINUE

C 500 CONTINUE C C C

PLOT THE LINE SEGMENTS.

157

CHAPTER 9. HIDDEN LINES/SURFACES REMOVAL

158

IF (NOS.EQ.0) GO TO 700 ILAST = NOS - 1 DO 600 I = 1, ILAST, 2 IX1 = XS(I) IP1 = I + 1 IX2 = XS(IP1) IF (IX1.EQ.IX2) GO TO 600 SLZ = (ZS(IP1) - ZS(I)) / (XS(IP1) - XS(I)) CALL FLINE(IX1, IX2, NN, ZS(I), SLZ, ICOLOR) 600 CONTINUE C 700 CONTINUE C RETURN END SUBROUTINE PAINT(IX1, IX2, IY1, IY2, IOFF) C C C C C

THIS SUBROUTINE PAINTS THE Z BUFFER.

COMMON /ZBUFF/ IZBUF(640, 25) C DO 200 IY = IY1, IY2 C IC = 0 C DO 100 IX = IX1, IX2 C IC1 = IZBUF(IX, IY-IOFF) / 10000 IF (IC1.NE.0) THEN IF (IC.EQ.0) THEN CALL COLOR(IC1) CALL GCSPEN(IX, IY, 0) IC = IC1 ELSE IF (IC1.NE.IC) THEN CALL GCSPEN(IX-1, IY, 1) CALL COLOR(IC1) CALL GCSPEN(IX, IY, 0) IC = IC1 ENDIF ENDIF ELSE

9.7. SOURCE LISTING FOR Z-BUFFER IF (IC.NE.0) THEN CALL GCSPEN(IX-1, IY, 1) IC = 0 ENDIF ENDIF C 100 CONTINUE C IF (IC1.NE.0) CALL GCSPEN(IX2, IY, 1) C 200 CONTINUE C RETURN END SUBROUTINE SHADE(ISMAX, ISHADE) C C C C C C

THIS SUBROUTINE COMPUTER THE NORMAL VECTOR AND THEN COMPUTES A SHADE RANGING FROM 1 TO ISHMAX.

COMMON /POLYG/ X(100), Y(100), Z(100), XB(100), YB(100), & ZB(100), NPTS, IYMIN, IYMAX, ICOLOR C ISHADE = - 1 AX = 0. AY = 0. AZ = 0. X2 = X(NPTS) Y2 = Y(NPTS) Z2 = Z(NPTS) C DO 150 I = 1, NPTS C X1 Y1 Z1 X2 Y2 Z2 C C C

= = = = = =

X2 Y2 Z2 X(I) Y(I) Z(I)

COMPUTE NORMAL VECTOR BY COMPUTING AREAS. AX = (Z1 + Z2) * (Y1 - Y2) + AX

159

CHAPTER 9. HIDDEN LINES/SURFACES REMOVAL

160

AY = (X1 + X2) * (Z1 - Z2) + AY AZ = (Y1 + Y2) * (X1 - X2) + AZ C 150 CONTINUE C C C

USE COS SQUARED FORMULA. IF (AZ.LE.0.) GO TO 200 SHMX = ISMAX - 1 ISHADE = AZ * AZ * SHMX / (AX * AX + AY * AY + AZ * AZ) + 1.5

C 200 RETURN END

Chapter 10

BIBLIOGRAPHY 1. Anony., Understanding Phigs, Megatek Corporation, 1985. Probably the only book written so far on the newly proposed Phigs standard. 2. Anony., DI-3000 User’s Manual, PVI, Boulder, CO. 1984. Excellent user’s manual for DI-3000 (a CORE implementation) with a very good tutorial and introduction to computer graphics. 3. Anony., GK-2000 User’s Manual, PVI, Boulder, CO 1985. Same comments as above but for PVI’s implementation of GKS. 4. Ammerall, L, Programming Principles in Computer Graphics, J. Wiley & Sons, 1986. Deals with the most essential elements of computer graphics: Analytic Geometry, and Programming. Very good chapter on hidden line elimination, and numerous sample programs written in C. 5. Van Dam, A., Computer Software for Graphics, Scientific American, Sept. 1984. General introduction to Computer Graphics which appeared in a special issue of Scientific American. 6. Baxes, G.A., Digital Image Processing, Prentice-Hall, 1984. Good introductory book on image processing. 7. Dewey, B.R., Computer Graphics for Engineers, Harper & Row, 1988. A brief and concise technical treatment of most of the fields of computer graphics written primarily for Engineers. 8. Enderle, G., Kansy, K., and Pfaff, G., Computer Graphics Programming, GKSThe Graphics Standard, Springer-Verlag, Berlin, 1984. Probably the best and most extensive reference on the newly adopted international standard for Graphics GKS. The ”bible” for every serious GKS programmer. Interesting chapter on the evoluation of the standard. 9. Foley, J.D., and Van Dam, A.,Fundamentals of Interactive Computer Graphics, Adison-Wesley, 1983. 161

162

CHAPTER 10. BIBLIOGRAPHY ”Classical” reference on graphics. Special emphasis on the CORE proposed standard with numerous program listings in Pseudo-Pascal. Detailled discussion of hardware implementation.

10. Foley, J.D., Van Dam, et al., second edition, 1990 Most rigorous and comprehensive reference on Computer Graphics 11. Gasson, P.C., Geometry of Spatial Forms, Ellis Horwood, 1983. A very thorough and complete reference for 3D analytical geometries. Contains many useful formulae. 12. Haber, R.N., Flight Simulation, Scientific American, July 1986. Discusses the application of computer graphics to pilot training through flight simulators. 13. Harrington, S., Computer Graphics, A Programming Approach, McGraw-Hill, 1983. Clear coverage of Computer Graphics which parallels the CORE proposed Standard with numerous algorithms. 14. Harris, D., Computer Graphics and Applications, Chapman and Hall, 1984. Simple and concise coverage of graphics hardware, 2D and 3D graphics transformation, GKS, and special applications. 15. Hearn, D., and Baker, M.P., Computer Graphics, Prentice-Hall, 1986. General survey of all major components of Computer Graphics, includes some PASCAL codes. 16. Hopgood, F.R.A., Duce, D.A., Gallop, J.R., and Sutcliffe, D.C., Introduction to the Graphical Kernel System ‘G.K.S.’, Academic Press, 1983. The ”other” classical reference to GKS if you are after a simple introductory text. 17. Mortenson, M.E., Geometric Modeling, J. Wiley & Sons, 1985. Extensive mathematical treatment of curves surfaces and solids definitions, and their relational properties, transformations and intersections. 18. Newman, W.M., and Sproul, R.F., Principles of Interactive Computer Graphics, McGraw-Hill, 1979. Extensive coverage on the fundamentals of computer graphics. ”Classical” (but outdated) reference. 19. Peitgen, H.O., and Richter, P.H., The Beauty of Fractals, Images of Complex Dynamical Systems, Springer-Verlag, 1986. Detailled discussion of fractal representation of complex dynamical systems. Also included are numerous color illustrations with their underlying process, parameter choice, and window of displayed variables (for duplication on your own computer). 20. Pena, M.A., and Patterson, R.R., Projective Geometry and its Applications to Computer Graphics, Prentice Hall, 1986.

163 What is typically one or two chapters in most computer books, is expanded into a rigorous and detailled coverage of analytic projective geometry as a sub-discipline of Computer Graphics. 21. Peitgen, H.O., and Richter, P.H., The Beauty of Fractals, Springer-Verlag, 1986. This book provides not only a thorough and rigorous introduction to fractals, but also shows how they can be easily generated throough simple computer programs. It also provides a very useful table of processes, parameters, and windows for the display of each of its numerous figures. 22. Raker, D., and Rice, H., Inside AUTO-CAD, New Riders Publishing, 1985. A teaching guide to the Auto-CAD microcomputer design and drafting program which has emerged as the most widely used system in its field of application. 23. Rivlin, R., The Algorithmic Image, Microsoft Press, 1986. A very good non-technical introductory book on computer graphics, very readable, with excellent overview coverage. Very good treatment of various components of rendering. 24. Rogers, D.F., and Adams, J.A., Mathematical Elements for Computer Graphics, McGraw-Hill, 1976. A classical reference on the mathematics associated with two and three dimensional transformations, plane and space curves, and surface description. Numerous numerical examples. 25. Rogers, D.F., Procedural Elements for Computer Graphics, McGraw-Hill, 1985. Excellent reference for the fundamentals of computer graphics and its implementation on a raster device. Major sections on Clipping, Hidden Lines and Surfaces, and Rendering. Includes numerous numerical examples, flowcharts, and ”pseudo-codes” for some of the major algorithms. 26. Sproul, R.F., Sutherland, W.R., and Ullner, M.K., Device-Independent Graphics, McGraw Hill, 1986. Discusses grahics hardware, and software (GKS). Last two parts deal with geometry and raster graphics. Includes listing of numerous sample programs in FORTRAN for the IBM PC with a Professional Graphics Adapter. Note: It is unfortunate that you will find very few, if any, of those books in the Engineering Library, as those which have been acquired by the University are housed in the Math-Physics library along with the Graphics Journals and Conference proceedings.