ECSE 6800
Advanced 3D Graphics & Visualization
RPI, Spring 2004

Note: Many of the links that were valid when this page was created have since rotted.

Table of Contents

New entries are at the top. This is updated by hand and so might be obsolescent at times.

1. CS seminar: Multiresolution and Discrete Models as Foundations for Scalable Simulation, March 30
2. Direct X, OpenGL and Misc; for March 22
3. Homework 3 Due Mar 22
4. Project Ideas
5. Thu Mar 18 class replaced by CS talk
6. Chandra Narayanaswami's talk rescheduled to Apr 22
7. Fast HW
8. Stereographs
9. Linear Programming
10. Voronoi diagrams
11. Convex Hulls
12. Tight COCONE
13. Bring me your point clouds
14. Due Dates
15. Homework 2 Due Date
16. Class Schedule
17. JPEG
18. MPEG
19. NTSC Video Compression
20. Resolutions of Early Monitors
21. New Scientist on Colors
22. Syllabus
23. Student Presentations
24. Term Project
25. Course Subjects (Tentative)

Term Paper Presentations

Misc Announcements

• Google Copernicus Center is hiring
• IBM announces the Virtual Universe Operating System - OS/VU

Homework 3 Due Mar 22

You may do this work in teams of up to 2 people.

1. If you have a rotation of 180 degrees about the X-axis, followed by a rotation of 180 degrees about the Y-axis, what are the axis and angle of the combined rotation? Use quaternions.
2. Now find the combined rotation if the two rotations are applied in the opposite order.
3. In 9-dimensional (Euclidean) space, how much time would the best known convex hull algorithm take to process N points?
4. In 9-dimensional (Euclidean) space, how much time would the best known Voronoi diagram algorithm take to process N points?
5. In the following figure, which points are depth 1, depth 2, depth 3, depth 4, and depth 5? Depth is described in Preparata & Shamos.
6. Pick one of Curtis Priem's patents, and describe it.
7. Give me a title and 100 words on your term project.

Project Ideas

If you're still searching for ideas, check out some of the things I'm thinking of, here.

Yes, thinking of ideas is hard. However it's a very useful skill. E.g, that's what I do for each proposal that I write to try to raise money. It's what you would do before talking to a venture capitalist.

Thu Mar 18 class replaced by CS talk

Chandra Narayanaswami coming April 22

Chandra Narayanaswami's visit has been rescheduled, to Thurs Apr 22. He'll be speaking at 3:30 in DCC 324. That replaces the class that day. I encourage everyone to attend.

Bring me your point clouds

On Feb 23, I'll be discussing Tight COCONE, which fits a surface to a point cloud. In preparation for that, if you like, send me a point cloud or two. The format is one point per line:

x1 y1 z1
x2 y2 z2
...

Due Dates

Homework 2 Due Feb 19

1. JPEG quality vs accuracy
   1. Pick a photographic-like image you like, which has a hi technical quality, like 24 bit color, but with only about 100 rows and columns.
   2. Convert it to jpeg at several different quality levels.
   3. Make a website showing the different versions, and the image sizes in bits per pixel (bpp).
   4. What do you think is the minimum acceptable bits per pixel?
   5. Repeat this with an image of text.
   6. Optionally, graph the average intensity difference as a function of bpp.

   Note: Use anything you like; I would do this with xv, and/or netpbm.

2. MPEG quality vs accuracy
   1. Look at the frames of my union of cubes video, here.
   2. Encode them repeatedly into mpegs at varying quality levels and sizes. I used ppmtompeg with this parameter file. If you prefer, you may use another tool.
   3. What's the minimum bits/pixel/frame that you find acceptable for that example?
   4. In what way does the video look bad as the quality falls?
   5. Put the videos on a website for me to see.
   6. OptionalRepeat this with an example of your choosing.

3. From: http://www.eskimo.com/~billb/amateur/holo1.html.

   HAND-DRAWN HOLOGRAMS!
   (c)1995 William J. Beaty
   

   I've stumbled across a technique for drawing holograms directly upon a plastic plate by hand. It sounds crazy, but I've been sitting on the livingroom sofa making holographic images of floating polyhedra, words, 3D starfields, etc. No laser, no isolation table, no darkroom, no expensive film plates. This takes nothing more than a compass and some scraps of black plexiglas. Too cool, if I say so myself!.....

   This homework problem is to try to make a hand-drawn hologram, bring it to class, and report on your success. I don't know how well it works, but that's the nature of research.

4. Start thinking about your Term Project.

   Give me an idea (or more if you're uncertain) of what you want to do.

IAEA Internship Available

(Not related to this course).

(formerly http://www.bnl.gov/ispo/Internship/internship.htm) Spend a year in Vienna. The deadline is RSN.

Homework 1 Due Feb 3

1. Suppose you combine these 2-D transformations:
   1. Translate by (1,2).
   2. Rotate by 90 degrees. I.e. (1,0) -> (0,1).
   3. Translate by (3,4).
   4. Rotate by -90 degrees.

   This is equivalent to one translation (x,y) followed by one rotation by angle t. What are they?

   I have not discussed this at all, so use your creativity, and any legal method. If almost no one gets it, then we'll cover it in class.

2. Review the SIGGRAPH course #33 notes, including the parts I skipped, and anything else you like, and answer these questions:
   1. Why should red and blue not be used directly together?
   2. With NTSC, do saturated colors come out well or not?
   3. What is the Mach band effect?
   4. What is the difference between kinematics and dynamics in animation?
   5. How is the rendering equation related to nuclear physics?
   6. Is raytracing or radiosity better at modeling lenses?
   7. Is raytracing or radiosity better at modeling surfaces with diffuse reflection?
3. Make a creative video MPEG in POVRAY. Put it in the web, perhaps in a protected place, and give me the URL.

Due Jan 27

Each person please email me a ranked list of 4 research labs you'd like to review, and 4 dates. I'll pick two for each person, giving priority to the earlier email.

Class Schedule

• (available) means that this date is still available for a 10 minute student presentation.

• The lecture date is often linked to a copy of the notes that I wrote during the lecture.

Direct X, OpenGL and Misc; for March 22

1. official MS site
2. 5star on 9.0b summary
3. Brian Clair FAQ (4 yr old) - good summary comparing versions
4. another good summary comparing versions
5. (formerly at: http://thetechnozone.com/pcbuyersguide/software/system/DirectX8.html) TechZone PC buyers guide on 8.0
6. MS: Introducing the New Managed Direct3D Graphics API in the .NET Framework
7. figures for previous page
8. MS: Introduction to the DirectX 9 High-Level Shader Language (HLSL). Excellent.
9. MS: GDI+ - links to good overview and ref
10. (brief) summary of direct x
11. MS FAQ
12. MS on OpenGL
13. Real-Time Rendering - book extracts and many links to other books. Excellent.
14. Craig Andera's Managed Direct3D Tutorial
15. Andy Pike's DirectX 8 Tutorials
16. Direct3D vs OpenGL
17. OpenGL and X - excellent
18. Basic OpenGL Operation
19. opengl.org
20. OpenGL HW registry
21. What's New in OpenGL 1.5
22. MS Steve's Computer Graphics Index. Excellent.

Fast Hardware

1. Curtis Priem, RPI'82 is co-founder of Nvidia. He has 88 patents.
2. KarbosGuide to video systems
3. Ray Tracing on Programmable Graphics Hardware
4. High Performance Graphics Hardware Design Requirements
5. 3D Graphics Hardware in Linux
6. MMX etc
7. Intel i815 chipset
8. Pentium 4
9. Intel 845PE chipset
10. 845GE
11. Intel extreme graphics
12. busses
13. busses
14. graphics card
15. VRAM
16. Video cards in general
17. karbosuide AGP
18. webopedia AGP
19. pcguide AGP
20. intel AGP
21. intel AGP
22. SGI on OpenGL
23. MS DirectX
24. Tom's HW on ATI Mobility Radeon 9700
25. Beyond 3D on HW Geometry Processing

Stereographs

This is a nice 3D technique, whose basis is this:

There are many programs to make stereographs. On linux, the xstereograph rpm is good.

Here are some samples.

Voronoi Diagrams

1. Demo applet that lets you move points.
2. Higher order Vor applet
3. SUNY Stony Brook's Excellent summary.
4. Size: for N points in d-D, the size can be proportional to N^ceil(D/2). I.e., 2D=>N. 3D=>N².
5. Construction, 2D:
   1. Divide and conquer: Build a Voronoi diagram on the left N/2 points and anoter on the right N/2 points. Sew them together. T=NlogN.
   2. Steve Fortune's sweepline method is the best code.
6. Qhull is perhaps the best higher dimensional code. Matlab and Mathematica use it.
7. Preparata & Shamos is one of the best books on this.
8. Voronoi diagrams are closely linked to convex hulls.
   1. If you have a Voronoi diagram in d-D, you can easily find the convex hull of those same points in d-D.
   2. If you know how to find a convex hull in (d+1)-D, you can find a Voronoi diagram in d-D.

      E.g., If your 2-D points are (x,y), then find the convex hull of the 3-D points (x,y,x²+y²). The adjacent points on the 3-D convex hull correspond exactly to the adjacent points in the 2-D Voronoi diagram.

   3. Therefore, I'll cover convex hulls first.
9. (formerly http://www.ifor.math.ethz.ch/staff/fukuda/polyfaq/polyfaq.html) Frequently Asked Questions in Polyhedral Computation

Convex Hulls

1. Convex hull applet
2. SUNY Stony Brook on convex hulls.
3. Good ref: Preparata & Shamos.
4. Methods:
   1. Divide & conquer
   2. Graham scan. See Princeton's animation.
   3. Jarvis march. See Princeton's animation.
   4. qhull. See Princeton's animation.

Tight COCONE

Tamal Dey's Tight COCONE program takes an unstructured point cloud and fits a water-tight surface, regardless of how badly spaced the points are. The algorithm is described in these papers: cocone, tcocone.

The executables and test files are here.

Since COCONE's algorithm was designed by someone who knows a lot of Computational Geometry, I'll summarize the hilites in class.

I will be displaying the output with geomview.

A lot of data is at Stanford, tho it has to be converted from their ply format. Some local copies are here

JPEG

1. 8x8 blocks
2. rotate color space from RGB to perhaps YUV emphasize intensity, since people see intensity more accurately than hue.
3. downsample color planes
4. transform to a discrete cosine series (like a Fourier series but using step functions)
5. drop hi-freq components
6. encode the coefficients with as few bits as possible, using Huffman code or similar
7. =>lossy

ref: comp.compression Frequently Asked Questions

MPEG

1. Predict the motion from frame to frame.
2. I (intra) frames: still images
3. P (predicted) frames: difference from previous I or P.
4. B (bidirectional) frames: interpolate from closest I or P on each side.
5. Typical sequence: IBBPBBPBBPBBIBBPBBPB...

NTSC video compression

This is worth learning as an excellent example of electrical engineering.

1. Specification requirement:
   1. Add color to B&W NTSC.
   2. Upward compatible.
   3. Downward compatible.
2. Useful properties:
   1. People see color info less precisely than B&W info.
   2. People see blue-yellow color less precisely than red-green.
   3. In typical images, a scan-line is much the same as the previous one.
3. Engineering implications:
   1. We can lo-pass filter the color.
   2. The fourier transform of the intensity looks like a comb.
4. Solutions:
   1. Rotate (R,G,B) to (Y,I,Q).
   2. Lo-pass filter I to 2/3 of normal bandwidth.
   3. Lo-pass filter Q to 1/3.
   4. Combine: I cos omega t + Q sin omega t, or something like that.
   5. Shift the combined color signal up in frequency by 1/2 the frequency of one scan-line and add to the Y.
5. Limitations:
   1. Sudden intensity changes cause false color aliases.
   2. Vice-versa.
   3. Color changes that are not filtered properly are especially bad.
   4. Interference causes phase changes causes color shift.
6. Solution: HDTV.

One good TV ref is http://www.howstuffworks.com/tv.htm

Resolutions of Early Monitors

This is an excellent example of engineering design. It's an edited post from johana!tsw@apple.com (Tom Watson) to alt.folklore.computers on 27 Apr 92 23:13:32 GMT.

The reason for the 16x64 character resolution for early personal computers was that you could use 512 bit shift registers (that were common in that day). Usually everyone used 80 columns (look at an ADM-3) and the reason for 24 rows was that usually the character generators were 5x7 dots and with a few dots for inter-line spacing (total of 9 dots/line) one got 216 scan lines for 24 rows. This fit just fine into NTSC monitors that used 265.5 (interlaced, remember) lines/field (the difference was used for blanking). The reason for 40 character displays was again a limiting function of TV's with 5 dots across (add a couple for nice spacing) we get 7 dots.

If one uses 80 characters we get 560 dots across the line. In normal TV scan lines the horozontal rate is 63.5 (about) microseconds and taking the fact that the max frequency is with alternating white and black dots (total of 280 transitions) and that gives a frequency of about 5Mhz (can't use all of the 63.3 usec due to blanking). Since TVs have a video bandwidth of only 4MHz (on a good day), that is too much, so everyone used 40 characters/line to get in proper bandwidth of a TV. If they added color, it really was necessary, since the color bandwidth was even less (1.25MHz for NTSC TV).

Now days color monitors with .31mm dot pitch high bandwidths (over 15 MHz) and high scan rates (31Khz horizontal, 70 Hz vertical) are very common, but then again they don't use NTSC composite video. The original displays were almost always TV's, or TV monitors since they were CHEAP!!

On the other hand, some early CRT display terminals used vector displays, and stroke character generators. BIG horizontal and BIG vertical yoke amplifiers. Video bandwidth wasn't a big problem then, but 300 watt 1MHz yoke amplifiers were!!

New Scientist on Colors

This was from a page at www.newscientist.com that appears not to be online anymore.

Q: I was taught at school that the three primary colours are red, blue and yellow and that by mixing these, all the other colours could be made. If you look closely at a television screen, you can see that the picture is made up of red, blue and green dots. Why and how do televisions use these colours and how, for instance, do they make yellow from them?

A: Televisions start with a black screen and add coloured light. Painters start with white paper and add paint which serves to remove colours from the reflected light. The television uses additive colours, so called because adding more makes the image brighter. Painting uses subtractive colours and works in the opposite way.

As you might expect, the two systems complement each other. Adding yellow and blue paints together gives green, which is an additive primary colour. Conversely, yellow light can be made out of red and green light.

Here's where the fun starts. The subtractive primaries are technically yellow, cyan (an intense light blue similar to sky blue) and magenta (a kind of purple). True red paint can be made from yellow and magenta paint. The problem is that it is difficult to get a really good magenta, and so artists end up using red instead of magenta. Although this precludes being able to mix a good, clean magenta, it is rare to find one in the environment anyway, so it's not missed. However, without magenta, it is difficult to make a good, deep blue from cyan and so ultramarine is used instead. The effect of this is that green is now difficult to create, and so bright green is used. So really, although artists claim to use yellow, blue and red, they in fact use a couple of reds, yellow, green, blue, a large tube of white, black, and often an assortment of tertiaries. Painting is an engineered solution.

Syllabus

Student Presentations

Each person will present two 10-minute talks in class, one on some current topic related to the course, and one summarizing another research lab. Pick a topic and a date.

Research labs to talk about:

1. Brown University - Computer Graphics Group (Stephen Bourdeau)
2. U North Carolina - Graphics and Image Analysis Research (Metin Inanc)
3. Duke - Visualization Technology Group (Metin Inanc)
4. U Texas/Austin - Graphics Lab, Department of the Computer Sciences, (David Bang)
5. U Washington - Computer Graphics, Computer Vision and Animation (David Millman)
6. Microsoft - Research - Graphics (Samson Chu)
7. IBM Research - Graphics & Visualization (Christian Vogt)
8. Caltech - Computer Graphics and Multi-Res Modeling. (Al Barr is an RPI alum.) (Micky Chiang)
9. U Waterloo - Computer Graphics Lab (David Bang)
10. Georgia Tech - Graphics, Visualization & Usability Center, including Animation Lab (David Millman)
11. Ohio State - Computer Graphics Research, Computer Animation, Geometric Modeling, & Volume Visualization (still available)
12. ICASE - Visualization and Graphics. This lab has closed, but it's still interesting. (still available)
13. Stanford - Computer Graphics Lab (Stephen Bourdeau)
14. UC Berkeley - Multimedia, Human Computer Interaction and Computer Graphics (Samson Chu)
15. UC Santa Cruz - Lab for Visualization and Graphics (still available)
16. U Utah - Computer Graphics (Eric Wharton)
17. U Geneva - MIRAlab (Christian Vogt)
18. MIT (Micky Chiang)
19. Pixar (still available)
20. Raindrop Geomagic (still available)
21. Any other interesting place - you pick. (still available)

Hardware to talk about

Ideas to talk about:

1. (still available)
2. (still available)
3. (still available)
4. (still available)
5. (still available)

Term Project

1. Write a 10 page paper in an academic style on any topic even vaguely related to the course. It could be either
   1. research,
   2. implementation, or
   3. survey.
   Format it reasonably, with abstract, refs, etc.
2. Give a 15 minute talk in class, to be followed by 5 minutes of questions. Use visual aids, such as HTML, powerpoint, or wimpypoint.

   Email me to reserve a slot to present your talk on April 19, 22, or 25.

3. Teams are ok.
4. Combining with another course is ok, if you tell everyone concerned.
5. Building on existing work is ok, if you tell me.

Course Subjects (Tentative)

I modify these based on class feedback.

1. 3d rotations - use matlab, maple, quaternions
2. video formats (NTSC etc)
3. hidden surface removal algs
4. http://www.cc.gatech.edu/gvu/multimedia/nsfmmedia/cware/graphics/notes/vsdet/hisel/hisel00.html
5. SIG2 advanced global illumination (read: course notes)
6. SIG3 developing efficient graphics sw (read: course notes)
7. SIG9 simulating nature (read course notes)
8. SIG21 digital color (read course notes)
9. IG25 Blinn Tensor diagrams
10. Preparata & Lee paper: