Shape processor and method for representing shape

• US 20050007367A1
• Filed: 05/05/2004
• Published: 01/13/2005
• Est. Priority Date: 11/06/2001
• Status: Active Grant

• Current Assignee: Naoto Morikawa
• Original Assignee: Naoto Morikawa
• Inventors: Morikawa, Naoto
• Granted Patent: US 7,477,249 B2
• Time in Patent Office: Days
• US Class Current: 345/441
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A shape processor for processing an objective shape in a three-dimensional space while approximating, characterized by comprising an approximating section for generating a basic tile chain, i.e., a chain of basic tiles approximating the structure of the objective shape partially or entirely, by connecting the basic tiles of predetermined three dimensional shape having substantially tetrahedral shape including four vertexes sequentially starting with a starting point basic tile on the face of the basic tile.

Claims

1. A shape processor for imitating a shape of an object in a two-dimensional space, comprising:

an approximation unit operable to generate a chain of basic tiles which imitates the shape of the object by connecting a basic tile with a following tile by an edge one by one from an initial tile, wherein the basic tile comprises a predetermined set of basic tiles of two-dimensional shapes; and

a generation unit operable to generate a three-dimensional shape by specifying whether each basic block is assigned to corresponding basic space, wherein the basic block are assignable to each basic space, which is the convex hull of eight points of a lattice in a three-dimensional space, and the basic block includes one reference vertex and division lines, wherein the reference vertex corresponds to a vertex which is shared by the predetermined three faces that are to be projected onto the predetermined two-dimensional plane simultaneously, and the division line corresponds to the line drawn from the reference vertex to its opposite vertex of the corresponding face,

the generation unit

corresponds to a part or all of the chain of the divided faces obtained by projecting the divided faces into the two-dimensional space, wherein the divided faces are divided by the corresponding division line from the face of one or more of the basic block(s) assigned in the basic space,

assigns each of the basic blocks to the corresponding basic space, and

generates a three-dimensional shape that corresponds to the shape of an object

so that two adjacent basic tiles in the basic tile chain corresponds a part or all of shape obtained by projecting the divided-faces of one basic block or two consecutive basic blocks in the three-dimensional space into the two-dimensional space.

3. The shape processor as recited in claim 1, wherein the generation unit chooses a set of points of the lattice to generate a three-dimensional shape by assigning basic blocks to all of the basic spaces which correspond to triangular pyramids defined by the chosen points of the lattice, and

the generation unit further comprises an administration unit operable to keeps the generated shape as a set of points.

2. A shape processor for imitating a shape of an object in a two-dimensional space, comprising a generation unit operable to generate three-dimensional shape defined by designating whether each basic blocks assignable to a basic space surrounded by eight points of a lattice in a three-dimensional space is to be assigned to the corresponding basic space, so that a two-dimensional shape, which is defined by projecting it into a direction where three faces of the basic block consisting of the three-dimensional shape may be seen, imitates the shape of the object, wherein

the basic block is divided into two divided faces by a line connecting a reference vertex and a vertex positioned diagonally with respect to the reference vertex of the faces, wherein the reference vertex is a vertex shared by the three faces of the basic block,

the generation unit executes:

a first step of choosing one of the divided-faces of a basic block as the initial reference divided-face and one of the two edges of the initial reference divided-face that are edges of the corresponding basic block as the reference edge;

a second step of choosing one of the two divided-faces which share the reference edge with the reference divided-face and whose image by the projection into the predetermined plane do not overlap with the image of the reference divided-face by the same projection, wherein the generation unit chooses the divided-face in such a way that the projection of the chosen divided-face imitates a part or all of the shape of the object;

a third step of choosing the divided-face chosen in the second step as the new reference divided-face; and

a fourth step of choosing the other edge of the new reference divided-face that is not the division line as the new reference edge,

a chain of the divided-faces that were chosen as reference divided-faces during the execution is obtained by executing the steps from the second step to the fourth step repeatedly,

the two-dimensional shape obtained by the projection of the chain into the predetermined plane imitates the shape of the object, and

the generation unit generates a three-dimensional shape by assigning basic blocks that contains one of the divided-faces of the chain to their corresponding basic space.

4. The shape processor as recited in claim 2, wherein the generation unit encodes the generated shape by assigning a value 0 or 1 to each divided-faces of the chain according to the choice in the second step.

5. A shape processor for imitating a shape of an object in a three-dimensional space, comprising:

an approximation unit operable to generate a chain of basic tiles which imitates the shape of the object by connecting a basic tile with a following tile by an face one by one from an initial tile, wherein the basic tile comprises a predetermined set of basic tiles of three-dimensional shapes; and

a generation unit operable to generate a four-dimensional shape by specifying whether each basic block is assigned to corresponding basic space, wherein the basic block are assignable to each basic space, which is the convex hull of sixteen points of a lattice in a four-dimensional space,

the basic block comprises four hyperfaces projected into the three-dimensional space,

each of the four hyperfaces of the basic block is divided into six division hyperfaces by a division face, which is a face including either of a reference vertex shared by the four hyperface of the basic block, a vertex positioned opposite from the reference vertex on the hyperfaces, or another vertex on the hyperfaces,

the generation unit

corresponds to a part or all of the chain of the divided hyperfaces obtained by projecting the divided hyperfaces into the three-dimensional space, wherein the divided hyperface are included by each of the hyperfaces of the basic block assigned in the basic space,

assigns each of the basic blocks to the corresponding basic space, and

generates a four-dimensional shape

so that two adjacent basic tiles in the basic tile chain corresponds a part or all of shape obtained by projecting the divided-hyperfaces of one basic block or two consecutive basic blocks in the four-dimensional space into the three-dimensional space.

7. The shape processor as recited in claim 5, wherein the generation unit chooses a set of points of the lattice to generate a four-dimensional shape by assigning basic blocks to all of the basic spaces which correspond to triangular pyramids defined by the chosen points of the lattice, and

the generation unit further comprises an administration unit operable to keeps the generated shape as a set of points.

6. A shape processor for imitating the shape of an object in a three-dimensional space, comprising a generation unit operable to generate four-dimensional shape defined by designating whether each basic blocks assignable to each basic space surrounded by sixteen points of a lattice in a four-dimensional space is to be assigned to the corresponding basic space, so that a three-dimensional shape, which is defined by projecting it into a direction where three hyperfaces of the basic block consisting of the four-dimensional shape may be seen, imitates the shape of the object, wherein

each of the hyperfaces of the basic block is divided into six divided hyperfaces by a division surface, which is a surface including either of a reference vertex which is a vertex shared by the four hyperfaces of the basic block projected into the projection direction, a vertex located opposite from the reference vertex on the hyperfaces, or another vertex on the hyperface,

the generation unit executes:

a first step of choosing one of the divided-hyperfaces of a basic block as the initial reference divided-hyperface and one of the two faces of the initial reference divided-hyperface that are faces of the corresponding basic block as the reference face;

a second step of choosing one of the two divided-hyperfaces which share the reference face with the reference divided-hyperface and whose image by the projection into the predetermined plane do not overlap with the image of the reference divided-hyperface by the same projection, wherein the generation unit chooses the divided-hyperface in such a way that the projection of the chosen divided-hyperface imitates a part or all of the shape of the object;

a third step of choosing the divided-hyperface chosen in the second step as the new reference divided-hyperface; and

a fourth step of choosing the other face of the new reference divided-hyperface that is not the division line as the new reference face,

a chain of the divided-hyperfaces that were chosen as reference divided-hyperfaces during the execution is obtained by executing the steps from the second step to the fourth step repeatedly,

the three-dimensional shape obtained by the projection of the chain into the predetermined plane imitates the shape of the object, and

the generation unit generates a four-dimensional shape by assigning basic blocks that contains one of the divided-hyperfaces of the chain to their corresponding basic space.

8. The shape processor as recited in claim 6, wherein the generation unit encodes the generated shape by assigning a value 0 or 1 to each divided-faces of the chain when one choose them in the second step.

9. A shape processor for imitating the structure of a polymer in a three-dimensional space, comprising an approximation unit operable to generate a chain of basic tiles to imitates a part or all of the structure of a polymer, wherein the shape of the basic tile is a kind of tetrahedron, that is, a three-dimensional shape with four vertices, and the chain of basic tiles is generated by connecting a basic tile with the following tile by an face one by one from a initial tile.

10. The shape processor as recited in claim 9, further comprising a generation unit operable to generate a four-dimensional shape defined by the assignment of the basic block by specifying whether each basic block is assigned to corresponding basic space, wherein the basic block are assignable to each basic space, which is the convex hull of sixteen points of a lattice in a four-dimensional space,

the basic block comprises four hyperfaces projected into the three-dimensional space,

each of the four hyperfaces of the basic block is divided into six division hyperfaces by a division face, which is a face including either of a reference vertex shared by the four hyperface of the basic block, a vertex positioned opposite from the reference vertex on the hyperfaces, or another vertex on the hyperfaces,

the generation unit

corresponds to a part or all of the chain of the divided hyperfaces obtained by projecting the divided hyperfaces into the three-dimensional space, wherein the divided hyperfaces are included by each of the hyperfaces of one or more of the basic block(s) assigned in the basic space,

assigns each of the basic blocks to the corresponding basic space, and

generates the four-dimensional shape that corresponds to a part or all of the structure of the polymer

so that two adjacent basic tiles in the basic tile chain corresponds a part or all of shape obtained by projecting the divided-hyperfaces of one basic block or two consecutive basic blocks in the four-dimensional space into the three-dimensional space.

11. The shape processor as recited in claim 9, further comprising a generation unit operable to generate four-dimensional shape defined by designating whether each basic blocks assignable to each basic space surrounded by sixteen points of a lattice in a four-dimensional space is to be assigned to the corresponding basic space, so that a three-dimensional shape, which is defined by projecting it into a direction where three hyperfaces of the basic block consisting of the four-dimensional shape may be seen, imitates the chain of basic tiles, wherein

each of the hyperfaces of the basic block is divided into six divided hyperfaces by a division surface, which is a surface including either of a reference vertex which is a vertex shared by the four hyperfaces of the basic block projected into the projection direction, a vertex located opposite from the reference vertex on the hyperfaces, or another vertex on the hyperface,

the generation unit executes:

a first step of choosing one of the divided-hyperfaces of a basic block as the initial reference divided-hyperface and one of the two faces of the initial reference divided-hyperface that are faces of the corresponding basic block as the reference face;

a second step of choosing one of the two divided-hyperfaces which share the reference face with the reference divided-hyperface and whose image by the projection into the predetermined plane do not overlap with the image of the reference divided-hyperface by the same projection, wherein the generation unit chooses the divided-hyperface in such a way that the projection of the chosen divided-hyperface imitates a part or all of the structure of the polymer;

a third step of choosing the divided-hyperface chosen in the second step as the new reference divided-hyperface; and

a fourth step of choosing the other face of the new reference divided-hyperface that is not the division line as the new reference face,

a chain of the divided-hyperfaces that were chosen as reference divided-hyperfaces during the execution is obtained by executing the steps from the second step to the fourth step repeatedly,

the three-dimensional shape obtained by the projection of the chain into the predetermined plane imitates a part or all of the structure of the polymer, and

the generation unit generates a four-dimensional shape by assigning basic blocks that contains one of the divided-hyperfaces of the chain to their corresponding basic space.

12. The shape processor as recited in claim 10, wherein

the generation unit chooses a set of points of the lattice to generate a four-dimensional shape by assigning basic blocks to all of the basic spaces which correspond to four-dimensional version of square pyramids defined by the chosen points of the lattice, and

the generation unit further comprises an administration unit operable to keep the generated shape as a set of points.

13. The shape processor as recited in claim 11, wherein the generation unit encodes the structure of a polymer by assigning a value 0 or 1 to each divided-faces of the chain when one choose them in the second step.

14. The shape processing system as recited in claim 9, wherein

the basic tile comprises four vertices:

A, B, C and D,

the approximation unit generates a chain of basic tiles which imitates a part or all of the structure of the polymer by connecting a basic tile from the initial tile with a following tile sequentially such that

three vertices C, D and B of the basic tile are coincide with vertices A, B and C of the following basic tile respectively, or

three vertices C, D and A of the basic tile are coincide with vertices A, Band D of the following basic tile respectively.

15. The shape processor as recited in claim 14, wherein the generation unit encodes a part or all of the structure of a polymer by assigning a value 0 or 1 each basic tile of the chain which imitates the structure, where the assigned value denotes the way the basic tile is connected with the following basic tile.

16. The shape processor as recited in claim 9, wherein the polymer comprises a protein, and the generation unit imitates the structure of a chain of amino-acids which is a part or all of the protein, where one amino-acid corresponds to three consecutive basic tiles.

17. The shape processor as recited in claim 9, wherein the polymer comprises a DNA molecule, and the generation unit imitates the structure of a chain of nucleotides which is a part or all of the DNA molecule, where one nucleotides corresponds to one basic tile.

18. A method for representing the structure of a polymer in a three-dimensional space, wherein

the structure includes a predetermined set of basic tiles of three-dimensional shapes, each of which is associated with four vertices A, B, C and D which form a tetrahedron, a part or all of the structure of the polymer is imitated by a chain of basic tiles which is generated by connecting a basic tile from an initial tile with a following tile by face sequentially such that

three vertices C, D and B of a basic tile are coincide with vertices A, B and C of the following basic tile respectively, or

three vertices C, D and A of a basic tile are coincide with vertices A, B and D of the following basic tile respectively.