Generating angular coordinate of raster scan of polar-coordinate addressed memory

• US 4,434,437 A
• Filed: 08/31/1981
• Issued: 02/28/1984
• Est. Priority Date: 01/26/1981
• Status: Expired due to Term

• Current Assignee: RCA Corporation
• Original Assignee: RCA Corporation
• Inventors: Strolle, Christopher H., Smith, Terrence R.
• Primary Examiner(s): Martin, John C.
• Assistant Examiner(s): Coles, Edward L.
• Application Number:
  US06/298,269
• Time in Patent Office: 911 Days
• Field of Search: 358/140, 340/727, 340/728, 343/6 TV, 343/5 SC, 360/9.1, 360/33.1, 364/731, 364/815
• US Class Current: 348/442
• CPC Class Codes: G06F 1/02 Digital function generators
• CPC Class Codes: G06F 1/0307 Logarithmic or exponential functions G06F1/0314, G06F1/035 take precedence
• CPC Class Codes: G06F 17/175 of multidimensional data
• CPC Class Codes: G06F 2101/04 Trigonometric functions
• CPC Class Codes: G06F 2101/08 Powers or roots
• CPC Class Codes: G06F 2101/10 Logarithmic or exponential functions
• CPC Class Codes: G06T 3/606 by memory addressing or mapping
• CPC Class Codes: G11C 7/00 Arrangements for writing information into, or reading information out from, a digital store G11C5/00 takes precedence; auxiliary circuits for stores using semiconductor devices G11C11/4063, G11C11/413
• CPC Class Codes: G11C 8/04 using a sequential addressing device, e.g. shift register, counter
• CPC Class Codes: G11C 8/16 Multiple access memory array, e.g. addressing one storage element via at least two independent addressing line groups
• CPC Class Codes: H04N 9/78 for separating the brightness signal or the chrominance signal from the colour television signal, e.g. using comb filter

Abstract

Graphics for television display which emphasize circles, ellipses, circular or elliptical arcs, and the radii of circles or ellipses are conveniently stored in image memories addressable in polar coordinates. Television images which are to be rotated are conveniently stored in such memories, so the angular coordinate of the image memory addresses can be incremented or decremented to rotate the image with hardware as simple as a single adder. To read image memories addressed in polar coordinates, the Cartesian coordinates descriptive of television raster display are scan-converted to polar coordinates. This scan conversion takes place in real time at video sampling rates. The generation of the angular coordinate of the polar coordinates is facilitated by dividing one Cartesian coordinate by another by differentially combining their logarithms as found from read-only-memory table look-up, then finding an arc tangent from the logarithm of their difference as found from further read-only-memory table look-up. Since the non-linearities of the logarithm and arc tangent functions tend to track each other to a degree, combining the anti-logarithm and arc tangent look-up steps in a single read-only memory provides greater angular resolution for number of bits used in the read-only-memory input addresses.

Claims

1. Scan conversion apparatus comprising:

means for parallelly supplying streams of first and second binary numbers descriptive of raster scanning in first and second orthogonal Cartesian coordinates, the first coordinates describing pixel positions along scan lines and the second coordinates describing scan line positions in the field of raster scan;

means for generating pairs of logarithms, each logarithm in a pair being generated responsive to a respective one of the first and second binary numbers appearing in said parallely supplied streams at successive times;

means linearly combining the logarithms in each of said pairs of logarithms as they are generated, for generating the difference of the logarithms of concurrently supplied first and second binary numbers; and

first read-only memory means responsive to said differences for supplying binary numbers descriptive of raster scan in terms of angular position from a reference position in said raster scan.

2. Scan conversion apparatus as set forth in claim 1 further including:

means for supplying binary numbers programmably offset from the binary numbers supplied by said first read-only memory means.

3. Scan conversion apparatus as set forth in claim 1 wherein said means for parallelly supplying streams of first and second binary numbers is of a type supplying them in two'"'"'s complement form;

wherein said means for linearly combining pairs of logarithms consists of a digital adder; and

wherein said means for generating pairs of logarithms comprises;

means for selectively complementing the less significant bits of said first binary numbers in two'"'"'s complement form responsive to their respective most significant bits being ONE'"'"'s and forwarding them without complementing responsive to their respective most significant bits being ZERO'"'"'s;

second read only memory means, responsive to the output from this means for selectively complementing and forwarding without complementing, for supplying the logarithm of the reciprocal of this output as input to said digital adder;

means for selectively complementing the less significant bits of said second binary numbers in two'"'"'s complement form responsive to their respective most significant bits being ONE'"'"'s and forwarding them without complementing responsive to their respective most significant bits being ZERO'"'"'s; and

third read-only memory means, responsive to the output from this means for selectively complementing and forwarding without complementing, for supplying the logarithm of this output as input to said digital adder.

4. In combination:

a memory for storing data addressed in first and second coordinates, which second coordinates are angular coordinates;

raster generator means for generating a description of raster scan in x and y Cartesian coordinates;

scan conversion means for converting said description of raster scan in x and y Cartesian coordinates to a description of raster scan in said first and second coordinates, which description in said first and second coordinates is used to address said memory for storing data, thereby to raster scan the data stored in said memory;

means, included in said scan conversion means, for supplying from read-only memory respective logarithmic responses to said x and y Cartesian coordinates applied as input addresses;

means, included in said scan conversion means, for linearly combining those logarithmic responses to obtain logarithms descriptive of one of said x and y Cartesian coordinates divided by the other;

means included in said scan conversion means, for supplying from further read-only memory said angular coordinates as the arc tangents of the anti-logarithms of said logarithms descriptive of one of said x and y Cartesian coordinates divided by the other, which logarithms are applied as input addresses to said further read-only memory; and

means, included in said scan conversion means, for determining said second coordinates from said arc tangents.

5. A combination as set forth in claim 4 wherein said memory for storing data stores television image data, said combination being included in a television display system together with:

a display device having a horizontal deflection system, having a vertical deflection system and having a video drive input;

a horizontal sweep generator generating horizontal deflection signals applied to said horizontal deflection system for causing horizontal deflection of trace on said display device, which deflection changes in proportion with said x coordinates of raster scan;

a vertical sweep generator generating vertical deflection signals applied to said vertical deflection system for causing vertical deflection of trace on said display device, which deflection changes in proportion with said y coordinates of raster scan; and

means, responsive to output from said memory for storing data, for generating video drive signal applied to the video drive input of said display device over at least a portion of a display.

6. In combination:

a memory for storing data addressed in angular coordinates and in coordinates orthogonal to said angular coordinates;

raster generator means for generating a description of raster scan in a two'"'"'s complement x coordinate and a two'"'"'s complement y coordinate;

means responsive to said x and y coordinates for generating said coordinates orthogonal to said angular coordinates, which are applied to said memory for storing data for addressing that memory in coordinates orthogonal to said angular coordinates;

means for exclusive-ORing the most significant or sign bit of said x coordinate with each of its other bits, and

means for obtaining logarithms of the signal samples thus generated;

means for exlusive-ORing the most significant or sign bit of said y coordinate with each of its other bits, and

means for obtaining logarithms of the reciprocal of the signal samples thus generated;

means for linearly combining the logarithms, and

means for obtaining from table look-up memory the arc tangents of the anti-logarithms of the signal samples thus generated were x and y descriptive of one quadrant of the angular coordinates;

means for specifying said angular coordinates in two'"'"'s complement form, including

means responsive to the most significant bit of one of said x and y coordinates for determining the most significant bit of said angular coordinates absent rotation of the data read from said memory storing data, including

means responsive to exclusive OR of the most significant bits of said x and y coordinates for determining the secondmost significant bit of said angular coordinates absent rotation of the data read from said memory for storing data, including

means dependent on that secondmost significant bit for selectively complementing said arc tangents of anti-logarithms of signal samples to provide the bits of lesser significance in said angular coordinates absent rotation of the data read from said memory for storing data, and where the data read from said memory for storing data are to be rotated including

means for offsetting the two'"'"'s complement number thusfar formed by combination with another two'"'"'s complement number indicative of the degree of data rotation, thereby to generate addresses in angular coordinates which are applied to said memory for storing data for completing the addressing of that memory.

7. A combination as set forth in claim 6 wherein said memory for storing data stores television image data, said combination being included in a television display system together with:

a display device having a horizontal deflection system, having a vertical deflection system and having a video drive input;

a horizontal sweep generator generating horizontal deflection signals applied to said horizontal deflection system for causing horizontal deflection of trace on said display device, which deflection charges in proportion with said x coordinates of raster scan;

a vertical sweep generator generating vertical deflection signals applied to said vertical deflection system for causing vertical deflection of trace on said display device, which deflection changes in proportion with said y coordinates of raster scan; and

means, responsive to output from said memory for storing data, for generating video drive signal applied to the video drive input of said display device over at least a portion of a display.

8. In the combination of

means for generating a description of a scanning point in Cartesian coordinates, one of said Cartesian coordinates being an x coordinate in two'"'"'s complement form and the other being a y coordinate in two'"'"'s complement form, and means for converting said Cartesian coordinates to angular coordinates, the improvement wherein said means for converting comprises:

means for calculating said angular coordinates from the logarithm of the magnitude of one of said x and y coordinates divided by the magnitude of the other;

means linearly combining logarithmic functions of said x and y coordinates for approximating the logarithm of one of said x and y coordinates divided by the other;

means for providing table look-up of logarithmic functions of said x and y coordinates responsive to first and second signals respectively, which means for providing avoids the problem of dividing by zero by including, in addition to

read-only memory means for storing logarithm look-up tables,

means exclusive-ORing the most significant bit of said x coordinate with each of its less significant bits to generate a first set of input signals for said read-only memory means, and

means exclusive-ORing the most significant bit of said y coordinate with each of its less significant bits to generate a second set of input signals for said read-only memory means.

9. Apparatus for calculating a function of the angle between first and second orthogonal vectors, comprising:

means for generating a digital electric signal representation of the amplitude of said first vector;

means for generating a digital electric signal representation of the amplitude said second vector;

read-only memory receptive of said digital electric signal representation of the amplitude said first vector for responding with a digital electric signal representation of the logarithm of the amplitude of said first vector;

read-only-memory receptive of said digital electric signal representation of the amplitude of said second vector for responding with a digital electric signal representation of the logarithm of the reciprocal of the amplitude of said second vector;

an adder adding the digital electronic signal representations of the logarithm of the amplitude of the first vector and of the reciprocal of the amplitude of the second vecotor for developing a digital electric signal representation of the quotient of the amplitudes of said first and second vectors; and

read-only memory receptive of the digital electric signal representation of the quotient of the amplitudes of said first and second vectors for supplying a digital electric signal representation of the associated value of the function of the angle between said first and second vectors.

10. Apparatus as set forth in claim 9 wherein said read-only memory receptive of the digital electric signal representation of the quotient of the amplitudes of said first and second vectors supplies digital electric signal representative of the angle itself between said first and second vectors.