Tutorials of GMP 2012

Please download the file for more details on the tutorials.

¡¡

June 18

9:30a.m.-11:30a.m.

Kai Hormann

Generalized Barycentric Coordinates

11:30a.m.-1:30p.m.

Lunch

1:30p.m.-3:30p.m.

David Xianfeng Gu

Computational Conformal Geometry, Theory, Algorithm and Application

3:30p.m.-4:00p.m.

Coffee break

4:00p.m.-6:00p.m.

Ying He
Shi-Qing Xin

Discrete Geodesics

June 19

8:30a.m.-12:00a.m.

Myung Soo Kim
Gershon Elber

Numeric and Symbolic Processing in Geometric Modeling

12:00a.m.-1:30p.m.

Lunch

1:30p.m.-3:30p.m.

Wenping Wang

Computation and Applications of Centroidal Voronoi Tessellations

3:30p.m.-4:00p.m.

Coffee break

4:00p.m.-5:00p.m.

Bert J¨¹ttler

Isogeometric Analysis

  

1.     Tutorial 1 (9:30a.m.-11:30a.m., June 18)

Title: Generalized Barycentric Coordinates

Lecture: Kai Hormann

Time: 9:30a.m.-11:30a.m., June 18

Abstract:

In 1827, August Ferdinand Möbius published his seminal work on the ¡°barycentric calcul¡± which provides a novel approach to analytic geometry. One key element in his work is the idea of barycentric coordinates which allow to write any point inside a triangle as a unique convex combination of the triangle¡¯s vertices. These triangular barycentric coordinates are linear and possess the Lagrange property, and are therefore commonly used to linearly interpolate values given at the vertices of a triangle. Möbius also noticed that this construction extends nicely to linear interpolation of data given at the vertices of a d-dimensional simplex, and by giving up positivity of the coordinates, we can even extrapolate the data to every point in d dimensions.

While barycentric coordinates are unique for simplices, they can be generalized in several ways to arbitrary polygons and polytopes in higher dimensions, and over the past few years, a number of recipes for such generalized barycentric coordinates have been developed. As they are usually given in closed form and can be evaluated efficiently, they have many useful applications, e.g. in computer graphics, computer aided geometric design, and image processing.

In this tutorial, we discuss the theoretical background of generalized barycentric coordinates and present hands-on examples, ranging from colour interpolation and improved Phong shading to image warping and mesh deformations.

Syllabus: (2 hours with a 20-minute coffee break)

1.    Introduction (5 minutes)
2.    The essence of barycentric coordinates (15 minutes)
3.    Three-point coordinates (15 minutes)
4.    Barycentric data interpolation (15 minutes)
Coffee break (20 minutes)
5.    Transfinite barycentric interpolation (15 minutes)
6.    Barycentric mappings (15 minutes)
7.    Mesh deformations (15 minutes)
8.    Wrap-up (5 minutes)

Lecturer¡¯s short biography:

Kai Hormann is an associate professor in the faculty of informatics at the University of Lugano. He received a Ph.D. in computer science from the University of Erlangen in 2002 and spent two years as a postdoctoral research fellow at the Multi-Res Modeling Group at Caltech and the CNR Institute of Information Science and Technologies in Pisa, before joining the faculty at Clausthal University of Technology as an assistant professor in 2004. During the winter term 2007/2008 he visited the Berlin Mathematical School at Freie Universität Berlin as a BMS substitute professor.

His research interests are focussed on the mathematical foundations of geometry processing algorithms as well as their applications in computer graphics and related fields. In particular, he is working on parameterization of meshes, surface reconstruction from point clouds, barycentric coordinates for arbitrary polygons, and subdivision of curves and surfaces.

Prof. Hormann has published over 50 papers in the professional literature and is an active member of ACM Siggraph and SIAM. He served on more than 20 of the leading graphics and geometry conference programme committees and is a frequent reviewer for international funding agencies and the top journals in his field. Moreover, he is an associate editor of Computer Aided Geometric Design, Computer Graphics Forum, and the Dolomites Research Notes on Approximation.

 

2.     Tutorial 2 (1:30p.m.-3:30p.m., June 18)

Title: Computational Conformal Geometry, Theory, Algorithm and Application

Lecture: David Xianfeng Gu

Time: 1:30p.m.-3:30p.m., June 18

Abstract:

According to Klein¡¯s Erlangen program: different geometries study the invariants under different transformation groups. In Geometric Modeling and Processing field, topology, Riemannian geometry and surface differential geometry have been extensively applied. This tutorial focuses on conformal geometry, which studies the invariants under angle preserving transformation group. Conformal geometry is more rigid than topology and more flexible than Riemannian geometry, which offers powerful tools for fundamental problems in geometric modelling and processing, including shape matching, registration, geometric classification and so on.

Conformal geometric methods have the following merits:

  1. Unification : All the surfaces in real life can be eventually unified to one of three canonical shapes,  the sphere, the plane or the hyperbolic disk.

  2. Dimension Reduction: All 3D geometric processing problems are converted to 2D image processing problems.

  3. Information Preservation: All the deformations preserves the original geometric information, there is no information loss during the transformation.

  4. General Transformations: Conformal geometric method is capable of modelling and processing all the homeomorphisms among surfaces.

Therefore, conformal geometric methods are valuable for practical applications.

This talk will introduce the main theorems in conformal geometry, including Hodge theory, surface uniformization theorem, Ricci flow theory; main computational algorithms, including harmonic mapping, holomorphic forms, discrete Ricci flow; and main applications, including surface parameterization, spline fitting, surface registration, geometric classification. 

Syllabus: (2 hours )

1.    Introduction (8 minutes)
2.    Phase-Shifting Geometric Accquisition  (8 minutes)
3.    Homotopy Theory (8 minutes)
4.    Homology/Cohomology Theory (8 minutes)
5.    Hodge Theory (8 minutes)
6.    Harmonic Mapping (8 minutes)
7.    Holomorphic form Method (8 minutes)
8.    Ricci Flow Theory (8 minutes)
9.    Surface uniformization Theorem (8 minutes)
10.  Beltrami-Equation and Quasi-ConformalMapping (8 minutes)
11. Conformal Module/Teichmuller Space (8 minutes)
12. Surface Parameterization (8 minutes)
13. Manifold Spline (8 minutes)
14. Conformal Welding for 2D Shape Space (8 minutes)
15. Surface Registration (8 minutes)

Lecturer¡¯s short biography:

David Xianfeng Gu got his PhD from Harvard in 2002 in Computer Science and now is an associate professor in State University of New York at Stony Brook. In his PhD thesis, under the supervision of his advisor, a Fields medalist Prof. Shing-Tung Yau, David invented the algorithm for computing the conformal structure of surfaces with general topologies based on Hodge theory. Later, by collaborating with mathematicians, David invented the algorithms for computing surface uniformization based on Ricci flow theory. By collaborating with computer scientists and medical doctors, David has applied computational conformal methods in many fields in engineering and medicine, including computer graphics, computer vision, geometric modelling and processing, wireless sensor network, computational topology and medical imaging.

 

3.     Tutorial 3 (4:00p.m.-6:00p.m., June 18)

Title: Discrete Geodesics

Lecturers: Ying He and Shi-Qing Xin

Time: 4:00p.m.-6:00p.m., June 18

Abstract:

Computing discrete geodesics on polygonal meshes plays an important role in many applications in computer graphics and computational geometry, such as surface parameterization, remeshing, non-rigid registration, shape segmentation, etc. This tutorial covers both the fundamental and state-of-the-art techniques in discrete geodesics, which include geodesic distance field, geodesic paths/loops, geodesic offsets, and all-pairs geodesic distance query. Some demos are also shown in the tutorial to illustrate how user interaction enhances the modeling and processing of geometric shapes.

Syllabus: (2 hours with a 20-minute coffee break)

1.    Introduction (5 minutes)
2.    Concepts & data structures (15 minutes)
3.    Classical discrete geodesic algorithms (30 minutes)
4.    All-pairs geodesics (10 minutes)
Coffee break (20 minutes)
5.    Geodesic paths/loops (20 minutes)
6.    Geodesic offsets (15 minutes)
7.    Wrap-up (5 minutes)

Lecturer¡¯s short biography:

Ying He is an Associate Professor at School of Computer Engineering, Nanyang Technological University. His research interests fall into the general areas of visual computing and he is particularly interested in the problems that require geometric analysis and computation. He has applied geometric approaches to a wide spectrum of engineering fields, including computer graphics, multimedia, wireless sensor network and medical imaging. For details, please visit http://www.ntu.edu.sg/home/yhe

Shi-Qing Xin got his PhD degree in Zhejiang University in 2009. After that, he has been working as a research fellow at Nanyang Technological University in Singapore, working with Dr. Ying He. In the past several years, he focused on discrete geodesic and its applications. His research interests include computer graphics, computational geometry and mobile computing.

 

4.     Tutorial 4 (8:30a.m.-12:00a.m., June 19)

Title: Numeric and Symbolic Processing in Geometric Modeling

Lecturers: Myung Soo Kim and Gershon Elber

Time: 8:30a.m.-12:00a.m., June 19

Abstract:

In recent years several research groups were investigating tools that can make geometric modeling more stable and efficient.   Tools to process spline and NURBs curves and surfaces in various operations were designed that are far more robust.

In this tutorial we will start by presenting a subdivision based solver, which is based on a spline representation, for solving sets of non-linear multivariate constraints.  This solver exploits well known properties of the Bezier and B-spline representations and is able to isolate all roots, globally.  We will then show how such a solver can be used to greatly enhance our analysis and synthesis of geometric modeling capabilities, demonstrating its use in a variety of modeling applications.

The second half of this tutorial will dive into optimizing several geometric operations including symbolic tools in offset operations and trimming of offsets, Minkowski sums, self-intersections detections and eliminations, bisectors/trisectors symbolic/numeric computation as well as consider efficiency in numeric geometric computations, including the use of freeform Coons patches as bounding surfaces.

Syllabus: (3.5 hours with a 30-minute coffee break)

1.    Introduction (5 minutes)
2.    Subdivision based MV solvers (35 minutes)
3.    Examples using the MV solver in geometric modeling (50 minutes)
Coffee break (30 minutes)
5.    Offsets, Minkowski sums, and sweeps (30 minutes)
6.    Bisectors, trisectors, and Voronoi diagrams in R2 and R3 (30 minutes)
7.    Efficiency in numeric geometric processing (30 minutes)
8.    Wrap-up (5 minutes)

Lecturers¡¯ short biography:

Gershon Elber is a professor in the Computer Science Department, Technion, Israel. His research interests span computer aided geometric designs and computer graphics. Prof. Elber received a BSc in computer engineering and an MSc in computer science from the Technion, Israel in 1986 and 1987, respectively, and a PhD in computer science from the University of Utah, USA, in 1992. He is a member of the ACM.

Prof. Elber has served on the editorial board of the Computer Aided Design, Computer Graphics Forum, The Visual Computer, Graphical Models, and the International Journal of Computational Geometry & Applications and has served in many conference program committees including Solid Modeling, Shape Modeling, Geometric Modeling and Processing, Pacific Graphics, Computer Graphics International, and Siggraph.  Prof. Elber was one of the paper chairs of Solid Modeling 2003 and Solid Modeling 2004, and one of the conference chairs of Solid and Physical Modeling 2010.  He has published over 150 papers in international conferences and journals and is one of the authors of a book titled "Geometric Modeling with Splines - An Introduction".

Elber can be reached at the Technion, Israel Institute of Technology, Department of Computer Science, Haifa 32000, ISRAEL. Email: gershon@cs.technion.ac.il, WWW: http://www.cs.technion.ac.il/~gershon, Fax: 972-4-829-5538.

Myung Soo Kim is a Professor of the School of Computer Science and Engineering. In the past, he served as the CIO of Seoul National University and the Director of University Computer Center. He also served as the Director of Institute of Computer Technology and as the Head of School of Computer Science and Engineering, Seoul National University. His research interests are in computer graphics and geometric modeling.  Prof. Kim received BS and MS degrees from Seoul National University in 1980 and 1982, respectively.  He continued his graduate study at Purdue University, where he received an MS degree in applied mathematics in 1985 and MS and PhD degrees in computer science in 1987 and 1988, respectively.  Since then until 1998, he was with the Department of Computer Science, POSTECH, Korea. Prof. Kim serves/served on the editorial boards of Computer-Aided Design, Computer Aided Geometric Design, Computer Graphics Forum, and Int'l J of Shape Modeling.  He also edited more than ten special issues of journals such as Computer-Aided Design, Computer Aided Geometric Design, Graphical Models,  J of Visualization and Computer Animation, The Visual Computer, and  Int'l J of Shape Modeling.  With two other editors, Gerald Farin and Josef Hoschek, he edited Handbook of Computer Aided Geometric Design, North-Holland, 2002. In 2010, he served as a technical program co-chair of the ACM Symposium on Solid and Physical Modeling, Haifa, Israel. In 2011, he also served as a program co-chair of the SIAM Conference on Geometric and Physical Modeling, Orlando, USA.

Prof. Kim can be reached at Seoul National University, School of Computer Science and Engineering, Seoul 151-744, Korea. Email: mskim@snu.ac.kr, WWW: http://cse.snu.ac.kr/mskim, Fax: +82-2-871-4912.

 

5.     Tutorial 5 (1:30p.m.-3:30p.m., June 19)

Title: Computation and Applications of Centroidal Voronoi Tessellations

Lecturer: Wenping Wang

Time: 1:30p.m.-3:30p.m., June 19

Abstract:

Centroidal Voronoi Tessellation (CVT) is a special geometric structure that have been receiving much research interest due to its widespread applications in science and engineering. In this 2-hour tutorial,  I'll start with a brief introduction to related concepts and previous works. Then I shall present some recent advances on the computation and applications of CVT:
1)      A fast quasi-Newton method for computing CVT;
2)
      High quality mesh generation;
3)
      Modeling minimal surfaces and Constant Mean Curvature surfaces;
4)
      Circle packing and circle coverage;
5)
      A comparative study on CVT and ODT (optimal Delaunay triangulation), which is promising alternative to CVT for tetrahedral mesh generation.

Key references:
1)
      Qiang Du, Vance Faber and Max Gunzburger, Centroidal Voronoi Tessellations: Applications and Algorithms, SIAM Review, Vol. 41, No. 4 (Dec., 1999), pp. 637-676.
2)
      Qiang Du,  Max Gunzburger,  Lili Ju,  Advances in Studies and Applications of Centroidal Voronoi Tessellations,Numerical Mathematics--A Journal of Chinese Universities. 2010.
3)
      Y. Liu, W. Wang, B. Levy, F. Sun, D.M. Yan, L. Lu and C.L. Yang, On centroidal Voronoi tessellation -- energy smoothness and fast computation, ACM Transactions on Graphics, vol. 28. no. 4, (2009), pp. 1-17.

Lecturers¡¯ short biography:

Wenping Wang is Professor of Computer Science at The University of Hong Kong. His research covers computer graphics,  visualization, and geometric computing. He has recently focused on mesh generation and surface modeling for architectural design. He is journal associate editor of Computer Aided Geometric Design (CAGD), Computers&Graphics, and IEEE Transactions on Visualization and Computer Graphics (TVCG). He has served as program chair of several international conferences, including Pacific Graphics 2003, ACM Symposium on Physical and Solid Modeling (SPM 2006), and International Conference on Shape Modeling (SMI 2009).

 

6.     Tutorial 6 (4:00p.m.-5:00p.m., June 19)

Title: Isogeometric Analysis

Lecture: Bert J¨¹ttler

Time: 4:00p.m.-5:00p.m., June 19

Abstract:

Isogeometric Analysis (IGA) is a new approach to numerical simulation, which was introduced by Hughes et al. in 2005. It has the potential to bridge the gap between geometric design, which is often based on NURBS (non-uniform rational B-splines) and finite-element-based numerical simulation. The main idea of IGA is to use the same representation of the geometry both for simulation and for design, thereby eliminating the conversion processes, such as mesh generation. The tutorial will introduce the basic concepts of NURBS-based isogeometric analysis. It is based on the paper:

A.-V. Vuong, C. Heinrich, B. Simeon, ISOGAT: A 2D tutorial MATLAB Code for Isogeometric Analysis, Comp. Aided Geom. Design 27 (2010), 644-655.

The MATLAB sources are available from

http://www-m2.ma.tum.de/bin/view/Allgemeines/EXCITING

Syllabus: (1 hour)

1.    Introduction (5 minutes)
2.    Model problem (10 minutes)
3.    Galerkin projection (10 minutes)
4.    IGA basics (10 minutes)
5.    Transformation to the parametric domain (10 minutes)
6.    Matlab Code (5 minutes)
7.    Examples (5 minutes)
8.  Closing remarks (5 minutes)

Lecturer¡¯s short biography:

Bert J¨¹ttler is professor of mathematics at the Johannes Kepler University of Linz, Austria. His reserarch interests include Computer Aided Geometric Design and Isogeometric Analysis. From 2008 to 2012 he coordinated the European project ¡°Exact Geometry Simulation for Optimized Design of Vehicles and Vessels¡± which applied Isogeometric Analysis to several industrial application scenarios.