Jacquelyn Ford Morie

Note: Please give feedback on the Taxonomy to Jacquelyn Ford Morie (Morie_at_siggraph_dot_org).

DESCRIPTION

This project will define a relational taxonomy of Computer Graphics concepts, covering not only the breadth of topics pertaining to Computer Graphics Imaging (CGI) but also considerable depth within in each of the topic areas inventoried.
The taxonomy includes basic and advanced CG concepts that are pertinent across many disciplines, from art to engineering.

The taxonomy, as presented here, is a first draft at what is hoped to become a comprehensive taxonomy, especially in terms of depth.
CGI is a multi-faceted discipline—based as it is on diverse areas such as mathematics, engineering, physics, art and design, just to mention a few more notable ones.
The primary goal of this taxonomy project will be to solicit and include a wide range of additional input from experts in CGI, as well as ACM SIGGRAPH Education Committee (ASEC) members, so the taxonomy can be as complete as possible.

Within the taxonomy many topics have pointers to related areas or subjects that are essential to most uses of that topic but which are outside the scope of this taxonomy.
Much more input is requested in completing the range of these internal and external topic pointers.

The end goal of this project is to provide a tool for educators and CGI practitioners alike to facilitate their usage and understanding of a wide range of CGI topics. One of the ultimate uses of this taxonomy project, besides the educational ones listed below, will be to serve as the framework for the SIGGRAPH Education Committee's Digital Library project (ASEC Digital Library). This NSF-funded project, headed up by Scott Owen, will be the repository for an online, accessible common body of educational materials for CGI and Visualization: this CGI Taxonomy will provide the searchable database index for a large part of the ASEC Digital Library.

It is important to note that this project represents only one approach for organizing these concepts into a coherent whole. We acknowledge that there are many, many ways of organizing these concepts. This specific organization is presented, not as a primary or ultimate organization, but as a working framework that educators can use to see how topics relate and fit together, and as an index for the ASEC Digital Library. As an evolving index, topics will continue to be added. Other uses of this taxonomy will depend on the specific goals of the educators using this information, but some suggestions are noted within the GOALS section that follows.

GOALS

The goals of this project include (for teachers, students as well as life-long learners):

• Compiling a comprehensive and relational listing of the concepts of CGI in one document that can serve as a index to a wide range of curricular and reference materials
• Providing a tool for educators to plan their future courses/curricula, as well as evaluate what they are covering in their current classes
• Presenting related topics that supplement or enhance the computer graphics concepts, especially in professional contexts
• Allowing educators and learners to see what concepts they might want to learn more about within a given area
• Enabling a dialog between educators and prospective employers in many fields to determine essential background training needed to support specific job skills

SCOPE OF PROJECT

Phase 1: Initial Draft of Taxonomy

Phase 2: Seek advice and input from a variety of experts in CGI on the following:

• Inclusion of additional topics (ensure completeness)
• Correctness of topic placement
• Specification of related concepts outside the taxonomy
• Relational pointers within the taxonomy

Phase 3: Solicit advice from ASEC members for the above list.

• Place reviewed taxonomy on web site for Phase 4.
• Taxonomy at this stage is also ready to be used as the framework for the Digital Library Project.

Phase 4: Request for educators to “wrap” curriculum around the taxonomy, for specific curricula (art, science, math, animation, etc.)

• On a per-class basis specify each section (both depth and breadth) from taxonomy that is covered.
• Request for any additional “related competencies” for sections
• Specific resources or reference materials
  (articles, papers, books, videos) for each topic

Phase 5: Present final Project at SIGGRAPH 2001.
(panel/course/workshop or other Conference venue)

SUGGESTED SCHEDULE

Phase 1:	Initial Draft Presented to ASEC	April 2000
Phase 2:	Initial Review and Feedback from Experts	July 2000
Phase 3:	ASEC Review & Discussion Taxonomy ready for Digital Library Database Post Taxonomy on ASEC web site; Announce at SIGGRAPH	SIGGRAPH 2000
Phase 4:	Descriptive Article in CG/Call for Input	Fall 2001
	Collection of Data from Web posting	Fall/Winter 2002
Phase 5:	Compilation of Results	Spring 2002
	Presentation of Results (to committee and at Conference)	SIGGRAPH 2002

I. Hardware

A. Input

1. Bit-based
1. Switches
2. Punched tape
3. Magnetic tape
2. Alpha-numeric (keyboards)
3. Valuator Dials
4. Light Pens
5. 2D Data Capture
1. Tablets
2. Scanners
3. Video Boards
6. 3D Data Capture
1. 3D Positional
1. Point-Based
2. Joint Angle Based (Armatures, Monkeys)
3. Sketch-Based
2. Video Capture Methods
1. Grid Projections
2. Others
3. Laser Methods
1. Cyberscan (need generic name)
2. LIDAR (dopler-assisted)
7. 4D Data Capture
1. Motion Trackers
2. Waldos
1. Motion Amplification
2. Distance MotionTransfer
8. Audio Input: Sound, Speech Synthesizors
9. Haptic Input Methods

B. Output

1. Softcopy (monitors/displays)
1. Vector
1. Phosphors
2. Mechanics
   Movement of electron guns, refresh mechanisms
3. DLP (Display List Processor)
2. Raster (CRTs) *Video Technology
1. Phosphors
2. Mechanics
   Shadow masks, electron gun scaning, interlaced vs. non-interlaced
3. Lookup Tables * See also Frame Buffers, Sec. 1 E-1
3. Flat Panel Technologies
1. Gas Plasma
2. LCD
3. LEDs
4. LEP
4. Head Mounted Displays
5. Night-Vision Displays
1. Acoustic-reflected
2. Infrared
6. Volume Display Technologies
1. Laser Displays
2. Holographic Displays
3. Doped Crystal Displays
2. Hardcopy
1. Printers, Plotters
2. *PostScript
3. Film Recorders
4. 2D Cutting Tools
3. Sound
4. MIDI/WAV
5. Other File Formats

3D Output

1. 3D Photographic
2. Additive Rapid Prototyping
1. Stereolithography
2. Sintering
3. LOM (Laminated)
3. Subtractive Rapid Prototyping
1. Numerical Milling Machines
2. Robotic Motion

C. Processors

1. Function

2. Speed

3. Architecture

a) Standard

b) RISC-Based

c) Parallel Architectures

d) Neural Hardware

D. Memory and Storage

1. Comparisons of Memory (RAM) and Storage

2. Online

3. Offline

4. Nearline

E. Special-Purpose Graphics Hardware

1. Frame Buffers

a) Image buffers

b) Z-buffers

c) Alpha-buffers

2. Accelerators

3. DDRs, PARs (Digital disk or personal animation recorders), frame recorders

4. Parallel Processors, Math Co-Processors

5. Graphic or Rendering Hardware Pipelines

II. Software

A. BIOS

B. Operating Systems

C. Programming Languages

1. Low Level

a) Machine Language *Binary, Octal & Hexadecimal

Number Systems

b) Assemblers

2. High Level

a) Interpreted

b) Compiled

3. Application Software

4. Interfaces * Human Factors

a) GUIs

b) APIs

c) Gesture Recognition Interfaces

III. Geometry

A. Coordinate Systems

1. 2D, 3D Cartesian

2. Right and Left Handed Cartesian Axes Systems

3.                  Polar Coordinates

4.                  Hyperbolic Coordinates

5. Homogeneous Coordinates

6. Spherical Coordinates

7. Global, Local

8. UVW (texture or parameter) Coordinate Space

B. Objects

1. Points and Vertices

2. Lines

3. Curves

a) Quadratic Curves

b) Cubic Curves

(1) Splines

(a) General Concepts, History

(b) CVs and Construction of

(c) Continuity

(d) Uses of splines in CG

(2) Approximating

(a) B-Splines

• Description

• Properties

• Mathematics

• Advantages, Disadvantages in usage

(3) Interpolating

(a) Catmull-Rom

• Description

• Properties

• Mathematics

• Advantages, Disadvantages in usage

(4) Tangent-based and Others

(a) Bezier

• Description

• Properties

• Mathematics

• Advantages, Disadvantages in usage

(b) Hermite

• Description

• Properties

• Mathematics

• Advantages, Disadvantages in usage

(c) Kochanek-Bartels

• Description

• Properties

• Mathematics

• Advantages, Disadvantages in usage

(d) Beta

• Description

• Properties

• Mathematics

• Advantages, Disadvantages in usage

(e) Cardinal

• Description

• Properties

• Mathematics

• Advantages, Disadvantages in usage

(5) Rational vs. Non-Rational

(6) Uniform vs. Non-Uniform

(a) Knot s & spacing

(b) NURBS

• Description

• Properties

• Mathematics

• Advantages, Disadvantages in usage

(c) Hierarchical NURBS

• Description

• Properties

• Mathematics

• Advantages, Disadvantages in usage

c) Higher degree curves

4. Primitives

a) 2D Polygonal

(1) Vertex Connectivity

(2) Normals * See also Rendering, Sec. B, 1&2

(a)   True

(b)   Interpolated

(3) Backfaces and Culling

(4) Concave

(5) Convex

b) 3D Polygonal Primitives

(1) Spheres, Cubes, Cones, Cylinders, Torii

5. Surface Models

a) Polygonal Meshes

(1) Specifying Connectivity (Edge-Vertex Schemes)

(a) Edge List

(b) Winged Edge Representations

(2) Other Schemes

(3) Sub-division Surfaces

b) Surfaces of Transformation

(1) Rotation

(2) Translation (Extrusion)

(3) Scaling

(4) Lofting, Skinning, Cross-sectional Modeling

c) Functional Surfaces

(1) Explicit Functions

(a) Parametric Bi-Cubic Spline Patches

• Coons Patches

• Hermite

• Bezier

• B-Spline

(b) Quadric Forms

• Quadrics

• Super Quadrics

(2)               Implicit Functions

(3)               Subdivision Surfaces

6. Solid Models

a) Solids of Transformation

(1) Rotation (Revolution)

(2) Translation (Extrusion)

(3) Scaling

(4) Lofting, Skinning, Cross-sectional Modeling

b) Constructive Solid Geometry

(1) Primitives

(2) Attributes

(3) Boolean Operations

(4) Representational Tree Structure

c) Boundary Representations

d) Decomposition Models

(1) Voxels

(2)               Octree, Quadtree Data Structures

e) Volumetric Surfaces (density functions)* See also Implicit Surfaces, Sec. III B 5 c (2)

7. Generative Processes

a) Fractals

b) Particles * See also Simulations, Sec. VI, G&H

c) L-Systems

d) Genetic Algorithms

C. Levels of Detail in Models

D. Automatic Data Extraction Methods

IV. Display

A. Pixels

1. Internal Representation

2.                  Screen Representation

3.                  Storage * See also Graphic File Formats, Sec. XI, A

B. Spatial systems for CGI

1. Object Space

2. World Space

3. Viewports /Camera Space

4. Screen Space

5. Raster Space

6. Parameter Space (uvw, stu)

C. 3D Camera

D. Visibility Algorithms

1. Visible Surface

2. Hidden Line

3. Depth Buffer

4. Scan Line

5. Priority List

6.                  Space Sub-division

7.                  Ray Tracing

E. Clipping

1. 2D

a) Cohen-Sutherland

b) Liang-Barsky

c) Cyrus-Beck-Liang-Barsky

d) Nichol-Lee Nichol

2. 3D

a) Hither and Yon

F. Projections

1. Perspective

2. Orthogonal

3. Others

V. Transformations

A. Geometric Transformations

1. Matrix Representation

2. Affine Transformations

a) Translate

b) Scale (reflection)

c) Rotate

d) Shear (skew)

3. Non-Affine Transformations

4.                  Structure-Deforming Transformations

a) Taper

b) Twist

c) Bend

5.                  Isotropic and Anisotropic

B. Ordering Transformations

1. Gimbel Lock

2. Euler Angles

3. Quaternions

VI. Animation

A. Definition and General Comparisons to Traditional Animation * 12 Principles of Trad. Animation

B. Scripted Systems

C. Key Framing

1. Time vs. Space Curves

2. Inbetween interpolation

a) Linear, Quadratic, Cubic *See also section XXX on curves

b) Ease-in, Ease-out

(1) Relationship to acceleration. deceleration

c) Continuity *See also section XXX on curves

(1) Manipulations

d) Cycles

e) Dependencies

D. Rotoscoping (as used for Animation)

E. Kinematics

F. Inverse Kinematics

G. Simulation * Physics * Finite analysis

1. Collisons, Avoidances

2. Behavior

3. Dynamics

4. Particle System Simulations

H. Other Procedural Animation Techniques * Control Systems

1. Artificial Life

2. Automonmous Agents

3. Emergent Behaviors

I. Motion Capture

1. Standard

(2)               Realtime

3. Marker-based

4. Surface_based * See also Modeling

5. Video & other markerless systems

6. Automatic vs hand post processing

VII. Resolutions

A. Aliasing

1. Spatial

2. Temporal

3. Color/Tonal *See also sections VIII, esp.E

a) Color Artifacts

b) Mach Bands

B. Anti-Aliasing

1. Sampling Theory (brief) * See also section X:D Image Processing

2. Super-Sampling

2.                  Gupta-Sproul Techniques

4. Resolution independence methods * See also section

VIII. Color

A. Visual Perception of * Color Design Principles

1. Electromagnetic Spectrum

2. Theories of Human Visual Perception * Subjective perception phenomena

B. Models

1. Subtractive

a) RYB (paint)

b) CYMK

2. Additive

a) RGB

3. Relationship of Additive and Subtractive

C. Color Spaces/Specifications

1. CIE

2. YIQ

3. Pantone

4. HSV/HSB/HLS etc.

D. Filters, dyes and other related concepts

E. Color Resolution

1. Color Depth

2. Quantization

a) Log vs. linear schemes

b) Extension Schemes

c) LUTS

IX. Rendering

A. Basic Concepts

1. Goal of Rendering

2. Lighting Components

a) Ambient

b) Diffuse

c) Specular

d) Types of light sources

(1) point, spot, directional, area, sun, etc.

B. Lighting Models

1. Basic Lighting Models

a) Flat, Constant, Faceted, Lambert

b) Gouraud

c) Phong

2. Advanced Shading Models

a) Blinn

b) Torrence-Sparrow

c) Cook-Torrence

3. Global Illumination Models

a) Ray Tracing

(1) Optical Ray Tracing

(2) Backwards Ray Tracing

(3) Cone Tracing

(4) Distributed Ray Tracing

(5) Adaptive Ray Tracing

(6) Photon Maps

(7) Other Ray Tracing Techniques

b) Radiosity

(1) Basic Approach (Classical Radiosity)

(2) Higher Order Radiosity

(3) Iteration techniques

(4) Form Factors

i. Analytic

ii. Numeric

(5) Participating Media

(6) Hierarchical Radiosity

c) Hybrid Approaches

4. Image-based Rendering

5. Volume Rendering

6. Other Rendering Techniques

7. Rendering Tools and Interfaces

C. Texture Mapping

1. Texture Space

2. Uses of

a) Basic 2D Texture

b) Bump Mapping

c) Reflection Mapping

d) 2D Procedural Maps

e) 3D (Solid) Texture Maps

f) Displacement Mapping

g)      Shadow Mappings

3. Existance and Alpha Mapping

D. Increasing Realism

1. Motion Blur

2. Atmospheric Perspective (Attenuation)

3. Depth of Field

4. Caustics

5. Reproducing Film Artifacts

E. Improving Images * See also section VIII: E

1. Dithering

2. Super-Sampling

3. Jittering

X. 2D Techniques

A. Image Processing * Signal Processing

1. Signals and Sampling

a) Analog

b) Discrete

2. Spatial vs Frequency Domain

3. Image Manipulation

a) Convolution

b) Pixel Point Processes

(1) Contrast and Brightness Modification

(2) Gamma Correction

(3) Combination Functions

(a) +, -, x, /, AND, OR, XOR

c) Spatial (Pixel Group) Filters

(1) High Pass, Low Pass

(2) Boundary/Edge Detectors

(a) Shift and Difference

(b) Gradient

(c) Laplacian

(3) Geometric Operations

(a) Transforms

(b) Scaling

d) Fourier Transforms

a) Uses

b) Basic

c) FFT

c) Wavelets

B. Compositing

1. Basic Concepts * See also section X.A.3.

2. Matte Channels (2 bit)

3. Alpha Channels (2bit and higher)

4. Green Screen Techniques

5. Pixel Arithmetic * See also section X.A.3.b

a) Basic Concepts

b) Pre-Multiplied Alpha

c) Global, Local Alpha

d) Correlated, Non-Correlated Edge

6. Tracking (2D, 3D)

7. Rotoscoping

C. Morphing

1. 2D Techniques

2. 3D Techniques

XI. Graphic File Formats

A. 2D Formats

1. Resolution dependent

2. Resolution independent formats

B. 3D formats

1. Geometry * See Geometry, section III

2. Scene Descriptions

C. Animation Files

1.      2D

a) Delta Frame Data

b) Per Frame Data

2.      3D

a) Implicit (motion or script)

b) Explicit (geometry per frame)

D. Compression Techniques

1. RLE, Scan Line Coherence

2. JPEG, MPEG

3. Fractal

4. Wavelet Compression