![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to pathlist.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDTahoe / new / X / libibm / libsrc|
Return to pathlist.c CVS log | Up to [CSRG BSD Unix] / 43BSDTahoe / new / X / libibm / libsrc |
1.1 root 1: #ifndef lint
2: static char *rcsid_pathlist_c = "$Header: pathlist.c,v 10.1 86/11/19 10:43:18 jg Exp $";
3: #endif lint
4: /* pathlist.c - Coverter for vertex list
5: *
6: * PathListConverter Convert a list of vertices
7: * into absolute striaght lines
8: * Spline Generates a series of line segments
9: * that make up a smooth curve
10: * Matrix Utility rtn used by Spline to interpolate
11: * points along the curve
12: *
13: * Author:
14: * Scott Bates
15: * Brown University
16: * IRIS, Box 1946
17: * Providence, RI 02912
18: *
19: *
20: * Copyright (c) 1986 Brown University
21: *
22: * Permission to use, copy, modify and distribute this software and its
23: * documentation for any purpose and without fee is hereby granted, provided
24: * that the above copyright notice appear in all copies, and that both
25: * that copyright notice and this permission notice appear in supporting
26: * documentation, and that the name of Brown University not be used in
27: * advertising or publicity pertaining to distribution of the software
28: * without specific, written prior permission. Brown University makes no
29: * representations about the suitability of this software for any purpose.
30: * It is provided "as-is" without express or implied warranty.
31: */
32:
33: #include "private.h"
34: #include "pathlist.h"
35:
36: /*
37: * Convert vertex list
38: */
39:
40: PathListConverter(verts, vertcount, xbase, ybase, newverts, newvertcount, type)
41: register Vertex *verts;
42: int vertcount;
43: short xbase, ybase;
44: Vertex **newverts;
45: int *newvertcount;
46: int type;
47: {
48: register Vertex *ThisVertex = verts;
49: register Vertex *LastVertex;
50: register Vertex *NewVerts;
51: register Segment *CurrentSegment;
52: register i, j;
53: int VertexCount;
54: int VertexIndex = 0;
55: int SegmentIndex = 0;
56: int CurvedSegments = 0;
57: int MaxSegments = INITIAL_SEGMENTS;
58: int TotalVertexCount = vertcount;
59:
60: #ifdef TRACE_X
61: fprintf (stderr, "In PathListConverter\n");
62: fflush (stderr);
63: #endif TRACE_X
64:
65: /*
66: * Perform initial allocation of segment table
67: */
68:
69: CurrentSegment = SegmentTable =
70: (Segment *)malloc(MaxSegments * sizeof(Segment));
71: if(SegmentTable == NULL) {
72: return(NULL);
73: }
74:
75: /*
76: * Prime first segment table entry
77: */
78:
79: ThisVertex->x += xbase;
80: ThisVertex->y += ybase;
81:
82: CurrentSegment->Index = 0;
83: CurrentSegment->Count = 1;
84:
85: switch(ThisVertex->flags & VERTEX_TYPE_MASK) {
86: case(LINE): /* First segment is a line */
87:
88: CurrentSegment->Type = LINE_SEGMENT;
89: break;
90:
91: case(START_CLOSED_CURVE): /* First segment is a closed curve */
92:
93: CurrentSegment->Type = CLOSED_CURVE_SEGMENT;
94: CurvedSegments++;
95: break;
96:
97: default: /* First segment is a line */
98:
99: /*
100: * turn off bogus flags and make this first segment a line
101: */
102:
103: ThisVertex->flags &= ~(START_CLOSED_CURVE | END_CLOSED_CURVE);
104: CurrentSegment->Type = LINE_SEGMENT;
105: }
106:
107: /*
108: * Convert remaining vertices to absolute coordinates and
109: * divide them up into there appropriate segemnts.
110: */
111:
112: do {
113: if(++VertexIndex < vertcount) {
114: /*
115: * Move on to next vertex and save current vertex
116: */
117:
118: LastVertex = ThisVertex++;
119: } else {
120: /*
121: * Conversion has completed. If the last segment was a
122: * curved segment verify it before exiting loop.
123: */
124:
125: if(CurrentSegment->Type == CLOSED_CURVE_SEGMENT &&
126: ((ThisVertex->flags & VERTEX_TYPE_MASK) != END_CLOSED_CURVE ||
127: CurrentSegment->Count < 3)) {
128: return(NULL);
129: } else if(CurrentSegment->Type == OPEN_CURVE_SEGMENT &&
130: CurrentSegment->Count < 3) {
131: return(NULL);
132: }
133: break;
134: }
135:
136: /*
137: * Make Vertex an absolute coordinate
138: */
139:
140: if(ThisVertex->flags & VertexRelative) {
141: ThisVertex->x += LastVertex->x;
142: ThisVertex->y += LastVertex->y;
143: } else {
144: ThisVertex->x += xbase;
145: ThisVertex->y += ybase;
146: }
147:
148: /*
149: * If this is the last vertex turn off any bogus flags
150: * before processing it
151: */
152:
153: if((VertexIndex + 1) == vertcount &&
154: CurrentSegment->Type != CLOSED_CURVE_SEGMENT) {
155: ThisVertex->flags &= ~(END_CLOSED_CURVE);
156: }
157:
158: /*
159: * add this vertex to the current segement or start a new one.
160: */
161:
162: switch(ThisVertex->flags & VERTEX_TYPE_MASK) {
163:
164: case(LINE): /* This vertex is a LINE */
165: switch(LastVertex->flags & VERTEX_TYPE_MASK) {
166:
167: case(LINE): /* Last vertex was a LINE */
168: /*
169: * Add this vertex to the current segment
170: */
171:
172: CurrentSegment->Count++;
173: break;
174:
175: case(CURVE): /* Last vertex was a CURVE */
176: /*
177: * If the current segment type is a closed curve
178: * convert it to an open curve segment.
179: */
180:
181: if(CurrentSegment->Type == CLOSED_CURVE_SEGMENT) {
182: CurrentSegment->Type = OPEN_CURVE_SEGMENT;
183: if(CurrentSegment->Index > 0) {
184: CurrentSegment->Index--;
185: CurrentSegment->Count++;
186: }
187: }
188: if(++CurrentSegment->Count < 3) {
189: return(NULL);
190: }
191:
192: case(END_CLOSED_CURVE): /* Last vertex was a END_CLOSED_CURVE */
193: /*
194: * Start a line segment
195: */
196:
197: StartNewSegment(LINE_SEGMENT, VertexIndex, 1);
198: break;
199:
200: case(START_CLOSED_CURVE): /* Last vertex was start closed curve */
201: /*
202: * Convert the current segment to a line segment
203: */
204:
205: CurrentSegment->Type = LINE_SEGMENT;
206: CurrentSegment->Count++;
207: CurvedSegments--;
208: }
209: break;
210:
211: case(CURVE): /* This vertex was a curve */
212:
213: switch(LastVertex->flags & VERTEX_TYPE_MASK) {
214:
215: case(LINE): /* Last vertex was a line or */
216: case(END_CLOSED_CURVE): /* end closed curve */
217: /*
218: * Start an open curve segment
219: */
220:
221: StartNewSegment(OPEN_CURVE_SEGMENT, VertexIndex - 1, 2);
222: CurvedSegments++;
223: break;
224:
225: case(CURVE): /* Last vertex was a curve or start */
226: case(START_CLOSED_CURVE): /* closed curve */
227: /*
228: * Add this vertex to current segment
229: */
230:
231: CurrentSegment->Count++;
232:
233: }
234: break;
235:
236: case(START_CLOSED_CURVE): /* This vertex is start closed curve */
237:
238: switch(LastVertex->flags & VERTEX_TYPE_MASK) {
239:
240: case(CURVE): /* Last vertex was a curve */
241: /* If the current segment type is a closed curve
242: * convert it to a open curve segment. Then start
243: * a closed curve segment using this vertex.
244: */
245:
246: if(CurrentSegment->Type == CLOSED_CURVE_SEGMENT) {
247: CurrentSegment->Type = OPEN_CURVE_SEGMENT;
248: if(CurrentSegment->Index > 0) {
249: CurrentSegment->Index--;
250: CurrentSegment->Count++;
251: }
252: }
253: if(++CurrentSegment->Count < 3) {
254: return(NULL);
255: }
256:
257: case(LINE): /* Last vertex was a line or */
258: case(END_CLOSED_CURVE): /* end closed curve */
259: /*
260: * Start closed curve segemnt
261: */
262:
263: StartNewSegment(CLOSED_CURVE_SEGMENT, VertexIndex, 1);
264: CurvedSegments++;
265: break;
266:
267: case(START_CLOSED_CURVE): /* Last vertex was start closed curve */
268: /*
269: * Indicate to caller that there was a
270: * path list error.
271: */
272:
273: return(NULL);
274: }
275: break;
276:
277: case(END_CLOSED_CURVE): /* This vertex is end closed curve */
278: /*
279: * Add this vertex to the current segment
280: */
281:
282: ++CurrentSegment->Count;
283:
284: /*
285: * Last vertex was a curve
286: */
287:
288: if((LastVertex->flags & VERTEX_TYPE_MASK) == CURVE) {
289: /*
290: * Vaild vertex count of curved segment
291: */
292:
293: if(CurrentSegment->Count < 3) {
294: return(NULL);
295: }
296:
297: /*
298: * If the current segment is a closed segment
299: * validate that the last vertex of the segment
300: * equals the first.
301: */
302:
303: if(CurrentSegment->Type == CLOSED_CURVE_SEGMENT) {
304: if(verts[CurrentSegment->Index].x != verts[VertexIndex].x ||
305: verts[CurrentSegment->Index].y != verts[VertexIndex].y) {
306: return(NULL);
307: }
308: } else {
309: /*
310: * Start a line segment using this vertex
311: */
312:
313: StartNewSegment(LINE_SEGMENT, VertexIndex, 1);
314: }
315: }
316: break;
317:
318: default:
319: /*
320: * Indicate to caller that there was a
321: * path list error.
322: */
323:
324: return(NULL);
325: }
326: } while(1);
327:
328: /*
329: * If there are curved segments in this path list
330: * then perform the required setup and call the spline
331: * rtn .
332: */
333:
334: SplineUsed = 0;
335: if(CurvedSegments) {
336: Vertex *Vertex_A;
337: Vertex *Vertex_B;
338: Vertex *Vertex_C;
339: Vertex *Vertex_D;
340: int Count;
341:
342: /*
343: * Initial allocating of the spline vertex buffer
344: */
345:
346: SplineVertexIndex = 0;
347: MaxSplineVerts = INITIAL_SPLINE_VERTS;
348: SplineVertexBuffer = (Vertex *)malloc(MaxSplineVerts * sizeof(Vertex));
349: if(SplineVertexBuffer == NULL) {
350: return(NULL);
351: }
352: SplineUsed++;
353:
354: /*
355: * Loop thru all the path list segments looking
356: * for all open and closed curve segments.
357: */
358:
359: for(i = 0; i <= SegmentIndex; i++) {
360:
361: switch((CurrentSegment = &SegmentTable[i])->Type) {
362:
363: case(LINE_SEGMENT):
364: /*
365: * Ignore line segments
366: */
367:
368: continue;
369:
370: case(OPEN_CURVE_SEGMENT):
371: /*
372: * Generate a series of line segments
373: * that represent the open curve defined
374: * by this segment.
375: */
376:
377: Count = 0;
378: Vertex_A = &verts[CurrentSegment->Index +
379: CurrentSegment->Count - 1];
380: Vertex_B = &verts[CurrentSegment->Index];
381: Vertex_C = Vertex_B + 1;
382: Vertex_D = Vertex_C + 1;
383: CurrentSegment->Index = SplineVertexIndex;
384: j = CurrentSegment->Count - 2;
385:
386: while(1) {
387: Count += Spline(Vertex_A, Vertex_B, Vertex_C, Vertex_D);
388: if(--j == 0) {
389: break;
390: }
391: Vertex_A = Vertex_B;
392: Vertex_B = Vertex_C;
393: Vertex_C = Vertex_D++;
394: }
395: break;
396:
397: case(CLOSED_CURVE_SEGMENT):
398: /*
399: * Generate a series of line segments
400: * that represent the closed curve defined
401: * by this segment.
402: */
403:
404: Count = 0;
405: LastVertex = &verts[CurrentSegment->Index + 1];
406: Vertex_A = &verts[CurrentSegment->Index +
407: CurrentSegment->Count - 2];
408: Vertex_B = &verts[CurrentSegment->Index];
409: CurrentSegment->Index = SplineVertexIndex;
410: Vertex_C = Vertex_B + 1;
411: Vertex_D = Vertex_C;
412: j = CurrentSegment->Count - 2;
413:
414: while(j--) {
415: Vertex_D++;
416: Count += Spline(Vertex_A, Vertex_B, Vertex_C, Vertex_D);
417: Vertex_A = Vertex_B;
418: Vertex_B = Vertex_C;
419: Vertex_C = Vertex_D;
420: }
421: Vertex_D = LastVertex;
422: Count += Spline(Vertex_A, Vertex_B, Vertex_C, Vertex_D);
423:
424: }
425:
426: /*
427: * Adjust the current segment count and
428: * increase the total vertex to reflect
429: * the new points generated by the spline rtn.
430: */
431:
432: CurrentSegment->Count = Count;
433: TotalVertexCount += Count;
434:
435: /*
436: * If there are no more curved segments exit early
437: */
438:
439: if(--CurvedSegments == 0) {
440: break;
441: }
442: }
443: }
444:
445: /*
446: * Allocate space for new vertex list
447: */
448:
449: NewVerts = *newverts = (Vertex *)malloc((TotalVertexCount << 1) *
450: sizeof(Vertex));
451: if(NewVerts == NULL) {
452: return(NULL);
453: }
454:
455: /*
456: * Loop thru coordinate list
457: */
458:
459: for(VertexCount = 0, i = 0; i <= SegmentIndex; i++) {
460: /*
461: * If this segment is a line segment get verts from original
462: * vertex list else use the spline vertex list.
463: */
464:
465: if((CurrentSegment = &SegmentTable[i])->Type == LINE_SEGMENT) {
466: ThisVertex = &verts[CurrentSegment->Index];
467: } else {
468: ThisVertex = &SplineVertexBuffer[CurrentSegment->Index];
469: }
470:
471: /*
472: * Get segment vertex count
473: */
474:
475: j = CurrentSegment->Count;
476:
477: /*
478: * Convert path list to fill format
479: */
480:
481: if(type == FILL_PATH_LIST) {
482: do {
483: /*
484: * Something to draw ?
485: */
486:
487: if(ThisVertex->flags & VertexDontDraw) {
488: /*
489: * Indicate start of closed polygon
490: */
491:
492: ThisVertex->flags |= START_OF_CLOSED_POLY;
493:
494: /*
495: * Increment vertex pointers
496: */
497:
498: LastVertex = ThisVertex++;
499:
500: /*
501: * Continue processing of current segment
502: */
503:
504: continue;
505: }
506:
507: /*
508: * If this vertex is not a dup save the
509: * line segment represented by the last
510: * vertex and this one in NewVerts.
511: * If it is a dup ignore this vertex.
512: */
513:
514: if(ThisVertex->x != LastVertex->x ||
515: ThisVertex->y != LastVertex->y) {
516:
517: /*
518: * Save start and end points of
519: * visible line
520: */
521:
522: *NewVerts++ = *LastVertex;
523: *NewVerts++ = *ThisVertex;
524:
525: /*
526: * Increment vertex count
527: */
528:
529: VertexCount += 2;
530:
531: /*
532: * Increment vertex pointers
533: */
534:
535: LastVertex = ThisVertex++;
536: } else {
537: /*
538: * Ignore this vertex
539: */
540:
541: ThisVertex++;
542: }
543: }while(--j);
544: } else {
545: do {
546: /*
547: * Something to draw ?
548: */
549:
550: if(ThisVertex->flags & VertexDontDraw) {
551: /*
552: * Increment vertex pointers
553: */
554:
555: LastVertex = ThisVertex++;
556:
557: /*
558: * Continue processing current segment
559: */
560:
561: continue;
562: }
563:
564: if(ThisVertex->x != LastVertex->x ||
565: ThisVertex->y != LastVertex->y) {
566: /*
567: * Save start and end points of
568: * visible line
569: */
570:
571: *NewVerts++ = *LastVertex;
572: *NewVerts = *ThisVertex;
573:
574: /*
575: * Shorten line by one point if
576: * "VertexDrawLastPoint" flag is off
577: */
578:
579: if(!(ThisVertex->flags & VertexDrawLastPoint)) {
580: int DeltaX, DeltaY;
581: int SignX = 0, SignY = 0;
582:
583: if((DeltaX = ThisVertex->x - LastVertex->x) < 0) {
584: SignX = -1;
585: DeltaX = -DeltaX;
586: }
587:
588: if((DeltaY = ThisVertex->y - LastVertex->y) < 0) {
589: SignY = -1;
590: DeltaY = -DeltaY;
591: }
592:
593: if (DeltaX > DeltaY) {
594: SignX < 0 ? NewVerts->x++ : NewVerts->x--;
595: if ((DeltaX >> 1) <= DeltaY) {
596: SignY < 0 ? NewVerts->y++ : NewVerts->y--;
597: }
598: } else if (DeltaX < DeltaY ) {
599: SignY < 0 ? NewVerts->y++ : NewVerts->y--;
600: if ((DeltaY >> 1) <= DeltaX) {
601: SignX < 0 ? NewVerts->x++ : NewVerts->x--;
602: }
603: } else {
604: if (DeltaX > 0) {
605: SignX < 0 ? NewVerts->x++ : NewVerts->x--;
606: SignY < 0 ? NewVerts->y++ : NewVerts->y--;
607: } else {
608: /*
609: * Line now has a length of zero
610: * so we skip this one. Back up the
611: * buffer pointer and move on to the
612: * next vertex
613: */
614:
615: NewVerts--;
616:
617: /*
618: * Increment vertex pointers
619: */
620:
621: LastVertex = ThisVertex++;
622: continue;
623: }
624: }
625: }
626:
627: /*
628: * Advance buffer pointer
629: */
630:
631: NewVerts++;
632:
633: /*
634: * Increment vertex count
635: */
636:
637: VertexCount += 2;
638:
639: /*
640: * Increment vertex pointers
641: */
642:
643: LastVertex = ThisVertex++;
644: } else {
645: /*
646: * Ignore this vertex
647: */
648:
649: ThisVertex++;
650: }
651: } while(--j);
652: }
653: }
654:
655: /*
656: * Save final vertex count and free any resources used
657: * during path list conversion.
658: */
659:
660: *newvertcount = VertexCount;
661: free((caddr_t)SegmentTable);
662: if(SplineUsed) {
663: free((caddr_t)SplineVertexBuffer);
664: }
665: return(1);
666: }
667:
668: /*
669: * Generate a series of points that will form
670: * a curve between Vertex_B and Vertex_C.
671: */
672:
673: static
674: Spline(Vertex_A, Vertex_B, Vertex_C, Vertex_D)
675: register Vertex *Vertex_A;
676: register Vertex *Vertex_B;
677: register Vertex *Vertex_C;
678: register Vertex *Vertex_D;
679: {
680: register Vertex *Verts = &SplineVertexBuffer[SplineVertexIndex];
681: register i;
682: int nls = 1;
683: int Delta_X, Delta_Y;
684: long Matrix();
685:
686: #ifdef TRACE_X
687: fprintf (stderr, "In Spline\n");
688: fflush (stderr);
689: #endif TRACE_X
690:
691: GrowSplineVertexBuffer(Verts, 2);
692: *Verts++ = *Vertex_B;
693: SplineVertexIndex++;
694: if((Vertex_C->flags & VertexDontDraw) == 0) {
695: /*
696: * Compute how many points to generate
697: * based on the largest delta change in either
698: * the X or Y direction. This number represents
699: * the maximum number of points to be generated
700: * and may be reduced by an increasing amount
701: * as the change (delta) gets larger. This allows
702: * us to generate fewer points and therefore
703: * improve performace and still generate
704: * quality smooth curve.
705: */
706:
707: if((Delta_X = Vertex_C->x - Vertex_B->x) < 0) {
708: Delta_X = -Delta_X;
709: }
710:
711: if((Delta_Y = Vertex_C->y - Vertex_B->y) < 0) {
712: Delta_Y = -Delta_Y;
713: }
714:
715: if(Delta_X > Delta_Y) {
716: if(Delta_X > 64) {
717: nls = Delta_X >> 3;
718: } else if(Delta_X > 32) {
719: nls = Delta_X >> 2;
720: } else if(Delta_X > 16) {
721: nls = Delta_X >> 1;
722: } else {
723: nls = Delta_X;
724: }
725: } else {
726: if(Delta_Y > 64) {
727: nls = Delta_Y >> 3;
728: } else if(Delta_Y > 32) {
729: nls = Delta_Y >> 2;
730: } else if(Delta_Y > 16) {
731: nls = Delta_Y >> 1;
732: } else {
733: nls = Delta_Y;
734: }
735: }
736:
737: /*
738: * Generate the actual points
739: */
740:
741: if(nls) {
742: GrowSplineVertexBuffer(Verts, nls);
743: for(i = 1; i < nls; i++, Verts++) {
744: Verts->x = Matrix((long)Vertex_A->x, (long)Vertex_B->x,
745: (long)Vertex_C->x, (long)Vertex_D->x, nls, i);
746: Verts->y = Matrix((long)Vertex_A->y, (long)Vertex_B->y,
747: (long)Vertex_C->y, (long)Vertex_D->y, nls, i);
748: Verts->flags = Vertex_C->flags & VertexDrawLastPoint;
749: }
750: SplineVertexIndex += nls;
751: } else {
752: nls = 1;
753: SplineVertexIndex++;
754: }
755: } else {
756: SplineVertexIndex++;
757: }
758: *Verts = *Vertex_C;
759:
760: /*
761: * Return the number of points generated
762: */
763:
764: return(nls + 1);
765: }
766:
767: /*
768: * This rtn performs the matrix math require to interpolate a
769: * point on the curve represented by a, b, c, and d. The generated
770: * point will be between points b and c.
771: */
772:
773: static long
774: Matrix(a, b, c, d, nls, i)
775: register long a, b, c, d;
776: register nls;
777: int i;
778: {
779: register long p = SHIFT_LEFT_16(-a + b - c + d);
780:
781: #ifdef TRACE_X
782: fprintf (stderr, "In Matrix\n");
783: fflush (stderr);
784: #endif TRACE_X
785:
786: p = PERCENT_16(p, i, nls) + SHIFT_LEFT_16((a << 1) - (b << 1) + c - d);
787: p = PERCENT_16(p, i, nls) + SHIFT_LEFT_16(-a + c);
788: return(ROUND_16(PERCENT_16(p, i, nls) + SHIFT_LEFT_16(b)));
789: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.