Graphics and Visualization (GV)
Computer graphics is the term commonly used to describe the computer generation and manipulation of images. It is the science of enabling visual communication through computation. Its uses include cartoons, film special effects, video games, medical imaging, engineering, as well as scientific, information, and knowledge visualization. Traditionally, graphics at the undergraduate level has focused on rendering, linear algebra, and phenomenological approaches. More recently, the focus has begun to include physics, numerical integration, scalability, and special-purpose hardware, In order for students to become adept at the use and generation of computer graphics, many implementation-specific issues must be addressed, such as file formats, hardware interfaces, and application program interfaces. These issues change rapidly, and the description that follows attempts to avoid being overly prescriptive about them. The area encompassed by Graphics and Visual Computing (GV) is divided into several interrelated fields:
- Fundamentals: Computer graphics depends on an understanding of how humans use vision to perceive information and how information can be rendered on a display device. Every computer scientist should have some understanding of where and how graphics can be appropriately applied and the fundamental processes involved in display rendering.
- Modeling: Information to be displayed must be encoded in computer memory in some form, often in the form of a mathematical specification of shape and form.
- Rendering: Rendering is the process of displaying the information contained in a model.
- Animation: Animation is the rendering in a manner that makes images appear to move and the synthesis or acquisition of the time variations of models.
- Visualization. The field of visualization seeks to determine and present underlying correlated structures and relationships in data sets from a wide variety of application areas. The prime objective of the presentation should be to communicate the information in a dataset so as to enhance understanding
- Computational Geometry: Computational Geometry is the study of algorithms that are stated in terms of geometry.
Graphics and Visualization is related to machine vision and image processing (in the Intelligent Systems KA) and algorithms such as computational geometry, which can be found in the Algorithms and Complexity KA. Topics in virtual reality can be found in the Human Computer Interaction KA.
This description assumes students are familiar with fundamental concepts of data representation, abstraction, and program implementation.
GV. Graphics and Visualization (2 Core-Tier1 hours, 1 Core-Tier2 hours)
| Core-Tier1 hours | Core-Tier2 hours | Includes Electives | |
| GV/Fundamental Concepts | 2 | 1 | Y |
| GV/Basic Rendering | Y | ||
| GV/Geometric Modeling | Y | ||
| GV/Advanced Rendering | Y | ||
| GV/Computer Animation | Y | ||
| GV/Visualization | Y |
GV/Fundamental Concepts
[2 Core-Tier1 and 1 Core-Tier2 hours]
For nearly every computer scientist and software developer, an understanding of how humans interact with machines is essential. While these topics may be covered in a standard undergraduate graphics course, they may also be covered in introductory computer science and programming courses. Part of our motivation for including immediate and retained modes is that these modes are analogous to polling vs. event driven programming. This is a fundamental question in computer science: Is there a button object, or is there just the display of a button on the screen? Note that most of the outcomes in this section are at the knowledge level, and many of these topics are revisited in greater depth in later sections.
Topics:
[Core-Tier1]
- Media applications including user interfaces, audio and video editing, game engines, cad, visualization, virtual reality.
- Digitization of analog data, resolution, and the limits of human perception, e.g., pixels for visual display, dots for laser printers, and samples for audio (HCI Foundations)
- Use of standard APIs for the construction of UIs and display of standard media formats (see HCI GUI construction).
- Standard media formats, including lossless and lossy formats
[Core-Tier2]
- Additive and subtractive color models (CMYK and RGB) and why these provide a range of colors
- Tradeoffs between storing data and re-computing data as embodied by vector and raster representations of images
- Animation as a sequence of still images
[Elective]
- Double buffering.
Learning Outcomes:
[Core-Tier1]
- Identify common uses of digital presentation to humans (e.g., computer graphics, sound). [Familiarity]
- Explain in general terms how analog signals can be reasonably represented by discrete samples, for example, how images can be represented by pixels. [Familiarity]
- Explain how the limits of human perception affect choices about the digital representation of analog signals. [Familiarity]
- Construct a simple user interface using a standard API. [Usage]
- Describe the differences between lossy and lossless image compression techniques, for example as reflected in common graphics image file formats such as JPG, PNG, MP3, MP4, and GIF. [Familiarity]
[Core-Tier2]
- Describe color models and their use in graphics display devices. [Familiarity]
- Describe the tradeoffs between storing information vs. storing enough information to reproduce the information, as in the difference between vector and raster rendering. [Familiarity]
[Elective]
- Describe the basic process of producing continuous motion from a sequence of discrete frames (sometimes called “flicker fusion”). [Familiarity]
- Describe how double-buffering can remove flicker from animation. [Familiarity]
GV/Basic Rendering
[Elective]
This section describes basic rendering and fundamental graphics techniques that nearly every undergraduate course in graphics will cover and that are essential for further study in graphics. Sampling and anti-aliasing are related to the effect of digitization and appear in other areas of computing, for example, in audio sampling.
Topics:
- Rendering in nature, e.g., the emission and scattering of light and its relation to numerical integration.
- Forward and backward rendering (i.e., ray-casting and rasterization).
- Polygonal representation.
- Basic radiometry, similar triangles, and projection model.
- Affine and coordinate system transformations.
- Ray tracing.
- Visibility and occlusion, including solutions to this problem such as depth buffering, Painter’s algorithm, and ray tracing.
- The forward and backward rendering equation.
- Simple triangle rasterization.
- Rendering with a shader-based API.
- Texture mapping, including minification and magnification (e.g., trilinear MIP-mapping).
- Application of spatial data structures to rendering.
- Sampling and anti-aliasing.
- Scene graphs and the graphics pipeline.
Learning Outcomes:
- Discuss the light transport problem and its relation to numerical integration i.e., light is emitted, scatters around the scene, and is measured by the eye. [Familiarity]
- Describe the basic graphics pipeline and how forward and backward rendering factor in this. [Familiarity]
- Create a program to display 3D models of simple graphics images. [Usage]
- Derive linear perspective from similar triangles by converting points (x, y, z) to points (x/z, y/z, 1). [Usage]
- Obtain 2-dimensional and 3-dimensional points by applying affine transformations. [Usage]
- Apply 3-dimensional coordinate system and the changes required to extend 2D transformation operations to handle transformations in 3D. [Usage]
- Contrast forward and backward rendering. [Assessment]
- Explain the concept and applications of texture mapping, sampling, and anti-aliasing. [Familiarity]
- Explain the ray tracing/rasterization duality for the visibility problem. [Familiarity]
- Implement simple procedures that perform transformation and clipping operations on simple 2-dimensional images. [Usage]
- Implement a simple real-time renderer using a rasterization API (e.g., OpenGL) using vertex buffers and shaders. [Usage]
- Compare and contrast the different rendering techniques. [Assessment]
- Compute space requirements based on resolution and color coding. [Assessment]
- Compute time requirements based on refresh rates, rasterization techniques. [Assessment]
GV/Geometric Modeling
[Elective]
Topics:
- Basic geometric operations such as intersection calculation and proximity tests
- Volumes, voxels, and point-based representations.
- Parametric polynomial curves and surfaces.
- Implicit representation of curves and surfaces.
- Approximation techniques such as polynomial curves, Bezier curves, spline curves and surfaces, and non-uniform rational basis (NURB) spines, and level set method.
- Surface representation techniques including tessellation, mesh representation, mesh fairing, and mesh generation techniques such as Delaunay triangulation, marching cubes, .
- Spatial subdivision techniques.
- Procedural models such as fractals, generative modeling, and L-systems.
- Graftals, cross referenced with programming languages (grammars to generated pictures).
- Elastically deformable and freeform deformable models.
- Subdivision surfaces.
- Multiresolution modeling.
- Constructive Solid Geometry (CSG) representation.
Learning Outcomes:
- Represent curves and surfaces using both implicit and parametric forms. [Usage]
- Create simple polyhedral models by surface tessellation. [Usage]
- Generate a mesh representation from an implicit surface. [Usage]
- Generate a fractal model or terrain using a procedural method. [Usage]
- Generate a mesh from data points acquired with a laser scanner. [Usage]
- Construct CSG models from simple primitives, such as cubes and quadric surfaces. [Usage]
- Contrast modeling approaches with respect to space and time complexity and quality of image. [Assessment]
GV/Advanced Rendering
[Elective]
Topics:
- Solutions and approximations to the rendering equation, for example:
- Distribution ray tracing and path tracing
- Photon mapping
- Bidirectional path tracing
- Reyes (micropolygon) rendering
- Metropolis light transport
- Time (motion blur), lens position (focus), and continuous frequency (color) and their impact on rendering
- Shadow mapping
- Occlusion culling
- Bidirectional Scattering Distribution function (BSDF) theory and microfacets
- Subsurface scattering
- Area light sources
- Hierarchical depth buffering
- The Light Field, image-based rendering
- Non-photorealistic rendering
- GPU architecture
- Human visual systems including adaptation to light, sensitivity to noise, and flicker fusion
Learning Outcomes:
- Demonstrate how an algorithm estimates a solution to the rendering equation. [Assessment]
- Prove the properties of a rendering algorithm, e.g., complete, consistent, and unbiased. [Assessment]
- Analyze the bandwidth and computation demands of a simple algorithm. [Assessment]
- Implement a non-trivial shading algorithm (e.g., toon shading, cascaded shadow maps) under a rasterization API. [Usage]
- Discuss how a particular artistic technique might be implemented in a renderer. [Familiarity]
- Explain how to recognize the graphics techniques used to create a particular image. [Familiarity]
- Implement any of the specified graphics techniques using a primitive graphics system at the individual pixel level. [Usage]
- Implement a ray tracer for scenes using a simple (e.g., Phong’s) BRDF plus reflection and refraction. [Usage]
GV/Computer Animation
[Elective]
Topics:
- Forward and inverse kinematics
- Collision detection and response
- Procedural animation using noise, rules (boids/crowds), and particle systems
- Skinning algorithms
- Physics based motions including rigid body dynamics, physical particle systems, mass-spring networks for cloth and flesh and hair
- Key-frame animation
- Splines
- Data structures for rotations, such as quaternions
- Camera animation
- Motion capture
Learning Outcomes:
- Compute the location and orientation of model parts using an forward kinematic approach. [Usage]
- Compute the orientation of articulated parts of a model from a location and orientation using an inverse kinematic approach. [Usage]
- Describe the tradeoffs in different representations of rotations. [Assessment]
- Implement the spline interpolation method for producing in-between positions and orientations. [Usage]
- Implement algorithms for physical modeling of particle dynamics using simple Newtonian mechanics, for example Witkin & Kass, snakes and worms, symplectic Euler, Stormer/Verlet, or midpoint Euler methods. [Usage]
- Discuss the basic ideas behind some methods for fluid dynamics for modeling ballistic trajectories, for example for splashes, dust, fire, or smoke. [Familiarity]
- Use common animation software to construct simple organic forms using metaball and skeleton. [Usage]
GV/Visualization
[Elective]
Visualization has strong ties to Human Computer Interaction as well as Computational Science. Readers should refer to the HCI and CN KAs for additional topics related to user population and interface evaluations.
Topics:
- Visualization of 2D/3D scalar fields: color mapping, isosurfaces.
- Direct volume data rendering: ray-casting, transfer functions, segmentation.
- Visualization of:
- Vector fields and flow data
- Time-varying data
- High-dimensional data: dimension reduction, parallel coordinates,
- Non-spatial data: multi-variate, tree/graph structured, text
- Perceptual and cognitive foundations that drive visual abstractions.
- Visualization design.
- Evaluation of visualization methods.
- Applications of visualization.
Learning Outcomes:
- Describe the basic algorithms for scalar and vector visualization. [Familiarity]
- Describe the tradeoffs of visualization algorithms in terms of accuracy and performance. [Assessment]
- Propose a suitable visualization design for a particular combination of data characteristics and application tasks. [Assessment]
- Analyze the effectiveness of a given visualization for a particular task. [Assessment]
- Design a process to evaluate the utility of a visualization algorithm or system. [Assessment]
- Recognize a variety of applications of visualization including representations of scientific, medical, and mathematical data; flow visualization; and spatial analysis. [Familiarity]