Topology determination, decomposable shape generation, and structured mesh generation

A topology determination apparatus for determining topological consistency of shape data that provides a spatial graph of an input shape, the apparatus comprising:

• a shape data storage device for storing the shape data;
• means for reading the shape data from the shape data storage device, calculating positions of intersections of a shape element, generating pairs of the calculated intersection positions to create a causal intersection list and storing the causal intersection list in a memory;
• means for selecting an intersection pair from the causal intersection list and determining topological consistency of the shape element between the selected pair of intersections;
• means for registering the selected intersection pair as a causal intersection pair, in response to the determination of the topological consistency;
• and
• means for causing the causal intersection pair to be identified in the causal intersection list, in response to the registration.