Topology determination, decomposable shape generation, and structured mesh generation

• US 7,714,867 B2
• Filed: 09/16/2008
• Issued: 05/11/2010
• Est. Priority Date: 06/27/2003
• Status: Active Grant

• Current Assignee: Activision Publishing Incorporated (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Doi, Jun, Inoue, Keisuke, Yamada, Atsuhshi
• Primary Examiner(s): NGUYEN, PHU K
• Application Number:
  US12/211,521
• Publication Number:
  US 20090128559A1
• Time in Patent Office: 602 Days
• Field of Search: 345/419, 345/420, 345/421, 345/441, 345/619, 345/620
• US Class Current: 345/441
• CPC Class Codes: G06T 17/10 Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes

Abstract

Enables efficient correction of topological consistency of an input three-dimensional shape approximated in a spatial graph. Structured mesh generation systems of the present invention include: a topology determination apparatus for reading shape data from a shape data storage device to determine topological consistency and outputting data for solving a problem about topological consistency; a decomposable shape generation apparatus for reading the data outputted by the topology determination apparatus, changing a constraint condition of an integer programming problem solver to execute a shape correction process and outputting corrected shape data; and a structured mesh generation apparatus for reading the corrected shape data to generate a structured mesh.

Claims

1. A method 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, the method causing the computer to execute steps of:

reading a 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.

2. The method according to claim 1, wherein the step of determining topological consistency comprises a step of listing the number of intersections that exist in the shape element coupling the selected pair of intersections and storing the list in a memory.

3. The method according to claim 1, wherein the step of causing the causal intersection pair to be identified in the causal intersection list executes a step of deleting intersection pairs other than the causal intersection pair from

the causal intersection list or a step of inserting an identifier indicating that the causal intersection is a causal intersections pair.

4. The method according to claim 1, wherein the step of determining topological consistency comprises a step of determining the selected intersection pair to be a causal intersection pair with the use of the parity of the number of the intersections.

5. The method according to claim 1, further comprising:

reading the causal intersection list generated to determine a causal intersection pair;

reading a constraint condition and an objective function for an integer programming problem for eliminating the causal intersection pair included in the causal intersection list from the storage device;

reading shape data from a shape data storage device to specify a shape element that provides the causal intersection pair;

using the constraint condition and the objective function to numerically calculate the integer programming problem and correct the shape data; and

updating the shape data including the causal intersection pair with corrected shape data obtained as a result of the numerical calculation and storing the updated shape data.

6. The method according to claim 5, wherein the shape correction step comprises a step of determining an unprocessed causal intersection pair in the causal intersection list and a step of reading updated shape data in response to the determination until there is no unprocessed causal intersection pair.

7. The method according to claim 5, wherein the shape correction step reads the constraint condition for correcting the position of the shape element constituting the specified causal intersection pair from the storage device.

8. The method according to claim 5, further comprising:

a step of reading shape data including no causal intersection pair from the shape data storage device;

generating structured mesh data using a two-dimensional shape or a polyhedron, from an outer edge toward the inside of the read shape data; and

storing the generated structured mesh data in a storage device.

9. 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.

10. 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.