diff options
Diffstat (limited to 'src/Type1/lines.c')
| -rw-r--r-- | src/Type1/lines.c | 186 |
1 files changed, 186 insertions, 0 deletions
diff --git a/src/Type1/lines.c b/src/Type1/lines.c new file mode 100644 index 0000000..3afcfc1 --- /dev/null +++ b/src/Type1/lines.c @@ -0,0 +1,186 @@ +/* $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. + */ + /* 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 "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; + } + } +} |