Annotation of OpenXM_contrib/gnuplot/util3d.c, Revision 1.1.1.2
1.1 maekawa 1: #ifndef lint
1.1.1.2 ! maekawa 2: static char *RCSid = "$Id: util3d.c,v 1.7 1998/09/21 21:04:42 lhecking Exp $";
1.1 maekawa 3: #endif
4:
5:
6: /* GNUPLOT - util3d.c */
7:
8: /*[
9: * Copyright 1986 - 1993, 1998 Thomas Williams, Colin Kelley
10: *
11: * Permission to use, copy, and distribute this software and its
12: * documentation for any purpose with or without fee is hereby granted,
13: * provided that the above copyright notice appear in all copies and
14: * that both that copyright notice and this permission notice appear
15: * in supporting documentation.
16: *
17: * Permission to modify the software is granted, but not the right to
18: * distribute the complete modified source code. Modifications are to
19: * be distributed as patches to the released version. Permission to
20: * distribute binaries produced by compiling modified sources is granted,
21: * provided you
22: * 1. distribute the corresponding source modifications from the
23: * released version in the form of a patch file along with the binaries,
24: * 2. add special version identification to distinguish your version
25: * in addition to the base release version number,
26: * 3. provide your name and address as the primary contact for the
27: * support of your modified version, and
28: * 4. retain our contact information in regard to use of the base
29: * software.
30: * Permission to distribute the released version of the source code along
31: * with corresponding source modifications in the form of a patch file is
32: * granted with same provisions 2 through 4 for binary distributions.
33: *
34: * This software is provided "as is" without express or implied warranty
35: * to the extent permitted by applicable law.
36: ]*/
37:
38:
39: /*
40: * 19 September 1992 Lawrence Crowl (crowl@cs.orst.edu)
41: * Added user-specified bases for log scaling.
42: *
43: * 3.6 - split graph3d.c into graph3d.c (graph),
44: * util3d.c (intersections, etc)
45: * hidden3d.c (hidden-line removal code)
46: *
47: */
48:
49: #include "plot.h"
50: #include "setshow.h"
51:
52: extern int xleft,xright,ybot,ytop;
53: extern int hidden_active; /* HBB 980324: hidden_no_update was unused here */
54:
55: /* ACCESS THINGS THAT OUGHT TO BE HIDDEN IN hidden3d.c - perhaps we
56: * can move the relevant code into hidden3d.c sometime
57: */
58:
59: /* Bitmap of the screen. The array for each x value is malloc-ed as needed */
60:
61: extern int suppressMove;
62:
63: extern double min_array[], max_array[];
64: extern int auto_array[], log_array[];
65: extern double base_array[], log_base_array[];
66:
67: /* for convenience while converting to use these arrays */
68: #define x_min3d min_array[FIRST_X_AXIS]
69: #define x_max3d max_array[FIRST_X_AXIS]
70: #define y_min3d min_array[FIRST_Y_AXIS]
71: #define y_max3d max_array[FIRST_Y_AXIS]
72: #define z_min3d min_array[FIRST_Z_AXIS]
73: #define z_max3d max_array[FIRST_Z_AXIS]
74: #define min3d_z min_array[FIRST_Z_AXIS]
75: #define max3d_z max_array[FIRST_Z_AXIS]
76:
77: typedef double transform_matrix[4][4];
78:
79: void mat_unit(mat)
80: transform_matrix mat;
81: {
82: int i, j;
83:
84: for (i = 0; i < 4; i++) for (j = 0; j < 4; j++)
85: if (i == j)
86: mat[i][j] = 1.0;
87: else
88: mat[i][j] = 0.0;
89: }
90:
91: void mat_trans(tx, ty, tz, mat)
92: double tx, ty, tz;
93: transform_matrix mat;
94: {
95: mat_unit(mat); /* Make it unit matrix. */
96: mat[3][0] = tx;
97: mat[3][1] = ty;
98: mat[3][2] = tz;
99: }
100:
101: void mat_scale(sx, sy, sz, mat)
102: double sx, sy, sz;
103: transform_matrix mat;
104: {
105: mat_unit(mat); /* Make it unit matrix. */
106: mat[0][0] = sx;
107: mat[1][1] = sy;
108: mat[2][2] = sz;
109: }
110:
111: void mat_rot_x(teta, mat)
112: double teta;
113: transform_matrix mat;
114: {
115: double cos_teta, sin_teta;
116:
117: teta *= Pi / 180.0;
118: cos_teta = cos(teta);
119: sin_teta = sin(teta);
120:
121: mat_unit(mat); /* Make it unit matrix. */
122: mat[1][1] = cos_teta;
123: mat[1][2] = -sin_teta;
124: mat[2][1] = sin_teta;
125: mat[2][2] = cos_teta;
126: }
127:
128: void mat_rot_y(teta, mat)
129: double teta;
130: transform_matrix mat;
131: {
132: double cos_teta, sin_teta;
133:
134: teta *= Pi / 180.0;
135: cos_teta = cos(teta);
136: sin_teta = sin(teta);
137:
138: mat_unit(mat); /* Make it unit matrix. */
139: mat[0][0] = cos_teta;
140: mat[0][2] = -sin_teta;
141: mat[2][0] = sin_teta;
142: mat[2][2] = cos_teta;
143: }
144:
145: void mat_rot_z(teta, mat)
146: double teta;
147: transform_matrix mat;
148: {
149: double cos_teta, sin_teta;
150:
151: teta *= Pi / 180.0;
152: cos_teta = cos(teta);
153: sin_teta = sin(teta);
154:
155: mat_unit(mat); /* Make it unit matrix. */
156: mat[0][0] = cos_teta;
157: mat[0][1] = -sin_teta;
158: mat[1][0] = sin_teta;
159: mat[1][1] = cos_teta;
160: }
161:
162: /* Multiply two transform_matrix. Result can be one of two operands. */
163: void mat_mult(mat_res, mat1, mat2)
164: transform_matrix mat_res, mat1, mat2;
165: {
166: int i, j, k;
167: transform_matrix mat_res_temp;
168:
169: for (i = 0; i < 4; i++) for (j = 0; j < 4; j++) {
170: mat_res_temp[i][j] = 0;
171: for (k = 0; k < 4; k++) mat_res_temp[i][j] += mat1[i][k] * mat2[k][j];
172: }
173: for (i = 0; i < 4; i++) for (j = 0; j < 4; j++)
174: mat_res[i][j] = mat_res_temp[i][j];
175: }
176:
177:
178: /* Test a single point to be within the xleft,xright,ybot,ytop bbox.
179: * Sets the returned integers 4 l.s.b. as follows:
180: * bit 0 if to the left of xleft.
181: * bit 1 if to the right of xright.
182: * bit 2 if above of ytop.
183: * bit 3 if below of ybot.
184: * 0 is returned if inside.
185: */
186: int clip_point(x, y)
187: unsigned int x, y;
188: {
189: int ret_val = 0;
190:
191: if (x < xleft) ret_val |= 0x01;
192: if (x > xright) ret_val |= 0x02;
193: if (y < ybot) ret_val |= 0x04;
194: if (y > ytop) ret_val |= 0x08;
195:
196: return ret_val;
197: }
198:
199: /* Clip the given line to drawing coords defined as xleft,xright,ybot,ytop.
200: * This routine uses the cohen & sutherland bit mapping for fast clipping -
201: * see "Principles of Interactive Computer Graphics" Newman & Sproull page 65.
202: */
203: void draw_clip_line(x1, y1, x2, y2)
204: unsigned int x1, y1, x2, y2;
205: {
206: int x, y, dx, dy, x_intr[4], y_intr[4], count, pos1, pos2;
207: register struct termentry *t = term;
208:
209: #if defined(ATARI) || defined(MTOS)
210: if(x1<0||x2<0||y1<0||y2<0) return; /* temp bug fix */
211: #endif
212:
213: pos1 = clip_point(x1, y1);
214: pos2 = clip_point(x2, y2);
215: if (pos1 || pos2) {
216: if (pos1 & pos2) return; /* segment is totally out. */
217:
218: /* Here part of the segment MAY be inside. test the intersection
219: * of this segment with the 4 boundaries for hopefully 2 intersections
220: * in. If none are found segment is totaly out.
221: * Under rare circumstances there may be up to 4 intersections (e.g.
222: * when the line passes directly through at least one corner). In
223: * this case it is sufficient to take any 2 intersections (e.g. the
224: * first two found).
225: */
226: count = 0;
227: dx = x2 - x1;
228: dy = y2 - y1;
229:
230: /* Find intersections with the x parallel bbox lines: */
231: if (dy != 0) {
232: x = (ybot - y2) * dx / dy + x2; /* Test for ybot boundary. */
233: if (x >= xleft && x <= xright) {
234: x_intr[count] = x;
235: y_intr[count++] = ybot;
236: }
237: x = (ytop - y2) * dx / dy + x2; /* Test for ytop boundary. */
238: if (x >= xleft && x <= xright) {
239: x_intr[count] = x;
240: y_intr[count++] = ytop;
241: }
242: }
243:
244: /* Find intersections with the y parallel bbox lines: */
245: if (dx != 0) {
246: y = (xleft - x2) * dy / dx + y2; /* Test for xleft boundary. */
247: if (y >= ybot && y <= ytop) {
248: x_intr[count] = xleft;
249: y_intr[count++] = y;
250: }
251: y = (xright - x2) * dy / dx + y2; /* Test for xright boundary. */
252: if (y >= ybot && y <= ytop) {
253: x_intr[count] = xright;
254: y_intr[count++] = y;
255: }
256: }
257:
258: if (count >= 2) {
259: int x_max, x_min, y_max, y_min;
260:
261: x_min = GPMIN(x1, x2);
262: x_max = GPMAX(x1, x2);
263: y_min = GPMIN(y1, y2);
264: y_max = GPMAX(y1, y2);
265:
266: if (pos1 && pos2) { /* Both were out - update both */
267: x1 = x_intr[0];
268: y1 = y_intr[0];
269: x2 = x_intr[1];
270: y2 = y_intr[1];
271: }
272: else if (pos1) { /* Only x1/y1 was out - update only it */
273: if (dx * (x2 - x_intr[0]) + dy * (y2 - y_intr[0]) > 0) {
274: x1 = x_intr[0];
275: y1 = y_intr[0];
276: }
277: else {
278: x1 = x_intr[1];
279: y1 = y_intr[1];
280: }
281: }
282: else { /* Only x2/y2 was out - update only it */
283: if (dx * (x_intr[0] - x1) + dy * (y_intr[0] - y1) > 0) {
284: x2 = x_intr[0];
285: y2 = y_intr[0];
286: }
287: else {
288: x2 = x_intr[1];
289: y2 = y_intr[1];
290: }
291: }
292:
293: if (x1 < x_min || x1 > x_max ||
294: x2 < x_min || x2 > x_max ||
295: y1 < y_min || y1 > y_max ||
296: y2 < y_min || y2 > y_max) return;
297: }
298: else
299: return;
300: }
301:
302:
303: #ifndef LITE
304: if(hidden3d && hidden_active && draw_surface)
305: {
306: draw_line_hidden(x1, y1, x2, y2);
307: return;
308: };
309: #endif /* not LITE */
310: if(!suppressMove) (*t->move)(x1,y1);
311: (*t->vector)(x2,y2);
312: }
313:
314:
315:
316: /* And text clipping routine. */
317: void clip_put_text(x, y, str)
318: unsigned int x,y;
319: char *str;
320: {
321: register struct termentry *t = term;
322:
323: if (clip_point(x, y)) return;
324:
325: (*t->put_text)(x,y,str);
326: }
327:
328: /* seems sensible to put the justification in here too..? */
329: void clip_put_text_just(x,y,str,just)
330: unsigned int x,y;
331: char *str;
332: enum JUSTIFY just;
333: {
334: register struct termentry *t = term;
335: if (clip_point(x,y)) return;
336: if (!(*t->justify_text)(just)) {
337: assert(CENTRE == 1 && RIGHT == 2);
338: x -= (t->h_char * strlen(str) * just)/2;
339: }
340: (*t->put_text)(x,y,str);
341: }
342:
343:
344:
345: /* Clip the given line to drawing coords defined as xleft,xright,ybot,ytop.
346: * This routine uses the cohen & sutherland bit mapping for fast clipping -
347: * see "Principles of Interactive Computer Graphics" Newman & Sproull page 65.
348: */
349:
350: int clip_line(x1, y1, x2, y2)
351: int *x1, *y1, *x2, *y2;
352: {
353: int x, y, dx, dy, x_intr[4], y_intr[4], count, pos1, pos2;
354: int x_max, x_min, y_max, y_min;
355: pos1 = clip_point(*x1, *y1);
356: pos2 = clip_point(*x2, *y2);
357: if (!pos1 && !pos2) return 1; /* segment is totally in */
358: if (pos1 & pos2) return 0; /* segment is totally out. */
359: /* Here part of the segment MAY be inside. test the intersection
360: * of this segment with the 4 boundaries for hopefully 2 intersections
361: * in. If non found segment is totaly out.
362: */
363: count = 0;
364: dx = *x2 - *x1;
365: dy = *y2 - *y1;
366: /* Find intersections with the x parallel bbox lines: */
367: if (dy != 0) {
368: x = (ybot - *y2) * dx / dy + *x2; /* Test for ybot boundary. */
369: if (x >= xleft && x <= xright) {
370: x_intr[count] = x;
371: y_intr[count++] = ybot;
372: }
373: x = (ytop - *y2) * dx / dy + *x2; /* Test for ytop boundary. */
374: if (x >= xleft && x <= xright) {
375: x_intr[count] = x;
376: y_intr[count++] = ytop;
377: }
378: }
379: /* Find intersections with the y parallel bbox lines: */
380: if (dx != 0) {
381: y = (xleft - *x2) * dy / dx + *y2; /* Test for xleft boundary. */
382: if (y >= ybot && y <= ytop) {
383: x_intr[count] = xleft;
384: y_intr[count++] = y;
385: }
386: y = (xright - *x2) * dy / dx + *y2; /* Test for xright boundary. */
387: if (y >= ybot && y <= ytop) {
388: x_intr[count] = xright;
389: y_intr[count++] = y;
390: }
391: }
392: if (count < 2) return 0;
393: if (*x1 < *x2)
394: x_min = *x1, x_max = *x2;
395: else
396: x_min = *x2, x_max = *x1;
397: if (*y1 < *y2)
398: y_min = *y1, y_max = *y2;
399: else
400: y_min = *y2, y_max = *y1;
401: if (pos1 && pos2) { /* Both were out - update both */
402: *x1 = x_intr[0];
403: *y1 = y_intr[0];
404: *x2 = x_intr[1];
405: *y2 = y_intr[1];
406: }
407: else if (pos1)
408: { /* Only x1/y1 was out - update only it */
409: if (dx * (*x2 - x_intr[0]) + dy * (*y2 - y_intr[0]) >= 0)
410: {
411: *x1 = x_intr[0];
412: *y1 = y_intr[0];
413: }
414: else
415: {
416: *x1 = x_intr[1];
417: *y1 = y_intr[1];
418: }
419: }
420: else
421: { /* Only x2/y2 was out - update only it */
422: if (dx * (x_intr[0] - *x1) + dy * (y_intr[0] - *y1) >= 0)
423: {
424: *x2 = x_intr[0];
425: *y2 = y_intr[0];
426: }
427: else
428: {
429: *x2 = x_intr[1];
430: *y2 = y_intr[1];
431: }
432: }
433:
434: if (*x1 < x_min || *x1 > x_max ||
435: *x2 < x_min || *x2 > x_max ||
436: *y1 < y_min || *y1 > y_max ||
437: *y2 < y_min || *y2 > y_max)
438: return 0;
439: return 1;
440: }
441:
442:
443: /* single edge intersection algorithm */
444: /* Given two points, one inside and one outside the plot, return
445: * the point where an edge of the plot intersects the line segment defined
446: * by the two points.
447: */
448: void edge3d_intersect(points, i, ex, ey, ez)
449: struct coordinate GPHUGE *points; /* the points array */
450: int i; /* line segment from point i-1 to point i */
451: double *ex, *ey, *ez; /* the point where it crosses an edge */
452: {
453: /* global x_min3d, x_max3d, y_min3d, y_max3d, min3d_z, max3d_z */
454: int count;
455: double ix = points[i-1].x;
456: double iy = points[i-1].y;
457: double iz = points[i-1].z;
458: double ox = points[i].x;
459: double oy = points[i].y;
460: double oz = points[i].z;
461: double x, y, z; /* possible intersection point */
462:
463: if(points[i].type == INRANGE)
464: {
465: /* swap points around so that ix/ix/iz are INRANGE and ox/oy/oz are OUTRANGE */
466: x = ix;ix = ox;ox = x;
467: y = iy;iy = oy;oy = y;
468: z = iz;iz = oz;oz = z;
469: }
470:
471: /* nasty degenerate cases, effectively drawing to an infinity point (?)
472: cope with them here, so don't process them as a "real" OUTRANGE point
473:
474: If more than one coord is -VERYLARGE, then can't ratio the "infinities"
475: so drop out by returning the INRANGE point.
476:
477: Obviously, only need to test the OUTRANGE point (coordinates) */
478:
479: /* nasty degenerate cases, effectively drawing to an infinity point (?)
480: cope with them here, so don't process them as a "real" OUTRANGE point
481:
482: If more than one coord is -VERYLARGE, then can't ratio the "infinities"
483: so drop out by returning FALSE */
484:
485: count = 0;
486: if(ox == -VERYLARGE) count++;
487: if(oy == -VERYLARGE) count++;
488: if(oz == -VERYLARGE) count++;
489:
490: /* either doesn't pass through 3D volume *or*
491: can't ratio infinities to get a direction to draw line, so return the INRANGE point */
492: if(count > 1){
493: *ex = ix;
494: *ey = iy;
495: *ez = iz;
496:
497: return;
498: }
499:
500: if(count == 1)
501: {
502: *ex = ix;
503: *ey = iy;
504: *ez = iz;
505:
506: if(ox == -VERYLARGE)
507: {
508: *ex = x_min3d;
509: return;
510: }
511:
512: if(oy == -VERYLARGE)
513: {
514: *ey = y_min3d;
515: return;
516: }
517:
518: /* obviously oz is -VERYLARGE and (ox != -VERYLARGE && oy != -VERYLARGE) */
519: *ez = min3d_z;
520: return;
521: }
522:
523: /*
524: * Can't have case (ix == ox && iy == oy && iz == oz) as one point
525: * is INRANGE and one point is OUTRANGE.
526: */
527: if(ix == ox) {
528: if(iy == oy) {
529: /* line parallel to z axis */
530:
531: /* assume inrange(iy, y_min3d, y_max3d) && inrange(ix, x_min3d, x_max3d) */
532: *ex = ix; /* == ox */
533: *ey = iy; /* == oy */
534:
535: if (inrange(max3d_z, iz, oz))
536: *ez = max3d_z;
537: else if (inrange(min3d_z, iz, oz))
538: *ez = min3d_z;
539: else {
540: graph_error("error in edge3d_intersect");
541: }
542:
543: return;
544: }
545:
546: if(iz == oz) {
547: /* line parallel to y axis */
548:
549: /* assume inrange(iz, min3d_z, max3d_z) && inrange(ix, x_min3d, x_max3d) */
550: *ex = ix; /* == ox */
551: *ez = iz; /* == oz */
552:
553: if (inrange(y_max3d, iy, oy))
554: *ey = y_max3d;
555: else if (inrange(y_min3d, iy, oy))
556: *ey = y_min3d;
557: else {
558: graph_error("error in edge3d_intersect");
559: }
560:
561: return;
562: }
563:
564: /* nasty 2D slanted line in a yz plane */
565:
566: /* does it intersect y_min3d edge */
567: if (inrange(y_min3d, iy, oy) && y_min3d != iy && y_min3d != oy) {
568: z = iz + (y_min3d-iy) * ((oz-iz) / (oy-iy));
569: if (inrange(z, min3d_z, max3d_z)) {
570: *ex = ix;
571: *ey = y_min3d;
572: *ez = z;
573: return;
574: }
575: }
576:
577: /* does it intersect y_max3d edge */
578: if (inrange(y_max3d, iy, oy) && y_max3d != iy && y_max3d != oy) {
579: z = iz + (y_max3d-iy) * ((oz-iz) / (oy-iy));
580: if (inrange(z, min3d_z, max3d_z)) {
581: *ex = ix;
582: *ey = y_max3d;
583: *ez = z;
584: return;
585: }
586: }
587:
588: /* does it intersect min3d_z edge */
589: if (inrange(min3d_z, iz, oz) && min3d_z != iz && min3d_z != oz) {
590: y = iy + (min3d_z-iz) * ((oy-iy) / (oz-iz));
591: if (inrange(y, y_min3d, y_max3d)) {
592: *ex = ix;
593: *ey = y;
594: *ez = min3d_z;
595: return;
596: }
597: }
598:
599: /* does it intersect max3d_z edge */
600: if (inrange(max3d_z, iz, oz) && max3d_z != iz && max3d_z != oz) {
601: y = iy + (max3d_z-iz) * ((oy-iy) / (oz-iz));
602: if (inrange(y, y_min3d, y_max3d)) {
603: *ex = ix;
604: *ey = y;
605: *ez = max3d_z;
606: return;
607: }
608: }
609: }
610:
611: if(iy == oy) {
612: /* already checked case (ix == ox && iy == oy) */
613: if(oz == iz) {
614: /* line parallel to x axis */
615:
616: /* assume inrange(iz, min3d_z, max3d_z) && inrange(iy, y_min3d, y_max3d) */
617: *ey = iy; /* == oy */
618: *ez = iz; /* == oz */
619:
620: if (inrange(x_max3d, ix, ox))
621: *ex = x_max3d;
622: else if (inrange(x_min3d, ix, ox))
623: *ex = x_min3d;
624: else {
625: graph_error("error in edge3d_intersect");
626: }
627:
628: return;
629: }
630:
631: /* nasty 2D slanted line in an xz plane */
632:
633: /* does it intersect x_min3d edge */
634: if (inrange(x_min3d, ix, ox) && x_min3d != ix && x_min3d != ox) {
635: z = iz + (x_min3d-ix) * ((oz-iz) / (ox-ix));
636: if (inrange(z, min3d_z, max3d_z)) {
637: *ex = x_min3d;
638: *ey = iy;
639: *ez = z;
640: return;
641: }
642: }
643:
644: /* does it intersect x_max3d edge */
645: if (inrange(x_max3d, ix, ox) && x_max3d != ix && x_max3d != ox) {
646: z = iz + (x_max3d-ix) * ((oz-iz) / (ox-ix));
647: if (inrange(z, min3d_z, max3d_z)) {
648: *ex = x_max3d;
649: *ey = iy;
650: *ez = z;
651: return;
652: }
653: }
654:
655: /* does it intersect min3d_z edge */
656: if (inrange(min3d_z, iz, oz) && min3d_z != iz && min3d_z != oz) {
657: x = ix + (min3d_z-iz) * ((ox-ix) / (oz-iz));
658: if (inrange(x, x_min3d, x_max3d)) {
659: *ex = x;
660: *ey = iy;
661: *ez = min3d_z;
662: return;
663: }
664: }
665:
666: /* does it intersect max3d_z edge */
667: if (inrange(max3d_z, iz, oz) && max3d_z != iz && max3d_z != oz) {
668: x = ix + (max3d_z-iz) * ((ox-ix) / (oz-iz));
669: if (inrange(x, x_min3d, x_max3d)) {
670: *ex = x;
671: *ey = iy;
672: *ez = max3d_z;
673: return;
674: }
675: }
676: }
677:
678: if(iz == oz) {
679: /* already checked cases (ix == ox && iz == oz) and (iy == oy && iz == oz) */
680:
681: /* nasty 2D slanted line in an xy plane */
682:
683: /* assume inrange(oz, min3d_z, max3d_z) */
684:
685: /* does it intersect x_min3d edge */
686: if (inrange(x_min3d, ix, ox) && x_min3d != ix && x_min3d != ox) {
687: y = iy + (x_min3d-ix) * ((oy-iy) / (ox-ix));
688: if (inrange(y, y_min3d, y_max3d)) {
689: *ex = x_min3d;
690: *ey = y;
691: *ez = iz;
692: return;
693: }
694: }
695:
696: /* does it intersect x_max3d edge */
697: if (inrange(x_max3d, ix, ox) && x_max3d != ix && x_max3d != ox) {
698: y = iy + (x_max3d-ix) * ((oy-iy) / (ox-ix));
699: if (inrange(y, y_min3d, y_max3d)) {
700: *ex = x_max3d;
701: *ey = y;
702: *ez = iz;
703: return;
704: }
705: }
706:
707: /* does it intersect y_min3d edge */
708: if (inrange(y_min3d, iy, oy) && y_min3d != iy && y_min3d != oy) {
709: x = ix + (y_min3d-iy) * ((ox-ix) / (oy-iy));
710: if (inrange(x, x_min3d, x_max3d)) {
711: *ex = x;
712: *ey = y_min3d;
713: *ez = iz;
714: return;
715: }
716: }
717:
718: /* does it intersect y_max3d edge */
719: if (inrange(y_max3d, iy, oy) && y_max3d != iy && y_max3d != oy) {
720: x = ix + (y_max3d-iy) * ((ox-ix) / (oy-iy));
721: if (inrange(x, x_min3d, x_max3d)) {
722: *ex = x;
723: *ey = y_max3d;
724: *ez = iz;
725: return;
726: }
727: }
728: }
729:
730: /* really nasty general slanted 3D case */
731:
732: /* does it intersect x_min3d edge */
733: if (inrange(x_min3d, ix, ox) && x_min3d != ix && x_min3d != ox) {
734: y = iy + (x_min3d-ix) * ((oy-iy) / (ox-ix));
735: z = iz + (x_min3d-ix) * ((oz-iz) / (ox-ix));
736: if (inrange(y, y_min3d, y_max3d) && inrange(z, min3d_z, max3d_z)) {
737: *ex = x_min3d;
738: *ey = y;
739: *ez = z;
740: return;
741: }
742: }
743:
744: /* does it intersect x_max3d edge */
745: if (inrange(x_max3d, ix, ox) && x_max3d != ix && x_max3d != ox) {
746: y = iy + (x_max3d-ix) * ((oy-iy) / (ox-ix));
747: z = iz + (x_max3d-ix) * ((oz-iz) / (ox-ix));
748: if (inrange(y, y_min3d, y_max3d) && inrange(z, min3d_z, max3d_z)) {
749: *ex = x_max3d;
750: *ey = y;
751: *ez = z;
752: return;
753: }
754: }
755:
756: /* does it intersect y_min3d edge */
757: if (inrange(y_min3d, iy, oy) && y_min3d != iy && y_min3d != oy) {
758: x = ix + (y_min3d-iy) * ((ox-ix) / (oy-iy));
759: z = iz + (y_min3d-iy) * ((oz-iz) / (oy-iy));
760: if (inrange(x, x_min3d, x_max3d) && inrange(z, min3d_z, max3d_z)) {
761: *ex = x;
762: *ey = y_min3d;
763: *ez = z;
764: return;
765: }
766: }
767:
768: /* does it intersect y_max3d edge */
769: if (inrange(y_max3d, iy, oy) && y_max3d != iy && y_max3d != oy) {
770: x = ix + (y_max3d-iy) * ((ox-ix) / (oy-iy));
771: z = iz + (y_max3d-iy) * ((oz-iz) / (oy-iy));
772: if (inrange(x, x_min3d, x_max3d) && inrange(z, min3d_z, max3d_z)) {
773: *ex = x;
774: *ey = y_max3d;
775: *ez = z;
776: return;
777: }
778: }
779:
780: /* does it intersect min3d_z edge */
781: if (inrange(min3d_z, iz, oz) && min3d_z != iz && min3d_z != oz) {
782: x = ix + (min3d_z-iz) * ((ox-ix) / (oz-iz));
783: y = iy + (min3d_z-iz) * ((oy-iy) / (oz-iz));
784: if (inrange(x, x_min3d, x_max3d) && inrange(y, y_min3d, y_max3d)) {
785: *ex = x;
786: *ey = y;
787: *ez = min3d_z;
788: return;
789: }
790: }
791:
792: /* does it intersect max3d_z edge */
793: if (inrange(max3d_z, iz, oz) && max3d_z != iz && max3d_z != oz) {
794: x = ix + (max3d_z-iz) * ((ox-ix) / (oz-iz));
795: y = iy + (max3d_z-iz) * ((oy-iy) / (oz-iz));
796: if (inrange(x, x_min3d, x_max3d) && inrange(y, y_min3d, y_max3d)) {
797: *ex = x;
798: *ey = y;
799: *ez = max3d_z;
800: return;
801: }
802: }
803:
804: /* If we reach here, the inrange point is on the edge, and
805: * the line segment from the outrange point does not cross any
806: * other edges to get there. In this case, we return the inrange
807: * point as the 'edge' intersection point. This will basically draw
808: * line.
809: */
810: *ex = ix;
811: *ey = iy;
812: *ez = iz;
813: return;
814: }
815:
816: /* double edge intersection algorithm */
817: /* Given two points, both outside the plot, return
818: * the points where an edge of the plot intersects the line segment defined
819: * by the two points. There may be zero, one, two, or an infinite number
820: * of intersection points. (One means an intersection at a corner, infinite
821: * means overlaying the edge itself). We return FALSE when there is nothing
822: * to draw (zero intersections), and TRUE when there is something to
823: * draw (the one-point case is a degenerate of the two-point case and we do
824: * not distinguish it - we draw it anyway).
825: */
826: TBOOLEAN /* any intersection? */
827: two_edge3d_intersect(points, i, lx, ly, lz)
828: struct coordinate GPHUGE *points; /* the points array */
829: int i; /* line segment from point i-1 to point i */
830: double *lx, *ly, *lz; /* lx[2], ly[2], lz[2]: points where it crosses edges */
831: {
832: int count;
833: /* global x_min3d, x_max3d, y_min3d, y_max3d, min3d_z, max3d_z */
834: double ix = points[i-1].x;
835: double iy = points[i-1].y;
836: double iz = points[i-1].z;
837: double ox = points[i].x;
838: double oy = points[i].y;
839: double oz = points[i].z;
840: double t[6];
841: double swap;
842: double x, y, z; /* possible intersection point */
843: double t_min, t_max;
844:
845: /* nasty degenerate cases, effectively drawing to an infinity point (?)
846: cope with them here, so don't process them as a "real" OUTRANGE point
847:
848: If more than one coord is -VERYLARGE, then can't ratio the "infinities"
849: so drop out by returning FALSE */
850:
851: count = 0;
852: if(ix == -VERYLARGE) count++;
853: if(ox == -VERYLARGE) count++;
854: if(iy == -VERYLARGE) count++;
855: if(oy == -VERYLARGE) count++;
856: if(iz == -VERYLARGE) count++;
857: if(oz == -VERYLARGE) count++;
858:
859: /* either doesn't pass through 3D volume *or*
860: can't ratio infinities to get a direction to draw line, so simply return(FALSE) */
861: if(count > 1){
862: return(FALSE);
863: }
864:
865: if(ox == -VERYLARGE || ix == -VERYLARGE)
866: {
867: if(ix == -VERYLARGE)
868: {
869: /* swap points so ix/iy/iz don't have a -VERYLARGE component */
870: x = ix;ix = ox;ox = x;
871: y = iy;iy = oy;oy = y;
872: z = iz;iz = oz;oz = z;
873: }
874:
875: /* check actually passes through the 3D graph volume */
876: if(ix > x_max3d && inrange(iy, y_min3d, y_max3d) && inrange(iz, min3d_z, max3d_z))
877: {
878: lx[0] = x_min3d;
879: ly[0] = iy;
880: lz[0] = iz;
881:
882: lx[1] = x_max3d;
883: ly[1] = iy;
884: lz[1] = iz;
885:
886: return(TRUE);
887: }
888: else {
889: return(FALSE);
890: }
891: }
892:
893: if(oy == -VERYLARGE || iy == -VERYLARGE)
894: {
895: if(iy == -VERYLARGE)
896: {
897: /* swap points so ix/iy/iz don't have a -VERYLARGE component */
898: x = ix; ix = ox; ox = x;
899: y = iy; iy = oy; oy = y;
900: z = iz; iz = oz; oz = z;
901: }
902:
903: /* check actually passes through the 3D graph volume */
904: if(iy > y_max3d && inrange(ix, x_min3d, x_max3d) && inrange(iz, min3d_z, max3d_z))
905: {
906: lx[0] = ix;
907: ly[0] = y_min3d;
908: lz[0] = iz;
909:
910: lx[1] = ix;
911: ly[1] = y_max3d;
912: lz[1] = iz;
913:
914: return(TRUE);
915: }
916: else {
917: return(FALSE);
918: }
919: }
920:
921: if(oz == -VERYLARGE || iz == -VERYLARGE)
922: {
923: if(iz == -VERYLARGE)
924: {
925: /* swap points so ix/iy/iz don't have a -VERYLARGE component */
926: x = ix; ix = ox; ox = x;
927: y = iy; iy = oy; oy = y;
928: z = iz; iz = oz; oz = z;
929: }
930:
931: /* check actually passes through the 3D graph volume */
932: if(iz > max3d_z && inrange(ix, x_min3d, x_max3d) && inrange(iy, y_min3d, y_max3d))
933: {
934: lx[0] = ix;
935: ly[0] = iy;
936: lz[0] = min3d_z;
937:
938: lx[1] = ix;
939: ly[1] = iy;
940: lz[1] = max3d_z;
941:
942: return(TRUE);
943: }
944: else {
945: return(FALSE);
946: }
947: }
948:
949: /*
950: * Quick outcode tests on the 3d graph volume
951: */
952:
953: /*
954: * test z coord first --- most surface OUTRANGE points generated between
955: * min3d_z and z_min3d (i.e. when ticslevel is non-zero)
956: */
957: if(GPMAX(iz,oz) < min3d_z || GPMIN(iz,oz) > max3d_z)
958: return(FALSE);
959:
960: if(GPMAX(ix,ox) < x_min3d || GPMIN(ix,ox) > x_max3d)
961: return(FALSE);
962:
963: if(GPMAX(iy,oy) < y_min3d || GPMIN(iy,oy) > y_max3d)
964: return(FALSE);
965:
966: /*
967: * Special horizontal/vertical, etc. cases are checked and remaining
968: * slant lines are checked separately.
969: *
970: * The slant line intersections are solved using the parametric form
971: * of the equation for a line, since if we test x/y/z min/max planes explicitly
972: * then e.g. a line passing through a corner point (x_min,y_min,z_min)
973: * actually intersects all 3 planes and hence further tests would be required
974: * to anticipate this and similar situations.
975: */
976:
977: /*
978: * Can have case (ix == ox && iy == oy && iz == oz) as both points OUTRANGE
979: */
980: if(ix == ox && iy == oy && iz == oz)
981: {
982: /* but as only define single outrange point, can't intersect 3D graph volume */
983: return(FALSE);
984: }
985:
986: if(ix == ox) {
987: if(iy == oy) {
988: /* line parallel to z axis */
989:
990: /* x and y coords must be in range, and line must span both min3d_z and max3d_z */
991: /* note that spanning min3d_z implies spanning max3d_z as both points OUTRANGE */
992: if(!inrange(ix, x_min3d, x_max3d) || !inrange(iy, y_min3d, y_max3d))
993: {
994: return(FALSE);
995: }
996:
997: if (inrange(min3d_z, iz, oz)) {
998: lx[0] = ix;
999: ly[0] = iy;
1000: lz[0] = min3d_z;
1001:
1002: lx[1] = ix;
1003: ly[1] = iy;
1004: lz[1] = max3d_z;
1005:
1006: return(TRUE);
1007: } else
1008: return(FALSE);
1009: }
1010:
1011: if(iz == oz) {
1012: /* line parallel to y axis */
1013:
1014: /* x and z coords must be in range, and line must span both y_min3d and y_max3d */
1015: /* note that spanning y_min3d implies spanning y_max3d, as both points OUTRANGE */
1016: if(!inrange(ix, x_min3d, x_max3d) || !inrange(iz, min3d_z, max3d_z))
1017: {
1018: return(FALSE);
1019: }
1020:
1021: if (inrange(y_min3d, iy, oy)) {
1022: lx[0] = ix;
1023: ly[0] = y_min3d;
1024: lz[0] = iz;
1025:
1026: lx[1] = ix;
1027: ly[1] = y_max3d;
1028: lz[1] = iz;
1029:
1030: return(TRUE);
1031: } else
1032: return(FALSE);
1033: }
1034:
1035: /* nasty 2D slanted line in a yz plane */
1036:
1037: if(!inrange(ox, x_min3d, x_max3d))
1038: return(FALSE);
1039:
1040: t[0] = (y_min3d - iy)/(oy - iy);
1041: t[1] = (y_max3d - iy)/(oy - iy);
1042:
1043: if(t[0] > t[1]) {
1044: swap = t[0];t[0] = t[1];t[1] = swap;
1045: }
1046:
1047: t[2] = (min3d_z - iz)/(oz - iz);
1048: t[3] = (max3d_z - iz)/(oz - iz);
1049:
1050: if(t[2] > t[3]) {
1051: swap = t[2];t[2] = t[3];t[3] = swap;
1052: }
1053:
1054: t_min = GPMAX(GPMAX(t[0],t[2]),0.0);
1055: t_max = GPMIN(GPMIN(t[1],t[3]),1.0);
1056:
1057: if(t_min > t_max)
1058: return(FALSE);
1059:
1060: lx[0] = ix;
1061: ly[0] = iy + t_min * (oy - iy);
1062: lz[0] = iz + t_min * (oz - iz);
1063:
1064: lx[1] = ix;
1065: ly[1] = iy + t_max * (oy - iy);
1066: lz[1] = iz + t_max * (oz - iz);
1067:
1068: /*
1069: * Can only have 0 or 2 intersection points -- only need test one coord
1070: */
1071: if(inrange(ly[0], y_min3d, y_max3d) &&
1072: inrange(lz[0], min3d_z, max3d_z))
1073: {
1074: return(TRUE);
1075: }
1076:
1077: return(FALSE);
1078: }
1079:
1080: if(iy == oy) {
1081: /* already checked case (ix == ox && iy == oy) */
1082: if(oz == iz) {
1083: /* line parallel to x axis */
1084:
1085: /* y and z coords must be in range, and line must span both x_min3d and x_max3d */
1086: /* note that spanning x_min3d implies spanning x_max3d, as both points OUTRANGE */
1087: if(!inrange(iy, y_min3d, y_max3d) || !inrange(iz, min3d_z, max3d_z))
1088: {
1089: return(FALSE);
1090: }
1091:
1092: if (inrange(x_min3d, ix, ox)) {
1093: lx[0] = x_min3d;
1094: ly[0] = iy;
1095: lz[0] = iz;
1096:
1097: lx[1] = x_max3d;
1098: ly[1] = iy;
1099: lz[1] = iz;
1100:
1101: return(TRUE);
1102: } else
1103: return(FALSE);
1104: }
1105:
1106: /* nasty 2D slanted line in an xz plane */
1107:
1108: if(!inrange(oy, y_min3d, y_max3d))
1109: return(FALSE);
1110:
1111: t[0] = (x_min3d - ix)/(ox - ix);
1112: t[1] = (x_max3d - ix)/(ox - ix);
1113:
1114: if(t[0] > t[1]) {
1115: swap = t[0];t[0] = t[1];t[1] = swap;
1116: }
1117:
1118: t[2] = (min3d_z - iz)/(oz - iz);
1119: t[3] = (max3d_z - iz)/(oz - iz);
1120:
1121: if(t[2] > t[3]) {
1122: swap = t[2];t[2] = t[3];t[3] = swap;
1123: }
1124:
1125: t_min = GPMAX(GPMAX(t[0],t[2]),0.0);
1126: t_max = GPMIN(GPMIN(t[1],t[3]),1.0);
1127:
1128: if(t_min > t_max)
1129: return(FALSE);
1130:
1131: lx[0] = ix + t_min * (ox - ix);
1132: ly[0] = iy;
1133: lz[0] = iz + t_min * (oz - iz);
1134:
1135: lx[1] = ix + t_max * (ox - ix);
1136: ly[1] = iy;
1137: lz[1] = iz + t_max * (oz - iz);
1138:
1139: /*
1140: * Can only have 0 or 2 intersection points -- only need test one coord
1141: */
1142: if(inrange(lx[0], x_min3d, x_max3d) &&
1143: inrange(lz[0], min3d_z, max3d_z))
1144: {
1145: return(TRUE);
1146: }
1147:
1148: return(FALSE);
1149: }
1150:
1151: if(iz == oz) {
1152: /* already checked cases (ix == ox && iz == oz) and (iy == oy && iz == oz) */
1153:
1154: /* nasty 2D slanted line in an xy plane */
1155:
1156: if(!inrange(oz, min3d_z, max3d_z))
1157: return(FALSE);
1158:
1159: t[0] = (x_min3d - ix)/(ox - ix);
1160: t[1] = (x_max3d - ix)/(ox - ix);
1161:
1162: if(t[0] > t[1]) {
1163: swap = t[0];t[0] = t[1];t[1] = swap;
1164: }
1165:
1166: t[2] = (y_min3d - iy)/(oy - iy);
1167: t[3] = (y_max3d - iy)/(oy - iy);
1168:
1169: if(t[2] > t[3]) {
1170: swap = t[2];t[2] = t[3];t[3] = swap;
1171: }
1172:
1173: t_min = GPMAX(GPMAX(t[0],t[2]),0.0);
1174: t_max = GPMIN(GPMIN(t[1],t[3]),1.0);
1175:
1176: if(t_min > t_max)
1177: return(FALSE);
1178:
1179: lx[0] = ix + t_min * (ox - ix);
1180: ly[0] = iy + t_min * (oy - iy);
1181: lz[0] = iz;
1182:
1183: lx[1] = ix + t_max * (ox - ix);
1184: ly[1] = iy + t_max * (oy - iy);
1185: lz[1] = iz;
1186:
1187: /*
1188: * Can only have 0 or 2 intersection points -- only need test one coord
1189: */
1190: if(inrange(lx[0], x_min3d, x_max3d) &&
1191: inrange(ly[0], y_min3d, y_max3d))
1192: {
1193: return(TRUE);
1194: }
1195:
1196: return(FALSE);
1197: }
1198:
1199: /* really nasty general slanted 3D case */
1200:
1201: /*
1202: Solve parametric equation
1203:
1204: (ix, iy, iz) + t (diff_x, diff_y, diff_z)
1205:
1206: where 0.0 <= t <= 1.0 and
1207:
1208: diff_x = (ox - ix);
1209: diff_y = (oy - iy);
1210: diff_z = (oz - iz);
1211: */
1212:
1213: t[0] = (x_min3d - ix)/(ox - ix);
1214: t[1] = (x_max3d - ix)/(ox - ix);
1215:
1216: if(t[0] > t[1]) {
1217: swap = t[0];t[0] = t[1];t[1] = swap;
1218: }
1219:
1220: t[2] = (y_min3d - iy)/(oy - iy);
1221: t[3] = (y_max3d - iy)/(oy - iy);
1222:
1223: if(t[2] > t[3]) {
1224: swap = t[2];t[2] = t[3];t[3] = swap;
1225: }
1226:
1227: t[4] = (iz == oz) ? 0.0 : (min3d_z - iz)/(oz - iz);
1228: t[5] = (iz == oz) ? 1.0 : (max3d_z - iz)/(oz - iz);
1229:
1230: if(t[4] > t[5]) {
1231: swap = t[4];t[4] = t[5];t[5] = swap;
1232: }
1233:
1234: t_min = GPMAX(GPMAX(t[0],t[2]),GPMAX(t[4],0.0));
1235: t_max = GPMIN(GPMIN(t[1],t[3]),GPMIN(t[5],1.0));
1236:
1237: if(t_min > t_max)
1238: return(FALSE);
1239:
1240: lx[0] = ix + t_min * (ox - ix);
1241: ly[0] = iy + t_min * (oy - iy);
1242: lz[0] = iz + t_min * (oz - iz);
1243:
1244: lx[1] = ix + t_max * (ox - ix);
1245: ly[1] = iy + t_max * (oy - iy);
1246: lz[1] = iz + t_max * (oz - iz);
1247:
1248: /*
1249: * Can only have 0 or 2 intersection points -- only need test one coord
1250: */
1251: if(inrange(lx[0], x_min3d, x_max3d) &&
1252: inrange(ly[0], y_min3d, y_max3d) &&
1253: inrange(lz[0], min3d_z, max3d_z))
1254: {
1255: return(TRUE);
1256: }
1257:
1258: return(FALSE);
1259: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to util3d.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / gnuplot