Topology determination, decomposable shape generation, and structured mesh generation

• US 7,436,407 B2
• Filed: 06/25/2004
• Issued: 10/14/2008
• Est. Priority Date: 06/27/2003
• Status: Active Grant

• Current Assignee: Activision Publishing Incorporated (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Yamada, Atsushi, Doi, Jun, Inoue, Keisuke
• Primary Examiner(s): Nguyen, Phu K
• Application Number:
  US10/876,952
• Publication Number:
  US 20050007368A1
• Time in Patent Office: 1,572 Days
• Field of Search: 345419-421, 345619-620, 345/441
• 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 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.

2. A topology determination apparatus according to claim 1, wherein the means for determining topological consistency comprises means for listing the number of intersections that exist in the shape element coupling the selected pair of intersections.

3. A topology determination apparatus according to claim 1, wherein the means for causing the causal intersection pair to be identified in the causal intersection list comprises means for deleting intersection pairs other than the causal intersection pair from the causal intersection list or for inserting an identifier indicating that the causal intersection is a causal intersection pair.

4. A topology determination apparatus according to claim 1, wherein the means for determining topological consistency comprises means for determining the selected intersection pair to be a causal intersection pair with the use of the parity of the number of the intersections.

5. A decomposable shape generation apparatus for determining topological consistency of shape data that provides a spatial graph of an input shape and correcting the shape data so that it can be decomposed, the apparatus comprising:

the topology determination apparatus according to claim 1;

a storage device for storing a constraint condition and an objective function for an integer programming problem;

means for referring to a causal intersection list provided by the topology determination apparatus to a read causal intersection pair;

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

shape correction means for reading the constraint condition for eliminating the intersection of the causal intersection pair form the storage device and numerically calculating the integer programming problem to correct the shape data; and

means for 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 decomposable shape generation apparatus according to claim 5, wherein the shape correction means comprises means for determining an unprocessed causal intersection pair in the causal intersection list and means for reading updated shape data in response to the determination until there is no unprocessed causal intersection pair.

7. The decomposable shape generation apparatus according to claim 5, wherein the shape element is at least one of:

a face; and

an edge thereof.

8. The decomposable shape generation apparatus according to claim 5, wherein the shape correction means reads the constraint condition for correction the position of the shape element constituting the specified causal intersection pair from the storage device.

9. A structured mesh generation apparatus, comprising:

the decomposable shape generation apparatus according to claim 5;

means for reading shape data including no causal intersection pair, that is provided by the decomposable shape generation apparatus, from a shape data storage device to generate structured mesh data using a two-dimensional shapes or a polyhedron; and

means for storing the generated structured mesh data in a storage device.

10. The structured mesh generation apparatus according to claim 9, wherein the means for generating structured mesh data comprises means for generating mesh data from the outer edge toward the inside of the shape data.