JP2000099761A - Graphics processing apparatus and method - Google Patents

Abstract

(57) [Problem] To provide a 3D graphics processing device capable of obtaining a sufficient 3D display speed and quality even in a system with a small amount of hardware such as personal information equipment. According to the present invention, based on system capabilities and user settings, 3
Provided is an interface capable of selecting the degree of detail of an individual model of D graphics and an apparatus therefor. In addition, the present invention proposes a method and a system configuration for enabling beautiful display even in a system with few displayable colors or a system without resources such as a Z buffer.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a 3D graphics display technology for displaying 3D (three-dimensional) graphics, and more particularly, to a high-speed display of 3D graphics in a system with a small amount of hardware such as a personal information device. And a 3D graphics processing apparatus and method for processing with sufficient quality.

[0002]

2. Description of the Related Art In a system for displaying 3D graphics, an application does not use hardware directly but introduces an intermediate software layer (hereinafter referred to as middleware) between hardware and an application program. In addition, application development costs can be reduced and hardware can be easily changed.

[0003] In such a flow, not only a conventional graphics workstation (GWS) but also a personal computer (PC) and a personal information device in real time 3
The demand for D display is increasing, and it is desirable that common contents can be displayed at high speed on devices of different levels.

[0004] Level of detail is used to display common contents at high speed on devices having different levels.
(LOD) and polygon reduction. LOD is described in, for example, the document “VRML2.0 SOURCEBOOK p.499-p.
As described in “508”, 3D models of different degrees of detail (for example, the number of polygons) are prepared for the same object, and the model displayed according to the distance in the z direction during execution is unnecessary. This technology avoids high-definition display and enables high-speed display.

[0005] Polygon reduction is set by a user in order to display a high-resolution model simply and at high speed, as described in the document "SoftImage / 3D Modeling pp. 317 to 346". This technology reduces the number of polygons according to rules. It is also used to automatically generate models of different levels of detail for LOD.
For an algorithm that continuously reduces the number of polygons,
For example, there is an SRA (Successive Relaxation Algorithm) described in “Nikkei CG August Issue p. 174”.

There is also a method of using an index color mode so that common contents can be displayed at high speed on machines of different levels. For example, the document "X
-Pseud described in "Window Ver.11 Programming (Ryoichi Kinoshita, Nikkan Kogyo Shimbun) p.242-243"
o Color is equivalent to the index color here. By preparing a color map, which is a correspondence table between indexes and actual colors, in hardware, it is possible to display relatively beautiful 2D images with a small number of colors.

[0007] The luminance calculation result in 3D display usually represents the luminosity of red, blue and green as a decimal number between 0 and 1, and the result is converted into an appropriate index.
It is necessary to prepare a color map that can be properly converted. As an easy way to achieve this, for example, as described in “OpenGL Programming Guide Japanese Edition Addison Wesley, pp. 192 to 194”, the color map is fixed to a format that easily reflects the luminance calculation results. There is a way to do that.

[0008] As a graphics processing technique, there is a technique called a hidden surface elimination method. This hidden surface elimination method
This is a technique for displaying two figures with overlap. As the hidden surface elimination method, there are a Z sort method and a tile division method.
These are described in the document “Interface, Dec. 1997”, p.
p.114 ". First, the Z-buffer method is currently the most widely used method, and can perform hidden pixel erasing on a pixel-by-pixel basis, but requires a memory proportional to the area of the display area, and increases the bus transfer speed between the memory and the graphics processor. Easy to become a bottleneck. Next, Z
The sorting method is a method that has been often used in the past, and requires less memory and is simple.
Two adjacent faces may not be processed correctly.
The tile division method is a hidden surface elimination method that compensates for these disadvantages.
Since the screen is divided into small areas and the Z buffer for each small area is used for each, the required memory is constant and the hidden surface can be erased in pixel units. However, there is a possibility that the rearrangement processing of the planes in the small area division may become an overhead, and the computing power of the system becomes important.

At present, it is practical to use the Z-sort method in personal information devices with severe restrictions on the amount of hardware. However, with the development of technology in the future, the Z-buffer method, the tile division method, and other hidden methods will be used. It is thought that the number of cases where the surface elimination method is adopted will increase.

[0010] In addition, it is necessary to devise a method for increasing the speed of the display algorithm.

It is necessary to speed up the clipping at the boundary of the display area of the surface. A basic algorithm of clipping is to calculate an intersection of a display area and a surface, determine a region, and deform the surface. In order to increase the speed by omitting the intersection calculation and area determination, consider a virtual area larger than the display area, and use the rendering hardware as an interface to draw fast, so that high-speed clipping by rendering hardware is possible. It can be carried out. However, the size of the virtual area has hardware limitations.

[0012]

Conventionally, with respect to the above LOD and polygon reduction, according to the displayable resolution and drawing / display speed of the 3D graphics processing apparatus,
There is no interface between the 3D graphics processing device and the external input / output device or the 3D graphics development environment that changes the degree of detail of the 3D graphics.

In view of the above, the present invention provides an interface for selecting the level of detail of each model of 3D graphics based on system capabilities and user settings.
A first object is to provide a configuration of a device using this interface.

Conventionally, since the number of colors is not considered in 3D data, there is a problem that the number of colors becomes insufficient in the luminance calculation in the index color mode. For this reason, the brightness calculation result in 3D cannot be displayed correctly, and it is necessary to fix the color map and arrange the brightness in order, so as to approach the correct display.

That is, there is a problem that the color map cannot be freely determined.

In view of the above, the present invention provides a method and an apparatus for displaying 3D data which does not consider the color number limitation, as correctly as possible, even in an index color mode having a free color map. As a second object.

Conventionally, a specific method (for example, the Z-buffer method) has been assumed as the hidden surface elimination method, and thus there has been a problem that the structure of 3D data cannot be displayed well by another method (for example, the Z-sort method).

It is a third object of the present invention to provide a method and an apparatus for converting a 3D graphics processing apparatus into a model suitable for a hidden surface elimination method.

Conventionally, if the clipping of a rectangle protruding outside the display area is accurately performed by using the intersection calculation, there has been a problem that the speed cannot be increased using the simple rectangle drawing function of the hardware.

Accordingly, it is a fourth object of the present invention to provide a method and an apparatus for drawing a clipped rectangle at high speed by dividing a rectangle and using a rectangle drawing function of hardware. .

[0021]

The object of the present invention is to generate a plurality of types of display data having different data structures for one display data, a plurality of types of display data having different data structures, and a type of display data. Device, and a plurality of types of display data and types of display data having different data structures output from the external device, and the coarseness of the data to be displayed determined by the drawing process and the display data This can be achieved by a processing device that selects data to be displayed from a plurality of types of display data having different data structures, and a display device that displays the display data selected by the processing device.

Further, the object is to provide an external device for outputting display data, a CPU, and a graphics processor for performing a drawing process on the display data output from the external device in accordance with a command from the CPU. This can be achieved by a processing device that generates a color conversion table from an index color table that corresponds to the above, and a display device that displays display data selected by the processing device.

[0023] The above object is also achieved by a processing device having an external device for outputting display data, a CPU, and a graphics processor for performing a drawing process on the display data output from the external device in accordance with a command from the CPU. A display device for displaying the drawn display data, wherein the external device divides the data to be displayed in advance when the request from the processing device is to remove the hidden surface, and displays the divided display data. This can be achieved by outputting data to a processing device.

The above object is also achieved by a processing device having an external device for outputting display data, a CPU, and a graphics processor for performing a drawing process on the display data output from the external device in accordance with a command from the CPU. A display device for displaying the divided display data, wherein the CPU of the processing device divides the data to be displayed when the data to be displayed exceeds the display area, and the graphics processor This can be achieved by performing a drawing process on the data to be displayed.

[0025]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, description will be made with reference to the drawings.

FIG. 1 shows the configuration of a 3D graphics system using the present invention. The three-dimensional graphics system includes a 3D graphics processing device 1, an external input / output device 2, a 3D graphics development environment 3, a user interface device 4, and a display device (CRT) 5.

First, peripheral devices connected to the three-dimensional graphics processing device 1 will be described.

The external input / output device 2 includes a broadcast receiver 10, D
The device is a device such as a VD / CD playback device 11, a WWW server 12, or the like, and inputs or outputs VRML, 3D model data such as 3D terrain information. These are the SCSI cable 20 for the broadcast receiver and the SCSI cable 2 for the playback device.
1. Connect to the 3D graphics processing device 1 using the Internet line 22.

The 3D graphics development environment 3 is a device 13 such as a workstation or a personal computer. The 3D graphics development environment 3 creates 3D model data for the 3D graphics processing device 1 or held in the external input / output device 2 and uses the Internet line 22 or the like. Exchange data with these devices via the.

The user interface device 4 is a device such as a keyboard 14 and a mouse 15, and transmits a user's operation of the device to the 3D graphics processing device 1 through a keyboard cable 23 and a mouse cable 24.

Next, the three-dimensional graphics processing device 1 connected to the external input / output device 2, the three-dimensional graphics development environment 3, the user interface device 4, and the display device 5 will be described.

The 3D graphics processing device 1 has an external interface unit 6, a calculation processing unit 7, and a graphics processing unit 8, and the three-dimensional graphics processing device 1 and the calculation processing unit 7 are connected by an external input / output bus 40. And the calculation processing unit 7
And the graphics processing unit 8 are connected by a system bus 60. Incidentally, the external input / output bus 40 and the system bus 60 are constituted by a plurality of signal lines.
Further, the external interface unit 6 includes a SCSI 30 for a broadcast receiver,
It is composed of a playback device SCSI 31, a 10BaseT 32, a modem controller 33, and a serial I / O 34, and exchanges information with the outside. The calculation processing unit 7 includes a timer 35, a CPU 50, an interrupt controller 51, an external bus interface 52, a main memory 53, and an interrupt control signal line 54, and interprets 3D model data, performs geometric calculation processing,
Processing such as storage of processing results and control of data transmission / reception with the external input / output device 2 are performed. The graphics processor 8 includes a graphics processor 70, a graphics memory bus 71, and a graphics memory 72, and generates an image to be displayed based on graphics information such as the position and color of a graphic.

FIG. 2 shows a detailed configuration of the graphic processing unit 8. As shown in this figure, the graphics processor 70 includes a system bus I / O 701 for inputting and outputting data and the like of the system bus 60, an internal register 703, a memory interface 705 for exchanging data with the graphics memory, A rendering device 706 for generating pixel image data to be displayed in accordance with a drawing command, a display device 707 for performing control for displaying the generated pixel image data on the display device 5, and a display I for outputting image data to the display device 5. /
O709.

The graphics memory 72 includes a display list buffer 721 and a frame buffer 72.
2, a texture buffer 723. The display list buffer 721 stores a drawing / display instruction sequence generated by the CPU 50 and executable by the graphics processor 70. The frame buffer 722 holds the pixel image data generated by the rendering device 706, and the texture buffer 723 stores a texture image used when the rendering device 706 performs a drawing process. The texture is image data to be pasted on the surface of the image represented by the contour. The CPU 50 receives the texture data from the external input / output device 2 or the 3D graphics development environment 3 and passes the texture data through the graphics processor 70. The data is stored in the texture buffer 723. At this time, the CPU 50 stores information such as which part of the texture buffer 723 is stored in the main memory 53 and assigns a texture ID 907 as an identifier to each texture.

The three-dimensional graphics processing system having the above-described configuration is a three-dimensional graphics processing device that converts 3D model data such as VRML and 3D terrain information from the external input / output device 2 and the three-dimensional graphics development environment 3. 1
The 3D graphics processing device 1 processes the 3D model data according to its own processing capacity, and displays an image on a display device.

Next, the operation of processing the 3D model data on the WWW server and displaying an image on the display device 5 by the three-dimensional graphics processing device 1 configured as described above will be described.

FIG. 28 shows an operation performed by the CPU 50 among operations for processing 3D model data on the WWW server and displaying an image on the display device 5.

When the user detects that a URL (Uniform Resource Locator; notation indicating a method of accessing information on the Internet) has been input from the user interface device 4 by the user, the input URL is converted to a serial I / O of the external interface unit 6. Main memory 5 via / O34
3 (1451). Next, 3D model data is fetched from the WWW server 12 of the external input / output device based on the input URL and stored in the main memory 53 (145).
2). Next, 3D processing is performed on the received 3D model data, and the processed result is stored in the main memory 53 (14).
53). Here, 3D processing refers to performing coordinate conversion, luminance calculation, light source calculation, clipping processing, and the like on the model data. Note that programs for these processes are stored in the main memory 53 in advance. A program for performing these processes is described in the document “Computer Graphics <Technical CG Standard Textbook>” (supervised by the Technical CG Standard Textbook Editing Committee, published by the Image Information Education Promotion Association). I have. Next, a drawing and display instruction sequence (hereinafter, referred to as “display list”) executable by the graphic processor is generated and stored in the main memory 53 (1454). Next, the display list stored in the main memory 53 is stored in the graphics processor 70.
(1455). Next, a drawing command is issued to the graphics processor 70 (1456). Finally, a display start command is issued to the graphics processor 70 (1457).

Next, the drawing operation of the graphic processor 70 will be described.

FIG. 29 shows the operation of the graphics processor.

First, when the memory interface 705 is
Receiving the display list sent from U50,
It is stored in the display list buffer 721 (146
1). Next, drawing is performed by the rendering device 706 according to the drawing command sent from the CPU 50 (146).
2). Here, the memory interface 705 is a CPU
The information of the rendering command from 50 is stored in the internal register 703, and the rendering device 706 checks the internal register 703. If the rendering command is stored in the internal register, the rendering command is stored in the display list buffer 721. The display list is read and interpreted, and a drawing process is executed. The image generated by the drawing processing is stored in the frame buffer 722.

Finally, when the CPU 50 issues a display start command, the display is started (1463). Here, the memory interface 705 stores the information of the display start command from the CPU 50 in the internal register 703. The display device 707 checks this internal register 703,
If the display start command has been issued, the image is read from the frame buffer 722 and the CRT display I / O 70
9 to an image signal bus 80.

A configuration for displaying an optimal 3D model according to the capability of the graphics processing device 1 in the three-dimensional graphics system configured as described above will be described. First, the data of the three-dimensional model will be described. Since a polygon can be configured by combining a plurality of triangles, the triangle will be described here.

FIG. 3 shows the structure of the 3D model data. The three-dimensional model data includes the number of vertices 901, the vertex coordinates 902, the number of triangles 903, and the triangles (vertexes constituting the triangle) 9
04, color 905, normal vector 906, texture ID
907 and texture coordinates 908.

Here, vertex coordinates 902 and triangle 904
Represents the shape of a 3D figure. The color 905 defines the color of the surface of the triangle, and the normal vector 9
06 is used for light source calculation. The texture coordinates 908 are used to cut out a part of the texture or to repeatedly paste the texture.

FIG. 7 shows the vertex coordinates 902 when placed at the center coordinates (0, 0, 0) of a 128-triangle donut-shaped figure such as the example 912 of the 3D model in FIG. FIG. 9 shows vertices 904 forming a triangle. 3
The D model data is stored in the main memory 53 in the form of numerical data as shown in FIGS.

The following describes LOD, polygon reduction, color conversion at the time of luminance calculation, hidden surface elimination, and clipping processing in the graphics processing system.
Note that LOD and polygon reduction are executed by the CPU 50, and color conversion, hidden surface elimination, and clipping processing at the time of luminance calculation are executed by a graphics processor.

The LOD is pre-processed on the WWW server of FIG. 1 or on the 3D graphics converter of FIG. 13, and the model is selected by selecting the level of detail in the flowchart of FIG. Polygon reduction is WW in Fig. 1.
It is executed on the W server or the 3D graphics converter of FIG. Pre-processing (division of a surface) is performed on the WWW server in FIG. 1 or the 3D graphics converter in FIG. In the hidden surface erasing process itself, data necessary for generating the display list shown in FIG. 5 is generated and processed by the graphics processor.

The application of the present invention to LOD and display of three-dimensional model data according to the capability of the graphic processing device 1 will be described.

[0050] LOD is to prepare 3D models with different levels of detail (for example, the number of polygons constituting a model) for the same object, and change the model to be displayed according to the distance in the z direction from the viewpoint. Thus, this technology avoids unnecessary high-definition display and enables high-speed display.

In order to realize this, in the present invention, three-dimensional models having different levels of detail are prepared, and the level of detail is obtained from the level of detail of the entire level, the level of detail of the model, and the level of detail determined by the z value. Determine the 3D model to use. here,
The degree of detail corresponds to the number of faces and vertices constituting the three-dimensional model. The most detailed three-dimensional data (original three-dimensional data) is set to 1, and the smaller the number of faces and vertices, the smaller the number of faces and vertices. , Assigned with smaller values. Hereinafter, the overall detail level, the detail level count of the model, the detail level coefficient determined from the z value, and the detail level will be described.

The overall level of detail is determined by the drawing processing capability of the three-dimensional graphics processing device 1 and the required drawing capability of the device storing the three-dimensional model. The rendering processing capability value may be any value as long as it indicates the processing capability of the three-dimensional graphics processing device 1.
Here, what indicates how much a triangle can be drawn in one second is set as a drawing processing capability value. In order to see the performance of the entire 3D graphics system, the area of the triangle drawn here is assumed to be an area proportional to the display area of the display device 5 on average (for example, about 1/100). The CPU 50 has a program for adjusting the drawing capability value by the user through the user interface device 4, so that fine adjustment can be performed.

Similarly, the required drawing capability value of the device storing the three-dimensional model is a value that indicates how much a triangle can be drawn in one second.

From the drawing processing capability value of the three-dimensional graphics processing device 1 thus determined and the required drawing capability value of the device storing the three-dimensional model, the drawing capability value ÷ the required drawing capability value is displayed. Level of detail common to all 3D models to be processed (“the overall level of detail”). Note that the drawing processing capability value of the three-dimensional graphics processing apparatus 1 is stored in the main memory 53 in advance.
To be stored.

Next, the detail level coefficient of the model will be described. The model detail level coefficient is determined, for example, for each application. In a certain application, a model with high importance increases the model detail level coefficient, and a model with low importance decreases the model detail level coefficient. And can be set arbitrarily. The detail level coefficient of this model is the detail level table 915 in FIG.
And sent from the outside together with the three-dimensional data.

Next, the detail level coefficient determined from the Z value will be described. This is a correspondence between the Z value, that is, the distance from the viewpoint and the degree of detail of the model. In other words, as the Z value increases, the distance from the viewpoint increases, so that a three-dimensional model with a small degree of detail is used, and as the Z value decreases, the distance from the viewpoint is short, so a three-dimensional model with a large degree of detail is used. . FIG. 12 shows a configuration for converting the Z value for realizing this into a detail level coefficient. Here, two conversion methods are shown, and in FIG. 12A, the relationship between the Z value and the detail level coefficient is defined by a function f (z).
In FIG. 12B, the relationship between the Z value and the detail level coefficient is defined by a table.

The data of the 3D models having different degrees of detail are used to obtain the detail level coefficient from the coordinates 914 of the representative points of the model shown in FIG. 4 and the detail level table 915 in addition to each 3D model, and the z value described above. Consists of functions or tables. Here, the model representative point 914 is used to calculate the distance from the viewpoint, and is determined by, for example, calculating the center of gravity when the model is created. In addition, the detail level table 9
15 is composed of a model name 9151 and a degree of detail 9153 determined by the number of triangular faces. Incidentally, instead of the number of faces of the triangle, other parameters such as the number of vertices may be used.

Next, a method of selecting one three-dimensional model from a plurality of three-dimensional models having different levels of detail according to the overall level of detail and the level of detail from the viewpoint of the 3D model will be described. FIG. 6 shows a flowchart for performing this.

First, coordinate transformation of a representative point of the model is performed to obtain a z-coordinate value representing a distance from the viewpoint (921).
1). Next, a detail coefficient determined from the z value is calculated (9
212). Next, the detail level used for selecting the model is calculated from “detail level = the overall detail level × the detail level coefficient of the model × the detail level coefficient determined from the z value” (9213). A model is selected from the detail level and the detail level table 915 shown in FIG. 4 (9214).

FIG. 5 shows a flowchart of a process in the case where the method of determining a three-dimensional model from the overall degree of detail and the degree of detail based on the distance from the viewpoint of the 3D model is applied to LOD. This flowchart is executed by the CPU 5
Performed by 0.

First, one model is selected from 3D models having different levels of detail according to the overall level of detail shown in FIG. 6 and the level of detail of the three-dimensional model from the viewpoint (92).
1). Next, coordinate transformation 922 of the vertex coordinates of the 3D model is performed, luminance calculation using normal vectors (923), clipping of figures outside the area (924), and generation of a display list from drawing figure information (925). Do.

Next, polygon reduction for reducing the number of polygons of a high-definition model and displaying at high speed according to the present invention will be described.

FIG. 30 shows a flowchart of the vertex deletion for performing the polygon reduction according to the present invention. First, a connectable vertex i ′ corresponding to the vertex number i is obtained (1471). Next, a triangle including the vertex i is extracted (1472). And the vertex number i of the extracted triangle
Is replaced with i ′ (1473). Lastly, triangles with overlapping vertices are deleted (1474). This process will be specifically described using Torus1 in FIG. 4 as an example.

This Torus1 is composed of 64 vertices v0 to v63.
This is a donut-shaped 3D model composed of a plurality of vertices and 128 triangles f0 to f127. Specifically, the vertex coordinates are as shown in FIG. 7 and the triangle vertex numbers are as shown in FIG.

In order to satisfy the condition that the 3D model is composed of triangles, the vertices to be deleted are connected to neighboring vertices. Here, it is assumed that v31 has been selected as the connectable vertex of v63. In this example, when v63 is selected as the deleted vertex (vertex number i), the triangles f126 (v0, v35, v63), f63 are selected as shown in FIG.
125 (v35, v31, v63), f108 (v31,
v27, v63), f109 (v27, v59, v6
3), f110 (v59, v28, v63), f127
Six triangles (v28, v0, v63) are targeted.
Here, by replacing v63 with v31 and deleting triangles with overlapping vertices, as shown in FIG.
Triangle F126 (v0, v35, v31), F109
(v27, v59, v31), F110 (v59, v2)
8, v31), 4 of F127 (v28, v0, v31)
One is reduced.

In consideration of such a vertex deletion algorithm, the data structure of a 3D model that can be dynamically polygon-reduced is as follows: the number of vertices 901, the number of vertices 902, the number of triangles 903, and the vertices (constituting vertices) 904 in FIG. , Color 9
05, a normal vector 906, a texture ID 907, and a texture coordinate 908, in addition to a 3D model detail coefficient 909, a connectable vertex 910, and a triangle list 911 including the vertex.

The detail level coefficient 909 indicates the degree of importance for each 3D model. In the present algorithm, the value of the original 3D model is set to 1, and 3D generated by polygon reduction is set.
The detail coefficient of the D model data is calculated by “detail coefficient = number of triangles ÷ number of triangles of original 3D model”. The connectable vertices 910 are a list indicating the order in which vertices are deleted and to which vertices they are connected. A list 911 of triangles including vertices is an inverse conversion table of the triangle 904 in FIG. There is no problem in this as well as the amount generated at the time of executing polygon reduction which is a preprocessing stage. It can be easily generated when executing the polygon reduction algorithm. Hereinafter, the connectable vertex 910 and the triangle list 911 including the vertex are collectively referred to as a vertex list.

Hereinafter, an algorithm for generating a model having a desired number of faces will be described with reference to the 3D model of FIG.

Assume that Torus2 is obtained from Torus1 in FIG. 4 as a result of polygon reduction on the 3D graphics development environment 3 or on the external input / output device 2. These vertex coordinates are a subset of the vertex coordinates of Torus1 because the vertex deletion algorithm is applied. Specifically, the vertex numbers 0 to 31 in FIG. 7 correspond to the vertex coordinates of Torus2. At this time, the vertex list is as shown in FIG.

FIG. 31 shows a flowchart of polygon reduction using vertex deletion. First, a vertex to be deleted is extracted from the vertex list (1481), and vertex deletion (vertex deletion by a connectable vertex) is applied to this vertex. As a result, when the number of triangles in the model data becomes equal to or less than the required number of triangles determined from the level of detail, the algorithm ends. Go back to the beginning if you need further reduction.

In the example shown in FIG. 8, the vertices to be deleted are arranged in the direction in which the vertices are reduced from the vertex number 63. Therefore, by using the above-described vertex deletion algorithm in this direction, the vertices do not completely match, but almost the desired vertices are obtained. A model of the number of faces is obtained. Unlike a general polygon reduction algorithm, since the vertices to be deleted are determined in the pre-processing, it can be executed in a relatively short time.

If this algorithm is used, a model having an arbitrary number of planes can be generated in principle if the data shown in FIG. However, it takes a very long time to generate a model having a small number of vertices from a model having a very large number of vertices. Therefore, a plurality of model data having a low level of detail other than the level of detail 1 are prepared.

By passing the information of the degree of detail from the 3D graphics processing apparatus 1 to the external input / output device 2, the information of the detail corresponding to the drawing capability is passed to the external The 3D graphics processing apparatus 1 can obtain 3D model data having a desired level of detail by selecting model data having a required level of detail from among the above and applying the present polygon reduction algorithm to the model data.

Next, the color conversion at the time of calculating the luminance according to the present invention will be described.

First, the handling of colors in the 3D graphics processing device 1 will be described. As a method of storing colors in the graphics memory 72, the direct color method, which is a format for directly storing the luminous intensity values of red, blue, and green, and data of the number of colors that can be simultaneously developed are prepared and indexed. There is an index color system to add. In the present system, the internal register 703 of FIG. 2 holds a color map which is a correspondence table between the index and the actual color, and the display device 707 converts the index into the actual color, thereby realizing the index color system. I have. The luminance calculation in the 3D display is performed using the luminous intensity of each of the three primary colors of light, red, blue, and green, using a decimal value between 0 and 1. This system has a mode for displaying an 8-bit index color. This is achieved by storing an 8-bit index color table 1200 (corresponding to a color map) in FIG.
The index color method is implemented. In this method, it is necessary to convert the result into an appropriate index and prepare a color map that can convert the result properly. In many cases, it is necessary to devise a method according to the application.

For example, for an 8-bit index color, it is easy to assign red, blue, and green at a ratio of 3 bits, 3 bits, and 2 bits, but it is not very effective because the color change is extreme.

As another example of easily converting a luminance calculation result into an index, there is a method of fixing a color map to a format in which the luminance calculation result is easily reflected (see “OpenGL P
rogramming Guide Japanese Edition ”, published by Addison Wesley, pages 192 to 194. However, care must be taken when using this method because the range of colors that can be expressed is narrow.

The index color conversion of the luminance calculation result in the present system provides a method using a color conversion table and a method using a system color area in addition to the above method.

First, a method using a color conversion table will be described. The color conversion table 12 of FIG.
10 and the data of this color conversion table is created in advance before displaying the 3D model, so that a color map having a high degree of freedom can be used for the luminance calculation result, and high-speed processing can be performed. It becomes possible. The disadvantage of this method is that
Although the luminance calculation result reflects only the luminance information without using the information on the color of the light source, for example, in an application such as a three-dimensional map display, the color of the surface itself is more important than the color of the light source. This algorithm is effective for various applications. Hereinafter, a method of generating data of the color conversion table 1210 and a method of calculating luminance using the table will be described.

Referring to FIG. 20, color conversion table creation 12
30 algorithms will be described. The input is a luminance gradation stage L1220 and an 8-bit index color table 120.
0. This 8-bit index color table is represented by arrays R [256], G [256], and B [256]. The operation will be described below in order. The counter i of the row (corresponding to the index in FIG. 19) is initialized to 0, 1231,
A counter j of the column (corresponding to the luminance gradation value 1211) is initialized to 0 (1232). Next, an RGB value Rij, Gij, Bij is calculated for the index i based on the luminance gradation value j 1233. Here at the same time, dcmin to use later
And index have been initialized. The parts for searching for the closest color of (Rij, Gij, Bij) are 1234, 1235, 124
1, 1242, and 1243. K is 256 at 1243
Then, since the index of the closest color is obtained in the index, this is stored in table [i] [j], and 1 is added to j 1244. The process returns to 1233 by the number of times of the luminance gradation stage L1220 for the column, and the color conversion table 1210 corresponding to the index i is created. Further, this operation is performed 256 times.
1246, 1247 repeated times. Thus, a color conversion table 1210 is obtained.

How the color conversion table 1210 is used in the 3D graphics processing device 1 will be described with reference to FIG.

The calculation of the luminance index color by the color conversion table is performed by using the luminance gradation 112 obtained as a result of the luminance calculation.
21, a base index color 1222 representing an index color displayed when the luminance is 0.5, and a color conversion table 1210.

The luminance gradation stage L 1220 is determined from the color conversion table 1210.

The algorithm multiplies the luminance gradation 1121 by the luminance gradation stage 1251 and converts the result into an integer 125.
2. This value is clipped from 0 to (L-1), 1253, and the clipped value is set as a column, base index color 1222.
Is used as a row, and the luminance index color li 1223 as an output is obtained by referring to the color conversion table 1210. Next, a method using a system use area will be described.
In the index color method, it is necessary to prepare an index color area (system use area) that can be freely used by the present system in order to correctly reflect information on colors other than luminance as a luminance calculation result. On the contrary, it can be said that the index color area cannot be used freely by the application.

In the present system, a flag indicating whether or not each color is a system use area is held in the main memory 53 in the index color table, and thereby the system use area is managed.

The algorithm 1270 for calculating the luminance index color using the system use area will be described with reference to FIG. Here, for simplicity, it is assumed that, when the number of system use area colors si is set, the index from (255-si) to 255 becomes the system use area.

First, the input is a luminance calculation result 1261 and a system use area color 1262.

Next, the operation will be described. First, an index 1271 for a free system use area is obtained. If there is a space, the brightness calculation result (R,
G, B) are registered, and this location is output as a luminance index color. If there is no free space, it is determined whether or not to compress the system use area. If so, an operation of retrieving similar colors and combining them into one is performed (compression of system use area 1275), and the process returns to 1271. If not compressed, search for an approximate color from the index color table 1276
And output this.

Next, conversion to a model according to the hidden surface elimination method will be described.

FIG. 24A shows an example in which two surfaces intersect each other. When the hidden surface is eliminated by the Z-sort method,
The display is as shown in FIG. By knowing the client information in advance or inquiring by the server, the triangle ABC can be divided into a quadrilateral ACHG and a triangle GHB as shown in FIG. The division can be easily performed by finding the intersection of the straight line AB and the plane DEF for the point G and the intersection of the straight line BC and the plane DEF for the point H.

Such division is performed by the WWW server 12, 3D
An algorithm performed on a device capable of two-way communication with the 3D graphics processing device 1, such as the graphics development environment 3, will be described with reference to FIG.

When the server (the external input / output device 2 or the 3D graphics development environment 3) receives a request for 3D model data from the 3D graphics processing device 1, first, the server can use the 3D graphics processing device. Inquire of the 3D graphics processing apparatus 1 about the hidden surface elimination method 1
441. Next, it is determined 1442 whether or not the hidden surface elimination method of the 3D graphics processing apparatus 1 is the Z sort method. If the Z sort method, the intersecting surface is found 1443, and the intersection is calculated and divided 1444. . This is repeated as long as the intersecting faces remain.
Send 1446 to the graphics processing unit.

Hereinafter, another feature of the present invention, as a mechanism of high-speed 3D graphics display in a system with a small amount of hardware such as an embedded device, is 3
The D clipping process will be described with reference to FIGS. Here, a quadrangle drawing function of the graphics processor 70 will be described as an example.

First, the drawing of a rectangle by the graphics processor 70 will be described.

When the graphics processor 70 receives a command conforming to the format 1100 of the square drawing command shown in FIG. 15 from the CPU 50, as shown in an operation 1114 of the square drawing command shown in FIG. Coordinate TXS1102, Y coordinate TYS110
(DX) in the display area from the width TDX1104, height TDY1105)
1, DY1), (DX2, DY2), (DX3, DY3),
In a rectangle 1116 having (DX4, DY4) (designated by 1106 to 1113) as a vertex, it is deformed and drawn according to the shape of the rectangle 1116 in the display area. Here, the display area indicates an area of data held in the frame buffer 722 of FIG. 2, and the texture area indicates an area of data held in the texture buffer 723 of FIG.

The graphics processor 70 has a function of not performing drawing outside the display area (clipping), which is called a hardware clipping function. However, as can be seen from the format 1100 of the square drawing command, since the coordinate value can only take a value from -1024 to 1023, a hardware limit 1121 as shown in FIG. 16 exists. There is a restriction that it is not drawn. In the case of this example, MaxX = 1023, MaxY = 1023, Min
X = −1024, MinY = −1024.

The effect of the hardware limit function will be described with reference to FIG. Since the graphics processor 70 performs clipping on the squares A and B in FIG.
The U50 can transmit the coordinate data as it is to the graphics processor 70 (this is called complete drawing). The squares C and D do not need to be rendered by the CPU 50 executing a general area determination algorithm (see "Figure Processing Engineering by Computer, Fujio Yamaguchi, Nikkan Kogyo Shimbun" p. 141). .

However, regarding the square E, FIG.
As shown at 131, since it is in a range that cannot be specified by the rectangular drawing command format 1100, it is necessary to cut the surface so as to fall within the hardware limit x = MaxX. For these reasons, clipping cannot be completely achieved with the graphics processor 70 alone.

There are two methods for solving this problem as shown in FIG. The first is a method of performing clipping 1132 at the boundary of the display area. This method requires the calculation of the intersection between the display area and the surface, but the information related to the texture cannot be matched with the format 1100 of the rectangle drawing command, so that correct display cannot be performed. Also, since a division is required, the processing becomes slow.

The second is to convert the surface division clipping 1133 to C
There is a method of performing this in the PU 50. Texture coordinates,
The calculation of the width and height information (1102 to 1105) can be performed at high speed because a right-shift operation can be used when a fixed-point numerical expression is used. The diagram of the plane division clipping in FIG. 17 is a process in which the plane division clipping is applied to the above-described rectangle E.

FIG. 1 shows the algorithm of the plane division clipping.
8 will be described.

For the sake of simplicity, only the right side of the hardware limit area (x = MaxX) will be described.

The input is vertex coordinates 1 (x1, y1) 114
1, vertex coordinates 2 (x2, y2) 1142, vertex coordinates 3 (x
(3, y3) 1143, vertex coordinates 4 (x4, y4) 1144
And the display area boundary coordinates (right) X1145 and the hardware limit (right) MaxX1146.

The processing first finds the minimum x value of the vertex 11
62. It is determined whether or not this value x is within the display area.
8. If so, find the maximum x value of the vertex 11
64. It is determined whether this value exceeds the hardware limit 1165, and if not, complete drawing 1167 is performed. If not, the midpoint of each side is determined, the rectangle is divided, and this algorithm is applied 1166 to each of the divided rectangles. As a result, vertex coordinates 1151 of a plurality of surfaces to be drawn are output as information of a rectangle to be completely drawn.

The clipping of 3D graphics must be performed by the CPU 50 because the graphics processor 70 has no function of processing it. Also in the z direction, there are two types, a method of obtaining an intersection with the clipping plane and a plane division clipping. As can be seen from the square drawing command format 1100 of the graphics processor 70, the method of finding the intersection has a drawback that the texture cannot be correctly pasted. On the other hand, although the segmentation clipping has a disadvantage that the clipping plane is not clipped correctly, the texture can be correctly applied.

In 3D graphics processing, perspective projection is often performed in order to make objects far from the viewpoint appear small. For example, as shown in FIG.
= Point b on the n-th surface, and point b is projected on the point B.

Since it is necessary to divide by a value close to 0 at a point close to the viewpoint such as point b, there is a danger that the value will overflow in normal perspective projection transformation. At the point behind the viewpoint, the sign of the value is switched.

A method for solving this problem will be described with reference to FIG.

For a point b before the z = n plane, z = n
Select points farther than the plane. Here, it is assumed that point a is selected. The intersection point M of the projection point A by perspective projection of the point a and the straight line ab and z = n is obtained, and aM: Mb = AM: M
The point B 'which becomes B' is calculated as a temporary perspective projection point of the point b.

By using the temporary perspective projection points obtained by this method, a two-dimensional plane segmentation clipping algorithm can be applied, and a quadrangle can be drawn at high speed in the present system, and the texture can be correctly pasted. It becomes possible.

Finally, the 3D graphics processing device 1
And external input / output device 2 and 3D graphics development environment 3
FIG. 23, which is an embodiment different from FIG. 1, will be described as an example in which a device having the functions described so far is placed in between.

This is the same as the system configuration example of FIG. 1 except that the WWW intermediate server 2001 and the broadcast reception intermediate server 2011
WWW for connecting each to the 3D graphics processing device 1
The system has a configuration in which an intermediate server connection line 2002 and a broadcast reception intermediate server connection cable 2012 (hereinafter, these two are collectively referred to as a connection line) are added. There are two reasons for placing such an intermediate server.

One is that by placing the intermediate server at a short distance from the 3D graphics processing apparatus 1, the bandwidth of the connection line can be widened, so that interactive information communication between the intermediate server and the 3D graphics processing apparatus 1 can be performed. This is because it becomes possible. The other is that, in an external database such as the WWW server 12, data is not always transmitted only to the personal information device level device assumed by the 3D graphics processing device 1, so that general 3D data is used. In order to improve the display performance, an intermediate device for generating data for the 3D graphics processing device 1 is prepared, and the method described in the present invention is implemented.

As a specific example of the intermediate server, there is a system configuration as shown in FIG. WWW server 12, dial-up server 3001, and 3D graphics converter 30
02 is connected via the Internet line 22, and the dial-up server 3001 and the 3D graphics processing device 1
Are connected via a telephone line 3003. Here, in order to represent the difference in performance, the 3D graphics processing device A /
B, display device A / B, mouse A / B like A and B
FIG.

Here, the dial-up server 3001 and the 3D graphics converter 3002 are connected to the WWW server 12
And a 3D graphics processing device 1.

The operation of the system configuration shown in FIG. 13 will be described with reference to FIG. First, the 3D graphics processing device 1 issues a dial-up connection request to the dial-up server 3001 3101. If the connection is successful, a dial-up connection OK signal returns 3102.

These can be generally realized by an AT command of a modem. With this connection, the 3D graphics processing device 1 can convert the 3D graphics
2. Data communication with the WWW server 12 can be performed on a TCP / IP basis.

Next, the 3D graphics processing device 1
The performance information is transmitted 3103 to the D graphics converter 3002, and the signal of the performance information update end 3104 is received. The performance information needs to be obtained in advance by using, for example, the method of measuring the drawing speed of a triangle described in the present embodiment.

The above is the initial setting. Next, the 3D graphics processing device 1 sends the desired 3D graphics to the WWW server 12 via the 3D graphics conversion device 3002.
A request 3105 for D model data is made. WWW server 1
2 can be accessed by a protocol generally called HTTP. According to this protocol, transmission 3107 of 3D model data is performed from the WWW server 12 to the 3D graphics converter 3002. The 3D model data is converted by the 3D graphics conversion device 3002, and the 3D model data is transmitted 3108 to the 3D graphics processing device 1. By interpreting this by the 3D graphics processing device 1, 3D display according to performance is realized.

[0120]

According to the present invention, a 3D graphics processing apparatus for adding information such as a vertex deletion order to 3D graphics data created for a workstation or a higher-level personal computer and interpreting the information is used for personal information. Sufficient 3D display speed and quality can be obtained even in a system with a small amount of hardware such as information equipment. Further, by using a method for taking a system configuration taking into account the capability of the 3D graphics processing apparatus such as the limitation of displayable colors and the type of hidden surface elimination method, general-purpose 3
Even for D data, a sufficient display speed can be obtained with a system with a small amount of hardware.

[Brief description of the drawings]

FIG. 1 is a configuration example of a 3D graphics system according to an embodiment of the present invention.

FIG. 2 shows details of a graphics processor.

FIG. 3 is a data structure of a 3D model and an example of the 3D model.

FIG. 4 shows 3D models having different levels of detail and a level of detail table.

FIG. 5 is a display algorithm of a 3D model.

FIG. 6 is an algorithm for selecting a degree of detail.

FIG. 7 is a table of vertex coordinates of Torus1.

FIG. 8 is a table of information necessary for continuous polygon reduction of Torus1.

FIG. 9 is a table of torus 1 triangle vertex numbers.

FIG. 10 is a table of a triangle vertex number (1) of Torus2.

FIG. 11 is a table of a triangle vertex number (2) of Torus2.

FIG. 12 is a setting method of a detail level coefficient corresponding to a z value.

FIG. 13 is a system configuration example using an intermediate server.

FIG. 14 is a sequence chart of the system in FIG. 13;

FIG. 15 shows the format and operation of a square drawing command.

FIG. 16 is a diagram showing a limitation on rectangle drawing by a hardware limit (a range in which a rectangle can be drawn).

FIG. 17 shows a rectangular clipping method that cannot be drawn due to restrictions.

FIG. 18 is a diagram illustrating a plane segmentation clipping algorithm in a right portion of a region.

FIG. 19 shows formats of an index color table and a color conversion table.

FIG. 20 is a color conversion table creation algorithm.

FIG. 21 is a calculation algorithm of a luminance index color based on a color conversion table.

FIG. 22 is a calculation algorithm of a luminance index color using a system use area.

FIG. 23 is an intermediate server.

FIG. 24 shows division of a surface suitable for the Z-sort method.

FIG. 25 shows the operation of the vertex deletion algorithm.

FIG. 26 shows transmission of a model according to the hidden surface elimination method.

FIG. 27 shows a method of calculating a temporary perspective projection point.

FIG. 28 is a view showing 3D model data on a WWW server.

FIG. 29 is a drawing operation of the graphics processor.

FIG. 30: Vertex deletion by a connectable vertex.

FIG. 31 shows polygon reduction using a vertex deletion algorithm.

[Explanation of symbols]

DESCRIPTION OF SYMBOLS 1 ... 3D graphics processing apparatus, 2 ... External input / output equipment, 3, 13 ... 3D graphics development environment, 4 ... User interface equipment, 5 ... Display device (CRT), 10 ...
Broadcast receiver, 11 ... DVD / CD player, 12 ... WW
W server, 14 keyboard, 15 mouse, 20 SCSI cable for broadcast receiver, 21 SCS for playback device
I cable, 22 Internet line, 23 keyboard cable, 24 mouse cable, 30 SCSI for broadcast receiver, 31 SCSI for playback device, 32 10
BaseT, 33: Modem controller, 34: Serial I
/ O, 35 timer, 40 external I / O bus, 50 C
PU, 51: interrupt controller, 52: external bus interface, 53: main memory, 60: system bus, 70:
Graphics processor, 71: Graphics memory bus, 72: Graphics memory, 80: Image signal bus, 701: I / O for system bus, 702: Graphics processor internal bus, 703: Internal register,
704: internal register signal line, 705: memory interface, 706: rendering device, 707: display device, 708: image signal output line, 709: I / O for CRT display, 721: display list buffer, 7
22 ... frame buffer, 723 ... texture buffer, 1100 ... format of square drawing command (1
6bit), 1114: operation of a square drawing command, 11
32: clipping at the boundary of the display area; 1133: clipping in plane division; 1161: clipping in plane division (right side); 1200: 8-bit index color table;
1210: Color conversion table, 1230: Color conversion table creation, 1250: Calculation of luminance index color using color conversion table, 1270: Calculation of luminance index color using system use area, 1430: Client side erases hidden surface by Z-sort method Is divided on the server side on the basis of the information
1. Broadcast receiving intermediate server.

 ──────────────────────────────────────────────────続 き Continuing on the front page (72) Inventor Akihiro Katsura 7-1-1, Omikacho, Hitachi City, Ibaraki Prefecture Inside Hitachi Research Laboratory, Hitachi, Ltd. (72) Inventor Shigeru Matsuo 7-1 Omikamachi, Hitachi City, Ibaraki Prefecture No. 1 Hitachi, Ltd. Hitachi Research Laboratory (72) Inventor Tetsuya Shimomura 7-1-1, Omika-cho, Hitachi City, Ibaraki Prefecture Inside Hitachi Research Laboratory Hitachi Research Laboratory (72) Inventor Isao Kakebe Hitachi, Ibaraki Prefecture 7-1-1, Omikacho Hitachi Research Laboratories Hitachi Research Laboratory, Ltd. (72) Inventor Yasuhiro Nakatsuka 5-20-1, Josuihoncho, Kodaira-shi, Tokyo F-term in the Semiconductor Division, Hitachi, Ltd. 5B080 AA13 BA03 FA02 FA06 FA08 GA01 5C082 BA12 BB51 DA87 MM05 MM09

Claims (6)

[Claims] An external device for generating a plurality of types of display data having different data structures for one display data and outputting the plurality of types of display data having different data structures and the type of display data; A plurality of types of display data and types of display data having different data structures output from the external device are input and displayed based on the roughness of data to be displayed determined by a drawing process and the type of the display data. A graphics system comprising: a processing device for selecting data for display from a plurality of types of display data having different data structures; and a display device for displaying the display data selected by the processing device. 2. The processing device according to claim 1, wherein the processing device is configured to determine a processing capability of the processing device and a processing capability of the external device, a roughness of data to be displayed determined by a drawing process, and a type of the display data. A graphics system that selects the data to be displayed. 3. The graphics system according to claim 1, wherein the external device generates display data having a different data structure by deleting vertices of the three-dimensional data to be displayed according to a predetermined rule. 4. An external device for outputting display data, a CPU, and a graphics processor for performing a drawing process on the display data output from the external device in accordance with an instruction of the CPU, wherein the CPU has a number and a color. A graphics system comprising: a processing device that generates a color conversion table from an index color table that causes the display device to display display data selected by the processing device. 5. A processing device comprising: an external device for outputting display data; a CPU; and a graphics processor for performing a rendering process on the display data output from the external device in accordance with a command from the CPU. A graphics device having a display device for displaying the rendered display data, wherein the external device divides data to be displayed in advance when the request from the processing device is hidden surface erasure, A graphics system for outputting the displayed data to the processing device. 6. A processing device comprising: an external device for outputting display data; a CPU; and a graphics processor for performing a drawing process on the display data output from the external device in accordance with a command from the CPU. A graphics device having a display device for displaying the rendered display data, wherein the CPU of the processing device divides the data to be displayed when the data to be displayed exceeds the display area; Is a graphics system that performs drawing processing on the divided data to be displayed.