Apparatus for Displaying Three-Dimensional Objects

The present invention relates to a display apparatus for displaying a plurality of three-dimensional objects on a display as two-dimensionally displayed figures, and for showing precisely the positional relationship among the three-dimensional objects in a manner suitable, for instance, to robot simulation or the like.

Along with the advancement in robot technology, there have been developed various kinds of languages to control and manipulate robots. Computer robot language has frequently been used to simulate the behavior of a robot.

A robot's simulator displays the robot hands and the three-dimensional objects with which the robot is interacting. The robot's hands and objects are shown on the display as two-dimensional figures, and the motion of the robot hands is traced on the display. In the two-dimensional display of the three-dimensional objects, each object is treated as a projected figure or a perspective figure as seen from a certain line-of-sight. Accordingly, the user follows the behavior of the robot on the two dimensional display controlled by the robot language while inspecting the presence or absence of any connecting relationship indicated on the display, such as interference (collision) between objects that are displayed as two-dimensional figures.

However, when the projected views or perspective views are employed, the displayed positional relationship among the objects varies depending on the direction of line-of-sight. For this reason, the user can have difficulty in visualizing the interfering relationships among a plurality of objects, and whether or not the objects appear to be in contact or separated depends upon the direction of the line-of-sight.

Therefore, if a plurality of objects that are displayed as two-dimensional figures are seen as overlapping (when it is not clear whether or not there exists an interference), the user gives the command to change the direction of line-of-sight. Upon receipt of this command, the simulator obtains and displays a projected or perspective view of the three-dimensional objects as seen along a different direction of line-of-sight. However, the selection of the direction of line-of-sight is executed by the user on a trial and error basis. It is not unusual to change the line-of-sight many times until the user can determine whether interference exists among the objects. The prior art systems consequently have poor processing efficiency.

The general operation and programming of a robot is discussed in Kodaira et al., "Interactive Robot Programming with Real-Time Graphic Simulation," IECON'84, pp. 35-39.

The object of the present invention is to provide an apparatus for displaying a plurality of three-dimensional objects as two-dimensional figures, and to detect interferential relationships among the objects in a form that can be understood clearly, without repeated changes in the direction of line-of-sight. The display apparatus reads out form and position data for each of the designated three-dimensional objects from an environmental data memory and calculates a direction of line-of-sight which can display without mutual interference two-dimensionally displayed figures of the plurality of three-dimensional objects based on the form and position data obtained. The apparatus then prepares two-dimensional figure data for the plurality of three-dimensional objects in accordance with the calculated direction of line-of-sight and the form and position data obtained.

According to the present invention, interferential relationships among a plurality of three-dimensional objects is checked in accordance with the form and position data for the three-dimensional objects. When it is determined that there does not exist interference, a direction of line-of-sight which can show clearly the noninterfering state is calculated and two dimensionally projected figure data from that direction of line-of-sight is determined. Therefore, a plurality of objects that have no mutual interference can be displayed as two-dimensional figures in a form that clearly show the absence of interference, eliminating the need for the operator to change the direction of line-of-sight on a trial and error basis. As a result, it becomes possible to carry out robot simulation in an efficient manner.

FIG. 1 is a block diagram which shows a preferred embodiment of the present invention.

FIG. 2A is a schematic diagram of a representative three-dimensional object which shows the apex numbers, segment numbers, and surface numbers associated with the object.

FIG. 2B is a schematic diagram which shows the internal configuration and contents of the environmental data memory for the object of FIG. 2A.

FIG. 3 is a flow chart which shows the processing procedure of the apparatus shown in FIG. 1.

FIG. 4 is a schematic diagram which illustrates the reform determining a direction of line of sight.

FIG. 5A is a schematic diagram of the display screen which illustrates the presence of interference between two-dimensionally displayed figures for two objects.

FIG. 5B is a schematic diagram of the display screen which illustrates the state of separation between the two-dimensionally displayed figures for the two objects of FIG. 5A.

Referring now to the figures, the present invention will be described in detail.

FIG. 1 shows a schematic block diagram for a preferred embodiment of the present invention which may be applied to a robot simulator.

An input portion 1 can have, for example, a keyboard for inputting control information necessary for operating and controlling a robot simulator. A display 2 displays two-dimensional representations of the robot and the objects with which the robot works A simulator 3 consists of an environmental data memory 4, which stores the form and position data of the robot and the three-dimensional objects, a display control unit 5, which prepares two dimensional figure data for displaying the robot and the three-dimensional objects on the display as two-dimensional figures, and a line-of-sight computation unit 6 which calculates the direction of line of-sight for the robot and the three-dimensional objects to be displayed as two-dimensional figures.

The environmental data memory 4 stores the form and position data of the robot and the three-dimensional objects as position coordinates of each apex, line segment, and surface information of objects in a predetermined three-dimensional coordinate space. FIG. 2B is a diagram which shows an example of storing the form and position data. For example, for the object depicted as a rectangular parallelepiped in FIG. 2A, coordinate information for eight apices a1-a8 (absolute coordinate values), segment information for 12 sides 11-112 (numbers for both end points of each side), and surface information for 6 surfaces s1-s6 (numbers for all edge points for each surface) are stored as shown in FIG. 2B.

Form and position data concerning each object are retrieved, when the name of the object is designated through the input unit 1 by a display change indication from the environmental data memory 4 in accordance with the name of the object. The information is provided to the display control unit 5 and the line-of-sight computation unit 6 respectively.

The display control unit 5 determines the two-dimensional figure data by computing the projected coordinates as seen from a particular direction of line-of-sight for each object from the form and position data concerning each object in accordance with the direction of line-of-sight (line-of-sight vector) indicated by the line-of-sight computation unit 6 as will be described below. The two-dimensional figure data obtained in the display control unit 5 is given to the display 2 where the two-dimensional figure is displayed. Ordinarily, information in a certain predetermined direction of line-of-sight is provided from the line-of-sight computation unit 6. Consequently, the display control unit 5 prepares two-dimensional figure data from the predetermined direction of line-of-sight, and displays the data on the display 2.

The line-of-sight computation unit 6 is actuated when an operator indicates for a change in the direction of line-of-sight, via the input unit 1. the line-of-sight computation unit 6 calculates a line-of-sight vector for displaying a three-dimensional object as a two-dimensional figure using the method as shown in FIG. 3.

FIG. 3 describes the process of displaying the two-dimensional figures. When the interferential relationship between some objects that are displayed on display 2 is unclear (for example, when two objects are displayed as mutually overlapping), input unit 1 indicates a change in display. This indication of display change can be accomplished by inputting the names of the two objects whose interferential relationship the operator wishes to clarify (step a). The line-of-sight computation unit 6 retrieves the form and position data concerning the specified two objects from the environmental data memory 4 (step b). Next, both objects are tested to determine if either has a convex shape (step c). If either object is convex (i.e. the surfaces of the object are convex), a check is made to determine whether or not the two objects are mutually interfering (step d). If no interference exists, the normal vector to a plane which separates the two objects is determined using the form and position data for the two objects (step e). Selection of the normal vector is continued until it is found to satisfy the display standard, that is, until a vector is determined that is normal to a plane which completely separates the two objects (step f). Once a normal vector is determined, a line-of-sight vector which is orthogonal to the normal vector, namely, a line-of-sight direction along which it is possible to display the two objects as two-dimensional figures without mutual interference, is calculated (step g). The line-of-sight vector determined in this manner is provided to the display control unit 5 where two-dimensional figure data for the two objects is prepared in accordance with the line-of-sight direction (step h). The newly obtained two-dimensional figure is displayed on the display 2 (step i). Thus the line-of-sight direction which displays an ambiguous two-dimensional figure indicating an interferential relationship of the three-dimensional objects is changed to one showing without ambiguity the relationship of the objects.

Next, the computational processing for the line-of-sight direction in the line-of-sight computation unit 6 will be described in more detail.

When two objects A and B that mutually overlap on display 2 are identified at input 1, the form and position data are read respectively as follows.

where a.sub.i and b.sub.j are apex coordinates; l.sub.i ' and l.sub.j ' are end points of sides; s.sub.i " and s.sub.j " are all edge points of a surface.

Then, whether or not the two objects A and B are convex is checked. The method for confirming that an object is convex is to see that all of the segments that are obtained by joining arbitrary end points of the objects (namely, a.sub.i1 a.sub.i2 (i.ltoreq.i1,i2.ltoreq.m) for object A, and b.sub.j1 b.sub.j2 (l.ltoreq.j1, j2.ltoreq.n) for object B) are contained within the object.

If at least one of the objects has a concave surface, there can be a penetrating relationship between the objects although there is no interference or contact. There are some cases in which it is not possible to display the objects as separate two-dimensional figures even with changes in the line-of-sight direction. In those cases, the computational processing for the change of line-of-sight direction will not be carried out. However, if the two objects are situated sufficiently separate from each other so that a concave object may be regarded as though it were a convex object and the computational processing for the line-of-sight direction for two-dimensional figure display by separation may be carried out.

When two objects A and B are confirmed to be convex objects, the first step is to judge whether or not they are mutually interfering based on the form and position data for them. The method for judging this is done by examining whether or not any side of object A intersects with the surfaces of object B. In other words, first the line equation for an arbitrary side of object A is determined from li', second the plane equation for, an arbitrary plane of object B is determined from sj", and third the intersection between the corresponding infinite line and the infinite plane is determined.

Next, it is determined if the intersection lies on the finite side of object A and in the finite plane of object B and a similar test is carried out for all possible combinations of all sides of A and for all surfaces of B. If it is found for all the combinations that none of the intersections are on the finite side of object A or at a surface of object B then a similar examination is carried out for the reversed situation, namely, for each side of B and for each surface of A. If no intersections are found to lie in the regions corresponding to interference between objects for all possible combinations, then it is determined that the two objects A and B are not mutually interfering. When there is an interference between objects, it is impossible to obtain a two-dimensional figure display showing separation of the two objects, so that the processing will be discontinued at that point.

Now, when two convex objects A and B exist in three dimensional space without mutual interference, there exists necessarily some plane C which separates the objects A and B, as shown in FIG. 4. Consequently, by choosing a direction in the plane C as a direction of line-of-sight, it becomes possible to display the two objects A and B as separate two-dimensional figures.

If the position coordinate of a fixed point in the plane C is called e, the position coordinate of an arbitrary point in the plane C is called x, and the normal vector to the plane C is called n, then the equation of the plane C is given by

where . signifies an inner product. If respective apices ai and bj of the two objects A and B are located into two regions defined by the plane C, it can be said that the plane C separates A and B in the three-dimensional space. Therefore it is sufficient if the following conditions are met:

By finding a normal vector n that satisfies the above conditions, and by determining a vector V which satisfies

one may choose the vector V as the line-of-sight vector. That is, the line-of-sight vector V may be used for the line-of-sight direction which can display the two objects A and B as non-overlapping two-dimensional figures. (It should be noted that the vector V which satisfies the above orthogonality condition can exist as a plurality of solutions, but it suffices if one of them is obtained.)

The fixed point e in the plane C preferably is determined as follows. First, the centers of gravity ga and gb of the two objects A and B, respectively, can be represented from the apex coordinates in the form and position data as ##EQU1## Since the objects A and B are convex objects, each of the respective centers of gravity ga and gb are interior points of the objects. In addition, due to the fact that the objects A and B are free from interference as mentioned earlier, there necessarily exists a point on the straight line 7 (as shown in FIG. 4) that connects the two centers of gravity ga and gb, and that is not an interior point of either one of the objects. Therefore, one needs only to choose a point on the straight line 7 which is contained in neither of the objects A and B, as the fixed point e in the above.

More specifically, if the equation for the straight line 7 is given by

one needs to determine the maximum value of t (=t.sub.a) for a point k on the straight line 7 that can exist as an interior point of the object A, and the minimum value of t (=t.sub.b) for a point k that, can exist as an interior point of the object B. Then, as shown in FIG. 4, the fixed point e may be defined as the midpoint between these points as given by ##EQU2##

On the other hand, the normal vector n to the plane C can be determined by using, for example, the two-division learning system of Perceptron. If one sets

for the apex coordinates ai and bj and the fixed point e, the conditions in Equation (1) become

Consequently, by arbitrarily choosing an initial value for the normal vector n, one examines whether or not the conditions in Equation (2) are satisfied by that normal vector n. For example one chooses ##EQU3## as the initial, value for n, and examines whether or not the conditions in Equation (2) are satisfied for a.sub.i ' and b.sub.j '. If at least one of the conditions in Equation (2) for a.sub.i ' and b.sub.j ' is not satisfied, then the initial value of the normal vector n is changed as follows. ##EQU4## where .vertline. .vertline. the magnitude of a vector. By repeating such a change of the normal vector and the decision processing of whether or not the normal vector n satisfies the conditions in Equation (2), one can determine a normal vector n that satisfies both of the conditions.

According to the learning method of Perceptron, the existence of the solution is guaranteed so that with a finite number of changes of the normal vector n, it is possible to determine a normal vector n that satisfies the conditions in Equation (2).

Using a normal vector n thus obtained, the line-of-sight direction (line-of-sight vector V) for which a two-dimensional figure display is possible with a complete separation of the two objects A and B, can be determined.

For example, if one writes the normal vector n obtained as ##EQU5## and the line-of-sight vector V to be determined as ##EQU6## then one needs only to determine V that satisfies

from V.n =0. (Although a plurality of solutions can exist, one needs only to determine one of them.)

When a line-of-sight vector V is obtained in this way, the line-of-sight computation unit 6 shown in FIG. 1 sends the information on V to the display control unit 5. The display control unit 5 prepares two-dimensional figure data to be displayed on the display 2 from the line-of-sight vector V and the apex coordinates ai and bj that are read from the environmental data memory 4. For example, the transformation matrix m for the line-of-sight can be expressed as ##EQU7## which can be expressed as ##EQU8## If the apex coordinates are expressed as ##EQU9## then the apex coordinates (X, Y) of the two-dimensional figure to be depicted o the display can be determined by ##EQU10##

Accordingly, if the interferential relationship between two objects X and Y is unclear when they are displayed on the display screen as two-dimensional figures, as in FIG. 5A, a line-of-sight direction which shows the interferential relationship between the two objects can be selected merely be indicating a change in display by designating the two objects at the input 1. The display is changed as shown in FIG. 5B. In other words, two objects X and Y that are displayed as overlapping in FIG. 5A can be displayed as mutually separated two-dimensionally displayed figures as shown in FIG. 5B without the operator going through a series of trial and error changes in the line-of-sight direction.

It should be noted that the present invention is not limited to the embodiment described in the foregoing. Thus, for instance, the algorithm for computational processing for the line-of-sight direction may be modified in various ways such as to be carried out with expanded display conditions and under quantitative conditions. In addition, in showing the interferential relationship among three or more objects, it may be arranged to find a direction along which overlapping among these objects tends to be decreased. In other words, by giving special emphasis to the portion for which the overlapping condition is most critical, the line-of-sight direction may be determined so as to have that portion separated and displayed as two-dimensional figures. Moreover, the particular two-dimensional figure display is not limited to that described in the present embodiment.