Mapping application for rendering pixel imagery

• US 7,379,063 B2
• Filed: 07/29/2004
• Issued: 05/27/2008
• Est. Priority Date: 07/29/2004
• Status: Active Grant

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: Raytheon Company (Rtx Corporation)
• Inventors: Hoff, Christopher G.
• Primary Examiner(s): Chauhan; Ulka
• Assistant Examiner(s): Chow; Jeffrey J.
• Application Number:
  US10/901,603
• Publication Number:
  US 20060022978A1
• Time in Patent Office: 1,398 Days
• Field of Search: 345/427, 345/648, 345/649, 345/672
• US Class Current: 345/427
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 3/02 Affine transformations for image registration G06T3/147; for image mosaicing G06T3/4038

Abstract

A mapping application relies on a modified affine transformation algorithm to provide near real-time navigation of imagery, track-up capability and integration of segment and picture data. The affine transformation is modified to map a “world space” comprised of a plurality of pixel maps onto a view port. The pixel data for the maps is preferably stored in vertical strips of memory to reduce the likelihood of cache misses. The mapping application is most useful for rendering pixel imagery on a platform with limited processing power, limited memory and small display sizes, e.g., “hand held devices” such as a GPS handset, or Pocket PC.

Claims

1. A memory device encoding a mapping application for use with a display, said mapping application comprising the steps of:

storing a plurality of maps in memory, each said map having its own map space comprising pixel data;

in response to a first input, selecting a plurality of objects assigned to different said maps and arranging them in a world space coordinate system, each said object defining the extent of its map in world space;

in response to a second input, positioning a view port representing a portion of display space within world space;

for each pixel in the view port, assigning said pixel a world space coordinate using a first affine transformation from display space to world space;

for each assigned world space coordinate, determining which objects, if any, intersect the coordinate and for at least a topmost intersecting object determining its map space coordinate using a second object-specific affine transformation from world space to that object'"'"'s map space based on the extent of that object'"'"'s map in world space and sampling the object'"'"'s map pixel data at its determined map space coordinate to assign a value to the associated pixel in the view port so that only object map pixel data that contributes to painting the display within the view port is sampled;

assigning a background value to the pixels in the view port that do not intersect an object; and

painting the display with the map and background pixels assigned to the view port.

2. The memory device of claim 1, wherein the first affine transformation performs a first linear interpolation along a vertical axis of the view port and a second linear interpolation along a horizontal axis of the view port.

3. The memory device of claim 2, wherein the second affine transformation performs a linear interpolation along a vertical axis of the object in map space and a second linear interpolation along a horizontal axis of the object.

4. The memory device of claim 1, wherein the mapping application stores said pixel data for each said map in a plurality of vertical strips, each said vertical strip including multiple partial rows of row-oriented pixel data, in a main memory, a hardware caching operation retrieving pixel data from a sequential range of memory addresses around a most recently accessed address from a vertical strip in main memory and storing the pixel data into a cache memory.

5. The memory device of claim 4, wherein said pixel data is sampled from main memory by,

determining the vertical strip in memory in which the pixel data resides;

converting the map space coordinate into a vertical strip column coordinate; and

sampling the pixel data from the vertical strip at the column coordinate.

6. The memory device of claim 4, wherein the view port can be rotated 0 to 360 degrees to an arbitrary rotation angle within world space, whereby a probability of a cache hit over sill rotation angles of the view port when sampling pixel data is greater than if the pixel data were stored in rows of memory.

7. The memory device of claim 4, wherein first and second pixels stored in the vertical strips in memory are separated by the difference in their horizontal offset plus the difference in vertical rows multiplied by the width of the vertical strip.

8. The memory device of claim 4, whereby storing the pixel data in vertical strips of main memory increases a probability of a cache miss for view port rotations of 0°

and 180° and

reduces a probability of a cache miss for view port rotations of 90° and

270°

when sampling the map pixel data.

9. The memory device of claim 4, wherein each said vertical strip includes pixel data from multiple complete columns and multiple partial rows of equal width.

10. The memory device of claim 1, further comprising for each assigned world space coordinate, if at least one other underlying object intersects the coordinate, determining its map space coordinate using a second object-specific affine transformation from world space to that object'"'"'s map space based on the extent of that object'"'"'s map in world space and sampling the object'"'"'s map pixel data at its determined map space coordinate and arbitrating the overlapping objects by alpha blending the sampled map pixel data for the topmost object and said +at least one underlying objects.

11. The memory device of claim 1, wherein the first affine transformation automatically rotates the view port in world space according to the display'"'"'s orientation so that the direction a user is facing is always upward on the view port.

12. The memory device of claim 1, wherein some of the maps are 1-bit per pixel maps of a line segment data.

13. The memory device of claim, 1, wherein a processor executes the mapping application using integer fixed-point math, writes out the pixel data to the view port in double words and constructs an entire graphics frame in an off-screen double-buffer and then paints the entire frame to the view port at once.

14. The memory device of claim 1, wherein said plurality of objects are arranged at different locations in world space according to their map'"'"'s geo-location or user preference.

15. The memory device of claim 1, further comprising for each pixel in world space determining coordinates in map space and sampling map pixel data for only the topmost intersecting object.

16. The memory device of claim 1, wherein the view port rotates 0-360°

and scales in world space in response to the input.

17. A memory device encoding a mapping application for use with a hand-held device in which a plurality of maps having their own map spaces are stored as pixel data in memory for presentation on a display, a processor executing the mapping application comprising the steps of:

selecting a plurality of objects assigned to different said maps and arranging them in a world space coordinate system, each said object defining the extent of its map in world space;

positioning a view port representing a portion of display space at rotation and scale in world space;

for each pixel in the view port, assigning said pixel a world space coordinate using a first affine transformation from display space to world space;

for each assigned world space coordinate, determining at least a topmost object, if any, that intersects the coordinate and for only said topmost intersecting object determining its map space coordinate using a second object-specific affine transformation from world space to that object'"'"'s map space based on the extent of that object'"'"'s map in world space and sampling the object'"'"'s map pixel data at its determined map space coordinate to assign a value to the associated pixel in the view port;

assigning a background value to the pixels in the view port that do not intersect an object; and

painting the display once with the map and background pixels assigned to the view port to render said plurality of maps at the same time.

18. The memory device of claim 17, wherein the first affine transformation performs a first linear interpolation along a vertical axis of the view port and a second linear interpolation along a horizontal axis of the view port, and wherein the second affine transformation performs a linear interpolation along a vertical axis of the object in map space and a second linear interpolation along a horizontal axis of the object.

19. The memory device of claim 17, wherein the mapping application stores said pixel data for each said map in a plurality of vertical strips, each said vertical strip including multiple partial rows of row-oriented pixel data, in a main memory, a hardware caching operating retrieving pixel data from a sequential range of memory addresses around a most recently accessed address from a vertical strip in main memory and storing the pixel data into a cache memory.

20. The memory device of claim 17, wherein the first affine transformation automatically rotates the view port in world space according to the display'"'"'s orientation so that the direction a user is facing is always upward on the view port.

21. A memory device encoding a mapping application for use with a hand-held device in which a plurality of rectangular maps having their own map spaces are stored for presentation on a rectangular display, said mapping application comprising the steps of:

storing said pixel data for each said rectangular map in a plurality of vertical strips in main memory, a hardware caching operating storing pixel data for a range of addresses around a most recently accessed address from a vertical strip into a cache memory;

selecting a plurality of rectangular objects assigned to different said maps and arranging them in a world space coordinate system, each said rectangular object defining the extent of its map in world space;

positioning a rectangular view port representing a portion of display space with a specified translation, rotation and scale in world space;

for each pixel in the view port, assigning said pixel a world space coordinate by performing two liner interpolations, one along the vertical axis of the view port and a second along the horizontal axis of the view port from display space to world space;

for each assigned world space coordinate, determining which objects, if any, intersect the coordinate and for at least a topmost intersecting object determining its map space coordinate by performing two linear interpolations, one along the vertical axis of the rectangular object and the second along the horizontal axis of the rectangular object, based on the extent of that object'"'"'s map in world space and sampling the object'"'"'s map pixel data from cache and then main memory at its determined map space coordinate to assign a value to the associated pixel in the view port;

assigning a background value to the pixels in the view port that do not intersect an object; and

painting the display with the map and background pixels assigned to the view port to render said plurality of maps at the same time.

22. The memory device of claim 21, wherein only object map pixel data that contributes to painting the display within the view port is sampled.

23. The memory device of claim 21, wherein the two linear interpolations performed on each pixel in the view port automatically rotates the view port in world space according to the display'"'"'s orientation so that the direction a user is facing is always upward on the view port.

24. A hand held device, comprising:

a display;

non-volatile storage for storing a plurality of pixel maps each having its own map space and a mapping application;

main memory into which the mapping application is loaded once initiated and segments of said pixel maps are stored in vertical strips, each said vertical strip including multiple partial rows of row-oriented pixel data, in response to user input;

a processor that retrieves pixel data from a sequential range of memory addresses around the most recently accessed address in a vertical strip of main memory and stores the pixel data in cache memory; and

user I/O for loading maps from non-volatile storage into main memory in a world space coordinate system and for navigating world space to position a view port representing a portion of display space therein,

said processor executing the mapping application to position one or more objects in world space that define the position and spatial extent of the respective maps, for each pixel in the view port, assigning said pixel a world space coordinate using a first affine transformation from display space to world space, for each assigned world space coordinate, determining which objects, if any, intersect the coordinate and for at least a topmost intersecting object determining its map space coordinate using a second affine transformation from world space to that object'"'"'s map space based on the extent of that object'"'"'s map in world space and attempting to sample the object'"'"'s map pixel data at its determined map space coordinate to assign a value to the associated pixel in the view port from cache and if unsuccessful sampling the map pixel data from the vertical strip stored in main memory to assign a value to that pixel in the view port, assign a background value to the pixels that do not intersect an object and paint the display with the map and background pixels assigned to the view port.

25. The hand held device of claim 24, wherein the processor executes the first affine transformation by performing a first linear interpolation along a vertical axis of the view port and a second linear interpolation along a horizontal axis of the view port, and executes the second affine transformation by performing a linear interpolation along a vertical axis of the object in map space and a second linear interpolation along a horizontal axis of the object based on the extent of that object'"'"'s map in world space.

26. The hand held device of claim 24, wherein the processor samples said pixel data by first interacting with cache memory to determine whether the map space coordinates are within the range of addresses for the vertical strip stored in cache and, if not, interacting with main memory by determining the vertical strip in main memory in which the pixel data resides, converting the map space coordinate into a vertical strip column coordinate, and sampling the pixel data from the vertical strip at the column coordinate.

27. The band held device of claim 24, whereby a probability of a cache hit is greater than if the pixel data were stored in rows of memory.

28. The hand held device of claim 24, whereby storing the pixel data in vertical strips of main memory increases a probability of a cache miss for view port rotations of 0°

and 180° and

reduces a probability of a cache miss for view port rotations of 90° and

270°

when sampling the map pixel data.

29. The hand held device of claim 24, further comprising direction-finding hardware whereby the first affine transformation automatically rotates the view port in world space according to the display'"'"'s orientation so that the direction a user is facing is always upward on the view port.

30. The hand held device of claim 24, wherein the user I/O is capable of rotating the view port 0-360°

and scaling the view port in world space in response to a user input.

31. The hand held device of claim 24, wherein each said vertical strip includes pixel data from multiple complete columns and multiple partial rows of equal width.

32. The hand held device of claim 24, wherein said processor determines the topmost object, if any, that intersects the coordinate and for only the topmost intersection object determines its map space coordinate using second affine transformation to sample only the topmost object'"'"'s map pixel data.