15-859E Project

Revision 2, 29 Oct. 1998
The goal of the project is to give you practice at doing research and development in the topic of the course, hierarchical methods for simulation. Most projects will involve implementing an algorithm, but some could be more theory-oriented or survey-like. You should:
  1. do literature search on related previous work,
  2. do your new work,
  3. give a presentation in class, and
  4. write up a description of your work, with comparison of your results to previous work, if possible. Papers should be 8-12 pages in length. The "new work" of phase (2) above could be application of existing algorithms to a new problem; a variation on an existing algorithm; design, implementation, and testing of a new algorithm; novel theoretical analysis of an algorithm; or a survey of previous work on some topic. In a select cases, a project intentionally entailing rediscovery of a known method will be acceptable, in which case there will probably be papers/books that you should avoid looking at in phase (1).


    Project Topic Ideas

    The following are some possible project topics. The list is not exclusive! You can also modify an idea listed here, or propose something totally new. To get other ideas, see survey papers such as Gree90, Gree94, Bran88, bibliographies such as chapter 14 of Stol96, or popular press books such as Hubb98. I've listed references that I know of, but the list is incomplete, so you should plan on doing your own literature search.


    Web pages for this course: http://www.cs.cmu.edu/~ph/859E/www/
    David Baraff and Andrew Witkin, Large Steps in Cloth Simulation, Proc. SIGGRAPH 98, 1998, pp. 43-54, http://www.cs.cmu.edu/~baraff/papers/index.html
    Josh Barnes and Piet Hut, A hierarchical O(NlogN) force-calculation algorithm, Nature, 324, Dec. 1986, pp. 446-449
    Thaddeus Beier and Shawn Neely, Feature-based Image Metamorphosis, Computer Graphics (SIGGRAPH '92 Proceedings), 26 (2), July 1992, pp. 35-42
    Guy Blelloch and Girija Narlikar, A Practical Comparison of N-Body Algorithms, Parallel Algorithms, American Mathematical Society, 1997, on web
    A. Brandt, Guide to multigrid development, Multigrid Methods, W. Hackbusch and U. Trottenberg, eds., Springer-Verlag, 1982, pp. 220-312
    A. Brandt, The Weizmann Institute research in multilevel computation: 1988 report, Proc. 4th Copper Mountain Conf. on Multigrid Methods, J. Mandel and others, eds. SIAM, 1989, pp. 13-53, (I have copy)
    Tony F. Chan and Susie Go and L. Zikatanov, Lecture Notes on Multilevel Methods for Elliptic Problems on Unstructured Grids, UCLA Math. Dept., (97-11), Mar. 1997, http://www.math.ucla.edu/~chan/mgpapers.html
    I. Cohen, (paper on multigrid optical flow), Marie-Odile Berger and others, eds., Images, wavelets and PDE's., Proc. 12th Intl. Conf. on Analysis and Optimization of Systems, Springer-Verlag, 1996
    Matthias Eck and Tony DeRose and Tom Duchamp and Hugues Hoppe and Michael Lounsbery and Werner Stuetzle, Multiresolution Analysis of Arbitrary Meshes, SIGGRAPH '95 Proc., Aug 1995, pp. 173-182, probably on web
    David R. Forsey and Lifeng Weng, Multi-resolution surface approximation for animation, Proc. Graphics Interface '93, 1993, pp. 192-200
    Steven J. Gortler, Wavelet Methods for Computer Graphics, Princeton, NJ Department of Computer Science, Princeton University PhD thesis, (CS-TR-473-94), jan 1995, http://hillbilly.deas.harvard.edu/~sjg/
    Steven J. Gortler and Michael F. Cohen, Hierarchical and Variational Geometric Modeling with Wavelets, 1995 Symposium on Interactive 3D Graphics, pp. 35-42, http://www.research.microsoft.com/research/graphics/cohen/
    Leslie Greengard and V. Rokhlin, A Fast Algorithm for Particle Simulations, Journal of Computational Physics, 73, 1987, pp. 325-348
    L. Greengard, The numerical solution of the N-body problem, Computers in Physics, 4 (2), mar-apr 1990, pp. 142-152
    L. Greengard, Fast algorithms for classical physics, Science, 265 (5174), 12 Aug. 1994, pp. 909-914
    Markus H. Gross and R. Gatti and O. Staadt, Fast Multiresolution Surface Meshing, Proc. IEEE Visualization '95, jul 1995, http://www.inf.ethz.ch/publications/tr.html
    Barbara Burke Hubbard, The World According to Wavelets: The Story of a Mathematical Technique in the Making, A K Peters, 1998
    Stephane Jaffard, Wavelet Methods for Fast Resolution of Elliptic Problems, SIAM Journal on Numerical Analysis, 29 (4), aug 1992, pp. 965-986,
    papers by Leif Kobbelt: http://www9.informatik.uni-erlangen.de/Persons/Kobbelt/publist.html
    Peter Litwinowicz and Lance Williams, Proceedings of SIGGRAPH '94, Animating Images with Drawings, jul 1994, pp. 409-412
    R. A. Lorentz and W. R. Madych, Spline wavelets for ordinary differential equations, Gesellschaft fur Mathematik und Datenverarbeitung , no. 562, 1991 (in E&S library)
    Sam Qian and John Weiss, Wavelets and the numerical solution of partial differential equations, J. Comp. Phys., 106, 1993, pp. 155-175
    John K. Salmon and Michael S. Warren, Skeletons from the Treecode Closet, J. Comp. Phys., 111 (1), 1994, pp. 136-155, http://www.cacr.caltech.edu/~johns/papers.html
    papers by Peter Schroeder: http://www.multires.caltech.edu/pubs/
    Eric J. Stollnitz and Tony D. DeRose and David H. Salesin, Wavelets for Computer Graphics, 1996, Morgann Kaufmann
    D. Terzopoulos, Multilevel computational processes for visual surface reconstruction, Computer Vision, Graphics, and Image Processing, 24, 1983, pp. 52-96
    Andrew Willmott's VL library (fancier brother of SVL): http://www.cs.cmu.edu/~ajw/public/dist/
    P. Wesseling, An Introduction to Multigrid Methods, John Wiley & Sons, 1992
    Andrew Witkin and Michael Kass, Reaction-diffusion textures, Computer Graphics (SIGGRAPH '91 Proceedings), 25 (4), jul 1991, pp. 299-308, http://www.cs.cmu.edu/~aw/gallery.html, see Ray Tracing News, v.5, n. 1 & 2 for errata: http://www.acm.org/tog/resources/RTNews/html/
    George Wolberg, Digital Image Warping, IEEE Computer Society Press, 1990
    Stephen Wong's multipole diagrams, http://wong.physics.oberlin.edu/


    15-859E, Hierarchical Methods for Simulation
    Paul Heckbert

    This file is http://www.cs.cmu.edu/~ph/859E/www/project.html