[go: up one dir, main page]

WO2003052733A1 - Utilisation d'informations de structure hierarchique pour ameliorer le dessin au trait dans les systemes numeriques - Google Patents

Utilisation d'informations de structure hierarchique pour ameliorer le dessin au trait dans les systemes numeriques Download PDF

Info

Publication number
WO2003052733A1
WO2003052733A1 PCT/US2002/039716 US0239716W WO03052733A1 WO 2003052733 A1 WO2003052733 A1 WO 2003052733A1 US 0239716 W US0239716 W US 0239716W WO 03052733 A1 WO03052733 A1 WO 03052733A1
Authority
WO
WIPO (PCT)
Prior art keywords
run
order
line
cells
runs
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/US2002/039716
Other languages
English (en)
Inventor
Peter Stephenson
Bruce Litow
Nicholas Diakopoulos
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Fraunhofer CRCG Inc
Original Assignee
Fraunhofer CRCG Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Priority claimed from PCT/US2002/024711 external-priority patent/WO2003012599A2/fr
Application filed by Fraunhofer CRCG Inc filed Critical Fraunhofer CRCG Inc
Priority to EP02790102A priority Critical patent/EP1466313A4/fr
Priority to US10/498,467 priority patent/US20050001840A1/en
Priority to AU2002353125A priority patent/AU2002353125A1/en
Priority to US10/500,772 priority patent/US20050116951A1/en
Priority to PCT/US2003/000240 priority patent/WO2003058405A2/fr
Priority to EP03702002A priority patent/EP1472654A2/fr
Priority to AU2003202890A priority patent/AU2003202890A1/en
Publication of WO2003052733A1 publication Critical patent/WO2003052733A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G09—EDUCATION; CRYPTOGRAPHY; DISPLAY; ADVERTISING; SEALS
    • G09G—ARRANGEMENTS OR CIRCUITS FOR CONTROL OF INDICATING DEVICES USING STATIC MEANS TO PRESENT VARIABLE INFORMATION
    • G09G5/00—Control arrangements or circuits for visual indicators common to cathode-ray tube indicators and other visual indicators
    • G09G5/20—Function-generator circuits, e.g. circle generators line or curve smoothing circuits
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T11/00—2D [Two Dimensional] image generation
    • G06T11/20—Drawing from basic elements, e.g. lines or circles
    • G06T11/203—Drawing of straight lines or curves
    • G—PHYSICS
    • G09—EDUCATION; CRYPTOGRAPHY; DISPLAY; ADVERTISING; SEALS
    • G09G—ARRANGEMENTS OR CIRCUITS FOR CONTROL OF INDICATING DEVICES USING STATIC MEANS TO PRESENT VARIABLE INFORMATION
    • G09G5/00—Control arrangements or circuits for visual indicators common to cathode-ray tube indicators and other visual indicators
    • G09G5/36—Control arrangements or circuits for visual indicators common to cathode-ray tube indicators and other visual indicators characterised by the display of a graphic pattern, e.g. using an all-points-addressable [APA] memory
    • G09G5/39—Control of the bit-mapped memory
    • G09G5/393—Arrangements for updating the contents of the bit-mapped memory
    • G—PHYSICS
    • G09—EDUCATION; CRYPTOGRAPHY; DISPLAY; ADVERTISING; SEALS
    • G09G—ARRANGEMENTS OR CIRCUITS FOR CONTROL OF INDICATING DEVICES USING STATIC MEANS TO PRESENT VARIABLE INFORMATION
    • G09G2300/00—Aspects of the constitution of display devices
    • G09G2300/08—Active matrix structure, i.e. with use of active elements, inclusive of non-linear two terminal elements, in the pixels together with light emitting or modulating elements
    • G09G2300/0809—Several active elements per pixel in active matrix panels

Definitions

  • the invention relates generally to techniques for determining which cells of a raster are intersected by a particular line.
  • the cells of the raster are represented in the memory of a computer system and the determination is made by the computer system's processor.
  • the cells of the raster may generally represent a set of locations. The locations may be pixels in a display, and when they are, the techniques may be used to determine which pixels in the display represent the particular line, and thus to generate the line in the display.
  • FIG. 9 is a high-level overview of a computer system with a raster display device.
  • the main components of system 901 are a processor 911 with memory 903 to which processor 903 has access and a monitor 915 for which processor 911 generates displays.
  • Monitor 915 is a raster display device and as such, has a grid of pixels 917.
  • bitmap 909 is an area of memory that corresponds to grid of pixels 917.
  • Each item of data in bitmap 909 corresponds to a pixel in grid of pixels 917.
  • Drawing code 985 is code for drawing graphical entities such as lines or polygons in bitmap 909.
  • Bitmap data 907 is data, typically supplied by a user program, which bitmap drawing code 985 uses to draw a graphical entity.
  • processor 911 For example, if a user program wishes to specify a line, it will typically indicate the start and end coordinates of the line in grid of pixels 917 and drawing code 985 will use that information to draw a corresponding line in bitmap 909.
  • Processor 911 then reads from bitmap 909 to generate an image for display on grid of pixels 917.
  • a display generator component 913 of processor 911 reads bitmap 909 and produces the actual signals for monitor 915 from the data in bitmap 909. It should be noted here that the task of producing a display 917 may be distributed in many different ways across hardware and software components, with the amount of hardware increasing as performance demands increase.
  • FIG. 10 Drawing straight lines is a problem with any raster display device.
  • FIG. 10 shows why.
  • the representation includes those pixels in the grid that are intersected by line 1003. These pixels form a pattern 1004 that is termed the intersection pattern for the line.
  • a line's intersection pattern depends not only on the line's slope, but also on the location of its endpoints relative to the grid of pixels.
  • the intersection pattern for any straight line has regular features that can be used in drawing the straight line in a raster display or analyzing a straight line that is displayed in a raster display.
  • the intersection pattern for line 1003 is a sequence of pixels. For a given next pixel, there are only two possibilities: if the current pixel has the coordinates (a.b), the next pixel has either the coordinates (a+l,b) or (a+l,b+l). Which of the two possibilities the next pixel has depends on where the line intersects the current pixel. To draw a line one pixel at a time, one need only determine for each pixel where the line intersects the current pixel and use that information to determine which of the two possible positions to give the next pixel. As is apparent from FIG. 10, the intersection pattern includes groups of adjacent pixels that have the same v coordinate. Such a group of pixels is called a run. One such run of three pixels is shown at 1005.
  • line 1003 contains 41 pixels and 17 runs.
  • intersection pattern 1004 of line 1003 shows that the long and short runs themselves occur in repeating patterns.
  • intersection pattern 1004 there is a repeating pattern of a long run (/) followed by two short runs (s) followed by a long run followed by one short run, or Issls, as shown at 1011 and 1013.
  • Issls In general, there are four possibilities for the patterns of runs:
  • intersection pattern 1004 the complete sequence of runs is Islslsslslslss; therefore we have singularly occurring runs / separating sequences of shorts runs s + and the intersection pattern is constructed of runs of runs with the shape Is*.
  • the terminology of runs of runs is cumbersome so let us define these runs of runs to be second order runs. Where a run is defined by its position and length, a second order run is defined by its position, its length is defined by the number of runs which comprise it, and its shape is determined by whether there are more long or short runs in the pattern.
  • runs can be first order runs and pixels to be zero order runs.
  • the number of second order runs must be the same as the number of long runs in the pattern by definition. If there are n long runs in the line there are a runs to divide amongst n second order runs. Therefore if the division is to be as even as possible the length of a short second order run, r l2] , will be
  • the second order runs appear at 1011 and 1013 in intersection pattern 1004. There are more short runs 1013 than long, so the second order runs have the shape ls + , i.e., one long run followed by a sequence of short runs. There are three long runs 1011 of length three and four short runs 1013 of length two.
  • the shape of the order 3 runs is s I. For lines with a rational slope, the hierarchical description of ordered runs within the intersection pattern will be bounded, as the intersection pattern is eventually repeated if a and d are not coprime.
  • 17 is the entire intersection pattern of the line / : y - — x and the lattice ⁇ £ (4 ⁇ ,i 7 )
  • the b m numerator sequence is a sequence of the numerators of the fractions - L — . These fractions d specify the point in the left edge of the pixel at which the line intersects the pixel. Therefore the line is at least — from any lattice point. If the value of ⁇ is raised slowly, the intersection d pattern will remain unchanged until the line crosses or intersects a lattice point. Therefore the first change will occur when ⁇ - — . Let the lattice point intersected be (x h , ytj. d
  • FIG. 11 gives an example. At 1001, the figure shows the intersection pattern of the line
  • the numerator sequence for order 0 of 1001 is shown at 1 109 and that for order O of 1101 at 1 111.
  • the shifting of the intersection pattern due to the introduction of a non-zero intercept has a number of side effects.
  • DDA works at the pixel level. Initially, floating-point x and y increments are computed. The x increment is the difference between the ending and starting x coordinates divided by the line's length and the y increment is the difference between the ending and starting y coordinates divided by the line's length. Each time a pixel is set, the current x and y coordinates, which are floating point values, are converted to integers and the pixel is set at the cell defined by the increment. Then the x increment is added to the x coordinate and the y increment is added to the y coordinate.
  • a difficulty with any pixel-by-pixel approach is that it requires a determination where the next pixel will be placed relative to the last pixel for each new pixel.
  • this determination is a floating-point operation. As such, it is both expensive to perform and subject to rounding errors. Moreover, because the determination must be performed with every pixel, the rounding errors may accumulate quickly and cause the line to be drawn inaccurately.
  • run-based line drawing An important advantage of run-based line drawing is that the structural information about the line that is used to determine which run length is to come next may also be used to accelerate other processes involved in drawing the line as well.
  • three examples of such acceleration are given: parallelization of drawing full runs, using the structural information in adding anti-aliasing pixels to lines, and using the structural information to set lines in a memory that permits writing of blocks of contiguous pixels. It is thus an object of the present invention to provide improved techniques for drawing lines that are based on the structural information used to do run-based line drawing.
  • One use of the structural information is to compute the positions of a plurality of sets of cells and then processing the sets of cells in parallel.
  • the parallel processing may be done either by processing the sets of cells in parallel or by processing cells within the set of cells in parallel.
  • the sets of cells whose positions are computed may include cells belonging to a full run and may also include additional cells that are affected when a cell is intercepted by a line.
  • Another use of the structural information is to determine how to process additional cells that are affected by run-based line drawing.
  • additional cells are anti-aliasing cells.
  • the structural information may be used to determine the number and location of the anti-aliasing cells relative to the cells of a run and also to determine how the values of the pixels in the antialiasing cells are set. In the latter case, the values may be set in accordance with the value of an error term ⁇ that indicates where the line intersects the leading edge of the first cell in the run.
  • the anti-aliasing cells may be added to the ends of the run, above or below the run, or both.
  • Such additional cells may also be involved in systems where a number of pixels are read from or written to memory in a single operation.
  • the structural information can be used to determine how a chunk that contains cells of a run and/or anti-aliasing cells is to be written to the memory.
  • Sets of cells that include additional cells may of course be processed in parallel in the same fashion as sets of cells that include only the cells of a run.
  • FIG. 1 is an overview of the manner in which lines are drawn using the techniques of the invention
  • FIG. 2 is an overview of a system which draws lines using the techniques of the invention
  • FIG. 3 is a flowchart of how the bitmap processor processes complete runs of pixels
  • FIG. 4 is a flowchart of how the bitmap processor processes truncated runs of pixels
  • FIG. 5 is a flowchart of how the bitmap processor processes a run of order 1;
  • FIG. 6 is a flowchart of how the first truncated run of an order i is processed and set;
  • FIG. 7 shows how the first pixel of a line is handled using the techniques of the invention
  • FIG. 8 shows a flowchart of how a complete run of order / is processed
  • FIG. 9 shows a system in which the invention may be employed
  • FIG. 10 shows the structure of a representation of a line as a set of pixels
  • FIG. 11 shows the effect of a displacement of the starting point from the origin on the structure of the representation
  • FIG. 12 shows an example line
  • FIG. 13 shows how the first pixel of the example line is handled;
  • FIG. 14 shows truncated runs of orders 1-3 in the example line;
  • FIG. 15 shows the geometry of the error term and structural parameters in a run of order 1;
  • FIG. 16 is a flowchart of a technique for drawing lines in parallel;
  • FIG. 17 is a detail of an aliasing technique;
  • FIG. 18 shows three different anti-aliasing masks;
  • FIG. 19 shows lines drawn using anti-aliasing masks;
  • FIG. 20 is a graph showing speed of execution of line drawing using run masks
  • FIG. 21 shows a line drawn using HI and H3 anti-aliasing masks and details of the anti-aliasing masks; and FIG. 22 shows how an anti-aliasing mask may be associated with a range of values of ⁇ .
  • FIG. 1 Overview of line drawing with the invention: FIG. 1
  • FIG. 1 is a flowchart [101] that provides an overview of how a line segment may be drawn using this invention.
  • Starting parameters include the maximum order of the runs to be used in drawing the lines [122] and the start and endpoints of the line [112,114].
  • the maximum order can be predefined by the manufacturer of an apparatus based on the invention, calculated based on the characteristics of the system or based on the length of the line. In the preferred embodiment the maximum order of the runs [120] is set to two.
  • the line segment defined between the starting point [112] (x 0 ,y 0 ) and the end point [114] (x,, >,) consists of, at most, three sets of runs of any order, /: The first truncated run of order i, the set of full-length runs of order i, and the final truncated run of order /.
  • the first truncated run of order i the set of full-length runs of order i
  • the final truncated run of order / To draw the line segment from (x 0 ,y 0 ) to (x ⁇ y , we will describe how to calculate and set in the Bitmap Memory [108]: • The first truncated run of order i [202] .
  • An alternative embodiment would calculate the first truncated run, each full length run and the final truncated run separately.
  • Another alternative embodiment would have a desired maximum order [120] of infinity, and therefore the processing of the first truncated run length would draw the entire line segment unless the maximum depth of the hierarchy of runs was reached.
  • FIG. 2 Overview of the components of a system for drawing lines according to the invention: FIG. 2
  • FIG. 2 shows the components of a system 201 for drawing lines according to the invention.
  • the main components of system 201 are a Truncated Run Processor [102], which calculates the structure of the first truncated run of order i [202] and the structure of the hierarchy of runs [140] in the line segment, and the Run Processor [104], which calculates the length of the full length runs and the final truncated run [206].
  • the Run Processor [104] calculates the length of the full length runs and the final truncated run [206].
  • the Bitmap Processor is responsible for breaking the run into its composite pixels and setting each pixel into the Bitmap Memory [108].
  • the Truncated Run Processor [102] is responsible for calculating the structure of the first truncated run of the desired order [120] and supplying this structure to the Bitmap Processor [106] so that the truncated run [194] can be set into the Bitmap Memory [108].
  • Bitmap memory [108] may be a bit map such as bitmap 909 in FIG. 9.
  • Truncated Run Processor calculates the structure of the first truncated run, it also calculates the structure of the hierarchy of runs [140] and stores this information [142] for the use by the Run and Memory Processors [104,106]. During this process if the desired maximum order of the process [ 120] is found to be greater than the maximum order of the hierarchy of runs in the line, the maximum order [120] is set to be the maximum depth ofthe hierarchy [124].
  • the Truncated Run Processor Based on the start and end points of the line [110], the Truncated Run Processor also calculates and stores [132] the starting pixel position for the line [130]. Each component of the first truncated run is calculated based on the error term [150]. As each component is processed the error term is retrieved [152], updated and stored again [154]. Once the first truncated run has been processed, the error term remaining [150] is used by the Run Processor [104] to define the full-length runs in a similar manner.
  • the Run Processor [104] is responsible for calculating the length of each full-length run of the desired maximum order in the digital line. These lengths are passed to the Bitmap Processor [106] such that the runs can be set into the Bitmap Memory [108]. The length of the full-lengths is decided based on the error term [150], which is retrieved [156], updated and stored [158] to process the next full-length run. Thus, the error term is recalculated only at the beginning of each full-length run of the maximum order instead of for each pixel.
  • Bitmap Processor [106] The Bitmap Processor [106] is responsible for actually setting the runs into the Bitmap Memory [108].
  • the Bitmap Processor [106] also keeps a track of the current position of the line being drawn in relation to the end point of the line [1 10]. If the line moves reaches the end point [1 14], the Bitmap Processor [106] signals the Truncated Run Processor [102] or the Run Processor [104] to terminate [162] using an internally stored termination condition [160].
  • the Bitmap Memory [108] is the memory representing the raster display of a graphics system, video memory, image memory or any other type of bitmap.
  • the Bitmap Processor [106] handles the process of setting the pixels of the Bitmap Memory [108]. To draw the line, the Bitmap Processor is given a set of commands [194][196] to draw a collection of runs of various orders into the Bitmap Memory. The information given in the command to draw a run is the length of the run, r [ J ] , and the order of the run, i [194] [196]. The position of the run in the bitmap [130], x j [ y j ] ) , is initialized [132] by the Truncated Run
  • Bitmap Memory [108] permits the setting of runs of pixels or runs of runs, etc., the process of reducing the run of order / to runs of order i-1 can be stopped at the permitted level. Therefore instead of setting pixels into the Bitmap Memory, runs or runs of runs can also be used.
  • each run of any nonzero order / within the digital line has, at most, only two possible run lengths that are consecutive integers where the length is measured as the number of composite runs of the next lowest order, i-l.
  • the runs of order 1 in the line segment (0, 0) to (41, 17) can be described by (Islslsslslslslsss) ' ' .
  • a run of order - can then be defined recursively by:
  • a run of order 1 is the maximal set of contiguous pixels with a similar abscissa.
  • a run of order i is the maximal set of contiguous runs of order i-1 such that each run has a shape (l + s) [ '-' J , (ls + ) *" IJ , (s + l) ⁇ "M or (sl + ) [ " l] , where (l + ) [ "' ] and (s + ) r "' ⁇ denote the occurrence of one or more long and short runs of order i-1 respectively.
  • a run of order 2 can only possess the shape ( s) [1J or (/-. + M
  • the type of order 1, / [1] is defined to be zero.
  • the types of orders greater than 1 are calculated using structural parameters; the structural parameters and their calculation will be described in detail below.
  • Inputs to the process are the length of the run of order i to be set [194] and the structure of the hierarchy of runs. The process will cease if the end point ofthe line has been reached [304].
  • the pixels of the run are set directly [340] into the Bitmap Memory. If the order of the run is at least 2, the run is reduced into its composite runs of the next lesser order and each run is set into the Bitmap Memory:
  • the process of reducing the first truncated run of order k into full-length runs of order k-1 follows directly from the instructions to reduce full-length runs.
  • the only variation comes from the fact that a truncated run is defined to be a run not of its full-length. Therefore at least one run of order k-1 has been truncated from the run of order k. Because this is the first run in the line, the truncated run occurs at the beginning of the run.
  • the process is shown at 401 in FIG. 4.
  • the inputs are the length of the run of order / that is to be set [194] and the structure of the hierarchy of runs [146].
  • the process 401 will cease if the end point ofthe line has been reached [404].
  • the truncated run comprises two long runs and the final short run of order i-1: (lls/' ⁇ 1J . Therefore to set the initial truncated run length, we set in order r ⁇ - 1 long runs of order i-1 (length r ]' ⁇ n - r [ X ] + 1 ) [412] and one short run of order i-1 (length r s " ' 1 ) [414].
  • FIG. 5 Setting the pixels of a run of order 1 into the Bitmap Memory: FIG. 5
  • FIG. 5 is a flowchart 501 showing how to set the pixels of a run of order 1 [340].
  • the method requires as inputs the starting pixel [136], (X j y ⁇ ] ) , the end point of the line [114], and the length of the run [194], rj ] , are required.
  • the starting pixel is stored and updated internally [136].
  • the length of the run [194] is passed to the Bitmap Processor.
  • Each pixel in the run has a similar y-coordinate, which is the y-coordinate of the starting pixel [136], Vj
  • the starting coordinate of the next run of order 1 in the line is calculated from the current coordinate value by incrementing the current y-coordinate of the next pixel position [430], (-t m , , ;. m , ) - (x[ 0] , y [ ° ] + 1) .
  • FIGS. 6 and 12 How the first truncated run of order i in the line segment is processed by the Truncated Run Processor: FIGS. 6 and 12
  • a truncated run length of order k is of course made up of run lengths of orders 0 through k-1.
  • the bits for that order are set before the next higher order is processed.
  • the bits set for order - ' -1 will always make up the complete truncated or untruncated first run of the order i .
  • the endpoints of the line segment are the real number coordinates (x 0 ,y 0 ) and ( , , ⁇ , ) [112], such that x 0 ⁇ x x and y Q ⁇ y x , therefore the slope of the line, a , has a value between zero and one, 0 ⁇ ⁇ 1.
  • Example line 1201's endpoint (x 0 , yo) 1203 is (1/ 2,12/ 41) ; its endpoint (x y,) 1207 is (41 + 1/2,17 + 12/41) . Note that while the coordinates of the endpoints are rational numbers in this case, a coordinate may be any real number.
  • the first step in the algorithm is to handle the pixel in which the start point of line lies as described in FIG. 13. At the completion of this step, the dark pixel 1301 at the start of the line 5 will have been processed.
  • the coordinates of the lower left-hand corner 1303 of pixel 1301 that contains the start point 1203 of line 1201 is:
  • the choice from these two is made using the value of the error term ⁇ 0 [0] .
  • the choice from these two is made by the value of the error term j ⁇ 0 [0] .
  • the next pixel is pixel (xj ⁇ 1 + 1, y 0 [0] ) .
  • the next pixel is pixel (x 0 [0] + l,y 0 l0] + 1) . Accordingly the error term is also updated.
  • the coordinate (x Q ] ,y 0 l] ) is stored as the position ofthe next run in the line segment [130].
  • the error term ⁇ 0 [0] is stored [152] as the error term for the next run [150].
  • the current error term of order k is the next error term for order k+1 [532].
  • the structure of the hierarchy of runs stores a description of each level in the hierarchy from order 1 to the defined maximum order [120].
  • Each record of the description for order - ' stores the following entries:
  • the type of the runs of order - ' in the line, t either 0 or 1.
  • the error parameter ⁇ l ' ] is used to calculate lengths of runs and the structural parameters L. (,, and ⁇ [, are used to determine the type of an order.
  • FIG. 15 shows geometrically why the error parameter and the structural parameters can be used in this fashion.
  • the figure shows a first-order run / of pixels 1505 representing a portion of line 1507 with slope a .
  • the slope ⁇ r [1] of the run is the same as the slope of the line 1507.
  • Shown at 1503 is the last pixel of the run y ' -l .
  • the coordinates (xJ [ ⁇ y j [ ] ) are the coordinates of the lower left-hand corner of the first pixel of run j; the coordinates x j l l x ,y l l x ) are the coordinates of the lower left-hand corner of the first pixel of the first pixel of run j+1.
  • the values of the error parameter and the structural parameters are defined geometrically by means of lines that are parallel to line 1507 and intersect corners of the pixels of run j.
  • line 1509 intersects the upper left-hand corner of pixel 1503;
  • line 1511 intersects the upper left- hand corner of the last pixel 1506 in r nj; line 1513 intersects the bottom left-hand corner of the first pixel in run /.
  • the error parameter r ] is the distance on the line formed by the top of pixel 1506 between the intersections of lines 1507 and 1513 with that line. The greater the distance between lines 1507 and 1513, the shorter the next run must be. Moreover, since a line is drawn beginning with a partial run of the maximum order k and the partial run is made by beginning with a partial run of order 1, followed by a partial run of order 2, and continuing through order k, the error term for the partial run of order i is that resulting from order / - 1.
  • the structural parameter ⁇ 3 [1] is the distance on the line formed by the top of pixel 1506 between the intersection of line 1513 with the line formed by the top of pixel 1506 and the upper left- hand corner of pixel 1506.
  • the structural parameters vary with the slope c--'- 1 of the line as represented by runs of order i, and thus can be used to determine the type of order i + 1.
  • FIG. 14 shows line 1201 and the pixels 1402 that will be generated to represent it according to the technique under discussion.
  • At 1401 is shown how the first truncated run 1403 of order 1 is set;
  • at 1405 is shown how the first truncated run 1405 of order 2 is set; and
  • at 1407 how the first truncated run of order 3 is set.
  • first pixel 1301 has been set and the position of the next pixel relative to first pixel 1301 has been determined as described above.
  • the next step is to handle the first truncated run of order 1 if it exists.
  • the portion on the line that will be processed is described by the dark pixels 1403.
  • Order 2 The initial truncated run of order 21405 is described by the dark pixels 1407 in line 1201.
  • the initial truncated run of order 2 has a length of one (i.e. one run of order 1).
  • the last run of order 1 in a run of order 2 is a short run of order 1.
  • a short run of order 1 has a length of two pixels. Therefore two pixels are set in this stage.
  • the initial truncated run of order 3 1409 is described by the dark pixels 1411.
  • the initial truncated run of order 3 has a length of one (i.e. one run of order 2).
  • the runs of order 3 in the line have a shape s + l , the last run of order 2 in a run of order 3 is a long run. Therefore we will set a run of order 2 of length three.
  • a single run of order 2 comprises the run of order 3.
  • the normalized intercept value of order 3 5/6 , can be used to initialize the iterative decision process.
  • the Run Processor [104] performs the steps shown in flowchart 801.
  • the inputs are the maximum order of the runs
  • the run processor determines the length of the run of order i in the line and passes the run's length and order to the Bitmap Processor [106] to set the actual pixels of the run into the Bitmap Memory [732].
  • the calculation of the length of the run of order i is based on the type of order (i) [702] and the value of the error term [150] , ⁇ j ⁇ retrieved [158] by the Run Processor [710,720].
  • the run is set into memory [194] by the Bitmap Processor [106] and [732].
  • the Run Processor keeps processing runs as just described until it reaches the end of the line segment [730].
  • a technique similar to the 2D polygon scan conversion embodiment is used.
  • a technique that is also possible is to shade the polygon using lines of constant depth. Think of a plane parallel to the view plane being used. As the plane is moved backwards through the polygon, the line of intersection between the plane and the polygon can be defined. This line has a constant depth that can be used to make the shading technique more efficient. To shade the polygon you can step along this line using the line drawing technique described setting each pixel the color calculated by the shading algorithm.
  • a common problem is to determine if two points are visible to one another. If the environment that can occlude the two points can be defined on a 2D grid, the line drawing technique describe can be used to check each of the grid points linearly separating the two points to determine if they are occluded from one another.
  • Ray tracing has long been used to render height fields or elevation maps.
  • the run-based ray line drawing technique can be adapted to traverse a ray over the height field to seek an intersection with an elevation.
  • the voting process requires a line of votes to be cast into an array.
  • the run-based line digitization techniques described can be used to cast the votes.
  • FIG. 1 Parallel techniques for determining the cells of a raster that are intercepted by a line: FIG.
  • An advantage of using runs of any order n to determine the cells of a raster that are intercepted by a line is that once the first truncated run of order n is drawn and the structural information about the line has been computed, it can be used to determine the positions in the raster of all of the other runs of order n of cells that are intercepted by the line. Consequently, if the hardware or software being used to determine the cells permits it, the cells belonging to the other runs of order n can be computed in parallel.
  • the parallel computations can be performed by calculating each run of order n in the cells intersected by the line in parallel; or by calculating the positions of groups of runs of order n in the cells intersected by the line in parallel and using the sequential version of the algorithm to draw each group. Another level of parallelism could be attained within each run by setting multiple runs of a lower order or pixels per iteration of the sequential or parallel version of the algorithm.
  • the run of order n could be divided into runs of an order less than n, each of which could be processed in parallel.
  • FIG. 16 gives an overview of how runs may be computed in parallel.
  • initialization 1615 which calculates and sets the first truncated run of cells and then computes the starting cells of each of the full runs of order i being set, and the part 1615 that sets the full runs in parallel. Beginning with start 1603, the first part of the initialization is done as shown in FIG. 6. As set forth in the explanation of FIG. 6, truncated run processor 102 receives as inputs the endpoints of the line; from the endpoints, it calculates the line's slope and determines the starting pixel and the starting point and error term ⁇ for the first run truncated run of order 1.
  • the apparatus of FIG. 2 may be modified to perform the processing of FIG. 16 by replacing bitmap processor [106] with a number of bitmap processors 106(a..j), which can operate on bitmap memory 108 in parallel.
  • Run processor 104 would then give each bitmap processor 106(i) the starting cell and structure parameters for the run that bitmap processor 106(i) is to set.
  • the degree of order n may be determined by the number of bitmap processors 106; for example, if there are four bitmap processors, the degree of order n may be that at which the line contains full runs and a final truncated or untruncated run such that the total number of the full and final runs is divisible by 4.
  • the degree of order n may be determined by the designer or based on external parameters such as the length and slope of the line.
  • the bitmap processors may also be able to set an array of bits in a single operation; in that case, the order whose runs best fit the array that the bitmap processor can set might be the one for which the operation is parallelized.
  • ⁇ and v are the structural parameters described in the parent of the present application.
  • j in the image given the line segment (x 0 , ⁇ 0 ) to (x, , , ) such that 0 J ⁇ ⁇ 1 where e R and x 0 ⁇ x, :
  • V [ 2 ] r [2] _, ] else
  • Algorithm 1 illustrates a possible implementation of an order 1 algorithm.
  • Algorithm 1 Calculating the length and position ofthej-th run of order 1 in the digital line.
  • Constants pertaining to the /-th run of order 1 1.
  • the constants c, and cy can be calculated once in the initialization of the algorithm.
  • the constants cy and c can be calculated iteratively as each new parallel task is created from preexisting constants. Therefore each run can be set in parallel for a cost of approximately 6 additions, a multiplication and a comparison compared to a cost of 3 additions and two comparisons for the central loop of the sequential algorithm. Hence, the overhead imposed by the parallelization ofthe algorithm is quickly recouped.
  • migrating to a parallel implementation would add two divisions and a multiplication to the cost of initializing the algorithm and 10 additions, a multiplication and division and a comparison to the cost of calculating the length and position of each run of order 2.
  • Algorithm 2 Calculating the length and position of the j-th run of order 2 in the digital line. Constants pertaining to the line: ⁇ ['>1 a"
  • . else The length of the j-t run of order 2 is short, rj 2 ' Th e height of the full runs of order 2, shape 0: l + s : else
  • _r [2] J. else The length of the j-th run of order 2 is long, 2]
  • Algorithm 3 Calculating the length and position of they-th run of order i in the digital line. Constants pertaining to the line:
  • a line is given a width (for example, one pixel) and when a pixel has a portion within the line, the pixel is given the line's color with an intensity that is a function of the amount of the pixel that is within the line.
  • a common technique for determining the intensity of anti-aliasing pixels for applications such as line drawing is to employ a filter such as the box filter, which can be easily incorporated into a pixel-based line drawing algorithm and implemented in hardware.
  • the box filter based on area sampling, determines the fraction of a pixel covered by the line but has far from optimal frequency response.
  • the frequency response can be improved by convolving the box filter with a triangle or cone filter.
  • Gupta and Sproull pre-computed the values of a cone filter of radius one and stored them in a table indexed by the perpendicular distance from a pixel center to the center of the ideal line. See S. Gupta and R. Sproull. Filtering edges for grayscale displays. Computer Graphics (SIGGRAPH '81 proceedings), 15(3), August 1981, pp. 1-5. For each major axis step in the set of cells representing the line, Gupta and Sproull intensified 3 pixels, as shown in FIG. 17. At 1703 is shown the line; the three pixels are shown at 1705,
  • pixel 1705 Since pixel 1705 is barely intercepted by the line, it will have the lowest intensity; pixel 1707 has the largest portion of its area in the line, so it will have the highest intensity, while the intensity of 1709 will lie between those extremes.
  • Gupta and Sproull found that only for extreme cases would more than three pixels be needed to anti-alias a line of unit thickness. The extension to lines of non-unit width, however, can be made.
  • FIG. 21 The structural information acquired in the course of drawing lines using runs of pixels can be used to accelerate anti-aliasing. This is done by defining and precomputing a number of run masks describing the anti-aliased pixel intensities for the one or two run lengths used in drawing the line. Once the run masks are defined, the line can be drawn using the run masks in place of their corresponding run lengths. As with the run lengths, which run mask to use at a given point in the line can be determined from the structural information and run masks may be set in parallel. The intensities of the pixels in the run masks can be determined using any pre-filtering technique.
  • Run masks offer a significant reduction in the cost of drawing the line and the results obtained are little different from those obtained by doing anti-aliasing a pixel at a time. Given the length of the lines we will consider and the fact that in most applications the hierarchical runs must be broken down into pixels or runs of pixels when the runs are set, we will concentrate our discussion on run masks consisting of runs of pixels. However extending these ideas to higher order runs is straightforward.
  • one or more higher-order run masks must be defined for each higher-order run length.
  • the higher-order run mask could be defined as a bitmap or a recursive description of lower-order run masks.
  • the run masks can have various shapes and the pixels in them can have varying intensities.
  • FIG. 18 shows three examples. As shown at 1801, the exemplary run masks are to be applied to a line of unit width 1803.
  • the order 1 runs for the line include one of 3 pixels (1805) and another of two pixels (1807).
  • the exemplary run masks include the Height-3 (H3) mask shown at 1809, the couplet Height-2 mask (H2) shown at 181 1 , and the Height- 1 mask (HI) shown at 1813.
  • H3 Height-3
  • H2 couplet Height-2 mask
  • HI Height- 1 mask
  • H3 mask 1809 is based on the observation of Gupta and Sproull that no more than three pixels per column have to be intensified per major axis step in order to anti-alias a line of unit thickness. As shown at 1809, the H3 mask includes both the run of pixels calculated using the run-based line drawing algorithm and the runs immediately above and below this run, thereby covering the pixels that should be intensified using the three pixel per column idea.
  • HI mask 1813 achieves the same goal as the H3 mask by extending the length of each run.
  • the mask is only one pixel high, but its length is increased to cover the pixels above the previous and below the next run in the line.
  • H2 mask 1811 takes a slightly different approach from the other two. Instead of extending a single run, a H2 mask extends two adjoining runs to cover the major axis step. Therefore at least four basic masks are required not just two.
  • the H2 masks are defined for every pair of run lengths: short-short, short-long, long-short and long-long.
  • the maximum height in pixels provided by a sequence of H2 run mask is two pixels, and the H2 run mask therefore offers less complete coverage of the unit line than the other styles of run mask.
  • FIG. 21 shows examples of a line drawn using the HI and H3 masks and of long and short masks for the line.
  • the values of the pixels for the line drawn using the HI mask is shown at 2101 ; an HI mask for a short run of order 1 is shown at 2103; an HI mask for a long run of order 1 is shown at 2105.
  • the values of the pixels for the same line drawn using the H3 mask are shown at 2107; an H3 mask for a short run of order 1 is shown at 2109; an H3 mask for a long run of order 1 is shown at 21 11.
  • Any pre-filtering algorithm used in anti-aliasing can be adapted to compute the intensities of the pixels in the run masks.
  • Run masks can be constructed for any level of the hierarchy of runs in the digital line, however we will concentrate on run masks defined as runs of pixels. The ideas we describe can be easily extended to higher order runs.
  • structural parameters for a line may be used to determine lengths of runs. These structural parameters a, ⁇ , and v are shown in FIG. 15.
  • To calculate each run mask we will use a pixel -based approach based on a look-up table of pre-filtered pixel intensities.
  • One of the structural parameters, the intercept value ⁇ is used to index the look-up table of pixel intensities when pre-calculating the run mask.
  • the main decision in defining the run mask lies in where to initially place the continuous line relative to the run such that the run mask generated is representative of the pixel intensities that exist in runs of that length in the digital line. This can be achieved by carefully choosing for each mask the initial intercept value, ⁇ 0 .
  • run mask is pre-computed.
  • v is another one of the structural parameters shown in FIG. 15.
  • line segment form a boundary on the run structure of the line that can cause truncation of the first and/or last runs of the line.
  • the separate calculation of additional first and last run masks can be avoided by observing that truncated run masks can be constructed directly from either the short or long run masks.
  • FIG. 22 presents an example of how to use multiple run masks for each run length. As shown at
  • a long run is set if the value of the intercept, ?. , is 0 ⁇ ?. ⁇ v and short if v ⁇ ⁇ ⁇ a . Since there is only one run mask for each short run in the line, whenever the intercept value is v ⁇ ⁇ j ⁇ a , the single short run-mask is used. If the intercept value is 0 ⁇ ⁇ ⁇ v and a long run is to be set, one of the long run masks is used if the intercept value is in the range ⁇ 0 and the other if it is in the range 5, , as shown at 2203..
  • FIG. 19 shows the output of the lines produced by using the HI (1909), H2 (1907), and H3 (1905) run masks.
  • the HI mask performs the most accurately, with just a 3.9% error, followed by the H3 mask with a 4.3% error.
  • the H2 masks have a 6.2% error.
  • Table 1 Comparison of the mean pixel-by-pixel errors of the run-based and the Gupta- Sproull algorithms.
  • the length of a line plays an important role in determining the order of runs to use for a line drawing algorithm.
  • the cost of initializing the run masks and the run-based digitization algorithm dictate that for very short lines, using run masks makes little sense.
  • the cost of initialization however is quickly recouped as the length of the line increases.
  • the differences between the costs of using HI, H2 or H3 run masks are a result of the cost of pre-calculating the run masks. If H2 masks are used, there are four masks in the simplest case instead of two.
  • the HI mask also gains a slight advantage over the H3 mask for lines of small slope.
  • run masks in run-based line drawing algorithms can significantly reduce the costs of producing an anti-aliased line in many applications while giving a visual quality that does not greatly differ from that provided by pixel-based algorithms.
  • the run mask idea can be applied to algorithms based on runs of runs, run length slices, or any other higher order run, either by defining run masks for the higher orders or by setting run masks defined as runs of pixels. The choice of which order to use must, however, be made individually for each application as the costs of initializing each new level of the algorithm dictates that for short lines, lower order algorithms are more efficient.
  • the style of the mask chosen dictates the cost of its computation. Both the HI and H3 mask pre- computation are more efficient than the H2 since only two run masks are computed rather than four. The HI mask is also faster to compute than the H3 mask because some arithmetic operations are avoided as a result of the simpler mask geometry. The HI mask gains an additional advantage in the drawing stage of the algorithm in that it is completely coherent to the layout of the raster memory and thus requires only one memory operation in comparison to the three required by the H3 mask.
  • the hardware provides a memory operation that permits multiple pixels to be written at once
  • techniques closely related to those used with anti-aliasing can be used to write runs which are contained partially or entirely in the sets of multiple pixels that can be simultaneously written.
  • the starting position of the run can be computed from the end of the last run and the structure parameters give the run's length, and thus, the portion of the run that is within the set of multiple pixels can be determined and the multiple pixels set up so that the pixels in the portion of the run that is within the set of multiple pixels can be set as required for the line and the remainder set as required for the line's background, whereupon all of the pixels can be written at once.
  • the same technique can be used to write anti-aliasing masks as well as runs.
  • a line that is written using anti-aliasing masks or by writing sets of multiple pixels can of course be written in parallel in the same fashion as was explained above for writing runs in parallel. Instead of computing the position of each run and writing the runs in parallel, one computes the position of each run mask or each set of multiple pixels and then writes the masks or sets of multiple pixels in parallel.
  • the techniques include using the structural information to determine sets of cells of a lattice, which may be processed in parallel and using the structural information to determine sets of cells that include the run and cells additional thereto.
  • the latter technique includes using the structural information to determine the locations and pixel values of anti-aliasing pixels and using the structural information to determine how multi-pixel chunks of memory are to be read or written.

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Hardware Design (AREA)
  • Image Generation (AREA)

Abstract

L'invention concerne des techniques de dessin au trait qui font intervenir des parcours ou des parcours de pixels pour dessiner au trait les informations de structure hiérarchique de calcul de trait qui leur servent ensuite pour déterminer la séquence de parcours dans le trait. Ces informations de structure hiérarchique peuvent servir à améliorer le dessin au trait. Un des moyens consiste à utiliser les informations de structure hiérarchique pour calculer les positions d'une pluralité de parcours, puis à représenter ces parcours parallèlement. Un autre moyen consiste à utiliser les informations de structure hiérarchique pour déterminer les propriétés des ensembles de cellules qui contiennent non seulement les cellules du parcours en question, mais également d'autres cellules qui sont attribuées par la présence des cellules du parcours. Les cellules du parcours associées aux cellules anticrénelage constituent un des exemples de ce type d'ensemble de cellules. Les informations de structure hiérarchique peuvent servir à déterminer l'emplacement et la taille d'un ensemble de cellules ainsi que les intensités des cellules anticrénelage. Les cellules qui sont transcrites simultanément dans une seule opération de mise en mémoire constituent un autre exemple de ce type d'ensemble de cellules. Ces ensembles de cellules peuvent être dessinées parallèlement de la même façon que les parcours.
PCT/US2002/039716 2001-12-13 2002-12-12 Utilisation d'informations de structure hierarchique pour ameliorer le dessin au trait dans les systemes numeriques Ceased WO2003052733A1 (fr)

Priority Applications (7)

Application Number Priority Date Filing Date Title
EP02790102A EP1466313A4 (fr) 2001-12-13 2002-12-12 Utilisation d'informations de structure hierarchique pour ameliorer le dessin au trait dans les systemes numeriques
US10/498,467 US20050001840A1 (en) 2001-12-13 2002-12-12 Using line struture information to enhance line drawing in digital systems
AU2002353125A AU2002353125A1 (en) 2001-12-13 2002-12-12 Using line structure information to enhance line drawing in digital systems
US10/500,772 US20050116951A1 (en) 2002-01-07 2003-01-06 Using runs of cells to traverse a ray through a volume
PCT/US2003/000240 WO2003058405A2 (fr) 2002-01-07 2003-01-06 Utilisation de series de cellules pour la traversee d'un rayon dans un volume
EP03702002A EP1472654A2 (fr) 2002-01-07 2003-01-06 Utilisation de series de cellules pour la traversee d'un rayon dans un volume
AU2003202890A AU2003202890A1 (en) 2002-01-07 2003-01-06 Using runs of cells to traverse a ray through a volume

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
US60/341,503 2001-12-13
US60/341,194 2001-12-13
PCT/US2002/024711 WO2003012599A2 (fr) 2001-08-03 2002-08-02 Procedes et appareil pour la determination d'intersections d'une ligne particuliere avec des cellules dans un reseau
USPCT/US02/24711 2002-08-02

Publications (1)

Publication Number Publication Date
WO2003052733A1 true WO2003052733A1 (fr) 2003-06-26

Family

ID=21743226

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/US2002/039716 Ceased WO2003052733A1 (fr) 2001-12-13 2002-12-12 Utilisation d'informations de structure hierarchique pour ameliorer le dessin au trait dans les systemes numeriques

Country Status (1)

Country Link
WO (1) WO2003052733A1 (fr)

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4939671A (en) * 1987-09-08 1990-07-03 Auto-Trol Technology Corporation Method and system for line drawing with next matrix feature
US5140315A (en) * 1990-04-16 1992-08-18 Analog Devices, Inc. Antialiased pixel based display system for lines and solids
US5164717A (en) * 1989-09-28 1992-11-17 Sun Microsystems, Inc. Method and apparatus for the dithering of antialiased vectors
US6433790B1 (en) * 1999-01-19 2002-08-13 Intel Corporation Methods and systems for rendering line and point features for display

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4939671A (en) * 1987-09-08 1990-07-03 Auto-Trol Technology Corporation Method and system for line drawing with next matrix feature
US5164717A (en) * 1989-09-28 1992-11-17 Sun Microsystems, Inc. Method and apparatus for the dithering of antialiased vectors
US5140315A (en) * 1990-04-16 1992-08-18 Analog Devices, Inc. Antialiased pixel based display system for lines and solids
US6433790B1 (en) * 1999-01-19 2002-08-13 Intel Corporation Methods and systems for rendering line and point features for display

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See also references of EP1466313A4 *

Similar Documents

Publication Publication Date Title
KR100243174B1 (ko) 서브픽셀 마스크 발생방법 및 장치
Loop et al. Resolution independent curve rendering using programmable graphics hardware
JP5188628B2 (ja) ３ｄオブジェクトの３ｄモデルをレンダリングするための方法及びシステム
Loop et al. Real-time GPU rendering of piecewise algebraic surfaces
US7239319B2 (en) Rendering outline fonts
US7006110B2 (en) Determining a coverage mask for a pixel
KR102278147B1 (ko) 그래픽 프리미티브의 클립핑
US7352369B2 (en) System and method for approximating an editable surface
Nehab et al. Random-access rendering of general vector graphics
US7545387B2 (en) Method and apparatus for sampling on a non-power-of-two pixel grid
Moreton Watertight tessellation using forward differencing
US6850234B2 (en) Method and system for determining visible parts of transparent and nontransparent surfaces of there-dimensional objects
EP0718797B1 (fr) Correction de perspective des textures d'images graphiques par approximation adaptive
JP4311877B2 (ja) 副標本化テクスチャ端縁部のアンチエイリアシング
EP1466313A1 (fr) Utilisation d'informations de structure hierarchique pour ameliorer le dessin au trait dans les systemes numeriques
US20050116951A1 (en) Using runs of cells to traverse a ray through a volume
WO2003052733A1 (fr) Utilisation d'informations de structure hierarchique pour ameliorer le dessin au trait dans les systemes numeriques
US20040189641A1 (en) Method and apparatus for determining intersections of a particular line with cells in a lattice
Manson et al. Analytic rasterization of curves with polynomial filters
Zwicker Continuous reconstruction, rendering, and editing of point-sampled surfaces
US6903740B1 (en) Volumetric-based method and system for visualizing datasets
EP1472654A2 (fr) Utilisation de series de cellules pour la traversee d'un rayon dans un volume
Lehn et al. Rasterisation
Sud et al. Fast distance field computation using graphics hardware
Popescu et al. Forward rasterization

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): AU CA CN JP SG US

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): AT BE BG CH CY CZ DE DK EE ES FI FR GB GR IE IT LU MC NL PT SE SI SK TR

121 Ep: the epo has been informed by wipo that ep was designated in this application
DFPE Request for preliminary examination filed prior to expiration of 19th month from priority date (pct application filed before 20040101)
WWE Wipo information: entry into national phase

Ref document number: 10498467

Country of ref document: US

WWE Wipo information: entry into national phase

Ref document number: 2002790102

Country of ref document: EP

WWP Wipo information: published in national office

Ref document number: 2002790102

Country of ref document: EP

NENP Non-entry into the national phase

Ref country code: JP

WWW Wipo information: withdrawn in national office

Country of ref document: JP

WWW Wipo information: withdrawn in national office

Ref document number: 2002790102

Country of ref document: EP