tga_line.c revision ca133b17 
1/* $XFree86: $ */
2
3/*
4 * Copyright 1999 by Matthew Grossman, Seattle, USA.
5 *
6 * Permission to use, copy, modify, distribute, and sell this software
7 * and its documentation for any purpose is hereby granted without
8 * fee, provided that the above copyright notice appear in all copies
9 * and that both that copyright notice and this permission notice
10 * appear in supporting documentation, and that the name of Matthew
11 * Grossman not be used in advertising or publicity pertaining to
12 * distribution of the software without specific, written prior
13 * permission.  Matthew Grossman makes no representations about the
14 * suitability of this software for any purpose.  It is provided "as
15 * is" without express or implied warranty.
16 *
17 * MATTHEW GROSSMAN DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
18 * SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
19 * FITNESS, IN NO EVENT SHALL MATTHEW GROSSMAN BE LIABLE FOR ANY
20 * SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
21 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN
22 * AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING
23 * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
24 * SOFTWARE.
25 *
26 * Author:  Matthew Grossman, mattg@oz.net
27 *
28 */
29
30/* tga_line.c */
31/* accelerated solid and dashed lines */
32/* adapted from xaa/xaaLine.c */
33
34#ifdef HAVE_CONFIG_H
35#include "config.h"
36#endif
37
38#include <X11/X.h>
39#include "misc.h"
40#include "xf86.h"
41#include "xf86_OSproc.h"
42
43#include "scrnintstr.h"
44#include "pixmapstr.h"
45#include "miline.h"
46#include "xf86str.h"
47#include "xaa.h"
48#include "xaalocal.h"
49
50/*  #include "tga.h" */
51#include "tga_regs.h"
52
53/* line functions */
54extern void
55TGASetupForSolidLine(ScrnInfoPtr pScrn, int color, int rop,
56		     unsigned int planemask);
57extern void
58TGASubsequentSolidHorVertLine(ScrnInfoPtr pScrn, int x, int y, int len,
59			      int dir);
60extern void
61TGASubsequentSolidLine(ScrnInfoPtr pScrn, int x1, int y1, int x2, int y2,
62		       int octant, int flags);
63extern void
64TGASetupForClippedLine(ScrnInfoPtr pScrn, int x1, int y1, int x2, int y2,
65		       int octant);
66extern void
67TGASubsequentClippedSolidLine(ScrnInfoPtr pScrn, int x1, int y1, int len,
68			      int err);
69
70extern void
71TGASetupForDashedLine(ScrnInfoPtr pScrn, int fg, int bg, int rop,
72		      unsigned int planemask, int length,
73		      unsigned char *pattern);
74extern void
75TGASubsequentDashedLine(ScrnInfoPtr pScrn, int x1, int y1, int x2, int y2,
76			int octant, int flags, int phase);
77extern void
78TGASubsequentClippedDashedLine(ScrnInfoPtr pScrn, int x1, int y1, int len,
79			       int err, int phase);
80
81
82extern void
83TGASync(ScrnInfoPtr pScrn);
84
85void TGAPolySegment(DrawablePtr pDrawable, GCPtr pGC, int nseg,
86		    xSegment *pSeg);
87void TGAPolyLines(DrawablePtr pDrawable, GCPtr pGC, int mode, int npt,
88		  DDXPointPtr pptInit);
89void TGAPolySegmentDashed(DrawablePtr pDrawable, GCPtr pGC, int	nseg,
90			  xSegment *pSeg);
91void TGAPolyLinesDashed(DrawablePtr pDrawable, GCPtr pGC, int mode, int npt,
92			DDXPointPtr pptInit);
93
94
95void
96#ifdef POLYSEGMENT
97TGAPolySegment(
98	       DrawablePtr	pDrawable,
99	       GCPtr	pGC,
100	       int		nseg,
101	       xSegment	*pSeg
102#else
103	       TGAPolyLines(
104			    DrawablePtr pDrawable,
105			    GCPtr	pGC,
106			    int		mode,		/* Origin or Previous */
107			    int		npt,		/* number of points */
108			    DDXPointPtr pptInit
109#endif
110			    ){
111  XAAInfoRecPtr infoRec = GET_XAAINFORECPTR_FROM_GC(pGC);
112  BoxPtr pboxInit = REGION_RECTS(pGC->pCompositeClip);
113  int nboxInit = REGION_NUM_RECTS(pGC->pCompositeClip);
114  unsigned int bias = miGetZeroLineBias(pDrawable->pScreen);
115  int xorg = pDrawable->x;
116  int yorg = pDrawable->y;
117  int nbox;
118  BoxPtr pbox;
119#ifndef POLYSEGMENT
120  DDXPointPtr ppt;
121#endif
122  int x1, x2, y1, y2, tmp, len;
123
124#ifdef POLYSEGMENT
125/*    ErrorF("TGAPolySegment called!\n"); */
126#else
127/*    ErrorF("TGAPolyLines called\n"); */
128#endif
129
130  if(!nboxInit)
131    return;
132  /****************/
133  /* TGA FUNCTION */
134  /****************/
135  TGASetupForSolidLine(infoRec->pScrn, pGC->fgPixel, pGC->alu,
136		       pGC->planemask);
137
138#ifdef POLYSEGMENT
139  while (nseg--)
140#else
141    ppt = pptInit;
142  x2 = ppt->x + xorg;
143  y2 = ppt->y + yorg;
144  while(--npt)
145#endif
146    {
147      nbox = nboxInit;
148      pbox = pboxInit;
149
150#ifdef POLYSEGMENT
151      x1 = pSeg->x1 + xorg;
152      y1 = pSeg->y1 + yorg;
153      x2 = pSeg->x2 + xorg;
154      y2 = pSeg->y2 + yorg;
155      pSeg++;
156#else
157      x1 = x2;
158      y1 = y2;
159      ++ppt;
160      if (mode == CoordModePrevious) {
161	xorg = x1;
162	yorg = y1;
163      }
164      x2 = ppt->x + xorg;
165      y2 = ppt->y + yorg;
166#endif
167
168      if (x1 == x2) { /* vertical line */
169	/* make the line go top to bottom of screen, keeping
170	   endpoint semantics
171	*/
172	if (y1 > y2) {
173	  tmp = y2;
174	  y2 = y1 + 1;
175	  y1 = tmp + 1;
176#ifdef POLYSEGMENT
177	  if (pGC->capStyle != CapNotLast) y1--;
178#endif
179	}
180#ifdef POLYSEGMENT
181	else if (pGC->capStyle != CapNotLast) y2++;
182#endif
183	/* get to first band that might contain part of line */
184	while(nbox && (pbox->y2 <= y1)) {
185	  pbox++;
186	  nbox--;
187	}
188
189	/* stop when lower edge of box is beyond end of line */
190	while(nbox && (y2 >= pbox->y1)) {
191	  if ((x1 >= pbox->x1) && (x1 < pbox->x2)) {
192	    tmp = max(y1, pbox->y1);
193	    len = min(y2, pbox->y2) - tmp;
194	    if (len)
195	      TGASubsequentSolidHorVertLine(infoRec->pScrn, x1, tmp,
196					    len, DEGREES_270);
197	  }
198	  nbox--;
199	  pbox++;
200	}
201#ifndef POLYSEGMENT
202	y2 = ppt->y + yorg;
203#endif
204      } else if (y1 == y2) { /* horizontal line */
205	/* force line from left to right, keeping endpoint semantics */
206	if (x1 > x2) {
207	  tmp = x2;
208	  x2 = x1 + 1;
209	  x1 = tmp + 1;
210#ifdef POLYSEGMENT
211	  if (pGC->capStyle != CapNotLast)  x1--;
212#endif
213	}
214#ifdef POLYSEGMENT
215	else if (pGC->capStyle != CapNotLast) x2++;
216#endif
217
218	/* find the correct band */
219	while(nbox && (pbox->y2 <= y1)) {
220	  pbox++;
221	  nbox--;
222	}
223
224	/* try to draw the line, if we haven't gone beyond it */
225	if (nbox && (pbox->y1 <= y1)) {
226	  int orig_y = pbox->y1;
227	  /* when we leave this band, we're done */
228	  while(nbox && (orig_y == pbox->y1)) {
229	    if (pbox->x2 <= x1) {
230	      /* skip boxes until one might contain start point */
231	      nbox--;
232	      pbox++;
233	      continue;
234	    }
235
236	    /* stop if left of box is beyond right of line */
237	    if (pbox->x1 >= x2) {
238	      nbox = 0;
239	      break;
240	    }
241
242	    tmp = max(x1, pbox->x1);
243	    len = min(x2, pbox->x2) - tmp;
244	    if (len)
245	      TGASubsequentSolidHorVertLine(infoRec->pScrn, tmp,
246					    y1, len, DEGREES_0);
247	    nbox--;
248	    pbox++;
249	  }
250	}
251#ifndef POLYSEGMENT
252	x2 = ppt->x + xorg;
253#endif
254      } else{ /* sloped line */
255	unsigned int oc1, oc2;
256	int dmin, dmaj, e, octant;
257
258
259	if((dmaj = x2 - x1) < 0) {
260	  dmaj = -dmaj;
261	  octant = XDECREASING;
262	} else octant = 0;
263
264	if((dmin = y2 - y1) < 0) {
265	  dmin = -dmin;
266	  octant |= YDECREASING;
267	}
268
269	if(dmin >= dmaj){
270	  tmp = dmin; dmin = dmaj; dmaj = tmp;
271	  octant |= YMAJOR;
272	}
273
274	e = -dmaj - ((bias >> octant) & 1);
275	len = dmaj;
276	dmin *= 2;
277	dmaj *= 2;
278
279
280	while(nbox--) {
281	  oc1 = oc2 = 0;
282	  OUTCODES(oc1, x1, y1, pbox);
283	  OUTCODES(oc2, x2, y2, pbox);
284	  if (!(oc1 | oc2)) {   /* unclipped */
285	    TGASubsequentSolidLine(infoRec->pScrn, x1, y1, x2, y2,
286				   octant,
287#ifdef POLYSEGMENT
288				   (pGC->capStyle != CapNotLast) ? 0 :
289#endif
290				   OMIT_LAST
291				   );
292	    break;
293	  } else if (oc1 & oc2) { /* completely clipped */
294	    pbox++;
295
296	  } else { /* partially clipped */
297	    int new_x1 = x1, new_y1 = y1, new_x2 = x2, new_y2 = y2;
298	    int clip1 = 0, clip2 = 0;
299	    int err, adx, ady;
300
301	    if(octant & YMAJOR) {
302	      ady = dmaj /= 2;
303	      adx = dmin /= 2;
304	    } else {
305	      ady = dmin /= 2;
306	      adx = dmaj /= 2;
307	    }
308
309	    if (miZeroClipLine(pbox->x1, pbox->y1,
310			       pbox->x2 - 1, pbox->y2 - 1,
311			       &new_x1, &new_y1, &new_x2, &new_y2,
312			       adx, ady, &clip1, &clip2,
313			       octant, bias, oc1, oc2) == -1)
314	      {
315		pbox++;
316		continue;
317	      }
318
319	    if (octant & YMAJOR)
320	      len = abs(new_y2 - new_y1);
321	    else
322	      len = abs(new_x2 - new_x1);
323#ifdef POLYSEGMENT
324	    if (clip2 != 0 || pGC->capStyle != CapNotLast)
325	      len++;
326#else
327	    len += (clip2 != 0);
328#endif
329	    if (len) { /* we have a real line */
330	      int abserr, clipdx, clipdy;
331
332	      /* unwind bresenham error term to first point */
333	      if (clip1) {
334		clipdx = abs(new_x1 - x1);
335		clipdy = abs(new_y1 - y1);
336
337		if (octant & YMAJOR)
338		  err = e + clipdy*dmin - clipdx*dmaj;
339		else
340		  err = e + clipdx*dmin - clipdy*dmaj;
341	      } else
342		err = e;
343
344#define range infoRec->SolidBresenhamLineErrorTermBits
345	      abserr = abs(err);
346	      while((abserr & range) ||
347		    (dmaj & range) ||
348		    (dmin & range)) {
349		dmin /= 2;
350		dmaj /= 2;
351		abserr /= 2;
352		err /= 2;
353	      }
354	      TGASetupForClippedLine(infoRec->pScrn, x1, y1, x2,
355				     y2, octant);
356	      TGASubsequentClippedSolidLine(infoRec->pScrn,
357					    new_x1, new_y1, len,
358					    err);
359
360
361	    }
362	    pbox++;
363	  }
364	} /* while (nbox--) */
365      } /* sloped line */
366    } /* while (nline--) */
367
368#ifndef POLYSEGMENT
369  /* paint the last point if the end style isn't CapNotLast.
370       (Assume that a projecting, butt, or round cap that is one
371        pixel wide is the same as the single pixel of the endpoint.)
372    */
373
374  if ((pGC->capStyle != CapNotLast) &&
375      ((ppt->x + xorg != pptInit->x + pDrawable->x) ||
376       (ppt->y + yorg != pptInit->y + pDrawable->y) ||
377       (ppt == pptInit + 1)))
378    {
379      nbox = nboxInit;
380      pbox = pboxInit;
381      while (nbox--)
382	{
383	  if ((x2 >= pbox->x1) && (y2 >= pbox->y1) &&
384	      (x2 <  pbox->x2) && (y2 <  pbox->y2))
385	    {
386	      TGASubsequentSolidHorVertLine(infoRec->pScrn, x2, y2, 1,
387					    DEGREES_0);
388	      break;
389	    }
390	  else
391	    pbox++;
392	}
393    }
394#endif
395
396  TGASync(infoRec->pScrn);
397  return;
398}
399
400#undef range
401
402  void
403#ifdef POLYSEGMENT
404  TGAPolySegmentDashed(
405		       DrawablePtr	pDrawable,
406		       GCPtr	pGC,
407		       int		nseg,
408		       xSegment	*pSeg
409#else
410		       TGAPolyLinesDashed(
411					  DrawablePtr pDrawable,
412					  GCPtr	pGC,
413					  int		mode,		/* Origin or Previous */
414					  int		npt,		/* number of points */
415					  DDXPointPtr pptInit
416#endif
417					  ){
418    XAAInfoRecPtr infoRec = GET_XAAINFORECPTR_FROM_GC(pGC);
419#if TGA_OLDPRIV || 1	/* XXX XXX XXX */
420    XAAGCPtr   pGCPriv = (XAAGCPtr) (pGC)->devPrivates[XAAGetGCIndex()].ptr;
421#else
422    XAAGCPtr   pGCPriv = (XAAGCPtr)dixLookupPrivate(&(pGC)->devPrivates, XAAGetGCKey());
423#endif
424    BoxPtr pboxInit = REGION_RECTS(pGC->pCompositeClip);
425    int nboxInit = REGION_NUM_RECTS(pGC->pCompositeClip);
426    unsigned int bias = miGetZeroLineBias(pDrawable->pScreen);
427    int xorg = pDrawable->x;
428    int yorg = pDrawable->y;
429    int nbox;
430    BoxPtr pbox;
431#ifndef POLYSEGMENT
432    DDXPointPtr ppt;
433#endif
434    unsigned int oc1, oc2;
435    int dmin, dmaj, e, octant;
436    int x1, x2, y1, y2, tmp, len, offset;
437    int PatternLength, PatternOffset;
438
439#ifdef POLYSEGMENT
440/*      ErrorF("TGAPolySegmentDashed called\n"); */
441#else
442/*      ErrorF("TGAPolyLinesDashed called\n"); */
443#endif
444
445    if(!nboxInit)
446      return;
447
448    PatternLength = pGCPriv->DashLength;
449    PatternOffset = pGC->dashOffset % PatternLength;
450
451    TGASetupForDashedLine(infoRec->pScrn, pGC->fgPixel,
452			  (pGC->lineStyle == LineDoubleDash) ? pGC->bgPixel : -1,
453			  pGC->alu, pGC->planemask, PatternLength, pGCPriv->DashPattern);
454
455
456#ifdef POLYSEGMENT
457    while (nseg--)
458#else
459      ppt = pptInit;
460    x2 = ppt->x + xorg;
461    y2 = ppt->y + yorg;
462    while(--npt)
463#endif
464      {
465	nbox = nboxInit;
466	pbox = pboxInit;
467
468#ifdef POLYSEGMENT
469	x1 = pSeg->x1 + xorg;
470	y1 = pSeg->y1 + yorg;
471	x2 = pSeg->x2 + xorg;
472	y2 = pSeg->y2 + yorg;
473	pSeg++;
474#else
475	x1 = x2;
476	y1 = y2;
477	++ppt;
478	if (mode == CoordModePrevious) {
479	  xorg = x1;
480	  yorg = y1;
481	}
482	x2 = ppt->x + xorg;
483	y2 = ppt->y + yorg;
484#endif
485
486
487
488	if((dmaj = x2 - x1) < 0) {
489	  dmaj = -dmaj;
490	  octant = XDECREASING;
491	} else octant = 0;
492
493	if((dmin = y2 - y1) < 0) {
494	  dmin = -dmin;
495	  octant |= YDECREASING;
496	}
497
498	if(dmin >= dmaj){
499	  tmp = dmin; dmin = dmaj; dmaj = tmp;
500	  octant |= YMAJOR;
501	}
502
503	e = -dmaj - ((bias >> octant) & 1);
504	len = dmaj;
505	dmin <<= 1;
506	dmaj <<= 1;
507
508
509	while(nbox--) {
510	  oc1 = oc2 = 0;
511	  OUTCODES(oc1, x1, y1, pbox);
512	  OUTCODES(oc2, x2, y2, pbox);
513	  if (!(oc1 | oc2)) {   /* unclipped */
514	    TGASubsequentDashedLine(infoRec->pScrn, x1, y1, x2, y2,
515				    octant,
516#ifdef POLYSEGMENT
517				    (pGC->capStyle != CapNotLast) ? 0 :
518#endif
519				    OMIT_LAST, PatternOffset);
520	    break;
521	  } else if (oc1 & oc2) { /* completely clipped */
522	    pbox++;
523	  } else { /* partially clipped */
524	    int new_x1 = x1, new_y1 = y1, new_x2 = x2, new_y2 = y2;
525	    int clip1 = 0, clip2 = 0;
526	    int err, adx, ady;
527
528	    if(octant & YMAJOR) {
529	      ady = dmaj >> 1;
530	      adx = dmin >> 1;
531	    } else {
532	      ady = dmin >> 1;
533	      adx = dmaj >> 1;
534	    }
535
536	    if (miZeroClipLine(pbox->x1, pbox->y1,
537			       pbox->x2 - 1, pbox->y2 - 1,
538			       &new_x1, &new_y1, &new_x2, &new_y2,
539			       adx, ady, &clip1, &clip2,
540			       octant, bias, oc1, oc2) == -1)
541	      {
542		pbox++;
543		continue;
544	      }
545
546	    if (octant & YMAJOR)
547	      len = abs(new_y2 - new_y1);
548	    else
549	      len = abs(new_x2 - new_x1);
550#ifdef POLYSEGMENT
551	    if (clip2 != 0 || pGC->capStyle != CapNotLast)
552	      len++;
553#else
554	    len += (clip2 != 0);
555#endif
556	    if (len) {
557	      int abserr, clipdx, clipdy;
558	      /* unwind bresenham error term to first point */
559	      if (clip1) {
560		clipdx = abs(new_x1 - x1);
561		clipdy = abs(new_y1 - y1);
562
563		if (octant & YMAJOR)
564		  err = e + clipdy*dmin - clipdx*dmaj;
565		else
566		  err = e + clipdx*dmin - clipdy*dmaj;
567	      } else
568		err = e;
569
570#define range infoRec->DashedBresenhamLineErrorTermBits
571	      abserr = abs(err);
572	      while((abserr & range) ||
573		    (dmaj & range) ||
574		    (dmin & range)) {
575		dmin >>= 1;
576		dmaj >>= 1;
577		abserr >>= 1;
578		err /= 2;
579	      }
580
581	      if(octant & YMAJOR)
582		offset = abs(new_y1 - y1);
583	      else
584		offset = abs(new_x1 - x1);
585
586	      offset += PatternOffset;
587	      offset %= PatternLength;
588
589	      TGASetupForClippedLine(infoRec->pScrn, x1, x2, y1, y2,
590				     octant);
591	      TGASubsequentClippedDashedLine(infoRec->pScrn, new_x1,
592					     new_y1, len, err,
593					     PatternOffset);
594	    }
595	    pbox++;
596	  }
597	} /* while (nbox--) */
598#ifndef POLYSEGMENT
599	len = abs(y2 - y1);
600	tmp = abs(x2 - x1);
601	PatternOffset += (len > tmp) ? len : tmp;
602	PatternOffset %= PatternLength;
603#endif
604      } /* while (nline--) */
605
606#ifndef POLYSEGMENT
607    /* paint the last point if the end style isn't CapNotLast.
608       (Assume that a projecting, butt, or round cap that is one
609        pixel wide is the same as the single pixel of the endpoint.)
610    */
611
612    if ((pGC->capStyle != CapNotLast) &&
613	((ppt->x + xorg != pptInit->x + pDrawable->x) ||
614	 (ppt->y + yorg != pptInit->y + pDrawable->y) ||
615	 (ppt == pptInit + 1)))
616      {
617	nbox = nboxInit;
618	pbox = pboxInit;
619	while (nbox--) {
620	  if ((x2 >= pbox->x1) && (y2 >= pbox->y1) &&
621	      (x2 <  pbox->x2) && (y2 <  pbox->y2))
622	    {
623	      TGASubsequentDashedLine(infoRec->pScrn, x2, y2, x2, y2, 0, 0,
624				      PatternOffset);
625	      break;
626	    } else
627		pbox++;
628	}
629    }
630#endif
631
632    TGASync(infoRec->pScrn);
633    return;
634}
635
636
637