Transformable graphical regions

Details Transformable graphical regions Transformable graphical regions

1999-07-30

2001-12-11

Jankus, Almis R. (Department: 2672)

Computer graphics processing and selective visual display system

Computer graphics processing

Graphic manipulation

Reexamination Certificate

active

06330003

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to image storage and processing in computers, and, more particularly, to storing and processing of graphical regions by preserving the original path data, and combination or transformation operations that define the region, and converting regions to a device-specific coordinate space on an as-needed basis.
BACKGROUND OF THE INVENTION
Most modern computer graphics systems today use raster graphics to display images. A raster graphics system displays an image as a raster grid, where each line of the grid is composed of a row of pixels. The image may be stored as a two-dimensional array of values, where each row of the array corresponds to a grid line of pixels, and each value of the array represents the data associated with a particular pixel. The image can then be processed via the array, and converted back into scan lines for display on the raster grid.
Operating systems have specially designed graphics subsystems that have been developed to address the problems inherent in creating, manipulating (e.g., define, clip, fill, draw and combine), and storing images in computer memory. For example, in the Microsoft® Windows® operating systems, the subsystem that controls the display of text and graphics is called the Graphics Device Interface (GDI). GDI functionality is provided through an application programming interface (API) that includes functions to create graphical objects and manipulate those objects in memory. GDI draws lines, curves, closed figures, text, and bitmapped images on display devices and printers. There are a number of methods that have been developed in GDI for manipulating complex images.
One method of storing image data is to define the image data as a “region.” The concept of a region was developed for the graphics subsystem in the Microsoft Windows® operating system to more easily store and process arbitrary two-dimensional shapes. Regions accommodate shapes that can be displayed as simple opaque images. The image data structure of the region is based on an image of an arbitrary two-dimensional shape expressed as a grid of binary values, e.g., 0 and 1, where the value 0 represents a transparent pixel (absence of the shape), and the value 1 represents an opaque pixel (presence of the shape).
A limitation of GDI regions, however, is that once a region is created for a specific device context (HDC), its dimensions are fixed by the resolution of the specific device (e.g., a monitor or printer) associated with that HDC. In particular, the conversion entails converting the shape of the region to device coordinates specific to the particular device. Further, the original path information that defined the shape of the region is not retained and is replaced with the device resolution-specific scan rectangles. Thus, if two device contexts were associated with different devices having different resolutions, then using the same region for both device contexts would produce unwanted results.
Another limitation of regions is that once they have been created, transforming them with matrix operations such as translate, scale, rotate, and skew can accentuate the “jaggies”. The primary reason for this effect is that it is not the original shape that is transformed, but it is the sequence of rectangle spans produced from the shape. A solution to this problem is using constructive geometry to create transformable regions. Such a solution is proposed in Java 2D. However, this solution is too complex and costly to implement, and without significant graphical resources, results in slow rendering of graphics regions. Thus, this solution is feasible only for extremely fast and expensive graphical subsystems.
Related to the above is the inability of regions to store and process images having non-binary values associated with the pixels of the image. As noted above, a region can only store the fully opaque and fully transparent areas and, therefore, does not store anti-aliasing information. The use of anti-aliasing techniques improves the appearance of the image by altering the opacity of pixels at the image's boundaries. Thus, when matrix operations are performed on a region within a particular graphics context (i.e., a specific device), the resulting region often includes significant aliasing resulting in the appearance of “jaggies” or “staircasing” at the edges of the primitives of the image region. These undesirable characteristics are common because most shapes can only be approximated with pixels on the raster grid.
In view of the above, there is a need for an improved graphics engine in a computing device that overcomes the limitations of the prior art. In particular, there is a need for a graphics engine capable of manipulating regions such that the regions may be associated with multiple devices having different resolutions. Further, there is a need for a graphics engine that provides for transformable regions using matrix operations. Still further, there is a need for a graphics engine that provides regions that may be rendered anti-aliased on devices having different resolutions. The present invention provides a solution to these problems.
SUMMARY OF THE INVENTION
The present invention utilizes transformable regions that are converted into device resolution-specific form only when needed. The original path data of the region, as well as all logical and matrix transformation operations performed to combine regions is preserved. Because the original path information is preserved, transformation operations may be applied to the path data such that the region can be regenerated for different devices.
In accordance with the present invention, a region can be represented by a hierarchical tree, wherein the leaf nodes contain path or geometric data (e.g., rectangles, ellipses, pies, and polygons) and the branch nodes contain the operations to be performed on the path, geometric data and regions. As the tree is traversed and regions are used, they are converted to a device resolution-specific regions and operations are performed on the device resolution-specific regions, rather then using complex constructive geometry to combine regions. In addition, the present invention allows for matrix transformation operations (e.g., translate, scale, skew and rotate) to be applied to the regions, because the original path information is preserved. Thus in accordance with the present invention, if a transformation matrix is applied to the region or if the region is used in a device having a different resolution, the tree can be re-traversed. Accordingly, regions may be freely transformable objects after they have been combined with other regions.
Other features of the invention are described below.


REFERENCES:
patent: 5701467 (1997-12-01), Freeston
patent: 5745121 (1998-04-01), Politis
patent: 5926183 (1999-07-01), Menon et al.
patent: 6191797 (2001-02-01), Politis
patent: WO 94/22101 (1994-09-01), None
van Kleij, R., “Efficient Display of Quadric CSG Models,”Computers in Industry, May 19, 1992, No. 2, pp. 201-211.
Rappoport, A., et al. “Interactive Boolean Operations for Conceptual Design of 3-D Solids,” Computer Graphics Proceedings, Siggraph, Annual Conference Series, 1997, pp. 269-278.

Affiliated with

Also associated with

Rating

Transformable graphical regions does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Transformable graphical regions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Transformable graphical regions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2577843