Method for constructing three-dimensional polyhedron model

• US 4,775,946 A
• Filed: 03/28/1986
• Issued: 10/04/1988
• Est. Priority Date: 03/29/1985
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Anjyo, Kenichi
• Primary Examiner(s): Hackcom, Gary V.
• Assistant Examiner(s): HERNDON, HEATHER R
• Application Number:
  US06/845,198
• Time in Patent Office: 921 Days
• Field of Search: 364/518-522, 340/720, 340/723, 340/727, 340/729, 340/747, 382/44-46
• US Class Current: 345/419
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

In order to achieve an interpolation display of a display object existing between two adjacent planes according to the triangulation when digital data on the two adjacent planes is given, the data items on the two planes are grouped into a plurality of connected components, respectively, and several connected components on the first plane are projected onto the connected components on the second plane. Thereafter, a sequence of points enclosing each one of the projected components are selected, and the selected point sequence is corresponded to a sequence of boundary points which enclose one of the connected components which contains the subcomponent whose projected image onto the connected components on the second plane is equal to the projected component. Then, by using every corresponding pairs of the sequences, the triangular faces are generated.

Claims

1. A method for displaying a three-dimensional object on a display unit based on binary data representing cross sections along a plurality of parallel planes passing through the object wherein triangulation is effected between sequences of outer-most boundary points of overlapped components associated with a pair of data of adjacent planes selected from the parallel planes and the triangulation is sequentially effected on all pairs of data of adjacent planes to configure a three-dimensional model of the object, thereby displaying an approximated surface contour of the object, said method comprising the following steps of:

(a) for two adjacent planes, obtaining overlapped components on the respective planes by use of data on said two planes;

(b) projecting the overlapped components of a first plane of the adjacent planes onto a second plane thereof and labeling intersections between the projected components and the overlapped components on the second plane;

(c) obtaining extended components each containing one each of the intersections labeled on the second plane, said components having no intersection therebetween and a union of said components being consistent with an overlapped component including the intersections on the second plane;

(d) effecting triangulation by assuming as verteces sequences of outer-most boundary points of the components on the first plane and the extended components of the extended components having a same label on the second plane, respectively; and

(e) sequentially effecting the triangulation on said plurality of parallel planes so as to approximate a surface contour of the three-dimensional object.

2. A method for displaying a three-dimensional object on a display unit based on binary data representing cross sections along a plurality of parallel planes passing through the object wherein triangulation is effected between sequences of outer-most boundary points of overlapped components associated with a pair of data of adjacent planes selected from the parallel planes and the triangulation is sequentially effected on all pairs of data of adjacent planes to configure a three-dimensional model of the object, thereby displaying an approximated surface contour of the object, said method comprising the following steps of:

(a) for two adjacent planes, obtaining overlapped components on the respective planes by use of data on said two planes;

(b) projecting the overlapped components of a first plane of the adjacent planes onto a second plane thereof and labeling intersections between the projected components and the overlapped components on the second plane;

(c) obtaining extended components each containing one each of the intersections labeled on the second plane, said components having no intersection therebetween and a union of said components being consistent with an overlapped component including the intersections on the second plane;

(d) projecting the overlapped components on the second plane onto the first plane and labeling intersections between the projected components and the overlapped components on the first plane;

(e) obtaining extended components each containing one each of the intersections labeled on the first plane, said components having no intersection therebetween and a union of said components being consistent with an overlapped component including the intersections in the first plane;

(f) effecting triangulation by assuming as verteces sequences of outer-most boundary points of the extended components on the first plane and the second plane, respectively, the first and second planes each including a same label; and

(g) sequentially effecting the triangulation on said plurality of parallel planes so as to approximate a surface contour of the three-dimensional object.

3. A method according to claim 2 further comprising the steps of:

(a) determining the presence or absence of a hole for each said overlapped component on the adjacent planes based on the data associated therewith;

(b) projecting the overlapped components obtained from the first plane onto the second plane;

(c) projecting onto the data on the second plane as an overlapped component each determined to have a hole based on the data on the first plane, said overlapped components being summed with a sequence of inner boundary points, and labeling intersections between the projected component and the overlapped and summed components on the second plane;

(d) projecting onto the data on the first plane as an overlapped component each determined to have a hole based on the data on the second plane, said overlapped components being summed with a sequence of inner boundary points, and labeling intersections between the projected component and the overlapped and summed components on the first plane; and

(e) effecting triangulation by assuming as verteces sequences of outer-most boundary points of the extended components on the first plane and the second plane, respectively, the first and second planes each including a same label; and

if said extended components include sequences of inner boundary points, effecting the triangulation between the sequences of inner boundary points.

4. A three-dimensional digital image display method in a system including a computer accompanied by a file storing digital data of a three-dimensional object to be displayed and a graphic display unit displaying a result obtained by reconfiguring a shape of the object by the computer based on the data, in which a fundamental step includes an operation based on the data on two parallel adjacent planes in a display space for displaying a surface portion of the object between the two planes by use of triangle patches, and an entire surface of the object is reconfigured by triangle patches by repeating the fundamental step in the computer, wherein said fundamental step comprising the following steps of:

assuming one of the two planes as a first plane;

defining two arbitrary points in a component configured by the data on the first plane to belong to a same connected component only when the two points can be linked to each other with a line having nodal points in the component and one of two adjacent nodes of the line is in the vicinity of the other point thereof;

representing the component as a union of the connected components having no intersection therebetween, assuming the other plane of the two planes as a second plane, and representing a component configured by the data on the second plane as a union of connected components having no intersection therebetween;

projecting the connected components on the first plane onto each connected component on the second plane so as to obtain projected smaller components;

obtaining boundary point sequences of points in the connected components on the second plane, said sequences each including one each of the projected smaller components;

establishing a one-to-one correspondence between one of the boundary point sequences and a sequence of boundary points of the connected components on the first plane, the projected thereof result onto the connected components on the second plane being the projected smaller component enclosed with the boundary point sequence; and

creating and displaying triangle faces by sequentially connecting each point of the boundary point sequence on the first plane and each point of the boundary point sequence on the second plane.

5. A method according to claim 4 comprising the following steps of

for each said projected smaller component projected onto the connected components configured with the data on the second plane, obtaining subcomponents of the connected components each including one each of the projected smaller components and having no intersection therebetween, a union of said subcomponents being consistent with the connected components;

establishing a one-to-one correspondence between a sequence of boundary points of the subcomponents and a sequence of boundary points including boundary points of the connected components and enclosing the connected components, the projected result thereof onto the connected components being the proected smaller component enclosed with the boundary point sequence; and

generating triangle faces by sequentially connecting the points of the boundary sequences on the first and second planes, respectively.

6. A method according to claim 4 further including the steps of:

for each projected smaller component projected onto the connected components configured with the data on the second plane, defining an extended projected smaller component as the projected smaller component;

defining as points of the extended projected smaller component points selected from the vicinity of each boundary point of the extended porjected smaller component, said selected points of the connected components not belonging to any extended projected smaller component;

growing the extended projected smaller component by repeating the foregoing operation until a union of the extended projected smaller component becomes consistent with the total of the connected components;

for each extended projected smaller component, obtaining a sequence of boundary points including boundary points of the extended projected smaller component and enclosing the extended projected smaller component;

establishing a one-to-one correspondence between one of the boundary point sequences and a sequence of boundary points including boundary points of the connected components on the first plane and including the connected components, the projected result thereof onto the connected components being the projected smaller component enclosed with the boundary point sequence; and

producing triangle faces by sequentially connecting the boundary point sequences of the first and second planes, respectively.

7. A method according to claim 4 further comprising the following steps of:

obtaining sequences of boundary points in the connected components on the second plane, said components including one each of the projected smaller components on the second plane;

for one of the boundary point sequences, establishing a one-to-one correspondence between the boundary point sequence and a sequence of boundary points including nodes of an outermost loop selected from the loops; and

generating triangle faces by sequentially connecting the boundary point sequences on the first and second planes respectively.

8. A method according to claim 4 further comprising the following steps of:

obtaining subcomponents of said connected components including one each of the projected smaller components projected onto the connected components configured with the data on the second plane and having no interface therebetween, a union thereof being consistent with the connected components;

establishing a one-to-one correspondence between a sequence of boundary points including nodes of an outermost loop of the loops and a sequence of boundary points of the connected components on the first plain, the projected result thereof onto the connected components being the projected smaller component enclosed with the boundary point sequence; and

generating triangle faces by connecting the points of the boundary point sequences of the first and second planes, respectively.

9. A three-dimensional object polyhedron model display method in a system in which a polyhedron model of a three-dimensional object is configured by a computer based on a two-dimensional digital image data supplied thereto, said data associated with a plurality of parallel cross sections of the object for displaying by the polyhedron model a surface contour of the object between two adjacent cross sections selected from the cross sections, said method comprising the following steps of;

determining one of the two adjacent cross sections associated with the digital image data and the other thereof as a first cross section and a second cross section, respectively;

representing the two cross sections by unions of connected components, respectively;

for each of the connected components of said representing step, obtaining all outer boundary point sequences enclosing the connected component and all inner boundary point sequences enclosing holes in the connected component;

determining as a third cross section common portions between the first and second cross sections;

obtaining subsets of connected components of the first cross section having no common portion therebetween, one of the subsets including an arbitrary connected component of a union of the third cross section and all inner boundary point sequences of the first cross sections and the whole first cross section being consistent with a union of the subsets;

treating each said subset as a portion component of the first cross section with respect to the third cross section;

obtaining subsets of connected components of the second cross section having no common portion therebetween, one of the subsets including an arbitrary connected component of a union of the third cross section and all inner boundary point sequences of the second cross section and the whole second cross section being consistent with a union of the subsets;

treating each of said subset as a partition component of the second cross section with respect to the third cross section;

obtaining all connected components of the third cross section;

for each said connected component, configuring faces of a polyhedron from an outer boundary point sequence of the partition component of the first cross section including the connected component and from an outer boundary point sequence of the partition component of the second cross section including the connected component;

determining as a new first cross section a component of which an outer boundary point sequence comprises an inner boundary point sequence of the first cross section in the partition component thereof;

determining as a new second cross section a component of which an outer boundary point sequence comprises an inner boundary point sequence of the second cross section in the partition component thereof;

determining as a new third cross section an intersection of the new first cross section and the new second cross section;

obtaining a partition component of the new first cross section with respect to the new third cross section and a partition component of the new second cross section with respect to the new third cross section;

determining partition components of the new first and second cross sections, said components including the connected components consistent with the connected components of the new third cross section; and

configuring faces of a polyhedron based on the outer boundary point sequence of the partition component of the new first cross section and the outer boundary point sequence of the partition component of the new second cross section, thereby displaying the object based on the polyhedron model.

10. A method according to claim 9 further including the following steps of:

for obtaining a partition component of the first cross section with respect to the third cross section for each connected component of a set including the third cross section and all inner boundary points of the first cross section, determining the connected components as the partition component;

determining, among eight points in the vicinity of each boundary point of the partition component, points of the first cross section not included in any one of the other partition components as points of the partition component;

sequentially growing the partition component by repeatedly achieving the foregoing operation for all partition components until a union of the partition components becomes consistent with the first cross section;

determining each said partition component as a partition component of the first cross section with respect to the third cross section;

for obtaining a partition component of the second cross section with respect to the third cross section for each connected component of a set comprising the third cross section and all inner boundary points of the second cross section, determining the connected components as the partition component;

determining, among four or eight points in the vicinity of each boundary point of the partition boundary, points of the second cross section not included in any one of the other partition components as points of the partition component;

sequentially growing the partition component by repeatedly achieving the foregoing operation for all partition components until a union of the partition components becomes consistent with the second cross section;

treating each said partition component as a partition component of the second cross section with respect to the third cross section;

for obtaining a partition component of the new first cross section with respect to the third cross section, treating, for each connected component of the new third cross section, the connected component as the partition component;

determining, among eight points in the vicinity of each boundary point of the partition boundary, points of the new first cross section not included in any other partition components as points of the partition component;

sequentially growing the partition component by repeatedly achieving the foregoing operation for all partition components until a union of the partition components becomes consistent with the new first cross section;

treating each said partition component as a partition component of the new first cross section with respect to the new third cross section;

for obtaining a partition component of the new second cross section with respect to the new third cross section, treating, for each said connected component of the new third cross section, the connected component as a partition component;

determining, among eight points in the vicinity of each boundary point of the partition component, points of the new second cross section not included in any other partition components as points of the partition component;

sequentially growing the partition component by repeatedly achieving the foregoing operation for all partition components until a union of the partition components becomes consistent with the new second cross section; and

treating each said partition component as a partition component of the new second cross section with respect to the new third cross section.