grid.cpp

英特尔&#174 线程构建模块（英特尔&#174 TBB）是一个屡获殊荣的 C++ 运行时库

  if (*list == NULL)
    return 0;

  numobj =  cellbound(gold, index, &gmin, &gmax);

  VSub(&gmax, &gmin, &gsize);
  len = 1.0 / (MYMAX( MYMAX(gsize.x, gsize.y), gsize.z ));
  gsize.x *= len;  
  gsize.y *= len;  
  gsize.z *= len;  

  if (numobj > 16) {
    numcbrt = (int) cbrt(2*numobj); 
    
    xs = (int) ((flt) numcbrt * gsize.x);
    if (xs < 1) xs = 1;
    ys = (int) ((flt) numcbrt * gsize.y);
    if (ys < 1) ys = 1;
    zs = (int) ((flt) numcbrt * gsize.z);
    if (zs < 1) zs = 1;

    g = (grid *) newgrid(xs, ys, zs, gmin, gmax);
    engrid_objectlist(g, list);

    newobj = (objectlist *) rt_getmem(sizeof(objectlist));    
    newobj->obj = (object *) g;
    newobj->next = *list;
    *list = newobj;

    g->nextobj = gold->objects;
    gold->objects = (object *) g;
  }

  return 1;
}

static int engrid_objectlist(grid * g, objectlist ** list) {
  objectlist * cur, * next, **prev;
  int numsucceeded = 0; 

  if (*list == NULL) 
    return 0;
  
  prev = list; 
  cur = *list;

  while (cur != NULL) {
    next = cur->next;

    if (engrid_object(g, cur->obj)) {
      *prev = next;
      free(cur);
      numsucceeded++;
    }
    else {
      prev = &cur->next;
    }

    cur = next;
  } 

  return numsucceeded;
}



static int engrid_object(grid * g, object * obj) {
  vector omin, omax; 
  gridindex low, high;
  int x, y, z, zindex, yindex, voxindex;
  objectlist * tmp;
 
  if (obj->methods->bbox(obj, &omin, &omax)) { 
    if (!pos2grid(g, &omin, &low) || !pos2grid(g, &omax, &high)) {
      return 0; /* object is not wholly contained in the grid */
    }
  }
  else {
    return 0; /* object is unbounded */
  }

  /* add the object to the complete list of objects in the grid */
  obj->nextobj = g->objects;
  g->objects = obj;

  /* add this object to all voxels it inhabits */
  for (z=low.z; z<=high.z; z++) {
    zindex = z * g->xsize * g->ysize;
    for (y=low.y; y<=high.y; y++) {
      yindex = y * g->xsize;
      for (x=low.x; x<=high.x; x++) {
        voxindex = x + yindex + zindex; 
        tmp = (objectlist *) rt_getmem(sizeof(objectlist));
        tmp->next = g->cells[voxindex];
        tmp->obj = obj;
        g->cells[voxindex] = tmp;
      }
    }
  }
 
  return 1;
}

static int pos2grid(grid * g, vector * pos, gridindex * index) {
  index->x = (int) ((pos->x - g->min.x) / g->voxsize.x);
  index->y = (int) ((pos->y - g->min.y) / g->voxsize.y);
  index->z = (int) ((pos->z - g->min.z) / g->voxsize.z);
  
  if (index->x == g->xsize)
    index->x--;
  if (index->y == g->ysize)
    index->y--;
  if (index->z == g->zsize)
    index->z--;

  if (index->x < 0 || index->x > g->xsize ||
      index->y < 0 || index->y > g->ysize ||
      index->z < 0 || index->z > g->zsize) 
    return 0;

  if (pos->x < g->min.x || pos->x > g->max.x ||
      pos->y < g->min.y || pos->y > g->max.y ||
      pos->z < g->min.z || pos->z > g->max.z) 
    return 0; 

  return 1;
}


/* the real thing */
static void grid_intersect(grid * g, ray * ry) {
  flt tnear, tfar, offset;
  vector curpos, tmax, tdelta, pdeltaX, pdeltaY, pdeltaZ, nXp, nYp, nZp;
  gridindex curvox, step, out; 
  int voxindex;
  objectlist * cur;

  if (ry->flags & RT_RAY_FINISHED)
    return;

  if (!grid_bounds_intersect(g, ry, &tnear, &tfar))
    return;
 
  if (ry->maxdist < tnear)
    return;
 
  curpos = Raypnt(ry, tnear); 
  pos2grid(g, &curpos, &curvox);
  offset = tnear;

  /* Setup X iterator stuff */
  if (fabs(ry->d.x) < EPSILON) {
    tmax.x = FHUGE;
    tdelta.x = 0.0;
    step.x = 0;
    out.x = 0; /* never goes out of bounds on this axis */
  }
  else if (ry->d.x < 0.0) {
    tmax.x = offset + ((voxel2x(g, curvox.x) - curpos.x) / ry->d.x); 
    tdelta.x = g->voxsize.x / - ry->d.x;
    step.x = out.x = -1;
  }
  else {
    tmax.x = offset + ((voxel2x(g, curvox.x + 1) - curpos.x) / ry->d.x);
    tdelta.x = g->voxsize.x / ry->d.x;
    step.x = 1;
    out.x = g->xsize;
  }

  /* Setup Y iterator stuff */
  if (fabs(ry->d.y) < EPSILON) {
    tmax.y = FHUGE;
    tdelta.y = 0.0; 
    step.y = 0;
    out.y = 0; /* never goes out of bounds on this axis */
  }
  else if (ry->d.y < 0.0) {
    tmax.y = offset + ((voxel2y(g, curvox.y) - curpos.y) / ry->d.y);
    tdelta.y = g->voxsize.y / - ry->d.y;
    step.y = out.y = -1;
  }
  else {
    tmax.y = offset + ((voxel2y(g, curvox.y + 1) - curpos.y) / ry->d.y);
    tdelta.y = g->voxsize.y / ry->d.y;
    step.y = 1;
    out.y = g->ysize;
  }

  /* Setup Z iterator stuff */
  if (fabs(ry->d.z) < EPSILON) {
    tmax.z = FHUGE;
    tdelta.z = 0.0; 
    step.z = 0;
    out.z = 0; /* never goes out of bounds on this axis */
  }
  else if (ry->d.z < 0.0) {
    tmax.z = offset + ((voxel2z(g, curvox.z) - curpos.z) / ry->d.z);
    tdelta.z = g->voxsize.z / - ry->d.z;
    step.z = out.z = -1;
  }
  else {
    tmax.z = offset + ((voxel2z(g, curvox.z + 1) - curpos.z) / ry->d.z);
    tdelta.z = g->voxsize.z / ry->d.z;
    step.z = 1;
    out.z = g->zsize;
  }

  pdeltaX = ry->d;
  VScale(&pdeltaX, tdelta.x);
  pdeltaY = ry->d;
  VScale(&pdeltaY, tdelta.y);
  pdeltaZ = ry->d;
  VScale(&pdeltaZ, tdelta.z);

  nXp = Raypnt(ry, tmax.x);
  nYp = Raypnt(ry, tmax.y);
  nZp = Raypnt(ry, tmax.z);

  voxindex = curvox.z*g->xsize*g->ysize + curvox.y*g->xsize + curvox.x; 
  while (1) {
    if (tmax.x < tmax.y && tmax.x < tmax.z) {
      cur = g->cells[voxindex];
      while (cur != NULL) {
        if (ry->mbox[cur->obj->id] != ry->serial) {
          ry->mbox[cur->obj->id] = ry->serial; 
          cur->obj->methods->intersect(cur->obj, ry);
        }
        cur = cur->next;
      }
      curvox.x += step.x;
      if (ry->maxdist < tmax.x || curvox.x == out.x) 
        break; 
      voxindex += step.x;
      tmax.x += tdelta.x;
      curpos = nXp;
      nXp.x += pdeltaX.x;
      nXp.y += pdeltaX.y;
      nXp.z += pdeltaX.z;
    }
    else if (tmax.z < tmax.y) {
      cur = g->cells[voxindex];
      while (cur != NULL) {
        if (ry->mbox[cur->obj->id] != ry->serial) {
          ry->mbox[cur->obj->id] = ry->serial; 
          cur->obj->methods->intersect(cur->obj, ry);
        }
        cur = cur->next;
      }
      curvox.z += step.z;
      if (ry->maxdist < tmax.z || curvox.z == out.z) 
        break;
      voxindex += step.z*g->xsize*g->ysize;
      tmax.z += tdelta.z;
      curpos = nZp;
      nZp.x += pdeltaZ.x;
      nZp.y += pdeltaZ.y;
      nZp.z += pdeltaZ.z;
    }
    else {
      cur = g->cells[voxindex];
      while (cur != NULL) {
        if (ry->mbox[cur->obj->id] != ry->serial) {
          ry->mbox[cur->obj->id] = ry->serial; 
          cur->obj->methods->intersect(cur->obj, ry);
        }
        cur = cur->next;
      }
      curvox.y += step.y;
      if (ry->maxdist < tmax.y || curvox.y == out.y) 
        break;
      voxindex += step.y*g->xsize;
      tmax.y += tdelta.y;
      curpos = nYp;
      nYp.x += pdeltaY.x;
      nYp.y += pdeltaY.y;
      nYp.z += pdeltaY.z;
    }

    if (ry->flags & RT_RAY_FINISHED)
      break;
  }
}

static void voxel_intersect(grid * g, ray * ry, int voxindex) {
  objectlist * cur;

  cur = g->cells[voxindex];
  while (cur != NULL) {
    cur->obj->methods->intersect(cur->obj, ry);
    cur = cur->next;
  }
}

static int grid_bounds_intersect(grid * g, ray * ry, flt *near, flt *far) {
  flt a, tx1, tx2, ty1, ty2, tz1, tz2;
  flt tnear, tfar;

  tnear= -FHUGE;
  tfar= FHUGE;

  if (ry->d.x == 0.0) {
    if ((ry->o.x < g->min.x) || (ry->o.x > g->max.x)) return 0;
  }
  else {
    tx1 = (g->min.x - ry->o.x) / ry->d.x;
    tx2 = (g->max.x - ry->o.x) / ry->d.x;
    if (tx1 > tx2) { a=tx1; tx1=tx2; tx2=a; }
    if (tx1 > tnear) tnear=tx1;
    if (tx2 < tfar)   tfar=tx2;
  }
  if (tnear > tfar) return 0;
  if (tfar < 0.0) return 0;

  if (ry->d.y == 0.0) {
    if ((ry->o.y < g->min.y) || (ry->o.y > g->max.y)) return 0;
  }
  else {
    ty1 = (g->min.y - ry->o.y) / ry->d.y;
    ty2 = (g->max.y - ry->o.y) / ry->d.y;
    if (ty1 > ty2) { a=ty1; ty1=ty2; ty2=a; }
    if (ty1 > tnear) tnear=ty1;
    if (ty2 < tfar)   tfar=ty2;
  }
  if (tnear > tfar) return 0;
  if (tfar < 0.0) return 0;

  if (ry->d.z == 0.0) {
    if ((ry->o.z < g->min.z) || (ry->o.z > g->max.z)) return 0;
  }
  else {
    tz1 = (g->min.z - ry->o.z) / ry->d.z;
    tz2 = (g->max.z - ry->o.z) / ry->d.z;
    if (tz1 > tz2) { a=tz1; tz1=tz2; tz2=a; }
    if (tz1 > tnear) tnear=tz1;
    if (tz2 < tfar)   tfar=tz2;
  }
  if (tnear > tfar) return 0;
  if (tfar < 0.0) return 0;

  *near = tnear;
  *far = tfar; 
  return 1;
}