GeometryProcessing/Spring2009/Schedule

From VistrailsWiki
Revision as of 20:55, 17 December 2008 by Csilva (talk | contribs)
Jump to navigation Jump to search

Typical Class

Lecturer: Claudio

Topics: Scientific Visualization

Required Reading/Notes: lec01-notes.pdf

Slides: intro

Animations: NCSA storm animation

Further reading:

(Optional reading) Provenance for Computational Tasks: A Survey

Introduction (Jan 10)

Presenter: Claudio Silva

In this first lecture, we briefly discuss the field of digital geometry processing, and the objectives of this course. We also talked about the overall structure of the class, and in what the grades will be based on. Here is a link to the slides used: [1].

Combinatorial Topology (Jan 12)

Presenter: Claudio Silva

Slides: [2]

In this class, we review concepts from combinatorial topology. Most of the material is covered in the reference below, which is required reading:

  • [GT], chapter 3.

It is also useful to read:

  • [TOP], chapter 1 and parts of chapter 4.

In order to check your understanding of the basic concepts covered in class, you might want to browse through this paper:

  • Progressive simplicial complexes, Jovan Popovic, Hugues Hoppe, ACM SIGGRAPH 1997, pp. 217-224, 1997. [3]

Compression (Jan 17)

Presenter: Louis Bavoil

Slides: [4]

Required reading:

  • J. Rossignac. Edgebreaker: Connectivity compression for triangle meshes. IEEE Transactions on Visualization and Computer Graphics, 5(1):47–61, January-March 1999. [5]

Recommended reading:

  • Helio Lopes, Jarek Rossignac, Alla Safonova, Andrzej Szymczak and Geovan Tavares. Edgebreaker: A Simple Compression Algorithm for Surfaces with Handles. Computers&Graphics International Journal, Vol. 27, No. 4, pp. 553-567, 2003. Conference version: [6]

Optional reading:

  • Efficient Edgebreaker for surfaces of arbitrary topology. T. Lewiner, H. Lopes, J. Rossignac and A. Wilson-Vieira. SIBGRAPI/SIACG 2004. [7]
  • J. Rossignac, A. Safanova, and A. Szymczak. 3D compression made simple: Edgebreaker on a Corner Table. In Proceedings of Shape Modeling International Conference, Genoa, Italy May 2001. [8]

Compression (Jan 19)

Presenter: Louis Bavoil

Slides: [9]

Required reading:

  • Streaming Compression of Tetrahedral Volume Meshes, Martin Isenburg, Peter Lindstrom, Stefan Gumhold, Jonathan Shewchuk, submitted for publication, 2005. [10]

Recommended reading:

  • "3D Mesh Compression", Jarek Rossignac, Chapter in the Visualization Handbook. Academic Press. Eds. C. Hansen and C. Johnson. 2004. [11]
  • Streaming Meshes, Martin Isenburg, Peter Lindstrom, Proceedings of Visualization 2005, pages 231-238, October 2005. [12]

Optional reading:

  • Grow & fold: compression of tetrahedral meshes, Andrzej Szymczak and Jarek Rossignac, ACM Symposium on Solid Modeling and Applications, pp. 54-64, 1999. [13]

Remeshing (Jan 24)

Presenter: Samuel Gerber

Slides: [14]

Required Reading:

  • V. Surazhsky and C. Gotsman. Explicit surface remeshing. Proceedings of the Symposium on Mesh Processing, June 2003. [15]
  • P. Alliez , E. Colin de Verdiere, O. Devillers, and M. Isenburg. Isotropic surface remeshing. In Proceedings of Shape Modeling International 2003. [16]

Optional Reading:

  • Recent Advances in Remeshing of Surfaces, Pierre Alliez, Giuliana Ucelli, Craig Gotsman and Marco Attene, Part of the state-of-the-art report of the AIM@SHAPE EU network, 2005. [17]
  • High Quality Compatible Triangulations, Vitaly Surazhsky, Craig Gotsman, Proceedings of 11th International Meshing Roundtable, 2002 [18]

Some Links I found useful:

  • Genus Defintion [19]
  • Voronoi Diagramms [20]
  • Centroidal Voronoi Tessellations [21]
  • Delaunay Triangulation [22]
  • Slides from another lecture about remeshing [25]
  • Remeshing apllication [26]

Introduction to Topology I - Morse Theory (Jan 26)

Presenter: Claudio Silva

Slides: [27]

Required reading:

  • Chapter 1 of [MORSE] was the basis for the lecture. (Let me know if you would like a copy of chapter 1, and I will give you a copy.)
  • Morse Theory on Wikipedia (up to The Morse inequalities) [28]

Recommended reading:

  • Chapter 5 of [TOPCOMP] can be useful reading.
  • Surface Coding Based on Morse Theory, Yoshihisa Shinagawa , Tosiyasu L. Kunii, Yannick L. Kergosien, IEEE Computer Graphics and Applications, 11(5):66-78, 1991. [29]
  • Constructing a Reeb graph automatically from cross sections, Yoshihisa Shinagawa and Tosiyasu L. Kunii, IEEE Computer Graphics and Applications, 11(6):44-51. 1991. [30]

Remeshing (Jan 31)

Presenter: Claurissa Tuttle

Slides: [31]

Required Reading:

  • Quadrangulating a Mesh using Laplacian Eigenvectors, Shen Dong, Peer-Timo Bremer, Michael Garland, Valerio Pascucci, John C. Hart, Tech Rep. UIUCDCS-R-2005-2583, June 2005. [32]

Recommended Reading:

  • Harmonic functions for quadrilateral remeshing of arbitrary manifolds. S. Dong, S. Kircher, and M. Garland. Computer Aided Geometry Design, 22(5):392–423, 2005. [33]
  • A Topological Hierarchy for Functions on Triangulated Surfaces. Peer-Timo Bremer, Herbert Edelsbrunner, Bernd Hamann, Valerio Pascucci. TVCG 10, 4, 385-396. [34]
  • Graph Partitioning. Jim Demmel. [35]

Other links:

  • John C. Hart's slides on Computational Topology [36]
  • Gabriel Taubin's "A Signal Processing Approach to Fair Surface Design" [37]
  • Graph Partitioning Slides. [38]
  • Spectral Graph Theory and its applications. Daniel A. Spielman. [39]

Introduction to Voronoi Diagrams and Delaunay Triangulations (Feb 2)

Presenter: Solomon Boulos

Slides: [40]

Required Reading:

  • J-D. Boissonnat. Voronoi diagrams, triangulations and surfaces. In Differential Geometry and Topology, Computational Geometry, J-M. Morvan and M. Boucetta Ed., NATO Science Series III:Computer and Systems Sciences, Vol. 197, pp. 340-368, 2005. [Sections 1-3] [41]
  • Also, see [GT], chapter 1.

Recommended Reading:

  • David Mount's Computational Geometry Lectures (pages 67-81, 111-117) [42]

Classical Surface Reconstruction (Feb 7)

Presenter: Solomon Boulos

Slides: [43]

Required Reading:

  • N. Amenta, M. Bern, and M. Kamvysselis. A new Voronoi-based surface reconstruction algorithm. In Proceedings of SIGGRAPH 98, pp. 415–422, July 1998. [44]
  • Nina Amenta and Marshall Bern. Surface reconstruction by Voronoi filtering, Discrete and Computational Geometry, 22, pages 481-504, (1999). [45]

Recommend Reading:

  • Nina Amenta, Power Crust Presentation [46]
  • Nina Amenta, Marshall Bern and David Eppstein. The crust and the beta-skeleton: combinatorial curve reconstruction, Graphical Models and Image Processing, 60/2:2, pages 125-135 (1998). [47]

Surface Meshing by Reconstruction (Feb 9)

Presenter: Tobias Martin

Slides: [48]

Required Reading:

  • J-D. Boissonnat. Voronoi diagrams, triangulations and surfaces. In Differential Geometry and Topology, Computational Geometry, J-M. Morvan and M. Boucetta Ed., NATO Science Series III:Computer and Systems Sciences, Vol. 197, pp. 340-368, 2005. [Sections 4-5.] [49]
  • J-D. Boissonnat and S. Oudot. Provably Good Sampling and Meshing of Surfaces. Graphical Models 67 (2005) 405-451. [50]

Recommended Reading:

  • J-D. Boissonnat and S. Oudot. Provably Good Surface Sampling and Approximation. In Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, pages 9-18 [51]
  • J-D. Boissonnat, L. J. Guibas, and S. Oudot. Learning Smooth Objects by Probing. Proceedings of the 21st Annual Symposium on Computational Geometry, Pisa, Italy, pp. 198-207, 2005. [52]
  • T. K. Dey, G. Li and T. Ray. Polygonal surface remeshing with Delaunay refinement. Proc. 14th Internat. Meshing Roundtable (2005), 343-361. [53]
  • Nina Amenta and Marshall Bern. Surface reconstruction by Voronoi filtering, Discrete and Computational Geometry, 22, pages 481-504, (1999). [54]

Moving Least Squares Surfaces I (Feb 14)

Presenter: Carlos Scheidegger

Slides: [55]

I'll go over the underlying math in detail on the lectures. So the best way to prepate for this is to simply read the two graphics papers:

  • M. Alexa, J. Behr, D. Cohen-Or, S. Fleishman, D. Levin, and C. Silva. Point Set Surfaces, IEEE Visualization 2001, pp. 21-28, 2001. [56]
  • Andrew Nealen. An As-Short-As-Possible Introduction to the Least Squares, Weighted Least Squares and Moving Least Squares Methods for Scattered Data Approximation and Interpolation, manuscript, 2004. [57]

These two are background math for those who are interested (I plan to spend about half of the lecture in these)

  • P. Lancaster and K. Salkauskas, Surfaces generated by moving least squares methods. Mathematics of Computation 87, 141–158, 1981. [58]
  • D. Levin, Mesh-independent surface interpolation. In "Geometric Modeling for Scientific Visualization" Edited by Brunnett, Hamann and Mueller, Springer-Verlag, 2003, 37-49. [59]

Moving Least Squares Surfaces II (Feb 16)

Presenter: Carlos Scheidegger

Slides: [60]

These are followup work, mostly about alternative definitions with different (better?) properties. In my opinion, the Adamson and Alexa series of papers are more interesting because they are much simpler to implement, and no one has yet shown any way in which they are worse, in theory or practice. The big difference is that they require oriented normals. Amenta and Kil's papers provide good insight on the nature of the projection and some of the underlying problems, but fall short of giving a satisfactory solution (I'll go over this in detail). I've cut this down to three papers because otherwise we won't have time. And, this time, one of the papers is really simple :)

  • Nina Amenta and Yong Kil. Defining point-set surfaces, SIGGRAPH 2004, pages 264-270. [61]
  • Nina Amenta and Yong Joo Kil. The domain of a point-set surface, Eurographics Workshop on Point-based Graphics, 2004, pages 139--147. [62]
  • Anders Adamson and Marc Alexa. Approximating and Intersecting Surfaces from Points. Proceedings of EG Symposium on Geometry Processing 2003, pages 245-254. [63]

I probably won't go over this, since it's pretty obvious given the previous two.

  • Anders Adamson, Marc Alexa. Anisotropic Point Set Surfaces. Proceedings of Afrigraph 2006. [64]

This is a pretty technical paper, mostly about making sure projections are orthogonal. The main advantage of having orthogonal projections is that they direcly define a distance field, which is very useful for subsequent processing.

  • Anders Adamson and Marc Alexa. On Normals and Projection Operators for Surfaces Defined by Point Sets. Proceedinsg of Eurographics Symposium on Point-based Graphics 2004, pp. 149-156. [65]

Link to PointShop3D. There is also a plugin for the implementations from Yong Kil for the Defining point-set surface paper available. [66]

Note about Principal Component Analysis. PCA is a very important technique in many areas, and it is heavily used for defining the normals of point sets. Here is a short description of it: [67]. Also see section 3 of [68].

Moving Least Squares Surfaces III (Feb 21)

Presenter: Emanuele Santos

Slides: [69]

  • S. Fleishman, D. Cohen-Or, and C. Silva. Robust Moving Least-squares Fitting with Sharp Features. ACM Transactions on Graphics (Proceedings of SIGGRAPH 2005). [70]
  • Forward search
    • ATKINSON, A. C., AND RIANI, M. 2000. Robust Diagnostic Regression Analysis. Springer.
  • Statistical Concepts
    • Errors and residuals [71]
    • Studentized residuals [72]
    • Median [73]
    • Robust Statistics [74]

Surface Reconstruction with MLS (Feb 23)

Presenter: Tobias Martin

Slides: [75]

  • Peer-Timo Bremer, John C. Hart. A Sampling Theorem for MLS Surfaces. Proc. Point Based Graphics, June 2005. [76]
  • T. K. Dey and J. Sun. An Adaptive MLS Surface for Reconstruction with Guarantees. Symposium on Geometry Processing 2005, 43--52. [77]

Optional Reading:

  • R. Kolluri. Provably Good Moving Least Squares. Proceedings of the 2005 ACM-SIAM Symposium on Discrete Algorithms, Vancouver, Canada, January 23-25, pp. 1008-1018. [78]

Visibility Ordering (Feb 28)

Presenter: Steve Callahan

Slides: [79]

  • [GT], chapter 1.
  • P. Cignoni, L. De Floriani. Power Diagram Depth Sorting. 10th Canadian Conference on Computational Geometry, 1998. [80]
  • R. Cook, N. Max, C. Silva, and P. Williams. Image-Space Visibility Ordering for Cell Projection Volume Rendering of Unstructured Data, IEEE Transactions on Visualization and Computer Graphics, Vol 10, No 4, 2004. [81]

Optional reading:

  • P. Williams. Visibility Ordering Meshed Polyhedra [82]
  • C. Silva, J. Mitchell, and P. Williams. An Exact Interactive Time Visibility Ordering Algorithm for Polyhedral Cell Complexes [83]
  • J. Comba, J. Klosowski, N. Max, J. Mitchell, C. Silva and P. Williams. Fast Polyhedral Cell Sorting for Interactive Rendering of Unstructured Grids [84]
  • J. Comba, J. Mitchell, and C. Silva. On the Convexification of Unstructured Grids from a Scientific Visualization Perspective [85]

Hardware-Based Visibility Ordering (March 2)

Presenter: Steve Callahan

Slides: [86]

  • S. Callahan, M. Ikits, J. Comba, and C. Silva. Hardware-Assisted Visibility Sorting for Unstructured Volume Rendering, IEEE Transactions on Visualization and Computer Graphics, 2005. [87]
  • Naga K. Govindaraju, Ming Lin, Dinesh Manocha. Vis-Sort: Fast Visibility Ordering of 3-D Geometric Primitives, UNC-CH Technical Report 2004. [88]

Simplification I (March 7)

Presenter: Huy T. Vo

Slides: [89]

The simplification framework, and topology constraints are well covered in the textbook:

  • [GT], chapter 4.

The generalized QEM is best covered in these two papers:

  • M. Garland and Y. Zhou. Quadric-based Simplification in any Dimension. ACM Transactions on Graphics, 24(2), April 2005. [90]
  • H. T. Vo, S. P. Callahan, P. Lindstrom, V. Pascucci, C. T. Silva. Streaming Simplification of Tetrahedral Meshes, manuscript, 2005. [91]

Simplification II (March 9)

The material that was going to be covered here was already covered last clas.

There will be no class today, please attend Dr. Alan Heirich's (SONY) talk.

Update: Unfortunately, Alan could not come because he missed his flight. We will be re-scheduling him...

Spring Break (March 14)

No class.

Spring Break (March 16)

No class.

Hexahedral mesh generation for Solid Models (March 21)

Presenter: Jason Shepherd

Slides: [92]

The following pages from Steven Owen, "A Survey of Unstructured Mesh Generation Technology" [93] [94] [95] [96]

Theory of Hexahedral Mesh Generation (March 23)

Presenter: Jason Shepherd

Slides: [97]

Bill Thurston "Hexahedral Decomposition of Polyhedra" [98]

Scott Mitchell, "A characterization of the quadrilateral meshes of a surface which admit a compatible hexahedral mesh of the enclosed volume" [99]

David Eppstein, "Linear Complexity Hexahedral Mesh Generation" [100]

And here is a paper that Jason cited in class that was not listed before: [101]

Hexahedral Mesh Generation for Image-based Models (March 28)

Presenter: Jason Shepherd

Slides: [102]

"Adaptive and Quality Quadrilateral and Hexahedral Meshing from Volumetric Data" [103]

"Surface Smoothing and Quality Improvement of Quadrilateral/Hexahedral Meshes with Geometric Flow" [104]

And this paper by Jason: [105]

Isosurface Extraction March 30

Presenter: Erik Anderson

  • W. Lorensen and H. Cline. Marching Cubes: A high resolution 3D surface construction algorithm. In Proceedings of SIGGRAPH 87, pp. 163–169, 1987. [106]
  • L. Kobbelt, M. Botsch, U. Schwanecke, and H.-P. Seidel. Feature sensitive surface extraction from volume data. In Proceedings of SIGGRAPH 2001, pp. 57–66, 2001. [107]

Dual Contouring (April 4)

Presenter: Erik Anderson

  • T. Ju, F. Losasso, S. Schaefer, and J. Warren. Dual contouring of Hermite data. In Proceedings of SIGGRAPH 2002, pp. 339–346, 2002. [108]
  • Tao Ju. Robust Repair of Polygonal Models. ACM Transactions on Graphics, 23(3):888-895. [109]

Optional Reading:

  • Evgeni V. Chernyaev. Marching cubes 33: Construction of topologically correct isosurfaces. Technical Report CN/95-17, CERN, Geneva, Switzerland, 1995.

[110]

Multi-Valued Volumes April 6

Presenter: Thiago Ize

  • Kathleen S. Bonnell, Mark A. Duchaineau, Daniel A. Schikore, Bernd Hamann, Kenneth I. Joy, Material Interface Reconstruction, in IEEE Transactions on Visualization and Computer Graphics, Volume 9, Number 4, pp 500--511, 2003. [111]
  • Stephan Bischoff, Leif Kobbelt. Extracting consistent and manifold interfaces from multi-valued volume data sets. Bildverarbeitung für die Medizin (2006), to appear. [112]

Introduction to Topology II (April 11)

CLASS CANCELED.

Topology Simplification (April 13)

Presenter: Aaron Knoll

  • PT Bremer, B Hamann, H Edelsbrunner, V Pascucci, A topological hierarchy for functions on triangulated surfaces. IEEE Transactions on Visualization and Computer Graphics, 2004. [113]
  • A. Gyulassy, V. Natarajan, V. Pascucci, P.-T. Bremer, and B. Hamann, Topology-based Simplification for Feature Extraction from 3D Scalar Fields. IEEE Visualization 2005, pages 275-280, 2005. [114]
  • To understand the above two papers, I highly recommend reading the following. It will make life much easier.

H Edelsbrunner, J Harer, A Zomorodian, Hierarchical Morse-Smale Complexes for Piecewise Linear 2-Manifolds. Discrete and Computational Geometry, 2003. [115]

Introduction to Topology III (April 18)

Presenter: Claudio Silva

  • Forman's discrete topology.

Discrete Differential Geometry I (April 20)

Presenter: Joel Daniels

  • Eitan Grinspun, Peter Schröder, and Mathieu Desbrun. Discrete Differential Geometry: An Applied Introduction. ACM SIGGRAPH'05 Course Notes. [116]

Discrete Differential Geometry II (April 25)

Presenter: Joel Daniels

Tetrahedral Meshing (April 27)

Presenter: Linh Ha

Slides: [117]

  • [GT], chapter 6
  • Pierre Alliez, David Cohen-Steiner, Mariette Yvinec, and Mathieu Desbrun. Variational Tetrahedral Meshing, ACM Trans. on Graphics (SIGGRAPH '05), 24(3), pp. 617-625. [118]

Recommend:

  • Jonathan Richard Shewchuk, Lecture Notes on Delaunay Mesh Generation [119]
Retrieved from "https://www.vistrails.org//index.php?title=GeometryProcessing/Spring2009/Schedule&oldid=1561"