JPH0782425B2 - Sorting circuit - Google Patents

Description

The present invention relates to a sorting circuit, and more particularly to a circuit for sorting a plurality of reference axis data.

[Background Art] An image synthesizing circuit synthesizes and outputs various image signals for CRT display based on image information supplied from the outside, and is not only a two-dimensional plane image but also a three-dimensional image.
Since three-dimensional images can also be composited and output, for example, video games for three-dimensional images, flight simulators for airplanes and various vehicles, computer graphics, CA.
Widely used for D device display and other applications.

By the way, in the case of synthesizing a three-dimensional image having a depth in real time by using an image synthesizing circuit, the three-dimensional data of each object is processed at high speed for each frame based on the coordinate value in the image depth direction, that is, Z axis data. I need to sort it out.

Therefore, it has been desired to develop a circuit capable of high-speed sorting of a plurality of three-dimensional data based on predetermined reference axis data, that is, Z axis data.

However, conventionally, such sorting has been performed on all data by sequentially comparing adjacent Z-axis data included in each data and rearranging each time.

For this purpose, data transfer of all Z-axis data between memories must be repeated many times. Therefore, there is a problem that the data sorting operation cannot be performed at high speed.

In particular, in this conventional technique, when the number of Z-axis data to be compared increases, the sorting work takes too much time and effort. Therefore, in order to perform high-speed sorting, a relatively large computer must be used, and there is a problem that the entire device becomes complicated and expensive.

[Problems to be Solved by the Invention] An object of the present invention is to sort a plurality of data at high speed with a simple configuration, and particularly when the number of reference axis data to be sorted is large. It is to provide a sorting circuit that can be performed at high speed.

[Means for Solving the Problems] In order to achieve the above-mentioned object, according to the present invention, a plurality of data and predetermined reference axis data corresponding to one to one are input, and the plurality of data are converted into the reference axis data. An information memory for storing the plurality of data in association with a data number common to the plurality of data and the reference axis data, and a sorting means to which the reference axis data is input. The sorting means has a data number generating means for generating a data number corresponding to each input reference axis data, and a first data number storage area in which an address is designated based on the reference axis data, When the reference axis data corresponding to each storage area is first input, the data number generated by the data number generating means is recorded in this storage area. It has a first buffer memory to store and a last data number storage area whose address is specified based on the reference axis data, and a data number is generated in this storage area every time the reference axis data corresponding to each storage area is input. A last buffer memory for updating and storing the data number generated by the means, a chain buffer memory having a chain data number storage area whose address is designated based on the data number, and each time the data number of the last buffer memory is updated, First control means for writing a new data number to be updated in a chain data number storage area specified by the data number before updating, and last data after writing the data number to the first buffer memory and the last buffer memory Designated by the data number stored in the number storage area By writing the data number stored in the first data number storage area having a predetermined correspondence with the last data number storage area to the chain data number storage area, the reference axis data is stored in the chain data number storage area. Write the data numbers so that the numbers are linked in ascending or descending order.
And a third control means for reading the data numbers written in the chain data number storage area according to a predetermined read rule and reading the data from the information memory in the order of the read data numbers. The feature is that the data is sorted and output based on the reference axis data.

Further, the present invention is a circuit for sorting a plurality of reference axis data consisting of a plurality of digits, wherein the reference number data is generated by a data number generating means for generating a data number corresponding to each input reference axis data. A reference time data memory that stores the data corresponding to the data number, and a plurality of digits of the reference axis data output from the reference axis data memory are divided into a plurality of search groups each including one to a plurality of digits. There is a first data number storage area whose address is designated based on the value of the group, and when each search group corresponding to each storage area is first input, the data number generated by the data number generating means is stored in this storage area. A first buffer memory for storing the last buffer, and an address designated based on the value of each search group output from the reference axis data memory. Has a data number storage area, and each time each search group corresponding to each storage area is input, a last buffer memory that updates the data number generated by the data number generation means in this storage area, and an address based on the data number At least two chain buffer memories each having a chain data number storage area designated by: and each time the data number of the last buffer memory is updated, the at least two designated by the data number before update
First control means for writing a new data number to be updated in any one of the chain data number storage areas in one chain buffer memory, and after the completion of writing the data number in the first buffer memory and the last buffer memory , A chain data number storage area specified by the data number stored in the last data number storage area, and stored in the first data number storage area having a predetermined correspondence with the last data number storage area. Second control means for writing the data numbers so that the values of the respective search groups are linked in ascending or descending order in any one of the chain data number storage areas, and the reference axis data. Update the search group that is the target of the search from the lower digit to the upper digit. The newly searched search groups are read from the reference axis data memory in the order in which they are written in the chain data number storage area by the second control means, and the first control means and the second control means are read. Fourth control means for repeatedly performing the processing according to (4) while switching the chain buffer memory until the search group located on the uppermost side of the reference axis data, and after the sorting processing of the uppermost side search group is completed,
Third control means for reading out the data number written in the corresponding chain data number storage area according to a predetermined reading rule and sorting and outputting each reference axis data from the reference axis data memory in the order of the read data number. It is characterized by

Further, the present invention is a circuit for sorting a plurality of data and a predetermined reference time data consisting of a predetermined digit corresponding to the plurality of data, wherein the plurality of data is stored in the plurality of data and the reference axis. An information memory for storing a data number common to the data; and a sorting means for inputting the reference axis data, wherein the sorting means generates data for generating the data number corresponding to each reference axis data. A number generating means, a reference axis data memory for storing each reference axis data in association with the data number, and a plurality of digits of the reference axis data output from the reference axis data memory are stored in a plurality of one to a plurality of digits. When divided into search groups, it has a first data number storage area whose address is specified based on the value of each search group and corresponds to each storage area. Based on the value of each search group output from the reference axis data memory, a first buffer memory that stores the data number generated by the data number generating means in this storage area when each search group is first input. A last buffer memory which has a last data number storage area in which an address is designated and which updates and stores the data number generated by the data number generating means in this storage area each time each search group corresponding to each storage area is input. And at least two chain buffer memories each having a chain data number storage area whose address is designated based on the data number, and each time the data number of the last buffer memory is updated, the data number before the update is designated. At least 2
First control means for writing a new data number to be updated in any one of the chain data number storage areas in one chain buffer memory, and after the completion of writing the data number in the first buffer memory and the last buffer memory , A chain data number storage area specified by the data number stored in the last data number storage area, and stored in the first data number storage area having a predetermined correspondence with the last data number storage area. Second control means for writing the data numbers so that the values of the respective search groups are linked in ascending or descending order in any one of the chain data number storage areas, and the reference axis data Change the search group to be searched from the lower digit to the upper digit. The newly searched search groups are read from the reference axis data memory in the order in which they are written in the chain data number storage area by the second control means, and the first control means and the second control means are read. Fourth control means for repeatedly performing the processing according to (4) while switching the chain buffer memory until the search group located on the uppermost side of the reference axis data, and after the sorting processing of the uppermost side search group is completed,
A third control means for reading the data number written in the corresponding chain data number storage area according to a predetermined reading rule and reading the data from the information memory in the order of the read data number; The feature is that the sorting output is performed based on the axis data.

[Operation] As described above, according to the present invention, the reference axis data to be sorted is input to the first buffer memory and the last buffer memory in the order of the data numbers.

Then, the first buffer memory stores the data number when the corresponding reference axis data is first input, in the first data number storage area.

Similarly, the last buffer memory sequentially updates and stores the corresponding data number in the last data number storage area each time the corresponding reference axis data is read. Therefore,
In each last data number, the data number when the corresponding reference axis data was last read is stored.

When the data number stored in the last data number storage area is updated and stored, the data number stored in the storage area and the newly stored data number are input to the chain buffer memory.

Then, each time the data in the last data number storage area is updated, the chain buffer memory writes a new data number after update in the chain data number storage area specified by the data number before update. Therefore, when the reference axis data with the same value and different data number is repeatedly input, the history of the reference axis data, that is, the order of the data number of the reference axis data, is the chain data number. It will be written in the storage area.

After the data writing to the series of first buffer memory, last buffer memory and chain buffer memory is completed, the last data number and the last data number are stored in the chain data number storage area specified by the data number stored in the last data number storage area. Storage area The data numbers stored in the first data number storage area having a predetermined correspondence are sequentially written. In this way, the data numbers are written in the respective storage areas of the chain data number storage area so that the reference axis data are linked in ascending or descending order.

In the sorting circuit of the present invention, the data number written in the chain data number storage area is read according to a predetermined read rule. Then, read control is performed so that the input reference axis data is output in the order of the data numbers thus read.

By doing so, the input reference axis data is sorted and output in ascending or descending order.

Particularly, in the sorting circuit according to the first aspect, the reading control is performed so that the data is output from the information memory in the order of the data numbers thus read. By doing so, the plurality of data are sorted and output from the information memory in ascending or descending order based on the reference axis data.

As described above, according to the present invention, roughly, the data transfer of the input reference axis data to the first buffer memory, the last buffer memory and the chain buffer memory, and the transfer from the first buffer memory and the last buffer memory are performed. The reference axis data can be sorted by two transfer operations including data transfer to the chain buffer memory. For this reason, the number of data transfers is significantly reduced, and sorting can be performed at high speed, as compared with the conventional sorting technology in which adjacent reference axis data are compared and the reference axis data themselves are sequentially rearranged. it can.

Furthermore, according to the present invention, instead of using the reference time data itself for sorting, the data number of the reference axis data is used to indirectly sort the reference axis data. Even if the number of data is large, sorting can be performed easily and at high speed.

In particular, according to the invention of claim (1), a memory for storing the input reference axis data is unnecessary, and the sorting can be performed by a simpler circuit.

Further, according to the inventions of claims (2) and (3), even if the number of digits of the reference axis data is long, it is not necessary to increase the memory capacity of each buffer memory, and sorting can be performed with a simpler circuit. It becomes possible to do.

[Embodiment] Next, a preferred embodiment of the present invention will be described with reference to the drawings.

First Embodiment FIG. 1 shows a preferred embodiment of a sorting circuit according to the present invention. The circuit of the embodiment is a data generation circuit 8
The reference axis data output from the reference axis data memory 10, the data number pointer 12, the first buffer memory 20, the last buffer memory 30, the chain buffer memory 40, and each of these memories. And a sorting control circuit 80 for controlling writing and reading of data.

(A) Writing / reading to / from the reference axis data memory 10 The reference axis data memory 10 has a total of N reference axis data storage areas 14 from 1 to N designated by the data number pointer 12. Here, if the reference axis data is composed of M-bit data, each reference axis data storage area 14 may be formed to have a storage capacity of M bits.

When a plurality of reference axis data to be sorted are input from the outside, data numbers 1 to N are assigned to the reference axis data in the order of input, and data numbers 1 to N addressed by the data number pointer 12 are assigned. Are sequentially written in the reference axis data storage area 14.

In this way, when the writing of the reference axis data to be sorted into the reference axis data memory 10 is completed, the reference axis data from the reference axis data memory 10 is 1 to N.
Are sequentially read out in the order of the data numbers and output to the first buffer memory 20 and the last buffer memory 30.

In the embodiment, the reference axis data is read from the data number pointer 12 with a data number of 1 as a read address.
It is performed by sequentially outputting in the order of ~ N. When the address is designated by the data number, the reference axis data is read from the designated reference axis data storage area 14 toward the first buffer memory 20 and the last buffer memory 30.

(B) Writing to the buffer memories 20 and 30 Further, the first buffer memory 20 and the last buffer memory 30 have a first data number storage area 24 that corresponds to all possible values of the reference axis data in a one-to-one correspondence,
It has a last data number storage area 34.

When the reference axis data is composed of M bits as in the embodiment, a total of 2 ^M values of 0, 1, 2 ... (2 ^M −1) can be taken.

Therefore, the fast buffer memory 20 is provided with at least 2 ^M fast data number storage areas 24 designated by respective addresses of 0, 1, 2 ... (2 ^M −1). Similarly, the last buffer memory 30, 2 are designated by the respective addresses of at least 0,1,2 ... (2 ^M -1) ^M
An individual first data number storage area 34 is provided.

Further, the data number of the reference axis data output from the reference axis data memory 10 is written in the first data number storage area 24 and the last data number storage area 34. In the present embodiment, the data numbers are represented by 1 to N, and the maximum value is N. Therefore, each of the data number storage areas 24 and 34 may be formed so as to have a capacity of {log ₂ N} bits (where {} is a symbol representing an integer rounded up to the nearest whole number).

Then, when the reference axis data is input from the reference axis data memory 10 to the first buffer memory 20 and the last buffer memory 30, the first buffer memory 20 and the last buffer memory 30 are designated by the corresponding address pointers 22 and 32. The data number of the reference axis data is written in the data number storage areas 24 and 34.

In the present embodiment, such data writing is performed as follows using the first control circuit 80a of the sorting control circuit 80.

That is, when the reference axis data of the data number designated by the data number pointer 12 is output from the reference axis data memory 10, the reference axis data is stored in the address pointer 2.
The reference axis data thus set is output as a write address from the address pointers 22 and 32. Then, the data number (the data number corresponding to the reference axis data) designated by the data number pointer 12 is written in each of the data number storage areas 24, 34 designated by the write address.

Here, the first data number storage area 24 is
Once the data number is stored, the reference axis data memory 10
Even if new reference axis data with the same value is sequentially output from,
The new data number is formed so as not to be overwritten. On the other hand, the last data number storage area 34 is
Even if the data number is stored once, when the reference axis data having the same value is output from the reference axis data memory 10 next time, the data number of the reference axis data is newly updated and stored.

In this way, in the first data number storage area 24,
The data number when the value of the reference axis data first appears is stored. On the other hand, the last data number storage area 34 stores the data number when the value of each reference axis data appeared last.

Therefore, the same data number is written at the same address in the first data number storage area 24 and the last data number storage area 34 when the reference axis data having the same value is output from the reference axis data memory 10 only once. However, if the reference axis data having the same value is output a plurality of times, different data numbers will eventually be stored.

Therefore, when the value of the last data number storage area 34 of the last buffer memory 30 is updated and stored a plurality of times, if it is known how this update was performed, when the reference axis data is sorted in ascending or descending order. The arrangement of the data numbers of the respective reference axis data is found.

Therefore, in the chain buffer memory 40, a chain data number storage area 44 in which addresses are designated in the order of 0 to N based on the data number output by the address pointer 42
Is provided. Like each of the first data number storage area 24 and the last data number storage area 34, each of the chain data number storage areas 44 may be formed to have a storage capacity of at least {log ₂ N} bits.

When the contents of the last data number storage area 34 are updated and recorded, the data number before the update is changed to the address pointer 42.
And the chain data number storage area 44 is addressed. Then, a new data number after updating is written in the designated chain data number storage area 44.

In this way, when the last data number storage area 34 is updated and stored, the update history is sequentially written in the chain buffer memory 40.

As described above, according to the present embodiment, when the reference axis data is output from the reference axis data memory 10 in the order of the data numbers, the output reference axis data is used as the write address,
The data number is written in the first buffer memory 20 and the last buffer memory 30, and further, the data writing from the last buffer memory 30 to the chain buffer memory 40 is performed in association with this.

When such data transfer writing is completed, data transfer from the first buffer memory 20 and the last buffer memory 30 to the chain buffer memory 40 is started next.

(C) Transfer writing of data to the buffer memory 40 When such data transfer is started, the second control circuit 80b of the sorting control circuit 80 performs the following transfer control.

First, the data number stored in the last data number storage area 34 is set in the address pointer 42. Next, the chain data number storage area 44 addressed by the address pointer 42 is written with the data number of the first data number storage area 24 having a predetermined correspondence relationship with the designated address.

Writing of such data numbers is slightly different between sorting data in ascending order and sorting in descending order, but here, the case of sorting data in ascending order will be described as an example.

For example, when a data number is stored in the last data number storage area 34 designated by the address 0, the data number stored in the address 0 is set in the address pointer 42 first.

Then, the data number is read from the first data number storage area 24 designated by the address 1, and this data number is written in the chain data number storage area 44 designated by the address pointer 42.

At this time, if the data number is not stored in the first data number storage area 24 designated by the address 1, the data number is read from the storage area 24 designated by the address 2 and stored in the chain data number storage area 44. Write. Further, when the data number is not stored in the first data number storage area 24 designated by the address 2, the address 3, the address 4, ... And the address k are sequentially incremented until the data is found.

When a data number is read from the storage area 24 designated by the address k, this data number is read by the tuine data number storage area 44 designated by the address pointer 42.
Written in.

When such reading and writing is completed, next, a data number is read from the last data number storage area 34 designated by the address k, and is used as a write address in the chain data number storage area 44 in the same manner as the previous time. Data is written.

The apparatus of the embodiment repeatedly writes data in the chain data number storage area 44 as described above.

When such a series of write operations is completed, the chain data number storage area 44 of the chain buffer memory 40 stores data numbers so that the reference axis data are linked in ascending order.

Then, the third control circuit 80c of the sorting control circuit 80
Reads the data number written in the chain data number storage area 44 according to a predetermined reading rule. Then, the reading control is performed so that the reference axis data is output from the reference axis data memory 10 in the order of the read data numbers.

By doing so, the reference axis data is sorted and output from the reference axis data memory 10 in ascending order.

Specific Sorting Operation Next, using such a sorting circuit, the case where the seven reference axis data output from the data generating circuit 8 are sorted in ascending order and in descending order will be described as an example.

(I) When sorting in ascending order FIG. 2 shows an example of such a sorting circuit.

In the present embodiment, since seven reference axis data are sorted, the reference axis data memory 10 is formed to have a total of seven reference axis data storage areas 14 designated by data numbers 1 to 7. do it.

Further, the reference axis data is assumed to be composed of 2-bit data so as to take any value of 0 to 3. In this way, the first buffer memory 20 and the last buffer memory 30 have four data number storage areas 24, 24 whose addresses are reference axis data 0 to 3, respectively.
May be formed.

(A) Writing / reading to / from the reference axis data memory 10 Here, first, the reference axis data is directed from the external data generation circuit 8 to the reference axis data memory 10, and the reference axis data is 2 → 1 → 3 → 3 → 0 → 2 → 3. When input in the order of, the input reference axis data
The data numbers of 2, 3, ... Are written in the memory area 14 as an address.

One of the features of the present invention is thus the data memory 10
When the reference axis data is written in, the reference axis data is sorted using the data number instead of the reference axis data itself.

By doing so, even when the number of digits of the reference axis data to be sorted is large, the reference axis data can be sorted at high speed with a simple circuit.

In this embodiment, the reference axis data memory 10
When the reference axis data is written therein, the reference axis data is sequentially read from the reference axis data memory 10 in the order of the data numbers.

(B) Writing to the buffer memories 20 and 30 When the reference axis data is read in this way, the corresponding data number is used as the address and the corresponding data number is stored in the first data number storage area 24 and the last data number. It is sequentially written in the storage area 34.

Therefore, when the reference axis data “2” specified by the data number “1” is first output from the data memory 10, the reference axis data “2” is used as an address in each data number storage area 24, 34. , The data number “1” is written.

Similarly, when the reference axis data "1" specified by the data number "2" is output from the reference axis data memory 10, the reference axis data "1" is used as an address and the data numbers 24 and 34 The data number "2" is written.

Next, when the reference axis data "3" similarly specified by the data number "3" is output from the reference axis data memory 10, the reference axis data "3" is used as an address and the data number storage area 24, The data number “3” is written in 34.

Next, when the reference axis data "3" specified by the data number "4" is output, the data number "4" is stored in the data number storage areas 24 and 34 with the reference axis data "3" as an address. Is entered. At this time, since the data number has already been written in the first data number storage area 24, no new data number is written. On the other hand, the last data number storage area 34 updates and stores the previous data number “3” into the new data number “4”. Therefore, the updated data number "4" is written in the chain data number storage area 44 with the data number "3" before the update as an address.

Next, when the reference axis data “0” specified by the data number “5” is read from the reference axis data memory 10, the reference axis data “0” is used as an address in each data number storage area 24, 34. Is written with the data number "5".

Next, when the reference axis data "2" specified by the data number "6" is output from the reference axis data memory 10, the number reference axis data "2" is addressed to the data storage area 24, The data number “6” is input to 34. At this time, the data number "1" has already been written in the first data number storage area 24 designated by the address "2". Therefore, the newly input data number "6" is not written. On the other hand, the contents of the last data number storage area 34 designated by the address "2" are updated and stored in the newly input data number "6".

In this way, the contents of the last data number storage area 34
When the data is updated from "1" to "6", the data number "1" before the update is used as an address for the chain data number storage area.
A new data number “6” after updating is written in 44.

Next, when the last reference axis data “3” specified by the data number “7” is read from the reference axis data memory 10,
This reference axis data “3” is used as an address, and the data number
The data number "7" is input to 24 and 34. At this time, since the data number "3" has already been written in the first data number storage area 24, the newly input data number will not be written. On the other hand, the contents of the last data number storage area 34 are updated and stored in the newly input data number "7".

In this way, the contents of the last data number storage area 34
When the data number is updated from "4" to "7", the new data number "7" after the update is stored in the chain data number storage area 44 with the data number "4" before the update as an address.

By such a series of writing operations, the data number when each reference axis data first appears is written in the first data number storage area 24 having the reference axis data as an address.

Further, the last data number storage area 34 having the reference axis date as an address stores the data number when the value of each reference axis data appeared last.

Furthermore, each time the data in the last data number storage area 34 is updated and stored in the chain data number storage area 44 having the data number as the address, the data number after the update is sequentially written using the data number before the update as the address. Will be done. Therefore, when the same reference axis data is output from the reference axis data memory 14 a plurality of times, the storage area 44 stores a history of the data number order of the reference axis data. become.

(C) Transfer writing of data to the buffer memory 40 When such a series of writing operations is completed, data from the first buffer memory 20 and the last buffer memory 30 to the chain buffer memory 40 is then transferred as shown in FIG. The transfer starts.

When such data transfer is started, first, the data number storage area 24 in which data is stored is searched for in order from the smallest address. And that storage area 24
The data number stored in 1 is read out as the start address and is written in the address 0 of the chain data number storage area 44.

When the address 0 of the storage area 44 is used for another purpose, the start address is, for example, a start address pointer as shown by a dotted line in FIG.
It may be formed so as to be set to 310.

In this embodiment, when the data number storage area 24 in which the data is stored is searched in order from the smallest address, it is detected that the data number is written in the storage area 24 of the address 0. Then, this data number "5" is written in the chain data number storage area 44 designated by the address 0 as shown in FIG.

When the storage area 44 of the address "0" is used for another purpose, it is set in the start address pointer 310.

Next, the data number when the reference axis data “0” appears last is used as an address, and the data number when the reference axis data “1” larger than this appears first is written in the chain data number storage area 44. .

To do so, the data number "5" in the last data number storage area 34 designated by the address "0" is read as the write address. Then, the chain data number storage area 44 designated by this address "5"
It is sufficient to write the data in the first data number storage area 24 designated by the address "1".

Next, similarly, the data number when the reference axis data “1” appears last is used as a write address, and the data number when the reference axis data “2” above that appears for the first time is set as the chain data number storage area. Write to 44.

In order to perform such writing, the data number "2" in the last data number storage area 34 designated by the address "1" is read as the write address. Then, the data "1" in the first data number storage area 24 designated by the address "2" may be written in the chain data number storage area 44 designated by the address "2".

Similarly, the data number "6" when the reference axis data "2" appears last is used as a write address, and the data number "3" when the reference axis data "3" appears first is stored as a chain data number. Write in area 44.

When such a series of data transfer work is completed, the data numbers are written in the chain data number storage area 44 so that the reference axis data are linked in ascending order.

(D) Reference axis data sorting output Upon completion of transfer and writing of such data, the chain buffer memory 40 outputs the data numbers sequentially as read addresses to the reference axis data memory 10 according to a predetermined read rule. It

In the present embodiment, the read start address is stored in the chain data number storage area 44 designated by address 0. Therefore, first, the address “0” is set in the address pointer 42. As a result, the data number "5" stored in the address "0" of the data number storage area 44 is read as the read start address.

In this way, the data number is stored in the data number storage area 44.
When read from, the read data number is set in the address pointer 42 next.

Therefore, the next data number "2" is read from the data number storage area 44 designated by the address "5", and the read data number is newly set in the address pointer 42.

When the data numbers are sequentially read according to such a reading rule, the data numbers are sequentially output from the chain data number storage area 44 in the order of 5 → 2 → 1 → 6 → 3 → 4 → 7.

Therefore, if the data number read in this way is used as a data read address for the reference axis data memory 10, the reference axis data memory 10 will be in the order of 0 → 1 → 2 → 2 → 3 → 3 → 3. , The reference axis data is sequentially sorted and output in ascending order.

(II) Case of Sorting in Descending Order Next, using the sorting circuit of the present invention, sorting of reference axis data in descending order, and sorting of 7 pieces of reference axis data in descending order as shown in FIG. Will be described as an example.

(A) Writing / reading to / from the reference axis data memory 10 This operation is the same as the case of sorting the reference axis data in ascending order, and the description thereof will be omitted.

(B) Writing to the buffer memories 20 and 30 This operation is also similar to the case of sorting data in ascending order, and therefore the description thereof is omitted here.

(C) Transfer / writing of data to / from the buffer memory 40 A method of transferring / writing data to / from the buffer memory 40 is slightly different between sorting the reference axis data in ascending order and sorting in descending order.

FIG. 20 shows an example of data transfer from the first buffer memory 20 and the last buffer memory 30 to the chain buffer memory 40 when data is sorted in descending order.

When the sorting is performed in descending order, the data number storage area 24 in which the data is stored is searched first in descending order of the address when the data transfer is started. Then, the data number stored in the storage area 24 is
It is read as a start address and written in address 0 of the chain data number storage area 44.

When the address 0 of the storage area 44 is used for another purpose, the start address is set to, for example, the start address pointer 310 as shown by the dotted line in FIG.
It may be formed so as to be set to.

In this embodiment, when the data number storage area 24 in which data is stored is searched in order from the largest address (reference axis data), the data number is written in the storage area 24 of the address “3”. Is detected. This data number "3" is the chain data number storage area designated by the address "0" as shown in FIG.
Written on 44.

When the storage area 44 of the address "0" is used for another purpose, it is set in the start address pointer 310.

Next, the data number when the reference value data “3” appears last is used as an address, and the data number when the smaller reference axis data “2” first appears is written in the chain data number storage area 44. .

In order to do this, the data number "7" in the last data number storage area 34 specified by the address "3"
Is read as a write address. And the chain data number storage area specified by this address "7"
The data “1” in the first data number storage area 24 designated by the address “2” may be written in 44.

Next, similarly, the data number when the reference axis data “2” appears last is used as the write address, and the data number when the reference axis data “1” below that appears for the first time is set as the chain data number storage area. Write to 44.

In order to perform such writing, the data number "6" in the last data number storage area 34 designated by the address "2" is read as the write address. Then, the data "2" in the first data number storage area 24 designated by the address "1" may be written in the chain data number storage area 44 designated by the address "6".

Similarly, the data number "2" when the reference axis data "1" appears last is the write address, and the data number "5" when the reference axis data "0" appears first is the chain data number storage. Write in area 44.

When such a series of data transfer operations are completed, data numbers are written in the chain data number storage area 44 so that the reference axis data are linked in descending order.

(D) Reference axis data sorting output Upon completion of transfer and writing of such data, the chain buffer memory 40 outputs the data numbers sequentially as read addresses to the reference axis data memory 10 according to a predetermined read rule. It

In the present embodiment, the read start address is stored in the chain data number storage area 44 designated by the address "0". Therefore, first, the address “0” is set in the address pointer 42. As a result, the data number "3" stored in the address "0" of the data number storage area 44 is read as the read start address.

In this way, the data number is stored in the data number storage area 44.
When read from, the read data number is set in the address pointer 42 next.

Therefore, the next data number "4" is read from the data number storage area 44 designated by the address "3", and the read data number is newly set in the address pointer 42.

When the data numbers are sequentially read according to such a reading rule, the data numbers are sequentially output from the chain data number storage area 44 in the order of 3 → 4 → 7 → 1 → 6 → 2 → 5.

Therefore, if the data number thus read out is used as a data read address for the reference axis data memory 10, the reference axis data memory 10 is in the order of 3 → 3 → 3 → 2 → 2 → 1 → 0. , The reference axis data are sequentially output in descending order.

(III) Summary of Ascending and Descending Coating Operations Thus, according to the present invention, the reference axis data itself is not used when sorting the reference axis data in ascending order or in descending order. By using the data number assigned to the reference axis data, even if the number of bits of the reference axis data is large, sorting work can be performed quickly and easily without being affected so much. It will be possible.

In particular, according to the present invention, the sorting of the reference axis data is repeated for each reference axis data, and the operation of rearranging the reference axis data while comparing one reference axis data with all the remaining reference axis data is performed as in the conventional case. Compared to the ones, the number of times of data transfer is much smaller and the number of data to be transferred is also significantly less, so it is possible to transfer the reference axis data with a simple circuit and at extremely high speed. .

In addition, in the said Example, although the case where all four reference-axis data of 0-3 existed, it demonstrated that this invention is not restricted to this, and one reference-axis data in this, for example, reference-axis data. Even when "1" does not exist, the sorting work can be performed in the same manner.

In this case, as shown in FIG. 4, even if the data transfer from the reference axis data memory 10 to the first buffer memory 20 and the last buffer memory 30 is completed, the address "1" of each of the buffer memories 20 and 30 is changed. No data number is written in the data number storage areas 24, 34 designated by.

Therefore, for example, when sorting data in ascending order, when performing the data transfer work from the buffer memories 20 and 30 to the chain buffer memory 40, the data number "0" when the reference axis data "0" was last output is displayed. 5 ”as an address, and the data number 1 when the further reference axis data, that is, the reference axis data 2 first appears
Should be written in the chain data number storage area 44. Incidentally, the subsequent data writing is performed in the same manner as the embodiment shown in FIG.

Second Embodiment FIG. 21 shows a second preferred embodiment of the present invention.

In the first embodiment, the case where the data number pointer 12 of the reference axis data memory 10 functions as a data number generating means has been described as an example. In this embodiment, a data number generation counter 13 is used instead, and the counter 13 is made to function as a data number generation means.

That is, when the reference axis data to be sorted is sequentially output from the external data generation circuit 8, the reference axis data is sequentially written and stored in the reference axis data memory 10 as in the first embodiment. At the same time, it is input to the data number counter 13, the first buffer memory 20, and the last buffer memory 30.

At this time, the data number counter 13 generates a corresponding data number each time the reference axis data is input. In the embodiment, 0, 1, 2 ... (2 ^M −1) is synchronized with the input of the reference axis data.
The data numbers are output in this order.

The data generating circuit 8 is stored in the storage areas 24 and 34 of the first buffer memory 20 and the last buffer memory 30, respectively.
The data number output from the data number counter 13 is written in the same manner as in the first embodiment, using the reference axis data output from the write address as the write address. At this time, data is also written in the chain buffer memory 40 in the same manner as in the first embodiment.

When the data transfer writing to the respective buffer memories 20, 30, 40 is completed, the reference axis data writing to the reference axis data memory 10 is also completed. Then, after such data transfer writing is completed, data is transferred from the first buffer memory 20 and the last buffer memory 30 to the chain buffer memory 40 in the same manner as in the first embodiment.

When the data transfer and writing to the chain buffer memory 40 is completed, the chain buffer memory 40 stores the data numbers so that the reference axis data are chained in ascending or descending order.

Therefore, the third control circuit 80c reads the data number written in the chain data number storage area 44 according to a predetermined reading rule. Then, the reading control is performed so that the reference axis data is output from the reference axis data memory 10 in the order of the read data numbers. As a result, the reference axis data is sorted and output from the reference axis data memory 10 in ascending or descending order.

Thus, according to the present embodiment, the reference axis data memory 10
Since the writing of the reference axis data to and the sorting operation of the reference axis data can be performed in parallel at the same time, the sorting of the reference axis data can be performed at a higher speed than in the first embodiment.

As a result, like the first embodiment, the reference axis data can be sorted and output in ascending order or descending order.

Third Embodiment In the first and second embodiments, the case where the input reference axis data is sorted has been described as an example, but the present invention is not limited to this, and the reference axis data and its combination information ( Sorting can also be performed in the same manner for sorting data composed of reference axis data and information that forms a pair.

FIG. 19 shows a preferred embodiment in which sorting data containing such combination information is sorted based on the reference axis data. The circuit of this embodiment can be formed by using either the circuit of the first embodiment or the circuit of the second embodiment.
Description will be given by taking as an example a case where the circuit is formed using the circuit of the embodiment.

The sorting circuit of the embodiment has a reference axis data memory 10
And an information memory 58. Then, this circuit stores the reference axis data included in the sorting data output from the data generation circuit 8 in the reference axis data memory 10 and the combination information paired with each reference axis data in the information memory 58. Is formed.

Here, the reference axis data memory 10 has a total of N reference axis data storage areas 14 designated by the data number pointer 12 from at least 1 to N.

The information memory 58 also has a total of N combination information storage areas 58a of at least 1 to N designated by the data number pointer 12.

When a plurality of reference axis data to be sorted are input from the external data generation circuit 8, the reference axis data are assigned data numbers 1 to N in the order of input. Then, the reference axis data included in the sorting data and the combination information thereof are stored in the data number pointer 12
1 to N reference axis data storage area 14 designated by
And sequentially written in the combination information storage area 58a.

In this way, when sorting data is input to the sorting circuit of this embodiment from the outside, the reference axis data and its combination information included in the sorting data are stored in each storage area 14 designated by the data number pointer 12. , 58a are sequentially written with a predetermined correspondence relationship.

Therefore, if the reference axis data stored in the reference axis data memory 10 is sorted in the same manner as in the first embodiment, the reference axis data is stored in the chain data storage area 44 of the chain buffer memory 40. The data numbers will be stored in ascending or descending order.

Therefore, if the data numbers thus stored in the chain data number storage area 44 are read in the same manner as in the first embodiment and the combination information is read from the information memory 58 in the order of the read data numbers, the information memory 58 From this, a series of combination information is sorted and output in ascending or descending order based on the reference axis data.

As described above, according to this embodiment, even when the sorting data itself has a large amount of information, the reference axis data memory
10. The sorting process using the buffer memories 20, 30, 40 can be completed in a short time. Therefore, even when the amount of information per unit of sorting data is large, this sorting process can be efficiently performed in a short time.

Fourth Embodiment FIG. 22 shows a fourth preferred embodiment of the present invention. In the third embodiment, the case where the circuit for sorting the sorting data including the combination information based on the reference axis data is formed using the circuit of the first embodiment has been described as an example. The present embodiment is characterized in that such a sorting circuit is formed by using the circuit of the second embodiment. The members corresponding to those in the above-mentioned respective embodiments are designated by the same reference numerals and the description thereof will be omitted.

The sorting circuit of this embodiment comprises an information memory 58 and the circuit shown in the second embodiment. The reference axis data memory 10 is not provided.

The reference axis data included in the sorting data output from the external data generating circuit 8 is input to the data number counter 13 and the buffer memories 20 and 30, and the combination information paired with the reference axis data is the above-mentioned first information. It is sequentially stored in the information memory 58 in the same manner as in the third embodiment. Of course, the reference axis data may be included in the combination information sequentially stored in the information memory 58.

When the reference axis data is input, the buffer memories 20, 30, 40, the data number counter 13 and the sorting control circuit 80 operate in the same manner as in the second embodiment. Therefore, in the chain data storage area 44 of the chain buffer memory 40, the data numbers are stored so that the reference axis data are linked in ascending or descending order.

Then, the third control circuit 80c reads out the data numbers stored in the chain data number storage area 44 in the same manner as in the first embodiment, and controls the reading of the combination information from the information memory 58 in the order of the read data numbers. . As a result, a series of combination information is sorted and output from the information memory 58 in ascending or descending order based on the reference axis data.

Fifth Embodiment FIG. 23 shows a modification of the first embodiment as a fifth embodiment.

The feature of this embodiment is that even if the number of digits of the reference axis data stored in the reference axis data memory 10 is large, each buffer memory
The purpose is to enable high-speed sorting of reference axis data without increasing the memory capacity of 20,30,40.

In this embodiment, the reference axis data memory 10 has a reference axis data storage area 14 whose address is designated by a data number.

Two sets of chain buffer memory 40 are provided. When data is written in one memory 40, the other memory
It is configured to read data from 40.

Then, the reference axis data output from the data generating circuit 8 is sequentially written and stored in the storage area 14 corresponding to the data number order. In the embodiment, the reference axis data composed of 3 Mbits is written in the corresponding storage area 14.

When the writing of the reference axis data into the reference axis data memory 10 is completed in this way, the reading of the reference axis data from the reference axis data memory 10 is started next.

The feature of this embodiment is that a plurality of search digits of the 3M-bit data forming the reference axis data is provided for each predetermined bit (the search digits collected for each predetermined bit in this way correspond to a search group).
And reading the reference axis data memory from the reference axis data memory 10 in search digit units.

In this embodiment, when the writing of the reference axis data into the reference axis data memory 10 is completed, first, the lower M bit data is sequentially read from the reference axis data memory 10 in the order of the data numbers 1 to N, and the first buffer The data is output to the memory 20 and the last buffer memory 30.

The lower M-bit data of each reference axis data read out in this way is subjected to the sorting process as in the first embodiment. At this time, data is written to one of the two sets of chain buffer memories 40. Therefore, the data number is written in the chain data number storage area 44 of the one chain buffer memory 40 so that the lower M bit data of the reference axis data are chained in ascending or descending order.

In the present embodiment, the fourth control circuit 80d is the chain data number storage area of one chain buffer memory 40.
The data number written in 44 is read according to a predetermined read rule, as in the first embodiment. Then, in the order of the read data numbers, the reference axis data memory
The medium M-bit data of the reference axis data from 10 is directed to the buffer memories 20 and 30 and controlled.

The middle M-bit data of the reference axis data read out in this way is similarly sorted. At this time, data is written to the other of the two sets of chain buffer memories 40. As a result, the data number is written in the chain data number storage area 44 of the other chain buffer memory 40 so that the middle M-bit data of the reference axis data are chained in ascending or descending order.

The fourth control circuit 80d of the embodiment reads the data number thus written in the other chain data number storage area 44 according to a predetermined read rule. Then, the higher order M-bit data of the reference axis data is sequentially read from the reference axis data memory 10 in the order of the read data numbers, and is output to the buffer memories 20 and 30.

Then, the upper M bits of the reference axis data output to the buffer memories 20 and 30 in this way are similarly sorted. At this time, data is written into one of the two sets of chain buffer memories 40. Therefore, in the chain data number storage area 44 of the one chain buffer memory 40, the upper M bits of the reference axis data are written. So that the data is chained in ascending or descending order,
The data number will be written.

In this way, a predetermined digit of the reference axis data is set as a search digit (a digit composed of M-bit data in the embodiment), and the sorting processing of the reference axis data based on each search digit is performed.
The search digit is shifted repeatedly from the lowest search digit of the reference axis data to the highest search digit. As a result, when the sorting process of the reference axis data based on the highest search digit is completed, the data numbers are written in the chain data number storage area 44 so that the reference axis data are linked in ascending or descending order.

Therefore, the third control circuit 80c of the embodiment, after finishing the sorting process of the reference axis data based on the highest search digit,
The data number written in the chain data number storage area 44 is read according to a predetermined read rule. Then, in the order of the read data numbers, the reference axis data memory
Read control to output the reference axis data from 10.

As a result, even when the reference axis data memory 10 is composed of a large number of digits, it is possible to perform high-speed sorting with a simple configuration without increasing the memory capacity of each buffer memory 20, 30, 40. .

Next, a specific operation when sorting the reference axis data in ascending order will be described with reference to FIG. Here, in order to simplify the description, a case will be described as an example in which the reference axis data composed of a ternary number is sorted one digit at a time from the least significant digit.

First, assume that the reference axis data is stored in the reference axis data memory 10 as shown in FIG.

When the first sorting operation is started for the reference axis data thus stored, the variable m representing the search digit is set to 0. Then, the value of the search digit of m = 0 is read out from the reference axis data memory 10 in the order of the data numbers, and the read reference axis data of the search digit of m = 0 is sorted as described above. As a result, the chain data number storage area 44 stores the data number so that the values of the search digit of m = 0 of the reference axis data are linked in ascending order.

Next, the data numbers written in the chain data number storage area 44 are read according to a predetermined read rule, and the reference axis data memory is read in the order of the read data numbers.
The search digit of m = 1 of the reference axis data is read from 10. At this time, the reading order of the reference axis data read from the reference axis data memory 10 is as shown in FIG. 24 (B). As is apparent from the figure, it is understood that the value of the digit of m = 1 of the reference axis data is sorted and read in ascending order according to the value of the search digit of m = 0.

When the read m = 1 search digit value is similarly sorted, the m = 1 search digit value of the reference axis data is chained in ascending order in the chain data number storage area 44. The data number will be stored. Therefore, based on the data number written in the chain data number storage area 44, the reference axis data memory 10
By reading the m = 2 search digit of the reference axis data from, the value of the m = 2 search digit of the reference axis data is read from the reference axis data memory 10 in the order shown in FIG. 24 (C). Will be done.

In this way, the sorting process is repeatedly performed while shifting the search digit from the lowest digit of the reference axis data to the highest digit of the reference axis data by one digit.
When the sorting process of No. 2 is completed, the reference axis data is stored in the chain data number storage area 44 as shown in FIG.
The data numbers are written so that they are linked in ascending order as shown by.

Therefore, the third control circuit 80c determines that the highest search digit m =
After the sorting process of No. 2 is completed, the data numbers written in the chain data number storage area 44 are read in a predetermined reading order, and the reference axis data is read from the reference axis data memory 10. As a result, from the reference axis data memory 10,
The reference axis data is sorted and output in ascending order as shown in FIG.

Here, the case where the reference axis data is sorted in the ascending order has been described as an example, but the reference axis data can be sorted and output in the descending order by repeating the operation of sorting the values of each search digit in the descending order. .

Further, in the present embodiment, the case where two chase buffer memories 40 are provided has been described as an example. However, not limited to this,
For example, after the data number written in the chain bunfer memory 40 is once transferred to another memory, the data number is read from the memory according to a predetermined read rule, and the reference axis data memory 10 is read in the order of the read data numbers. To M-bit data of a predetermined search digit from each buffer memory 20,30
It may be configured to perform read control toward. By doing so, the data sorting speed is reduced, but only one set of the chase buffer memory 40 is required.

Sixth Embodiment FIG. 25 shows a sixth preferred embodiment of the present invention. In the third embodiment, the case where the circuit for sorting the sorting data including the combination information based on the reference axis data is formed using the circuit of the first embodiment has been described as an example. The present embodiment is characterized in that such a sorting circuit is formed by using the circuit of the fifth embodiment.

The sorting circuit of this embodiment comprises an information memory 58 and the circuit shown in the second embodiment.

Then, the reference axis data included in the sorting data output from the external data generating circuit 8 is input to the reference axis data memory 10 and subjected to the sorting process in the same manner as the fifth embodiment. Therefore, the chain buffer memory
In the chain data storage area 44 of 40, the data numbers are stored so that the reference axis data are linked in ascending order or descending order.

Then, the third control circuit 80c reads the data numbers stored in the chain data number storage area 44 in the same manner as in the fifth embodiment, and controls the reading of the combination information from the information memory 58 in the order of the read data numbers. To do. As a result, a series of combination information is sorted and output from the information memory 58 in ascending or descending order based on the reference axis data.

Comparison with the Sorting Circuit of the Present Application The applicant of the present application filed a new sorting circuit in addition to the sorting circuit of the present application on August 31, 1987 (Japanese Patent Application No. 62-217044).

A simple comparison of the sorting time between the sorting circuit according to this prior application and the sorting circuit of the first embodiment of the present application is as follows.

First, assuming that the number of reference axis data to be sorted is N and the number of bits of each reference axis data is M, the sorting processing time (RAM access) is as follows in a simple comparison.

First, in the sorting circuit according to the prior application, the sorting processing time is represented by (4N + 2) × M + N + 4 cycles (1). Since the details of this equation have already been described in the specification of the prior application, the description thereof will be omitted here.

Here, N = 1023, M = 15 bits, RAM access
If the cycle steal is 6.144MHz, the total processing time is 62437 cycles / 6.144MHz = 10.2msec, which is sufficiently long within one field time (about 16.5mmsec).

However, when the number of data increases and N = 2047 and M = 15 bits, this processing time becomes 124901 cycles / 6.144MHz = 20.3msec, which is not enough for one field time. I will end up.

As described above, in the sorting circuit according to the prior application, if the number of data is larger than the number of bits of the data to be sorted, the sorting process cannot be performed in the time for one field, which causes a problem.

In particular, in the three-dimensional image synthesizing apparatus described later, the number of data to be sorted (the number of display polygons in terms of system) tends to increase, so a higher speed sorting circuit is required.

The sorting circuit of the present invention has been made under such a requirement, and when the simple calculation is performed under the same conditions, the sorting processing time is as follows.

First, since the reference axis data memory 10 reads out all the reference axis data once, it requires N cycles.

The fast buffer memory 20 requires N cycles for writing data and 2 ^M cycles for reading when transferring data to the chain buffer memory 50.

The last buffer memory 30 has N cycles for reading for checking data, N cycles for writing data, and for transferring data to the chain buffer memory 40.
Requires 2 ^M cycles.

Further, the chain buffer memory 40 requires N cycles for writing data.

In addition to this, in order to clear the contents of the first buffer memory 20 and the last buffer memory 30 to zero before writing the data to each buffer memory, the first buffer memory 20 is cleared to zero for N cycles, and the last buffer memory 30 is cleared to zero. N cycles are required to clear.

Therefore, to summarize the above, the processing time of 7 × N + 2 × 2 ^M cycles (2) is required for the entire sorting processing work. Therefore, assuming that the number of bits of the reference axis data to be sorted is M = 15, the number N of the description axis data is changed, and the sorting processing time is calculated based on the first and second equations, the prior application The sorting processing time according to the present invention and the processing time of the sorting circuit according to the present invention are shown in the following table.

As is clear from Table 1, when the number of reference axis data to be sorted is small, the processing time of the sorting circuit of the prior application is shorter, but the number of reference axis data to be sorted increases. Accordingly, it will be understood that the processing time of the sorting circuit of the present invention is significantly reduced.

Therefore, according to the present invention, as the number of reference axis data increases, it becomes possible to perform high-speed sorting by significantly reducing the sorting time.

Applications As described above, the sorting circuit according to the present invention can sort a large amount of reference axis data at high speed. Therefore, even if the reference axis data is combined with various information and the sorting data has a large amount of data, various sorting data with such a large amount of data can be sorted at high speed based on the reference axis data. Therefore, for example, it can be widely used for sorting information on a database based on reference axis data such as date and for other purposes.

Concrete Example FIG. 5 shows a preferable concrete example of the three-dimensional image synthesizing apparatus to which the present invention is applied. The apparatus of the embodiment is a polygon information generating circuit 50, a polygon information transferring circuit 52, a sorting circuit S. , Including the polygon display circuit 60, three-dimensional two-dimensional image,
That is, the pseudo three-dimensional image is displayed on the CRT of the polygon display circuit 60.
It is formed so as to display a composite image above.

In the present embodiment, the polygon information generation circuit 50 handles three-dimensional stereoscopic information and performs various conversions such as rotation, parallel movement, perspective, projection, etc., to convert the three-dimensional information to be displayed into a two-dimensional polygon. Converted to combination information, (X,
Y) Coordinates are calculated as polygon information.

The polygon information generation circuit 50 also calculates the display point in the depth direction of each polygon, that is, the Z coordinate of the center of each polygon, as polygon information, and further calculates polygon color information, luminance information, etc. as necessary. Calculate as accompanying information.

In the present embodiment, in order to simplify the description, the following description will be given on the assumption that color information is calculated as the incidental information.

FIG. 6 shows an example of polygon information of the polygon thus calculated.

When the polygon information generation circuit 50 calculates polygon information (XY coordinates at the vertex positions of the polygon, Z coordinates at the center point, and color information) of each polygon in this way, the polygon information transfer circuit 52 causes the polygon information transfer circuit 52 shown in FIG. As shown in, the polygon information of each polygon is separated into Z coordinate data and other data, the Z coordinate data is written in the reference axis data memory 10, and the other data (grouping information) is written. Write to XYRAM58.

In this way, each time polygon information of each polygon is calculated and output from the polygon information generation circuit 50, the Z coordinate of this polygon information is sequentially input into the reference axis data memory 10, and polygons other than the Z coordinate are also input. Information is sequentially input to XYRAM58. At this time, the data number register 54 counts the number of polygons calculated and output from the polygon information generation circuit 50, and detects the number of display polygons for each raster scan.

FIG. 8 shows a sorting circuit S used in the three-dimensional image synthesizing apparatus of the embodiment. The sorting circuit S of the embodiment shows a plurality of polygon information calculated for each screen of the CRT. Sorting is performed in ascending order from the smallest Z coordinate value, and output to the polygon display circuit 60.

Therefore, as shown in Fig. 9, the X-axis is set so that the Z coordinate increases in the depth direction with the CRT screen as the reference point.
When the three-dimensional coordinates of Z are set, the sorting circuit S outputs the polygons displayed in front of the screen, that is, polygon information having a high priority in order.

Then, the polygon display circuit 60 synthesizes the polygon information of each polygon thus output based on the priority thereof, and, for example, when a plurality of polygons are superimposed and displayed, the polygon information is displayed. A three-dimensional image is composed so that a polygon with a high priority is preferentially displayed.

Polygon Information Generation Circuit FIG. 10 shows a specific configuration of the polygon information generation circuit 50 applied to the airplane simulator, and the polygon information generation circuit 50 of the embodiment is used for various flights during flight. The simulation image of the condition is calculated and output.

First, the three-dimensional arithmetic circuit 50-4 assumes a moving coordinate system whose origin is an airplane.

Then, when the moving coordinates representing the current position of the airplane are output from the main CPU circuit 50-2, the three-dimensional arithmetic circuit 50
-4 reads out predetermined polyhedron data from the three-dimensional information memory 50-3. In the embodiment, the three-dimensional information memory 50
Since the information written in -3 is expressed using a fixed coordinate system, the three-dimensional arithmetic circuit 50-4 converts the information read from the three-dimensional information memory 50-3 into coordinate data of the moving coordinate system. There is a need to.

This conversion can be realized by a combination of two calculation elements of rotation and translation of coordinates, and in the process of this calculation, information (Z <0, etc.) which is found not to be in the field of view of the pilot is removed. To be done. The status data obtained by the conversion is output to the main CPU circuit 50-2. Then, the coordinate-converted pieces of polyhedron information are perspective-projected toward the viewpoint of Z <0 assuming that the display screen is on the plane Z-0.

By such perspective projection conversion, each polyhedron data is represented as a collection of point information obtained by converting each vertex coordinate of the polyhedron into two dimensions of X and Y.

Further, in performing such perspective projection conversion, the distance between the viewpoint and each vertex coordinate of the polyhedron is obtained.

Then, the two-dimensional point coordinates (coordinates of the vertices of the polyhedron) obtained by the perspective projection transformation are classified for each polygon representing the surface of the polyhedron, and whether the classified polygons are in the visual field of the pilot, that is, the visual field of the screen. Check whether or not, and remove polygons that do not fit in the field of view.

After that, the three-dimensional arithmetic circuit 50-4 determines, for a polygon within the acceptance coordinate range, the value of the Z coordinate at the center point of the polygon as a representative value.

At the same time, the three-dimensional arithmetic circuit 50-4 calculates the incidental data of each polygon within the acceptance coordinate range, that is, color information in the embodiment.

Then, the three-dimensional arithmetic circuit 50-4 outputs the XY coordinates of the vertices of the respective polygons thus obtained, the Z coordinate of the center position thereof, and the color information as polygon information for each polygon.

The polygon information of each polygon output from the polygon information generating circuit 50 of the embodiment is composed of 17 words, one word of which is the Z coordinate of the center point, and the remaining 16 words are the XY coordinates of the vertices of the polygon. It is used to represent color information.

The 1 word is composed of 16 bits.

In this way, the polygon information generation circuit 50 of the embodiment,
The situation in which the pilot is in the visual field is converted into a plurality of polygon combination information, and the polygon information of each polygon is output to the sorting circuit S in order.

Here, since each polygon is displayed closer to the screen as the Z coordinate value included in the polygon information is smaller, the smaller the Z coordinate value included in the polygon information is, the higher the priority of the polygon is. become. Therefore, if the polygon information of each polygon that is randomly output in this way is sorted in ascending order of the Z coordinate value, it becomes possible to easily and quickly synthesize the three-dimensional image by the polygon display circuit 22.

Sorting Circuit The sorting circuit of the present invention is characterized by sorting a plurality of data including predetermined reference axis data based on the reference axis data.

FIG. 8 shows a specific configuration of the sorting circuit S according to this embodiment.

The sorting circuit S includes a reference axis data memory 10 and
Of the polygon information of one screen including the XYRAM 58 used as an information memory and output from the polygon information generation circuit 50, Z as the reference axis data.
The axis information is written in the reference axis data memory 10, and the remaining information is written in the XYRAM 58.

Here, the reference axis data memory 10 includes a first buffer memory 20, a last buffer memory 30 and a chain buffer memory 40 together with a group of sortings.
It is formed as RAM70.

Then, the sorting control circuit 80 uses this sorting
The writing and reading of the data in the RAM 70 are controlled, and the data number is written in the chain buffer 40 so that the reference axis data are linked in ascending order.

Then, the data number written in the chain buffer 40 is read according to the above-mentioned predetermined reading rule. Then, the polygon information of the polygon for one screen is read from the XYRAM 58 in the order of the read data numbers.

In this way, the apparatus of this embodiment can sort the polygon information for one screen output from the polygon information generating circuit 50 in ascending order based on the Z coordinate and output it to the polygon display circuit 60. .

Hereinafter, the specific circuit configuration will be described in detail by taking the sorting circuit of the third embodiment (sorting circuit shown in FIG. 19) as an example.

(A) First control circuit 80a FIG. 11 shows a specific circuit configuration of the first control circuit 80a shown in FIG. 19, and FIG. 12 shows a flowchart showing its operation. Has been done.

The first control circuit 80a sequentially reads the Z-axis data written in the reference-axis data memory 10 in the order of the data numbers. Then, using the read Z-axis data as an address, the corresponding data number is written to the first buffer memory 20 and the last buffer memory 30. At the same time, when the data number in the last buffer memory 30 is updated and recorded, the data number after the update is written in the chain buffer memory 40 by using the data number before the update as an address.

In this embodiment, the first control circuit 80a includes a data number pointer 12, a data number register 54, a comparison / determination circuit 110, and a step 1 control circuit 112.

Here, the data number pointer 12 is formed so as to output a data number of 1 to N as the write / read address of the reference axis data memory 10 as described above.

Therefore, when the Z-axis data is output from the reference axis data memory 10 to the buffer memories 20, 30 and 40, the data number pointer 12 outputs the data numbers 1, 2, 3 as shown in FIG. The output is sequentially incremented in the order of, ....

As a result, the Z-axis data is sequentially output from the reference axis data memory 10 to the address input terminals of the buffer memories 20 and 30 in the order of the data numbers and to the step 1 control circuit 112.

At this time, the data number output from the data number pointer 12 is output to the data input terminal I of the first buffer memory 20, the last buffer memory 30, and the chain buffer memory 40, and also to the comparison / determination circuit 110. Has been done.

Therefore, in the respective data number storage areas 24, 34 in the first buffer memory 20 and the last buffer memory 30,
For example, as indicated by the flow 1000 in FIG. 12, the reference axis data input to the address input terminal A is used as a write address, and the data number input to the data input terminal I is written and stored.

At this time, when the data number in the last data number storage area 34 is updated and recorded, the data before the update is output to the output terminal O
Is output to the address input terminal A of the chain buffer memory 40.

Therefore, as shown in the flow 1100 of FIG. 12, the chain data number storage area 44 of the chain buffer memory 40 outputs the data number before update output from the last buffer memory 30 as an address from the data number pointer 12. The new data number will be written and stored.

Such data transfer / writing work is repeatedly performed each time a new data number is incrementally output from the data number pointer 12.

Then, the comparison / determination circuit 110 directs the data to the step 1 control circuit 112 when the data number incremented and output from the data number pointer 12 matches the CRT-screen polygon information number output from the data number register 54. Output the transfer control end signal. As a result, the step 1 control circuit 112 finishes a series of data writing operations to the buffer memories 20, 30 and 40.

Next, the sorting circuit switches to the operation of step 2. Then, using the data numbers stored in the respective data number storage areas 34 of the last buffer memory 30 as write addresses, the data numbers in the data number storage areas 24 in the first buffer 20 having a predetermined correspondence relationship are set to the chain buffer memory 40. A series of operations for writing data in the data number storage area 44 inside is started.

(B) Second control circuit 80b FIG. 13 shows a specific circuit configuration of the second control circuit 80b that performs the transfer control of step 2 as described above.
FIG. 14 shows a flowchart showing the operation.

The second control circuit 80b includes a step 2 control circuit 210,
It includes a start address selector 212, a start address pointer 214, and address pointers 22 and 32.

Then, when the operation of step 2 is started, the step 2 control circuit 210 resets the address pointers 22 and 32 to "0" according to the flow 2000 shown in FIG. Then, it is determined whether or not a data number is written in the first data storage area 24 designated by the "0" address output from the address pointer 22. At this time, if the data number is not stored in the address 0, the address pointer 22 is incremented, and the data number is stored in the first data number storage area 24 designated by the incremented new address. Whether or not it is determined. Such a discrimination operation is repeated according to the flow 2100 shown in FIG. 14 until the first data number storage area 24 in which the data number is stored is detected.

Then, when the first data number storage area 24 in which the data number is stored is detected, the start address pointer 310 is set with the data number at that time as the start address.
Set to. Therefore, for example, taking the case shown in FIG. 3 as an example, from the first data number storage area 24 in which the smallest reference axis data is stored (in this case, the storage area 24 designated by address 0), the reference axis data is stored. The data number "5" corresponding to is read and set in the start address pointer 310 as the start address.

In this way, when the start address is set,
Next, in accordance with the flow 2200 of FIG. 14, the data number stored in the last data number storage area 34 is used as a write address, and the data number stored in the first data number storage area 24 having a predetermined correspondence with this is set to A series of operations of writing to the data number storage area 44 is repeated. As a result, for example, as shown in FIG. 3, data numbers are written in the chain data number storage area 44 so that the reference axis data (Z axis data in this case) are linked in ascending order. .

At this time, for example, as shown in FIG. 4, when there is a storage area in which the data number is not written in the data number storage areas 24, 34, the first data is processed according to the flow 2300 shown in FIG. While determining whether or not a data number has been written in the number storage area 24, 24
The address pointer 24 is incremented until is detected.

Then, at the same time when the first data number storage area 24 in which the data number is stored is detected, the data number is similarly written to the chain data number storage area 44 in accordance with the flow 2200.

(C) Flag memory 214 By the way, when the reference axis data is sorted in units of hundreds or thousands, the first data number storage area 24 in which the reference axis data is written is detected to some extent. It takes a lot of time. However, considering that a series of sorting operations must be completed within one field time (1/60 second) in a three-dimensional image device, the detection time becomes a non-negligible value.

For this reason, in the present embodiment, the flag memory 214 is provided in order to greatly shorten the detection time and to perform the sorting at a higher speed.

FIG. 16 shows the configuration of the flag memory 214 in association with the first data number storage area 24.

This flag memory 214 has a plurality of 1-bit flag storage areas 214a corresponding to 1: 1 in each first data number storage area 24.
When data is stored in, the flag is formed to be set in the corresponding 1-bit flag area 214a.

In the embodiment, the flag memory 214 is designated by a flag address with eight 1-bit flag areas as a group unit, and outputs flag information in a group unit (8-bit data) from a group of flag areas designated by the flag address. Is formed.

Therefore, for example, when the flag address 000H is designated, the data number is written in the 8 bits of the first data storage area 24 designated by the addresses 0000H to 0007H from the 8-bit flag information output from the flag memory 214. It is possible to determine at once whether or not there is a rare storage area.

When a flag indicating the writing of the data number is detected during the detection of the data number storage area 24 in which the data number is written using such a flag memory 214, the flag address is designated by the flag address at this time. The 8-bit flag information is written in the shift register 210a as shown in FIG.

Then, the step 2 control circuit 210 causes the shift register 210
First data number storage area where the data number is written by shifting the contents of a to the right bit by bit.
Detect 24.

In this way, the 210 of the embodiment sequentially reads the contents of the flag memory 214 in increments of 8 bits while sequentially incrementing the flag address of the flag memory 214 from 000H.
The fast data number storage area 24 in which the data number is written is detected at high speed.

Note that the writing of the flag to the flag memory 214 is performed by the first
This is performed by the step 1 control circuit 112 shown in FIG. That is, the step 1 control circuit 112 writes the data number in the first data number storage area of the first buffer memory 20 and at the same time sequentially sets the corresponding flags in the flag memory 214.

By doing so, the operation of step 2 shown in FIG. 14, that is, the data writing operation from the respective buffer memories 20 and 30 to the chain buffer memory 40 can be performed at a higher speed.

If such a flag memory 214 is used, it is not necessary to clear the buffer memories 20 and 30 to zero by clearing the flag memory 214 to zero.

In addition, in the present embodiment, the reason why the group unit of the flag memory 214 designated by the flag address is 8 bits is that it is considered to be optimum from the physical data size of the memory and the stochastic viewpoint. is there.

For example, let us consider the problem of how many bit units should be read to minimize the read time when 2 ¹¹ data are randomly written to 2 ¹⁵ addresses. At this time, if the bit unit designated by each flag address is calculated as 16 bits, 8 bits, 4 bits, 2 bits,
The 4-bit unit is the minimum. However, since the data may overlap the same address, the minimum value seems to come when the bit unit specified by the flag address is 4 bits and 8 bits. I chose the bit unit.

(D) Third control circuit 80c As described above, when the data numbers are written in the respective data number storage areas 44 in the chain buffer memory 40 so that the reference axis data are linked in ascending order, Then, the operation of step 3 of reading the written data numbers according to a predetermined reading rule and sorting and outputting the polygon information from the XYRAM 58 in the order of the read data numbers is started.

FIG. 17 illustrates a specific circuit configuration of the third control circuit 80c that performs the operation of step 3 as described above.
FIG. 8 shows a flowchart showing the operation.

In the present embodiment, the third control circuit 80c includes a step 3 control circuit 312, a data number counter 314, and a comparison / determination circuit 31.
6, address pointer 42, start address pointer 310,
It includes a selector 318 and a latch 320.

Then, when the operation of step 3 is started, the step 3 control circuit 312 first resets the address pointer 42 and the data number counter 314. Next, the selector 318 is switched to the side of the start address pointer 310, and the data number preset in the start address pointer 310 is output to the XYRAM 58 via the selector 318 and the latch 320 as the start address.

Thus, for example, when the data number "5" is set as the start address as shown in FIG. 3, the XYRAM 58 outputs the polygon information specified by the data number "5". become.

Further, in synchronization with such a read operation, the value of the data number counter 314 is incremented by 1, and at the same time, the data number output from the latch 320 is set in the address pointer 42 as the next read address.

In this way, when the first polygon information is read,
Next, the step 3 control circuit 312 causes the selector 318 to move the chain buffer memory 40 from the starter address pointer 310 side.
Switch to the side. Then, the step 3 control circuit 312
According to the flow 3000 shown in FIG. 8, polygon information is sorted and output from the XYRAM 58 based on the Z-axis data.

That is, when a data number is output from the address pointer 42 as a read address, the data number is read from the chain data storage area 44 designated by the read address via the selector 318 and the latch 320. The polygon information is output from the XYRAM 58 using the read data number as a read address, and the data number is set in the address pointer 42 as a new read address.

The sorting circuit of the embodiment repeats such a polygon information reading operation.

At this time, the data number counter 314 counts the number of times the XYRAM 58 is accessed, that is, the number of polygon information sorted and output from the XYRAM 58, and outputs the count value to the comparison and determination circuit 316.

Then, the comparison / determination circuit 316 uses the data number counter 314.
When the value of is in agreement with the polygon information previously counted from the data number register 54, the end signal is output to the step 3 control circuit 312.

In this way, the sorting circuit of this embodiment completes a series of sorting operations.

It is needless to say that the present invention is not limited to the above-described embodiments, and various modifications can be made within the scope of the gist of the present invention.

[Effects of the Invention] As described above, according to the present invention, a large number of reference axis data can be sorted and output at high speed with a simple circuit.

In particular, according to the present invention, when the number of reference axis data is large relative to the number of bits of the reference axis data, the sorting operation can be performed at high speed, which is extremely effective when a large number of data are targeted for sorting. Will be things.

Further, according to the present invention, even when the reference axis data is combined with various kinds of information and the sorting data has a large amount of data, such sorting data having a large amount of data is quickly sorted based on the reference axis data. Therefore, it can be widely used for various purposes.

In particular, according to the invention of claim (1), a memory for storing the input reference axis data is unnecessary, and the sorting can be performed by a simpler circuit.

Further, according to the inventions of claims (2) and (3), even if the number of digits of the reference axis data is long, it is not necessary to increase the memory capacity of each buffer memory, and sorting can be performed with a simpler circuit. It becomes possible to do.

[Brief description of drawings]

FIG. 1 is an explanatory diagram showing a basic configuration of a sorting circuit according to the present invention, FIG. 2 is an explanatory diagram showing a data transfer operation from a reference axis data memory to each buffer memory, FIG. 3 and FIG. FIG. 5 is an explanatory diagram showing a data transfer operation from the first buffer memory and the last buffer memory to the chain buffer memory. FIG. 5 is a block circuit diagram showing an example of a three-dimensional image synthesizing apparatus to which the sorting circuit of the present invention is applied. 7 and FIG. 7 are explanatory diagrams of polygon information calculated and output from the polygon information generating circuit shown in FIG. 5, and FIG. 8 is a block of the sorting circuit of the present invention used in the three-dimensional image synthesizing apparatus shown in FIG. Circuit diagram, FIG. 9 is a three-dimensional conceptual diagram of an image displayed by using the circuit shown in FIG. 5, and FIG. 10 shows a concrete configuration of the polygon information generating circuit shown in FIG. Block circuit diagram, FIG. 11 is a block circuit diagram showing an example of the circuit configuration of a sorting circuit of the present invention, FIG. 12 is a flow chart diagram showing the operation of the circuit shown in FIG. 11, and FIG. 13 is a sorting circuit of the present invention. Fig. 14 is a block circuit diagram showing an example of a concrete circuit configuration of Fig. 14, Fig. 14 is a flowchart showing the operation of the circuit shown in Fig. 13, and Fig. 15 is a flag registered in the shift register of the circuit shown in Fig. 13. FIG. 16 is an explanatory view showing the configuration of the flag memory used in the circuit shown in FIG. 13 in association with the first data number storage area, and FIG. 17 is a concrete view of the sorting circuit of the present invention. FIG. 18 is a block circuit diagram showing an example of the circuit configuration, FIG. 18 is a flow chart diagram showing the operation of the circuit shown in FIG. 17, FIG. 19 is an explanatory diagram of a preferred third embodiment of the present invention, and FIG. Sort data in descending order FIG. 21 is an explanatory view showing the operation of transferring data from the first buffer memory and the last buffer memory to the chain buffer memory in the case of the following: FIG. 21 is an explanatory view of the preferred second embodiment of the present invention, and FIG. Of the preferred fourth embodiment of the present invention, FIG. 23 is an illustration of the preferred fifth embodiment of the present invention, and FIG. 24 shows (A), (B), (C) and (D). 23 is an explanatory view showing an example of a sorting operation of the sorting circuit shown in FIG. 23, and FIG. 25 is an explanatory view of a sixth preferred embodiment of the present invention. 10 …… Reference axis data memory, 12 …… Data number pointer, 13 …… Data number counter, 20 …… First buffer memory, 24 …… First data number storage area, 30 …… Last buffer memory, 34 …… Last data Number storage area, 40 ... chain buffer memory, 44 ... chain data number storage area, 58 ... information memory 80 ... sorting control circuit, 80a ... first control circuit, 80b ... second control circuit, 80c ... third control circuit, 80d ... fourth control circuit.

Claims (6)

[Claims] 1. A circuit for inputting a plurality of data and predetermined reference axis data corresponding to the data, and sorting the plurality of data based on the reference axis data. An information memory for storing a plurality of data and a data number common to the reference axis data, and a sorting means for inputting the reference axis data, wherein the sorting means includes each input reference axis. It has a data number generating means for generating a data number corresponding to the data, and a first data number storage area whose address is designated based on the reference axis data, and the reference axis data corresponding to each storage area is input first. At this time, a first buffer memory for storing the data number generated by the data number generating means in this storage area, and the reference axis data A last buffer which has a last data number storage area whose address is designated based on the reference axis data corresponding to each storage area and which updates and stores the data number generated by the data number generating means in this storage area. A memory, a chain buffer memory having a chain data number storage area whose address is designated based on the data number, and a chain data number designated by the data number before update every time the data number of the last buffer memory is updated. First control means for writing a new data number to be updated in the storage area, and designation by the data number stored in the last data number storage area after writing the data number to the first buffer memory and the last buffer memory The last data is stored in the chain data number storage area The data number stored in the first data number storage area, which has a predetermined correspondence with the number storage area, is written so that the reference axis data is linked in the chain data number storage area in ascending or descending order. Second
And a third control means for reading the data numbers written in the chain data number storage area according to a predetermined read rule and reading the data from the information memory in the order of the read data numbers. A sorting circuit, which outputs data based on reference axis data. 2. A circuit for sorting a plurality of reference axis data consisting of a plurality of digits, wherein the data number generating means generates a data number corresponding to each input reference axis data, and each of the reference axis data, A reference axis data memory for storing the data corresponding to the data number, and a plurality of digits of the reference axis data output from the reference axis data memory are divided into a plurality of search groups of 1 to a plurality of digits. Has a first data number storage area whose address is designated based on the value of, and when each search group corresponding to each storage area is first input, the data number generated by the data number generating means is stored in this storage area. And a last data number whose address is specified based on the value of each search group output from the reference axis data memory. No. storage area, and each time each search group corresponding to each storage area is input, a last buffer memory that updates the data number generated by the data number generating means in this storage area, and an address based on the data number Two chain buffer memories each having a designated chain data number storage area, and each time the data number of the last buffer memory is updated, the at least 2 designated by the data number before update
First control means for writing a new data number to be updated in any one of the chain data number storage areas in one chain buffer memory, and after the completion of writing the data number in the first buffer memory and the last buffer memory , A chain data number storage area specified by the data number stored in the last data number storage area, and stored in the first data number storage area having a predetermined correspondence with the last data number storage area. Second control means for writing data numbers so that the values of the respective search groups are linked in ascending or descending order in any one of the chain data number storage areas, and the reference axis data. Update the search group that is the target of the search from the lower digit to the upper digit, The search group which is another search target is read out from the reference axis data memory in the order in which it is written in the chain data number storage area by the second control means, and the first control means and the second control means are read. Fourth control means for repeatedly performing the processing according to (4) while switching the chain buffer memory until the search group located on the uppermost side of the reference axis data, and after the sorting processing of the uppermost side search group is completed,
Third control means for reading out the data number written in the corresponding chain data number storage area according to a predetermined reading rule, and sorting and outputting each reference axis data from the reference axis data memory in the order of the read data number. A sorting circuit characterized by that. 3. A circuit which sorts a plurality of data and a predetermined reference axis data composed of a plurality of digits corresponding to the data, wherein the plurality of data are combined with the plurality of data and the reference axis data. An information memory for storing the data number corresponding to a common data number, and a sorting means for inputting the reference axis data, wherein the sorting means generates a data number for generating the data number corresponding to each reference axis data. Generating means, a reference axis data memory for storing each of the reference axis data in association with the data number thereof, and a plurality of digits of the reference axis data output from the reference axis data memory. When divided into search groups, it has a first data number storage area whose address is specified based on the value of each search group and corresponds to each storage area. When each search group is first input, a first buffer memory for storing the data number generated by the data number generating means in this storage area, and an address based on the value of each search group output from the reference axis data memory And a last buffer number storage area in which each number of search groups corresponding to each storage area are input, and a last buffer memory which updates and stores the data number generated by the data number generating means in this storage area. , Two chain buffer memories each having a chain data number storage area whose address is designated based on the data number, and each time the data number in the last buffer memory is updated, the data number before the update is designated At least 2
First control means for writing a new data number to be updated in any one of the chain data number storage areas in one chain buffer memory, and after the completion of writing the data number in the first buffer memory and the last buffer memory , A chain data number storage area specified by the data number stored in the last data number storage area, and stored in the first data number storage area having a predetermined correspondence with the last data number storage area. Second control means for writing data numbers so that the values of the respective search groups are linked in ascending or descending order in any one of the chain data number storage areas, and the reference axis data. Change the search group that is the target of the search from the lower digit to the upper digit, The search group which is another search target is read out from the reference axis data memory in the order in which it is written in the chain data number storage area by the second control means, and the first control means and the second control means are read. Fourth control means for repeatedly performing the processing according to (4) while switching the chain buffer memory until the search group located on the uppermost side of the reference axis data, and after the sorting processing of the uppermost side search group is completed,
A third control means for reading the data number written in the corresponding chain data number storage area according to a predetermined read rule and reading the data from the information memory in the order of the read data number; A sorting circuit characterized by performing sorting output based on axis data. 4. A sorting circuit according to claim 1, wherein the data number generating means is formed by using a data number pointer. 5. A sorting circuit according to claim 1, wherein said data number generating means is formed by using a counter. 6. The information memory according to any one of claims (1) and (3) to (5), wherein at least one of a plurality of three-dimensional information (X, Y, Z) is stored in the information memory. X, Y) two-dimensional information is stored in the order of data numbers, the sorting means receives the Z-axis data included in the three-dimensional information as reference axis data, and the three-dimensional information included in the information memory A sorting circuit, which outputs sorting in ascending or descending order based on Z-axis data.