System and method for local storage of image data during object to image mapping

• US 5,870,105 A
• Filed: 05/31/1996
• Issued: 02/09/1999
• Est. Priority Date: 05/31/1996
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Jensen, Philip E.
• Primary Examiner(s): Hong, Stephen S.
• Application Number:
  US08/658,905
• Time in Patent Office: 984 Days
• Field of Search: 345/421, 345/422, 345/424, 345/427, 345/429, 345/433, 345/436, 345/437, 345/438, 345/439, 345/441, 345/121, 345/127, 345/419, 345/428
• US Class Current: 345/441
• CPC Class Codes: G06T 3/4007 based on interpolation, e.g. bilinear interpolation image demosaicing G06T3/4015; edge-driven or edge-based scaling G06T3/403

Abstract

A hybrid object to image mapping system and method includes a fragment generator that can be employed in conjunction with an interpolator within an image accelerator. The fragment generator includes a forward mapping mechanism for forward mapping an object data array from object space to image space so as to generate an object address set including image space addresses for each of the object data points, a pixel traversal mechanism for receiving and traversing the object address set to determine what pixels in the image space are located within an area of the object data set, and a reverse mapping mechanism for receiving pixel address data and determining at least two distances for each of the pixels within the area and for reverse mapping each of the distances from the image space to the object space relative to said data values in the local data buffer. In architecture, the forward mapping mechanism, the pixel traversing mechanism, and the reversed mapping mechanism are preferably pipelined in the foregoing sequential order. Thus, the data values from the object data array and the transformed distance values can be for further processing by a scaling operation such as interpolation or minification with a minimum amount of hardware and without reducing image quality.

Claims

1. A hybrid object to image mapping method for mapping image data on a computer-based system, comprising the steps of:

receiving an object data array comprising a plurality of object data points in object space, each said point having an associated data value;

placing said data values in a local data buffer,

forward mapping said object data array from object space to image space so as to generate an object address set comprising image space addresses for each said object data point;

traversing said object address set to determine which pixels in said image space that are located within an area of said object data set;

determining at least one X and Y distance for each said pixel within said area said pixel being within said image space, said X and Y distance representing said pixel'"'"'s distance from a reference point in said object data set; and

reverse mapping each said distance from said image space to said object space relative to said data values in said local data buffer.

2. The method of claim 1, further comprising the step of interpolating said data values in said local data buffer with said distances in said image space in order to generate intensity values for each said area of said data object set.

3. The method of claim 1, wherein said step of forward mapping and said step of reverse mapping are substantially inverse operations.

4. The method of claim 1, wherein said step of traversing said object data space comprises the step of performing a Jensen Serpentine algorithm.

5. The method of claim 1, wherein said step of traversing said object data space comprises the step of performing a raster scan algorithm.

6. The method of claim 1, wherein said step of traversing said object data space comprises the step of performing a double Breshenham line drawing algorithm.

7. The method of claim 1, wherein said step of forward mapping comprises perspective transformation.

8. The method of claim 2, wherein said step of interpolating comprises the steps of:

generating coefficients based upon said distances; and

performing bi-cubic interpolation on said data values in said local data buffer with said coefficients.

9. The method of claim 2, wherein said step of interpolating comprises bi-cubic interpolation.

10. A method for object to image mapping, comprising the steps of:

forward mapping an object data array from object space to image space so as to generate an object address set having at lease two edges;

traversing said object address set to determine which pixels in said image space that are located within said object address set;

determining a first distance from a first edge of said object address set and a second distance from a second edge of said object address set for each said pixel within said area, said first distance and said second distance representing each said pixel'"'"'s distance from a reference point in said object address set; and

reverse mapping each said first and second distances from said image space to said object space relative to data values in said local data buffer.

11. The method of claim 10, further comprising the step of interpolating data values from said object data array with said first and second distances in said image space in order to generate intensity values for each said pixel in said data object set.

12. The method of claim 10, wherein said step of forward mapping and said step of reverse mapping are substantially inverse operations.

13. A fragment generator for mapping image data, comprising:

a forward mapping mechanism for forward mapping an object data array from object space to image space so as to generate an object address set comprising image space addresses for each said object data point;

a pixel traversal mechanism for receiving and traversing said object address set to determine what pixels in said image space that are located within an area of said object data set; and

a reverse mapping mechanism for receiving pixel address data and determining at least one X and Y distance for each said pixel within said area, said pixel being within said image space, said X and Y distance representing said pixel'"'"'s distance from a reference point in said object data set and for reverse mapping each said distance from said image space to said object space relative to said data values in said local data buffer.

14. The fragment generator of claim 13, wherein said pixel traversal mechanism comprises means for performing a Jensen Serpentine algorithm.

15. The fragment generator of claim 13, wherein said forward mapping mechanism and said reverse mapping mechanism perform substantially inverse operations.

16. The fragment generator of claim 13, wherein said forward mapping mechanism performs rigid body coordinate transformation.

17. The fragment generator of claim 13, further comprising a local data buffer for storing data associated with points of said object data array.

18. The fragment generator of claim 17, further comprising an interpolator for interpolating said data in said local data buffer with distances in said image space in order to generate intensity values for each said pixel in said area of said data object set.

19. The fragment generator of claim 17, wherein said local data buffer comprises cache lines of a length substantially equal to a width of said data object array.

20. The fragment generator of claim 18, wherein said interpolator comprises a coefficient generator configured for generating an interpolation coefficients from said distances and a bi-cubic convolution kernel.