JPH0634239B2 - 3D image display device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION (Industrial field of application) The present invention provides a raster scanning C-type image of a polyhedron with color shading.
The present invention relates to a three-dimensional image display device for generating and displaying on an RT.

(Prior Art) As a method of generating and displaying a three-dimensional image with color shading on a raster scanning CRT, there is a display processing method using a z-buffer method of a polyhedral model. The display processing procedure will be described below.

(I) Shape modeling ... Define an object shape in a three-dimensional world coordinate system. In the polyhedron model, the object shape is expressed by the vertexes, ridges, surface coordinate values and their adjacency. When the surface of the object includes a curved surface, the curved surface is divided into polygons for approximation. The method of creating the polyhedral model will be described later.

(II) Projection conversion: Specify the projection plane, viewpoint, and projection method (parallel projection or central projection) in the world coordinate system, and make a three-dimensional screen coordinate system based on the screen frame set on the projection surface. Projection conversion is performed.

Projection transformation from the world coordinate system to the screen coordinate system is a combination of rotation of the coordinate axes, parallel movement, scaling to screen coordinates, and perspective transformation. As will be described later, from 4 × 4 matrix multiplication and perspective division. Become. The space part behind the projection plane seen from the viewpoint through the screen frame is mapped inside the rectangular parallelepiped of the screen coordinate system. The z value of the screen coordinate system is called depth and is used for hidden surface removal. In the polyhedron model, all the vertices of the polyhedron may be projected and transformed. In projective transformation, a straight line is transformed into a straight line, and since it has the property of not changing the internal division ratio, it is possible to draw the ridgeline or surface of the original polyhedron by linear interpolation calculation inside the screen coordinate system, and the depth is also 1 point. Correctly requested. As a result of the coordinate conversion, clipping or back surface removal may be performed.
Clipping sets a rectangular window on the projection surface, and removes all or part of the polygon protruding outside the window frame for each polygon surrounding the polyhedron in order to display only the inside of the window frame of the projection view. It is a process to do. The back surface removal is processing for detecting and removing a polygon on the back surface that is apparently invisible from the viewpoint.

(III) Scan conversion ... In order to fill and display a polygon represented as a series of vertices in the screen coordinate system, the polygon is converted into a series of pixels. To this end, pixels on the ridge line are interpolated and generated from the vertex coordinates of the polygon, and further pixels inside the polygon are interpolated and generated. To remove the hidden surface, the depth z from the projection surface to the polygon is calculated for each pixel.

(IV) Image display accompanied by hidden surface removal ... When multiple polygons overlap each other on the display screen, it is necessary to preferentially display the polygon closest to the viewpoint. The z-buffer method is to perform this hidden surface removal in pixel units. In the z-buffer method, for the two-dimensional pixel address (x, y), the intensity of the three primary colors R, G, B
In addition to an image memory (also referred to as a frame buffer) that stores a z, a z buffer memory (also referred to as a depth buffer) that stores a depth z is used.
The z buffer memory is filled with the maximum depth z _max . Image memory when a polygon is scanned and converted into a series of pixels (X _i , y _i , z _i , R _i , G _i , B _i ) i = 1, 2, 3, ... The intensity of the three primary colors R _i , G _i , B _i at (x _i , y _i )
Before writing, z buffer memory (x _i, y _i) address of the depth _{z M} (x _i, y _i) is read out is compared with _{z i, z} i <
Only when z _M , R _i , G _i , and B _i are written, and the value of z _M (x _i , y _i ) is updated with z _i . Therefore, the z buffer memory has a function of storing the depth of a polygon whose value drawn up to now is close to the viewpoint for each pixel, and prohibits the writing even if a polygon pixel having a depth larger than this comes. If the above processing is sequentially executed for all the scan-converted pixels of all polygons, a three-dimensional image in which the hidden surface is erased correctly and the depth of visible pixels is given is finally obtained.
Obtained by R _M , G _M , B _M , z _M. The value of (R, G, B) can be given different values for each polygon in advance, and the reflection intensity is calculated for each polygon when the light source is specified and shaded and displayed. There are methods, such as a method of calculating reflection intensity for each vertex and interpolating inside the polygon to give a smooth shadow.

The above display method is suitable for high-speed processing by hardware, and a three-dimensional image display device including a coordinate converter, a scan converter, and a z-buffer memory in addition to the image memory has been proposed. FIG. 18 shows the structure of a conventional three-dimensional image display device of this type. In the figure, the host processor 21 executes a large amount of calculation in the processing of expression conversion as will be described later, and sends the result to the display device side via the host interface 22. The control processor 23 controls each part of the device to execute the series of display processes described above. The graphic memory 24 stores polyhedron data, the coordinate converter 25 performs projection conversion of vertices, the scan converter 26 performs polygon scan conversion, and the memory updater 27 uses the z buffer memory 29 to erase hidden surfaces. While performing, a three-dimensional image is created in the image memory 28 and displayed on the CRT 30. The roles of the image memory 28 and the z buffer memory 29 are as described above.

Next, a conventional method for creating a polyhedral model will be described. FIG. 19 is a diagram showing the shape of a polyhedron that is synthesized by the spatial logical operation of two rectangular parallelepipeds A and B. FIG. 19A shows the positional relationship between A and B, and FIG. The sum A∨B, the logical product A∧B in the same figure (c), and the logical difference A in the same figure (d).
-B is the result. Normally, when the user of the system inputs the shapes and dimensions of basic solids such as A and B, both movement and rotation, and logical operation symbols, the polyhedral modeling system coordinates-converts both polyhedra to set the positional relationship. , A polyhedron model is created by finding all intersecting edges of both polyhedra and all polygons surrounding the target composite. The third, fourth basic solids and other composites are successively synthesized on the completed polyhedron to form a polyhedron of increasingly complicated shape. Fig. 20 shows four basic solids A ₁ , A ₂ , A ₃ , A
FIG. ₄ is a diagram showing an example of a synthesizing method of CSG (Constructive
Solid Geometory) or a CSG tree is a three-dimensional representation method. On the other hand, the representation by the set of polygons that surround the polyhedron is the boundary representation (Boundary Representatio
n) called. Since a large amount of calculation is required for the process of converting from the CSG representation to the boundary representation, this process is usually executed in the host processor 21 of FIG. The data is transferred to the memory 24, and the display processing is performed on the display device side after the projection conversion.

(Problems to be solved by the invention) However, in the processing method described above, it is necessary to examine three-dimensional intersections for all combinations of polygons surrounding both polyhedrons in order to obtain the intersecting ridgelines of the two polyhedra. Therefore, the user spends a lot of time from inputting the CSG representation of the polyhedron to obtaining the three-dimensional image, and this poor responsiveness is one of the major problems of the interactive polyhedron modeling system. It was a point.

The present invention has been made to solve the above-mentioned problems of the prior art, and provides a three-dimensional image display device capable of directly displaying a CSG expression polyhedron so that a polyhedral modeling system having excellent responsiveness can be constructed. The purpose is to provide.

(Means for Solving Problems) A two-dimensional image display device of the present invention stores the CSG expression data of a polyhedron and the basic stereoscopic data that is a component thereof in order to solve the problems of the above-mentioned conventional technology. 1 graphic memory, a coordinate converter that performs coordinate conversion and projection conversion on the basic stereoscopic data according to the CSG expression and viewpoint information, a second graphic memory that stores the converted basic stereoscopic data, and a basic stereoscopic data. A scan converter that scan-converts a polygon that surrounds the area into pixel data having three primary color intensities and depth, an image memory that stores the three primary color intensities of a three-dimensional image for each pixel on the screen, and a temporary depth for each pixel. The first z to remember
A buffer memory, a second z-buffer memory that temporarily stores only the depths of the constituent pixels when the front surface or the rear surface of only one of the basic solids in the CSG representation is scan-converted, and the visible pixels are CSG. A logical operation memory for determining whether each of the constituent pixels of the front surface or the rear surface of the basic solid is inside or outside of another basic solid and storing the result in order to detect according to the logical expression. An operation for writing pixel data to which depth has been added to the image memory and the first z buffer memory while erasing the hidden surface, and a memory update for controlling the second z buffer memory and the logical operation memory for CSG logical operation Is provided, the intensity and depth of the three primary colors are obtained for the constituent pixels of the visible basic solid, and the image memory and the first z-buffer memory are erased while the hidden surface of the data is hidden. By writing to, in which so as to display the 3-dimensional image of the polyhedron by the CSG representation.

(Function) Since the three-dimensional image display device is configured as described above according to the present invention, each technical means functions as follows.

The first graphic memory is the basic stereoscopic data and the polyhedral CSG.
Store expression data. The coordinate converter reads the basic stereoscopic data from the first graphic memory and performs coordinate conversion and projection conversion on it. The converted basic stereoscopic data is stored in the second graphic memory. The scan converter scan-converts a polygon surrounding a basic solid to obtain pixel data of three primary color intensities and depths. The pixel data is written in the image memory and the first z-buffer memory while the hidden surface is erased by the function of the memory updater. That is, the image memory stores the three primary color intensities of the three-dimensional image for each pixel on the screen, and the first z-buffer memory stores the depth for each pixel. By the way, in the present invention, a polyhedron is synthesized from the converted basic stereoscopic data stored in the second graphic memory. Due to this synthesis, the second z-buffer memory is only one of the basic solids. Only the depths of pixels obtained by scan-converting the front surface or the rear surface of are stored, while the logical operation memory holds the result of determining whether each pixel of one basic solid is inside or outside of another basic solid. Then, by the function of the memory updater, a pixel which becomes visible while referring to these information is obtained in accordance with the CSG logical operation. Then, by operating the memory renewal device, the data of the three primary color intensities and depths of the basic solids which are determined to be visible are erased while the image memory and the first data are erased.
Correctly written to the z-buffer memory of. Therefore, the polyhedral image can be directly displayed without conversion from the CSG representation to the boundary representation, and the problems of the above-mentioned conventional techniques are solved.

(Example) Hereinafter, one example of the present invention will be described in detail.

FIG. 1 is a block diagram showing the configuration of the three-dimensional image display device of this embodiment. In the figure, 1 is a host processor, 2 is a host interface, 3 is a control processor, 4 is a first graphic memory, 5 is a second graphic memory, 6 is a coordinate converter, and 7 is a coordinate converter.
Is a scan converter, 8 is a memory updater, 9 is an image memory, 1
Reference numeral 0 is a first z buffer memory, 11 is a second z buffer memory, and 12 is a logical operation memory. This device is the first
Compared with the conventional device of FIG. 8, the second graphic memory 5,
The main difference is that a second z-buffer memory 11 and a logical operation memory 12 are added. If the three-dimensional image display device of FIG. 1 is used, in addition to the polyhedral model of boundary representation,
Images of polyhedral models in CSG representation can also be generated. Less than,
The procedure of displaying the CSG-represented polyhedron using this apparatus will be described in detail.

All the 3 to be displayed in the first graphic memory 4 of FIG.
The dimensional figure data is stored. These graphic data are usually already described in the three-dimensional world coordinate system, and are sequentially read out, subjected to projection conversion by the coordinate converter 6 and scan conversion by the scan converter 7, and by the operation of the memory updater 8. The images are combined into the image memory 9 and the first z-buffer memory 10 as a three-dimensional image with depth. The polyhedron of CSG expression occurs as one expression form of these figures, and at this time, it is necessary to correctly synthesize and display the CSG polyhedron in the image memory 9.

The CSG representation polyhedron has a tree structure as illustrated in FIG. The "basic solid" located in the leaves of the CSG tree is defined as shown in FIG. Fig. 3 (a)
In the coordinate system O-XYZ fixed to the basic solid as described above, the coordinates of the vertices V _{1 to} V ₈ of the basic solid are defined as shown in FIG. 3 (b), and the surfaces S _{1 to} S surrounding the basic solid are defined. ₆ to FIG.
It is defined as a series of vertices as shown in (c). Each face is polygonal, and the vertices are arranged in order so as to be counterclockwise when viewed from the outside of the basic solid. The “transformation” located in the branch of the CSG tree in FIG. 20 designates coordinate transformation of a basic solid or a solid in the process of synthesis (hereinafter, simply referred to as solid), and is a combination of enlargement, reduction, translation, and rotation. Is allowed. This conversion is a multiplication of a vector and a matrix as shown below.

The "composite" located in the node of the CSG tree in FIG. 20 is to perform a binary logic operation of either sum, product or difference on the two coordinate-transformed solids. In Fig. 20, the basic solid A ₁ , A
₂ is subjected to “Synthesis 1”, basic solids A ₃ and A ₄ are subjected to “Synthesis 2”, and these synthetic bodies are further subjected to “Synthesis 3” to obtain a final synthetic body. "Transformation 7" has a function of placing or moving this composite body at an appropriate position in the world coordinate system. This composite is further subjected to “projection conversion” and displayed on the screen. However, since the surface of this composite is _one of the basic solids A ₁ , A ₂ , A ₃ , and A ₄ , as shown in FIG. 2, the basic solids A ₁ , A ₂ , A ₃ , and A _{4 are} The solids converted to the screen coordinate system are _designated as A _1S , A _2S , A _3S , and A _4S , respectively, and these converted basic solids may be synthesized by the same synthesis procedure as in FIG.

Basic stereoscopic data converted to screen coordinate system A _1S , A _2S , A _3S , A
_4S is stored in the second graphic memory 5. Screen coordinate system os-x
One of the basic stereoscopic data in syszs (for example, A _1S ) is selected and illustrated in FIG. FIG. 4 (a) is a diagram showing the spatial position of A _1S in the same coordinate system. The vertex coordinates in FIG. 4 (b) are calculated by the following equation.

[X _si y _si z _si w _si ] = [X _i Y _i Z _i 1] ・ M ₁・ M ₅・ M ₇・ M _p However, i = 1,2, ..., 8 ... where M ₁ , M ₅ , M ₇ , M _p are 4 × 4 matrices representing “transform 1”, “transform 5”, “transform 7”, and “projection transform”, respectively, and M ₁ , M ₅ , M ₇ are It has the same shape as a matrix. In the case of parallel projection, M _p has the same form as the matrix in the equation, but in the case of central projection, the fourth column is not [0,0,0,1]. In order to perform the coordinate transformation of the basic solid A ₁ , matrix multiplications are first performed to obtain M _1S = M ₁ · M ₅ · M ₇ · M _p ... And the matrix M _1S is multiplied. In the case of parallel projection, M _1S has the same form as the matrix of the formula, and the result of the formula is w _si
= 1, but w _si = 1 is not established in the case of central projection,
Division by And the values of these quotients need to be changed to x _si , y _si , z _si .

FIG. 4 (c) shows each surface S of the basic solid converted to the screen coordinate system.
data relating to _i , for each surface S _i , in addition to the vertex series,
It has the three primary color intensities R _i , G _i , and B _i and the z _s- direction component n ′ _zi of the outward normal vector. When shading is applied as the value of (R, G, B), a certain hue (r, g, b) is specified for the whole polyhedron, and when the polyhedron is placed in the world coordinate system, it is illuminated from a certain light source. the reflection intensity _{I i} of the light calculated for each surface _{S i} of the polyhedron _{has, R i = r × I i} , G i = g × I i, B i = b × I i
Let be (R _i , G _i , B _i ). This process is performed according to the following procedure. First, [x _wi y _wi z _wi 1] = [X _i Y _i Z _i 1] · M ₁ · M ₅ · M ₇
The coordinates of the basic stereoscopic data are converted to the world coordinate system by. The result is shown in FIG. Since the reflection intensity I _i of each surface S _i of the polyhedron is determined by the cosine of the inclination angle (incident angle) theta _i of the incident direction of the normal to the light standing on the surface, the unit normal of each surface S _i vectors n _i = (N _xi , n _yi , n _zi ) and from this and the unit vector l = (l _x , l _y , l _z ) in the light source direction, I _i = I _o cos θ _i = I _o (l _x n _xi) + l _y n _yi + l _z n _zi )…
Ask for. Here, I _o represents the intensity of the light source, and θ _i represents the incident angle. The surface normal vector is calculated from the coordinate values of the three points above it. For example, as shown in FIG. 5 (a), in order to obtain the outward unit normal vector n ₁ = (n _x1 , n _y1 , n _z1 ) of the surface S ₁ , three counterclockwise vertices V ₁ , V _The calculation is performed as follows using ₂ and V ₃ .

N _X1 = (y _w2 -y _w1 ) (Z _w3 -z _w1 )-(y _w3 -y _w1 ) (Z _w2-
z _w1 ) ... N _y1 = (z _w2 -z _w1 ) (x _w3 -x _w1 )-(z _w3 -z _w1 ) (x _w2-
x _w1 ) ... N _z1 = (x _w2 -x _w1 ) (y _w3 -y _w1 )-(x _w3 -x _w1 ) (y _w2-
y _w1 ) ... The result of the outward normal vector and the reflection intensity of each surface S _i is
It is shown in Figure (c). When θ _i > 180 °, the reflection intensity I _i according to the formula has a negative value, and the surface is the back side of the light source, but the non-negative value −I _i with the sign reversed, illuminates the inner surface of the surface. The reflection intensity in the case is shown. The (R _i , G _i , B _i ) in FIG. 4 (c) is obtained by multiplying the signed reflection intensity I _i thus obtained by (r, g, b) by the equation. Also,
In the case of parallel projection, the normal vector is projected and transformed into the screen coordinate system by the following formula, and [n′xi n′yi n′zi 1] = [nxi nyi nzi 1] · M _p . In this case, if only n ′ _zi is obtained by the equation (1) using the vertex coordinates projected to the screen coordinate system and stored as shown in FIG. 4 (c), the code of n ′ _zi is the basic solid. It shows whether the outer surface is the front or back with respect to the viewpoint. When _n'zi <0, this surface is the front surface because it is the front surface, and when _n'zi > 0, this surface is the rear surface that faces the opposite side and is therefore the rear surface. Call.
With a single polyhedron, only the front face needs to be displayed.
In the G expression polyhedron, the rear surface of the basic solid can be the surface of the composite body like the solid B in FIG. 19 (d). Therefore, it is necessary to display the rear surface of such a basic solid.

Next, basic stereoscopic data A _1S , A _2S , A converted to the screen coordinate system
A method of forming a composite image using _3S and A _4S will be described. In the following explanation, A _1S , A _2S , A _3S , A _4S will be referred to as A ₁ , A ₂ , A
_It is written as ₃ , A _4, and it is assumed that A ₁ , A ₂ , A ₃ , and A ₄ are convex polyhedrons in the screen coordinate system. The screen coordinate system is o-
It is written as xyz.

First, as the simplest case, a method of displaying the sum, difference, and product of _two convex polyhedra A ₁ , A ₂ will be described in order. Figure 6 shows the sum A ₁ ∨
Of A _2, it is a cross-sectional view taken along a horizontal plane (scan plane) y-coordinate contains a certain scan line. The cross sections of the polyhedra A ₁ and A ₂ are convex polygons, and the shaded area is the inside of the polyhedron A ₁ ∨ A ₂ . White circles and black circles in this figure are polyhedron A ₁
And pixels with a depth of one row obtained by scan-converting only the front surface of A ₂ . Since the viewpoint is at the point of negative infinity on the z axis, the pixel of the mark is visible and the mark is invisible. Further, it is clear from FIG. 6 that the rear surfaces of A ₁ and A ₂ are invisible. Therefore, to display A ₁ ∨ A ₂ , first, A ₁
Of the front surface of the image memory 9 and the first z
Write with hidden surface erase to the buffer memory 10,
Next, the same process may be performed on the front surface of A ₂ .

Figure 7 is a cross-sectional view with two convex polyhedrons A _1, A ₂ of the product A ₁ ∧A ₂ scan planes. FIG. 7 (a) shows the pixels on the front surface of A ₁ by a mark and a mark, and among them, the pixels of a mark inside A ₂ are on the front surface of A ₁ ∧ A _2. There is. FIG. 7 (b) shows that, of the front surface of A ₂ , the pixel marked with · is on the front surface of A ₁ ∧ A ₂ . Therefore, to display the composite A ₁ ∧A ₂ is, A ₁ and scan converting the front face of the A _2, FIG. 7 (a), detects the pixel of-sign in (b), of Figure 1 Writing with hidden surface erasing may be performed in the image memory 9 and the first z buffer memory 10. The second z-buffer memory 1 for selecting the marked pixels
1 and the logical operation memory 12 are used.

FIG. 8 shows a procedure for detecting and displaying the inside of A _{2 on} the front surface of A ₁ . First, in step 101, the entire second z buffer memory 11 is filled with the maximum value z _max of the z coordinate.
Next, in step 102, when the front surface of A ₁ is scan-converted to obtain a pixel row (X _i , y _i , z _i ) i = 1,2, ..., (x _{i of} the second z buffer memory 11 ₎ , y _i ) Write z _i at the address. That is, z _i → z _s (x _i , y _i ). Next step 103
The entire logical operation memory 12 is filled with zero. Then, in step 104, the front surface of A ₂ is scan-converted, and the pixel row (x _i , y
_{When i} , z _i ) i = 1,2, ... is obtained, the contents z _s (x _i , y _i ) of the address (x _i , y _i ) of the second z buffer memory 11 are compared with z _i. , _z i _{z s} (x _i, y _i) if satisfied (x _i, y _i) of the logical operation memory 12 address values _{C s} (x _i, y _i) is increased by 1. Then the rear face of the A ₂ and scan converted in step 105, the pixel row _{(x i, y i, z} i) i = 1,2, when give ... a, z _i
If z _s (x _i , y _i ) is satisfied, C _s (x _i , y _i ) is decreased by 1. As a result, of the pixels on the front surface of A ₁ , only those that are behind the front surface of A _{2 and} in front of the back surface of A ₂ have a value of C _s = 1 and the other pixels are C _s = 0
Becomes That is, the pixel marked with a mark in FIG. 7 has C _s = 1. Therefore, in step 106, the front surface of the polyhedron A ₁ is scan-converted again, and the pixel array (x _i , y _i ,
z _i , R _i , G _i , B _i ) i = 1,2, ... When C _s (x _i , y _i ) =
If 1 and z _i <z _M (x _i , y _i ), then z _i → z _M (x _i ,
y _i ), R _i → R _M (x _i , y _i ), G _i → G _M (x _i , y _i ), B
_i → B _M (x _i , y _i ) is written. As a result, A ₁
The inside of A ₂ and the boundary portion of the front surface of A are written in the image memory 9 and the first z-buffer memory 10 with hidden surface removal. Hereinafter, memory writing accompanied by such hidden surface erasure will be simply referred to as “display”.

Next, of the front surface of A ₂ , the inside of A ₁ is detected and displayed. The procedure is such that A ₁ and A ₂ are exchanged in FIG. As described above, the polyhedron A ₁ ∧A ₂ is displayed.

FIG. 9 shows a cross section on the scanning plane of the difference A ₁ -A ₂ between the _two convex bodies A ₁ and A ₂ . The figure (a) shows that the pixels / marks outside the A ₂ of the front surface of the A ₁ are the front surface of the A ₁ -A ₂ , and the figure (b) shows the rear surface of the A ₂ It is shown that the pixel / mark inside A ₁ is the front surface of A ₁ -A ₂ . The procedure for displaying the outside of A _{2 on} the front surface of A ₁ is C _s = 0 and z _{i in} step 106 of FIG.
<Z _M , z _i , R _i , G _i , and B _i may be written.
The method of displaying the inside of A _{1 on} the rear surface of A ₂ is similar. In this case, the inner surface of the _{A 2} is in the outer surface of the _A 1 -A _2.

The following precautions must be taken to determine the values of the three primary color intensities R _i , G _i , and B _{i on} the surface of the composite. The values of (R _i , G _i , B _i ) shown in FIG. 4 (c) indicate the intensity of the three primary colors with respect to the outer surface of the basic solid body with a sign. Therefore, when displaying the outer surface of the basic solid body, is set to _{(R i, G i, B} i) it if the value is non-negative, _{(R i, G i, B} i) if is negative (0,0,0). Further, when displaying the inner surface of the primitive as A ₂ in A ₁ -A _{2 is, (R i, G i,} B i) codes inverted (-R _i of, -G _i, -B _i ), if these values are non-negative, set them as they are, and if they are negative, set them to (0,0,0). However, with this method, the surface facing down from the light source is displayed in black level, so avoid this by the following method. Scattered reflection intensity I _o co due to the direct light I _o from the light source
A constant ambient light intensity I ′ _o is added to sθ _i , and I ₁ = I _o cos θ _i + I ′ _o ... Multiplying the hue (r, g, b) of the polyhedron by I ′ _o R ′ _o = r × I ′ _o , G ′ _o = g × I ′ _o , B ′ _o = b
× I ′ _o ... Is added to the non-negative intensities (R _i , G _i , B _i ) obtained as described above, and (R _i + R ′ _o , G _i + G ′ _o , B _i + B ′ _o ) is surrounded. It is written in the image memory 9 as the intensity of the three primary colors to which light is added. Generally, whether to display the outer surface or the inner surface of each basic solid that is a component of the composite body depends on whether the basic solid has an inversion symbol when the CSG tree is converted into the coordinate system as described later. Since it can be determined, the above calculation of the three primary color intensities of each surface is executed immediately after the coordinate conversion, and the result is stored in the second graphic memory 5 as (R _i , G _i , B _i ) in FIG. 4 (c). do it.

Next, a method of displaying a composite body of the _three convex polyhedrons A ₁ , A ₂ , and A ₃ will be described using various composite expressions. Figure 10 (a) shows A ₁ ∨ A ₂
∨A shows a section along the scanning plane ₃ may be displayed by sequentially scanning converting the outer surface of A _1, A _2, A ₃ to display it. FIG. 10 (b) shows a cross section of A ₁ ∧A ₂ ∧A ₃ , which can be displayed by displaying the inside of A ₂ ∧A _{3 on} the outer surface of A ₁ and the A ₃ ∧A on the outer surface of A _{2. 1} inside, A ₁ ∧ on the outside of A ₃
The inside of A ₂ may be displayed in order. This operation is expressed by the following equation.

A ₁ ∧A ₂ ∧A ₃ = A ₁ ⊆ (A ₂ ∧A ₃ ) + A ₂ ⊆ (A ₁ ∧A ₃ ) + A ₃ ⊆ (A
₁ ∧A ₂₎ ... wherein the _{A 1 ⊆ (A 2 ∧A 3} ) is _{A 2} ∧ of the outer surface of _{A 1}
The inside of A ₃ is shown, and the + sign indicates that the terms connected by this should be sequentially displayed. A ₁ ⊆
FIG. 11 shows a procedure for obtaining (A ₂ ∧A ₃ ) using the second z buffer memory 11 and the logical operation memory 12.
In the following description, one word for one pixel of the logical operation memory 12 is 16 bits, and as shown in FIG. 12, C _s , C _s1 , C
_The one classified into _s2 , ..., C _s8 is used. First, the front surface of the polyhedron A ₁ is drawn on the stage 201, and its depth is written in z _s . The front surface and the rear surface of A ₂ are drawn on the stage 202, it is determined whether each pixel of A ₁ is inside or outside A ₂ , and the result is written in C _s1 . Stage 203
Draw the front and back surfaces of A ₃ , and let each pixel of A ₁ be A ₃
Whether it is inside or outside, and the result is C _s2
Write in. In the stage 204, a logical operation of C _s1 ∧ C _s2 → C _s is executed for each pixel to detect a pixel inside A ₂ ∧ A ₃ . R, G, B, z in front of A _{1 on} stage 205
And display only the pixel of C _s = 1. Displaying in a similar manner for the A _2, A _3.

FIG. 10 (c) shows a cross section of (A ₁ ∧A ₂ ) -A ₃ . Internal _{A 2} ∧ ₃ of the outer surface of the _{A 1} to see this, _{A 1} ∧ ₃ inside the outer surface of the _{A 2,} may be displayed _{A 1} ∧A ₂ inside the inner surface of the _{A 3} in order. This operation is expressed by the following equation.

(A ₁ ∧ A ₂ ) −A ₃ = A ₁ ⊆ (A ₂ ∧ ₃ ) + A ₂ ⊆ (A ₁ ∧ ₃ ) + ₃ ⊆
_{(A 1} ∧A ₂₎ ... wherein the _{A 1 ⊆ (A 2 ∧ 3} ) 3 in the polyhedron _{A 3}
Shows the external _{region, 3} in ₃ ⊆ _{(A 1} ∧A ₂₎ shows the inner surface of the polyhedron _{A 3.} To display the inner surface, only the rear surface should be displayed. A ₁ ⊆ (A ₂
The procedure for obtaining ∧ ₃ ) by using z _s and C _s is that the stage 204 in FIG. 11 is changed to C _s1 ∧ _s2 → C _s .

The composites of FIGS. 10 (d), (e), (f), (g), and (h) are displayed by the following operations.

A ₁ -A ₂ ) -A ₃ = A ₁ ∧ ₂ ∧ ₃ = A ₁ ⊆ ( ₂ ∧ ₃ ) + ₂ ⊆ (A ₁
∧ ₃ ) + ₃ ⊆ (A ₁ ∧ ₃ ) …… A ₁ ∨ A ₂ ) ∧ A ₃ = A ₁ ⊆A ₃ + A ₂ ⊆A ₃ + A ₃ ⊆
(A ₁ ∨A ₂ ) ... (A ₁ ∧A ₂ ) ∨A ₃ = A ₁ ⊆A ₂ + A ₂ ⊆A ₁ + A _{3
...... (A 1 ∨A 2) -A} 3 = A 1 ⊆ 3 + A 2 ⊆ 3 + 3
_{⊆ (A 1 ∨A 2) ......} A 1 - (A 2 -A 3) = A 1 ∧ 2 ∨A 3) = A 1 ⊆ (2 ∨A 3) + 2 ⊆A
₁ + A ₃ ⊆A ₁ ... The thick lines in Fig. 10 (b) to (h) indicate the boundary surface of the basic solid to be displayed by the formula ~, and the front surface and the rear surface are not distinguished.

Next, a method for displaying the four CSG trees of polyhedra will be described with an example. FIG. 13 (a) shows four convex polyhedrons A ₁ ,
The CSG tree of the composite body F by the logical formula F = (A ₁ ∨A ₂ ) − (A ₃ ∧A ₄ ) ... Of A ₂ , A ₃ , and A ₄ is shown. The display process consists of the following three steps.

(1) Conversion of CSG tree to standard form (2) Creation of inversion table, function table, interference table (3) Sequential display process of basic solids In these, the processes of (1) and (2) are for each basic solid It may be executed before the coordinate conversion of.

The result of converting the CSG tree of FIG. 13 (a) to the standard form is shown in FIG. 13 (b). This is a CSG tree obtained by converting the logical expression of the expression into a form that does not include the difference operation as in the following expression.

F = (A ₁ ∨A ₂ ) ∧ ( ₃ ∨ ₄ ) ... FIG. 14 shows the conversion method to the standard form. First, all difference operations in the CSG tree are decomposed into product operations and inversion operations as shown in FIG. Next, the inversion operation symbol generated thereby is moved to the basic solid along the tree. Fig. 14
As shown in (b) and (c), if you encounter sums and products in the Tory's clause, you can move by branching by changing the sum to the product and the product to the sum according to Domorgan's law. Fig. 14 (d)
If another inversion operation is encountered on the branch of the tree as shown in, the cancellation is performed. Finally, as shown in FIG. 14 (e), the basic solid A _i with the inversion operator is represented by using the inversion symbol _i .

Using the standard CSG tree of Fig. 13 (b),
FIG. 15 shows the result of creating the function table and the interference table. First
The inversion table in Fig. 5 (a) shows inversion = 1, non-inversion = for each basic solid.
The distinction of 0 is shown. The function table of FIG. 15 (b) is an expression or an expanded expression of the expression as a truth table. FIG. 16 is a diagram showing this function table, in which the 4-bit code of A ₄ A ₃ A ₂ A ₁ is entered in each area divided by the inclusion relation of A _{1 to} A ₄ and F is The true area is shaded. From this figure, the operation of displaying the composite F is represented by the following equation.

F = A ₁ ⊆ ( ₃ ∨ ₄ ) + A ₂ ⊆ ( ₃ ∨ ₄ ) + ₃ ⊆ (A ₁ ∨A ₂ ) +
₄ ⊆ (A ₁ ∨ A ₂ ) ... That is, ₃ ∨ ₄ inside of the outer surface of A _{1 and} of the outer surface of A ₂ .
₃ ∨ ₄ inside, _{A 1} ∨A ₂ inside the inner surface of the _{A 3,} may be _{A 1} ∨A ₂ inside the sequential display of the inner surface of the _{A 4.} The thick line in FIG. 16 indicates the boundary portion of the basic solid to be displayed according to the formula. In the formula, A ₁ and A ₂ do not require mutual interference because A ₁ and A ₂ are connected by the sum operation ∨ in FIG. 13 (b), and the relationship between A ₃ and A ₄ is also It is the same. A table showing the mutual interference between such basic solids is an interference table, and the results are shown in FIG. 15 (c). To create this,
Create a matrix with 0 diagonal elements and 1 off-diagonal elements
In the CSG tree of (b), proceeding from A ₁ to F, and when encountering a sum operation node, write 0 to the corresponding element of the matrix so that the relationship with all A _i belonging to the other party of the sum does not interfere. . This is also done for A ₂ , A ₃ , and A ₄ .

FIG. 17 shows a procedure for sequentially displaying basic solids using the three tables in FIG. This is an extension of the display procedure of the CSG tree of three polyhedra to the case of four polyhedra. In steps 303 and 317, either the front surface or the rear surface of A _i is scan-converted by referring to the inversion table of FIG. 15 (a). In step 309, the interference table of FIG. 15 (c) is referred to, and if the value is 0, the interference process of A _i and A _j is omitted. At step 316, C _s1 ,
The logical operation of C _s2 , C _s3 , C _s4 is performed,
The function table of FIG. (B) is stored in the memory updater 8, and A
This table is indexed as ₁ = C _s1 , A ₂ = C _s2 , A ₃ = C _s3 , A ₄ = C _s4 , the value of F is calculated, and it is sufficient to write in C _s . By using C _{s1 to} C _{s8 in} FIG. 12, it is possible to display a composite body composed of up to eight basic solids by the processing procedure described above. For example, in the case of a composite body consisting of 8 basic solids, conversion of CSG tree to standard form,
After creating the inversion table, the function table, and the interference table, in FIG. 17, change “fill C _{s1 to} C _s4 with 1” described in step 305 to “fill C _{s1 to} C _s8 with 1”, In step 307, “fill C _{s1 to} C _s4 with 0” described in “C _s1 to
C _s8 is _filled with 0 ”,“ j = 4 ”described in step 314 is changed to“ j = 8 ”, and“ j = 4 ”described in step 318 is changed to“ j = 8 ”. , Step 316
_May be changed so that the value of the logical expression of the composite field given using C _{s1 to} C _s8 is obtained and the result is Cs.

(Effects of the Invention) As described above in detail, by using the three-dimensional image display device according to the present invention, it is possible to directly display without converting from the CSG representation to the boundary representation, and the intersection between the polyhedra can be displayed. It eliminates the need for a large amount of complicated processing for explicit calculation. Since the display processing of the CSG polyhedron by the device of the present invention can be realized by using a high-speed arithmetic device equipped with conventional hardware such as a coordinate converter and a polygonal scan converter, or a memory expansion means, Speeding up is possible. Therefore, the present invention is suitable for interactively verifying a CSG expression model which a user of a solid modeling system repeatedly sets through trial and error through a display. Further, according to the present invention, when the desired shape is obtained, the host processor or the like may take another time to convert it into the boundary representation,
A boundary expression polyhedron can also be displayed at high speed by the conventional processing procedure.

[Brief description of drawings]

FIG. 1 is a block diagram showing a configuration of a three-dimensional image display device according to the present invention, FIG. 2 is a diagram showing a modified CSG tree,
FIG. 3 is an explanatory diagram of a definition method of a basic solid, FIG. 4 is an explanatory diagram of basic stereoscopic data converted into a screen coordinate system, and FIG. 5 is an explanatory diagram of basic stereoscopic data converted into a world coordinate system. 6 is a cross-sectional view of the sum of polyhedra, FIG. 7 is a cross-sectional view of the product of polyhedra, FIG. 8 is a flowchart showing a display processing procedure of the product of polyhedra, FIG. 9 is a cross-sectional view of the difference of polyhedra, and FIG. Is a cross-sectional view showing a CSG operation of three polyhedra, FIG. 11 is a flowchart showing a display processing procedure of a CSG tree of three polyhedra, and FIG. 12 is a view showing a division of a logical operation memory.
FIG. 14 is a diagram showing an example of a CSG tree of four polyhedra, FIG. 14 is an explanatory diagram of a conversion method of the CSG tree to a standard form, FIG. 15 is a diagram showing a table used for displaying the CSG tree, and FIG.
FIG. 17 is a diagram showing the inclusion relationship of basic solids, FIG. 17 is a flow chart showing the display processing procedure of four basic solid CSG trees, and FIG. 18 is a block diagram showing the configuration of a conventional 3D image display device. FIG. 19 is an explanatory diagram of a conventional polyhedral model creating method, and FIG. 20 is an explanatory diagram of a basic solid synthesizing method. 1 ... Host processor, 2 ... Host interface, 3 ... Control processor, 4 ... First graphic memory, 5 ... Second graphic memory, 6 ... Coordinate converter, 7 ... Scan converter, 8 ... Memory updater, 9 ... Image memory, 10 ... First z-buffer memory, 11 ... Second z-buffer memory, 12 ... Logical operation memory.

Claims (1)

[Claims] 1. A first graphic memory for storing CSG expression data of a polyhedron and basic stereoscopic data which is a component thereof, and coordinate conversion and projection conversion for the basic stereoscopic data according to the CSG expression and viewpoint information. A coordinate converter for applying, a second graphic memory for storing the converted basic stereoscopic data, a scan converter for scanning and converting a polygon surrounding the basic solid to decompose it into pixel data having three primary color intensities and depths, and a screen. An image memory for storing the three primary color intensities of the three-dimensional image for each pixel, a first z-buffer memory for temporarily storing the depth for each pixel, and a front surface or a rear surface of only one of the basic solids in the CSG representation. A second z-buffer memory that temporarily stores only the depths of the constituent pixels when the surface is scanned and converted, and a second z-buffer memory for each of the constituent pixels on the front surface or the rear surface of the basic solid. A logical operation memory that determines whether the object is inside or outside of the solid and stores the result, and an operation that writes the pixel data with the depth to the image memory and the first z buffer memory while erasing the hidden surface. A z-buffer memory and a memory updater for controlling a logical operation memory are provided, and the memory updater includes: (a) an inversion table for each basic solid created by converting the CSG representation of the polyhedron, and interference between basic solids. A table, a function table of CSG logical expressions, (b) previously filling the image memory with a background color and the first z-buffer memory with a maximum depth value, and (c) one particular basis that constitutes the CSG representation. According to the value of the inversion table, the solid is scan-converted on either the front surface or the rear surface, the depth distribution is created in the second z buffer memory, and (d) the front surface is scan-converted by the processing of (c). If you do the logic If the inside / outside determination result portion of the arithmetic memory is filled with 1 and the rear surface is scan-converted in the process of (c), the inside / outside determination result portion of the logical operation memory is filled with 0, and (e) according to the value of the interference table, Scan-convert the front surface and the rear surface of each of the other basic solids that interfere with the basic solid, and (f) whether the depth stored in the second z-buffer memory is between the front surface and the rear surface. Whether or not it is determined for each pixel by using the determination counter of the logical operation memory, the determination result is written in the internal / external determination result part of the logical operation memory, and (g) the function table is obtained using the value of the combination of the internal and external determination results. The function value of is determined for each pixel, and it is discriminated into a visible pixel having a function value of 1 and an invisible pixel having a function value of 0, and (h) the front surface or the rear surface of the specific basic solid is scan-converted again to obtain the three primary color intensities. And the depth is obtained, and the function value is 1 A portion of the surface of the particular elementary solid by updating the values of the first z-buffer memory and the image memory when the depth is less than the depth of the corresponding pixel of the first z-buffer memory for Is displayed, and (i) the processes of (c) to (h) are sequentially performed for all basic solids represented by CSG to display a three-dimensional image of a polyhedron represented by CSG. Display device.