COMP 790-058: Fall 2006

Topics to be covered

1. Geometric Data Structures for Dynamic Datasets
2. Interactive Ray Tracing of Dynamic Scenes
3. Motion Planning in Dynamic Envoronments
4. Proximity Queries between Deformable Models
5. Interactive Visualization of Time-varying Datasets
6. Dynamic Texture Synthesis

Geometric Data Structures for Dynamic Datasets

Spatial and bounding volume hierarchies

Kinetic data structures

Incremental algorithms

Interactive Ray Tracing of Dynamic Scenes

Overview

• Introduction, general advantages
• Other applications of ray tracing (line-of-sight, visibility, ...)
• kd-tree intro and traversal, SAH construction
• Other acceleration structures (BVH, grid-based)
• Ray packets and frusta

Issues

• Animation breaks precomputed structure
• Different types of animated scenes
• Hierarchical motion
• deforming models
• unstructured
• Rebuilding vs. updating, issues with kd-tree
• Older approaches (spacetime, high-level tree, ...)

Recent approaches

• BVH and updates, rebuild heuristic, (s-kd-trees)
• Coherent Grid Traversal
• kd-tree based approaches (razor, motion decomposition, ...)
• Recent hardware systems, i.e. bkd-tree

Future work

Motion Planning in Dynamic Envoronments

Basic Motion Planning in Dynamic Environments

• Define the basic problem, general principles, variants
  • Configuration spaces
  • R2, R2 x S1, etc
• Classes of path planners
  • Cell Decomposition
  • Potential Field
  • Roadmap (both PRM and RRT, possibly SRT/RRF)
• Introduction notion of dynamic obstacles etc

Situations and Complications of extending to dynamic domains

• Configuration x time, state space
• Sensor/localization error (necessary to fix changes even in a static environment)
• Known obstacle motion (a.k.a. perfectly predicted motion)
• Unknown obstacle motion
  • An aside for pursuer-evader problem
• Inevitable collision states
• Obstacle/robot interactions or manipulation
  • Further, if robot can manipulate scene, the obstacle configuration space
    (i.e. the robot may need to alter the configuration of the obstacles in order to solve the problem)
• Bottlenecks
  • Generically, Nearest Neighbor, Collision Query, Link query, etc
  • In specialized cases, distance fields, other potential fields

Solving the problem, more deterministic approaches

• Fast replanning for cell decomposition (D* algorithm)
• Constraint-based motion planning (utilizing GPUs for fast distance distance field generation)
• V-Plan-based

Randomized Approaches

• Kinodynamic PRM
• Deformable robot in a Deformable environment
  • Planning in manipulation forces space
• ICRA 06, Replanning with RRTs
• If allowed by Sandia, our RRT-based approach

Proximity Queries between Deformable Models

Interactive Visualization of Time-varying Datasets

Dynamic Texture Synthesis

NOTE: Papers marked with "**" before them are strongly recommended reading (available from the papers/resources page).

Introduction to Texture Synthesis

• Importance and Applications
• Parametrization/Dimensionality
• 2D (IMAGE, surface)
• 3D (volume, VIDEO, DYNAMIC SURFACE)
• 4D (animated volume, view-dependent, lightfield)
• 6D (Bidirectional texture functions - BTF - lighting + view dependent)
• Synthesis Paradigms
• Parametric vs. Non-parametric synthesis
• Procedural vs. Example-based
• Optimization-based
• Non-parametric pixel-based texture synthesis
• Markov Random Field formulation
• Efros'99, **Wei'00
• Nearest neighbor search (computational bottleneck)

Video Texture Synthesis

• Video Textures (**Schoedl'00)
• Time as dimension
• Looping video (exploit repetitiveness)
• Temporal neighborhoods for matching
• Incoporating future information (optimizing loops through Reinforcement-learning)
• Dynamic Textures (Soatto'01)
• Parametric approach (System Identification)
• Precomputation of temporal texture information

Visual Stitching in Space-Time

• Image Quilting (**Efros'01)
• Patches better than pixels (higher visual continuity)i
• Hiding of seams between blocks
• Graphcut Textures (**Kwatra'03)
• General seam finding algorithm (no restriction on dimension)i
• 3D application: Spatio-temporal video textures
• Graphcut Image Merging + Interactive Photomontage (Kwatra'03, Agrawala'04)
• Video Panoramas (even higher dimensional dataset)
• Panoramic Video Textures (Agrawala'05)
• Dynamosaics (Rav-Acha'05)

Lighting/View Dependent Synthesis on Surfaces

• Surface Texture Synthesis (Turk'01,Wei'01)
• Dynamic Lighting and Viewpoint Textures (**Tong'02)
• Bidirectional Texture Functions (BTFs)
• Storage and compression of BTFs
• K-coherence search

Dynamic (Time-varying) Controllable Texture Synthesis

• Texture Optimization for Controllable Synthesis (**Kwatra'05)
  • Optimization of Texture Quality
  • Flow-guided Texture Animation
  • Temporal coherence + Visual continuity
• Dynamic Surface Texture Synthesis (**Kwatra'06)
• Fluid Texturing
• Parametrization and Matching
• Temporal coherence (color + orientation)

Interactive Synthesis

• Real-time Synthesis on GPU (Lefebvre'05)
• Appearance Space Synthesis (**Lefebvre'06)
• Deformation field based interaction
• Flow guided synthesis
• Flow-based Video Synthesis and Editing (Bhat'04)
• User-specified flow lines
• Interactive Fluid Video Synthesis