Line Drawing

Article
06/30/2006

The process of drawing one or more lines is broken into three discrete phases: the prepare phase, the drawing phase, and the completion phase.

Step 1: Line drawing prepare phase

Line drawing begins when an application calls Polyline. GDI handles the call to Polyline. GDI validates that there are at least two vertices and that the line style is not NULL. GDI then calls the GPE DrvStrokePath function or, for a wide pen, DrvFillPath. When GDI calls the GPE member function, it passes the following information from the device context: surface object, path object, clip rectangle, the brush, the ROP2 value, and solid or dashed line attributes. These parameters were either set by an application or are realized attributes. GPE uses some of the input parameters to set the members of its GPELineParms structure.

GPE then calls the display driver's GPE::Line function, passing in the GPELineParms and passing the value gpePrepare. The driver examines the properties of the line to be drawn. The driver then chooses whether it should use the GPE EmulatedLine function or handle the line with its own accelerated function.

Before selecting an accelerated function, the driver must determine whether the hardware can handle the line style and ROP. In the sample ATI display driver, available in the %_WINCEROOT%\Public\Common\OAK\Drivers\Display\ATI directory, the driver sets the function pointer to EmulatedLine by default, but chooses hardware acceleration for lines that are in video memory and use ROP 0x0D0D. The following code sample shows how to choose hardware acceleration for lines that are in video memory.

if (phase == gpeSingle || phase == gpePrepare){
  pLineParms->pLine = EmulatedLine;
  if (((ATISurf*)(pLineParms->pDst))->InVideoMemory() && pLineParms->mix == 0x0d0d){
    pLineParms->pLine = (SCODE (GPE::*)(struct GPELineParms*)) AcceleratedSolidLine;
  }
}

Also, in the prepare phase, the driver can optionally perform additional processing, such as initializing the hardware registers with the selected color. After the prepare phase, control returns to the GPE DrvStrokePath function.

Step 2: Line drawing draw phase

After determining the appropriate line-drawing function, the DrvStrokePath function carries out the two nested loops. The following example shows the clipping rectangles a path falls into.

for( each clip rectangle in clip list )
{
    for( each line segment in stroke path )
    {
       calculate line segment clipped to current cliprect
       call pParms->pLine(pParms);
    }
}

The GPE::Line function of the driver does not have to clip the line segments to the clipping rectangle because DrvStrokePath performs this action. In fact, the driver is prevented from clipping because no valid clipping information is available during the prepare phase. There might not be a clipping rectangle or there might be an entire sequence of clipping rectangles for a single prepare call.

EmulatedLine is the GPE default line-drawing function. The following code example shows the algorithm EmulatedLine uses.

long accum = (long)(pParms->dN) + pParms->llGamma;
long axstp = (long)(pParms->dN);
long dgstp = (long)(pParms->dN) - (long)(pParms->dM);
for( remainingPels = pParms->cPels; remainingPels; remainingPels-- )
{
   if( accum < 0)
   {
      accum += axstp;
   }
   else
   {
       increment_in_minor_direction;
       accum += dgstp;
   }
}
increment_in_major_direction;
draw_current_pixel;
}

Use EmulatedLine to handle diagonal lines, which are relatively rare and therefore usually do not need to be accelerated. Similarly, it is quite rare for line styles to be used. EmulatedLine should be used as the default processor for this case as well.

For devices that support hardware line-drawing acceleration, the driver can implement its own accelerated line function to replace the default EmulatedLine implementation. Alternatively, the driver can call an existing emulation function or create a new software emulation function to handle the line drawing. Even if adequate line-drawing acceleration is available, if solid-fill blit acceleration is implemented in the hardware, this should be used to accelerate horizontal and vertical lines, because hardware-accelerated blit operations are almost always faster than hardware accelerated line operations.

The recommended approach for most situations is to emulate all diagonal and styled lines, and to use either line-drawing hardware or fill-blit hardware to accelerate horizontal and vertical lines. Horizontal and vertical lines constitute the majority of lines drawn, so this approach could lead to better results.

For horizontal and vertical lines, dN will be 0 and no account need be taken of the subpixel information in dM and error term llgamma, as shown in the following code example.

if( pLineParms->dN == 0 )
{
     //Line is vertical or horizontal
     //Use fill-BLGT or h/w line to draw a line starting at
     //pLineParms->xStart, pLineParms->yStart
     //in the direction specified by pLineParms->iDir
     //for a total of pLineParms->cPels pixels
}
else   // use software implementation for diagonal lines
{
     return EmulatedLine( pLineParms );
}

For diagonal lines, the values in the dM, dN, and error term llgamma fields of GPELineParms contain subpixel information. This information should be used when initializing hardware line-drawing registers; otherwise, diagonal lines that are clipped will be incorrectly drawn. This effect can be quite noticeable when moving a window over another window that contains a diagonal line.

In the prepare phase, the driver performs a general inspection of the line parameters to determine whether it can accelerate the line. When the acceleration function is called, the driver might need to perform additional validation. This is because when the driver's accelerated function is called, the function is for a specific path segment clipped to a specific clipping region. The driver must ensure that the line segment length will not cause its hardware registers to overflow.

The code sample below shows how to make these additional checks. Because the dM and dN values are originally expressed in one-sixteenths of a pixel, the hardware slope iterations of the device must retain these lengths for whatever line segment is being drawn. Most hardware is designed to draw a diagonal line across the entire screen, but this hardware expects the dM and dN values or equivalents to be expressed in pixels. Because GPE uses subpixel precision, these counters need four more bits. For short lines, this is not a problem. However, for long lines, these values can overflow the registers and cause the hardware to draw incorrect lines.

While diagonal lines are uncommon, long diagonal lines are extremely rare, so the amount of time to render long diagonal lines using the EmulatedLine function is not important. The following code sample shows one method for verifying the line parameters will not overflow the hardware registers.

Int errTerm = (in)pLineParms->dN + 
              (in)pLineParms->llGamma – 
              ( ( command & PLUS_X ) ? 0 " 1 );
   if(
     ( pLineParms->dN > 4090 ||   //Remember dM >= dN
     ( errTerm > 4090 ) ||
     ( errTerm < -4090 ) )
   {
      RetVal = EmulatedLine(pLineParms); //The hardware DDA would
                                         //overflow; use emulation.
   }
   else
   {
     WaitForFIFO(7);     //seven parameters required
     reg_ALT_CURXY = ((pLineParms->xStart + ((IGS2010Surf*)
                      (pLineParms->pDst))->Left()) << 16 |
                      (pLineParms->yStart + ((IGS2010Surf*)
                      (pLineParms->pDst))->Top());
     reg_MAJ_AXIS_PCNT = (pLineParms->cPels-1);
     reg_ALT_STEP = (((pLineParms->dN-pLineParms->dN)/*&0x3FFF*/)<<16) |
                    (pLineParms->dN /*&0x3FFF*/);
     reg_err_Term = errTerm /*&0x3FFF*/;
     reg_CMD = command;
     RetVal = S_OK;
   }

Step 3: Line drawing completion phase

A line drawing sequence ends with a call to the driver's GPE::Line function with the gpeComplete value as the phase parameter. The driver can use the completion phase as an opportunity to reset any hardware registers or take other configuration actions to the display hardware as necessary.

Line Drawing

Step 1: Line drawing prepare phase

Step 2: Line drawing draw phase

Step 3: Line drawing completion phase

See Also

Additional resources