Geometric Modelling System

The present invention relates to a geometric modeling system which constitutes a base for the construction of various automatic systems which automatically perform various works necessary in the design and production of goods with the aid of computers, such as systems known as CAE, CAD and CAM. More particularly, the invention is concerned with a geometric modeling system which is suitable for use in interactive operations.

In generating a three-dimensional form from two-dimensional wire frame patterns or figures which are typically produced by a drafting system, it is necessary that a three-dimensional surface be stored in a computer in such a mathematically complete form that the relationships of points, lines and surfaces are represented by a solid model in terms of boundary expression. To this end, it has been a common practice to employ a process which has the steps of cutting the wire frame which represents the boundary of the actual object out of the two-dimensional wire frame in accordance with the form of the object through an interactive method, appointing the cut wire frames sequentially so as to take up the surfaces or the boundaries of the surfaces which constitute the three-dimensional object, and synthesizing them so as to complete the three-dimensional form. This method is disclosed, for example, in pp 23-28, "COMPUTERS IN ENGINEERING 1982 Vol. 1" which was released in the Second International Computer Engineering Conference which was held in August, 1982.

The conventional graphic system, however, is not convenient for the users in that it requires a large number of command inputs in the interactive processing, as well as laborious inputting operations.

Another problem is that the two-dimensional wire frame pattern formed by the drafting system sometimes irregularly or incompletely indicate the states of intersection between the constituent lines such as straight lines and arcuate lines, so that the user cannot correctly recognize the states of intersection of the lines from the pattern on display. Therefore, the user must define again the data concerning such irregular and incomplete wire frame patterns, thereby to obtain regular and complete presentation, following laborious inputting steps.

It is to be pointed out also that the work for appointing the wire frames which represent the boundaries in the actual object and the work for visually recognizing the three-dimensional structure from the design drawings are not always conducted in concert with each other, with the result that the performance of the man-machine interface for inputting modeling commands is impeded seriously.

Accordingly, an object of the invention is to provide a geometric modeling system for generating a three-dimensional form from two-dimensional wire frame patterns, which system being improved in such a manner as to remarkably simplify the inputting process and to ensure a higher performance of the man-machine system, thus enabling easy operation by the users.

According to the invention, this object is achieved by a modeling system in which the user appoints internal points in a displayed two-dimensional wire frame patterns which represent surfaces as constituents of a three-dimensional object, whereby definite surfaces or boundaries of definite surfaces are automatically taken out with good matching, while checking the completeness of the double definition of the constituent line elements and the state of intersection and satisfying the geometrical relationship.

The above-mentioned object is achieved also by a method in which definite surfaces or the boundaries of the definite surfaces are automatically taken-out and a specific patterns with surface are appointed by the user.

The operation of the modeling system in accordance with the invention is as follows. As the user appoints the internal points in the two-dimensional wire frame patterns, an operation unit generates data concerning definite surfaces or boundaries of a definite surface, in accordance with the coordinate values appointed by the user and two-dimensional wire frame pattern data extracted from a data base. The operation unit then performs a three-dimensional process by using the thus obtained data concerning the definite surface or the boundaries of the definite surface. Alternatively, the definite surfaces or the boundaries of the definite surfaces are automatically taken out.

FIG. 1 is a block diagram showing constituent elements of an embodiment of the invention, as well as the flow of the process for generating a three-dimensional form;

FIG. 2 is a detailed illustration of a three-dimensional surface generating processing section whose processing arrangement is common to the form processing sections shown in FIG. 1;

FIG. 3 is an illustration of the process on a CRT display for the formation of the data in the processing section shown in FIG. 2;

FIG. 4A is an illustration of a process on a CRT display for the generation of a three-dimensional form from a sectional view;

FIG. 4B is an illustration of a process on a CRT display for generation of a three-dimensional form from a developed view;

FIG. 5A is an illustration of the process on a CRT display for surface definition (three-dimensional processing) step 3 in FIG. 3, which process is taken when a plurality of internal points P are appointed;

FIG. 5B is an illustration of a process on a CRT display for surface definition (three-dimensional processing) step 3 in FIG. 3, which process is taken when there are a plurality of wire frames e representing one and the same three-dimensional object;

FIG. 6A is an illustration of a process on a CRT display for the formation of a parallel sweeper for a closed solid body with curved surface;

FIG. 6B is an illustration of a process on a CRT display for the generation of a rotary sweeper of a closed solid body with curved surface;

FIGS. 6C to 6E are illustrations of examples of specific pattern;

FIGS. 7A to 7D are illustrations of a surface pick-up algorithm;

FIGS. 8A to 8F are illustrations of a practical model on a CRT display, explaining the surface pick-up algorithm;

FIGS. 9 to 12 are illustrations of a process in which a tree structure of the data for loop retrieval is formed on the basis of a wire frame having a direction D in any desired two-dimensional wire frame;

FIGS. 13A, 13B, 14A and 14B re illustrations of the manner in which, when a wire frame is divided, the "parent" wire frame is substituted, in the process for forming the tree structure in the loop retrieval;

FIG. 15 is an illustration of a process in which a loop retrieval is conducted for a two-dimensional wire frame as an object, from a given starting line;

FIGS. 16, 17A, 17B, 18A, 18B, 19A, 19B, 20A, 20B, 21A, 21B, 22A, 22B, 23A, 23B, 24A, 24B, 25A, 25B, 26A, 26B, 27A, 27B, 28A and 28B are graphical representation of the states of retrieval of the groups of two-dimensional wire frames in respective steps, as well as the tree structures obtained in respective steps;

FIGS. 29A and 29B are illustrations of conditions for the judgement as to whether the loop structure is for the outer loop retrieval;

FIGS. 30A, 30B, 31A and 31B are illustrations of conditions for judgement as to whether the loop structure is for the inner loop retrieval;

FIGS. 32A, 32B, 33A, 33B, 34A and 34B are illustrations of a process for the separation and synthesis of edge lines obtained through a loop retrieval; and

FIG. 35 is a Table showing the data structures used in the loop retrieval.

A preferred embodiment of the invention will be described hereinafter with reference to the accompanying drawings.

A. Explanation of Whole System

As shown in FIG. 1, an interactive geometric modeling system embodying the present invention has the following parts: a graphic display 6; an input device 8 such as a combination of a tablet and a stylus or, alternatively, a keyboard, for inputting commands and parameters; an operation unit 5 which performs arithmetic operations in response to the input commands and parameters so as to generate two-dimensional wire frame pattern data in a two-dimensional wire frame defining section 13; and a data base 2 in which the thus-generated pattern data is stored.

The user operates the operation unit 5 through the input device 8 in accordance with the two-dimensional wire-frame pattern data extracted from the data base 2, so that two-dimensional or three-dimensional forms are generated in various sections including a two-dimensional surface/wire frame model generating processing section 9, three-dimensional wire frame model generating processing section 10, three-dimensional surface model generating processing section 11, and a closed curved-surface solid model generating processing section 12. The three-dimensional form data and the two-dimensional form data thus obtained are inputted to a data base 3 and a data base 4, respectively.

B. Method of Forming Three-Dimensional Surface Model

The details of the three-dimensional surface generating processing section, which has the processing arrangement commonly adopted by various form processing sections shown in FIG. 1, will be explained hereinunder with specific reference to FIG. 2.

B1. Outline of Surface Model Generating Process

As will be seen from FIG. 2, the three-dimensional surface model generating process is constituted by the following commands and processing steps.

At Step 21, the user inputs a command for calling two-dimensional wire frames, as well as parameters thereof. In response to the input, the operation unit 5 calls, from the data base 2 (see FIG. 1), the data concerning the two-dimensional wire frame pattern generated and defined by, for example, a drafting system, and displays the thus called data on the display 6, as shown in frame 1 in FIG. 3. At Step 22, the user inputs commands and parameters for the division of the pattern and the definition of the coordinate systems. In response to this input, the operation unit 5 divides the displayed two-dimensional wire frame pattern into views such as a projection, a sectional view and a developed view, and defines these views as independent patterns, as shown in frame 2 in FIG. 3. Furthermore, the operation unit 5 defines the coordinate system for these independent patterns, the coordinate system determining the positional relationship between these independent patterns in a three-dimensional space.

For generating a three-dimensional form from the two-dimensional wire frame patterns, the user inputs at Step 23 a definite surface pick-up processing command, so as to appoint a point on the display representing the two-dimensional wire frame pattern or to appoint a pattern with an automatically-formed surface, the operation unit picks up a definite surface such as a projection surface, sectional surface, developing surface or the like at a Step 231 and, in a three-dimensional processing step (Step 232), a three-dimensional surface is formed from the thus picked-up definite surface, in accordance with a later-mentioned three-dimensional processing method, as shown in frame 3 in FIG. 3. The formation of the three-dimensional surface is conducted in such a way that the three-dimensional surface is combined with an already-generated three-dimensional wire frame, surface or a solid body, so as to obtain a matching necessary for a model. A step 27 is followed when it is desired to correct a generated three-dimensional surface on a developed pattern. The developed pattern has been obtained through developing a previously formed three-dimensional surface by the operation unit in accordance with the developed pattern defining command and parameter, and correcting the two-dimensional wire frame pattern having the thus obtained coordinate system.

For the purpose of generating a three-dimensional form from previously formed three-dimensional surfaces, points and lines constituting such a three-dimensional form are appointed at Step 26, so that a three-dimensional surfaces such as of fillets are formed, as shown in frame 6 in FIG. 3.

Then, Steps 23 to 27 are repeatedly executed until all the surfaces which constitute the desired three-dimensional model are formed.

When a model conversion is necessary, the closed surfaces are converted at Step 29 into a solid body, as shown in the frame 9 in FIG. 3. Conversely, a previously-formed solid body can be converted into a surface model provided that the conversion is carried out on the unit of surface.

The form data obtained through the above-mentioned process is registered in the three-dimensional form data base 3 at Step 30 for the form registration.

B2. Example of Interactive Processing

The process explained above in connection with FIG. 2 will be described in more detail using a practical form model, with specific reference to FIG. 3 which illustrates the process on a display on a CRT.

Referring to FIG. 3, the wire frame display in the frame 1 represents a group a of wire frames called at Step 21 shown in FIG. 2. A frame 2 shows a step for dividing the wire frames into patterns a.sub.1 and a.sub.2 and defining coordinate systems b for respective patterns. A frame 3 shows a surface definition process (three-dimensional processing). In this process, as an internal point P in the pattern a.sub.2 or a specific pattern with an automatically-formed surface is appointed at Step 231 of the process shown in FIG. 2, a two-dimensional projection surface f.sub.1 is formed. A wire frame e.sub.1 of the pattern a.sub.1 of the same three-dimensional object is also appointed at Step 232 of FIG. 2, a three-dimensional surface f is formed.

In a frame 6, there is shown a surface defining process (three-dimensional surface stretching process) in which a three-dimensional surface f.sub.3 is formed as lines e.sub.2 and e.sub.3 constituting a previously-formed three-dimensional surface f.sub.2 are appointed at Step 26 in FIG. 2. The boundaries of the three-dimensional surface are generated by effecting a development into a two-dimensional space on the basis of the input interpolation surface form, forming two-dimensional boundaries through a linear interpolation, and reforming the two-dimensional boundaries into three-dimensional space.

In frame 9, there is shown a surface-solid body conversion process in which a group f.sub.4 of previously-formed closed surfaces is formed into a solid body in conformity with the direction c of the space representing the solid body, in accordance with Step 29 in the process shown in FIG. 2. FIGS. 6C to 6E show, respectively, the cases where the specific pattern with automatically-formed surface is constituted by a surface ID, surface boundaries and the shading inside the surface.

B3. Three-Dimensional Processing of Definite Surface

An explanation will be given hereinafter as to the method for three-dimensional presentation of a definite surface, with reference to FIGS. 4A to 5B. Explanation of the projection pattern is omitted because it has been described already in connection with the frame 3 illustrating the surface definition process (three-dimensional processing).

Referring to FIG. 4, for the purpose of making a three-dimensional presentation of a sectional view, a two-dimensional section f.sub.1 is formed, as an internal point P in a pattern a.sub.2 or a specific pattern with an automatically-formed surface (referred to as "specific pattern" hereinafter) is appointed at Step 23 of the process shown in FIG. 2. Then, at Step 232 of the process shown in FIG. 2, a point e.sub.1 in the pattern a.sub.1 of the same three-dimensional object and a point e.sub.2 representing the same direction are appointed, thereby enabling the formation of the three-dimensional surface f.

On the other hand, a three-dimensional presentation of the developed pattern is conducted by appointing in Step 231 of the process shown in FIG. 2 an internal point P in a pattern a.sub.3 or a specific pattern thereby forming a developed surface f.sub.2 and then generating a three-dimensional surface f.sub.3 in Step 232 of FIG. 2.

When a circumstance allows appointment of a plurality of points, internal points P.sub.1 to P.sub.n of the pattern a.sub.2 or a specific pattern are appointed in Step 231 of FIG. 2 so as to form two-dimensional projection surfaces f.sub.1 to f.sub.n and, thereafter, the wire frame e.sub.1 of the pattern a.sub.1 of the same three-dimensional object is appointed in Step 232 of the process shown in FIG. 2, whereby a three-dimensional surface f is formed, as in the case of the example shown in FIG. 5A.

An explanation will be given hereinafter as to the case where a plurality of three-dimensional surfaces are formed, with reference to FIG. 5B. As an internal point P in the pattern a.sub.3 or a specific pattern is appointed in Step 231 of the process shown in FIG. 2, a two-dimensional projection surface f.sub.2 is formed and, thereafter, a plurality of three-dimensional surfaces F.sub.1 to F.sub.m are formed as the wire frames e.sub.1 to e.sub.m of the pattern a.sub.4 of the same three-dimensional object are appointed. It is also possible to appoint a plurality of wire frames e.sub.1 to e.sub.m of the same three-dimensional object, by appointing a plurality of internal points P.sub.1 to P.sub.n or a specific pattern.

Although the method of three-dimensional presentation of a projection pattern has been described with reference to FIGS. 5A to 5B, the same method applies also to the formation of a three-dimensional form from a sectional pattern or a developed pattern. It is not always necessary that the internal points P.sub.1 to P.sub.n shown in FIG. 5A are of the same pattern. Similarly, it is not always necessary that the wire frames e.sub.1 to e.sub.m shown in FIG. 5B are of the same pattern.

From the foregoing description, it will be understood how the three-dimensional model generating pattern is generated.

C. Method of Generating Two-Dimensional Surface Model and Solid Model

The two-dimensional surface-wire frame model generating processing section 9 and the closed curved-surface solid model generating processing section 12, which are shown in FIG. 1, have an arrangement substantially the same as that for the three-dimensional surface model generating processing explained above. Portions of respective processings, which are critical to the present invention, will be explained hereinunder.

In the two-dimensional surface-wire frame model generating processing section 9, the data formed in the definite surface pick-up step 231 shown in FIG. 2 is directly inputted to the two-dimensional form data base 4 as shown in FIG. 1.

On the other hand, at the curved-surface solid model generating processing step, the two-dimensional surface f.sub.1 is picked-up as the internal point P in the pattern a.sub.1 or a specific pattern is appointed as shown in FIG. 6A. Then, the amount c.sub.1 of translational movement is input, while the point e.sub.1 of the pattern a.sub.2 of the same three-dimensional object and a point e.sub.2 representing the direction are appointed, whereby a parallel sweeper s.sub.1 is generated. At the same time, an internal point P in the pattern a.sub.1 or a specific pattern is appointed to enable the pick-up of the two-dimensional surface f.sub.1 as shown in FIG. 6B. Then, the coordinate axis e.sub.1 of the pattern a.sub.1 is appointed, and the amount c.sub.1 of rotation about the axis e.sub.1 is inputted, followed by appointment of a point e.sub.2 in the pattern a.sub.2 and the point e.sub.3 representing the direction, whereby a rotary sweeper s.sub.1 can be obtained. The sweepers thus obtained are processed for the purpose of integration with a previously-formed closed curved-surface solid body, whereby the desired closed curved-surface solid body is formed.

As will be understood from the foregoing description, according to this embodiment of the invention, it is possible to pick-up the definite surface for the formation of a three-dimensional body or the boundaries of such definite surfaces, simply by appointing one point or a specific pattern in a two-dimensional wire frame pattern on display. This in turn enables a remarkable reduction in the number of commands to be input by the user. In addition, the direct appointment of surfaces representing the actual form can be kept up with the process of recognition of the three-dimensional surfaces by the user on the design drawings. The direct appointment also enables the user to work out a three-dimensional pattern through the same inputting operation, regardless of whether it is formed from a projection, sectional view or a developed view. This means that the performance of the man-machine interface has been improved significantly.

D. Method of Forming Definite Surface

D1. Basic Forming Method

The algorithm for the generation of a three-dimensional form on the basis of the appointment of an internal point conducted in the definite surface pick-up processing step 231 shown in FIG. 2 will be explained hereafter with reference to FIGS. 7A and 7B, as well as to FIGS. 8A to 8F which illustrate the CRT displays of a model having a practical form.

First of all, an explanation will be given as to a method for retrieval of an outer loop which constitutes the minimal region containing an appointed point.

The operation executed in Step 41 in FIG. 7A is as follows. Referring to FIG. 8A, points of intersection or contact between a half-line (starting at an appointed point P.sub.o and a group of wire frames W.sub.1 -W.sub.no are represented by c.sub.1 -c.sub.n1, and a plurality of lines starting at the appointed point P.sub.o and terminating at the points c.sub.1 -c.sub.n1 are drawn, thus forming a group of candidate retrieval starting lines. These lines are arrayed according to the distance between the starting and terminating points, from the smallest one to the greatest one, as represented by l.sub.1 -l.sub.n1.

In Steps 42-46 shown in FIG. 7A, a retrieval operation is conducted to pick-up the outer loop ##EQU1## containing the appointed point P.sub.o and having the smallest length, in accordance with the order of the candidate retrieval starting lines arrayed as described above, as shown in FIG. 8B. The detail of the outer loop retrieval method will be explained later.

An explanation will be given hereinafter as to the method of retrieving a group of inner loops, i.e., loops contained by the outer loop. At Step 47 of the process shown in FIG. 7B, a group of wire frames contained by the outer loop are cut out at connecting or crossing points from a group of wire frames W.sub.1 to W.sub.no shown in FIG. 8A, and the thus cut wire frames are determined as a group of candidate edge lines i.sub.1 -i.sub.n3, as shown in FIG. 8C. As shown in FIG. 8D, the operation performed at Steps 48 and 49 shown in FIG. 7B is as follows. A half-line m is drawn starting from the end of any unretrieved candidate edge line i.sub.1 of the picked-up group of candidate edge lines i.sub.1 to i.sub.n3 shown in FIG. 8, the half-line m extending in parallel with and in the positive direction (upward direction in the figure) of y-axis of a two-dimensional coordinate system (frame coordinate system) having a horizontal x-axis and vertical y-axis which has the point of origin located at a left lower point on the CRT display. Then, a group of candidate inner loop retrieval start lines, which terminate at points q.sub.1 -q.sub.k1 of intersection or contact between the half line m extending to the infinite point P.sub.i in the positive direction (upward direction in the figure) and the candidate edge lines i.sub.1 to i.sub.n3 shown in FIG. 8C, and these candidate starting lines are arrayed according to the distance, from the smallest to the greatest, as represented by m.sub.1 -m.sub.k1. Then, inner loop retrieval is conducted using the candidate inner retrieval starting lines in the sequence of the array.

At Steps 50 to 53 of the process shown in FIG. 7B, the inner loop ##EQU2## is retrieved in accordance with the sequence of array of the candidate inner loop retrieval starting lines, as shown in FIG. 8E.

The detail of the inner loop retrieval will be explained later. When the loop has not been completed yet, the candidate edge lines retrieved at Step 52 is excluded from the next loop retrieval processing step 52 at Step 55 shown in FIG. 7B.

After completion of the inner loop, the edge lines constituting the completed loop and candidate edge lines contained by this loop are excluded from the next processing steps 48, 49 and 52, at Step 54 shown in FIG. 7B. The steps 48 to 55 explained above are followed until no unretrieved candidate edges is left, whereby an inner loop ##EQU3## is picked-up as shown in FIG. 8F.

Then, Step 56 shown in FIG. 7B is executed in which the outer loop and the inner loop obtained through the loop retrieval are subjected to separation and synthesis of the edge lines for the outer and inner loops through a method which will be detailed later, thus defining the loops again.

From the foregoing description, it will be understood how the three-dimensional form is generated through appointment of internal points.

The formation of the three-dimensional form through appointment of specific patterns with automatically-formed surface at the definite surface pick-up processing step 231 of the process shown in FIG. 2 is carried out in a manner which will be explained hereinunder. In this case, an inner loop retrieval method which will be explained later applies to the retrieval of the outer loop starting lines and the judgement of the loop construction, as shown in FIGS. 7C to 7D. In this case, the lines counter to the group of edge lines constituting the boundaries of the previously-formed surfaces are used as the group of candidate starting lines and adjacent surfaces are successively formed using these starting lines. The patterns with these surfaces, such as the surface ID in FIG. 6C, boundaries of the surface shown by broken lines in FIG. 6D, or the shading indicated by the mesh shown in FIG. 6E are beforehand presented on the display.

The detail of the outer loop and inner loop retrieval procedures will be explained in connection with FIG. 9 and following Figures. A group of edge lines constituting the outer loop and the inner loop are picked-up from a two-dimensional wire frame group as an object of the loop retrieval. This can be conducted by forming a tree structure of data from a group of candidate wire frames, and forming a loop through retrieval of the tree structure. This processing method applies both to the outer and inner loops.

To explain in more detail, a tree structure is formed from a group of given two-dimensional wire frames in the following manner. For the purpose of simplification of explanation, it is assumed here that the two-dimensional wire frames have been cut at their connecting or intersecting points. FIG. 9 shows a process of loop retrieval of a two-dimensional wire frame pattern. In this process, it is assumed that the wire frame l.sub.ij having an orientation D is a parent, while a group of wire frames l.sub.1 to l.sub.nj connected together at a point P.sub.ED constitute children. A tree structure of data as shown in FIG. 10 can be obtained using these wire frames. Representing the level of the wire frame l.sub.ij in the tree structure by j, the level of the wire frames l.sub.1 to l.sub.nj as children is represented by (j+1). Referring back to FIG. 9, a contact vector counter to the parent wire frame l.sub.ij and starting from the terminal point P.sub.ED of the wire frame l.sub.ij is represented by d. Also, a group of contact vectors d.sub.1 to d.sub.nj starting from the point P.sub.ED are assumed for respective children wire frames. The candidate wire frames l.sub.1 to l.sub.nj are then arrayed according to the angle .theta. of their contact vectors d.sub.1 to d.sub.nj from the contact vector d as measured in counter-clockwise direction, from the greatest to the smallest as shown in FIG. 11. Thus, the children of the level (j+1) generated from the parent of the level j are arrayed as l.sub.3, l.sub.1, l.sub.4, l.sub.nj and l.sub.2 as illustrated in FIG. 12. The loop retrieval is carried out using these children wire frames successively as the parent of the next level in the tree structure. Thus, in the loop retrieval shown in FIG. 9, the wire frame l.sub.3 is used as the parent of the level (J+1) in the tree structure. When the wire frame l.sub.3 is not intersected by nor connected to any other wire frame, the operation is not conducted for generation of a tree structure using this child wire frame as a parent, as marked by a black circle in FIG. 12, but the operation is conducted for the generation of the tree structure using the child wire frame l.sub.1 of the next order as the parent. The generation of the tree structure is continued until a loop is formed or until the retrieval is finished with all the two-dimensional wire frames which are the objects of the retrieval. Different conditions are used for the judgement of formation of the outer loop and the inner loop, as will be explained later in detail.

In the described embodiment, it has been estimated that the given wire frames are not divided at the crossing points nor connected at terminal points. Namely, the wire frames formed as the drafting data are used as they are. It is, therefore, necessary to conduct division of the wire frames, as well as connection at the terminal points, in conducting the loop retrieval through the formation of the tree structure.

It is assumed here that an outer loop retrieval is being conducted in the state of wire frame as shown in FIG. 13A, using the wire frame l.sub.i in the direction of vector D.sub.i as the parent of the level j in the tree structure. Thus, wire frames l.sub.1, l.sub.2 and l.sub.3 constitute the children wire frames of the level (J+1). As explained before, these wire frames are arrayed on the order of the angles of the contact vectors a the point P.sub.1, as represented by l.sub.3, l.sub.1, l.sub.2, so that a data tree structure as shown in FIG. 13B is formed. The wire frame l.sub.3 is used as the parent of the (J+1) level in the outer loop retrieval. As shown in FIG. 13A, the wire frame l.sub.3 crosses the wire frames l.sub.a, l.sub.b . . . l.sub.n. Therefore, at the moment at which the wire frame l.sub.3 is selected as the parent of the level (j+1) in the data tree structure, the wire frames l.sub.3, l.sub.a, l.sub.b . . . l.sub.n are divided at respective crossing points. More specifically, the wire frame l.sub.3 is divided into l.sub.31, l.sub.32 and l.sub.33, while wire frames l.sub.a and l.sub.b are divided into l.sub.al and l.sub.a2, and l.sub.bl and l.sub.b2, respectively. Similarly, the wire frame l.sub.n is divided into l.sub.n1 and l.sub.n2. At this moment, the wire frame constituting the parent of the level (j+1), i.e., the wire frame l.sub.3 in FIG. 13A, is replaced by the first wire frame l.sub.31 which is the first division from the wire frame l.sub.3 and extending in the direction D.sub.i+1 of the loop retrieval. At the same time, the wire frame l.sub.3 is erased from the data processing and, hence, does not exist any more. Thus, the wire frame l.sub.31 is used as the parent wire frame of the level (j+1) in the tree structure as shown in FIG. 14B. Then, only the wire frames l.sub.a1, l.sub.a2, l.sub.32, l.sub.b1 and l.sub.b2 which are connected to the wire frame at the terminal point P.sub.2 are taken out from among the divisional wire frames, and are arrayed according to the angle of the contact vectors at the point P.sub.2, as represented by l.sub.a2, l.sub.b2, l.sub.32, l.sub.a1, l.sub.b1, whereby children wire frames of a level (J+2) are formed. As explained before in connection with Step 47 in FIG. 7B, in case of the inner loop, the loop retrieval operation is carried out first by picking up the wire frames contained by the outer loop and then cutting these wire frames at their points of crossing and connection, so that the necessity for the substitution of the parent due to the cutting of the wire frame is eliminated.

An explanation will be made hereinunder with reference to FIGS. 15 to 18B as to the process in which, using the retrieval starting lines given by the generation of tree structures explained above, edge lines of loops constituting the outer loop or the inner loop are extracted from a group of two-dimensional wire frames as the loop retrieval. This process basically applies both to the outer loop and the inner loop, although there is a difference in judgement as to whether the replacement of parent as a result of division of the wire frame is conducted or not and as to whether the completion of the loop is in success or not.

First of all, at Step 61 shown in FIG. 15, a given starting line is used as the parent of level 0 (zero) in order to form a tree structure for the loop retrieval, and wire frames constituting the children of the parent wire frame are taken out and arrayed in accordance with the procedure explained before. Assuming here that a starting line L.sub.ST having the direction D is given for the two-dimensional wire frames as shown in FIG. 16, all the wire frames L.sub.1, L.sub.10 and L.sub.n passing through the terminal point P.sub.c of the starting line L.sub.ST constitute the children wire frames. In either case of the outer loop retrieval and inner loop retrieval, the group of wire frames L.sub.1, L.sub.10 and L.sub.n are cut at the point P.sub.c and the divisions of these wire frames are arrayed as l.sub.10a, l.sub.1a, l.sub.na, l.sub.10b, l.sub.1b and l.sub.nb as shown in FIGS. 17A and 17B, so as to be used as the children of the level "1" in the tree structure. Then, the formation of the tree structure is commenced using the first wire frame amongst the children wire frames of the level "1". Namely, initial setting of the level and the address of this wire frame is conducted in Step 62 in FIG. 15. In the example shown at FIG. 17A, the wire frame l.sub.10a is selected as the first candidate edge line of the first level, as shown in FIG. 17B. This is conducted at Step 63 shown in FIG. 15. Then, the process proceeds to Step 64 in FIG. 15, in which a judgement is done as to whether the selected candidate edge line constitutes a loop. Different judging method apply to the outer loop and the inner loop, as will be detailed later. If the judgement at Step 64 has proved that a loop is formed, the process proceeds to Step 74 shown in FIG. 15 in which a group of edge lines forming the loop are extracted from the group of candidate edge lines obtained through the loop retrieval, thus completing the process. In the example shown in FIG. 17A, the wire frame l.sub.10a does not constitute any loop, so that the process proceeds to Step 65 shown in FIG. 15. Since the i-th candidate edge line of the level J does not constitute any loop, it is necessary that children wire frames of the next level are formed using this candidate edge line wire frame as the parent. To this end, at Step 65, a judgement is done as to whether this parent wire frame has any child, i.e., as to whether this wire frame is crossed by or connected to any other wire frame in the direction of the loop retrieval, i.e., in the direction from the starting point of the wire frame to the terminal point of the same. Since the wire frame l.sub.10a in FIG. 17A has neither crossing nor connection in the direction d, this wire frame does not have any child so that it is marked by a black circle in FIG. 17B. As a result, the process proceeds to Step 66 shown in FIG. 15. At Step 66, therefore, a wire frame of the same level as the i-th wire frame of the level J and next to this wire frame, i.e., the wire frame addressed at i+1 is selected as the parent. This wire frame is shown by l.sub.1a in FIG. 17B. In case of FIG. 17B, it is possible to renew the address of the child wire frame from l.sub.10a to l.sub.1a. In such a case, there would be such a case that the address i of the child after the renewal of the address exceeds the total number of the children. At Step 67, therefore, a judgement is conducted as to whether the total number of the children is exceeded.

If the total number of the children is exceeded by the address of a child, the level is brought back by "1" to J, at Step 68 shown in FIG. 15. If the level J is not 0 (zero), a retrieval is conducted at Step 75 of the process shown in FIG. 15 to search the address i of the child in the J level, and the process proceeds to Step 66. Conversely, the fact that the level J is 0 (zero) at Step 69 means that the loop could not be formed even after the loop retrieval of all the two-dimensional wire frames. In this case, therefore, the processing is finished. In the case of the example shown in FIG. 17B, the process is returned to Step 63 as a result of judgement at Step 67, thus continuing the process.

It is assumed here that an outer loop retrieval is being conducted for the wire frames shown in FIG. 17A. In this case, the process returns to Step 63 and then to Step 64 in FIG. 15. Since the wire frame l.sub.1a does not constitute any loop, the process proceeds to a judging Step 65 in FIG. 15. In this case, the wire frame l.sub.1a used as the parent has children because it crosses wire frames L.sub.2, L.sub.3 and L.sub.4, so that the process proceeds to Step 70 in FIG. 15. Since the present retrieval is for the outer loop, it is necessary to pick-up the wire frames constituting the parent and children through division of the wire frames for the purpose of generation of the tree structure. This is conducted in Steps 70 and 71 in FIG. 15. Namely, as shown in FIG. 18A, the wire frame l.sub.1a is divided into wire frames l.sub.ST and l.sub.14, L.sub.3 is divided into l.sub.13 and l.sub.16, and L.sub.4 is divided into l.sub.12 and l.sub.15. On the other hand, the wire frame L.sub. 2 is connected to the wire frame l.sub.la to form a wire frame l.sub.11. Then, as explained before, the parent wire frame l.sub.la is replaced with l.sub.ST and the group of wire frames l.sub.11, l.sub.12, l.sub.13, l.sub.14, l.sub.15 and l.sub.16 as the children of the new parent wire frame l.sub.ST are taken out and arrayed. This operation is conducted at Step 72 in FIG. 15. Subsequently, at Step 73, the wire frame of the first address (i=1) amongst these children wire frames is appointed as the parent of the next level (J+1), i.e., as the next candidate edge line, and the process is returned to Step 63 to execute the loop retrieval. In example shown in FIG. 18, the wire frame l.sub.11 is the wire frame constituting the candidate edge line at the level (J+1). In the case of the inner loop retrieval, the operation at Step 70 is not necessary because, as explained before, the inner loop retrieval does not necessitate the division of the wire frame group.

The Steps explained above are followed until a loop is formed or, if not, until the retrieval is finished with all of the wire frames.

In case of the process shown in FIG. 18A, a loop is formed as an outer loop, as a result of the repetition of the above-described Steps, when the wire frame l.sub.ST is selected as the candidate edge line of the first level.

FIGS. 19A to 28B illustrate the process which is conducted after the appointment of the wire frame l.sub.ST. In these Figures which show successive steps of the process, the wire frames which have become candidate edge lines are shown by solid lines, whereas the wire frames which have just become children at respective moments are indicated by broken lines. These wire frames are drawn in a manner overlapping the original two-dimensional wire frames. The Figures with suffix B correspond to the Figure of the same number with suffix A, and illustrate the tree structures corresponding to the loop retrieval steps shown in corresponding Figure having the suffix A. Black circles appearing in respective Figures show that the wire frames marked by the black circles are neither crossed by nor connected to any other wire frame so that the formation of the tree structure is not conducted with this wire frame. Thus, in Figures having suffix B, the solid lines show a side line which connect the groups of candidate edge lines up to the instant moment, whereas the broken lines show other side lines representing the relationship between parents and children formed up to the instant moment.

The judgement as to whether a loop has been formed or not is conducted as follows. As explained before, different conditions apply for the judgement of formation of the outer loop and the inner loop. More specifically, as shown in FIGS. 29A and 29B, the judgement of formation of an outer loop is given only when the terminal end of the wire frame constituting the parent at a certain level of the tree structure, i.e., a candidate edge line, has coincided with the terminal point P.sub.c of the loop retrieval starting line, i.e., the starting point of the candidate edge line l.sub.ST of the first level. The edge lines constituting the thus formed loop are the wire frames which have experienced the parent in the tree structures of respective steps of the loop retrieval until the loop is formed. For instance, in the step shown in FIG. 29A, seven underlined lines l.sub.ST, l'.sub.12 ' l'.sub.2.sup.1 ' l'.sub.32 ' , l.sub.51 and l.sub.62 are the edge lines as constituents of the loop. The outer loop thus obtained revolves in the direction of arrow R in FIG. 29A without exemption.

The formation of an inner loop is judged on either one of the following two conditions. One of these conditions is that the same as that for the judgement of the formation of the outer loop, i.e., the fact that the terminal end of a wire frame constituting the parent in a certain level of the tree structure, i.e., a candidate edge line, has coincided with the terminal point of the loop retrieval starting line l.sub.ST, as shown in FIGS. 30A and 30B. It will be seen that, in the step shown in FIG. 30A, the terminal point of the wire frame l.sub.52 constituting the parent of the fourth level in the tree structure coincides with the terminal point P.sub.c of the starting line l.sub.ST. Thus, the loop is formed of edge lines which are the four underlined lines l.sub.41 (l.sub.ST), l.sub.12, l.sub.22 and l.sub.52. The thus formed loop revolves, without exemption, in the clockwise direction R in FIG. 30A.

Another condition for judging the formation of an inner loop is that, as shown in FIGS. 31A and 31B, the terminal point of the wire frame of a certain level in the tree structure has coincided with the terminal point of any constituent wire frame amongst the wire frames which have experienced children in the tree structure formed up to the instant moment. In this case, as will be seen from FIG. 31A, the last edge line l.sub.2 constituting the loop has been already presented as a child in the tree structure of the level 2. Since the direction of this edge line l.sub.2 is counter to the direction R of rotation of the loop, it is necessary to reverse the direction of this edge line so as to form an edge line l'.sub.2 which is directed from the terminal point to the starting point. Thus, the inner loop is constituted by edge lines which include the wire frames which have experienced the parents of respective levels of the tree structure from the level of the reversed last edge line l'.sub.2 (level 1 in FIG. 39B) down to the level at which the loop is completed, and the last edge line l'.sub.2. Thus, in the step shown in FIG. 31B, the edge lines constituting the loop are the five underlined lines l.sub.12, l.sub.13, l.sub.82, l.sub.10 and l'.sub.2. The thus obtained inner loop revolves clockwise as indicated by an arrow R in FIGS. 31A without exemption.

It is thus possible to extract the edge lines as constituents of loops which are to become an outer loop and an inner loop.

According to the described embodiment, the thus extracted edge lines are subjected to a post-processing which is broadly sorted into two kinds of processing. These processings are required due to the fact that the described embodiment is intended for use as an interactive modeling system which constitutes a base for a system such as CAE, CAD and CAM systems.

The first one of these two kinds of processing is effected when the group of the edge lines constituting an outer loop includes the same edge line, i.e., when the loop passes one of the edge lines twice, or when two or more edge lines are concentrated to a common branching point. In such a case, the groups of the edge lines are divided into a group which constitutes the outer loop and a group which constitutes the inner loop, by erasing the edge lines which is passed twice or the branching point to which two or more edge lines are concentrated. FIGS. 32A and 32B illustrate an example in which the edge line which is passed twice is erased. Referring to FIG. 32A, the outer loop revolving in the direction R is originally constituted by nine edge lines l.sub.1, l.sub.2, l.sub.3, l.sub.4, l.sub.5, l.sub.6, l.sub.7, l.sub.2 and l.sub.8. Thus, the loop passes the edge line l.sub.2 two times. Therefore, the line l.sub.2 is erased and the edge lines l.sub.3 and l.sub.7 are combined into a single edge line l.sub.9, whereby the edge lines are grouped into four edge lines l.sub.9, l.sub.4, l.sub.5 and l.sub.6 constituting an outer loop revolving in the direction R and two edge lines l.sub.1 and l.sub.2 constituting an inner loop which revolves in a direction indicated by an arrow Q.

Referring now to FIG. 33A, an outer loop is constituted by edge lines l.sub.1 to l.sub.9, and four edge lines l.sub.1, l.sub.2, l.sub.6 and l.sub.7 amongst these edge lines are concentrated to a branching point P. In this case, therefore, the edge lines are grouped into an outer loop having the revolving direction R and constituted by four edge lines l.sub.3, l.sub.4, l.sub.5 and l.sub.10 which is formed by combining the edge lines l.sub.6 and l.sub.2, and an inner loop having the revolving direction Q and constituted by four edge lines l.sub.1, l.sub.7, l.sub.8 and l.sub.9.

Another post-processing is carried out both for the outer and inner loops. This processing is intended for modifying the loops obtained through the loop retrieval in such a manner as to minimize the number of the edge lines. More specifically, in this processing, edge lines which can be geometrically combined are reformed into a single edge line. Assume here that an outer loop revolving in the counterclockwise direction R is constituted by nine edge lines l.sub.a, l.sub.b, l.sub.c, l.sub.d, l.sub.e, l.sub.f, l.sub.g, l.sub.h and l.sub.i, as shown in FIG. 34A. It will be seen that the edge lines l.sub.1, l.sub.i and l.sub.h are geometrically assembled into a single line l.sub.A. Similarly, the edge lines l.sub.d and l.sub.e can be assembled together into a single line l.sub.D, while the edge lines l.sub.f and l.sub.g can be assembled together into a single line l.sub.E. Through this geometrical trimming operation, the outer loop shown in FIG. 34A can be formed from five edge lines l.sub.A, l.sub.b, l.sub.c, l.sub.D and l.sub.E which revolve in the direction of arrow as shown in FIG. 34B, whereby the number of edge lines is reduced to five.

An explanation will be made hereinunder, with specific reference to FIG. 35, as to the basic data used in the loop retrieval, as well as the information structures thereof. The dots appearing in this Figure represent the pointers to the storage position indicated by arrows.

A reference numeral 81 designates a two-dimensional wire-frame table having wire-frame storage portion which stores information H inherent in each wire frame and geometrical information data G. An edge-line table 82 stores data such as the pointers to a coordinate value table 88 which stores the coordinate values X, Y of the starting and terminal points in the actual space, position pointers to the wire frame table 81 storing the geometrical information, parametric values a.sub.1 and a.sub.2 of the starting and terminating points, and so forth.

A reference numeral 83 designates a parent edge-line table which stores starting and terminating pointers to a child edge-line table, in accordance with the levels of the parents.

The child edge-line table 84 stores in a given order the position pointers to the edge-line table 82, in relation to the starting and terminating pointers in the parent edge-line table 83.

A loop table 85 stores pointers to the edge-line table, with representation of positive or negative direction, in relation to outer-loop starting and terminating pointers in a definite surface table 86 and inner-loop starting and terminating pointers in an inner loop table 87.

The definite surface table 86 stores starting and terminating pointers to the loop table 85, as well as the starting and terminating pointers to the inner loop table 87 representing the groups of inner loops.

The inner loop table 87 stores the starting and terminating pointers to the loop table 85 representing the inner loop.

The process for forming a definite surface on the basis of given two-dimensional wire frames has been described from the view point of the data structures.

As will be understood from the foregoing description, according to the invention, it is possible to automatically pick-up, in compliance with the user's demand, an outer loop constituting the minimal region containing a group of inner loops therein, simply by input of a single point on a two-dimensional wire frame pattern or input of a single specific pattern, even when the two-dimensional wire frame pattern is constituted by two-dimensional wire frames which are taken out from a data base in the state as they are after formation thereof as drafting data.

The user can appoint, on the two-dimensional wire frame pattern shown on a graphic display, any desired point in a definite surface which is to be formed into a three-dimensional form or, alternatively, a specific pattern. This input operation can be conducted in good concert with the user's recognition of the three-dimensional form on the design drawings, so that a high efficiency of the interactive modeling system is ensured.

Furthermore, in the described invention, the geometrical processing including the loop retrieval in a group of two-dimensional wire frames can be conducted by the use of information structures such as tree structures which the computer can handle with the highest efficiency. Consequently, the described embodiment offers a high performance by virtue of increased processing speed and minimization of the data storage region thanks to dynamical allocation.

As has been described, according to the invention, it is possible to automatically pick-up a definite surface or a group of wire frames, simply by appointing a point within a region or appointing a specific pattern with automatically formed surface, on a two-dimensional wire frame pattern which represents the surfaces constituting a three-dimensional form, so that the number of commands which are to be input during the interactive processing can be reduced remarkably. Furthermore, the work for directly appointing the definite surface which represents the actual form can be done in good concert with the process for the recognition of the objective form by the user from the design drawings, which remarkably improves the performance of the man-machine interface in the interactive processing for the purpose of generating a three-dimensional form.

As has been described, the invention provides a geometric modeling system which is easy to operate, by virtue of the improvement in the performance of the man-machine interface, as well as the simplification of the input operation.