1 /**
2 ** drwcpoly.c ---- draw the outline of a custom (wide and/or dashed) polygon
3 **
4 ** Copyright (c) 1995 Csaba Biegl, 820 Stirrup Dr, Nashville, TN 37221
5 ** [e-mail: csaba@vuse.vanderbilt.edu]
6 **
7 ** This file is part of the GRX graphics library.
8 **
9 ** The GRX graphics library is free software; you can redistribute it
10 ** and/or modify it under some conditions; see the "copying.grx" file
11 ** for details.
12 **
13 ** This library is distributed in the hope that it will be useful,
14 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
15 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16 **
17 **/
18
19 #include "libgrx.h"
20 #include "shapes.h"
21 #include "clipping.h"
22 #include "arith.h"
23 #include "memcopy.h"
24
25 /*
26 * update the end point of line #1 and the starting point of line #2
27 * so that they intersect
28 */
intersect(int l1s[2],int l1e[2],int l2s[2],int l2e[2])29 static void intersect(int l1s[2],int l1e[2],int l2s[2],int l2e[2])
30 {
31 # define x11 l1s[0]
32 # define y11 l1s[1]
33 # define x12 l1e[0]
34 # define y12 l1e[1]
35 # define x21 l2s[0]
36 # define y21 l2s[1]
37 # define x22 l2e[0]
38 # define y22 l2e[1]
39 if(x12 != x21 || y12 != y21) {
40 int dx1 = x12 - x11;
41 int dy1 = y12 - y11;
42 int dx2 = x22 - x21;
43 int dy2 = y22 - y21;
44 long det = imul32(dx2,dy1) - imul32(dx1,dy2);
45 if( det != 0 ) {
46 /* Compute t for the parametric equation of line #2 */
47 /* then: x = x21 + dx2 * t2, and y = y21 + dy2 * t2 */
48 /* but do this with integer arithmetic */
49 /* and do rounding instead of truncation */
50 long det_t2 = imul32(dx1,(y21 - y11)) - imul32(dy1,(x21 - x11));
51 long ldet = labs(det);
52 /* make sure we're still near old start point of line #2 */
53 if( labs(det_t2) < (((ldet<<1) + ldet)>>1) ) {
54 int xdif2 = (int)(((long)(dx2 << 1) * det_t2) / det);
55 int ydif2 = (int)(((long)(dy2 << 1) * det_t2) / det);
56 if(xdif2 > 0) xdif2++;
57 if(ydif2 > 0) ydif2++;
58 xdif2 = x21 + (xdif2 >> 1);
59 ydif2 = y21 + (ydif2 >> 1);
60 /* don't create triangles */
61 if ( xdif2 != x11 && xdif2 != x22 &&
62 ydif2 != y11 && ydif2 != y22 ) {
63 l1e[0] = l2s[0] = xdif2;
64 l1e[1] = l2s[1] = ydif2;
65 return;
66 }
67 }
68 }
69 { /*
70 ** no good intersection point till now
71 ** Check mean point and its eight neighbours for
72 ** best compromise intersection point
73 **
74 ** y-y11 y12-y11 y-y21 y22-y21
75 ** ----- - ------- = 0 and ----- - ------- = 0
76 ** x-x11 x12-x11 x-x21 x22-x21
77 **
78 ** should hold for intersection point (x,y)
79 ** Measuring the errors for both lines:
80 **
81 ** e1 = (x12-x11)(y-y11)-(x-x11)(y12-y11) = dx1(y-y11)-(x-x11)dy1
82 ** e2 = (x22-x21)(y-y21)-(x-x21)(y22-y21) = dx2(y-y21)-(x-x21)dy2
83 **
84 ** search minimal err = |e1| + |e2|
85 */
86 static int xr[9] = { 0, -1, 0, 1, 0, -1, 1, 1, -1};
87 static int yr[9] = { 0, 0, 1, 0, -1, 1, 1, -1, -1};
88 int xc = (x12+x21) >> 1;
89 int yc = (y12+y21) >> 1;
90 int xb = 0, yb = 0;
91 int i;
92 long minerr=0, err;
93 for (i = 0; i < 9; ++i) {
94 int x = xc+xr[i];
95 int y = yc+yr[i];
96 long e1 = imul32(dx1,(y-y11)) - imul32(dy1,(x-x11));
97 long e2 = imul32(dx2,(y-y21)) - imul32(dy2,(x-x21));
98 err = labs(e1) + labs(e2);
99 if ( i==0 || err < minerr) {
100 minerr = err;
101 xb = xr[i]; yb = yr[i];
102 if (minerr == 0) break;
103 }
104 }
105 l1e[0] = l2s[0] = xc + xb;
106 l1e[1] = l2s[1] = yc + yb;
107 }
108 }
109 # undef x11
110 # undef y11
111 # undef x12
112 # undef y12
113 # undef x21
114 # undef y21
115 # undef x22
116 # undef y22
117 }
118
119 /*
120 * generate the four corner points of a wide line segment
121 *
122 * p1 end : rect[0] rect[1]
123 * p2 end : rect[2] rect[3]
124 *
125 */
genrect(int p1[2],int p2[2],int w,int rect[4][2])126 static void genrect(int p1[2],int p2[2],int w,int rect[4][2])
127 {
128 int dx = p2[0] - p1[0];
129 int dy = p2[1] - p1[1];
130 int wx,wy,wx1,wy1,wx2,wy2;
131
132 if(dx == 0) {
133 wx = w;
134 wy = 0;
135 }
136 else if (dy == 0) {
137 wx = 0;
138 wy = w;
139 }
140 else {
141 unsigned long minerr,error = ~0UL,w2 = imul32(w,w);
142 int mindelta = umin(iabs(dx),iabs(dy));
143 int maxdelta = umax(iabs(dx),iabs(dy));
144 wx1 = w/2;
145 if (wx1 <= 0) wx1 = 1;
146 if (wx1+wx1 < w) ++wx1;
147 wy1 = 0;
148 do {
149 wx = wx1++;
150 wy = wy1;
151 wy1 = urscale(wx1,mindelta,maxdelta);
152 minerr = error;
153 error = imul32(wx1,wx1) + imul32(wy1,wy1) - w2;
154 error = labs(error);
155 } while(error <= minerr);
156 if(iabs(dx) > iabs(dy)) iswap(wx,wy);
157 }
158 if(dx < 0) wy = (-wy);
159 if(dy >= 0) wx = (-wx);
160 wx1 = -(wx >> 1);
161 wy1 = -(wy >> 1);
162 wx2 = wx + wx1;
163 wy2 = wy + wy1;
164 if((wx1 + wx2) < 0) wx1++,wx2++;
165 if((wy1 + wy2) < 0) wy1++,wy2++;
166 rect[0][0] = p1[0] + wx1;
167 rect[0][1] = p1[1] + wy1;
168 rect[1][0] = p1[0] + wx2;
169 rect[1][1] = p1[1] + wy2;
170 rect[2][0] = p2[0] + wx2;
171 rect[2][1] = p2[1] + wy2;
172 rect[3][0] = p2[0] + wx1;
173 rect[3][1] = p2[1] + wy1;
174 }
175
176 /*
177 * working version of the line pattern and fill argument structures
178 */
179 typedef struct {
180 int w; /* line width */
181 int psegs; /* number of pattern segments */
182 int plength; /* total length of pattern in pixels */
183 int ppos; /* current pattern position (modulo plength) */
184 int on; /* is the pattern currently on ? */
185 unsigned char *patt; /* the pattern bits */
186 GrFiller *f; /* the filler functions */
187 GrFillArg c; /* the filler argument */
188 } linepatt;
189
solidsegment1(int p1[2],int p2[2],int prev[2],int next[2],linepatt * p)190 static void solidsegment1(
191 int p1[2], int p2[2],
192 int prev[2],int next[2],
193 linepatt *p
194 ){
195 int x1 = p1[0], y1 = p1[1];
196 int x2 = p2[0], y2 = p2[1];
197 (*p->f->line)(
198 (x1 + CURC->gc_xoffset),
199 (y1 + CURC->gc_yoffset),
200 (x2 - x1),
201 (y2 - y1),
202 p->c
203 );
204 }
205
solidsegmentw(int p1[2],int p2[2],int prev[2],int next[2],linepatt * p)206 static void solidsegmentw(
207 int p1[2], int p2[2],
208 int prev[2],int next[2],
209 linepatt *p
210 ){
211 int rect[4][2], prect[4][2], nrect[4][2];
212 genrect(p1,p2,p->w,rect);
213 if(prev) genrect(prev,p1,p->w,prect);
214 if(next) genrect(p2,next,p->w,nrect);
215 if(prev && next) {
216 int points[2];
217 points[0] = rect[1][0]; points[1] = rect[1][1];
218 intersect(prect[1],prect[2],rect[1],rect[2]);
219 intersect(points,rect[2],nrect[1],nrect[2]);
220 points[0] = rect[0][0]; points[1] = rect[0][1];
221 intersect(prect[0],prect[3],rect[0],rect[3]);
222 intersect(points,rect[3],nrect[0],nrect[3]);
223 } else
224 if(prev) {
225 intersect(prect[1],prect[2],rect[1],rect[2]);
226 intersect(prect[0],prect[3],rect[0],rect[3]);
227 } else
228 if(next) {
229 intersect(rect[1],rect[2],nrect[1],nrect[2]);
230 intersect(rect[0],rect[3],nrect[0],nrect[3]);
231 }
232 _GrScanConvexPoly(4,rect,p->f,p->c);
233 }
234
dashedsegment(int p1[2],int p2[2],int prev[2],int next[2],linepatt * p,void (* doseg)(int[2],int[2],int[2],int[2],linepatt *))235 static void dashedsegment(
236 int p1[2], int p2[2],
237 int prev[2],int next[2],
238 linepatt *p,
239 void (*doseg)(int[2],int[2],int[2],int[2],linepatt*)
240 ){
241 int on,pos,len,seg;
242 int x,y,dx,dy;
243 int error,erradd,errsub,count;
244 int xinc1,xinc2,yinc1,yinc2;
245 int start[2],end[2], se_init;
246
247 /* find the current starting segment for the pattern */
248 pos = (p->ppos %= p->plength);
249 for(on = 1,seg = 0; ; ) {
250 len = p->patt[seg];
251 if(pos < len) { len -= pos; break; }
252 if(++seg >= p->psegs) seg = 0;
253 on ^= 1;
254 pos -= len;
255 }
256 /* Can't have a zero length element here */
257
258 /* set up line drawing */
259 x = p1[0]; dx = p2[0] - x;
260 y = p1[1]; dy = p2[1] - y;
261 if(dx >= 0) { xinc2 = 1; }
262 else { xinc2 = -1; dx = -dx; }
263 if(dy >= 0) { yinc2 = 1; }
264 else { yinc2 = -1; dy = -dy; }
265 if(dx >= dy) {
266 count = dx + 1;
267 error = dx >> 1;
268 errsub = dy;
269 erradd = dx;
270 xinc1 = xinc2;
271 yinc1 = 0;
272 }
273 else {
274 count = dy + 1;
275 error = dy >> 1;
276 errsub = dx;
277 erradd = dy;
278 yinc1 = yinc2;
279 xinc1 = 0;
280 }
281 se_init = 0;
282 if(on) {
283 start[0] = x;
284 start[1] = y;
285 se_init = 1;
286 }
287 else {
288 prev = NULL;
289 }
290 /* go */
291 while(--count >= 0) {
292 if(on) {
293 end[0] = x;
294 end[1] = y;
295 se_init |= 2;
296 }
297 if((error -= errsub) < 0) {
298 error += erradd;
299 x += xinc2;
300 y += yinc2;
301 }
302 else {
303 x += xinc1;
304 y += yinc1;
305 }
306 if(--len <= 0) {
307 /* end of current segment */
308 int old_state = on;
309 do {
310 if(++seg >= p->psegs) seg = 0;
311 len = p->patt[seg];
312 on ^= 1;
313 } while (len == 0);
314 if ( !old_state && on && count > 0) {
315 start[0] = x;
316 start[1] = y;
317 se_init = 1;
318 } else
319 if ( old_state && !on) {
320 (*doseg)(start,end,prev,NULL,p);
321 prev = NULL;
322 se_init = 0;
323 }
324 /* else: zero length element(s), continue current segment */
325 }
326 }
327 if(on && se_init==3) {
328 (*doseg)(start,end,prev,next,p);
329 }
330 p->on = on;
331 }
332
dashedsegment1(int p1[2],int p2[2],int prev[2],int next[2],linepatt * p)333 static void dashedsegment1(
334 int p1[2], int p2[2],
335 int prev[2],int next[2],
336 linepatt *p
337 ){
338 dashedsegment(p1,p2,prev,next,p,solidsegment1);
339 }
340
dashedsegmentw(int p1[2],int p2[2],int prev[2],int next[2],linepatt * p)341 static void dashedsegmentw(
342 int p1[2], int p2[2],
343 int prev[2],int next[2],
344 linepatt *p
345 ){
346 dashedsegment(p1,p2,prev,next,p,solidsegmentw);
347 }
348
_GrDrawCustomPolygon(int n,int pt[][2],const GrLineOption * lp,GrFiller * f,GrFillArg c,int doClose,int circle)349 void _GrDrawCustomPolygon(
350 int n,int pt[][2],
351 const GrLineOption *lp,
352 GrFiller *f,GrFillArg c,
353 int doClose,int circle
354 ){
355 # define x1 start[0]
356 # define y1 start[1]
357 # define x2 end[0]
358 # define y2 end[1]
359 int i,start[2],end[2];
360 void (*doseg)(int[2],int[2],int[2],int[2],linepatt*);
361 linepatt p;
362 GrContext preclip;
363 if(n < 2) return;
364 /* set up working pattern */
365 p.f = f;
366 p.c = c;
367 p.w = imax((lp->lno_width - 1),0);
368 p.ppos = 0;
369 p.patt = lp->lno_dashpat;
370 p.psegs = p.patt ? imax(lp->lno_pattlen,0) : 0;
371 p.plength = 0;
372 for(i = 0; i < p.psegs; i++) {
373 /* if(!p.patt[i]) { p.plength = 0; break; } */
374 p.plength += p.patt[i];
375 }
376 if(p.plength)
377 doseg = p.w ? dashedsegmentw : dashedsegment1;
378 else {
379 if (p.psegs && p.patt[0]==0 ) return; /* nothing to do */
380 doseg = p.w ? solidsegmentw : solidsegment1;
381 }
382 /* preclip */
383 x1 = x2 = pt[0][0];
384 y1 = y2 = pt[0][1];
385 for(i = 1; i < n; i++) {
386 int *ppt = pt[i];
387 if(x1 > ppt[0]) x1 = ppt[0];
388 if(x2 < ppt[0]) x2 = ppt[0];
389 if(y1 > ppt[1]) y1 = ppt[1];
390 if(y2 < ppt[1]) y2 = ppt[1];
391 }
392 sttcopy(&preclip,CURC);
393 preclip.gc_xcliplo -= p.w; preclip.gc_ycliplo -= p.w;
394 preclip.gc_xcliphi += p.w; preclip.gc_ycliphi += p.w;
395 clip_ordbox((&preclip),x1,y1,x2,y2);
396 mouse_block(CURC,x1,y1,x2,y2);
397 /* do the polygon segments */
398 if(doClose) {
399 int *p1 = pt[0], *p2 = pt[n - 1];
400 if((n > 1) && (p1[0] == p2[0]) && (p1[1] == p2[1])) n--;
401 if(n < 3) doClose = FALSE;
402 }
403 for(i = 0; i < n; i++) {
404 int clipped,xmajor,length;
405 int *p1,*p2,*prev,*next;
406 if(!(i + doClose)) continue;
407 p1 = pt[(i + n - 1) % n];
408 p2 = pt[i];
409 prev = ((i > 1) || doClose) ? pt[(i + n - 2) % n] : NULL;
410 next = ((i < (n - 1)) || doClose) ? pt[(i + 1) % n] : NULL;
411 x1 = p1[0];
412 y1 = p1[1];
413 x2 = p2[0];
414 y2 = p2[1];
415 clipped = 0;
416 xmajor = iabs(x1 - x2);
417 length = iabs(y1 - y2);
418 if(xmajor > length) { length = xmajor; xmajor = 1; }
419 else xmajor = 0;
420 clip_line_((&preclip),x1,y1,x2,y2,goto outside,clipped = p.plength);
421 if(clipped) {
422 clipped = xmajor ? iabs(p1[0] - x1) : iabs(p1[1] - y1);
423 p.ppos += clipped;
424 length -= clipped;
425 }
426 (*doseg)(start,end,prev,next,&p);
427 outside:
428 p.ppos += length;
429 }
430 mouse_unblock();
431 # undef x1
432 # undef y1
433 # undef x2
434 # undef y2
435 }
436
437
438