Prism Trees: An Efficient Representation for Manipulating and Displaying Polyhedra with Many Faces.

Abstract

Computing surface and/or object intersections is a cornerstone of many algorithms in Geometric Modelling and Computer Graphic, for example Set Operations between solids, or surfaces Ray Casting display. This document presents an object centered, information preserving, hierarchical representation for polyhedra called Prism Tree. The author uses the representation to decompose the intersection algorithms into two steps: the localization of intersections, and their processing. When dealing with polyhedra with many faces (typically more than one thousand), the first step is by far the most expensive. The Prism Tree structure is used to compute efficiently this localization step. A preliminary implementation of the Set Operations and Ray Casting algorithms has been constructed. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1985
Accession Number
ADA162601

Entities

People

  • Jean Ponce

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Computational Science
  • Computer Graphics
  • Computer Vision
  • Computers
  • Graphics
  • Hierarchies
  • Information Systems
  • Laser Rangefinding
  • Lasers
  • Military Research
  • Polygons
  • Ray Tracing
  • Stochastic Processes
  • Triangles

Fields of Study

  • Computer science

Readers

  • Computational Modeling and Simulation
  • Graph Algorithms and Convex Optimization.
  • Image Processing and Computer Vision.