From CS294-10 Visualization Fa08

Jump to: navigation, search



Group Members

  • James Hamlin


Maps of 3D Environments

"Given a 3D model of a building (or perhaps just a set of floorplans, one per floor) automatically generate maps that show users how to go from any room to any other room. The challenges include: planning the path from room to room and ensuring that the entire path is visible from a single view. Maintaining good visibility is particularly challenging because the floors, walls, and ceilings of the building will occlude the path."

Initial Problem Presentation


Related Work / Bibliography

  1. Chittaro, Gatla, Venkataraman. The Interactive 3D Breakaway Map: a Navigation and Examination Aid for Multi-Floor 3D Worlds
  2. Niederauer, Houston, Agrawala, Humphreys. Un-Invasive Interactive Visualization of Dynamic Architectural Environments
  3. Li, Agrawala, Curless, Salesin. 'Automated Generation of Interactive 3D Exploded View Diagrams
  4. Li, Ritter, Agrawala, Curless, Salesin. Interactive Cutaway Illustrations of Complex 3D Models
  5. Diepstraten, Weiskopf, Ertl. Interactive Cutaway Illustrations
  6. Haumont, Debeir, Sillion. Volumetric cell-and-portal generation
  7. Rosenfeld, Pfaltz. Sequential Operations in Digital Picture Processing

Technical Challenges and Storyboard

  • Finding the shortest path between two rooms.
    • Identify rooms and connections between them. The literature for automatically generating 'cells' and 'portals' for the portal real-time occlusion culling technique may be helpful here.
    • Features such as stairs and elevators must be recognized in the 3D models or floorplans either by automatic detection (for stairs) or as part of the input.
  • Displaying the building and path in a single view such that the entire path is visible.
    • Placing the camera in an optimal location.
    • Employing cutaway views, exploded views, or a combination of these to maintain both path visibility and visibility of important contextual features of the building.
    • Slight deviations from the optimal path might be allowed to improve path visibility.
  • The right combination of camera angle and visibility techniques must be found - simulated annealing might be used to make this choice given a score based on path self-intersection (in the 2D projection), the geometry that must be culled, and any repercussions of the exploded view.


  • 11/15 Optimal path search and a "brute force" visualization algorithm that minimizes path self-intersections and simply culls obstructing geometry.
  • 11/22 Implement the generation of an exploded view of the building and smarter cutaways.
  • 11/29 Implement the search algorithm for optimally placing the camera and applying the techniques for maintaining path visibility.

Midpoint Design Discussion

Final Deliverables

[add comment]
Personal tools