Meeting 26: Course Summary

Talk tomorrow:
    Pat Hanrahan, 330pm in 34-101 (refreshments at 315)
    Digital Lights, Cameras, and Materials

Final project presentations:
    40 minute slots, arrange via e-mail to bryt@graphics

Some big questions in geometric computing:

• Capture
• Representation
• Inspection
• Responsiveness
• Simulation
• Design
• Visual inspection

•  Representation I
• Geometric primitives
• Operators (sidedness, etc.)
• Constructions vs. Closed-form expressions
  
  
• Duality!
• ... of geometric primitives
• ... of topological structure
  
  
• Adjacency data structures
• Winged-edge, quad-edge, etc.
  
  
• Workhorse algorithms
• Convex hull (2D, 3D, general d)
• Delaunay Triangulation/Voronoi Diagram
• Quadtree/Octree/k-D tree
• Linear programming
• Arrangements
  
  
•  Representation II
• 3D surfaces/solids
• Implicit, boundary, discretized
• Parametric curves and surfaces
  
  
•  Lifting transforms, geometric reductions
• Voronoi diagram (d-dim) to convex hull (d+1 - dim
• Using existing algorithm to solve a new problem
  
  
•  Degeneracy !
• Notion of general position (generic input)
•  Robust predicates: more precision, SoS, ...
  
  
• Hybrid data structures
• Arrangements of parametric curves/surfaces
  
  
• Algorithmic paradigms
• Brute-force, divide & conquer, incremental, sweep-line/plane
• Kinetic framework
  
  
• Iterative algorithms
• Estimating camera positions, features
• Estimating point/line nearest to k 3D lines
  
  
• Applications
• Surface reconstruction from volume data (marching cubes
• Visibility (aspect graph, 3D linespace)
• Radiance field capture (3D linespace)
• Semi-automatic IK skeletons (3D voronoi, medial axis)
• Architectural visibility (BSP trees, constrained search)
• 3D reconstruction from imagery (robust stats, sweep algs)

• Interpolation by curves, surfaces
• ... given some number of samples of a function,
  estimate the function at some other points
• Ideas ?
  
  
• Subdivision surfaces
• Curved surface generation through subdivision & averaging
  
  
• Terrain and GIS (geographic information systems)
• Data with attributes (income, race, children...)
• External memory algorithms/Adaptivity/Responsiveness
  
  
• Mesh generation
• CFD (air flow, etc.)
• Constrained tetrahedralization/hexahedralization
• Even harder: do so with bounded aspect ratio!
• Parallelization
  
  
• Minimum spanning trees
• Cosmology, organic systems, network design...
  
  
• Assembly planning
• Motion planning, grasping, assembly sequences
  
  
• CAD
• Interference detection, LOD, interaction & editing
• Intuitive 3D modeling operations
  
  
• CAM
• Tool sequencing, material use optimization
  
  
• Protein folding
• What shape does a given base-pair sequence assume?
  
  
• Computational drug design
• design molecule to bind to a given receptor
  
  
• VLSI design
• Routing; dissipation; 3D structures
  
  
• Graph drawing
• Genealogy, power networks, dynamic systems
  
  
• Alignment
• ... of DNA sequences
• ... of multiple 3D observations (MRI, range data, etc.)
  
  
• Medical Imaging
• 3D reconstruction from voxels, slices, etc.

• Capture via sensors
• Cameras, range-sensors, MRI ...
• Information hiding
• Geometric abstraction
• Robustness
• Self-checking codes; abstraction
• Responsiveness in the face of complexity
• Efficient data structures; external memory
• Responsiveness in the face of change
• Kinetic data structures
• Continuous / discrete hybrids
• Physically-based simulation
• Pedagogy!
• Visual inspection, exposition

Summary

• Course introduced a collection of tools & techniques for
• Representation (analytic/approximate)
• Construction & Maintenance
• Inspection & Simulation
• Maintaining responsiveness
• Application building
• Visual, analytic inspection

Last Meeting .... Next Meeting .... Course Page .... Meeting Schedule

Created: Feb 1998