Tile based rendering of smooth points using polygons

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.

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 . A computer-readable medium on which is stored a computer program 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, the computer program comprising instructions which, when executed by a computer, perform 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.    
   
   
       13 . The computer program of  claim 12 , 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.  
   
   
       14 . The computer program of  claim 12 , wherein the step of determining vertices further comprises the step of selecting vertices from a vertex table.  
   
   
       15 . The computer program of  claim 12 , 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.    
   
   
       16 . A computer-readable medium on which is stored a computer program 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, the computer program comprising instructions which, when executed by a computer, perform 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.    
   
   
       17 . The computer program of  claim 16 , wherein the step of approximating the circular point further comprises the step of selecting a polygon from a polygon table according to the radius.  
   
   
       18 . The computer program of  claim 16 , 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.  
   
   
       19 . The computer program of  claim 16 , 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.