Tile Based Rendering Of Smooth Points Using Polygons

• US 20100225652A1
• Filed: 05/19/2010
• Published: 09/09/2010
• Est. Priority Date: 05/25/2004
• Status: Active Grant

• Current Assignee: Xueshan Technologies Inc. (Wi-LAN Inc.)
• Original Assignee: 3DLabs Incorporated Limited (Creative Technology Ltd.)
• Inventors: DEMING, James L.
• Granted Patent: US 8,654,129 B2
• Time in Patent Office: Days
• US Class Current: 345/442
• CPC Class Codes: G06F 18/24 Classification techniques
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining
• CPC Class Codes: G06T 11/20 Drawing from basic elements, e.g. lines or circles
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 2200/24 involving graphical user interfaces [GUIs]
• CPC Class Codes: G06T 5/00 Image enhancement or restoration
• CPC Class Codes: G06T 7/74 involving reference images or patches

Abstract

An apparatus and method for rendering a smooth circular point using polygons on a computer graphics display. The circular point is approximated by a polygon and the selection of the polygon depends on the diameter of the point. The polygon is enclosed in a bounding area that is divided into a plurality of tiles. The tiles are classified into different sections depending on their location relative to the center of the point. The tiles in each section are processed according to an algorithm to generate a mask that is used to render the circular point.

Claims

1. A method for rendering a circular point on a display device, the circular point having a center, radius and a circumference and located within a bounding area, comprising the steps of:

selecting a polygon representing the circular point from a predefined set of polygons;

determining vertices of the polygon;

dividing the bounding area into one or more tiles;

classifying at least one tile of the one or more sections according to the center and the radius of the circular point, wherein the at least one tile is classified into one or more predetermined sections;

generating a mask for the at least one tile according to a section of the at least one tile; and

rendering the circular point according to the mask.

2. The method of claim 1, wherein the step of selecting a polygon further comprises the step of selecting an entry from a polygon table according to the radius of the circular point.

3. The method of claim 1, wherein the step of determining vertices further comprises the step of selecting vertices from a vertex table.

4. The method of claim 1, wherein the step of generating a mask further comprises the steps of:

determining an edge that connect two vertices and touch the at least one tile;

determining whether a point in the at least one tile is inside the polygon based on a position of the point relative to the edge; and

representing the point in the mask.

5. A method for rendering a circular point on a display device, the circular point having a center, radius and a circumference, comprising the steps of:

approximating the circular point by a polygon;

defining a bounding area for the polygon;

dividing the bounding area into one or more tiles;

generating a mask for each tile; and

rendering the circular point according to the mask.

6. The method of claim 5, wherein the step of approximating the circular point further comprises the step of selecting a polygon from a polygon table according to the radius.

7. The method of claim 5, wherein the step of defining a bounding area further comprises the step of calculating four corners based upon the center and the radius of the circular point.

8. The method of claim 5, wherein the step of generating a mask further comprises the steps of:

determining vertices of the polygon;

determining an edge that connect two vertices and touch at least one tile;

determining whether a point in the at least one tile is inside the polygon based on a position of the point relative to the edge; and

representing the point in the mask.

9. An apparatus for rendering a circular point on a display device, the circular point approximated by a polygon bounded by a bounding area, the polygon having an internal area and an external area within the bounding area, comprising:

a polygon database;

a vertex database;

an edge evaluator in communication with the polygon database and the vertex database, the edge evaluator receiving polygon information from the polygon database and vertex information from the vertex database and determining whether a point in the bounding area is internal or external to the polygon; and

a drawing element in communication with the edge evaluator, the drawing element approximating the circle by rendering every point in the bounding area depending on whether the point is in the internal area or external area of the polygon.

10. The apparatus of claim 9, wherein the polygon database further comprises of a plurality of entries, each entry listing a diameter and a corresponding polygon.

11. The apparatus of claim 10, wherein the diameter is measured in pixels.

12-19. -19. (canceled)