Department of Computer Science
Korea Advanced Institute of Science and Technology (KAIST)

CS780: Topics in Computer Graphics (Fall 2007)
Scalable Graphics/Geometric Algorithms

Instructor: Sung-eui Yoon

When and where: 2:30-3:45pm on Tues and Thur at Room 3444 (5th class room in 3rd floor at CS building)

First class: 4th of Sep. (Tues) (please come to first class for more information )

Office Hours: 3:45-4:30pm on Thur at Room 3432

TA: TBA

Prerequisites: Undergraudate computer graphics or equivalent OR Instructor's approval

Textbook: Course Notes and In-Class Handouts

Outline

Course overview

Fig. 1, Cross section of an oil tanker consisting of 82 milliion triangles (Excerpted from GigaWalk, Baxter et al. 2002)

Recent advances in model acquisition, computer-aided design, and simulation technologies have resulted in massive databases of complex geometric models (including an oil tanker model shown above) occupying multiple gigabytes and even terabytes. Such massive data sets pose numerous challenges in many different applications beyond computer graphics.

In this course we will discuss various techniques to design scalable computer graphics and geometric algorithms to deal with massive geometric data sets on commodity hardware. Particularly, we will focus on the following methods:

We will study these techniques in various computer graphics applications including rasterization, ray tracing, collision detection, path planning, image processing, and visualization.

What you will get at the end of the course:

What you will do:

Lecture schedule (subject to change)

# of lecture, date	Topics and slides	Related material(s)	Update time and notice
1, Sep - 4	Overview on the course and course policy	Tutorial on Massive Model Rendering Techniques, under submission for Computer Graphics and Applications, 2007 Course notes on massive model visualization, Eurographics 06 and SIGGRAPH 07	Sep-3 (2nd update)
2, Sep - 6	Two major rendering techniques: ray tracing and rasterizations	Course note on interactive ray tracing Dr. Brandon Lloyd's course on undergraduate computer graphics	Sep-3 (1st update)
3. Sep - 11	Visibility culling	A survey of visibility for walkthrough applications, D Cohen-Or, Y. Chrysanthou, C. Silva, and F. Durand, IEEE TVCG 03 PCU: The Programmable Culling Unit Jon Hasselgren, Tomas Akenine-Möller (Lund University), SIGGRAPH 07 Direct Visibility of Point Sets Sagi Katz, Ayellet Tal (Technion), Ronen Basri (The Weizmann Institute of Science) , SIGGRPH 07 Guided Visibility Sampling Peter Wonka, Kaichi Zhou (Arizona State University), Michael Wimmer (Technische Universit? Wien), Stefan Maierhofer, Gerd Hesina (Zentrum fur Virtual Reality und Visualisierung), Alexander Reshetov (Intel Corporation), SIGGRAPH 06 Interactive Shadow Generation in Complex Environments, Naga Govindaraju, Bradon Lloyd, Sung-Eui Yoon, Avneesh Sud and Dinesh Manocha, ACM SIGGRAPH, 2003	Sep-9 (1st updated)
4. Sep - 13 5. Sep - 18 6. Sep - 20	Multi-resolution methods	A Developer's Survey of Polygonal Simplification Algorithms. David Luebke, IEEE Computer Graphics &Applications, 2001 Stochastic Simplification of Aggregate Detail Robert L. Cook John Halstead Maxwell Planck David Ryu (Pixar Animation Studios), SIGGRAPH 07 Visual Equivalence: Towards a new standard for Image Fidelity Ganesh Ramanarayanan, James Ferwerda, Bruce Walter, Kavita Bala (Cornell University), SIGGRPH 07 , Far Voxels: A Multiresolution Framework for Interactive Rendering of Huge Complex 3D Models on Commodity Graphics Platforms Enrico Gobbetti, Fabio Marton (Center for Advanced Studies, Research and Development in Sardinia), SIGGRAPH 05
Sep - 25	No class (ChuSeok, Thanksgiving day)
7. Sep - 27 8. Oct - 2	Ray tracing methods with multi-resolutions	Tracing Ray Differentials, Homan Igehy Siggraph 1999 R-LODs: Fast LOD-based Ray Tracing of Massive Models, Sung-Eui Yoon, Christian Lauterbach, and Dinesh Manocha, Visual Computer (Pacific Graphics), 2006	Updated on 1:30am Sep-27 Submit your chosen topic by Oct-2 before the class time and presentation plan to the instructor
9. Oct - 4 10. Oct - 9 11. Oct - 11 12. Oct - 16	Cache-coherent algorithms	Fast Triangle Reordering for Vertex Locality and Reduced Overdraw Pedro Sander (Hong Kong University of Science and Technology), Diego Nehab (Princeton University), Josh Barczak (Advanced Micro Devices, Inc.), SIGGRAPH 07, Mesh Layouts for Block-Based Caches, Sung-Eui Yoon and Peter Lindstrom, IEEE Tran. on Vis. and Computer Graphics (TVCG) and IEEE Visualization, 2006 Cache-Oblivious Mesh Layouts Sung-Eui Yoon (University of North Carolina at Chapel Hill), Peter Lindstrom, Valerio Pascucci (Lawrence Livermore National Laboratory), Dinesh Manocha (University of North Carolina at Chapel Hill), SIGGRAPH 05 Survey: Out-Of-Core Algorithms for Scientific Visualization and Computer Graphics C. Silva, Y.-J. Chiang, W. Correa, J. El-Sana, and P. Lindstrom, 2003 2003 Martin Isenburg, Peter Lindstrom, Jack Snoeyink, Streaming Compression of Triangle Meshes, EG Symposium on Geometry Processing, 2005.	Updated at 2:00am on 4th of Oct.
13. Oct - 18	Collision detection	Survey: Collision Detection for Deformable Objects M. Teschner, S. Kimmerle, G. Zachmann, B. Heidelberger, Laks Raghupathi, A. Fuhrmann, Marie-Paule Cani, Fran?is Faure, N. Magnetat-Thalmann, W. Strasser Eurographics State-of-the-Art Report (EG-STAR), 2004 Survey: LIN M., MANOCHA D.: Collision and proximity queries. In Handbook of Discrete and Computational Geometry, 2003 , pdf file Prof. Ming Lin's course has very nice introduction on collision detection Continuous Collision Detection for Articulated Models using Taylor Models and Temporal Culling Xinyu Zhang, Stephane Redon, Minkyoung Lee, Young J. Kim , SIGGRAPH 07 CULLIDE: Interactive Collision Detection Between Complex Models in Large Environments using Graphics Hardware Naga K Govindaraju, Stephane Redon, Ming Lin, Dinesh Manocha in ACM SIGGRAPH/Eurographics Graphics Hardware 2003. Fast Collision Detection between Massive Models using Dynamic Simplification, Sung-Eui Yoon, Brian Salomon, Ming Lin, and Dinesh Manocha, ACM SIGGRAPH/Eurographics Symposium on Geometry Processing 2004, Nice, France.	Updated at 11:30pm on Oct-17
14. Oct - 23	Dynamic models	Ray Tracing Dynamic Scenes using Selective Restructuring Sung-Eui Yoon, Sean Curtis, Dinesh Manocha, Eurograhics Symp. on Rendering, 07	Updated at 1:00am on 16th of Oct
12. Oct - 25	Invited talk on continuous collision detection	Prof. YoungJun Kim, Ewha Unvi.
Oct - 30	No class (IEEE Visualization)
Nov - 1	No class (IEEE Visualization)
16. Nov - 6	YongJun Lee's talk		Submit a mid-term report within today (send it to the email address of the instructor with a subject [CS780])
17. Nov - 8	NaeJin Kong's talk
18. Nov - 13	SangWook Yu's talk
19. Nov - 15	SeokHoon Kim's talk
20. Nov - 20	YoungJun Kim's talk
21. Nov - 22	DaSung Han's talk
22. Nov - 27	JungHyun Kim's talk
23. Nov - 29	JaeSung Yoon's talk
24. Dec - 4	No Class
25. Dec - 6	Final presentations, Seok Hoon Kim, SangWok Yu, YongJun Lee, and JaeSung Yoon
26. Dec - 11	Final presentations, YoungJun Kim, NaeJin Kong, DaSung Han, and JungHyun Kim
27. Dec - 13	Summary of the course		Submit a final-term report

Related topics, but will not be covered in the class due to time constratins

Images/Textures	Scene Completion Using Millions of Photographs James Hays, Alexei A. Efros (Carnegie Mellon University) , SIGGRAPH 07 Capturing and Viewing Gigapixel Images Johannes Kopf (Universit? Konstanz), Matt Uyttendaele (Microsoft Research), Oliver Deussen (Universit? Konstanz), Michael Cohen (Microsoft Research), SIGGRAPH 07 Efficient Gradient-Domain Compositing Using Quadtrees Aseem Agarwala (Adobe Systems, Inc.), SIGGRAPh 07
Global illumination	Matrix Row-Column Sampling for the Many-Light Problem Milos Hasan (Cornell University), Fabio Pellacini (Dartmouth College), Kavita Bala (Cornell University), SIGGRAPH 07 Incremental Instant Radiosity for Real-Time Indirect Illumination Samuli Laine, Hannu Saransaari, Janne Kontkanen, Jaakko Lehtinen, Timo Aila, Eurographics Symp. on Rendering 07 Implicit Visibility and Antiradiance for Interactive Global Illumination Carsten Dachsbacher (REVES/INRIA Sophia-Antipolis), Marc Stamminger (Universit? Erlangen-N?nberg ), George Drettakis (REVES/INRIA Sopia-Antipolis), Frédo Durand (Massachusetts Institute of Technology, Computer Science and Artificial Intelligence Laboratory), SIGGRAPH 07
Path planning	Prof. David Hsu's course on "Motion planning" Prof. Dinesh Manocha's course on Motion planning Motion Planning: A Journey of Robots, Molecules, Digital Actors and Other Artifacts, Jean-Claude Latombe, 1999 LaValle's book on Planning Algorithm
Data compression	Survey: Recent advances in compression of 3D meshes, P. Alliez and C. Gotsman, Springer, 2005. Compressed Random-Access Trees for Spatially Coherent Data Sylvain Lefebvre, Hugues Hoppe, Eurographics Symp. on Rendering, 07 Compression of Motion Capture Databases Okan Arikan (University of Texas at Austin), ACM SIGGRAPH 06 Rendering from Compressed High Dynamic Range Textures on Programmable Graphics Hardware Lvdi Wang, Xi Wang, Peter-Pike Sloan, Li-Yi Wei, Xin Tong, Baining Guo SIGGRAPH Symposium on Interactive 3D Graphics and Games 2007 Random-Accessible Compressed Triangle Meshes , Sung-Eui Yoon and Peter Lindstrom, IEEE TVCG and Visualization 07 Martin Isenburg, Stefan Gumhold, Out-of-Core Compression for Gigantic Polygon Meshes, Proceedings of SIGGRAPH'03

Grade policy

The class grade of each student is determined by

Student presentations and reports

For your presentations, please use the this powerpoint template.

Additional reference materials and links

Copyright 2007. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the author.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.