Object processing for video system using slips and linked list
First Claim
1. An apparatus for rapidly processing data records representing moving and non-moving objects on a playfield to determine which objects to display on a portion of the playfield being displayed on a video display comprising:
- means for organizing all of the data records for moving objects to be displayed as a single linked list in memory, said single linked list organized by the locations where the objects would be displayed if the whole playfield were to be displayed;
means for processing only that portion of the single linked list for objects positioned near said portion of said playfield to be displayed;
wherein the data records for said objects include positional information expressed as x and y coordinate offsets from a reference point on the playfield.
4 Assignments
0 Petitions
Accused Products
Abstract
There is disclosed herein a system for rapid processing of the data records of many moving and nonmoving objects on a playfield only part of which is displayed and for determining collisions between objects. A search pipeline using a synchrounous state machine searching a linked list of the records organized by approximate position on the playfield implements the search function. A lookahead cycle in the state machine is provided to continue searching for the next object which is to be visible while the graphic data from a previously found object is being loaded into a line buffer. Slips point to the first objects on the list for the current scan line speed up the search process.
-
Citations
18 Claims
-
1. An apparatus for rapidly processing data records representing moving and non-moving objects on a playfield to determine which objects to display on a portion of the playfield being displayed on a video display comprising:
-
means for organizing all of the data records for moving objects to be displayed as a single linked list in memory, said single linked list organized by the locations where the objects would be displayed if the whole playfield were to be displayed; means for processing only that portion of the single linked list for objects positioned near said portion of said playfield to be displayed; wherein the data records for said objects include positional information expressed as x and y coordinate offsets from a reference point on the playfield.
-
-
2. An apparatus for rapidly processing data records representing moving and non-moving objects on a playfield to determine which objects to display on a portion of the playfield being displayed on a video display comprising:
-
means for organizing all of the data records for moving objects to be displayed as a single linked list in memory, said single linked list organized by the locations where the objects would be displayed if the whole playfield were to be displayed; means for processing only that portion of the single linked list for objects positioned near said portion of said playfield to be displayed; wherein said means for processing includes means for generating a slip indicating where on said linked list to begin processing to determine which moving objects are to be displayed said means for processing also for using said slip to control where processing on said linked list should begin so as to process only those data records for objects which are positioned on said playfield near said portion of said playfield to be displayed. - View Dependent Claims (3, 4, 5, 6, 7)
-
-
8. An apparatus for determining which of a plurality of motion objects positioned on a playfield to display on a video display in a window portion of said playfield, said window portion defined by a plurality of sequentially scanned raster scan lines including a current raster scan line defined as the raster scan line being processed at any particular moment:
-
first means for determining the current positions of said motion objects on said playfield and for storing in memory a data record for each motion object said data record for each said motion object including position information expressed in playfield relative terms as an offset from a known reference position on said playfield, said data records organized as a single linked list organized in the order the motion objects would be displayed if the entire playfield including all the motion objects thereon were to be displayed; second means for determining the position of said window portion of said playfield on said video display by determining in playfield relative terms as an offset between a point in said window and said playfield reference point; third means coupled to said second means for generating a slip from the position information of said window on said playfield, said slip defined as a pointer to the address in said memory of the data record which corresponds to the first motion object on said linked list through which said current raster scan line would pass if said current rater scan line extended completely across said playfield; fourth means coupled to said first, second and third means for using said slip to begin processing data records for motion objects on said linked list starting at the motion object data record identified by said slip to determine which said motion objects to display. - View Dependent Claims (9, 10, 11, 12)
-
-
13. An apparatus for displaying selected ones of a plurality of moving objects located in a window portion on a playfield, said window portion comprising a plurality of raster scan line which are sequentially scanned including a current raster scan line, each said raster scan line having a scan line number and comprised of a plurality of sequentially scanned pixels including a current pixel defined as the pixel being scanned at any particular moment, comprising:
-
means for reading user inputs and other data regarding the movements of said moving objects and for determining the position on the playfield of said moving objects in playfield relative terms with respect to a reference point on said playfield; means for storing data records regarding said moving objects including their playfield relative positions in a random access memory and for linking the data records of said moving objects as a linked list ordered approximately by the order in which said moving objects would be displayed if all the moving objects on the playfield were to be displayed in raster scan order instead of only the moving objects located within the boundaries of the current window portion; means for generating a playfield relative slip pointer from the scan line number of the current raster scan line indicating the address of the data record of said linked list for a predetermined moving object; means for comparing said playfield relative position information of said moving objects on said linked list starting with the moving object indicated by said slip pointer to the current raster scan line number and the position of the window portion to determine which moving objects on said linked list are to be displayed; and means for displaying the moving objects that are visible in said window portion.
-
-
14. A method of determining rapidly which of a plurality of moving objects on a playfield are to be displayed in a movable window displaying a portion of said playfield, said window comprised of a plurality of sequentially scanned raster scan lines including a current raster scan line, and for displaying said moving objects comprising the steps of:
-
organizing data records recording positions of each moving object on said playfield as a linked list ordered by the sequence in which all the moving objects would be written on a video display if the entire playfield were displayed in raster scan fashion instead of only the portion of the playfield visible in said window portion; storing said linked list in memory; generating a slip pointer address based upon said current scan line number, said slip pointer address pointing to the address in said memory of the data record on said linked list corresponding to a moving object positioned on said playfield near or within said window where processing should start; and processing the data records on said linked list starting with the data record pointed to by said slip pointer address to determine which of said moving objects are at least partially visible in said window; displaying those objects on said linked list which have position data indicating that said objects are at least partially visible within said window. - View Dependent Claims (15, 16, 17, 18)
-
Specification