Today we solved the sample final exam questions. The marks for the final assignment have been posted here. This will more than likely be the last post for the semester, so I just want to thank all of you for making it an enjoyable semester !

Wish you a merry Christmas and a happy and prosperous new year,

--Javad

Today, we discussed the solutions of the questions in Assignment 3.

Note: The final exam review will be on Wednesday (Dec. 15) at 10 a.m. in MS 239.

Today we covered the topic of rendering implicit surfaces. For direct rendering, ray tracing is pretty much the only option. For real-time rendering via OpenGL or a similar rasterizing API, we 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.

Finally, we talked about rendering Constructive Solid Geometry (CSG). This class of objects is a natural fit for ray casting. We can build enter-exit time lists (t-lists) for each solid primitive and simply apply the corresponding boolean operations to these lists. Finding the final shape's t-list can be facilitated by traversing its CSG-tree using a depth first search algorithm.

Today we had an open tutorial to focus on the questions regarding the final projects.

Note: In question 4 of the third assignment you should consider the boundaries as well.

Today, we first talked about implicit primitives and implicit field functions. 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|.

Then 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.

Finally, we talked about some simple boolean operations on implicit surfaces based on their field functions and their difference with similar operations in Constructive Solid Geometry (CSG).

Covered in the lab today:

• The relationship between decomposition (wavelet transform) and classic least-squares. The important point is that 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.
• Implementation of Multiresolution: We first discussed the general representation of Cubic B-Spline subdivision matrix including boundary filters as [P_s , P_r, P_e]. Then found corresponding B filter from this paper. Finally, used B filters in an efficient algorithm to extract details. The same approach can be followed in Question 4 of Assignment 3 with A filters.
• Example Applications: We discussed two important applications of Multiresolution, Curve Synthesis by Example and Terrain Synthesis by Example. In these applications we can apply decomposition filters recursively to the decomposed data to reach desired resolution of the new coarse data.

The grades of the second Assignment are finally posted here.

Today we first discussed the code structure of the bonus assignment. All necessary requirements have been provided on the labs of Nov. 1 and Nov. 10. To subdivide an RGB image, the subdivision masks should be applied to each color channel independently. Then we started talking about the wavelets and multiresolution. Some properties of Chaikin multiresolution including the biorthogonality property were discussed.

Note: In 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".

Today we first provided the solutions of the mid-term exam. Then computed the number of the new faces, edges and vertices after one level of Catmull-Clark subdivision. We then proved that the limit surface of Doo-Sabin subdivision is mostly made up by bi-quadratic B-splines. We finished the discussion of the subdivision surfaces by reviewing definition of the semi-sharp creases in the following paper:

Subdivision Surfaces in Character Animation

Covered in the lab today:

• Solutions for the written part of Assignment 2
• Analysis of surface 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 λ₀ = 1 and λ_{i ≠ 0} < 1 -- then the subdivision scheme will converge. For example, the eigenvalues of Loop subdivision are (1, 1/2, 1/2, 1/4, 1/4, 1/4).
• 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 the papers:

Original paper by Dyn, Levin, and Gregory

Modified Butterfly paper by Zorin et al.

Today's lab dedicated to demos of Assignment 2.

Here you can find an example on the Qt site about creating an image viewer program. It takes a different approach than the ImgWidget class discussed in the Nov. 1 tutorial, as it uses a QLabel to display the image. It also creates scroll bars for images that are too big. I recommend you to take a look at their code.

Today we reviewed all of the course materials up to the end of Loop subdivision. We also solved the sample midterm questions.

Here you can find a good resource on mesh data structures.

Note: Please be ready to demo your B-Spline program on Wednesday (Nov. 10).

Today, we discussed the implementation of subdivision based on half-edge data structure. We wrote pseudo codes to traverse all vertices of a face and visit all neighbours of a vertex. Then, we saw how to populate a half-edge data structure to load an OBJ file format, which is a popular mesh format. Finally, we introduced the quad-edge data structure.

For those who are working with meshes for their final projects, there are some great tutorials at this site. They also provide the source codes for OBJ file format. For advanced mesh representation and manipulation you can use OpenMesh data structure which is bundled with a flexible framework called OpenFlipper for advanced geometry modeling and Rendering.

Note: On Monday tutorial (Nov. 8) all of the midterm materials will be reviewed.

Today we discussed an algorithm to implement subdivision filters for curves. 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, while the subdivision masks are represented as rows of this matrix. For implementation we should find contributions of coarse points in a single fine point. The algorithm generates even masks, from the even elements of S, and odd masks from the odd elements of S.

After reviewing some of the mesh terminologies we focused on subdivision of images to increase their smoothness. The main issue is to handle boundaries properly. We discussed 3 approaches: special boundary masks, wrapping around the image for missing samples and symmetric extension to mirror samples about the boundaries.

We finished discussion of the subdivision of images by providing a sample code for loading and displaying images in Qt. Qt has two main image classes:

• QImage provides the image-loading interface and is optimized for I/O and pixel access and 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.

Since neither of these classes inherits from QWidget, we implemented an interface class that inherites from QWidget to be instantiated and added to GUI layout. Here are the code samples: [imgwidget.h] | [imgwidget.cpp]

Today we finished the discussion of Parametric Surfaces.
First we proved that if an order k spline function has more continuity than (k-2) over its knot sequence, it will be a polynomial. Then provided a data structure to represent a ruled surface and discussed different ways of drawing this surface. Finally, a simple mouse-look interface was provided to move camera around the object in polar coordinates. As mentioned, trackball rotation via quaternions is the best mouse-based interaction method, because quaternions allow rotations about arbitrary axis to be combined uniquely.

Here you can find some supplementary codes for today's coding exercise about ruled surfaces. Since the curve code is part of Assignment 2, just the executable is included in the archive.

Today we reviewed the Parametric Surfaces and discussed some of their properties.
We first showed that B-Spline surfaces are invariant under affine transformations. Then discussed the local control property of NURBS surfaces. Finally we proved that Coon's surfaces interpolate their boundary curves.

The grades of the first Assignment are now posted here.

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

The class also overrides the following operators: =, +, -, *, /, +=, -=, *=, /=, ==, and !=.

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") and add the corresponding object file to the makefile. You can do this in the barebones application by adding references to the .cpp and .o files under the CXXFILES and OBJECTS definitions in the makefile.

Today we focused on the "Sums of B-Splines" algorithm and traced an example, step by step. Then discussed the approach of demonstrating this algorithm in a geometric fashion.

Then we reviewed some of the properties of NURBS curves including local modification respect to control points and convex hull property. We can show that NURBS are invariant under projection (using a general 4 by 4 transformation matrix).

In today's tutorial the solutions for the written part of Assignment 1 were discussed. Then we discussed the questions of Assignment 2 and provided a simple mouse-based approach for control point manipulation.

Here you can find John Brosz's point-picking code example for selecting a 3D control point nearest to a mouse-click event. This involves projecting the control point from world coordinates to window coordinates.

Today's lab dedicated to demos of Assignment 1. Please think about the exercises at page 41 of the course notes and ask me if you have any question.

Today we first reviewed the properties of B-Splines, then proved the unit summation property in detail. The proof was based on the mathematical induction on the order of the B-Spline (k). Finally we found the tangent at u_max to a 3^rd-order (k=3) Spline curve with 4 control points (m=3) over a uniform knot sequence.

Note: Please be ready to demo your Helix program and Maya model on Wednesday (Oct. 13). Bear in mind that the demo session should take around 5 minutes.

Today we provided a quick overview of vector spaces and affine spaces. Then the formulas of 3^rd-order B-Spline (k=3) basis functions over a uniform integer knot sequence were derived using deBoor's recursive formula. Finally, we proved that the B-Spline basis functions are in fact Splines.

Note: It is important to show all the intermediate work for the assignment and exam questions.

Today we covered NURBS modeling in Maya. These are the main topics we discussed today:

• NURBS components
• Curve tools / Snapping
• Revolve tool
• Deleting history
• Duplicating
• Working with NURBS surfaces
• Detaching surfaces
• Inserting isoparms
• Sculpt geometry tool
• Extruding
• Lofting
• MEL script

These are some of the useful Maya tutorials:

• Modeling with NURBS
• Digital-Tutors' FreeTutorials
• Tutorialized.com's Modeling Tutorials

Today we covered Maya Basics. These are the topics we discussed in today's lab:

• An introduction to Maya
• Setting up the project in Maya
• Working with camera
• Changing the views in Maya and setting the panels
• Using hotbox controls
• Different ways of viewing the geometry
• Using the channel box
• Using layer palette
• Using attribute editor
• QWERTY tools
• Adjusting the user interface
• Using pre-built shelf and customizing new shelves

Covered in the lab today:

• Some hints for the Assignment 1
• Review of the Qt windowing system and its advantages over GLUT
• Barebones OpenGL/Qt application
• QT Designer and QT Creator
• Qt event system (Signals and Slots)
• Qt Designer tutorial, courtesy of John Brosz
• Spinning Globe tutorial, courtesy of Luke Olsen

Here is a barebones OpenGL/Qt application that can be used as a basis for your assignments and/or project. It should compile and run 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 the graphical objects and rendering duties, while Window is responsible for creating the window and GUI elements and communicating with Renderer.
The functions that most often will be needed, 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.

Some functions and basic rendering calls are stubbed out. When you compile it, you should see a multi-colored triangle on a black background.

In today's lab we reviewed some of the useful OpenGL primitives and provided a simple GLUT application to draw a colorful triangle. These are the main topics we discussed today:

• Basics of OpenGL and GLUT
• OpenGL programming guide (Red Book)
• OpenGL primitives and examples: (GLUT samples, Red Book samples, Red Book codes)
• Normal Vectors and Vertex Arrays
• The graphics pipeline
• Display Lists tutorial