Ray Tracer formats

• How do we store a polyhedron in memory?

  Must consider the following:

  • Memory
  • Efficiency

    Operations

• Will look at three formats
  • Ray Tracer
  • Generalized Ray Tracer
  • Winged-edge variations

Ray Tracer Format

• We already saw one ASCII format (for the ray tracer)
• Data structure for this is simple:
  • Array of points (triples of floats)
  • Array of faces, with pointers to points

  Compact, simple to get face information

• Advantages
  • Space efficient
  • Easy to generate, parse, build data structure
• Disadvantages
  • Vertex neighbors?
  • Modify the data structure?

  Example: What if we want to know faces surround a vertex?

  Radiosity might want this

• Solution: For each point, have a list of pointers to surrounding faces.
  • Can use same ASCII input format
  • Build lists when reading data

  Question: Where do these lists come from?

• Problems still remain:
  • How do we modify a polyhedron?
  • Easy to move vertex
  • Add face or vertex is easy
  • Split face not too hard

  • Delete is hard

    O(n) or leaves holes in our list