Method and program for converting boundary data into cell inner shape data

• US 7,321,366 B2
• Filed: 02/27/2003
• Issued: 01/22/2008
• Est. Priority Date: 02/28/2002
• Status: Expired due to Fees

• Current Assignee: Riken
• Original Assignee: Riken
• Inventors: Usami, Shugo, Makinouchi, Akitake, Kase, Kiwamu, Teshima, Yoshinori
• Primary Examiner(s): Chauhan; Ulka
• Assistant Examiner(s): WASHBURN, DANIEL C
• Application Number:
  US10/505,224
• Publication Number:
  US 20050216238A1
• Time in Patent Office: 1,790 Days
• Field of Search: 345/424
• US Class Current: 345/424
• CPC Class Codes: B33Y 50/00 Data acquisition or data processing for additive manufacturing
• CPC Class Codes: G06F 30/23 using finite element methods [FEM] or finite difference methods [FDM]
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects

Abstract

A method and a program for converting boundary data into cell inner shape data, includes a division step (A) of dividing external data (12) constituted of the boundary data of an object into cells (13) in an orthogonal grid, a cutting point deciding step (B) of deciding an intersection point of the boundary data and a cell edge as a cell edge cutting point, a boundary deciding step (C) of deciding a boundary formed by connecting the cell edge cutting points as the cell inner shape data, a cell classification step (D) of classifying the divided cells into a nonboundary cell (13a) including no boundary surface and a boundary cell (13b) including a boundary surface, and a boundary cell data classification step (E) of classifying cell data constituting the boundary cell into internal cell data inside the cell inner shape data and external cell data outside the cell inner shape data.

Claims

1. A method for converting boundary data into cell inner shape data, comprising:

a division step (A) of dividing external data constituted of the boundary data of an object into cells in an orthogonal grid;

a cutting point deciding step (B) of deciding an intersection point of the boundary data and a cell edge as a cell edge cutting point;

a boundary deciding step (C) of deciding a boundary formed by connecting the cell edge cutting points as the cell inner shape data;

a cell classification step (D) of classifying the divided cells into a nonboundary cell including no boundary surface and a boundary cell including a boundary surface;

a boundary cell data classification step (E) of classifying cell data constituting the boundary cell into internal cell data inside the cell inner shape data and external cell data outside the cell inner shape data; and

step (F) of outputting the cell inner shape data to a display, wherein the cells are rectangular cells in two-dimensional representation, and

in the cutting point deciding step (B), intersection points of boundary data and cell edges that have totally 2⁴=16 arrangement cases are decided as the cell edge cutting points, and the arrangement cases that become equivalence classes by rotational operation are decided as identical patterns so that the 2⁴=16 arrangement cases are further classified into 6 patterns, and

in the cutting point deciding step (B), as for arrangement of each intersection point, data concerning the rotational operation and data concerning the identical pattern are stored in a storage device, wherein

in the boundary deciding step (C), a boundary line made by connecting the cell edge cutting points is decided as the cell inner shape data for all the 6 patterns.

2. The method according to claim 1, characterized in that:

in the boundary deciding step (C), cell inner shape data patterns that become equivalence classes by three-dimensional rotational operation are decided as identical patterns so that the cell inner shape data patterns are classified into 22 patterns.

3. The method according to claim 1, further comprising the step of:

showing images on the display using the cell inner shape data.

4. A computer readable medium encoded with a program for converting boundary data into cell inner shape data, wherein the program causes a computer to execute:

a division step (A) of dividing external data constituted of boundary data of an object into cells in an orthogonal grid;

a cutting point deciding step (B) of deciding an intersection point of the boundary data and a cell edge as a cell edge cutting point;

a boundary deciding step (C) of deciding a boundary connecting formed by the cell edge cutting points as the cell inner shape data;

a cell classification step (D) of classifying the divided cells into a nonboundary cell including no boundary surface and a boundary cell including a boundary surface;

a boundary cell data classification step (E) of classifying cell data constituting the boundary cell into internal cell data inside the cell inner shape data and external cell data outside the cell inner shape data; and

step (F) of outputting the cell inner shape data to a display, wherein the cells are rectangular cells in two-dimensional representation, and

in the cutting point deciding step (B), intersection points of boundary data and cell edges that have totally 2⁴=16 arrangement cases are decided as the cell edge cutting points, and the arrangement cases that become equivalence classes by rotational operation are decided as identical patterns so that the 2⁴=16 arrangement cases are further classified into 6 patterns, and

in the cutting point deciding step (B), as for arrangement of each intersection point, data concerning the rotational operation and data concerning the identical pattern are stored in a storage device, wherein

in the boundary deciding step (C), a boundary line made by connecting the cell edge cutting points is decided as the cell inner shape data for all the 6 patterns.

5. The program according to claim 4, wherein the program further causes the computer to execute the step of:

showing images on the display using the cell inner shape data.

6. A method for converting boundary data into cell inner shape data, comprising the steps of:

(A) dividing external data constituted of the boundary data of an object into cells in an orthogonal grid;

(B) deciding an intersection point of the boundary data and a cell edge as a cell edge cutting point;

(C) deciding a boundary formed by connecting the cell edge cutting points as the cell inner shape data;

(D) classifying the divided cells into a nonboundary cell including no boundary surface and a boundary cell including a boundary surface;

(E) classifying cell data constituting the boundary cell into internal cell data inside the cell inner shape data and external cell data outside the cell inner shape data; and

(F) outputting the cell inner shape data to a display, wherein the cells are rectangular cells in two-dimensional representation, and

in step (B), intersection points of boundary data and cell edges that have totally 2⁴=16 arrangement cases are decided as the cell edge cutting points, and the arrangement cases that become equivalence classes by rotational operation are decided as identical patterns so that the 2⁴=16 arrangement cases are further classified into 6 patterns, and

in step (B), as for arrangement of each intersection point, data concerning the rotational operation and data concerning the identical pattern are stored in a storage device.

7. The method according to claim 6, further comprising the step of:

showing images on the display using the cell inner shape data.

8. A computer readable medium encoded with a program for converting boundary data into cell inner shape data, wherein the program causes a computer to execute the steps comprising:

(A) dividing external data constituted of boundary data of an object into cells in an orthogonal grid;

(B) deciding an intersection point of the boundary data and a cell edge as a cell edge cutting point;

(C) deciding a boundary connecting formed by the cell edge cutting points as the cell inner shape data;

(D) classifying the divided cells into a nonboundary cell including no boundary surface and a boundary cell including a boundary surface;

(E) classifying cell data constituting the boundary cell into internal cell data inside the cell inner shape data and external cell data outside the cell inner shape data; and

(F) outputting the cell inner shape data to a display, wherein the cells are rectangular cells in two-dimensional representation, and

in step (B), intersection points of boundary data and cell edges that have totally 2⁴=16 arrangement cases are decided as the cell edge cutting points, and the arrangement cases that become equivalence classes by rotational operation are decided as identical patterns so that the 2⁴=16 arrangement cases are further classified into 6 patterns, and

in step (B), as for arrangement of each intersection point, data concerning the rotational operation and data concerning the identical pattern are stored in a storage device.

9. The program according to claim 8, wherein the program further causes the computer to execute the step of:

showing images on the display using the cell inner shape data.

10. A method for converting boundary data into cell inner shape data, comprising:

a division step (A) of dividing external data constituted of the boundary data of an object into cells in an orthogonal grid;

a cutting point deciding step (B) of deciding an intersection point of the boundary data and a cell edge as a cell edge cutting point;

a boundary deciding step (C) of deciding a boundary formed by connecting the cell edge cutting points as the cell inner shape data;

a cell classification step (D) of classifying the divided cells into a nonboundary cell including no boundary surface and a boundary cell including a boundary surface;

a boundary cell data classification step (E) of classifying cell data constituting the boundary cell into internal cell data inside the cell inner shape data and external cell data outside the cell inner shape data; and

step (F) of outputting the cell inner shape data to a display, wherein the cells are rectangular parallelepiped cells, and

in the cutting point deciding step (B), intersection points of boundary data and cell edges that have totally 2¹²=4096 arrangement cases are decided as the cell edge cutting points, and the arrangement cases that become equivalence classes by rotational operation and mirroring operation are decided as identical patterns so that the 2¹²=4096 arrangement cases are further classified into 144 patterns, and

in the cutting point deciding step (B), as for arrangement of each intersection point, data concerning the rotational operation and mirroring operation and data concerning the identical pattern are stored in a storage device, wherein

in the boundary deciding step (C), a boundary line made by connecting the cell edge cutting points is decided as the cell inner shape data for all the 144 patterns.

11. The method according to claim 10, characterized in that:

in the cutting point deciding step (B), the cell edge cutting point patterns that become equivalence classes by an inversion operation regarding presence/nonpresence of cutting points are decided as identical patterns so that the cell edge cutting point patterns are classified into 87 patterns in which the number of the cell edge cutting points is 0 to 6.

12. The method according to claim 10, further comprising the step of:

showing images on the display using the cell inner shape data.

13. A method for converting boundary data into cell inner shape data, comprising the steps of:

(A) dividing external data constituted of the boundary data of an object into cells in an orthogonal grid;

(B) deciding an intersection point of the boundary data and a cell edge as a cell edge cutting point;

(C) deciding a boundary formed by connecting the cell edge cutting points as the cell inner shape data;

(D) classifying the divided cells into a nonboundary cell including no boundary surface and a boundary cell including a boundary surface;

(E) classifying cell data constituting the boundary cell into internal cell data inside the cell inner shape data and external cell data outside the cell inner shape data; and

(F) outputting the cell inner shape data to a display, wherein the cells are rectangular parallelepiped cells, and

in step (B), intersection points of boundary data and cell edges that have totally 2¹²=4096 arrangement cases are decided as the cell edge cutting points, and the arrangement cases that become equivalence classes by rotational operation and mirroring operation are decided as identical patterns so that the 2¹²=4096 arrangement cases are further classified into 144 patterns, and

in step (B), as for arrangement of each intersection point, data concerning the rotational operation and mirroring operation and data concerning the identical pattern are stored in a storage device.

14. The method according to claim 13, further comprising the step of:

showing images on the display using the cell inner shape data.

15. A computer readable medium encoded with a program for converting boundary data into cell inner shape data, wherein the program causes a computer to execute:

a division step (A) of dividing external data constituted of the boundary data of an object into cells in an orthogonal grid;

a cutting point deciding step (B) of deciding an intersection point of the boundary data and a cell edge as a cell edge cutting point;

a boundary deciding step (C) of deciding a boundary formed by connecting the cell edge cutting points as the cell inner shape data;

a cell classification step (D) of classifying the divided cells into a nonboundary cell including no boundary surface and a boundary cell including a boundary surface;

a boundary cell data classification step (E) of classifying cell data constituting the boundary cell into internal cell data inside the cell inner shape data and external cell data outside the cell inner shape data; and

step (F) of outputting the cell inner shape data to a display, wherein the cells are rectangular parallelepiped cells, and

in the cutting point deciding step (B), intersection points of boundary data and cell edges that have totally 2¹²=4096 arrangement cases are decided as the cell edge cutting points, and the arrangement cases that become equivalence classes by rotational operation and mirroring operation are decided as identical patterns so that the 2¹²=4096 arrangement cases are further classified into 144 patterns, and

in the cutting point deciding step (B), as for arrangement of each intersection point, data concerning the rotational operation and mirroring operation and data concerning the identical pattern are stored in a storage device, wherein

in the boundary deciding step (C), a boundary line made by connecting the cell edge cutting points is decided as the cell inner shape data for all the 144 patterns.

16. The program according to claim 15, wherein the program further causes the computer to execute the step of:

showing images on the display using the cell inner shape data.

17. A computer readable medium encoded with a program for converting boundary data into cell inner shape data, wherein the program causes a computer to execute the steps comprising:

(A) dividing external data constituted of the boundary data of an object into cells in an orthogonal grid;

(B) deciding an intersection point of the boundary data and a cell edge as a cell edge cutting point;

(C) deciding a boundary formed by connecting the cell edge cutting points as the cell inner shape data;

(D) classifying the divided cells into a nonboundary cell including no boundary surface and a boundary cell including a boundary surface;

(E) classifying cell data constituting the boundary cell into internal cell data inside the cell inner shape data and external cell data outside the cell inner shape data; and

(F) outputting the cell inner shape data to a display, wherein the cells are rectangular parallelepiped cells, and

in step (B), intersection points of boundary data and cell edges that have totally 2¹²=4096 arrangement cases are decided as the cell edge cutting points, and the arrangement cases that become equivalence classes by rotational operation and mirroring operation are decided as identical patterns so that the 2¹²=4096 arrangement cases are further classified into 144 patterns, and

in step (B), as for arrangement of each intersection point, data concerning the rotational operation and mirroring operation and data concerning the identical pattern are stored in a storage device.

18. The program according to claim 17, wherein the program further causes the computer to execute the step of:

showing images on the display using the cell inner shape data.