1. Tutorial on picking
2. gasket3dl.c gasket3 with a display list. On my S10 netbook, it's twice as fast.
3. pickdepth.c picking and name list.

1. AngelCG10.ppt Geometry. Most interesting points:
   1. Points vs vectors (in this context):
      1. A point is a position.
      2. A vector is a delta, a displacement or change from one point to another.
   2. Parametric representation of line
      1. given 2 endpoints: {$ P(t)=t A + (1-t) B $}
      2. given one point and the direction (tangent) {$ P(t) = A + tD $}
   3. Parametric representation of plane, given 3 points: {$ P(u,v)= A + u(B-A) + v(C-A) $}
   4. Parametric representations of curves and surfaces are important later.
   5. Normal to plane: {$ N = (B-A)\times (C-A) $}. The length of N is probably not 1, so you'll then need to normalize it.
2. AngelCG11.ppt Representation. Interesting points:
   1. Points in space don't need coordinates. E.g., you might name them. However, you need coordinates to work with them mathematically.
   2. You can imagine a fixed universal coordinate system.
   3. However, you can work with different coordinate systems for the same points. E.g., for an airplane:
      1. you might measure in meters from the nose with z pointing back, or
      2. in feet from the center of the wings with z pointing up, or
      3. ...
   4. You define a coordinate system by specifying (in terms of the universal coordinate system)
      1. its origin, and
      2. the directions of its 3 axes.
   5. If you know the coordinates of a point in one system, you can compute its coordinates in another.
   6. Homogeneous coordinates - big and important topic.
3. My note on homogeneous coordinates and projections demoed by Albrecht Durer.

1. Note that term project proposal is due Fri.
2. AngelCG12.ppt Transformations
   1. Each type of transformation is a matrix.
   2. If applying several transformations, faster to first multiply the matrices, then just multiply all the points by that one matrix.
3. AngelCG13.ppt Transformations 2

1. My note on 3D rotation
   1. all rigid transformations in 3D that don't move the origin have a line of fixed points, i.e., an axis, that they rotate around.
   2. deriving the vector formula for a rotation given the axis and angle
   3. computing the matrix from a rotation axis and angle
   4. testing whether a matrix is a rotation
   5. if it is, then finding the axis and angle
2. Bill Jacobs' OpenGL video tutorial - excellent

1. The big unsolved problems in (or using) CG (and related tech) (my view):
   1. Using CG to control complicated systems
      1. Augmented reality, haptics
   2. Using CG to understand large and complicated systems and data sets
   3. Using CG and videogame techniques to improve learning.
      1. Games force interaction, and provide small immediate rewards.
      2. It's like tossing fish to seals at Sea World.
      3. How to use those ideas for more effective teaching?
2. (Nothing to do with CG, but very interesting): Designs, Lessons and Advice from Building Large Distributed Systems at Google
3. AngelCG13.ppt OpenGL transformations
   1. Note that the last transformation catenated onto the current matrix is the first transformation applied to the object.
   2. (Unless I hear objections) I'll defer quaternions until later (if there's time).
   3. More info is in chapter 4.
4. AngelCG14.ppt Model Building
   1. This topic becomes ever more important as your models get bigger.
   2. The goal is to store large models in a more organized way, and then render them with fewer function calls.
   3. We start to see the separation of geometry from topology.
   4. A goal is to represent one piece of info, such as a vertex location, only once.
   5. Another goal is to store things that change more often (geometry), separately from things that don't (topology).
5. AngelCG15.ppt Classical viewing
   This IMHO is largely obsolete. However you should recognize the terms. ''Vanishing points'' is useful for drawing perspective objects by hand.
6. AngelCG16.ppt Computer viewing
   1. There are utility routines to help specify the camera and projection.
   2. The big idea is view normalization or projection normalization. We want to view the object with our desired perspective projection. To do this, we transform the object into another object that looks like an amusement park fun house (all the angles and lengths are distorted). However, the default parallel projection of this normalized object gives exactly the same result as our desired perspective projection of the original object. Therefore, we can always clip against a 2x2x2 cube, and project thus: (x,y,z)->(x,y,0) etc.
      More info is in Angel, page 270 and the next slide set.
7. Reading: Chapter 5.

1. AngelCG17.ppt Projection matrices
2. AngelCG18.ppt Shading I
   1. The big idea is the Phong shading model.
3. AngelCG19.ppt Shading II
   1. We start to get into OpenGL specifics.

This is not CG, but is interesting enough to go to. There will be no exam questions on this.

Dynamic Instrumentation for Application Security and Analysis

Modern applications, with dynamically-loaded modules and dynamically-generated code, are assembled at runtime. Consequently, the power and reach of static analysis tools are diminishing. In this talk, I will present DynamoRIO, a general framework for efficient, fine-grained, and comprehensive code observation and modification entirely at runtime. DynamoRIO is a flexible platform for creating dynamic tools in areas including program analysis, introspection, profiling, auditing, trace gathering, taint tracking, optimization, translation, and more. Tools built with DynamoRIO operate on unmodified application binaries on commodity hardware. I will discuss in detail several particular tools, including a system for providing strong security guarantees during program execution. Dubbed Program Shepherding, it turned into a successful, award-winning commercial security product.

Bio:
Derek Bruening leads the Advanced Development Tools team at VMware. Prior to VMware, he co-founded the security company Determina, which commercialized the Program Shepherding security system based on DynamoRIO. Determina was acquired by VMware in August 2007. Derek holds a PhD, MEng, and BS from MIT, where he was the primary author of DynamoRIO.

The DynamoRIO tool platform was first released to the public in June 2002 and has since been used by many researchers to develop systems ranging from taint tracking to prefetch optimization. DynamoRIO is now publicly available in open source form at dynamorio.org.

Host: Ana Milanova (x6887)

Wednesday, October 28, 2009
CII (LOW) 3051 - 4:00 p.m. to 5:00 p.m.

1. AngelCG20.ppt Shading in OpenGL
2. cubeview.c. Shows smooth shading the faces of a cube, and rotating it. See Angel 5.10.
3. sphere.c. Shows 3 modes of shading a sphere with different levels of accuracy.
4. shadow.c. Shows how to create a shadow onto a flat surface by projecting the object onto that surface. See Angel 5.10.
5. tutors_src.zip. Nate Robbins's light tutorial.

Reading: Angel 5.10, 6.

1. Computer graphics in the real world (enrichment only)
   1. Forma Urbis Romae - reconstruction of a street map of 211AD Rome from 1186 pieces like this one:
      
2. Another OpenGL tutorial The Practical Physicist's OpenGL tutorial Edward S. Boyden
3. Steve Baker's notes on some graphics topics:
   1. GL_MODELVIEW vs GL_PROJECTION
   2. basic OpenGL lighting
   3. Euler angles are evil
   4. Smooth Shading 'Gotcha's in OpenGL
4. AngelCG21.ppt Implementation I - Rasterization, Clipping

We now change from learning the API to studying how things are implemented under the API.

1. Advantage of using Cohen-Sutherland line clipping.
   1. You still have to include the code for the detailed clipping since sometimes the CS algorithm reports that it doesn't know.
   2. However often it can classify the line segment (or the box with everything inside) as either completely in or else completely out.
   3. In that case, the rest of the pipeline is faster.
   4. However you have to write more lines of code.
   5. You don't have to know how this works, only what its purpose is.
2. AngelCG22.ppt Implementation II - Clipping, Visibility
   1. clipping as a pipeline
   2. clipping concave polygons can break them into pieces
   3. tesselating concave polygons - breaking them into triangles - is common
   4. some visibility (aka hidden surface) algorithms iterate through the objects, others iterate through the pixels.

1. Properties of the various visibility methods:
   1. Painters:
      1. Sorting the faces is hard and maybe impossible. Then you must split some faces.
      2. However sometimes some objects are always in front of some other objects. Then you can render the background before the foreground.
   2. Z-buffer:
      1. Subpixel objects randomly appear and disappear (aliasing).
      2. Artifacts occur when objects are closer than their Z-extent across one pixel.
      3. This happens on the edge where two faces meet.
   3. BSP tree:
      1. In 3D, many faces must be split to build the tree.
2. Bresenham presents the fast line and circle drawing algorithms better than the text.
3. For more info on testing whether a point is in a polygon, see my note. Also see the comp.graphics.algorithms FAQ, question 2.03.
4. The flood fill will fail if the interior is not connected. That happens when two close edges cause adjacent pixels to be set. It will also fail if there is a gap in the perimeter - the color will leak out.
5. The scan line fill must handle special cases like a vertex being on a scan line. My solution is to pretend that any vertex on a scan line is really slightly above. This is a simple case of a serious technique called ''Simulation of Simplicity'' invented by Herbert Edelsbrunner.
6. One problem with interpolating color inside a polygon is that you may be creating successive frames of a video. Then, the color must be consistent from frame to frame even as the object is moving.
   E.g. if a quadrilateral rotates, it may be triangulated differently depending on its orientation. The two different triangulations may get shaded differently.
7. Anti-aliasing is a big and important topic.
8. Bresenham circle algorithm.
9. AngelCG23.ppt Implementation III, ctd

Reading: chapter 7.

1. AngelCG24.ppt Buffers
2. OpenGL and images:
   1. Following the less is more design philosophy, OpenGL has no facilities for reading and writing image data to disk. It does let you bitblt data between its buffers and your arrays. Otherwise, use your choice of tools.
   2. Netpbm is a large set of standalone command line programs for processing and converting image files.
      These programs follow the Unix pipe metaphor, and can be chained together.
   3. Imagemagick is another large set of standalone command-line programs for mogrifying images.
   4. You can run any standalone program from inside your C program with the system call. The only way to get info back and forth between that program and your program is via a file. It is dangerous to run system with an argument partly supplied by the user unless you thoroughly check for metachars. That, in a slightly different context, is the flaw exploited by the SQL injection attack on RFID tags.
   5. xv is a nice interactive shareware program, which I used in class today. I actually bought 2 licenses years ago.
   6. PPM (portable pixmap) is a file format that is so simple you can easily write programs to read or write it. Its files are big, but you can use one of the other above systems to convert. I showed this in class, and Angel's slides also do.
3. AngelCG25.ppt Texture mapping
   The hard problems with texture mapping are:
   1. Determining what texel in the texture map corresponds to each pixel in the frame buffer. The involves inverting some complicated mappings.
   2. That the pixel in the frame buffer is rarely the same size as the corresponding texel, but may be much larger or smaller. That varies with the distance of the object from the camera. Solutions include various smoothing techniques, and using a hierarchy of texture maps of different resolutions.
4. AngelCG26.ppt OpenGL Texture mapping

Reading: chapter 8.

1. tutors_src.zip. Nate Robbins's tutorials (ctd).
   1. fog
   2. texture
2. http://nehe.gamedev.net/data/lessons/lesson.asp?lesson=06 another nice and very detailed texture programming tutorial, from Neon Helium productions
3. http://gpwiki.org/index.php/OpenGL_Tutorial_Framework:Texture_Mapping
4. AngelCG27.ppt Compositing and blending
5. AngelCG28.ppt Programmable pipelines
6. AngelCG29.ppt GLSL I

1. AngelCG30.ppt GLSL II
2. Vertex and fragment shaders from chapter 17 of the OpenGL SuperBible.
3. AngelCG39.ppt Curves and surfaces in OpenGL

1. Now we have a few days on HW (vertex and fragment) shaders. I'll teach with examples from the excellent Open GL SuperBible. See also http://www.pdf-search-engine.com/the-opengl-superbible-pdf.html. The example programs are here.
   # GPUs:
   1. Wikipedia:Graphics_processing_unit
   2. Wikipedia:Radeon_R700
   3. http://ati.amd.com/products/radeonhd4800/overview-4890.html
   4. http://www.anandtech.com/printarticle.aspx?i=3354
   5. http://hardware.slashdot.org/article.pl?sid=09/04/02/193256
   6. http://www.extremetech.com/article2/0,2845,2344294,00.asp
   7. http://www.phoronix.com/scan.php?page=article&item=amd_radeon_hd4890&num=1
   8. http://www.gpureview.com/
2. GPGPU:
   1. http://www.gpgpu.org/
   2. http://graphics.stanford.edu/%7Ekayvonf/papers/fatahalianCACM.pdf - A closer look at GPUs
   3. http://gates381.blogspot.com/
   4. http://graphics.stanford.edu/~kayvonf/official/index.html
   5. http://s08.idav.ucdavis.edu/
   6. http://s08.idav.ucdavis.edu/luebke-nvidia-gpu-architecture.pdf
   7. http://s08.idav.ucdavis.edu/luebke-cuda-fundamentals.pdf
3. Wikipedia on shaders:
   1. Wikipedia:Shader
   2. Wikipedia:Vertex_shader
   3. Wikipedia:Geometry_shader
   4. Wikipedia:Pixel_shader
   5. Wikipedia:Unified_shader_model
   6. Wikipedia:Shading_language
   7. Wikipedia:OpenGL_Shading_Language
   8. Wikipedia:Comparison_of_OpenGL_and_Direct3D
4. GPU Programming For The Rest Of Us Note the matrix multiplication example.

1. Please email Kalyana with your preferred date (Dec 8 or 9) for your fast forward talk on your term project. We will put as many people as possible on their preferred date. Your team needs to talk only once, not once per person.
2. SIGGRAPH 91 and 92 preliminary programs. This is a bowdlerized version, from whence I have removed items that might give offense.
3. Raytracing jello brand gelatin
4. Shader examples from chapters 16 etc of the OpenGL SuperBible. Local Linux version including executables. Other versions linked above on Nov 20.

Bill Hoffman from Kitware talking in class on Tues Dec 1 about CMake/VTK/ITK/ParaView/Kitware, e.g. VTK.

Go to the IP panel at 4:15 in DCC (aka Darrin) 324.

This is only enrichment since it's not in the official class time. If you can, go to the Image Space Photon Mapping talk (see the google calendar) at 4pm in JEC3117

"The computer-generated 3D graphics in films like Terminator 4 are visually indistinguishable from real objects. They are hard to compute, however; the Photon Mapping algorithm used in most film productions requires about one day to compute every second of film. Our new Image Space Photon Mapping transforms that algorithm to a space where it can be evaluated in a fraction of a second. This enables nearly cinema- quality lighting for interactive applications like video games. We recently..."

1. AngelCG31.ppt Hierarchical Modeling I
2. AngelCG32.ppt Hierarchical Modeling II
3. AngelCG33.ppt Graphical Objects and Scene Graphs
4. AngelCG34.ppt Particle Systems

1. Remember the IDEA survey.
2. OpenGL Design tradeoffs and notes
3. Review, including old finals.

Final exam. 11:30-2:30.

1. Syllabus and Intro.
2. AngelCG01.ppt: What is Computer Graphics?

Reading:

1. Angel, chapter 1.

Announcements:

1. Homework 1 available.

In lab: work on homework, or go to the Carter financial talk.

1. Chapter 1. The progress of Computer Graphics is largely the progress of hardware. We'll see more of this later. However, here's an intro.
   1. What physical principles are each type of HW based on?
      1. CRT: certain rare earth materials emit photons when hit by electrons. Explaining this is what got Einstein his Nobel (not relativity).
      2. LCD: electric field causes big asymmetric molecules to untwist so that they no longer rotate polarized light passing through them.
   2. What engineering challenges required solving?
      1. Shadow-mask CRT: electron beams travel varying distances at different angles, but don't hit the wrong phosphor even as the system gets hotter. The precision is 0.1%.
      2. Hi-performance graphics requires hi bandwidth memory.
      3. Virtual reality headsets require knowing where your head is and its angle (harder).
   3. What tech advances enabled the solutions?
      1. Raster graphics requires cheap memory.
      2. LCD panels require large arrays of transistors.
2. AngelCG02.ppt: Image Formation
3. AngelCG03.ppt: Models and Architectures

Simple2


Simple3


Simple4


Simple5

1. Engineering Grounded In Reality
2. A little on API philosophy, e.g, Portability And Standards, and submarine patents.
3. AngelCG04.ppt: Programming in OpenGL I
4. simple2.c - simplest OpenGL program. Features:
   1. including required include file
   2. initializing OpenGL
   3. creating a top level window of default size and position
   4. setting window title
   5. defining and registering a display callback
   6. entering the main event loop
   7. clearing the frame (aka color) buffer to a default color (black)
   8. drawing a polygon with the default color (white)
   9. forcing pipeline to flush
   10. compiling and linking
5. simple3.c - slightly bigger OpenGL program
   1. setting vertex colors and observing polygon color
   2. overlapping polygons
6. my Makefile - YMMV

Reading:

1. Angel, chapter 2.

Announcements:

1. To compile the OpenGL examples in Visual C: If you get a redefinition error for exit, then do not include stdlib.h in your program. It is already included by another include file, and it lacks an inclusion guard.
2. Homework 1 is due Wed Sep 9.
3. Homework 2 now available, due Sep 16.
4. simple4.c - modification created in class to add another polygon that obscures the polygons below it (this also happened with simple3).
5. simple5.c - modification created in class to put glVertex in a for loop.

Shape_test

Topics:

1. AngelCG05.ppt: Programming in OpenGL II
2. Demo, discuss, and modify shape_test.c. New features:
   1. OpenGL datatypes like GLfloat
   2. Allocate and enable depth (aka Z) buffer
   3. Perspective view
   4. Several utility polyhedra
      1. sphere, cone, cube, torus, dodecahedron, teapot, octahedron, icosahedron
      2. wire or solid
   5. Light source and color
   6. Enabling and disabling lighting
   7. Reshape callback
   8. Push and pop transformation matrix
   9. Rotate, scale, translate transformations
   10. Using viewport to draw into a small region of the window. Anything outside the viewport is clipped.

Reading:
Announcements:

Gasket2


Gasket3

Topics:

1. AngelCG06.ppt: Programming in OpenGL III
2. Demo, discuss, and modify gasket2.c . Features:
   1. Array of vertices passed to glVertex2fv
   2. Array of triangles
   3. Recursively creating the graphic object
   4. glBegin and glVertex2fv are in different routines. It's the order in which they are executed that matters, not their order in the source file.
   5. Parallel (ortho) projection.
3. Demo, discuss, and modify gasket3.c . Features:
   1. 3D.
   2. Spec colors in an array.
   3. Reshape callback. It handles rectangular windows, keeping the tetrahedra undistorted, with the same aspect ratio, centered in the window.. Portrait and landscape mode are separate cases.
   4. glPostRedisplay

Announcements:

1. Homework 3 available, due Sep 23.

Topics:

1. AngelCG07.ppt: Input and interaction
2. Demo, discuss, and modify alpha.c . Features:
   1. color a triangle with a partially-transparent color, which, when drawn into the color buffer, will mix (blend) with the existing color.
   2. enable blending in OpenGL.
3. Demo, discuss, and modify paint.c . Features:
   1. keyboard callback
      1. write the key at a position stored in a global and update that
   2. mouse callback
   3. accumulating info, such as triangle vertices, from successive callbacks
   4. converting coords from what is passed to mouse callback (origin is top left corner) to what is used by openGL window (origin is bottom left corner)
   5. picking a region of window by analyzing coords of mouse click.
   6. immediate mode: on redisplay, if it's not explicitly redrawn, it's not there any more.
   7. colors as unsigned bytes.
   8. using globals to pass data to/from callback routines.
   9. menus
      1. create
      2. add entry
      3. add submenu
      4. attach to mouse button
   10. menu callback
       1. arg is the int key associated with that menu entry
   11. pushing and popping attributes
   12. writing text
       1. setting position
       2. writing char
       3. updating position by width of char

1. passivemotion.c. Changes the image depending on where the mouse is, using a mouse passive motion callback.
2. passivemotion2.c. Extends passivemotion to redraw only when something changes. This prevents the image tearing caused by redrawing during the refresh. It's also more efficient.
3. single_double.c. Shows:
   1. The difference between single and double buffering.
   2. Creating two graphics windows in one program. Note the order:
      1. Set the display mode.
      2. Create the window.
      3. Register the callbacks.
      4. Repeat for each window.
      5. Call MainLoop.
   3. Mouse input.
   4. Changing the idle callback. The new one replaces the previous one.
4. getinfo.c. Shows how to read information about the OpenGL version and how to get internal state variables. This also shows how to access command line arguments. This shows just a sample; there are more.
5. showinput.c. Shows how to get input. This also shows the coordinate system used to report mouse events. Units are pixels.

      (0,0) ...... (xmax,0)
      ....
      ....
      ....
      (0,ymax).....(xmax,ymax)  
   
6. Beyond double buffering: How to avoid tearing caused by swapping the foreground and background buffers in the middle of refreshing the image and the two buffers have different images?
   1. One solution is to wait until the vertical retrace to swap the buffers. However, if each buffer takes about 1/60 second to recompute, sometimes more and other times less, then the refresh rate will fluctuate between 1/60 and 2/60 second.
   2. Another solution is to use 3 buffers. You display from the 1st, have the 2nd ready to swap with the 1st in the next vertical retrace, and meanwhile compute into the 3rd. This uses 50% more memory.
   3. How to fight tearing
   4. OpenGL Extension WGL_I3D_swap_frame_lock
   5. Smooth Gaming with Triple Buffering
7. AngelCG08.ppt more on callbacks

Reading: Angel, chapter 3.
Announcements:

1. Homework 4 available, due Oct 2.

Steve Linthicum, Manager
Innovation Engineering
GE Health Care IT

Rex Roeges, Technology Account Manager
Software Technology Progream
GE Health Care IT

Innovation Electric develops new products and tools for the health care environment using cutting edge technologies. The STP recruits top graduates in Computer Science and Computer Engineering for a 3-year program to develop top engineering talent in medical infomatics.

GE Health Care IT is a major application of Computer Graphics and interactive techniques, and is a major employer.

1. OpenGL platform dependencies:
   1. On some systems, such as my (expensive) Lenovo w700 laptop at home, both windows of single_double look the same. Presumably those systems have better graphics. They look different on the cheap Lenovo s10 laptop that I use in class.
   2. On some systems again like my w700, paint's screen does not clear when you hide and the expose the window. That is because the windowing system is storing the window's contents, so that the program does not have to redraw the window. However, I think that popping up a program menu still clears the window. Please report any counterexamples.
2. Debugging OpenGL: The OpenGL FAQ and Troubleshooting Guide can be useful.
3. more OpenGL reference material:
   1. I've been using the OpenGL Programming Guide, 6th edition. ($42 from Amazon. The 5th edition is online free. The differences are small. My mirror of the demo programs is Gfiles:OpenGL-1.4-ProgGuide.tgz .
   2. The OpenGL(R) SuperBible: Comprehensive Tutorial and Reference (4th Edition) ($51 from Amazon) is also excellent.
   3. So is Angel's OpenGL Tutorial, which is smaller.
4. square2.c. Demonstrates glutMotionFunc callback. Change glutMotionFunc to glutPassiveMotionFunc to see what happens.
5. manywindows.c. Shows that many top level windows (a new one with each left mouse click) can be dynamically created.
6. paintxor.c modified by paint.c to write triangles into the color buffer in XOR mode. Everything else is still written in COPY mode. XOR mode is useful for cursors and rubberbanding because XORing the same object twice restores the original buffer.
7. feedback.c. Captures drawn objects, after transforming them, into an array instead of drawing them.
8. AngelCG09.ppt Better interactive programs. The problem is finding what in your hierarchical 3D object that's been transformed corresponds to the mouse position. This is harder because you may have a tree of objects of subobjects. Think of a fleet of cars, each with 4 wheels, each with 5 lug nuts. It's not sufficient to know that you clicked on a nut. You need to know that you clicked on nut #2 of wheel #3 of car #17. That's where the name stack comes in.