Object selection using hit test tracks

Details Object selection using hit test tracks Object selection using hit test tracks

1994-10-24

2001-04-17

Bayerl, Raymond J. (Department: 2773)

Computer graphics processing and selective visual display system

Display driving control circuitry

Controlling the condition of display elements

C345S215000, C345S215000, C345S215000, C345S205000, C707S793000

Reexamination Certificate

active

06219048

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to methods for selecting objects from a moving image sequence of digitized or synthesized images, and more particularly, to a technique for storing auxiliary data in an item buffer, along with a video track, so as to precisely identify objects which can be selected from within each frame of the video track.
BRIEF DESCRIPTION OF PRIOR ART
Object selection methods allow a user to select an individual object from among a group of objects in an image. One approach to object selection centers around determining which line segment on a two-dimensional screen image has been selected by a user. Typically, these line segments are connected to form a polygonal region, but they may also not be connected at all. One method, called “cursor picking”, which is described by J. D. Foley and A. Van Dam, in “Fundamentals of Interactive Computer Graphics”, Addison-Wesley Publishing Company, 1984, pps. 200-204, creates bounded extents, which can be checked using simple equations. Such a scheme, for example, would allow a user to select and modify the characteristics of a particular triangle on a screen, even though there may be many other objects, such as circles, trapezoids, and arbitrary polygonal regions, also visible on the screen. Another method for object selection is to have an object name associated with every object in a scene. To make an object an active selection, the user simply types in the object name that they want to select. This method has no geometric correspondence.
Another technique typically utilized in interactive systems, such as Apple Computer Incorporated's HyperCard™ program, permits the user to identify a rectangular bounding region on the screen with a particular object, such as a button or field. The HyperCard program looks to see where the cursor location is when a selection is made and, at that time, searches for the object (such as a button or field) that has a bounding rectangle at that location. If no bounding rectangle encloses the cursor location, no object is selected. Conversely, if there is a bounding rectangle which encloses the object, the corresponding object is selected. All of the above techniques do not allow for accurate object selection of arbitrarily complex boundaries and can be difficult to use when attempting to identify object boundaries precisely.
Item buffers are generally used to speed up image synthesis algorithms, such as ray tracing or radiosity. They may also be used to identify single object three-dimensional surface areas for usage with interactive painting and lighting systems which manipulate two-dimensional images. When computing radiosity form factors, a hemi-cube algorithm is typically used to speed up the calculation. In this algorithm, five faces of a cube are rendered as item buffers which contain object tags. By counting the number of tagged pixels in the face images, the form factor is computed for a particular polygon when seen from the vertex of another polygon. A description of such a system is presented by Michael F. Cohen and Donald P. Greenberg, in “The Hemi-Cube: A Radiosity Solution for Complex Environments”, Computer Graphics, #19, Vol. 3, July 1985, pp. 31-40.
Ray tracing may be accelerated by scan-converting an “object tag” image into an item buffer. Then, for each pixel, the ray from the camera corresponding to that pixel is assumed to intersect with the object whose tag is in that pixel. By using an item buffer the algorithm avoids performing any primary ray-object intersection tests. In this way, ray tracing is made more computationally efficient. A description of such a system is presented by Hank Weghorst, Gary Hooper, and Donald P. Greenberg, “Improved Computational Methods for Ray Tracing”, ACM Transactions on Graphics, Vol. 3, No. 1, January 1984, pp. 52-69.
In “Direct WYSIWYG Painting and Texturing on 3D Shapes,”by Pat Hanrahan and Paul Haeberli, Computer Graphics, Vol. 24, No. 4, August 1990. pp. 215-223, a single three-dimensional object is rendered into an “id buffer”which stores the surface u-v values for the visible surface in that pixel. When painting onto the image, the surface position and surface normal vectors are determined by examining the object id buffer and then the result is used to shade the pixel as the texture maps are modified. This method allows a user to paint on an image in two dimensions and allows modification of the object geometry or lighting in three-dimensional space. The resultant modification is computed in three-dimensional space and then calculated as two-dimensional screen pixels, which are selectively written into the visible screen buffer.
BRIEF DESCRIPTION OF THE INVENTION
A preferred embodiment of the present invention comprises a method for labeling the pixels within a selected visual area of at least one image frame containing that visual area from a sequence of image frames stored in memory and operative to be displayed on an interactive display so that a user may subsequently select the selected visual area on a pixel accurate, frame accurate basis. To label the selected visual area within an image frame, the scene within that image frame is segmented to identify the selected visual area, each pixel within that selected visual area is then labeled with an area identifier which is unique to that selected visual area, and the pixels containing the area identifiers are mapped into an item buffer. The item buffer is then compressed and stored within a labeled portion of memory linked with the stored frame image from which the item buffer was derived. When a user subsequently selects a pixel within any frame image of the sequence of frame images the pixel is decompressed within the labeled portion of memory corresponding to the pixel in the selected frame image to determine the area identifier for the selected pixel. This area identifier is then used for a number of purposes, such as to identify an area within the frame image corresponding to the selected pixel, or to cause some action related to the selected pixel to be performed.


REFERENCES:
patent: 4601003 (1986-07-01), Yoneyama et al.
patent: 4941111 (1990-07-01), Sfarti
patent: 4977518 (1990-12-01), Bonnet et al.
patent: 5021770 (1991-06-01), Aisaka et al.
patent: 5155806 (1992-10-01), Hoeber et al.
patent: 5174759 (1992-12-01), Preston et al.
patent: 5208909 (1993-05-01), Corona et al.
patent: 5237648 (1993-08-01), Mills et al.
patent: 5274753 (1993-12-01), Roskowski et al.
patent: 5307457 (1994-04-01), Beitel et al.
patent: 5317680 (1994-05-01), Ditter, Jr.
patent: 5388197 (1995-02-01), Rayner
patent: 0332256A1 (1989-09-01), None
Tonomura et al., “Content Oriented Visual Interface Using Video Icons for Visual Database Systems”, IEEE, 1989, pp. 68-73.*
Patent Abstracts of Japan, “CDI Disk for Karaoke”, vol. 15, No. 322 (P-1239), Ab. Date: Aug. 16, 1991, Patentee: Toppan Printing Co. Ltd., Patent Date: May 17, 1991, Inventor: Ota Minoru, et al., Pub. No.: JP3116474, Pub. Date: May 17, 1991, App. No.: JP890253152, App. Date: Sep. 28, 1989.
Foley, J.D., and Van Dam, A., “Fundamentals of Interactive Computer Graphics”, Reading, MA: Addison-Wesley, 1982, pp. 200-204.
Cohen, M.F., and Greenberg, D.P., “The Hemi-Cube: A Radiosity Solution for Complex Environments”, ACM:SIGGRAPH, V. 19, N. 3, 1985, pp. 31-40.
Hanrahan, P., and Haeberli, P., “Direct WYSIWYG Painting and Texturing on 3D Shapes”, ACM Computer Graphics, V. 24, N. 4, Aug. 1990, pp. 215-223.
Weghorst, H., Hooper, G., and Greenberg, D.P., “Improved Computational Methods for Ray Tracing”, ACM Transactions on Graphics, V. 3, N. 1, Jan. 1984, pp. 52-69.

Affiliated with

Also associated with

Rating

Object selection using hit test tracks does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Object selection using hit test tracks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Object selection using hit test tracks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2474082