Database and data structure representation for the efficient construction and display of three dimensional polyhedra

A new methodology and notation for the definition and construction of non-convex polyhedra is described. It uses constructive solid geometry to provide the geometric data for the fundamental cells and each composite structure is defined by a combination of such fundamental cells. To demonstrate the general principles behind this methodology we have used the construction techniques to produce crystalline structures. A minimal definition notation is used to construct a discrete surface representation in a standardised format which is used alongside a novel construction algorithm to develop an elaborate data structure representation, referred to as a polygonal mesh. The complexity of explicit description of non-convexity in discrete surface polyhedra is overcome using an extension to the minimal definition notation which permits the description of such polyhedra as a list of predominately convex fundamental cells.Non-convexity in the composite polyhedron will introduce new lines which are not part of the definition but are an artefact of the construction method. The display algorithm must explicitly depict these lines on the view plane of the chosen graphic medium. We have implemented two different methods for generating the final display. The first is a completely new display algorithm that pre-processes the data model to divide the discrete facet surfaces of the non-convex polyhedron into convex regions bounded by line segments. This subdivision renders the additional lines explicit in the data structure model. The second is the quad-tree display algorithm which uses quad-tree encryption to compute the projected image. Pre-processing is unnecessary since the interaction between the component cells is automatically generated during display, and the additional boundary lines will be explicitly drawn on the view plane.A database of fundamental cells and cell combinations is incorporated into the system. The construction algorithm allows interactive definition of an individual cell and its storage as cell polygonal mesh in the database. Thereafter compound structures can be generated either by interactive construction or retrieval of fundamental cells and cell combinations from this database. Any new combination of cells can be retained within the database. Retrieval of information from the database is achieved by reference to various key words, and the underlying database system performs the procedures necessary to maintain the dependencies.