Tile based rendering of smooth points using polygons

• US 8,654,129 B2
• Filed: 05/19/2010
• Issued: 02/18/2014
• 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
• Primary Examiner(s): Ma, Tize
• Application Number:
  US12/783,549
• Publication Number:
  US 20100225652A1
• Time in Patent Office: 1,371 Days
• Field of Search: 345441-443
• 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 a computing device to render a circular point on a display device, the circular point having a center, radius and a circumference and enclosed within a bounding area having a larger circumference than the circumference of the circular point, comprising the steps of:

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

determining vertices of the polygon;

logically dividing the bounding area into a plurality tiles, wherein the size of each of the plurality of tiles is determined by a user, the vertices of the polygon being within the one or more tiles;

classifying at least one of the one or more tiles of the bounding area according to the center and the radius of the circular point, wherein the at least one tile of the bounding area is classified into a predetermined section;

generating a mask for the at least one tile of the bounding area according to the classified predetermined section of the at least one tile; and

rendering the circular point according to the mask for the at least one tile of the bounding area.

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 connects two vertices and touches 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. The method of claim 1, wherein the bounding area is a rectangular area.

6. The method of claim 1, wherein the predetermined section is selected from the group consisting of a central section, a vertex section, an axial section, and a corner section, the central section being the tile that includes the center of the circular point, the vertex section being the tile that includes the farthest axial portion of the circular point, the axial section being the tile that is located between the central section and the vertex section, the corner section being the tile that is neither classified as the central section, the vertex section, nor the axial section.

7. The method of claim 1, wherein generating the mask for the at least one tile of the bounding area is performed according to the determined vertices of the polygon.

8. A method for a computing device to render 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 to enclose the polygon, the circumference of the bounding area being larger than the circumference of the circular point;

logically dividing the bounding area into a plurality of tiles, wherein the size of each of the plurality of tiles is determined by a user, the vertices of the polygon being within the one or more tiles;

classifying each of the one or more tiles of the bounding area into a section;

generating a mask for each of the one or more tiles of the bounding area according to its classified section; and

rendering the circular point according to the mask for each of the one or more tiles of the bounding area.

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

10. The method of claim 8, 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.

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

determining vertices of the polygon;

determining an edge that connects two vertices and touches 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.

12. An apparatus for rendering a circular point on a display device, the circular point approximated by a polygon that is enclosed by a bounding area having a larger circumference than the circumference of the circular point, the bounding area being divided into a plurality of tiles, wherein the size of each of the plurality of tiles is determined by the user, and wherein each tile is classified into a section, the polygon having an internal area and an external area within the bounding area, comprising:

a hardware having a polygon database;

a hardware containing 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, identifying one or more of the plurality of tiles that are within the bounding area, and determining whether a point in the bounding area is internal or external to the polygon according to the classified section; 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.

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

14. The apparatus of claim 13, wherein the diameter is measured in pixels.