Topology determination, decomposable shape generation, and structured mesh generation

A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for causing a computer to function as a topology determination apparatus for determining topological consistency of shape data that provides a spatial graph of an input shape, said method steps comprising:

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

A computer program product for causing determination of topological consistency of shape data that provides a spatial graph of an input shape, the computer program product comprising:

• a storage medium readable by a processing device and storing instructions for execution by the processing device for performing a method comprising:
• reading the shape data from a shape data storage device;
• calculating intersection positions of shape elements of the read shape data, generating pairs of the calculated intersection positions to create a causal intersection list and storing the causal intersection list in a memory;
• selecting an intersection pair from the causal intersection list and determining topological consistency of the shape element between the selected pair of intersections;
• registering the selected intersection pair
• as a causal intersection pair, in response to the determination of the topological consistency;
• and
• causing the causal intersection pair to be identified in the causal intersection list, in response to the registration.