Adaptive, multiresolution representation of a machine part; with exactly resolved features (edges, corners); top: 5% error; middle: 1% error; finest level mesh
CS 175: Topics in Geometric Modeling
Spring 2006



Homework Assignments


Submition instructions: Please send your theory work to Ke Wang's mailbox at the second floor of Jorgensen or his office. Please email your coding assignment and Readme file to Liliya.

  • Homework #1. (Due date: April 7 Fri. 5pm)

    Theory part (10 points each):
    1.5: 3&5; 2.10: 2 & 7; 3.13: 2 from the textbook

    Practical part (50 points):
    Implement de Casteljau recursion to generate approximation to a planar polynomial curve with stopping criteria/flatness check (read section 3.5 of the textbook to get detailed instructions).

    Note that:
    • Your code should accept arbitrary control points defined by users. Users should also be allowed to choose an epsilon for the stopping criteria.
    • You need to visualize the initial control points and the final approximation polygons.
    • Provide friendly Readme file so that your codes can be easily run by someone else. Explain the stopping criteria you chose.
    • Use one of the following programming languages: Matlab, Mathematica, C++, Java (try not to use any external libraries, if some are necessary, please document it).

  • Homework #2. (Due date: April 14 Fri. 5pm)

    10 points each problem.

    • Textbook: 5.12: 2,5,7;
    • Textbook: 6.9: 3, 9;
    • Assuming that knots are equidistant and new knots are inserted in the middle of each non-vanishing interval, derive the knot insertion formula of quadratic B-splines when one knot is 2-fold and all others are simple knots.

  • Homework #3. (Due date: April 21 Fri. 5pm)

    Textbook: 8.11: 2, 3, 5, 7. (10 pts each).

    We consider the 4-point scheme with \omega = 1/16.
    • (20pts) There are two ways to modify 4-point scheme near to the endpoints: One is to use all 4 stencils from one side and the other is to use lower order interpolating scheme. Compute the weights of modified 4-point scheme with endpoints in each case and implement them to get subdivision curves with endpoints.
    • (10pts) Show that the C2 test by analyzing 2nd order differencing scheme fails for 4-point scheme. Is this sufficient to conclude that 4-point scheme is actually not C2? Why or why not?
    • Bonus problem (10pts): Answer the second part of question 2) by reading Chapter 5 of the notes: http://www.cs.caltech.edu/~cs175/cs175-00/materials/book.pdf

  • Homework #4. (Due date: May 1 Mon. 5pm)
    Textbook (10pts each):
    9.12: 6
    10.8: 3
    15.11: 2,3,4


  • Homework #5. (Due date: May 12 Fri. 5pm)
    Part I. Theory:
    1. Read Section 7.2 of Joe Warren's notes and finish the proof of Theorem 21:
    http://www.cs.caltech.edu/~cs175/cs175-00/materials/book.pdf
    (20 pts)

    2. Consider the masks of Doo-Sabin subdivision scheme at the irregular vertex of valence k (See Fig. 4.12 from Siggraph course notes: http://www.multires.caltech.edu/pubs/sig00notes.pdf).
    By discrete Fourier transform, you can decompose the 4k by 4k subdivision matrix into a matrix with k blocks on the diagonal. The j-th block comes from Fourier coefficients of mode j-1.
    (10 pts each)
    (1) Compute the eigenvalues of subdivision matrix given the Doo-Sabin variant.
    (2) Compute the eigenvalues of subdivision matrix given the Catmull-Clark variant.
    (3) You will have k eigenvalues \lambda_0,\lambda_1,...,\lambda_k-1 to be determined by the masks of irregular vertex, where \lambda_j comes from Fourier mode j. Compute the masks such that \lambda_0=1, \lambda_1=lambda_{k-1}=\lambda (subdominant eigenvalue) and for else \lambda_j=0.
    (4) Compute the masks such that \lambda_0=1, \lambda_1=lambda_{k-1}=\mu, \lambda_2=lambda_{k-2}=\lambda(subdominant eigenvalue) and for else \lambda_j=0.
    (5) Fix k = 6 and \lambda=1/2. Compute the eigenvectors of subdivision matrix corresponding to the subdominant eigenvalue \lambda in (3) and (4). Show that the characteristic map is not injective in (4).

    Part II Implementation exercise
    Implement Doo-Sabin scheme with choices of masks in (1)-(4). You can use provided mesh code and visualizer here.
    Currently the code reads in mesh in obj format (given with command line argument -io) and does one step of subdivision with given mask (comand line argument -m (1 to 4)), and outputs the result in the obj file given with the option (-oo). In order to do more steps use option -n. Multiple steps are implemented by repeated read/write of the files.
    You will see four functions in the "Subdivide" class that you need to implement for the corresponding masks.



Copyright 2005 Ke Wang