[BACK]Return to util3d.c CVS log [TXT][DIR] Up to [local] / OpenXM_contrib / gnuplot

Annotation of OpenXM_contrib/gnuplot/util3d.c, Revision 1.1.1.1

1.1       maekawa     1: #ifndef lint
                      2: static char *RCSid = "$Id: util3d.c,v 1.17 1998/06/18 14:55:20 ddenholm Exp $";
                      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>