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 <stdio.h>
00042 
00043 #include "types.h"
00044 #include "objects.h"
00045 #include "spaces.h"
00046 #include "regions.h"
00047 #include "lines.h"
00048  
00049 /*
00050 :h3.Functions Provided to the TYPE1IMAGER User
00051  
00052 None.
00053 */
00054  
00055 /*
00056 :h3.Functions Provided to Other Modules
00057  
00058 This module provides the following entry point to other modules:
00059 */
00060  
00061 /*SHARED LINE(S) ORIGINATED HERE*/
00062  
00063 /*
00064 :h3.Macros Provided to Other Modules
00065  
00066 None.
00067 */
00068  
00069 /*
00070 :h2.StepLine() - Produces Run Ends for a Line After Checks
00071  
00072 The main work is done by Bresenham(); here we just perform checks and
00073 get the line so that its Y direction is always increasing:
00074 */
00075  
00076 void StepLine(R, x1, y1, x2, y2)
00077        register struct region *R;  /* region being built                     */
00078        register fractpel x1,y1;  /* starting point                           */
00079        register fractpel x2,y2;  /* ending point                             */
00080 {
00081        register fractpel dy;
00082  
00083        IfTrace4((LineDebug > 0), ".....StepLine: (%d,%d) to (%d,%d)\n",
00084                                             x1, y1, x2, y2);
00085  
00086        dy = y2 - y1;
00087  
00088 /*
00089 We execute the "GOING_TO" macro to call back the REGIONS module, if
00090 necessary (like if the Y direction of the edge has changed):
00091 */
00092        GOING_TO(R, x1, y1, x2, y2, dy);
00093  
00094        if (dy == 0)
00095                return;
00096  
00097        if (dy < 0)
00098                Bresenham(R->edge, x2, y2, x1, y1);
00099        else
00100                Bresenham(R->edge, x1, y1, x2, y2);
00101        return;
00102 }
00103 /*
00104 :h3.Bresenham() - Actually Produces Run Ends
00105  
00106 This routine runs a Bresenham line-stepping
00107 algorithm.  See, for example, Newman and Sproul, :hp1/Principles
00108 of Interactive Computer Graphics/, pp. 25-27.
00109 When we enter this, we
00110 are guaranteed that dy is positive.
00111 We'd like to work in 8 bit precision, so we'll define some macros and
00112 constants to let us do that:
00113 */
00114  
00115 #define PREC 8               /* we'll keep fraction pels in 8 bit precision  */
00116 /*
00117 RoundFP() rounds down by 'b' bits:
00118 */
00119 #define  RoundFP(xy,b)   (((xy)+(1<<((b)-1)))>>(b))
00120  
00121 /*
00122 TruncFP() truncates down by 'b' bits:
00123 */
00124 #define  TruncFP(xy,b)   ((xy)>>(b))
00125  
00126  
00127 void Bresenham(edgeP,x1,y1,x2,y2)
00128        register pel *edgeP;               /* pointer to top of list (y == 0) */
00129        register fractpel x1,y1;           /* starting point on line          */
00130        register fractpel x2,y2;           /* ending point on the line (down) */
00131 {
00132        register LONG dx,dy;  /* change in x and y, in my own precision       */
00133        register LONG x,y;    /* integer pel starting point                   */
00134        register int count;   /* integer pel delta y                          */
00135        register LONG d;      /* the Bresenham algorithm error term           */
00136  
00137        x1 = TruncFP(x1, FRACTBITS-PREC);
00138        y1 = TruncFP(y1, FRACTBITS-PREC);
00139        x2 = TruncFP(x2, FRACTBITS-PREC);
00140        y2 = TruncFP(y2, FRACTBITS-PREC);
00141  
00142        dx = x2 - x1;
00143        dy = y2 - y1;
00144 /*
00145 Find the starting x and y integer pel coordinates:
00146 */
00147  
00148  x = RoundFP(x1,PREC);
00149  y = RoundFP(y1,PREC);
00150 
00151  edgeP += y;
00152  count = RoundFP(y2,PREC) - y;
00153 /*------------------------------------------------------------------*/
00154 /* Force dx to be positive so that dfy will be negative             */
00155 /*       this means that vertical moves will decrease d             */
00156 /*------------------------------------------------------------------*/
00157  if (dx<0)
00158  {
00159   dx = -dx;
00160 #define P PREC
00161   d=(dy*(x1-(x<<P)+(1<<(P-1)))-dx*((y<<P)-y1+(1<<(P-1))))>>P;
00162 #undef P
00163   while(--count >= 0 )
00164   {
00165    while(d<0)
00166    {
00167     --x;
00168     d += dy;
00169    }
00170    *(edgeP++) = x;
00171    d -= dx;
00172   }
00173  }
00174  else  /* positive dx */
00175  {
00176    
00177    if ( dx == 0 ) {
00178      while(--count >= 0 ) {
00179        *(edgeP++) = x;
00180      }
00181      return;
00182      
00183    }
00184    
00185 #define P PREC
00186   d = (dy*((x<<P)-x1+(1<<(P-1)))-dx*((y<<P)-y1+(1<<(P-1))))>>P;
00187 #undef P
00188   while(--count >= 0 )
00189   {
00190    while(d<0)
00191    {
00192     ++x;
00193     d += dy;
00194    }
00195    *(edgeP++) = x;
00196    d -= dx;
00197   }
00198  }
00199 }