US5657479A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Hierarchical display list processing in graphics data retrieval system
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1995-12-04
•
Granted: 1997-08-12
•
Expires: 2015-12-04
Abstract
Abstract A hierarchical display list system and efficient processing method for same. The system provides a display list having discontiguous display list segments and an information retrieval system for same (e.g. DMA controller in one embodiment). Each display list segment (DLS) contains a call to a next to be processed DLS or a return. The call includes a push (which indicates the address of the return DLS) and also a jump control data (which indicates the address of the next to be processed DLS. The push and jump and also contain the length of the respective DLS's involved. DLSs can also contain return control data which include a POP and a jump. Nesting (e.g. the display list control path) is maintained by a display list stack. The discontiguous DLSs are separately stored in memory of the host processor. According to the system, the information for traversing the hierarchical display list is stored in the display list itself so the host processor is not required for display list processing aside from initializing the rendering procedure. In an improvement embodiment, the transfer control information (e.g., call and return) are placed in the front of the DLS so that the information retrieval system can initialize and set up for the control transfer in parallel while the current DLS is processed. This improvement provides faster control transfer between. DLSs and keeps the graphics FIFO substantially filled during the display list rendering process.
Inventors
- 👤 Robert Allen Shaw
- 👤 Peter R. Birch
- 👤 John C. Lin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 15:31
CPC Classifications
G; G06; G06T; G06T1/00; G06T1/60
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
181 words
A method for processing a display list stored in a memory unit, said method comprising the steps of: (a) retrieving a first display list segment of said display list from said memory unit, said display list comprising a plurality of display list segments linked together under a hierarchical acyclic directed graph format, said step of retrieving using a memory transfer engine coupled to control said memory unit; (b) interrogating said contents of said first display list segment for a call control data and for a return control data; (c) upon encountering a call control data, (1) pushing an address and length of a second display list segment from said call control data onto a stack memory and (2) transferring an address and length of a third display list segment from said call control data to said memory transfer engine; and (d) upon encountering a return control data word, (1) popping an address and length of a fourth display list segment from said stack memory and (2) transferring said address and length of said fourth display list to said memory transfer engine.
Claim 2
Independent Claim
181 words
A method for processing a display list stored in a memory unit, said method comprising the steps of: (a) retrieving a first display list segment of said display list from said memory unit, said display list comprising a plurality of display list segments linked together under a hierarchical acyclic directed graph format, said step of retrieving using a memory transfer engine coupled to control said memory unit; (b) interrogating said contents of said first display list segment for a call control data and for a return control data; (c) upon encountering a call control data, (1) pushing an address and length of a second display list segment from said call control data onto a stack memory and (2) transferring an address and length of a third display list segment from said call control data to said memory transfer engine; and (d) upon encountering a return control data word, (1) popping an address and length of a fourth display list segment from said stack memory and (2) transferring said address and length of said fourth display list to said memory transfer engine.
Claim 3
Dependent Claim
54 words
A method as described in claim 1 including control data comprising either said call control data or said return control data and wherein said control data is located at the end of each of said plurality of display list segments of said display list and wherein said memory transfer engine is a DMA engine.
Claim 4
Dependent Claim
54 words
A method as described in claim 1 including control data comprising either said call control data or said return control data and wherein said control data is located at the front of each of said plurality of display list segments of said display list and wherein said memory transfer engine is a DMA engine.
Claim 5
Dependent Claim
68 words
A method as described in claim 3 further comprising the steps of: supplying information from said first display list segment to a graphics generation circuit for visualization; and initializing retrieval of said third display list segment using said memory transfer engine upon receiving said address and length of said third display list segment, wherein said above step of supplying and said above step of initializing operate in parallel.
Claim 6
Dependent Claim
66 words
A method as described in claim 3 further comprising the steps of: supplying information from said first display list segment to a graphics generation circuit for visualization; and retrieving said fourth display list segment using said memory transfer engine upon receiving said address and length of said fourth display list segment, wherein said above step of retrieving and said above step of initializing operate in parallel.
Claim 7
Dependent Claim
28 words
A method as described in claim 4 wherein said display list represents graphics information for display on a display screen and wherein said graphics information comprises graphics primitives.
Claim 8
Dependent Claim
71 words
A method as described in claim 1 wherein said step of (d) comprises the steps of: determining if said stack memory is empty after said step of popping an address and length of said fourth display list segment from said stack memory; and ending processing of said plurality of display list segments of said display list if said stack memory is determined to be empty by said above step of determining.
Claim 9
Dependent Claim
216 words
In a graphics display system having a host processor, a memory transfer engine, a graphics generator circuit, a memory unit, and a stack memory, a method for reading a display list comprising the steps of: (a) retrieving an input display list segment of said display list from said memory unit, said display list comprising a plurality of display list segments linked together under a hierarchical acyclic directed graph format, said step of retrieving using said memory transfer engine coupled to control said memory unit; (b) interrogating contents of said input display list to locate control data therein, said control data comprising either a call control data or a return control data for said input display list segment; (c) if said control data includes said call control data, (1) pushing an address and length of a next-to-return display list segment from said call control data onto said stack memory and (2) transferring an address and length of a jump-to display list segment from said call control data to said memory transfer engine; and (d) if said control data includes a return control data word, (1) popping an address and length of a return display list segment from said stack memory and (2) transferring said address and length of said return display list to said memory transfer engine.
Claim 10
Dependent Claim
216 words
In a graphics display system having a host processor, a memory transfer engine, a graphics generator circuit, a memory unit, and a stack memory, a method for reading a display list comprising the steps of: (a) retrieving an input display list segment of said display list from said memory unit, said display list comprising a plurality of display list segments linked together under a hierarchical acyclic directed graph format, said step of retrieving using said memory transfer engine coupled to control said memory unit; (b) interrogating contents of said input display list to locate control data therein, said control data comprising either a call control data or a return control data for said input display list segment; (c) if said control data includes said call control data, (1) pushing an address and length of a next-to-return display list segment from said call control data onto said stack memory and (2) transferring an address and length of a jump-to display list segment from said call control data to said memory transfer engine; and (d) if said control data includes a return control data word, (1) popping an address and length of a return display list segment from said stack memory and (2) transferring said address and length of said return display list to said memory transfer engine.
Claim 11
Dependent Claim
29 words
A method as described in claim 8 wherein said control data is located at the end of each of said plurality of display list segments of said display list.
Claim 12
Dependent Claim
29 words
A method as described in claim 8 wherein said control data is located at the front of each of said plurality of display list segments of said display list.
Claim 13
Dependent Claim
69 words
A method as described in claim 10 further comprising the steps of: supplying information from said input display list segment to a graphics generation circuit for visualization; and retrieving said jump-to display list segment using said memory transfer engine upon receiving said address and length of said jump-to display list segment, wherein said above step of supplying and said above step of retrieving said jump-to-display list operation in parallel.
Claim 14
Dependent Claim
74 words
A method as described in claim 11 wherein said step of receiving an input display list comprises the step of receiving said input display list into a FIFO memory unit and further comprising the step of: preventing said FIFO from emptying by receiving said jump-to display list into said FIFO memory unit just as memory is made available in said FIFO memory unit from said input display list segment exiting said FIFO memory unit.
Claim 15
Dependent Claim
37 words
A method as described in claim 11 wherein said display list represents graphics information for display on a display screen, wherein said graphics information comprises graphics primitives and wherein said memory transfer engine is a DMA engine.
Claim 16
Dependent Claim
68 words
A method as described in claim 10 further comprising the steps of: supplying information from said input display list segment to a graphics generation circuit for visualization; and initializing retrieval of said jump-to display list segment using said memory transfer engine upon receiving said address and length of said jump-to display list segment, wherein said above step of supplying and said above step of initializing operate in parallel.
Claim 17
Dependent Claim
68 words
A method as described in claim 10 further comprising the steps of: supplying information from said input display list segment to a graphics generation circuit for visualization; and initializing retrieval of said return display list segment using said memory transfer engine upon receiving said address and length of said return display list segment, wherein said above step of supplying and said above step of initializing operate in parallel.
Claim 18
Dependent Claim
71 words
A method as described in claim 8 wherein said step of (d) comprises the steps of: determining if said stack memory is empty after said step of popping an address and length of said return display list segment from said stack memory; and ending processing of said plurality of display list segments of said display list if said stack memory is determined to be empty by said above step of determining.
Claim 19
Dependent Claim
229 words
A graphics display system for generating an image represented by graphics information of a display list, said system comprising: a host processor coupled to communicate with a memory unit; a stack memory; an information retrieval circuit comprising a FIFO memory for retrieving an input display list segment of said display list from said memory unit, said display list comprising a plurality of display list segments linked together under a hierarchical acyclic directed graph format; said information retrieval circuit also comprising a parsing processor for interrogating said input display list to locate control data therein, said control data comprising either a call control data or a return control data for said input display list segment; and control logic for determining if said control data includes said call control data, and if so, (1) for pushing an address and length of a next-to-return display list segment from said call control data onto said stack memory and (2) for transferring an address and length of a jump-to display list segment from said call control data to a retrieval circuit, said control logic also for determining if said control data includes said return control data word, and if so, (1) for popping an address and length of a return display list segment from said stack memory and (2) for transferring said address and length of said return display list to said retrieval circuit.
Claim 20
Dependent Claim
229 words
A graphics display system for generating an image represented by graphics information of a display list, said system comprising: a host processor coupled to communicate with a memory unit; a stack memory; an information retrieval circuit comprising a FIFO memory for retrieving an input display list segment of said display list from said memory unit, said display list comprising a plurality of display list segments linked together under a hierarchical acyclic directed graph format; said information retrieval circuit also comprising a parsing processor for interrogating said input display list to locate control data therein, said control data comprising either a call control data or a return control data for said input display list segment; and control logic for determining if said control data includes said call control data, and if so, (1) for pushing an address and length of a next-to-return display list segment from said call control data onto said stack memory and (2) for transferring an address and length of a jump-to display list segment from said call control data to a retrieval circuit, said control logic also for determining if said control data includes said return control data word, and if so, (1) for popping an address and length of a return display list segment from said stack memory and (2) for transferring said address and length of said return display list to said retrieval circuit.
Claim 21
Dependent Claim
29 words
A system as described in claim 17 wherein said control data is located at the end of each of said plurality of display list segments of said display list.
Claim 22
Dependent Claim
29 words
A system as described in claim 17 wherein said control data is located at the front of each of said plurality of display list segments of said display list.
Claim 23
Dependent Claim
53 words
A system as described in claim 19 wherein said parsing processor supplies information from said input display list segment to a graphics generation circuit for visualization while said retrieval circuit initializes retrieval of said jump-to display list segment upon said retrieval circuit receiving said address and length of said jump-to display list segment.
Claim 24
Dependent Claim
28 words
A system as described in claim 20 wherein said graphics information of said display list comprises graphics primitives and wherein said retrieval circuit is a DMA retrieval circuit.
Claim 25
Dependent Claim
53 words
A system as described in claim 19 wherein said parsing processor supplies information from said input display list segment to a graphics generation circuit for visualization while said retrieval circuit initializes retrieval of said return display list segment upon said retrieval circuit receiving said address and length of said return display list segment.
References Cited (Backward Citations)
US4312066A
Cited
US4862392A
Cited
US4967375A
Cited
US5206940A
Cited
US5097411A
Cited
US5179658A
Cited
US5193169A
Cited
US5020003A
Cited
US5018079A
Cited
US5251303A
Cited
US5058042A
Cited
US5388229A
Cited
US5333290A
Cited
US5291582A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-08-11 | 2001-02-10 | 2001-08-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-08-11 | 2005-02-10 | 2005-08-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-08-11 | 2009-02-10 | 2009-08-12 | $7700.00 | Window Closed / Lapsed |