Next: Euler's Formula Up: Polyhedral Data Structures Previous: Polyhedral Data Structures

# 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

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

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

• 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

CS488/688: Introduction to Interactive Computer Graphics
University of Waterloo
Computer Graphics Lab

cs488@cgl.uwaterloo.ca