/* $Xorg: lines.c,v 1.3 2000/08/17 19:46:30 cpqbld Exp $ */
/* Copyright International Business Machines, Corp. 1991
 * All Rights Reserved
 * Copyright Lexmark International, Inc. 1991
 * All Rights Reserved
 *
 * License to use, copy, modify, and distribute this software and its
 * documentation for any purpose and without fee is hereby granted,
 * provided that the above copyright notice appear in all copies and that
 * both that copyright notice and this permission notice appear in
 * supporting documentation, and that the name of IBM or Lexmark not be
 * used in advertising or publicity pertaining to distribution of the
 * software without specific, written prior permission.
 *
 * IBM AND LEXMARK PROVIDE THIS SOFTWARE "AS IS", WITHOUT ANY WARRANTIES OF
 * ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO ANY
 * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
 * AND NONINFRINGEMENT OF THIRD PARTY RIGHTS.  THE ENTIRE RISK AS TO THE
 * QUALITY AND PERFORMANCE OF THE SOFTWARE, INCLUDING ANY DUTY TO SUPPORT
 * OR MAINTAIN, BELONGS TO THE LICENSEE.  SHOULD ANY PORTION OF THE
 * SOFTWARE PROVE DEFECTIVE, THE LICENSEE (NOT IBM OR LEXMARK) ASSUMES THE
 * ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION.  IN NO EVENT SHALL
 * IBM OR LEXMARK BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
 * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
 * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
 * THIS SOFTWARE.
 */
/* $XFree86: xc/lib/font/Type1/lines.c,v 1.4 2001/01/17 19:43:22 dawes Exp $ */

 /* LINES    CWEB         V0003 ********                             */
/*
:h1.LINES Module - Rasterizing Lines
 
&author. Duaine W. Pryor, Jr. and Jeffrey B. Lotspiech (lotspiech@almaden.ibm.com)
 
 
:h3.Include Files
 
The included files are:
*/
 
#include "objects.h"
#include "spaces.h"
#include "paths.h"
#include "regions.h"
#include "lines.h"
 
/*
:h3.Functions Provided to the TYPE1IMAGER User
 
None.
*/
 
/*
:h3.Functions Provided to Other Modules
 
This module provides the following entry point to other modules:
*/
 
/*SHARED LINE(S) ORIGINATED HERE*/
 
/*
:h3.Macros Provided to Other Modules
 
None.
*/
 
/*
:h2.StepLine() - Produces Run Ends for a Line After Checks
 
The main work is done by Bresenham(); here we just perform checks and
get the line so that its Y direction is always increasing:
*/
 
void StepLine(R, x1, y1, x2, y2)
       register struct region *R;  /* region being built                     */
       register fractpel x1,y1;  /* starting point                           */
       register fractpel x2,y2;  /* ending point                             */
{
       register fractpel dy;
 
       IfTrace4((LineDebug > 0), ".....StepLine: (%p,%p) to (%p,%p)\n",
                                            x1, y1, x2, y2);
 
       dy = y2 - y1;
 
/*
We execute the "GOING_TO" macro to call back the REGIONS module, if
necessary (like if the Y direction of the edge has changed):
*/
       GOING_TO(R, x1, y1, x2, y2, dy);
 
       if (dy == 0)
               return;
 
       if (dy < 0)
               Bresenham(R->edge, x2, y2, x1, y1);
       else
               Bresenham(R->edge, x1, y1, x2, y2);
       return;
}
/*
:h3.Bresenham() - Actually Produces Run Ends
 
This routine runs a Bresenham line-stepping
algorithm.  See, for example, Newman and Sproul, :hp1/Principles
of Interactive Computer Graphics/, pp. 25-27.
When we enter this, we
are guaranteed that dy is positive.
We'd like to work in 8 bit precision, so we'll define some macros and
constants to let us do that:
*/
 
#define PREC 8               /* we'll keep fraction pels in 8 bit precision  */
/*
RoundFP() rounds down by 'b' bits:
*/
#define  RoundFP(xy,b)   (((xy)+(1<<((b)-1)))>>(b))
 
/*
TruncFP() truncates down by 'b' bits:
*/
#define  TruncFP(xy,b)   ((xy)>>(b))
 
 
void Bresenham(edgeP,x1,y1,x2,y2)
       register pel *edgeP;               /* pointer to top of list (y == 0) */
       register fractpel x1,y1;           /* starting point on line          */
       register fractpel x2,y2;           /* ending point on the line (down) */
{
       register long dx,dy;  /* change in x and y, in my own precision       */
       register long x,y;    /* integer pel starting point                   */
       register int count;   /* integer pel delta y                          */
       register long d;      /* the Bresenham algorithm error term           */
 
       x1 = TruncFP(x1, FRACTBITS-PREC);
       y1 = TruncFP(y1, FRACTBITS-PREC);
       x2 = TruncFP(x2, FRACTBITS-PREC);
       y2 = TruncFP(y2, FRACTBITS-PREC);
 
       dx = x2 - x1;
       dy = y2 - y1;
/*
Find the starting x and y integer pel coordinates:
*/
 
 x = RoundFP(x1,PREC);
 y = RoundFP(y1,PREC);
 edgeP += y;
 count = RoundFP(y2,PREC) - y;
/*------------------------------------------------------------------*/
/* Force dx to be positive so that dfy will be negative             */
/*       this means that vertical moves will decrease d             */
/*------------------------------------------------------------------*/
 if (dx<0)
 {
  dx = -dx;
#define P PREC
  d=(dy*(x1-(x<<P)+(1<<(P-1)))-dx*((y<<P)-y1+(1<<(P-1))))>>P;
#undef P
  while(--count >= 0 )
  {
   while(d<0)
   {
    --x;
    d += dy;
   }
   *(edgeP++) = x;
   d -= dx;
  }
 }
 else  /* positive dx */
 {
#define P PREC
  d = (dy*((x<<P)-x1+(1<<(P-1)))-dx*((y<<P)-y1+(1<<(P-1))))>>P;
#undef P
  while(--count >= 0 )
  {
   while(d<0)
   {
    ++x;
    d += dy;
   }
   *(edgeP++) = x;
   d -= dx;
  }
 }
}