home *** CD-ROM | disk | FTP | other *** search
/ Resource Library: Graphics / graphics-16000.iso / msdos / raytrace / rayshade / src / hf.c < prev    next >
Text File  |  1992-05-04  |  18KB  |  746 lines
  1. /*
  2.  * hf.c
  3.  *
  4.  * Copyright (C) 1989, 1991, Craig E. Kolb
  5.  * All rights reserved.
  6.  *
  7.  * This software may be freely copied, modified, and redistributed
  8.  * provided that this copyright notice is preserved on all copies.
  9.  *
  10.  * You may not distribute this software, in whole or in part, as part of
  11.  * any commercial product without the express consent of the authors.
  12.  *
  13.  * There is no warranty or other guarantee of fitness of this software
  14.  * for any purpose.  It is provided solely "as is".
  15.  *
  16.  * $Id: hf.c,v 4.0.1.1 91/09/29 15:44:53 cek Exp Locker: cek $
  17.  *
  18.  * $Log:    hf.c,v $
  19.  * Revision 4.0.1.1  91/09/29  15:44:53  cek
  20.  * patch1: Error messages missing newline.
  21.  * 
  22.  * Revision 4.0  91/07/17  14:38:15  kolb
  23.  * Initial version.
  24.  * 
  25.  */
  26. #include "geom.h"
  27. #include "hf.h"
  28.  
  29. static Methods *iHfMethods = NULL;
  30. static char hfName[] = "heighfield";
  31.  
  32. static void integrate_grid(), QueueTri();
  33. static int DDA2D(), CheckCell();
  34. static Float intHftri();
  35. static float minalt(), maxalt();
  36.  
  37. typedef struct {
  38.     int stepX, stepY;
  39.     Float tDX, tDY;
  40.     float minz, maxz;
  41.     int outX, outY;
  42.     Vector cp, pDX, pDY;
  43. } Trav2D;
  44.  
  45. hfTri *CreateHfTriangle(), *GetQueuedTri();
  46.  
  47. unsigned long HFTests, HFHits;
  48.  
  49. Hf *
  50. HfCreate(filename)
  51. char *filename;
  52. {
  53.     Hf *hf;
  54.     FILE *fp;
  55.     float val, *maxptr, *minptr;
  56.     int i, j;
  57.  
  58. #if defined(__WATCOMC__) || defined(__BORLANDC__)
  59.     fp = fopen(filename, "rb");
  60. #else
  61.     fp = fopen(filename, "r");
  62. #endif
  63.     if (fp == (FILE *)NULL) {
  64.         RLerror(RL_ABORT, "Cannot open heightfield file \"%s\".\n",
  65.                 filename);
  66.         return (Hf *)NULL;
  67.     }
  68.  
  69.     hf = (Hf *)RayMalloc(sizeof(Hf));
  70.     /*
  71.      * Make the following an option someday.
  72.      */
  73.     hf->BestSize = BESTSIZE;
  74.     /*
  75.      * Store the inverse for faster computation.
  76.      */
  77.     hf->iBestSize = 1. / (float)hf->BestSize;
  78.     /*
  79.      * Get HF size.
  80.      */
  81.     if (fread((char *)&hf->size, sizeof(int), 1, fp) == 0) {
  82.         RLerror(RL_ABORT, "Cannot read height field size.\n");
  83.         return (Hf *)NULL;
  84.     }
  85.         
  86.     hf->data = (float **)share_malloc(hf->size * sizeof(float *));
  87.     for (i = 0; i < hf->size; i++) {
  88.         hf->data[i] = (float *)share_malloc(hf->size * sizeof(float));
  89.         /*
  90.          * Read in row of HF data.
  91.          */
  92.         if (fread((char *)hf->data[i],sizeof(float),hf->size,fp)
  93.             != hf->size) {
  94.             RLerror(RL_ABORT, "Not enough heightfield data.\n");
  95.             return (Hf *)NULL;
  96.         }
  97.         for (j = 0; j < hf->size; j++) {
  98.             val = hf->data[i][j];
  99.             if (val <= HF_UNSET) {
  100.                 hf->data[i][j] = HF_UNSET;
  101.                 /*
  102.                  * Don't include the point in min/max
  103.                  * calculations.
  104.                  */
  105.                 continue;
  106.             }
  107.             if (val > hf->maxz)
  108.                 hf->maxz = val;
  109.             if (val < hf->minz)
  110.                 hf->minz = val;
  111.         }
  112.     }
  113.     (void)fclose(fp);
  114.  
  115.     /*
  116.      * Allocate levels of grid.  hf->levels = log base BestSize of hf->size
  117.      */
  118.     for (i = hf->size, hf->levels = 0; i > hf->BestSize; i /= hf->BestSize,
  119.                 hf->levels++)
  120.             ;
  121.     hf->levels++;
  122.     hf->qsize = CACHESIZE;
  123.     hf->q = (hfTri **)Calloc((unsigned)hf->qsize, sizeof(hfTri *));
  124.     hf->qtail = 0;
  125.  
  126.     hf->lsize = (int *)share_malloc(hf->levels * sizeof(int));
  127.     hf->spacing = (float *)share_malloc(hf->levels * sizeof(float));
  128.     hf->boundsmax = (float ***)share_malloc(hf->levels * sizeof(float **));
  129.     hf->boundsmin = (float ***)share_malloc(hf->levels * sizeof(float **));
  130.  
  131.     hf->spacing[0] = hf->size -1;
  132.     hf->lsize[0] = (int)hf->spacing[0];
  133.     hf->boundsmax[0] = (float **)share_malloc(hf->lsize[0]*sizeof(float *));
  134.     hf->boundsmin[0] = (float **)share_malloc(hf->lsize[0]*sizeof(float *));
  135.     /*
  136.      * Compute initial bounding boxes
  137.      */
  138.     for (i = 0; i < hf->lsize[0]; i++) {
  139.         hf->boundsmax[0][i]=(float *)share_malloc(hf->lsize[0]*sizeof(float));
  140.         hf->boundsmin[0][i]=(float *)share_malloc(hf->lsize[0]*sizeof(float));
  141.         maxptr = hf->boundsmax[0][i];
  142.         minptr = hf->boundsmin[0][i];
  143.         for (j = 0; j < hf->lsize[0]; j++) {
  144.             *maxptr++ = maxalt(i, j, hf->data) + EPSILON;
  145.             *minptr++ = minalt(i, j, hf->data) - EPSILON;
  146.         }
  147.     }
  148.  
  149.     for (i = 1; i < hf->levels; i++) {
  150.         hf->spacing[i] = hf->spacing[i-1] * hf->iBestSize;
  151.         hf->lsize[i] = (int)hf->spacing[i];
  152.         if ((Float)hf->lsize[i] != hf->spacing[i])
  153.             hf->lsize[i]++;
  154.         hf->boundsmax[i]=(float **)share_malloc(hf->lsize[i]*sizeof(float *));
  155.         hf->boundsmin[i]=(float **)share_malloc(hf->lsize[i]*sizeof(float *));
  156.         for (j = 0; j < hf->lsize[i]; j++) {
  157.             hf->boundsmax[i][j] = (float *)share_malloc(hf->lsize[i] *
  158.                             sizeof(float));
  159.             hf->boundsmin[i][j] = (float *)share_malloc(hf->lsize[i] *
  160.                             sizeof(float));
  161.         }
  162.         integrate_grid(hf, i);
  163.     }
  164.  
  165.     hf->boundbox[LOW][X] = hf->boundbox[LOW][Y] = 0;
  166.     hf->boundbox[HIGH][X] = hf->boundbox[HIGH][Y] = 1;
  167.     hf->boundbox[LOW][Z] = hf->minz;
  168.     hf->boundbox[HIGH][Z] = hf->maxz;
  169.  
  170.     return hf;
  171. }
  172.  
  173. Methods *
  174. HfMethods()
  175. {
  176.     if (iHfMethods == (Methods *)NULL) {
  177.         iHfMethods = MethodsCreate();
  178.         iHfMethods->create = (GeomCreateFunc *)HfCreate;
  179.         iHfMethods->methods = HfMethods;
  180.         iHfMethods->name = HfName;
  181.         iHfMethods->intersect = HfIntersect;
  182.         iHfMethods->normal = HfNormal;
  183.         iHfMethods->uv = HfUV;
  184.         iHfMethods->bounds = HfBounds;
  185.         iHfMethods->stats = HfStats;
  186.         iHfMethods->checkbounds = TRUE;
  187.         iHfMethods->closed = FALSE;
  188.     }
  189.     return iHfMethods;
  190. }
  191.  
  192. /*
  193.  * Intersect ray with height field.
  194.  */
  195. int
  196. HfIntersect(hf, ray, mindist, maxdist)
  197. Hf *hf;
  198. Ray *ray;
  199. Float mindist, *maxdist;
  200. {
  201.     Vector hitpos;
  202.     Float offset;
  203.     Trav2D trav;
  204.  
  205.     HFTests++;
  206.  
  207.     /*
  208.      * Find where we hit the hf cube.
  209.      */
  210.     VecAddScaled(ray->pos, mindist, ray->dir, &hitpos);
  211.     if (OutOfBounds(&hitpos, hf->boundbox)) {
  212.         offset = *maxdist;
  213.         if (!BoundsIntersect(ray, hf->boundbox, mindist, &offset))
  214.             return FALSE;
  215.         hitpos.x = ray->pos.x + ray->dir.x * offset;
  216.         hitpos.y = ray->pos.y + ray->dir.y * offset;
  217.         hitpos.z = ray->pos.z + ray->dir.z * offset;
  218.     } else
  219.         hitpos = ray->pos;
  220.     /*
  221.      * Find out in which cell "hitpoint" is.
  222.      */
  223.     if (equal(hitpos.x, 1.))
  224.         hitpos.x -= EPSILON;
  225.     if (equal(hitpos.y, 1.))
  226.         hitpos.y -= EPSILON;
  227.  
  228.     if (ray->dir.x < 0.) {
  229.         trav.stepX = trav.outX = -1;
  230.         trav.tDX = -1. / (ray->dir.x * hf->spacing[hf->levels -1]);
  231.     } else if (ray->dir.x > 0.) {
  232.         trav.stepX = 1;
  233.         trav.outX = hf->lsize[hf->levels -1];
  234.         /*
  235.          * (1./size) / ray
  236.          */
  237.         trav.tDX = 1. / (ray->dir.x * hf->spacing[hf->levels -1]);
  238.     }
  239.  
  240.     if (ray->dir.y < 0.) {
  241.         trav.stepY = trav.outY = -1;
  242.         trav.tDY = -1. / (ray->dir.y * hf->spacing[hf->levels -1]);
  243.     } else if (ray->dir.y > 0.) {
  244.         trav.stepY = 1;
  245.         trav.outY = hf->lsize[hf->levels -1];
  246.         trav.tDY = 1. / (ray->dir.y * hf->spacing[hf->levels -1]);
  247.     }
  248.  
  249.     trav.pDX.x = ray->dir.x * trav.tDX;
  250.     trav.pDX.y = ray->dir.y * trav.tDX;
  251.     trav.pDX.z = ray->dir.z * trav.tDX;
  252.     trav.pDY.x = ray->dir.x * trav.tDY;
  253.     trav.pDY.y = ray->dir.y * trav.tDY;
  254.     trav.pDY.z = ray->dir.z * trav.tDY;
  255.  
  256.     trav.cp = hitpos;
  257.     trav.minz = hf->minz;
  258.     trav.maxz = hf->maxz;
  259.     if (DDA2D(hf, &ray->pos, &ray->dir, hf->levels -1, &trav, maxdist)) {
  260.         HFHits++;
  261.         return TRUE;
  262.     }
  263.     return FALSE;
  264. }
  265.  
  266. /*
  267.  * Traverse the grid using a modified DDA algorithm.  If the extent of
  268.  * the ray over a cell intersects the bounding volume defined by the
  269.  * four corners of the cell, either recurse or perform ray/surface
  270.  * intersection test.
  271.  */
  272. static int
  273. DDA2D(hf, pos, ray, level, trav, maxdist)
  274. Hf *hf;
  275. Vector *pos, *ray;
  276. int level;
  277. Trav2D *trav;
  278. Float *maxdist;
  279. {
  280.     int x, y, size, posZ;
  281.     float **boundsmin, **boundsmax, spacing;
  282.     Float tX, tY;
  283.     Trav2D newtrav;
  284.     Vector nxp, nyp;
  285.  
  286.     size = hf->lsize[level];
  287.     spacing = hf->spacing[level];
  288.  
  289.     posZ = (ray->z > 0.);
  290.  
  291.     x = trav->cp.x * hf->spacing[level];
  292.     if (x == size)
  293.         x--;
  294.     y = trav->cp.y * hf->spacing[level];
  295.     if (y == size)
  296.         y--;
  297.     boundsmax = hf->boundsmax[level];
  298.     boundsmin = hf->boundsmin[level];
  299.  
  300.     if (trav->outX > size) trav->outX = size;
  301.     if (trav->outY > size) trav->outY = size;
  302.     if (trav->outX < 0) trav->outX = -1;
  303.     if (trav->outY < 0) trav->outY = -1;
  304.  
  305.     if (ray->x < 0.) {
  306.         tX = (x /spacing - trav->cp.x) / ray->x;
  307.     } else if (ray->x > 0.)
  308.         tX = ((x+1)/spacing - trav->cp.x) / ray->x;
  309.     else
  310.         tX = FAR_AWAY;
  311.     if (ray->y < 0.) {
  312.         tY = (y /spacing - trav->cp.y) / ray->y;
  313.     } else if (ray->y > 0.)
  314.         tY = ((y+1)/spacing - trav->cp.y) / ray->y;
  315.     else
  316.         tY = FAR_AWAY;
  317.  
  318.     nxp.x = trav->cp.x + tX * ray->x;
  319.     nxp.y = trav->cp.y + tX * ray->y;
  320.     nxp.z = trav->cp.z + tX * ray->z;
  321.  
  322.     nyp.x = trav->cp.x + tY * ray->x;
  323.     nyp.y = trav->cp.y + tY * ray->y;
  324.     nyp.z = trav->cp.z + tY * ray->z;
  325.  
  326.     do {
  327.         if (tX < tY) {
  328.             if ((posZ && trav->cp.z <= boundsmax[y][x] &&
  329.                  nxp.z >= boundsmin[y][x]) ||
  330.                 (!posZ && trav->cp.z >= boundsmin[y][x] &&
  331.                  nxp.z <= boundsmax[y][x])) {
  332.                 if (level) {
  333.                     /*
  334.                      * Recurse -- compute constants
  335.                      * needed for next level.
  336.                      * Nicely enough, this just
  337.                      * involves a few multiplications.
  338.                      */
  339.                     newtrav = *trav;
  340.                     newtrav.tDX *= hf->iBestSize;
  341.                     newtrav.tDY *= hf->iBestSize;
  342.                     newtrav.maxz = boundsmax[y][x];
  343.                     newtrav.minz = boundsmin[y][x];
  344.                     if (ray->x < 0.)
  345.                         newtrav.outX=hf->BestSize*x-1;
  346.                     else
  347.                         newtrav.outX=hf->BestSize*(x+1);
  348.                     if (ray->y < 0.)
  349.                         newtrav.outY=hf->BestSize*y-1;
  350.                     else
  351.                         newtrav.outY=hf->BestSize*(y+1);
  352.                     newtrav.pDX.x *= hf->iBestSize;
  353.                     newtrav.pDX.y *= hf->iBestSize;
  354.                     newtrav.pDX.z *= hf->iBestSize;
  355.                     newtrav.pDY.x *= hf->iBestSize;
  356.                     newtrav.pDY.y *= hf->iBestSize;
  357.                     newtrav.pDY.z *= hf->iBestSize;
  358.                     if (DDA2D(hf,pos,ray,level-1,
  359.                         &newtrav, maxdist))
  360.                         return TRUE;
  361.                 } else if (CheckCell(x,y,hf,ray,pos,maxdist))
  362.                     return TRUE;
  363.             }
  364.             x += trav->stepX;        /* Move in X */
  365.             if (*maxdist < tX || x == trav->outX)
  366.                 /* If outside, quit */
  367.                 return FALSE;
  368.             tX += trav->tDX;    /* Update position on ray */
  369.             trav->cp = nxp;        /* cur pos gets next pos */
  370.             nxp.x += trav->pDX.x;    /* Compute next pos */
  371.             nxp.y += trav->pDX.y;
  372.             nxp.z += trav->pDX.z;
  373.         } else {
  374.             if ((posZ && trav->cp.z <= boundsmax[y][x] &&
  375.                  nyp.z >= boundsmin[y][x]) ||
  376.                 (!posZ && trav->cp.z >= boundsmin[y][x] &&
  377.                  nyp.z <= boundsmax[y][x])) {
  378.                 if (level) {
  379.                     /* Recurse */
  380.                     newtrav = *trav;
  381.                     newtrav.tDX *= hf->iBestSize;
  382.                     newtrav.tDY *= hf->iBestSize;
  383.                     newtrav.maxz = boundsmax[y][x];
  384.                     newtrav.minz = boundsmin[y][x];
  385.                     if (ray->x < 0.)
  386.                         newtrav.outX=hf->BestSize*x-1;
  387.                     else
  388.                         newtrav.outX=hf->BestSize*(x+1);
  389.                     if (ray->y < 0.)
  390.                         newtrav.outY=hf->BestSize*y-1;
  391.                     else
  392.                         newtrav.outY=hf->BestSize*(y+1);
  393.                     newtrav.pDX.x *= hf->iBestSize;
  394.                     newtrav.pDX.y *= hf->iBestSize;
  395.                     newtrav.pDX.z *= hf->iBestSize;
  396.                     newtrav.pDY.x *= hf->iBestSize;
  397.                     newtrav.pDY.y *= hf->iBestSize;
  398.                     newtrav.pDY.z *= hf->iBestSize;
  399.                     if (DDA2D(hf,pos,ray,level-1,
  400.                             &newtrav, maxdist))
  401.                         return TRUE;
  402.                 } else if (CheckCell(x,y,hf,ray,pos,maxdist))
  403.                     return TRUE;
  404.             }
  405.             y += trav->stepY;
  406.             if (*maxdist < tY || y == trav->outY)
  407.                 return FALSE;
  408.             tY += trav->tDY;
  409.             trav->cp = nyp;
  410.             nyp.x += trav->pDY.x;
  411.             nyp.y += trav->pDY.y;
  412.             nyp.z += trav->pDY.z;
  413.         }
  414.     } while ((trav->cp.x <= 1. && trav->cp.y <= 1.) &&
  415.          ((posZ && trav->cp.z <= trav->maxz) ||
  416.          (!posZ && trav->cp.z >= trav->minz)));
  417.  
  418.         /*
  419.          * while ((we're inside the horizontal bounding box)
  420.          *        (usually caught by outX & outY, but
  421.          *         it's possible to go "too far" due to
  422.          *         the fact that our levels of grids do
  423.          *         not "nest" exactly if gridsize%BestSize != 0)
  424.          *      and
  425.          *      ((if ray->z is positive and we haven't gone through
  426.          *       the upper bounding plane) or
  427.          *      (if ray->z is negative and we haven't gone through
  428.          *       the lower bounding plane)));
  429.          */
  430.  
  431.     return FALSE;
  432. }
  433.  
  434. /*
  435.  * Check for ray/cell intersection
  436.  */
  437. static int
  438. CheckCell(x, y, hf, ray, pos, maxdist)
  439. int x, y;
  440. Hf *hf;
  441. Vector *ray, *pos;
  442. Float *maxdist;
  443. {
  444.     hfTri *tri1, *tri2;
  445.     Float d1, d2;
  446.  
  447.     d1 = d2 = FAR_AWAY;
  448.  
  449.     if (tri1 = CreateHfTriangle(hf, x, y, x+1, y, x, y+1, TRI1))
  450.         d1 = intHftri(ray, pos, tri1);
  451.     if (tri2 = CreateHfTriangle(hf, x+1, y, x+1, y+1, x, y+1, TRI2))
  452.         d2 = intHftri(ray, pos, tri2);
  453.  
  454.     if (d1 == FAR_AWAY && d2 == FAR_AWAY)
  455.         return FALSE;
  456.  
  457.     if (d1 < d2) {
  458.         if (d1 < *maxdist) {
  459.             hf->hittri = *tri1;
  460.             *maxdist = d1;
  461.             return TRUE;
  462.         }
  463.         return FALSE;
  464.     }
  465.  
  466.     if (d2 < *maxdist) {
  467.         hf->hittri = *tri2;
  468.         *maxdist = d2;
  469.         return TRUE;
  470.     }
  471.     return FALSE;
  472. }
  473.  
  474. static hfTri *
  475. CreateHfTriangle(hf, x1, y1, x2, y2, x3, y3, which)
  476. Hf *hf;
  477. int x1, y1, x2, y2, x3, y3, which;
  478. {
  479.     hfTri *tri;
  480.     Float xid, yid;
  481.     Vector tmp1, tmp2;
  482.  
  483.     /*
  484.      * Don't use triangles with "unset" vertices.
  485.      */
  486.     if (hf->data[y1][x1] == HF_UNSET ||
  487.         hf->data[y2][x2] == HF_UNSET ||
  488.         hf->data[y3][x3] == HF_UNSET)
  489.         return (hfTri *)0;
  490.  
  491.     xid = (Float)x1 / (Float)(hf->size -1);
  492.     yid = (Float)y1 / (Float)(hf->size -1);
  493.  
  494.     if ((tri = GetQueuedTri(hf, xid, yid, which)) != (hfTri *)0)
  495.         return tri;
  496.  
  497.     tri = (hfTri *)RayMalloc(sizeof(hfTri));
  498.  
  499.     tri->type = which;
  500.     tri->v1.x = xid;
  501.     tri->v1.y = yid;
  502.     tri->v1.z = hf->data[y1][x1];
  503.     tri->v2.x = (Float)x2 / (Float)(hf->size-1);
  504.     tri->v2.y = (Float)y2 / (Float)(hf->size-1);
  505.     tri->v2.z = hf->data[y2][x2];
  506.     tri->v3.x = (Float)x3 / (Float)(hf->size-1);
  507.     tri->v3.y = (Float)y3 / (Float)(hf->size-1);
  508.     tri->v3.z = hf->data[y3][x3];
  509.  
  510.     tmp1.x = tri->v2.x - tri->v1.x;
  511.     tmp1.y = tri->v2.y - tri->v1.y;
  512.     tmp1.z = tri->v2.z - tri->v1.z;
  513.     tmp2.x = tri->v3.x - tri->v1.x;
  514.     tmp2.y = tri->v3.y - tri->v1.y;
  515.     tmp2.z = tri->v3.z - tri->v1.z;
  516.  
  517.     (void)VecNormCross(&tmp1, &tmp2, &tri->norm);
  518.  
  519.     tri->d = -dotp(&tri->v1, &tri->norm);
  520.  
  521.     QueueTri(hf, tri);
  522.     return tri;
  523. }
  524.  
  525. /*
  526.  * Intersect ray with right isoscoles triangle, the hypotenuse of which
  527.  * has slope of -1.
  528.  */
  529. static Float
  530. intHftri(ray, pos, tri)
  531. hfTri *tri;
  532. Vector *pos, *ray;
  533. {
  534.     Float u, v, dist, xpos, ypos;
  535.  
  536.     u = dotp(&tri->norm, pos) + tri->d;
  537.     v = dotp(&tri->norm, ray);
  538.  
  539.     if ((u <= 0. || v > -EPSILON) && (u >= 0. && v < EPSILON))
  540.         return FAR_AWAY;
  541.  
  542.     dist = -u / v;
  543.  
  544.     if (dist < EPSILON)
  545.         return FAR_AWAY;
  546.  
  547.     xpos = pos->x + dist*ray->x;
  548.     ypos = pos->y + dist*ray->y;
  549.  
  550.     if (tri->type == TRI1 && xpos >= tri->v1.x && ypos >= tri->v1.y &&
  551.         xpos + ypos <= tri->v2.x + tri->v2.y)
  552.         return dist;
  553.     if (tri->type == TRI2 && xpos <= tri->v2.x && ypos <= tri->v2.y &&
  554.         xpos + ypos >= tri->v1.x + tri->v1.y)
  555.         return dist;
  556.     return FAR_AWAY;
  557. }
  558.  
  559. /*
  560.  * Compute normal to height field.
  561.  */
  562. /*ARGSUSED*/
  563. int
  564. HfNormal(hf, pos, nrm, gnrm)
  565. Hf *hf;
  566. Vector *pos, *nrm, *gnrm;
  567. {
  568.     *gnrm = *nrm = hf->hittri.norm;
  569.     return FALSE;
  570. }
  571.  
  572. /*ARGSUSED*/
  573. void
  574. HfUV(hf, pos, norm, uv, dpdu, dpdv)
  575. Hf *hf;
  576. Vector *pos, *norm, *dpdu, *dpdv;
  577. Vec2d *uv;
  578. {
  579.     uv->u = pos->x;
  580.     uv->v = pos->y;
  581.     if (dpdu) {
  582.         dpdu->x = 1.;
  583.         dpdu->y = dpdv->z = 0.;
  584.         dpdv->x = dpdv->z = 0.;
  585.         dpdv->y = 1.;
  586.     }
  587. }
  588.  
  589. /*
  590.  * Compute heightfield bounding box.
  591.  */
  592. void
  593. HfBounds(hf, bounds)
  594. Hf *hf;
  595. Float bounds[2][3];
  596. {
  597.     /*
  598.      * By default, height fields are centered at (0.5, 0.5, 0.)
  599.      */
  600.     bounds[LOW][X] = bounds[LOW][Y] = 0;
  601.     bounds[HIGH][X] = bounds[HIGH][Y] = 1;
  602.     bounds[LOW][Z] = hf->minz;
  603.     bounds[HIGH][Z] = hf->maxz;
  604. }
  605.  
  606. /*
  607.  * Build min/max altitude value arrays for the given grid level.
  608.  */
  609. static void
  610. integrate_grid(hf, level)
  611. Hf *hf;
  612. int level;
  613. {
  614.     int i, j, k, l, ii, ji;
  615.     float max_alt, min_alt;
  616.     float **maxinto, **mininto, **frommax, **frommin, *minptr, *maxptr;
  617.     int insize, fromsize, fact;
  618.  
  619.     maxinto = hf->boundsmax[level];
  620.     mininto = hf->boundsmin[level];
  621.     insize = hf->lsize[level];
  622.     frommax = hf->boundsmax[level-1];
  623.     frommin = hf->boundsmin[level-1];
  624.     fact = hf->BestSize;
  625.     fromsize = hf->lsize[level-1];
  626.  
  627.     ii = 0;
  628.  
  629.     for (i = 0; i < insize; i++) {
  630.         ji = 0;
  631.         for (j = 0; j < insize; j++) {
  632.             max_alt = HF_UNSET;
  633.             min_alt = -HF_UNSET;
  634.             for (k = 0; k <= fact; k++) {
  635.                 if (ii+k >= fromsize)
  636.                     continue;
  637.                 maxptr = &frommax[ii+k][ji];
  638.                 minptr = &frommin[ii+k][ji];
  639.                 for (l = 0; l <= fact; l++,maxptr++,minptr++) {
  640.                     if (ji+l >= fromsize)
  641.                         continue;
  642.                     if (*maxptr > max_alt)
  643.                         max_alt = *maxptr;
  644.                     if (*minptr < min_alt)
  645.                         min_alt = *minptr;
  646.                 }
  647.             }
  648.             maxinto[i][j] = max_alt + EPSILON;
  649.             mininto[i][j] = min_alt - EPSILON;
  650.             ji += fact;
  651.         }
  652.         ii += fact;
  653.     }
  654. }
  655.  
  656. /*
  657.  * Place the given triangle in the triangle cache.
  658.  */
  659. static void
  660. QueueTri(hf, tri)
  661. Hf *hf;
  662. hfTri *tri;
  663. {
  664.     if (hf->q[hf->qtail])        /* Free old triangle data */
  665.         free((voidstar)hf->q[hf->qtail]);
  666.     hf->q[hf->qtail] = tri;        /* Put on tail */
  667.     hf->qtail = (hf->qtail + 1) % hf->qsize;    /* Increment tail */
  668. }
  669.  
  670. /*
  671.  * Search list of cached trianges to see if this triangle has been
  672.  * cached.  If so, return a pointer to it.  If not, return null pointer.
  673.  */
  674. static hfTri *
  675. GetQueuedTri(hf, x, y, flag)
  676. Hf *hf;
  677. Float x, y;
  678. int flag;
  679. {
  680.     register int i;
  681.     register hfTri **tmp;
  682.  
  683.     for (i = 0, tmp = hf->q; i < hf->qsize; i++, tmp++) {
  684.         if (*tmp && (*tmp)->v1.x == x && (*tmp)->v1.y == y &&
  685.             (*tmp)->type == flag)
  686.             return *tmp;    /* vertices & flag match, return it */
  687.     }
  688.  
  689.     return (hfTri *)0;
  690. }
  691.  
  692. /*
  693.  * Return maximum height of cell indexed by y,x.  This could be done
  694.  * as a macro, but many C compliers will choke on it.
  695.  */
  696. static float
  697. minalt(y,x,data)
  698. int x, y;
  699. float **data;
  700. {
  701.     float  min_alt;
  702.  
  703.     min_alt = min(data[y][x], data[y+1][x]);
  704.     min_alt = min(min_alt, data[y][x+1]);
  705.     min_alt = min(min_alt, data[y+1][x+1]);
  706.     return min_alt;
  707. }
  708.  
  709. /*
  710.  * Return maximum cell height, as above.
  711.  */
  712. static float
  713. maxalt(y,x,data)
  714. int x, y;
  715. float **data;
  716. {
  717.     float  max_alt;
  718.  
  719.     max_alt = max(data[y][x], data[y+1][x]);
  720.     max_alt = max(max_alt, data[y][x+1]);
  721.     max_alt = max(max_alt, data[y+1][x+1]);
  722.     return max_alt;
  723. }
  724.  
  725. char *
  726. HfName()
  727. {
  728.     return hfName;
  729. }
  730.  
  731. void
  732. HfStats(tests, hits)
  733. unsigned long *tests, *hits;
  734. {
  735.     *tests = HFTests;
  736.     *hits = HFHits;
  737. }
  738.  
  739. void
  740. HfMethodRegister(meth)
  741. UserMethodType meth;
  742. {
  743.     if (iHfMethods)
  744.         iHfMethods->user = meth;
  745. }
  746.