JPH0896150A - Graphic drawing apparatus and graphic data dividing method - Google Patents

Abstract

(57) [Abstract] [Purpose] To improve the read access speed from the memory storing the image data serving as the texture source in the texture mapping process without using a complicated circuit or the like. In a graphic drawing device having a texture mapping function for expressing image data as a texture source by pasting it on a polygonal surface of a three-dimensional graphic, the image data is divided into rectangular blocks and the pixels in each block are the same. DRAM 32 that stores it as a page and this D
The polygon drawing engine 31 for requesting data reference with respect to the image data stored in the RAM 32 by using the coordinate values within the polygon plane, and the address position of the image data stored in the DRAM 32 can be obtained by the polygon drawing engine 31. And an address generator 35 that generates the coordinate values.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a graphic drawing apparatus having a texture mapping function in three-dimensional computer graphics and a graphic data dividing method.

[0002]

2. Description of the Related Art Conventionally, in three-dimensional computer graphics, a picture previously drawn by a paint tool or an image captured by an image scanner is used as image data as a texture (pattern) source, and a polygonal surface (polygon) is used. ), There is a graphic drawing device having a texture mapping function for pasting and expressing this image data.
In this type of graphic drawing apparatus, image data serving as a texture source is stored as a simple two-dimensional array in a memory usually composed of a DRAM, and the texture source data on the texture source data represented by coordinates (u, v) is stored. In order to extract the point information, the address generator calculates (address) = u + v × (constant greater than the maximum value that u can take) + (offset) (1) and accesses the corresponding address position in the memory. It was supposed to do.

On the contrary, assuming that the display coordinates on the display screen are (x, y), coordinate conversion of u = fu (x, y) and v = fv (x, y) (2) is performed. At the same time, the memory is accessed to read the image data, for example, V-RAM for image output.
It is to transfer data to the memory such as.

As described above, in the texture mapping process, when the stored image data is read from the memory, it is not accessed in the order stored in the memory, but every time one pixel is generated on the display screen by the coordinates based on the above calculation. Will be randomly accessed.

FIG. 6 shows a memory IM including a DRAM.
The following is an example of the order of addresses to be accessed when performing simple coordinate conversion in which the image data stored in the table is rotated 45 ° in the clockwise direction and reading the image data. As illustrated, the area of the memory IM is sequentially scanned diagonally. As described above, the image data is sequentially read from the memory IM storing the image data by accessing each address, and the image data is expanded on the memory for image output of the next stage.

As described above, the random access must be performed when the image data is read out from the memory by necessity, and it takes a long time to read out and it is difficult to perform high-speed processing.

Therefore, conventionally, for example, as a memory for storing image data, a method of using a cache memory that can be accessed at high speed, a method of using a high speed page mode of DRAM, and the like have been adopted.

[0008]

However, in the method using the cache memory described above, unlike a general-purpose processor used in a normal computer system, the texture source is accessed by the texture mapping processing immediately after referring to the data once referred to. The probability of doing is extremely low. Therefore, in order to expect a sufficient effect as a cache memory, a very large capacity of the cache memory is required, which causes a problem of poor cost performance.

Further, in the method utilizing the high speed page mode of the DRAM, there is no problem in making access while changing the address of the element component "u" within the same page component "v" of the DRAM. In FIG. 6, the page breaks are likely to occur frequently as they occur every time one pixel moves, and the performance cannot be utilized.

As described above, it is difficult to speed up access to the memory storing the texture source by the texture mapping process without using a circuit having a complicated structure.

The present invention has been made in view of the above situation, and an object of the present invention is to use a memory storing image data serving as a texture source in a texture mapping process without using a complicated circuit or the like. An object of the present invention is to provide a graphic drawing device and a graphic data dividing method capable of improving the access speed when reading image data.

[0012]

That is, according to the present invention, in a graphic drawing apparatus having a texture mapping function of expressing image data as a texture source by pasting it on a polygonal surface of a three-dimensional graphic, the image data is formed into a rectangular block shape. A memory for storing the divided pixels so that the pixels in each block are on the same page; and a coordinate generation means for requesting data reference with the coordinate values in the polygon plane for the image data stored in this memory. , Address generating means for generating the address position of the image data stored in the memory from the coordinate values obtained by the coordinate generating means.

[0013]

With the above-described structure, the possibility that image data of adjacent pixels will be stored in the same page of the memory becomes very high. Therefore, the page break when reading the image data from the memory is increased. Can be suppressed to a low level, and as a result, the access speed can be improved.

[0014]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment in which the present invention is applied to a personal computer will be described below with reference to the drawings.
FIG. 1 shows its circuit configuration. Reference numeral 11 is a microprocessor (CPU), 12 is a RAM accessed by the microprocessor 11, and 13 is a ROM.

Microprocessor (hereinafter referred to as CPU)
Reference numeral 11 controls the entire apparatus. The RAM 12 and the ROM 13 are accessed and the OS is started in accordance with the input instruction to execute processing based on an arbitrary application program.

The RAM 12 stores each control information according to the read application program.
When an application program for drawing an image of a three-dimensional figure is executed, various figure data and image data serving as a texture source are stored. ROM13 is the above OS
Store other fixed information.

Reference numeral 14 is a keyboard, 15 is a mouse, 17 is a color LCD (liquid crystal display panel) as a display unit, 20 is a floppy disk device (FDD), and 22 is a hard disk device (HDD).

The keyboard 14 is a keyboard interface (KB) for inputting various instructions, data, and other input information necessary for executing an application program for image drawing.
-IF) 16 to the CPU 11. This keyboard
The terminal interface 16 also serves as the controller of the mouse 15, and the coordinate movement direction and distance information input by the mouse 15 and the button click signal are also input to the CPU 11 via the keyboard interface 16. .

The color LCD 17 has, for example, 640 dots ×
It is composed of a 480-dot dot-matrix type transmissive liquid crystal display panel, has a backlight device (not shown) on the back side thereof, and uses 16 of 260,000 colors to display various windows and graphics based on the application program being processed. Display images in color. The display controller (display-CNT) 18 is a VRAM under the control of the CPU 11.
The display control of the color LCD 17 is performed while expanding the display image on the screen 19.
It has a palette for selecting from 60,000 colors.

The floppy disk device 20 stores the created data file and the like under the control of the CPU 11 via a disk interface (FDD-IF) 21. The hard disk device 22 is a disk interface (HD
The created data file and the like are stored under the control of the CPU 11 via the D-IF) 23.

Next, FIG. 2 schematically shows the functional configuration in the case of executing the texture mapping by executing the application program for drawing and displaying the three-dimensional figure on the personal computer shown in FIG. Corresponding to the CPU 11, a polygon drawing engine for controlling the drawing of polygons (polygonal surface), 32 corresponds to a partial area of the RAM 12, DRAM for storing image data serving as a texture source, 33 corresponds to the VRAM 19 as it is. The VRAM 33 serves as a display memory for expanding and storing the drawing result and providing the stored content for display.

The polygon drawing engine 31 operates according to a drawing command input from an external host through the bus 34, directly or indirectly accesses the DRAM 32 and VRAM 33, and draws a polygon image on the VRAM 33. Coordinates (u, v) indicating a point on the image data serving as the texture source or the address value of the VRAM 33 is directly sent to the address generator 35.

If the address generator 35 has coordinates sent from the polygon drawing engine 31, the corresponding DRA
An address composed of the page number and the element number of M32 is generated, and if the address is an address, the address value is used as it is to access the DRAM32.

In the DRAM 32, the pixel information of the image data stored in the access position of the address generator 35 is read out and sent to the palette 36 and the selector 37. palette
Reference numeral 36 indicates the display controller together with the conversion table memory 38.
The conversion table memory 38 is referred to by using the pixel information of the image data from the DRAM 32, the luminance information of each of the RGB primary colors is read out, and the selector 37 is provided.
Send to.

The selector 37 selects either the pixel information of the image data read from the DRAM 32 or the brightness information from the palette 36 and sends it to the polygon drawing engine 31. The polygon drawing engine 31 selects the selector 37. The pixel information or brightness information sent from
Expanded and stored in AM33 (19) and stored in the color LCD 17
Display output with.

Next, the operation of the above embodiment will be described. FIG. 3 (1) shows original image data serving as a texture source, and FIG. 3 (2) shows the DRAM 32 in a state in which this image data is stored. As shown in the figure, the image data is divided into rectangular blocks represented by Δu pixels × Δv pixels (4 pixels × 4 pixels in the figure), and the pixels in each block are stored in the DRAM 32 so that they are on the same page. For example, in the image data of FIG. 3A, the coordinates (u,
v) All pixel information in the upper left block including pixel information represented by (0,0) (1,0) is all stored in the page "pg n" of the DRAM 32 as indicated by the dotted arrow α. In this case, the pixel information of the coordinates (0,0) (1,0) is stored in the address positions of the element numbers "el 0" and "el 1" on the page number "pg n" of the DRAM 32. At this time, Δu = 2 ^iu and Δv 2 ^iv (3), Δu and Δv are multipliers of 2 and 1 of the DRAM 32 is used.
It is set in advance so that one page of pixel information can be stored in a page.

When a drawing command is input from the external host to the polygon drawing engine 31 via the bus 34 with the image data stored in the DRAM 32, the polygon drawing engine 31 analyzes the drawing command. Polygon drawing engine when texture mapping is required
The reference numeral 31 sends the point position in the original image to the address generator 35 in the form of coordinates (u, v) in order to sequentially scan and access the image data as the texture source stored in the DRAM 32.

The address generator 35 uses the coordinates (u, v)
On the other hand, an address composed of a page number and an element number in the DRAM 32 is generated according to the correspondence shown in FIG. That is, the procedure is as follows: (i) u is shifted to the right by iu bits to Hu. (ii) Shift v by iv bits to the right to obtain Hv. (iii) Take the lower iu bit of u and set it as Lu. (iv) Take the lower iv bit of v and set it as Lv. (v) Multiply Hv by Mu (a constant equal to or larger than the maximum value that u can take), add Hu to this, and further add an offset A that means the first page of data, and make the sum the page number. (vi) Lv shifted to the left by iu bits and L
The logical sum of u is taken as the element number.

As described above, the address can be generated only by performing a very simple operation, and the multiplication is performed in the above process (v), but generally Mu is a small number of about 4 (bits). Therefore, the hardware cost for constructing the multiplier is very low.

When the address composed of the page number and the element number generated by the address generator 35 is sent to the DRAM 32 for access, the pixel information at the corresponding address of the DRAM 32 is read, and the palette 36 and the selector 37 are read.
Sent to. DRAM 32 by this address generator 35
When the access is continuously performed, since the storage method as shown in FIG. 3 is adopted, the probability that adjacent pixel information in the original image data is stored in the same page of the DRAM 32 is high. It is very high and the probability of a page break causing a delay in access time is low,
As a result, reading of image data can be processed at high speed.

Similar to the case shown in FIG. 6, FIG. 4 exemplifies a case where the original image data is subjected to a simple coordinate conversion in which it is rotated by 45 ° in the clockwise direction and is output for display. (1) shows the original image data serving as a texture source, and FIG. 4 (2) shows the DRAM 32 in a state in which this image data is stored.

When the original image data shown in FIG. 4A is subjected to coordinate conversion so as to be sequentially scanned diagonally as indicated by solid arrows, when each address of the DRAM 32 storing the image data is designated. The order is as shown in FIG.

That is, first, each element "el 4 (I)""el1(II)""el" of the page "pg n".
8 (III) "" el 5 "" el 2 (IV) "
Pixel information stored in each of "el 12 (V)", "el 9", "el 6", and "el 3 (VI)" is sequentially accessed. During this period, the page is not moved, so no page break occurs.

Next, the pixel information stored in each of the element "el 0 (VII)" of the page "pg n + 3" and the element "el 13 (VIII)" of the page "pg n" is successively accessed. During this time, from page "pg n" to "pgn + 3" and then to "pg n
Two page breaks occur from "n + 3" to "pg n".

Next, the pixel information stored in each of the elements "el 10" and "el 7 (IX)" of the page "pg n" is successively accessed. During this time, no page break occurs.

After that, the element "el 0 (X)" of the page "pg n + 1", the elements "el 4 (XI)" and "el 1 (XI) of the page" pg n + 3 ".
I) ”, page“ pg n ”element“ el 14 ”
(XIII) ”and“ el 11 (XIV) ”, and the pixel information stored in each of the elements“ el 4 (XV) ”and“ el 1 (XVI) ”of the page“ pg n + 1 ”are sequentially and successively accessed. During this period, the page "pg
"n" to "pg n + 1", "pg n + 1" to "pg n + 3", "pg n + 3" to "pg
A total of four page breaks occur from "n" and from "pg n" to "pg n + 1".

FIG. 5A is a list of designated addresses of the series of DRAMs 32 in the form of coordinates (u, v), and the portion indicated by an arrow in the drawing shows the occurrence of a page break. While accessing and reading the pixel information for 20 pixels, 6 page breaks occur for a convenient reason.

On the other hand, according to the conventional method in which the two-dimensional array of the original image data is stored as it is in the DRAM 32 as shown in FIG. 6, the designated address when similarly reading from the DRAM 32 is shown in FIG. 2), and page breaks occur at all access positions as indicated by arrows in the figure, so that page breaks occur 19 times for the sake of convenience.

In order to further reduce the number of page breaks, it goes without saying that the number of pixels that can be stored in one page of the DRAM 32 is increased and the size of the rectangular block (Δu × Δv) is made larger, and the number of blocks used for one image is made smaller. For that purpose, it is conceivable to increase the storage capacity of the DRAM 32 itself and reduce the information amount of each pixel information stored.

Therefore, in the present invention, based on the pixel information read from the DRAM 32, the palette 36 refers to the conversion table memory 38 to read the luminance information of each of the RGB primary colors, and the selector 3
7. Through the polygon drawing engine 31, it is expanded in the VRAM 33 (19) which is a display memory.

That is, the pixel information of the image data of the texture source is originally Ct bits (normally 4 to 4) for each RGB color.
If it has an information amount of 8 bits), an information amount of 3 Ct bits per pixel is required. On the other hand, as a general tendency, the colors used in one image of the texture source are biased, and only a few tens to a few hundred colors are often used.

Therefore, using the color palette function, DR
The amount of pixel information stored in AM32 is 3 per pixel
By reducing the number of Ct bits to Cp (<< 3 Ct) bits, the number of pixel information that can be stored per page of the DRAM 32 can be increased.

If such a palette function is not adopted, the pixel information stored in the DRAM 32 is RGB as it is.
If it is composed of luminance information of each primary color, DRA
The pixel information read out from M32 is directly selected by the selector 37 and supplied to the polygon drawing engine 31, whereby the VRAM
Can be expanded to 33 (19).

The image data stored in the DRAM 32 is obtained by dividing the original image data into rectangular blocks as shown in FIG. 3 and storing the pixels in each block so as to have the same page. However, when the original image data is simply stored as it is in a two-dimensional array, the address generator 35 uses the coordinates (u, v) for the address sent from the polygon drawing engine 31. Then, the operations shown in (i) to (vi) above are not executed, and the addresses are sent to the DRAM 32 in the same format to access the addresses.

[0045]

As described above in detail, according to the present invention, it is very likely that the image data of the adjacent pixels are stored in the same page of the memory. Therefore, when the image data is read from the memory. It is possible to provide a figure drawing device and a figure data dividing method capable of suppressing the occurrence of the page break of the above, and consequently improving the access speed.

[Brief description of drawings]

FIG. 1 is a block diagram showing an overall circuit configuration according to an embodiment of the present invention.

FIG. 2 is a block diagram schematically showing a functional configuration according to the embodiment.

FIG. 3 is a diagram for explaining the operation according to the embodiment.

FIG. 4 is a view for explaining the operation according to the embodiment.

FIG. 5 is a view for explaining the operation according to the embodiment.

FIG. 6 is a diagram exemplifying a general read access order of an image by a texture mapping function.

[Explanation of symbols]

11 ... CPU, 12 ... RAM, 13 ... ROM, 14 ... Keyboard
Do, 15 ... Mouse, 17 ... Color LCD, 19, 33 ... VRA
M, 20 ... Floppy disk device (FDD), 22 ... Hard disk device (HDD), 31 ... Polygon drawing engine, 32 ... DRAM, 34 ... Bus, 35 ... Address generator, 36
… Palette, 37… Selector, 38… Conversion table memory.

─────────────────────────────────────────────────── ─── Continuation of the front page (51) Int.Cl. ⁶ Identification code Internal reference number FI technical display location 9365-5H G06F 15/72 450 A

Claims (5)

[Claims] 1. A graphic drawing apparatus for drawing a polygonal surface defined by a set of given vertex coordinates, wherein image data used for determining each pixel in the polygonal surface is divided into rectangular blocks. A memory for storing the pixels in each block so that each pixel is on the same page; and a coordinate generation means for requesting data reference with the coordinate values in the polygon plane for the image data stored in this memory, An address generating means for generating an address position of the image data stored in the memory from the coordinate value obtained by the coordinate generating means. 2. A graphic drawing device having a texture mapping function for expressing image data as a texture source by pasting it on a polygonal surface of a three-dimensional graphic, wherein the image data is divided into rectangular blocks and the pixels in each block are A memory for storing each page so that they are on the same page, a coordinate generation unit for requesting data reference with respect to the image data stored in this memory with coordinate values within the polygonal plane, and an image stored in the memory. A graphic drawing apparatus comprising: an address generating unit that generates an address position of data from the coordinate value obtained by the coordinate generating unit. 3. The graphic drawing apparatus according to claim 1, further comprising a palette for selectively storing color information used in the image data stored in the memory from a large number of color information. . 4. A graphic data division method applied to a graphic drawing apparatus for drawing a polygonal surface defined by a set of given vertex coordinates, wherein an image used to determine each pixel in the polygonal surface. The data is divided into rectangular blocks and stored in memory so that the pixels in each block are on the same page, and the image data stored in this memory is referenced with the coordinate values within the polygon plane. And the address position of the image data stored in the memory is generated from the coordinate value obtained by the coordinate generation means. 5. A graphic data dividing method applied to a graphic drawing apparatus having a texture mapping function, wherein image data as a texture source is pasted onto a polygonal surface of a three-dimensional graphic, and the image data is divided into rectangular blocks. Then, the pixels in each block are stored in the memory so that each pixel is on the same page, and the image data stored in this memory is requested to reference the data with the coordinate values within the polygon plane, A graphic data dividing method characterized in that the address position of the stored image data is generated from the coordinate values obtained by the coordinate generating means.