Shape processor and method for representing shape

• US 7,477,249 B2
• Filed: 05/05/2004
• Issued: 01/13/2009
• Est. Priority Date: 11/06/2001
• Status: Expired due to Fees

• Current Assignee: Naoto Morikawa
• Original Assignee: Naoto Morikawa
• Inventors: Morikawa, Naoto
• Primary Examiner(s): Tung; Kee M
• Assistant Examiner(s): YANG, ANDREW GUS
• Application Number:
  US10/840,555
• Publication Number:
  US 20050007367A1
• Time in Patent Office: 1,714 Days
• Field of Search: None
• US Class Current: 345/419
• 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 that 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 each basic tile is chosen from a predetermined set of basic tiles generated by projecting an image of three faces of each convex hull of a lattice of convex hulls from a three-dimensional space onto the two-dimensional space, wherein each face is further divided by a division line that intersects with two vertices including a reference vertex of the convex hull that is shared by the three faces and a vertex of the face that is not connected to the reference vertex by an edge, such that the projected image of the faces are also divided; and

a generation unit operable to generate a three-dimensional shape by specifying whether a set of one or more basic blocks is assigned to each convex hull of the lattice of convex hulls

and corresponds a part or all of a chain of divided faces obtained by projecting the assigned basic blocks with the chain of basic tiles.

2. The shape processor as recited in claim 1, wherein the generation unit chooses a set of points at the vertices of convex hulls of the lattice of convex hulls to generate a three-dimensional shape by assigning basic blocks to all of the convex hulls that correspond to triangular pyramids formed at the chosen points of the lattice by three faces of the convex hulls located at those vertices, and

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

3. A shape processor for imitating a shape of an object in a two-dimensional space, comprising a generation unit operable to generate a three-dimensional shape defined by designating whether basic blocks assignable to a convex hull surrounded by eight points of a lattice in a three-dimensional space is to be assigned to a corresponding space convex hull, so that a two-dimensional shape, which is defined by projecting three faces of the basic blocks constituting the three-dimensional shape onto a plane, imitates the shape of the object, wherein

each face of the basic blocks is divided into two divided faces by a division line connecting a reference vertex and a vertex positioned diagonally with respect to the reference vertex, wherein the reference vertex is a vertex of the basic block shared by the three faces of the basic block, such that each divided face comprises two edges that overlap two edges of the basic block and a division edge that overlaps with the division line,

the generation unit executes:

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

a second step of choosing one of the two divided-faces that share a reference edge with the reference divided-face and whose projected image does not overlap with the projected image of the reference divided-face, wherein the generation unit chooses the divided-face in such a way that the projected image 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 a new reference divided-face; and

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

and repeating the second, third, and fourth steps until a chain of divided-faces that were chosen as reference divided-faces is obtained,

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

a final step of generating a three-dimensional shape by assigning basic blocks that contain one of the divided-faces of the chain of divided-faces to corresponding convex hulls.

4. The shape processor as recited in claim 3, wherein the generation unit encodes the generated shape by assigning a value of 0 or 1 to each divided-faces of the chain of divided-faces according to the choices made 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 that imitates the shape of the object by connecting a basic tile with a following tile by a face one by one from an initial tile, wherein each basic tile is chosen from a predetermined set of basic tiles generated by projecting an image of four hyperfaces of each convex hull of a lattice of convex hulls from a four-dimensional space onto the three-dimensional space, wherein each hyperface is further divided by a division plane that intersects with three vertices including a reference vertex of the convex hull that is shared by the four hyperfaces, a vertex positioned opposite from the reference vertex on the hyperface, and another vertex on the hyperface; and

a generation unit operable to generate a four-dimensional shape by specifying whether a set of one or more basic blocks is assigned to each convex hull of the lattice of convex hulls

and corresponds a part or all of a chain of divided hyperfaces obtained by projecting the assigned basic blocks with the chain of basic tiles.

6. The shape processor as recited in claim 5, wherein the generation unit chooses a set of points at the vertices of convex hulls of the lattice of convex hulls to generate a four-dimensional shape by assigning basic blocks to all of the convex hulls that correspond to pyramids formed at the chosen points of the lattice by four hyperfaces of the convex hulls located at those vertices, and

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

7. A shape processor for imitating a shape of an object in a three-dimensional space, comprising a generation unit operable to generate a four-dimensional shape defined by designating whether basic blocks assignable to a convex hull surrounded by sixteen points of a lattice in a four-dimensional space is to be assigned to a corresponding convex hull, so that a three-dimensional shape, which is defined by projecting four hyperfaces of the basic blocks constituting the four-dimensional shape onto a three-dimensional space, imitates the shape of the object, wherein

each hyperface of the basic blocks is divided into six divided hyperfaces by a division plane, which is a plane that intersects with three vertices including a reference vertex that 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, and another vertex on the hyperface,

the generation unit executes:

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

a second step of choosing one of the two divided-hyperfaces that share a reference face with the reference divided-hyperface and whose projected image does not overlap with the image of the reference divided-hyperface, wherein the generation unit chooses the divided-hyperface in such a way that the projected image 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 a new reference divided-hyperface; and

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

and repeating the second, third, and fourth steps until a chain of divided-hyperfaces that were chosen as reference divided-hyperfaces is obtained,

and the three-dimensional shape obtained by projecting the chain of divided hyperfaces into the predetermined three-dimensional space imitates the shape of the object, and

a final step of generating a four-dimensional shape by assigning basic blocks that contains one of the divided-hyperfaces of the chain of divided hyperfaces to corresponding convex hulls.

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

9. A shape processor for imitating a structure of a polymer in a three-dimensional space, comprising an approximation unit operable to generate a chain of basic tiles to imitate a part or all of a structure of a polymer, wherein each 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 a following tile by a face one by one from a initial tile;

and

each basic tile is chosen from a predetermined set of basic tiles generated by projecting an image of four hyperfaces of each convex hull of a lattice of convex hulls from a four-dimensional space onto the three-dimensional space, wherein each hyperface is further divided by a division plane that intersects with three vertices including a reference vertex of the convex hull that is shared by the four hyperfaces, a vertex positioned opposite from the reference vertex on the hyperface, and another vertex on the hyperface.

10. The shape processor as recited in claim 9, further comprising a generation unit operable to generate a four-dimensional shape defined by assigning one or more basic blocks to a corresponding basic space, wherein each basic space is a convex hull of sixteen points of a lattice in a four-dimensional space,

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

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

the generation unit

corresponds a part or all of a chain of divided hyperfaces obtained by projecting the assigned basic blocks with the chain of basic tiles,

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 basic blocks in the four-dimensional space into the three-dimensional space.

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

12. 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 the four-dimensional shape into a direction where four 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.

13. The shape processor as recited in claim 12, 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 processor 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 the following tile sequentially such that either

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, B and 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 to 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 a structure of a polymer in a three-dimensional space with a chain of basic tiles, wherein

the basic tiles include a predetermined set 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;

and

each basic tile is chosen from a predetermined set of basic tiles generated by projecting an image of four hyperfaces of each convex hull of a lattice of convex hulls from a four-dimensional space onto the three-dimensional space, wherein each hyperface is further divided by a division plane that intersects with three vertices including a reference vertex of the convex hull that is shared by the four hyperfaces, a vertex positioned opposite from the reference vertex on the hyperface, and another vertex on the hyperface;

such that either

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.