JPH0752468B2 - Multiprocessor for line drawing display - Google Patents

Description

TECHNICAL FIELD The present invention relates to a line drawing display multiprocessor for displaying a line drawing on a display screen of a raster scanning display such as a CRT.

(Prior Art) A basic configuration of a display device for displaying a two-dimensional or three-dimensional figure on a display screen of a raster scanning CRT is shown in FIG. As shown in FIG. 1A, the display device includes a control processor (CP) 13 for controlling the entire device, a graphic file memory 14 for storing graphic data, coordinate conversion and scan conversion of graphic data (decomposition into pixels). A graphics processor (GP) 15 for performing one, a frame buffer memory (FBM) 16 for storing images for one screen, a video generator 1 for constantly reading out the frame buffer memory 16 and displaying it on the display screen of a CRT 18.
7. The interface 19 for communication with the host processor. On a three-dimensional graphic display device, a screen (xy plane)
A depth buffer memory (ZBM) 20 may be provided to store depth in the z-direction perpendicular to the. If the depth buffer memory 20 is used, the hidden surface can be easily erased by comparing the depths of two or more figures scanned and converted into the same pixel and selecting the figure having the smallest depth.

The obtained image is a collection of line segments or curves is called a wireframe image or a line drawing, and the collection of figures that fill the inside of a polygon or a closed curve is called a shading image or screen.

Generally, it takes the most processing time to generate a three-dimensional shaded image. Since the screen generation time or display performance is limited with one graphics processor (GP) 151, there is also an attempt to increase the speed by using a multiprocessor configuration that uses multiple graphics processors.

A conventional multiprocessor configuration diagram is shown in FIG.
It shows in (c). As shown in FIG. 2B, the graphic processor (GP) 15 is simply provided with a plurality of GP ₁ (15-1), GP ₂ (1
In the configuration of 5-2), ..., GP _n (15-n), access conflict occurs in writing to the frame buffer memory 16. Therefore, it becomes difficult to increase the number of GPs. Therefore, as shown in FIG. 3C, the frame buffer memory (FBM) 16 (and the depth buffer memory 20) is provided with a plurality of Fs.
There is a method in which the performance is increased by dividing into BM ₁ (16-1), FBM ₂ (16-2), ..., FBM _n (16-n) and directly connecting the corresponding GPs. This means that the screen is divided into areas.

(Problems to be Solved by the Invention) However, the multiprocessor described in FIG. 2C has the following problems.

When drawing a figure that covers a plurality of areas, it is necessary to divide the figure at the area boundaries, and the performance is reduced accordingly. This performance degradation can be tolerated in screen generation, but exceeds the permissible limit in line drawing generation.

Therefore, in the case of generating a line drawing at high speed, any of the multiprocessors shown in FIGS. 2B and 2C has a problem. Therefore, it has not been conventionally used to use a multiprocessor to obtain a line drawing with a particularly large number of line segments as a real time moving image increase (about 30 screens / second).

The present invention solves the above-mentioned problems and provides a multiprocessor for displaying a line drawing with an increased line drawing generation speed.

(Means for Solving Problems) In order to solve the above problems, the present invention provides a line drawing display multiprocessor for displaying a two-dimensional or three-dimensional line drawing on a display screen of a raster scanning type display. Having a partial graphic file obtained by dividing the graphic file to be processed, converting the coordinate of the graphic element in the partial graphic file, and classifying the line segment of the graphic element into steep slope or gentle slope with respect to the x-axis, The start point and the end point are determined based on the classification result, and if the gradient is steep with respect to the x-axis, a pixel data string in which the y coordinate changes by 1 is obtained, and if the gradient is gentle, a pixel data string in which the x coordinate changes by 1 is determined. As a result, m graphics processors that perform scan conversion of line segments, and one screen has M rows and N columns (M ≧
m, N ≧ m) are arranged two-dimensionally so as to correspond to each pixel position in the rectangular area when divided in a rectangular area having pixels
An image memory for storing pixel data at the pixel position of each rectangular area, M × N pixel processors for writing the pixel data from the graphic processor to the image memory, and outputs of the m graphic processors are output. A row distributor that cyclically shifts in parallel in the row direction to M row buses connected to the pixel processor, and columns of outputs of the m graphic processors to N column buses connected to the pixel processor. A column distributor that cyclically shifts in the direction and transfers in parallel, the m graphic processors simultaneously perform scan conversion of steep line segments according to the classification, and the row distributor and the M lines. Pixel data is transferred in parallel through the row bus of, and then the m graphic processors are simultaneously forwarded. Perform scan conversion of gently sloping line segments according to classification, transfer pixel data in parallel through the column distributor and the N column buses, and transfer each pixel data to one of the M × N pixel processors. The contents of the image memory of each pixel processor are displayed on the display screen of the display.

Preferably, the row distributor and the column distributor are composed of a counter and a cyclic digit mover.

(Operation) According to the present invention, since the line drawing display multiprocessor is configured as described above, the technical means operates as follows.
Each graphic processor (GP) processes different graphic elements independently. That is, after the coordinate conversion of the graphic element in each partial graphic file is performed, the line segments forming the graphic element are classified into a steeply sloping line segment and a gently sloping line segment. Each GP scan-converts the steep line segments all at once and outputs the pixel data to the row distributor. The row distributor cyclically shifts each image data in the row direction and outputs it to the pixel processor (PP) corresponding to the pixel data. The PP that has received the pixel data writes to the address of the image memory indicated by the pixel data. Next, each GP scan-converts the gently sloping line segments at the same time and transfers the pixel data in parallel to each PP via the column distributor, so that the image data is written in the image memory of the PP corresponding to the pixel data. . Like this, each GP
Processes different graphic elements independently, and image data can be transferred in parallel via a row distributor or a column distributor depending on the size of the slope of the line segment, so the transfer performance is degraded even if the number m of GPs is increased. There is no. Therefore, it is possible to solve the problems of the prior art.

(Embodiment) FIG. 1 is a block diagram showing an embodiment of the present invention, in which a control processor 1 passes a bus 2 to m graphic processors GP ₁ (3-1), GP ₂ (3-2). ),…, GP _m (3
-M). The output lines 4-1, 4-2, ..., 4-m of these graphic processors 3 (the reference numeral 3 is used to collectively refer to m GPs) are m-input M-output row distributors 5 and m-inputs. N output column distributor 7
Connected to. Of the M output terminals of the row distributor 5, the first output terminal is the N pixel processors PP ₁₁ (9-1-1), PP ₁₂ (9-
1-2), ..., PP _1N (9-1-N). Similarly, the M-th output terminal is similarly connected to the N pixel processors PP _M1 (9-M-1), PP _M2 (9-) via the row bus 6-M.
M-2), ..., PP _MN (9- _MN ). Of the N output terminals of the column distributor 7, the first output terminal is connected to the M pixel processors PP ₁₁ , PP ₂₁ , ..., PP _M1 via the column bus 8-1. Similarly, the Nth output terminal is connected to the M pixel processors PP _1N , PP _2N , ..., PP _MN via the column bus 8-N. As described above, the multiprocessor according to the present invention uses m one-dimensionally arranged graphic processors 3 and M × N two-dimensionally arranged pixel processors 9 (in the case where M × N PPs are collectively referred to, reference numeral 9 is used). ) Are connected by two paths, a row distributor and a column distributor. Data is always
It flows from GP3 to PP9. The output terminals of the M × N pixel processors 9 are unified by a video bus 10 and connected to a CRT display 12 through a video generator 11.

Each pixel processor has pixels located in a pattern that skips every M pixels in the y direction and every N pixels in the x direction among all the pixels that configure one screen. FIG. 3 is a pixel jump pattern diagram for explaining this state. Let y _max × x _max be the number of pixels on the entire screen, and y _max = M
If xP, x _max = NxQ (P and Q are natural numbers), the pixel processor PP ₁₁ (9-1-1) has P shown by a black circle in FIG.
Pixel processor PP with × Q pixels
_ij (9-i-j) is P × Q located at a point where the y coordinate is larger by i−1 and the x coordinate is larger by j−1 than the black circle pixel.
It has pixels. Where i = 1,2, ..., M; j = 1,2,
…, N. As shown in FIG. 3, if a black circle pixel is divided into P × Q rectangular regions having the upper left end point, M × N pixels in each rectangular region and the array of pixel processors are 1 It means to correspond to one-to-one.

FIG. 4 shows an example of the internal configuration of the pixel processor P _ij (9-i-j) and the video generator 11. PP _ij is connected to the row bus 6-i and the column bus 8-j, and pixel data (x _i , y _i , z _i , c _i ) is input from one of the two buses, and the multiplex (MPX ) 21 through 4 registers 22,2
Loaded at 3,25,24. Here, both M and N are powers of 2, and y _i and x _i are y _i = y _h × M + y _l (0 ≦ y _h <P, 0 ≦ y _l <M) ... x _i = x _h × N + x _l (0 ≦ x _h <Q, 0 ≦ x _l <N) ... The high-order bits x _h (contents of the register 22) and the high-order bits y _h (contents of the register 23) are used as addresses of the frame buffer memory 27 and the depth buffer memory 28 via the multiplexer (MPX) 26. Frame buffer memory 27,
The depth buffer memory 28 (collectively referred to as an image memory) stores color information C _M and depth Z _M for P × Q pixels, respectively. Also, the lower bit x _l
(Contents of register 22) and y _l (contents of register 23) are bits for selecting any of the M × N pixel processors 9, and in PP _ij , i = y _l + 1, j = x _l +
Only in the case of 1, writing to the memories 27 and 28 is permitted. This condition determination is performed by the write controller 29. Pixel writing with three-dimensional hidden surface removal is performed at the memory 27,2 at the address (x _h , y _h ).
If the contents of 8 are C _M (x _h , y _h ), Z _M (x _h , y _h ), Z _i <
_{Z M (x h, y h} ) iff _{Z M (x h, y h} ) with Z _i, C _M
This is accomplished by replacing (x _h , y _h ) with C _i .
The comparison between Z _i and Z _M is performed by the comparator 30. The contents of the frame buffer memory 27 are transferred to the video bus via the bus driver 31.
Read out to 10.

The video generator 11 includes a sync signal generator 32, screen address counters 33 and 34, a color table 35, and a DA converter (DAC) 3
It is composed of 6,37,38. Screen address counter 33 and 3
4 indicates a Q-adic counter x _h ′, an N-adic counter x _l ′, a P-adic counter y _h ′, an M-adic counter y so that (Nx _h ′ + x _l ′, My _h ′ + y _l ′) indicates a screen address. _It consists of _l ′. x _h ′, y _h ′ is passed through the multiplexer 26 to the frame buffer ( _CM ) 27
X _l ′, y _l ′ is output to the bus driver 31 and is used to select one of the M × N pixel processors 9. The data read onto the video bus 10 is converted by the color table 35 into the luminance levels of the three primary colors R, G, B.

The row distributor 5 is a data path of m inputs and M outputs, and is a parallel cyclic digit shifter (shifter) of M bit width controlled by a counter. The shift state of the row distributor 5 when m = 4 and M = 4 is shown in FIG. As shown in (a), (b), (c) and (d) of the same figure, there are four shift states depending on the value CN of the shift counter 39. As shown in FIG. 7A, when CN = 0, GP ₁ (3-1), GP _{2
(3-2), GP 3 (3-3} ), the output lines of the GP ₄ (3-4) 4-
Row buses 6-1, 6-2, 6- from 1,4-2,4-3,4-4 respectively
Data can be transferred in parallel to 3, 6-4. CN = 1,
In the case of 2 and 3, parallel transfer is possible with only CN bits cyclically shifted in the y direction (Figs. 5 (b), (c),
(D)).

6 (a) and 6 (b) are graphic processors GP.
₁ (3-1) decomposes the line segment AB into pixel columns, and the pixel data P ₀ , P ₁ , ..., Through the row distributor 5 and the row buses 6-1, 6-2, 6-3, 6-4. A method of transferring P ₈ to each destination pixel processor 9 is shown. Sixth both end points of the line segment as shown in Figure _{(a) A (x A,} y A), B (x B, y B) coordinate values are _{integers, | y B -y A | ≧} | x B -x _A | and y _B ≧ y _A 2
Two conditions shall be satisfied. First condition | y _B -y _A ｜
≧ | x _B −x _A | indicates that the line segment AB and the x-axis are inclined by 45 ° or more, and such a line segment is called a steep line segment.
The second condition y _B ≧ y _A indicates that a pixel row is generated from the end point A whose y coordinate is not large toward the other end point B.
The decomposition process of the steeply sloped line segment {circle around (3)} oriented in this way is usually performed as follows. When y _A = y _B , A and B are at the same point, so only one pixel is generated. If y _B > y _A The pixel series P _i (x _i , y _i ) is generated by y _i = y _A + i (y _A ≦ y _i ≦ y _B ). That is,
Starting from the point A, y-coordinate is increased one by one, x coordinate increases by one _{(x B -x A) / (} y B -y A), x -coordinate is used after integer by entering 4 disposable 5 Good. y coordinate is y
It ends when it reaches _B. In the case of three dimensions, the Z coordinate Calculate by Where z _A , z _B , z _i are A, B, P respectively
It is the z coordinate of _i .

FIG. 6B shows to which pixel processor the pixel data P ₀ , P ₁ , ..., P ₈ generated in the graphic processor GP ₁ should be transferred when M = N = 4. Here, it is assumed that P ₀ is transferred to the pixel processor PP ₂₂ , and the lower 2 bits of the y coordinate y _i of the pixel data selects the row bus, and the lower 2 bits of the x coordinate x _i is connected to the row bus. This is obtained by contrasting with FIG. 6 (a) because the pixel processor is selected.

FIGS. 7A and 7B show a method of transferring these pixel data through the row distributor 5. As shown in FIG. 7A, the pixel data P ₀ , P ₁ , ..., P ₈ are input from the input terminal 4-1 of the row distributor 5.
Output terminals 6-2, 6-3, 6-4, 6-1, ..., 6 that are cyclically continuous
-2 is output. This is the shift counter 39 CN = 1 →
It indicates that it is sufficient to increase the count like 2 → 3 → 0. One pixel data consists of 4 words of y _i , x _i , z _i , c, and if word data is transferred at 4 clocks word by word, the word counter (WN) 40 is set as shown in FIG. 7 (a). A pulse may be input from the clock input terminal 41 to count WN every time one word is transferred. FIG. 7B shows a time chart of the above transfer. T is a clock period.

FIGS. 8A and 8B show a case where pixel data are transferred in parallel through the row distributor 5 when four graphic processors generate different line graphics. The graphic processor shown in FIG.
GP ₁ generates the polygonal line P ₀ P ₁₀ P ₃₀ shown in FIG. Similarly, GP ₂ has a line segment Q ₀ Q ₅₀ , and GP ₃ has a line segment R ₀ R
₃₀ and GP ₄ generate curves S ₀ S ₂₀ and S ₂₁ S ₄₀ , respectively. As long as each GP generates a series of pixels in which the y-coordinate is incremented by 1, the shift counter 39 only counts up, and the rows are continuously transferred in parallel through the row distributor 5. However, since P ₀ , Q ₀ , R ₀ , S ₀ and S ₂₁ are transfer start points or restart points, a waiting time is generated. To determine whether a pixel should be transferred in a certain pixel transfer cycle, the value CN of the shift counter, the destination number of the pixel data (the lower 2 bits of the y coordinate), the row distributor and the row distributor are connected to the respective input terminals of the row distributor 5. 5
It is necessary to provide a determination circuit using the input terminal number of.

The column distributor 7 is a data path with m inputs and N outputs,
It is an N-bit parallel cyclic shifter controlled by a counter. The shift state of the column distributor 7 when m = 4 and N = 4 is shown in FIG. (A), (b), (c),
As shown in (d), there are four shift states. The column distributor 7 has a configuration similar to that of the row distributor 5, and cyclically shifts the CN bit of the shift counter 39 in the x direction from GP ₁ , GP ₂ , GP ₃ , GP ₄ by the column buses 8-1, 8. −2,8−
Transfer to 3,8-4 in parallel. The shift counter 39 is also used by the row distributor 5. When M = N, it is possible that the row distributor 5 and the column distributor 7 share the same shifter.

FIG. 10 shows how GP ₁ decomposes the line segment AB into pixel columns and transfers them to the pixel processor through the column distributor 7 and column buses 8-1, 8-2, 8-3, 8-4. As shown in FIG. 7A, when the line segment AB and the x-axis have an inclination of 45 ° or less, that is, when | x _B −x _A | ≧ | y _B −y _A | It is called a gently sloping line segment. Since a gently sloping line segment usually produces a series of pixels in which the x coordinate increases by 1, P _i
Find (x _i , y _i , z _i ).

x _i = x _A + i (x _A ≤x _i ≤x _B ) ... FIG. 10 (b) shows to which pixel processor the pixels P ₀ , P ₁ , ..., P ₁₀ generated in GP ₁ should be transferred when M = N = 4. Here, it is assumed that P ₀ is transferred to the pixel processor PP ₂₂ , and the lower 2 bits of the x coordinate of the pixel data select the column bus, and then y
The lower 2 bits of the coordinates are obtained by contrasting with FIG. 10 (a) since the pixel processor connected to the column bus is selected.

FIG. 11 shows how to transfer a sequence of pixels through the column distributor 7. In this case, each pixel data needs to have the x coordinate at the head.

Next, the processing contents of the graphic processor will be described. m
Since each GP can process different graphic elements independently, the graphic file to be displayed is divided into m partial solid files, and each GP holds the partial graphic file. GP first performs coordinate conversion for all graphic elements in its partial graphic file, then classifies and initializes line segments, then scan-converts only steep line segments in batch, and finally The scan conversion is performed only on the gently sloping line segment. m graphics processors simultaneously perform scan conversion of steeply sloping line segments, enabling parallel transfer through the row distributor 5.
Next, it is necessary that the m graphic processors simultaneously perform scan conversion of the gently sloping line segment so that parallel transfer can be performed through the column distributor 7.

Specific examples of line segment classification and initialization are shown in FIGS. 12 (a), (b),
It shows in (c). Now, as a result of the coordinate conversion of each vertex of a rectangular parallelepiped A ₁ A ₂ A ₃ A ₄ A ₅ A ₆ A ₇ A _{8 by} a certain graphic processor, it was converted into the screen coordinate system as shown in FIG. 12 (a). I shall. Each of the twelve line segments connecting the vertices is classified into a steep slope and a gentle slope by the method described above, the direction is given to the line segments, and the initial values and increments of x, y, z are obtained. As a result, the steeply sloping line segment is the eight directional line segments ▲ ▼, ▲ ▼, ▲ ▼, ▲ showing the thick line in Fig. 12 (a).
▼, ▲ ▼, ▲ ▼, ▲ ▼, ▲
▼, and the gently sloping line segment is the remaining four directed line segments ▲ ▼, ▲ ▼, ▲ ▼, ▲
▼ is shown, and the steeply sloping line segment is shown in FIG.
For the gently sloping line segment, data having the format as shown in FIG. 12 (c) can be obtained. Here, dx / dy, dz / dy, dy / dx, dz / dx are increment values, and l is the number of pixels to be generated. By performing cumulative calculation from these initial values and increments, scan conversion of line segments is performed.

(Effects of the Invention) As described in detail above, in the multiprocessor of the present invention, in two-dimensional or three-dimensional line drawing generation, m graphic processors perform parallel processing, and the pixel data generated by these are line segments. Depending on the size of the slope of, the parallel transfer can be performed through either the row distributor or the column distributor, so even if m is increased, the transfer performance will not be degraded and the display will be larger than with one graphics processor. It can be expected to increase the processing performance by m times.

The image memory for one screen is two-dimensionally divided by the pattern of pixels that skips every M rows and N columns, and is distributed and held in the pixel processors of the two-dimensional array. Therefore, this image memory is passed through the row distributor. It may appear as a memory system interleaved in the y-direction or as an interleaved memory system in the x-direction through the column distributor, in either case having a one-to-one correspondence with the graphics processor array.

Although line drawings are handled in the embodiment, each graphic processor has one line in a shift state with a row distributor, for example.
It is also possible to send a plurality of consecutive pixels in the x direction instead of one pixel, and thereby a screen composed of polygons or curved surfaces can also be generated by parallel processing. Since one graphic processor can write to any pixel of the image memory by changing the shift state of the distributor, it is possible to draw a graphic element of any shape, and one graphic element can be used as a plurality of graphic processors. No need to split and distribute for

In addition, since the pixel processor having a two-dimensional array can be configured relatively simply, it can be easily implemented as hardware and LSI and the array size can be increased. Since the interlaced pattern on the screen is assigned to the pixel processors, even load distribution can be expected among the pixel processors even if the array size is increased. The graphic processor can increase or decrease the number m depending on the required performance with the array size M being the upper limit.

Therefore, the multiprocessor of the present invention can generate a screen, but is suitable for obtaining a line drawing with a particularly large number of line segments as a real-time moving image increase.

[Brief description of drawings]

FIG. 1 is a block diagram of a multiprocessor for line drawing display according to the present invention, FIG. 2A is a block diagram showing a conventional graphic display device, and FIGS. 2B and 2C are conventional multiprocessors. FIG. 3 is a block diagram showing the pixel interlace pattern, FIG. 4 is an internal block diagram of the pixel processor and the video generator, and FIGS. 5 (a) to 5 (d) are shift states of the row distributor. 6 (a) and 6 (b) are explanatory diagrams of scan conversion of a steeply sloping line segment, and FIGS. 7 (a) and 7 (b).
Is an explanatory view of the image data transfer of the row distributor, 8th
FIGS. 9A and 9B are explanatory diagrams of parallel transfer, and FIGS.
(D) is a diagram showing a shift state of the column distributor,
FIGS. 10 (a) and 10 (b) are explanatory diagrams of scan conversion of a gently sloping line segment,
FIG. 11 is an explanatory diagram of pixel data transfer of the column distributor, and FIG. 12 is an explanatory diagram of classification and initialization of line segments. 1 ... Control processor, 2 ... Bus, 3 (3-1, 3-2,
…, 3-m) …… Graphic processor (GP), 4-1
4-2, ..., 4-m ... Output line, 5 ... Row distributor, 6-1, 6-2, ..., 6-M ... Row bus, 7 ... Column distributor, 8-1, 8-2, ..., 8-N ... Row bus, 9 (9
-1-1, ..., 9-i-j, ..., 9-MN) ... Pixel processor (PP), 10 ... Video bus, 11 ... Video generator, 21,26 ... Multiplexer (MPX ), 23 to 25 ... Register, 27 ... Frame buffer memory, 28 ... Depth buffer memory, 29 ... Write controller, 30 ... Comparator, 31 ...
Bus driver 32 Synchronous signal generator 33 34 Counter 35 Color table 36 to 38 DA converter (DAC) 39 Shift counter 40 Word counter 41 ...... Clock input terminal.

Claims (2)

[Claims] 1. A line drawing display multiprocessor for displaying a two-dimensional or three-dimensional line drawing on a display screen of a raster scanning type display device, which has a partial graphic file obtained by dividing a graphic file to be displayed. After the coordinate transformation of the graphic element in the figure, the line segment of the graphic element is classified into a steep slope or a gentle slope with respect to the x-axis, a start point and an end point are determined based on the classification result, and the If the slope is steep, a pixel data string whose y coordinate changes by 1 is obtained, and if the slope is gentle, a pixel data string whose x coordinate changes by 1 is calculated. When the screen is divided into rectangular areas having M rows and N columns (M ≧ m, N ≧ m), the pixels are arranged two-dimensionally so as to correspond to the respective pixel positions in the rectangular area. Pixel data of An M × N pixel processor having an image memory for storing the pixel data from the graphic processor and writing the pixel data from the graphic processor into the image memory, and M row buses connecting the outputs of the m graphic processors to the pixel processor. A row distributor that cyclically shifts in the row direction and performs parallel transfer, and an output of the m graphics processors that are cyclically shifted in the column direction and transferred in parallel to N column buses connected to the pixel processor. A column distributor, the m graphics processors simultaneously perform scan conversion of steep line segments according to the classification, and parallel transfer pixel data through the row distributor and the M row buses; Next, the m graphic processors simultaneously perform scan conversion of gently sloping line segments according to the classification. Then, the pixel data is transferred in parallel through the column distributor and the N column buses, each pixel data is transferred to one of the M × N pixel processors, and the contents of the image memory of each pixel processor are displayed. A multiprocessor for line drawing display, which is displayed on the display screen of the display. 2. The multiprocessor for line drawing display according to claim 1, wherein the row distributor and the column distributor are constituted by a counter and a cyclic digit shifter.