Method and apparatus for span and subspan sorting rendering system

• US 6,285,378 B1
• Filed: 03/08/1999
• Issued: 09/04/2001
• Est. Priority Date: 07/26/1995
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Duluk, Jerome F. Jr.
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US09/264,302
• Time in Patent Office: 911 Days
• Field of Search: 345/418, 345/419, 345/441, 345/442, 345/443, 345/118, 345/433
• US Class Current: 345/441
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 15/10 Geometric effects

Abstract

A data shifting capability that permits sorting the data in addition to searching for obtaining real-time performance in color, with high quality imagery through a simple search of a spacial database based on a rectangularly shaped search region or range search. A sorting Magnitude Comparison Content Addressable Memory (SMCCAM) performs a range search, introducing a conservative approximation of the idea Occluding Region, and provides a MCCAM wherein the data words stored in the fields are shifted to corresponding fields in an adjacent word, based on the magnitude comparisons. The 3D graphics method stores the parameters of a polygon span in a spatial database and a query operation is performed on the database to determine which of those spans, or portions of spans, are visible, and applies a rule for comparing a new span portion to an old span portion on a subspan-by-subspan basis, thereby providing additional polygon edge information within a raster line, providing anti-aliasing.

Claims

1. A sorting magnitude comparison content addressable memory (SMCCAM) apparatus comprising:

a plurality of addressable memory storage bits, each said storage bit for storing a data bit, said memory storage bits arranged into a plurality of words;

an input circuit providing an input comprising a plurality of input bits matching some of said data bits so as to have a one-to-one bit correspondence to said data bits;

a comparator circuit simultaneously comparing said plurality of input bits to data bits in all said words, said comparator circuit making simultaneous comparisons such that each said data bit is compared to its corresponding input bit, and said comparator circuit generating a query result for each said word which query results has a first state when all said data bits within said word which are compared to one of said input bits compare favorably to each corresponding input bit, and a second state when said bits do not compare favorably;

a flag memory storage storing a flag bit generated from said query result for each of said words;

an up-counter circuit for each said word, said up-counter circuit being conditionally incremented according to said flag bit, the up-counter used to indicate a position in an ordered list; and

a circuit locating the smallest value in said up-counter circuits.

2. In a graphical processing system for processing 3-dimensional object geometry data and rendering at least some of said object geometry data on a 2-dimensional display screen, said object geometry comprising polygons, a method for rendering a display raster line comprising the steps:

(i) maintaining a list of current polygons that intersect a current display raster line;

(ii) generating a polygon span for each polygon that intersects said current display raster line based on geometric properties of said polygon including said polygon parameters, each said polygon span including subraster information describing the geometric shape of said span within a vertical extent of said display raster line;

(iii) generating at least one dummy span, said dummy span representing a location and a clipping function of a clipping plane, each said dummy span including subraster information describing the geometric shape of said span within a vertical extent of said display raster line;

(iii) storing said geometric properties of each said generated span into a span memory, said generated spans, said current span portion comprised of a set of current subspans, each said

(iv) maintaining a current span portion that is part of a potentially visible one of said generated spans, said current span portion comprised of a set of current subspans, each said current subspan representing a rectangular area within said current span portion, and said set of current subspans approximating an area of said current span portion;

(v) performing at least one span occluding test to find any new span that potentially occludes said current span portion, where said span occluding test comprises;

(1) determining the leftmost, rightmost, and farthest spatial coordinates in said set of current subspans; and

(2) performing a query operation on the said stored geometric properties in said span memory to find all said spans whose stored geometric properties include a spatial coordinate located between said leftmost and said rightmost spatial coordinates of the said set of current subspans, and a spatial coordinate closer than said farthest spatial coordinate of the said set of current subspans;

(vi) generating a set of new subspans, each said new subspan representing a rectangular area within said new span, and said set of new subspans approximating an area of said new span;

(vii) for each said subspan in said set of current subspans, performing a subspan comparison comprising;

(1) performing a spatial comparison between said subspan in said set of current subspans and a corresponding subspan in the said set of new subspans; and

(2) determining the visibility, partial visibility, or non-visibility of each subspan in said set of current subspans, taking into account the clipping function of one of the dummy spans if the new span is a dummy span; and

(viii) updating said current span portion based on result of said subspan comparisons.