/* $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.4tsi 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:
*/
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
#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.
*/
/*
: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))
static void
Bresenham(pel *edgeP, fractpel x1, fractpel y1, fractpel x2, fractpel y2)
{
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;
}
}
}
/*
: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;
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;
}
|