JPH0241791B2 - - Google Patents

Description

[Detailed description of the invention]

[Technical Field of the Invention] The present invention generates a projected rectangular area of a basic object (a sphere, a rectangular parallelepiped, a cylinder, a cone, etc.) on a projected screen plane in the process of processing a three-dimensional object, and performs object recognition on these areas. This invention relates to a three-dimensional object recognition and display method that can be used to speed up image display. [Prior art and problems] Figure 1 shows an overview of a conventional three-dimensional object recognition and display system. In Figure 1, P is a pixel, ri and rj are line of sight, S is a screen plane, and a and b.
1 represents the basic object, and objects X to Z represent the coordinate axes of the world space. In the conventional three-dimensional object recognition and display method, objects are placed at each point (pixel) P on a screen (display surface of an image display device) S with basic objects a and b constituting an object 1 existing in world space. In order to determine whether or not to display 1, an intersection test between the line of sight ri, rj... emitted from the viewpoint and the basic objects a, b is performed on all pixels P.
going against Therefore, there is a drawback that the amount of calculation increases and display cannot be performed at high speed. [Object of the Invention] The present invention aims to eliminate the above-mentioned drawbacks by generating a two-dimensional rectangular area on a screen plane indicating the area where a three-dimensional object synthesized from basic objects exists, and The purpose of this invention is to provide an efficient three-dimensional object recognition and display method by performing intersection determination only when the line of sight passing through the rectangular area exists, thereby reducing the amount of calculation for intersection determination. [Structure of the Invention] Therefore, the three-dimensional object recognition and display method of the present invention includes a file storing a binary tree data structure in which each node corresponds to an object and leaf nodes correspond to basic objects; - Generate a box area surrounding the basic object indicated by the node, generate a rectangular area of the basic object based on the figure when the generated box area is projected onto the screen plane, and calculate the rectangular area of the generated basic object. Boundary area generation means for associating it with a corresponding leaf node, sequentially generating a rectangular area corresponding to each node based on the rectangular area of the leaf node, and associating the generated rectangular area with the corresponding node, and adding a rectangular area. The present invention is characterized by comprising an object recognition means that refers to the binary tree format data structure and performs intersection determination with an object only for a line of sight that passes through a rectangular area out of the line of sight that emanates from the viewpoint. [Embodiments of the Invention] The present invention will be described below with reference to the drawings. FIG. 2 is a diagram showing a rectangular area for the object 1 on the screen plane. In FIG. 2, a' indicates a projected rectangular area for basic object a, b' indicates a projected rectangular area for basic object 1, and 1' indicates a projected rectangular area for object 1, respectively. In the present invention, rectangular areas a', b', 1' projected onto the screen plane S of the basic objects a, b and the quasi-object (intermediate object) 1 in the synthesis process thereof are generated in the preprocessing stage. It is. This production rule can be used as an object composition method (+: union set, -: difference set,
(&: intersection set) based on three Boolean operators. FIGS. 3A and 3B are diagrams showing an outline of a three-dimensional object recognition and display system according to the present invention. In this example, object 1 is represented by the union of basic objects a and b. Third
Figure B shows a binary tree data structure representing object 1. In FIG. 3B, circles indicate intermediate nodes and squares indicate basic objects (leaf nodes). In the present invention, information indicating the projected rectangular area a' is added to the leaf node of a, information indicating the projected rectangular area b' is added to the leaf node of b, and the intermediate node of object 1 is attached with information indicating the projected rectangular area b'. Projected rectangular area 1'
Information indicating that is added. Then, during object recognition, this data structure is searched top-down, the line of sight continues only for objects included within this rectangular area, and finally intersection with the basic object is determined. In Figure 3 A,
Since the line of sight ri is not within the rectangular area 1', the basic objects a,
No cross determination with b is performed. FIG. 4 is a diagram illustrating the hierarchical representation of objects. In the present invention, the composition process for forming an object is expressed using a binary tree data structure. In this binary tree data structure, spatial information occupied by the intermediate object is added to each intermediate node, spatial information occupied by the basic object is added to each leaf node, and the binary tree data structure is Use as an expression. At this time, information such as position and size is stored only in leaf nodes that have information representing the basic object. Figure 3 shows a binary tree data structure representing an object called a house. An object called a house is expressed as house=a+b+(c-d). Note that a, b, c, and d indicate basic objects. First, as preprocessing, we determine the rectangular area of each intermediate node from the leaf node to the bottom up.
Add that information to each node. The method for defining this rectangular area is as follows. (i) For each basic object, define a box region circumscribing the basic object. FIG. 5 explains the definition of a box area for a basic object, and in FIG. 5, x, y, and z indicate the coordinate system of the basic object. (ii) Transform each vertex of the box region into screen coordinate space, and project each transformed vertex onto the screen. (iii) Determine the rectangular area of the basic object by finding the maximum and minimum values of the vertex coordinates projected on the screen. FIG. 6 explains the definition of a rectangular area on the screen. (iv) Next, while climbing the binary tree data structure from the bottom up, construct a rectangular area at each node according to the following rules.

〔Effect of the invention〕

As is clear from the above description, according to the present invention, since a rectangular area on the screen is effectively used in the object recognition process, the amount of calculation for intersection between the line of sight and the object can be minimized. This has the effect that processing such as object recognition and display can be performed at high speed.

[Brief explanation of drawings]

FIG. 1 is a diagram explaining a conventional three-dimensional object recognition and display system, FIG. 2 is a diagram showing a rectangular area on a screen plane in the present invention, and FIG. Figure 4 is a diagram showing a hierarchical representation of an object, Figure 5 is a diagram for explaining the definition of a box area surrounding a basic object, and Figure 6 is a diagram of a box of a basic object projected onto a screen plane. A diagram for explaining a method of creating a rectangular area from an area, FIG. 7 is a diagram showing a software configuration when the present invention is implemented using a computer, and FIG. 8 is a diagram for explaining the boundary generation routine of FIG. 7. Figure 9 is the 7th figure.
FIG. 3 is a diagram for explaining the object recognition routine shown in the figure. ri and rj... line of sight, a and b... basic objects.

Claims (1)

[Claims] 1 A file that stores a binary tree data structure in which each node corresponds to an object and leaf nodes correspond to basic objects, and a box generated by creating a box area surrounding the basic object indicated by the leaf node. A rectangular area of the basic object is generated based on the figure when the area is projected onto the screen plane, and the rectangular area of the generated basic object is associated with the corresponding leaf node. Boundary area generation means that sequentially generates rectangular areas corresponding to the nodes and associates the generated rectangular areas with the corresponding nodes, and a line of sight that emanates from the viewpoint with reference to the binary tree format data structure to which the rectangular areas are added. A three-dimensional object recognition and display system comprising: object recognition means for determining intersection with an object only for a line of sight passing through a rectangular area.