--- /dev/null
+/* $XConsortium: lines.c,v 1.2 91/10/10 11:18:21 rws 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;
+ }
+ }
+}
projects / rdpsrv / blobdiff