Back to index

tetex-bin  3.0
lines.c
Go to the documentation of this file.
00001 /* $XConsortium: lines.c,v 1.2 91/10/10 11:18:21 rws Exp $ */
00002 /* Copyright International Business Machines, Corp. 1991
00003  * All Rights Reserved
00004  * Copyright Lexmark International, Inc. 1991
00005  * All Rights Reserved
00006  *
00007  * License to use, copy, modify, and distribute this software and its
00008  * documentation for any purpose and without fee is hereby granted,
00009  * provided that the above copyright notice appear in all copies and that
00010  * both that copyright notice and this permission notice appear in
00011  * supporting documentation, and that the name of IBM or Lexmark not be
00012  * used in advertising or publicity pertaining to distribution of the
00013  * software without specific, written prior permission.
00014  *
00015  * IBM AND LEXMARK PROVIDE THIS SOFTWARE "AS IS", WITHOUT ANY WARRANTIES OF
00016  * ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO ANY
00017  * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
00018  * AND NONINFRINGEMENT OF THIRD PARTY RIGHTS.  THE ENTIRE RISK AS TO THE
00019  * QUALITY AND PERFORMANCE OF THE SOFTWARE, INCLUDING ANY DUTY TO SUPPORT
00020  * OR MAINTAIN, BELONGS TO THE LICENSEE.  SHOULD ANY PORTION OF THE
00021  * SOFTWARE PROVE DEFECTIVE, THE LICENSEE (NOT IBM OR LEXMARK) ASSUMES THE
00022  * ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION.  IN NO EVENT SHALL
00023  * IBM OR LEXMARK BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
00024  * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
00025  * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
00026  * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
00027  * THIS SOFTWARE.
00028  */
00029  /* LINES    CWEB         V0003 ********                             */
00030 /*
00031 :h1.LINES Module - Rasterizing Lines
00032  
00033 &author. Duaine W. Pryor, Jr. and Jeffrey B. Lotspiech (lotspiech@almaden.ibm.com)
00034  
00035  
00036 :h3.Include Files
00037  
00038 The included files are:
00039 */
00040  
00041 #include "types.h"
00042 #include "objects.h"
00043 #include "spaces.h"
00044 #include "regions.h"
00045 #include "lines.h"
00046  
00047 /*
00048 :h3.Functions Provided to the TYPE1IMAGER User
00049  
00050 None.
00051 */
00052  
00053 /*
00054 :h3.Functions Provided to Other Modules
00055  
00056 This module provides the following entry point to other modules:
00057 */
00058  
00059 /*SHARED LINE(S) ORIGINATED HERE*/
00060  
00061 /*
00062 :h3.Macros Provided to Other Modules
00063  
00064 None.
00065 */
00066  
00067 /*
00068 :h2.StepLine() - Produces Run Ends for a Line After Checks
00069  
00070 The main work is done by Bresenham(); here we just perform checks and
00071 get the line so that its Y direction is always increasing:
00072 */
00073  
00074 void StepLine(R, x1, y1, x2, y2)
00075        register struct region *R;  /* region being built                     */
00076        register fractpel x1,y1;  /* starting point                           */
00077        register fractpel x2,y2;  /* ending point                             */
00078 {
00079        register fractpel dy;
00080  
00081        IfTrace4((LineDebug > 0), ".....StepLine: (%dl,%dl) to (%dl,%dl)\n",
00082                                             x1, y1, x2, y2);
00083  
00084        dy = y2 - y1;
00085  
00086 /*
00087 We execute the "GOING_TO" macro to call back the REGIONS module, if
00088 necessary (like if the Y direction of the edge has changed):
00089 */
00090        GOING_TO(R, x1, y1, x2, y2, dy);
00091  
00092        if (dy == 0)
00093                return;
00094  
00095        if (dy < 0)
00096                Bresenham(R->edge, x2, y2, x1, y1);
00097        else
00098                Bresenham(R->edge, x1, y1, x2, y2);
00099        return;
00100 }
00101 /*
00102 :h3.Bresenham() - Actually Produces Run Ends
00103  
00104 This routine runs a Bresenham line-stepping
00105 algorithm.  See, for example, Newman and Sproul, :hp1/Principles
00106 of Interactive Computer Graphics/, pp. 25-27.
00107 When we enter this, we
00108 are guaranteed that dy is positive.
00109 We'd like to work in 8 bit precision, so we'll define some macros and
00110 constants to let us do that:
00111 */
00112  
00113 #define PREC 8               /* we'll keep fraction pels in 8 bit precision  */
00114 /*
00115 RoundFP() rounds down by 'b' bits:
00116 */
00117 #define  RoundFP(xy,b)   (((xy)+(1<<((b)-1)))>>(b))
00118  
00119 /*
00120 TruncFP() truncates down by 'b' bits:
00121 */
00122 #define  TruncFP(xy,b)   ((xy)>>(b))
00123  
00124  
00125 void Bresenham(edgeP,x1,y1,x2,y2)
00126        register pel *edgeP;               /* pointer to top of list (y == 0) */
00127        register fractpel x1,y1;           /* starting point on line          */
00128        register fractpel x2,y2;           /* ending point on the line (down) */
00129 {
00130        register LONG dx,dy;  /* change in x and y, in my own precision       */
00131        register LONG x,y;    /* integer pel starting point                   */
00132        register int count;   /* integer pel delta y                          */
00133        register LONG d;      /* the Bresenham algorithm error term           */
00134  
00135        x1 = TruncFP(x1, FRACTBITS-PREC);
00136        y1 = TruncFP(y1, FRACTBITS-PREC);
00137        x2 = TruncFP(x2, FRACTBITS-PREC);
00138        y2 = TruncFP(y2, FRACTBITS-PREC);
00139  
00140        dx = x2 - x1;
00141        dy = y2 - y1;
00142 /*
00143 Find the starting x and y integer pel coordinates:
00144 */
00145  
00146  x = RoundFP(x1,PREC);
00147  y = RoundFP(y1,PREC);
00148  edgeP += y;
00149  count = RoundFP(y2,PREC) - y;
00150 /*------------------------------------------------------------------*/
00151 /* Force dx to be positive so that dfy will be negative             */
00152 /*       this means that vertical moves will decrease d             */
00153 /*------------------------------------------------------------------*/
00154  if (dx<0)
00155  {
00156   dx = -dx;
00157 #define P PREC
00158   d=(dy*(x1-(x<<P)+(1<<(P-1)))-dx*((y<<P)-y1+(1<<(P-1))))>>P;
00159 #undef P
00160   while(--count >= 0 )
00161   {
00162    while(d<0)
00163    {
00164     --x;
00165     d += dy;
00166    }
00167    *(edgeP++) = x;
00168    d -= dx;
00169   }
00170  }
00171  else  /* positive dx */
00172  {
00173 #define P PREC
00174   d = (dy*((x<<P)-x1+(1<<(P-1)))-dx*((y<<P)-y1+(1<<(P-1))))>>P;
00175 #undef P
00176   while(--count >= 0 )
00177   {
00178    while(d<0)
00179    {
00180     ++x;
00181     d += dy;
00182    }
00183    *(edgeP++) = x;
00184    d -= dx;
00185   }
00186  }
00187 }