77     grid *g;  in newgrid()  local
79     g = (grid *)rt_getmem(sizeof(grid));  in newgrid()
80     memset(g, 0, sizeof(grid));  in newgrid()
82     g->methods = &grid_methods;  in newgrid()
83     g->id = new_objectid();  in newgrid()
85     g->xsize = xsize;  in newgrid()
86     g->ysize = ysize;  in newgrid()
87     g->zsize = zsize;  in newgrid()
89     g->min = min;  in newgrid()
90     g->max = max;  in newgrid()
92     VSub(&g->max, &g->min, &g->voxsize);  in newgrid()
93     g->voxsize.x /= (flt)g->xsize;  in newgrid()
94     g->voxsize.y /= (flt)g->ysize;  in newgrid()
95     g->voxsize.z /= (flt)g->zsize;  in newgrid()
97     g->cells = (objectlist **)rt_getmem(xsize * ysize * zsize * sizeof(objectlist *));  in newgrid()
98     memset(g->cells, 0, xsize * ysize * zsize * sizeof(objectlist *));  in newgrid()
102     return (object *)g;  in newgrid()
106     grid *g = (grid *)obj;  in grid_bbox()  local
108     *min = g->min;  in grid_bbox()
109     *max = g->max;  in grid_bbox()
116     grid *g = (grid *)v;  in grid_free()  local
119     numvoxels = g->xsize * g->ysize * g->zsize;  in grid_free()
123         lcur = g->cells[i];  in grid_free()
131     free(g->cells);  in grid_free()
134     free_objects(g->objects);  in grid_free()
136     free(g);  in grid_free()
176 static int cellbound(grid *g, gridindex *index, vector *cmin, vector *cmax) {  in cellbound()  argument
181     cur = g->cells[index->z * g->xsize * g->ysize + index->y * g->xsize + index->x];  in cellbound()
186     cellmin.x = voxel2x(g, index->x);  in cellbound()
187     cellmin.y = voxel2y(g, index->y);  in cellbound()
188     cellmin.z = voxel2z(g, index->z);  in cellbound()
190     cellmax.x = cellmin.x + g->voxsize.x;  in cellbound()
191     cellmax.y = cellmin.y + g->voxsize.y;  in cellbound()
192     cellmax.z = cellmin.z + g->voxsize.z;  in cellbound()
274     grid *g;  in engrid_scene()  local
291         g = (grid *)newgrid(numcbrt, numcbrt, numcbrt, gmin, gmax);  in engrid_scene()
292         engrid_objlist(g, list);  in engrid_scene()
295         g->nextobj = *list;  in engrid_scene()
296         *list = (object *)g;  in engrid_scene()
299         for (index.z = 0; index.z < g->zsize; index.z++) {  in engrid_scene()
300             for (index.y = 0; index.y < g->ysize; index.y++) {  in engrid_scene()
301                 for (index.x = 0; index.x < g->xsize; index.x++) {  in engrid_scene()
302                     engrid_cell(g, &index);  in engrid_scene()
311 void engrid_objlist(grid *g, object **list) {  in engrid_objlist()  argument
323         if (engrid_object(g, cur))  in engrid_objlist()
336     grid *g;  in engrid_cell()  local
366         g = (grid *)newgrid(xs, ys, zs, gmin, gmax);  in engrid_cell()
367         engrid_objectlist(g, list);  in engrid_cell()
370         newobj->obj = (object *)g;  in engrid_cell()
374         g->nextobj = gold->objects;  in engrid_cell()
375         gold->objects = (object *)g;  in engrid_cell()
381 static int engrid_objectlist(grid *g, objectlist **list) {  in engrid_objectlist()  argument
394         if (engrid_object(g, cur->obj)) {  in engrid_objectlist()
409 static int engrid_object(grid *g, object *obj) {  in engrid_object()  argument
416         if (!pos2grid(g, &omin, &low) || !pos2grid(g, &omax, &high)) {  in engrid_object()
425     obj->nextobj = g->objects;  in engrid_object()
426     g->objects = obj;  in engrid_object()
430         zindex = z * g->xsize * g->ysize;  in engrid_object()
432             yindex = y * g->xsize;  in engrid_object()
436                 tmp->next = g->cells[voxindex];  in engrid_object()
438                 g->cells[voxindex] = tmp;  in engrid_object()
446 static int pos2grid(grid *g, vector *pos, gridindex *index) {  in pos2grid()  argument
447     index->x = (int)((pos->x - g->min.x) / g->voxsize.x);  in pos2grid()
448     index->y = (int)((pos->y - g->min.y) / g->voxsize.y);  in pos2grid()
449     index->z = (int)((pos->z - g->min.z) / g->voxsize.z);  in pos2grid()
451     if (index->x == g->xsize)  in pos2grid()
453     if (index->y == g->ysize)  in pos2grid()
455     if (index->z == g->zsize)  in pos2grid()
458     if (index->x < 0 || index->x > g->xsize || index->y < 0 || index->y > g->ysize ||  in pos2grid()
459         index->z < 0 || index->z > g->zsize)  in pos2grid()
462     if (pos->x < g->min.x || pos->x > g->max.x || pos->y < g->min.y || pos->y > g->max.y ||  in pos2grid()
463         pos->z < g->min.z || pos->z > g->max.z)  in pos2grid()
470 static void grid_intersect(grid *g, ray *ry) {  in grid_intersect()  argument
480     if (!grid_bounds_intersect(g, ry, &tnear, &tfar))  in grid_intersect()
487     pos2grid(g, &curpos, &curvox);  in grid_intersect()
498         tmax.x = offset + ((voxel2x(g, curvox.x) - curpos.x) / ry->d.x);  in grid_intersect()
499         tdelta.x = g->voxsize.x / -ry->d.x;  in grid_intersect()
503         tmax.x = offset + ((voxel2x(g, curvox.x + 1) - curpos.x) / ry->d.x);  in grid_intersect()
504         tdelta.x = g->voxsize.x / ry->d.x;  in grid_intersect()
506         out.x = g->xsize;  in grid_intersect()
517         tmax.y = offset + ((voxel2y(g, curvox.y) - curpos.y) / ry->d.y);  in grid_intersect()
518         tdelta.y = g->voxsize.y / -ry->d.y;  in grid_intersect()
522         tmax.y = offset + ((voxel2y(g, curvox.y + 1) - curpos.y) / ry->d.y);  in grid_intersect()
523         tdelta.y = g->voxsize.y / ry->d.y;  in grid_intersect()
525         out.y = g->ysize;  in grid_intersect()
536         tmax.z = offset + ((voxel2z(g, curvox.z) - curpos.z) / ry->d.z);  in grid_intersect()
537         tdelta.z = g->voxsize.z / -ry->d.z;  in grid_intersect()
541         tmax.z = offset + ((voxel2z(g, curvox.z + 1) - curpos.z) / ry->d.z);  in grid_intersect()
542         tdelta.z = g->voxsize.z / ry->d.z;  in grid_intersect()
544         out.z = g->zsize;  in grid_intersect()
558     voxindex = curvox.z * g->xsize * g->ysize + curvox.y * g->xsize + curvox.x;  in grid_intersect()
561             cur = g->cells[voxindex];  in grid_intersect()
580             cur = g->cells[voxindex];  in grid_intersect()
591             voxindex += step.z * g->xsize * g->ysize;  in grid_intersect()
599             cur = g->cells[voxindex];  in grid_intersect()
610             voxindex += step.y * g->xsize;  in grid_intersect()
623 static void voxel_intersect(grid *g, ray *ry, int voxindex) {  in voxel_intersect()  argument
626     cur = g->cells[voxindex];  in voxel_intersect()
633 static int grid_bounds_intersect(grid *g, ray *ry, flt *nr, flt *fr) {  in grid_bounds_intersect()  argument
641         if ((ry->o.x < g->min.x) || (ry->o.x > g->max.x))  in grid_bounds_intersect()
645         tx1 = (g->min.x - ry->o.x) / ry->d.x;  in grid_bounds_intersect()
646         tx2 = (g->max.x - ry->o.x) / ry->d.x;  in grid_bounds_intersect()
663         if ((ry->o.y < g->min.y) || (ry->o.y > g->max.y))  in grid_bounds_intersect()
667         ty1 = (g->min.y - ry->o.y) / ry->d.y;  in grid_bounds_intersect()
668         ty2 = (g->max.y - ry->o.y) / ry->d.y;  in grid_bounds_intersect()
685         if ((ry->o.z < g->min.z) || (ry->o.z > g->max.z))  in grid_bounds_intersect()
689         tz1 = (g->min.z - ry->o.z) / ry->d.z;  in grid_bounds_intersect()
690         tz2 = (g->max.z - ry->o.z) / ry->d.z;  in grid_bounds_intersect()