CPSC 589 - Modeling for Computer Graphics   TA PAGE

The marks for the final assignment have been posted. The average was a little lower than the first two assignments, but overall everyone should be in good shape for the course. If you have a question about your mark, let me know.

This will more than likely be the last post for the semester, so I just want to say thanks to everyone for making it an enjoyable semester for me! I hope you guys learned a lot in the course, and maybe even pursue a further career in graphics. Best of luck finishing your projects!

- Luke

Important - Project Extension
The deadline for submission of your final project package has been extended by two days, to Wednesday, April 25. Hand in the package to Dr. Samavati's office (stick it under the door if no one is there).

Final Review
Some sample final questions have been posted on the class website. I'll cover solutions to those questions some time before the examl on Monday, but the time has yet to be decided.

I can possibly go over solutions tomorrow, but the regular lab time is unavailable. Furthermore, I think it would be more beneficial to you guys to have time to study and attempt the questions yourselves before the review, which I would hazard to guess won't be the case by tomorrow morning.

I will pencil Sunday in for now. If you prefer tomorrow, send me an email by the end of today (Thursday); if enough people ask for a review on Friday, then I will send out an update tomorrow.

As you've probably noticed by now, coding 3D graphics applications in a C++/Qt environment can be a frustrating experience. Most of the problems are due to Qt, which interfaces with C++ in a very unnatural way.

If you continue in graphics development, you may find yourself looking for better alternatives. Of course, there are two main graphics APIs: OpenGL and DirectX. I have experience in both, and would say that OpenGL is far better for any application where the most important consideration is not raw performance.

The flip side is, of course, that DirectX is a highly optimized API built expressly for gaming. If your square rendering task fits exactly into a DirectX hole, then you'll be amazed at how much a single function call can accomplish; if it doesn't, then you'll be dismayed at just how difficult it can be to do what you want.

A not-inconsequential benefit of OpenGL is that there are bindings to its API available for a large number of languages. For coding up a quick demo or prototype, Python + OpenGL is a very powerful combination, that can be used in conjunction with any window manager available to Python.

Another great combination is C# + OpenGL (Tao). The level of library support in C# is fantastic, and you can also use things from DirectX such as vectors, matrices, and quaternions while staying within the comfortable and familiar confines of OpenGL rendering. If you're interested in getting started in this environment, you can start with the simple application linked below, which is similar to the barebones Qt application we've been using all semester.

[C# OpenGL app]

Important! The deadline for Assignment 3 has been extended to Monday, April 9th due to Good Friday. As before, the code should be emailed to me by 11:59pm and the written portion put in the drop box by 4pm.

Covered in lab today:

How to define field functions for implicit primitives. Most often, field functions are based on the minimum distance to the primitive; for example, the field function of a point primitive p at a point q is proportional to the distance between p and q, |p - q|.

In lab, we derived the distance function for a line primitive, based on vector projection. For the line segment defined by p₁ and p₂, a point q will either project onto the line between p₁ and p₂, or outside of the line segment. If it projects between the endpoints, then the minimum distance is equal to the length of the orthogonal component of the projection. If it projects outside of the line segment, then the minimum distance is the distance from q to the closest endpoint.

I also talked about how to render implicit surfaces. For direct rendering, ray tracing is pretty much your only option. For real-time rendering via OpenGL or a similar rasterizing API, you have to first make a discrete representation of the surface. This is done via the Marching Cubes algorithm (in 2D, the algorithm is called Marching Squares; both are covered in the linked page). The basic idea is to partition the object space into voxels (equivalently pixels in 2D), and then evaluate the implicit field function at the vertices of the voxels. Edges/polygons are constructed within voxels that have a mixture of vertices inside and outside of the surface. The original paper is by Lorensen and Cline, and a later paper by Shoeb provided 8 extra disambiguating cases.

Important! Regarding Question 3 of Assignment 3, you might find it useful to rephrase the question as, "Show that bicubic B-spline subdivision of a regular quadrilateral mesh is equivalent to Catmull-Clark subdivision of the mesh." Please send me an email if you are unclear on this question.

Covered in lab today:

Boolean operations on implicit surfaces, as it relates to the third assignment.

Also, I talked a bit about wavelets/multiresolution, and the relationship between decomposition (wavelet transform) and classic least-squares. The important point is that while decomposition can be formulated as a least-squares problem, the fact that subdivision is a local operation means that having a local decomposition process is often desirable; a least-squares approach will yield a global, not a local, decomposition mask.

Covered in lab today:

The quad-edge data structure, as described in the Kettner paper linked below. The quad-edge structure is more complicated than the half-edge structure, but has the advantage of being easy to dualize and being able to represent non-orientable surfaces.

This site has a good discussion of the quad-edge structure from both theoretical and practical viewpoints:

[Quad-Edge library]

Here is a good resource on mesh data structures (half-edge, quad-edge, winged edge):

[Designing a Data Structure for Polyhedral Surfaces]

A common problem encountered when implementing a modeling program is this: given a 3D scene that is being rendered from an arbitrary viewpoint by an arbitrary projection, how can we map user input such as a mouse click into the 3D scene?

This is a problem with several solutions, some obvious and some more clever. One option is to project your geometry into 2D window coordinates and compare the results to the mouse position. For instance, if you have a 2D grid of control points defining a tensor product surface, you could manually project each control point (eg. gluProject()) and then do a search to find the point that projects nearest to your mouse position. This approach makes sense for simple applications, but becomes too inefficient for more complex tasks.

Here is some code that implements this approach, courtesy of John Brosz:

[point-pick.c]

A similar approach is to do the opposite: instead of projecting your 3D geometry to 2D, you can unproject your 2D mouse coordinate into 3D (eg. gluUnproject()). This approach has to make up an extra dimension somehow, and does so by looking at the depth buffer. The problems are basically the same as the previous approach.

OpenGL has some built-in tools to address this problem more robustly: the selection buffer. The idea is this: during a rendering pass, you can give each entity of interest a unique name ( glLoadName()). Your entity of interest could be coarse -- such as an entire mesh -- or fine, such as each face of a single mesh. When rendering, OpenGL will keep track of which entities rasterized to your area of interest, i.e. which objects contributed to the final pixel value of a pixel in your region of interest. Then you can get a list of all such entities (returned by glRenderMode()) and process it as you see fit.

Here are some code chunks that implement this:

[glselect.cpp]

The code won't compile as is, but should be easy to modify to suit your purposes.

The selection buffer idea can be mimicked in DirectX or even OpenGL by render-to-texture. If you render each entity in a unique color (without lighting, of course), then when a mouse click is received you simply do a constant-time lookup in your texture to get the name/ID of the entity. The texture only needs to be updated when the scene or camera change, so this method is very efficient in many cases.

Important! A quick note on the coding portion of Assignment 3: to subdivide an RGB image, you should apply the subdivision mask to each color channel independently.

Covered in lab today:

Tips on implementing subdivision, including:

• Definition of a half-edge data structure.
• How to populate a half-edge data structure when loading an OBJ file.
• How to traverse faces and vertex neighborhoods.
• How to modify the traditional half-edge structure to accomodate subdivision.
• How to apply subdivision masks and where to store the new vertices created during subdivision.
• How to create the new face structure after subdivision.

Covered in lab today:

Butterfly subdivision, which is a triangle-based scheme with a face-splitting structure similar to Loop subdivision. The difference is that Butterfly subdivision is interpolating, while most other schemes (Loop, Catmull-Clark, etc.) are approximating.

Left: Catmull-Clark     Right: Butterfly
Image taken from http://www.gamasutra.com/features/20000411/sharp_01.htm

The original Butterfly scheme creates artifacts at extraordinary vertices, so a modified scheme was later introduced. The image below illustrates these artifacts, and the improvements in the modified scheme.

Left: Original mesh      Middle: Butterfly      Right: Modified Butterfly
Image taken from http://graphics.stanford.edu/~dzorin/multires/butterfly/index.html

Here are some links:

• Original paper by Dyn, Levin, and Gregory
  
• Modified Butterfly paper by Zorin et al.

Covered in lab today:

Techniques for analyzing subdivision. The convergence and smoothness properties of a subdivision scheme can be determined by looking at the behaviour of a small neighborhood of points and the corresponding local subdivision matrix S. If the eigenvalues of S have a certain structure -- namely that l₀ = 1 and l_{i ≠ 0} < 1 -- then the subdivision scheme will converge. For example, the eigenvalues of cubic B-spline subdivision are (1, 1/2, 1/4, 1/8, 1/8).

We also talked a bit about the third assignment, in particular Question 1. I covered the same question for Catmull-Clark subdivision.

Finally, the second assignment was returned.

There is an example on the Qt site about creating an image viewer program:

http://doc.trolltech.com/4.2/widgets-imageviewer.html

Covered in lab today:

Implementation tips for Assignment 3, from a Qt-centric perspective.

Qt provides two main image classes: QImage and QPixmap.

• QImage provides the image-loading interface, and is optimized for I/O and pixel access/manipulation. Supported formats vary depending on the Qt configuration, but the machines in the graphics lab claim to support the popular formats: JPEG, GIF, BMP, PPM, etc.
• QPixmap is optimized for drawing.

Here is some code that implements a class that inherits from QWidget and can then be instantiated and added to a GUI layout.

[imgwidget.h | imgwidget.cpp]

If you have a severe aversion to Qt, I would suggest looking into the CImg library. That can be used in conjunction with ImageMagick to load more file types.

http://cimg.sourceforge.net
http://www.imagemagick.org

If you are working with meshes for your project, the OBJ format is a popular mesh file format.

At this site, there are some great tutorial programs that work with OBJ meshes, along with the source code. Take a look at the source if you need to write an OBJ parser for your project.

Covered in lab today:

I talked about how to apply subdivision to images. The main issue is how to handle the boundaries. There are three main approaches: a) use special boundary masks that interpolate the boundaries; b) wrap around the image for missing samples; c) use symettric extension (mirror the samples about the boundaries).

I made a mistake when covering solutions for the midterm. On Question 3, part b), the correct answer is that a cubic Bezier is smoother than the B-spline, because polynomials are infinitely smooth. Obviously the question tricked me, so hopefully it didn't trick you as well.

In yesterday's lab we talked about how to interpret and implement subdivision filters for curves. The important thing to remember is that a subdivision filter -- such as S = {1/4, 3/4, 3/4, 1/4} for Chaikin curves -- represents a regular column of the subdivision matrix, which equivalently represents the contribution of a single coarse point to all fine points.

For implementation we are generally more interested in finding all coarse points that contribute to a single fine point, which comes from the rows of the subdivision matrix; for binary subdivision schemes, there are two types of row masks: even masks, from the even elements of S, and odd masks from the odd elements of S.

Reminder: Assignment 2 is due this Friday, March 9. In order to give you guys as much time to work on the assignment as possible, please note the following specific deadlines:

Written portion: due before 4pm. I will empty the drop-box at 4pm.
Coding portion: due at 11:59pm via email.

Note also that the coding portion will be marked a little harder this time around. That means: ensure your code is implemented in an efficient manner. For example: don't compute the curve or surface in the display function; use display lists if your rendering is too slow; and so on.

Today we covered solutions to the midterm.

In today's lab, I covered solutions for the sample midterm that was posted on the course website. I also covered a true/false question from last year's midterm.

In today's lab, I did a quick midterm review, summarizing what has been covered so far. The first assignment was also returned.

Marks for Assignment 1 have (finally!) been posted. If you have any questions, or would like a break-down of your mark, send me an email. The average is very high, so great job everyone!

Here is some code from today's lab for ruled surfaces. Note that the curve code isn't included, since that is part of Assignment 2; instead, the executable is included in the archive.

[ruled.tar.gz]

Here is a good vector and matrix library. Feel free to use it in your assignments, and save the hassle of implementing one yourself. Basic usage is:

gmVector3 v, w(0.0, 0.0, 0.0);	// Default and initialization constructors
v.assign(1.0, 2.0, 2.0);	// Assign values to each component
v[2] = 3.0;	// Use [] to access elements individually
w = 2.0*v;	// Scalar-vector multiplication
float mag = w.length();	// Member function for getting vector length
float dp = dot(v, w)	// Dot product; also cross(v, w), distance(v, w) (for points)
w = normalize(v);	// Normalize to length = 1

Usage is similar for the matrix classes.

To use the vector classes in your code, you just need to include the appropriate header file (eg. #include "gmVec2.h"). For the matrix classes, you will have to include the header file, and add the corresponding source file to the makefile. You can add do this with the barebones app by adding references to the .cpp and .o files under the CXXFILES and OBJECTS definitions in the makefile.

[libgm.tar.gz]

In today's lab, we covered the efficient B-spline algorithm from the course notes and traced through an example.

I also explained the connection to -- and expectations of -- the Assignment 2 requirement to "include an option to demonstrate the algorithm in a geometric fashion."

Just a reminder that Assignment 1 is due tomorrow at 11:59pm. Please review the assignment procedures and check that your code compiles in the Graphics Lab.

Make sure you email your code archive (no executables, .o files, etc.) by the deadline. I will pick up the written portion from the drop boxes on Friday morning at 10:00am.

In today's lab, we briefly re-covered the equivalence of degree-d Bezier curves and order-d+1 B-splines (with a certain knot sequence).

We also covered some simple mouse-look interfaces, one that changes the object and one that moves the camera in polar coordinates. Trackball rotation via quaternions are the best mouse-based interaction method, but finding a good quaternion library for C++ is a chore. (Implementing trackball in C# or higher-level languages, though, is a breeze.)

Finally, we discussed NURBS, which can be interpreted as B-spline curves lifted to a higher dimension and then projected back down, and proved that NURBS are invariant under projection.

The Makefile in the lab 2 code was corrupt (thanks to Hasan for pointing this out). A new version is available, or the original Makefile from the barebones app can be used as well.

There was also a problem with the texture-loading function in the barebones app that caused it to not work properly outside of the Graphics Lab. LoadTexture() has been updated to a more robust version, including automatic selection of the power-of-2 dimensions, that should work on all department machines.

[Barebones update] [Lab 2 code update]

In next Monday's lab, I will be giving a preview of later course topics. If you haven't decided on a project topic, this will be a good opportunity to see some possible topics.

Sorry for the lack of recent updates. To recap the last few labs, on the 22nd I talked briefly about the assignment (hint: assume a 2D setting for Q1) and covered a Bezier curve question involving finding a control point based on known control points and a curve sample.

On the 24th, I did a quick refresher on vector spaces vs. affine spaces, and bases for them. We can treat polynomials as elements in a vector space, and for computer graphics there are some choices of basis that are better than others (i.e. Bernstein polynomials, B-splines).

On the 29th, we talked about affine invariance and proved that parametric curves are affine invariant if their basis functions have unit summation. We then showed that Bezier curves are a special case of B-splines by showing the equivalence of the basis functions in the 3rd-degree case. I also covered some properties of B-spline basis functions and hinted at how to prove them (in case it comes up ;). Finally, I gave a hint about how to set up OpenGL's viewport and projection when making a curve editor.

In today's lab, I covered a 3-part example involving B-splines: a) use the recursive definition to find the 3rd-order (k = 3) basis functions; b) prove that the basis functions are indeed splines; and c) assuming a curve with 4 points (m = 3), find the tangent at u_max.

Here is the code from the programming excercise covered in today's lab. The archive includes the texture map and all modifications of the barebones app that were discussed in lab today, which involved creating a spinning Earth and implementing some rudimentary camera control.

[Lab 2 code]

In today's lab we will be doing a programming exercise involving texture mapping, GUI programming, and animation using the barebones application and the texture given below.

[Earth texture]

Here is a barebones OpenGL/Qt application that can be used as a basis for your assignments and/or project. It should compile on the machines in the graphics lab without modification; just extract the files and run make.

[barebones.tar.gz]

The files of interest are renderer.* and window.*. The Renderer class handles your graphical objects and rendering duties, while Window is responsible for creating the the window and GUI elements and communicating with Renderer.

The functions you will most often need to modify, outside of declaration and initialization of variables in the headers and constructors, are:

• Renderer::initializeGL() This is where you should set up your OpenGL rendering state, position lights, load textures, initialize objects, and so on.



• Renderer::resizeGL() This is called once when the window is created, and again whenever the window is resized. Here is where you set up your viewport (eg. orthographic or perspective projection).



• Renderer::paintGL() This is where you make your rendering calls or call display lists. You don't call this function yourself; to add a redraw to the event queue, you can call Renderer::updateGL().



• Renderer::[mouse|key]*Event Here is where you get input events, such as keypresses or mouse clicks, and perform the appropriate actions. If you make any changes that modify rendering parameters, you should end with an updateGL() call.

Labs begin on Jan. 15. Check this page frequently for updates throughout the semester.