Rays—New representation for polygons and polyhedra

✍ Scribed by W. Randolph Franklin

• Publisher: Elsevier Science
• Year: 1983
• Weight: 483 KB
• Volume: 22
• Category: Article
• ISSN: 0734-189X
• DOI: 10.1016/0734-189x(83)90080-4

✦ Synopsis

A new data structure for storing polygons and polyhedra is presented. It can handle general cases with multiple disconnected components and nested holes with islands to an arbitrary depth. The advantage of this method is that, as in constructive solid geometry, it can support Boolean operations such as union and intersection on nested hierarchical objects. However, unlike CSG, properties such as area, perimeter, and moment of inertia can also be determined exactly. They can be determined by making one sequential pass through the object (which can be on secondary storage), calculating a scalar function of each ray, and adding the numbers. It is never necessary to determine either the global connectivity or the edges themselves. For polygons, the data structure is a set of semiinfinite rays where each ray also has an associated value, either + or -. Each edge of the polygon is represented by two rays, although these two rays are nowhere tagged as belonging to the same edge, but are interspersed with all the other rays.