Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
1999-10-29
2001-01-09
Hong, Stephen S. (Department: 2776)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
C345S440000, C345S443000
Reexamination Certificate
active
06172683
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to the field of data compression in a distributed computer system. In particular, the invention relates to a method for lossless compression of a graphical line, including its attributes, within an application server before transmitting the compressed line data to the graphical user interface of a workstation over a low bandwidth communication transport mechanism.
BACKGROUND OF THE INVENTION
Distributed computer systems utilize the technique of distributing application execution. More specifically, an application server provides application execution services to network users rather than running the application at the user's workstation. When an application runs, the application server intercepts the user's interface (e.g., the display screen, keyboard, and mouse) data and transmits/receives this data to/from a user program running at the user's workstation. For example, when an application involves graphical lines, the application server intercepts the graphical user interface and interacts with the user program to display lines on a display at the user's workstation.
Graphical lines are frequently required in most processing operations and come in various forms, including straight, arcs, ellipses, and bezier curves. In many distributed computer systems, it is desirable for the application server to communicate graphical line data to workstations over a low bandwidth communication transport mechanism, such as serial lines, telephone lines, local area networks and wide area networks.
In one known implementation, graphical curved lines are transmitted by the application server as pixel coordinates, with each pixel definition being 7 bytes in length. However, every active pixel is transmitted as there is no interpolation method employed at the receiving workstation. If, for example, a small circle consists of 1000 active pixels, then 7000 bytes of data are transmitted by the application server. Non-curved lines are transmitted as pixel coordinates, with each pixel representing an endpoint of a straight line. The receiving workstation is responsible for interpolating between every two endpoints. Each endpoint is represented as 4 bytes, and each set of endpoints includes an additional header 27 bytes in length. For example, a simple straight line of two points requires 35 bytes (27+4*(2)). Using this known implementation, the transmission of uncompressed data over a low bandwidth transport mechanism would be too slow for adequate usability.
It is therefore a principal object of this invention to provide a method for the lossless compression of lines in a distributed computer system that allows for the use low bandwidth communication transport mechanism, such as serial lines, telephone lines, local area networks and wide area networks.
SUMMARY OF THE INVENTION
Accordingly, the present invention features a method for the lossless compression of graphical line data for transmission from an application server over a low bandwidth communication transport mechanism to a graphical user interface of a workstation in a distributed computer system. The graphical line data is representative of a graphical line to be displayed on a display screen of the workstation.
In one embodiment, the lossless compression method of the invention is realized within the application server. The application server determines, from graphical line data, coordinate locations for the endpoints of each sub-path of the graphical line. The application also determines attributes of each sub-path from the graphical line data. The application server represents the coordinate locations as compressed coordinate location data of variable length and the attributes as compressed attribute data of variable length. The application server then generates a compressed line data packet of variable length which includes said compressed coordinate location data and said compressed attribute data for each sub-path.
The compressed line data packet generated by the application server fully defines the characteristics of the graphical line. The compressed line data packet is transmitted over a low bandwidth communication transport mechanism to the workstation. A decompression program in the workstation determines the graphical line data (i.e., coordinate locations for the endpoints of each sub-path of the graphical line and attributes of each sub-path) by decompressing the variable length compressed line data packet. The graphical user interface uses the decompressed graphical lines data to display the graphical line on the display screen of the workstation.
The invention offers the following noteworthy features. First, the invention compresses graphical lines and their attributes with a high average compression ratio. Second, the invention achieves lossless data compression (i.e., 100% reversible). Third, the invention does not require additional data for the decompression processes.
REFERENCES:
patent: 3596257 (1971-07-01), Patel
patent: 4013828 (1977-03-01), Judice
patent: 4322795 (1982-03-01), Lange et al.
patent: 4395754 (1983-07-01), Feissel
patent: 4410916 (1983-10-01), Pratt et al.
patent: 4430712 (1984-02-01), Coulson et al.
patent: 4463424 (1984-07-01), Mattson et al.
patent: 4499499 (1985-02-01), Brickman et al.
patent: 4503501 (1985-03-01), Coulson et al.
patent: 4562423 (1985-12-01), Humblet
patent: 4691281 (1987-09-01), Furui
patent: 4701871 (1987-10-01), Sasaki et al.
patent: 4779189 (1988-10-01), Legvold et al.
patent: 4862392 (1989-08-01), Steiner
patent: 4899149 (1990-02-01), Kahan
patent: 4905141 (1990-02-01), Bremza
patent: 4928247 (1990-05-01), Dolye et al.
patent: 4949281 (1990-08-01), Hillenbrand et al.
patent: 4992954 (1991-02-01), Takeda et al.
patent: 5103303 (1992-04-01), Shoji et al.
patent: 5115479 (1992-05-01), Murayama
patent: 5119319 (1992-06-01), Tanenbaum
patent: 5231697 (1993-07-01), Yamada
patent: 5233701 (1993-08-01), Nakata
patent: 5269003 (1993-12-01), Roskowski et al.
patent: 5309555 (1994-05-01), Akins et al.
patent: 5315698 (1994-05-01), Case et al.
patent: 5321806 (1994-06-01), Meinerth et al.
patent: 5339411 (1994-08-01), Heaton, Jr.
patent: 5351129 (1994-09-01), Lai
patent: 5357623 (1994-10-01), Megory-Cohen
patent: 5390318 (1995-02-01), Ramakrishnan et al.
patent: 5394531 (1995-02-01), Smith
patent: 5426752 (1995-06-01), Takahasi et al.
patent: 5434992 (1995-07-01), Mattson
patent: 5455576 (1995-10-01), Clark, II et al.
patent: 5473742 (1995-12-01), Polyakov et al.
patent: 5491808 (1996-02-01), Geist, Jr.
patent: 5537551 (1996-07-01), Denenberg et al.
patent: 5537635 (1996-07-01), Douglas
patent: 5561786 (1996-10-01), Morse
patent: 5566288 (1996-10-01), Koerhsen
patent: 5572206 (1996-11-01), Miller et al.
patent: 5579507 (1996-11-01), Hosouchi et al.
patent: 5651136 (1997-07-01), Denton et al.
patent: 5652854 (1997-07-01), Wong
patent: 5717893 (1998-02-01), Mattson
patent: 5771034 (1998-06-01), Gibson
patent: 5784070 (1998-07-01), Furuhashi et al.
patent: O684583A2 (1995-11-01), None
patent: 0684582A3 (1997-09-01), None
patent: WO94/03853 (1994-02-01), None
“The Norton Utilities Version 5.0 Disk Explorer,” Norton Utilities, 1990, pp. 28-54.
“Modern Operating Systems,” Andrew S. Tanenbaum, 1992, pp. 74-93.
“The Waite Group's C Programming Using Turbo C++,”Robert Lafore, 1990, p. 423.
“Patents on Data Compression Algorithms,” pp. 1-10, (website) printed out on Jan. 4, 1998.
Citrix Systems, Inc.
Hong Stephen S.
Testa Hurwitz & Thibeault LLP
LandOfFree
Method for the lossless compression of lines in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for the lossless compression of lines in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for the lossless compression of lines in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2536499