git.sesse.net Git - rdpsrv/blob - Xserver/lib/font/Type1/lines.c

   1 /* $XConsortium: lines.c,v 1.2 91/10/10 11:18:21 rws Exp $ */
   2 /* Copyright International Business Machines, Corp. 1991
   3  * All Rights Reserved
   4  * Copyright Lexmark International, Inc. 1991
   5  * All Rights Reserved
   6  *
   7  * License to use, copy, modify, and distribute this software and its
   8  * documentation for any purpose and without fee is hereby granted,
   9  * provided that the above copyright notice appear in all copies and that
  10  * both that copyright notice and this permission notice appear in
  11  * supporting documentation, and that the name of IBM or Lexmark not be
  12  * used in advertising or publicity pertaining to distribution of the
  13  * software without specific, written prior permission.
  14  *
  15  * IBM AND LEXMARK PROVIDE THIS SOFTWARE "AS IS", WITHOUT ANY WARRANTIES OF
  16  * ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO ANY
  17  * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
  18  * AND NONINFRINGEMENT OF THIRD PARTY RIGHTS.  THE ENTIRE RISK AS TO THE
  19  * QUALITY AND PERFORMANCE OF THE SOFTWARE, INCLUDING ANY DUTY TO SUPPORT
  20  * OR MAINTAIN, BELONGS TO THE LICENSEE.  SHOULD ANY PORTION OF THE
  21  * SOFTWARE PROVE DEFECTIVE, THE LICENSEE (NOT IBM OR LEXMARK) ASSUMES THE
  22  * ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION.  IN NO EVENT SHALL
  23  * IBM OR LEXMARK BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  24  * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  25  * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
  26  * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
  27  * THIS SOFTWARE.
  28  */
  29  /* LINES    CWEB         V0003 ********                             */
  30 /*
  31 :h1.LINES Module - Rasterizing Lines
  32
  33 &author. Duaine W. Pryor, Jr. and Jeffrey B. Lotspiech (lotspiech@almaden.ibm.com)
  34
  35
  36 :h3.Include Files
  37
  38 The included files are:
  39 */
  40
  41 #include "objects.h"
  42 #include "spaces.h"
  43 #include "regions.h"
  44 #include "lines.h"
  45
  46 /*
  47 :h3.Functions Provided to the TYPE1IMAGER User
  48
  49 None.
  50 */
  51
  52 /*
  53 :h3.Functions Provided to Other Modules
  54
  55 This module provides the following entry point to other modules:
  56 */
  57
  58 /*SHARED LINE(S) ORIGINATED HERE*/
  59
  60 /*
  61 :h3.Macros Provided to Other Modules
  62
  63 None.
  64 */
  65
  66 /*
  67 :h2.StepLine() - Produces Run Ends for a Line After Checks
  68
  69 The main work is done by Bresenham(); here we just perform checks and
  70 get the line so that its Y direction is always increasing:
  71 */
  72
  73 void StepLine(R, x1, y1, x2, y2)
  74        register struct region *R;  /* region being built                     */
  75        register fractpel x1,y1;  /* starting point                           */
  76        register fractpel x2,y2;  /* ending point                             */
  77 {
  78        register fractpel dy;
  79
  80        IfTrace4((LineDebug > 0), ".....StepLine: (%p,%p) to (%p,%p)\n",
  81                                             x1, y1, x2, y2);
  82
  83        dy = y2 - y1;
  84
  85 /*
  86 We execute the "GOING_TO" macro to call back the REGIONS module, if
  87 necessary (like if the Y direction of the edge has changed):
  88 */
  89        GOING_TO(R, x1, y1, x2, y2, dy);
  90
  91        if (dy == 0)
  92                return;
  93
  94        if (dy < 0)
  95                Bresenham(R->edge, x2, y2, x1, y1);
  96        else
  97                Bresenham(R->edge, x1, y1, x2, y2);
  98        return;
  99 }
 100 /*
 101 :h3.Bresenham() - Actually Produces Run Ends
 102
 103 This routine runs a Bresenham line-stepping
 104 algorithm.  See, for example, Newman and Sproul, :hp1/Principles
 105 of Interactive Computer Graphics/, pp. 25-27.
 106 When we enter this, we
 107 are guaranteed that dy is positive.
 108 We'd like to work in 8 bit precision, so we'll define some macros and
 109 constants to let us do that:
 110 */
 111
 112 #define PREC 8               /* we'll keep fraction pels in 8 bit precision  */
 113 /*
 114 RoundFP() rounds down by 'b' bits:
 115 */
 116 #define  RoundFP(xy,b)   (((xy)+(1<<((b)-1)))>>(b))
 117
 118 /*
 119 TruncFP() truncates down by 'b' bits:
 120 */
 121 #define  TruncFP(xy,b)   ((xy)>>(b))
 122
 123
 124 void Bresenham(edgeP,x1,y1,x2,y2)
 125        register pel *edgeP;               /* pointer to top of list (y == 0) */
 126        register fractpel x1,y1;           /* starting point on line          */
 127        register fractpel x2,y2;           /* ending point on the line (down) */
 128 {
 129        register long dx,dy;  /* change in x and y, in my own precision       */
 130        register long x,y;    /* integer pel starting point                   */
 131        register int count;   /* integer pel delta y                          */
 132        register long d;      /* the Bresenham algorithm error term           */
 133
 134        x1 = TruncFP(x1, FRACTBITS-PREC);
 135        y1 = TruncFP(y1, FRACTBITS-PREC);
 136        x2 = TruncFP(x2, FRACTBITS-PREC);
 137        y2 = TruncFP(y2, FRACTBITS-PREC);
 138
 139        dx = x2 - x1;
 140        dy = y2 - y1;
 141 /*
 142 Find the starting x and y integer pel coordinates:
 143 */
 144
 145  x = RoundFP(x1,PREC);
 146  y = RoundFP(y1,PREC);
 147  edgeP += y;
 148  count = RoundFP(y2,PREC) - y;
 149 /*------------------------------------------------------------------*/
 150 /* Force dx to be positive so that dfy will be negative             */
 151 /*       this means that vertical moves will decrease d             */
 152 /*------------------------------------------------------------------*/
 153  if (dx<0)
 154  {
 155   dx = -dx;
 156 #define P PREC
 157   d=(dy*(x1-(x<<P)+(1<<(P-1)))-dx*((y<<P)-y1+(1<<(P-1))))>>P;
 158 #undef P
 159   while(--count >= 0 )
 160   {
 161    while(d<0)
 162    {
 163     --x;
 164     d += dy;
 165    }
 166    *(edgeP++) = x;
 167    d -= dx;
 168   }
 169  }
 170  else  /* positive dx */
 171  {
 172 #define P PREC
 173   d = (dy*((x<<P)-x1+(1<<(P-1)))-dx*((y<<P)-y1+(1<<(P-1))))>>P;
 174 #undef P
 175   while(--count >= 0 )
 176   {
 177    while(d<0)
 178    {
 179     ++x;
 180     d += dy;
 181    }
 182    *(edgeP++) = x;
 183    d -= dx;
 184   }
 185  }
 186 }