System and method for efficient hit-testing in a computer-based system

• US 6,049,325 A
• Filed: 05/27/1997
• Issued: 04/11/2000
• Est. Priority Date: 05/27/1997
• Status: Expired due to Fees

• Current Assignee: Agilent Technologies, Inc.
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Alexander, Jay A
• Primary Examiner(s): Luu, Matthew
• Assistant Examiner(s): PIZIALI, JEFFREY J
• Application Number:
  US08/863,461
• Time in Patent Office: 1,050 Days
• Field of Search: 345/118, 345/133-134, 345/145, 345/157, 345/339, 345/440, 345/150, 340/709, 340/747, 364/580, 348/445, 395/326
• US Class Current: 345/157
• CPC Class Codes: G01R 13/0218 Circuits therefor
• CPC Class Codes: G06F 3/04842 Selection of displayed objects or displayed text elements G06F3/0482 takes precedence

Abstract

A hit-test system and methodology for use in a computer-based system having a graphical user interface for searching a display pixel map in successively-increasing distances from a selected pixel location associated with a current cursor position in accordance with a predetermined search topology defined by pixel offset values stored in a look-up table. The hit-test system comprises a distance computation module for generating the pixel offset values corresponding to each of the successively-increasing distances. The pixel offset values define a determined search topology. A display search engine searches pixel locations determined from the pixel offset values and the selected pixel location. The display search engine comprises a radius search module selecting the successively-increasing distances and adds the pixel offset values to the selected pixel location. A display analysis module determines whether the queried pixel location in the display pixel map contains a color indicative of a display element. Preferably, the radius search module determines a maximum search limit which defines a range of pixel locations likely to include a display element of interest to the user while avoiding causing the user to select an undesired display element. In another embodiment the hit-test system also includes a user interface module for determining when the user has selected a pixel location and for providing the display search engine with the selected pixel location. The selected pixel location may be represented by a cursor positioned with a pointing device such as a mouse, light pen, keyboard controls, touch pad, etc. Preferably, the selected pixel location is also represented by dwelling the cursor at the selected pixel location for a predetermined period of time.

Claims

1. A hit-test system for use in a computer-based system having a display, said hit-test system configured to search a display pixel map of pixel data in successively-increasing distances from a selected pixel location associated with a cursor position, said search performed in accordance with a search topology defined by pixel offset values stored in a look-up table.

2. The hit-test system of claim 1, wherein said hit-test system comprises:

a distance computation module for accessing said look-up table to retrieve said pixel offset values corresponding to each of said successively increasing distances.

3. The hit-test system of claim 1, wherein said hit-test system comprises:

a display search engine for adding said pixel offset values to said selected pixel location to determine which pixels in said display pixel map are to be queried.

4. The hit-test system of claim 3 wherein said display search engine comprises:

a radius search module for determining each of said successively-increasing distances and for performing said addition of said pixel offset values and said selected pixel location to generate said query pixel locations.

5. The hit-test system of claim 3 wherein said search topology has a predetermined symmetry, and further wherein said display search engine calculates some of said pixel offset values based upon said pixel offset values stored in said look-up table.

6. The hit-test system of claim 4, wherein said radius search module determines a maximum distance from said selected pixel location that is to be searched.

7. The hit-test system of claim 6 wherein said maximum distance defines a range of pixel locations likely to include a display element of interest to the user while avoiding causing the user to select an undesired display element, wherein when no display element is rendered at a pixel located within said maximum distance, said hit-test system identifies a background region of the display as being selected by the user.

8. The hit-test system of claim 4, further comprising:

a user interface module for determining a user-identified pixel location as said selected pixel location and for providing said display search engine with said selected pixel location.

9. The hit-test system of claim 8, wherein said selected pixel location is identified by a cursor controlled by a pointing device and activation of a selection switch.

10. The hit-test system of claim 9, wherein said selected pixel location is also represented by dwelling said cursor at said selected pixel location for a predetermined period of time.

11. The hit-test system of claim 4, wherein said display search engine further comprises:

a display analysis module operatively coupled to said radius search module for determining whether pixel data for each said query pixel location in said display pixel map contains a value indicative of a display element rendered at said pixel location.

12. The hit-test system of claim 11, wherein more than one display element may be located at a pixel location, and further wherein said display analysis module arbitrates between said more than one display element to select a display element that is more likely to be a display element desired by the user.

13. The hit-test system of claim 11 wherein said computer-based system is a digital oscilloscope comprising a video random access memory (VRAM) in which said display pixel map is stored, and

a waveform random access memory coupled to said VRAM containing display element data,

wherein said display analysis module accesses said waveform RAM to perform said arbitration.

14. The hit-test system of claim 1, wherein said search topology is a circular search topology.

15. The hit-test system of claim 1, wherein said search topology is an elliptical search topology.

16. The hit-test system of claim 7, wherein said pixel offset values stored in said look-up table are biased by the inverse of the linear aspect ratio of the pixels to accommodate displays having a different number of pixels per linear dimension in horizontal and vertical coordinates.

17. The hit-test system of claim 1, wherein said computer-based system is a test and measurement instrument.

18. The hit-test system of claim 17, wherein said computer-based system is a digital oscilloscope.

19. The hit-test system of claim 17, wherein said display elements comprise signal waveforms, function waveforms, memory waveforms, markers, trigger level indicators, and ground voltage indicators.

34. The hit-test system of claim 1, wherein said hit-test system searches said display pixel map until either a pixel having a display element rendered therein is located or when said successively-increasing distance search is a maximum distance from said cursor position.

35. The hit-test system of claim 11, wherein said value represents a color of said pixel.

20. A hit-test system for use in a computer-based system having a graphical user interface, said hit-test system configured to search a display pixel map to identify a highest priority display element located nearest to a selected pixel location in accordance with a predetermined search topology defined by pixel offset values stored in a look-up table.

36. The hit-test system of claim 20, wherein when said search topology is defined by pixel offset values.

37. The hit-test system of claim 36, wherein said pixel offset values are stored in a look-up table.

38. The hit-test system of claim 20, wherein said search topology is predetermined.

39. The hit-test system of claim 37, wherein said search topology is one of a plurality of search topologies each stored in a look-up table.

40. The hit-test system of claim 37, comprising:

a distance computation module for accessing said look-up table to retrieve said pixel offset values corresponding to each of said successively-increasing distances; and

a display search engine for adding said pixel offset values to said selected pixel location to determine which pixels in said display pixel map are to be searched for a display element rendering.

41. The hit-test system of claim 40, wherein said display search engine comprises:

a radius search module for determining each of said successively-increasing distances and for adding said pixel offset values to said selected pixel location to generate said querry pixel locations; and

a display analysis module operatively coupled to said radius search module for determining whether each said searched pixel location in said display pixel map contains a value indicative of a display element rendered at said pixel location.

42. The hit-test system of claim 41, wherein said value represents a color of said display element rendered at said pixel location.

43. The hit-test system of claim 20, wherein said selected pixel location is represented by dwelling said cursor at said selected pixel location for a predetermined period of time.

44. The hit-test system of claim 20, wherein said computer-based system is a test and measurement instrument.

45. The hit-test system of claim 20, wherein said hit-test system searches said display pixel map until either a pixel in which a display element is rendered is located or when said successively-increasing distance search is a maximum distance from said cursor position.

21. A hit-test system for use in a computer-based system having a graphical user interface, said hit-test system configured to query pixels offset a predetermined distance from a selected pixel location in a display pixel map located in memory of the computer-based system to identify a display element located nearest to said selected pixel location which is most likely to be desired by the user, said predetermined distances defined by pixel offset values stored in a look-up table located in memory of the computer-based system.

46. The graphical user interface of claim 21, wherein said pixel offset values represent successively-increasing distances from a pixel location in accordance with a search topology.

47. The graphical user interface of claim 21, wherein said graphical user interface searches said display pixel map until either a pixel having a display element rendered therein is located or when said successively-increasing distance search is a maximum distance from said cursor position.

48. The graphical user interface of claim 47, wherein said graphical user interface comprises:

a distance computation module for accessing said look-up table to retrieve said pixel offset values corresponding to each of said successively-increasing distances; and

a display search engine for adding said pixel offset values to said selected pixel location to determine which pixels in said display pixel map are to be queried.

49. The hit-test system of claim 21, wherein said computer-based system is a test and measurement instrument.

50. The graphical user interface of claim 48, wherein said display search engine comprises:

a radius search module for determining each of said successively-increasing distances and for performing said addition of said pixel offset values and said selected pixel location to generate said query pixel locations; and

a display analysis module operatively coupled to said radius search module for determining whether pixel data for each said query pixel location in said display pixel map contains a value indicative of a display element rendered at said pixel location.

51. The graphical user interface of claim 48, wherein said value represents a color of said pixel.

22. A system for identifying display elements nearest to a selected pixel position in a computer display represented by a pixel map, comprising:

display search means for determining whether pixel locations located at successively-increasing distances from the selected pixel position contain a display element;

a relative location look-up table containing pixel offset values each associated with one of said distances, said pixel offset values defining a search topology; and

distance computation means for accessing said look-up table and for providing said display search means with one or more of said pixel offset values corresponding to each of said increasingly-successive distances.

23. The system of claim 22, wherein said display search means comprises:

means for determining each of said successively-increasing distances and for adding said pixel offset values to said selected pixel location; and

display analysis means for determining whether said pixel locations in the display pixel map contains a color indicative of a display element.

24. A digital oscilloscope comprising:

a graphical user interface providing a waveform display;

a video random access memory containing a display pixel map for storing pixel values generating said waveform display;

a waveform random access memory containing pixel data associated with each pixel location, identifying display elements active at said associated pixel location; and

a hit-test system for searching said display pixel map in successively-increasing distances from a selected pixel location in accordance with a predetermined search topology defined by pixel offset values stored in a look-up table, including,

a distance computation module for generating said pixel offset values corresponding to each said distances of said predetermined search topology,

a display search engine for querying pixel locations determined from said pixel offset values and said selected pixel location, and for arbitrating between multiple display elements which are active at said queried pixel, and

a user interface module for determining when the user has selected a pixel location and for providing said display search engine with said selected pixel location, said selection achieved by activation of a pointing device and dwelling said cursor at said selected pixel location for a predetermined period of time.

25. The oscilloscope of claim 24, wherein said display search engine comprises:

a radius search module for determining each of said successively-increasing distances up to a maximum search limit and for adding said pixel offset values to said pixel location associated with said query pixel locations; and

a display analysis module for determining whether said queried pixel locations contain a color indicative of a display element.

26. A method for locating a display element nearest to a pixel location associated with a selected pixel location, comprising the steps of:

(a) determining when the user has attempted to select a display element;

(b) determining one or more pixels to be queried at a given distance from selected pixel location;

(c) determining which of said one or more query pixels contains a color corresponding to a display element of interest to the user; and

(d) repeating said steps (b) and (c) for successively-increasing distances from said selected pixel location, each of said one or more pixels conforming to a predetermined search topology.

27. The method of claim 26, wherein said step (a) comprises the steps of:

(1) monitoring system inputs to determine when the user has performed a display element select operation.

28. The method of claim 27, wherein said step (a) further comprises the steps of:

(2) monitoring an amount of time the user dwells the cursor at a pixel location; and

(3) identifying said pixel location as said selected pixel location when said dwell is for a time greater than a predetermined threshold.

29. The method of claim 26, wherein said step (b) comprises the steps of:

(1) obtaining one of said series of said pixel offset values from a look-up table corresponding to said given distance from said selected pixel location; and

(2) adding said pixel offset values to said selected pixel location to identify pixels to be queried at said given distance from said selected pixel location.

30. The method of claim 29, further comprising the steps of:

(e) before said step (a), computing said pixel offset values conforming to said search topology; and

(f) after said step (e), storing said pixel offset values in said lookup table.

31. The method of claim 29, wherein said step (c) comprising the steps of:

(1) determining which of said one or more queried pixels contains a color corresponding to a display element;

(2) arbitrating between multiple display elements which are to be rendered at one of said pixel location; and

(3) selecting said display element of interest from all found display elements.

32. The method of claim 31, wherein said step (c)(1) comprises the step of:

(a) analyzing a display pixel map at each of said pixel locations to determine whether said queried pixel location contains a color corresponding to a display element.

33. The method of claim 32, wherein said step (d) comprises the step of:

(1) repeating said steps (b) and (c) for successively-increasing distances from said selected pixel location up to a maximum distance from said selected pixel location.

52. The oscilloscope of claim 26, wherein said hit-test system comprises:

a distance computation module for generating said pixel offset values corresponding to each said distances of said predetermined search topology,

a display search engine for querying pixel locations determined from said pixel offset values and said selected pixel location, and for arbitrating between multiple display elements which are active at said queried pixel, and

a user interface module for determining when the user has selected a pixel location and for providing said display search engine with said selected pixel location, said selection achieved by activation of a pointing device and dwelling said cursor at said selected pixel location for a predetermined period of time.

53. A hit-test system for use in a computer-based system having a display, said hit-test system configured to search a display pixel map having stored therein pixel data, said search performed in successively-increasing distances from a selected pixel location associated with a cursor position in accordance with a search topology.

54. The hit-test system of claim 53, wherein when said search topology is defined by pixel offset values.

55. The hit-test system of claim 54, wherein said pixel offset values are stored in a look-up table.

56. The hit-test system of claim 53, wherein said search topology is predetermined.

57. The hit-test system of claim 53, wherein for each searched pixel location, said hit-test system tests a specific component of said pixel data at said searched pixel location.

58. The hit-test system of claim 57, wherein said tested component represents a color of said searched pixel location.

59. The hit-test system of claim 58, wherein a plurality of display elements may be rendered at a pixel location and wherein said pixel location is rendered in a color of a highest priority display element of said plurality of display elements.

60. The hit-test system of claim 59, wherein said pixel location is rendered in a color of more than one of said plurality of display elements, and wherein said hit-test system arbitrates between said more than one display element to select a display element that is more likely to be a display element desired by the user.

61. The hit-test system of claim 53, wherein said computer-based system is a digital oscilloscope and wherein said display pixel map is contained within a video random access memory (VRAM).

62. The hit-test system of claim 53, wherein said hit-test system searches said pixel display map until either a pixel in which a display element is rendered is identified or when said successively-increasing distance search is a maximum distance from said cursor position.

63. A hit-test system for use in a computer-based system having a display, said hit-test system configured to search a display pixel map having stored therein pixel data for each pixel in the display, said search performed in accordance with a search topology defined by pixel offset values.

64. The hit-test system of claim 63, wherein when said search is performed in successively-increasing distances from a selected pixel location associated with a cursor position, each said successively-increasing distance defined by said search topology.

65. The hit-test system of claim 64, wherein said pixel offset values are stored in a look-up table.

66. The hit-test system of claim 63, wherein said search topology is one of a plurality of search topologies each stored in a look-up table selected prior to said hit-test system performing s search.

67. The hit-test system of claim 63, wherein for each searched pixel location, said hit-test system tests a specific component of said pixel data at said searched pixel location.

69. The memory of claim 67, wherein said user selection comprises activation of a selection switch.

70. The memory of claim 67, wherein said user selection comprises dwelling the cursor at one pixel location for a predetermined period of time.

68. A memory for storing data for access by a program being executed on a computer-based system having a display, the memory comprising:

a data structure stored in said memory, said data structure including information used by said program to identify, in response to a user selection, a display element displayed on the display that is closest to a current cursor position, wherein the information in said data structure comprises pixel offset values for successively-increasing distances from the current cursor position, said successively-increasing distances representing a predetermined search topology,

whereby the program accesses said data structure to retrieve a portion of said pixel offset values associated with each of said distances to determine which pixels to query for a display element.