Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
1997-08-01
2001-04-10
Zimmerman, Mark (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
Reexamination Certificate
active
06215504
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention pertains to parallel algorithms for execution by a operand-rerouting, multi-operation vector processor. More specifically, the invention relates to an improved line drawing technique on such a processor.
2. Description of the Related Art
The microcomputer industry has seen a metamorphosis in the way computers are used over the last number of years. Originally, most operating systems were text based requiring typed user input and providing textual response. These systems have given way to graphical based environments. Current systems are heavily graphically based, both providing graphical user interfaces including icons, windows, and the like, and providing graphical interaction with a user through a variety of user input devices.
This trend is likely to continue. But graphical, multimedia environments place different and greater demands on processor capabilities than the old textual environments. For many years, the Intel x86 series of processors by Intel Corporation has provided the computing power for IBM PC compatible machines. The architecture of the Intel design, however, is not optimized towards graphical operations.
To this end, a number of extensions to the x86 architecture have been proposed and developed. These include the MMX extensions developed by Intel Corporation. Further, other manufacturers have similarly extended their instruction sets. For example, Sun Microcomputing has developed the UltraSparc, a graphics extension of the SPARC V9 architecture.
Typical vector processors provide for multiple operations simultaneously, but require that the same operation be performed by each partition within the vector (SIMD, or single instruction multiple data). In the multimedia extension unit architecture, this has changed. Not only can multiple operations be concurrently executed on vectorized data, but different operations can be simultaneously performed, and the vectorized data can be rerouted through a number of multiplexers.
This architecture presents a number of possibilities, but developing algorithms that efficiently utilize this architecture places its own demands, given the new features of the instruction set. It is desirable to efficiently utilize this architecture to execute algorithms for multimedia.
SUMMARY OF THE INVENTION
According to the invention, a multimedia extension unit architecture draws lines on a graphical display through new, faster, and unique techniques. The line drawing algorithm is highly vectorized, even though the Bresenham algorithm has historically been a serially executed algorithm.
A first sequence of Y pixel values and error values are calculated serially. Then, subsequent Y pixel values are calculated in parallel based on the previous Y and error values using the rerouting and operation selection of the multimedia extension unit.
REFERENCES:
patent: 4730261 (1988-03-01), Smith
patent: 4901266 (1990-02-01), Takagi
patent: 5001651 (1991-03-01), Rehme et al.
patent: 5020014 (1991-05-01), Miller et al.
patent: 5175701 (1992-12-01), Newman et al.
patent: 5627956 (1997-05-01), Dao et al.
patent: 5636153 (1997-06-01), Ikegaya et al.
patent: 5694345 (1997-12-01), Peterson
Kohn, L., et al., The Visual Instruction Set (VIS) in Ultra SPARC™, IEEE (1995), pp. 482-489.
Lee, Ruby B., Realtime MPEG Video via Software Decompression on a PA-RISC Processor, IEEE (1995), pp. 186-192.
Zhou, et al., MPEG Video Decoding with the UltraSPARC Visual Instruction Set, IEEE (1995), pp. 470-474.
Papamichalis, Panos, An Implementation of FFT, DCT, and other Transforms on the TMS320C30, (1990), pp. 53-119.
Gwennap, Linley, UltraSparc Adds Multimedia Instructions, Microprocessor Report, Dec. 5, 1994, pp. 16-18.
Goslin, Gregory Ray, Implement DSP functions of FPGAs to reduce cost and boost performance, EDN, Oct. 10, 1996, pp. 155-164.
Hearn & Baker,Computer Graphics(1986), pp. 58-61.
Programmer's Reference Manual, Intel Architecture MMX™ Technology, Chapters 2-5, Intel Corp., printed Sep. 26, 1996.
“Computer Graphics”: James D. foley, Andries van Dam, Steven K. Feiner, John F. Hughes; Section3.2.2, 1992.
Longhenry Brian E.
Thayer John S.
Thome Gary W.
Akin Gump Strauss Hauer & Feld & LLP
Compaq Computer Corporation
Padmanabhan Mano
Zimmerman Mark
LandOfFree
Line drawing using operand routing and operation selective... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Line drawing using operand routing and operation selective..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Line drawing using operand routing and operation selective... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2549685