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

CS780: Scalable Graphics/Geometric Algorithms (Fall 2007)

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
Prerequisites: Undergraudate computer graphics or equivalent OR Instructor's approval
Textbook: Course Notes and In-Class Handouts



  • Course overview
  • Lectures and tentative schedule
  • Grade policy
  • Student presentations
  • Additional reference materials
  • Line

    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:

  • Multi-resolution methods
  • Data layout optimization and computational re-ordering
  • Data compression
  • Culling techniques
  • 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:

  • Broad understanding on various topics related to computer graphics, geometric problems, and visualization
  • In-depth knowledge on dealing with massive geometric data sets
  • What you will do:

  • Become the in-class expert on a topic that is most interesting to you; you can bring your own research topic to the class.
  • Present about two talks related to the topic in the course and write a final report on the topic and propose an idea that can make contributions to the topic
  • (No mid nor final exam)
  • Line

    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

  • 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
  • Line

    Grade policy

    The class grade of each student is determined by

  • Class presentation (45%)
  • Mid and final report (45%)
  • Class participation (10%)
  • Line

    Student presentations and reports

    Topic Intro and progress slides Mid-term report Final-term report
    YoungJun Kim Subdivision meshes in GPU Intro slides mid-term report
    SeokHoon Kim Efficient image synthesis for 3D display Intro slides mid-term report
    JaeSung Yoon Hardware design for ray tracing Intro slides mid-term report
    JeongHyun Kim Hardware-driven visibility culling Intro slides mid-term report
    SangWook Yoo Compression of motion/animation data Intro slides mid-term report
    YongJun Lee Multi-resolution cloth simulation Intro slides mid-term report
    DaSeong Han, View-Dependent Articulated-body Simulation with Adaptive Forward Dynamics Intro slides mid-term report
    NaeJin Kong Coherent line drawing from video, NaeJin Kong Intro slides mid-term report

    For your presentations, please use the this powerpoint template.


    Additional reference materials and links

    Paper search:

  • Google scholar
  • Tim Rowley's graphics paper collections
  • Ke-Sen Huang's graphics paper collections
  • Line

    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.