rtsi.com/2014.01.www.rtsi.com.tar/www.rtsi.com/OS9/OSK/GRAPHICS/rayshade.lzh/voxels.c

Text File | 1990-05-08 | 5KB | 219 lines

/*
 * voxels.c
 *
 * Copyright (C) 1989, Craig E. Kolb
 *
 * This software may be freely copied, modified, and redistributed,
 * provided that this copyright notice is preserved on all copies.
 *
 * There is no warranty or other guarantee of fitness for this software,
 * it is provided solely .  Bug reports or fixes may be sent
 * to the author, who may or may not act on them as he desires.
 *
 * You may not include this software in a program or other software product
 * without supplying the source, or without informing the end-user that the
 * source is available for no extra charge.
 *
 * If you modify this software, you should include a notice giving the
 * name of the person performing the modification, the date of modification,
 * and the reason for such modification.
 *
 * $Id: voxels.c,v 3.0.1.3 90/04/04 19:05:23 craig Exp $
 *
 * $Log:    voxels.c,v $
 * Revision 3.0.1.3  90/04/04  19:05:23  craig
 * patch5: Changes to reflect that free() may be destructive.
 *
 * Revision 3.0.1.2  90/02/12  13:19:50  craig
 * patch4: Added reporting of total number of primitives.
 *
 * Revision 3.0.1.1  89/12/06  16:33:29  craig
 * patch2: Added calls to new error/warning routines.
 *
 * Revision 3.0  89/10/27  02:06:09  craig
 * Baseline for first official release.
 *
 */
#include <math.h>
#include <stdio.h>
#include "constants.h"
#include "typedefs.h"
#include "funcdefs.h"

/*
 * Process World object, converting to a Grid or List.
 */
SetupWorld()
{
    extern FILE *fstats;
    extern Object *World;
    extern int WorldXSize, WorldYSize, WorldZSize, Verbose;

    if (World->type == GRID)
        list2grid(World, WorldXSize, WorldYSize, WorldZSize);
    else
        make_list(World);

    if (Verbose) {
        fprintf(fstats,"World extent:\n");
        print_bounds(World->bounds);
        fprintf(fstats,"\t%ld primitive%c\n",World->prims,
                World->prims == 1 ? ' ' : 's');
    }
}

/*
 * Add object to grid's unbounded list.
 */
make_unbounded(obj, grid)
Object *obj;
Grid *grid;
{
    ObjList *tmp;

    tmp = (ObjList *)Malloc(sizeof(ObjList));

    tmp->data = obj;
    tmp->next = grid->unbounded;
    grid->unbounded = tmp;
}

/*
 * Place an object in a grid.
 */
engrid(obj, grid)
Object *obj;
Grid *grid;
{
    int x, y, z, low[3], high[3];
    ObjList *ltmp;

    /*
     * This routine should *never* be passed an unbounded object, but...
     */
    if (pos2grid(grid, obj->bounds[LOW], low) == 0 ||
        pos2grid(grid, obj->bounds[HIGH], high) == 0 ||
        obj->bounds[LOW][X] > obj->bounds[HIGH][X]) {
        /*
         * Object is partially on wholly outside of
         * grid -- this should never happen, but just
         * in case...
         */
        make_unbounded(obj, grid);
        RSwarning("Strange, engrid got an unbounded object...\n");
        return;
        }

    /*
     * For each voxel that intersects the object's bounding
     * box, add pointer to this object to voxel's linked list.
      */
    for (x = low[X]; x <= high[X]; x++) {
        for (y = low[Y]; y <= high[Y]; y++) {
            for (z = low[Z]; z <= high[Z]; z++) {
                ltmp = (ObjList *)share_malloc(sizeof(ObjList));
                ltmp->data = obj;
                ltmp->next = grid->cells[x][y][z];
                grid->cells[x][y][z] = ltmp;
            }
        }
    }
}

/*
 * Convert 3D point to index into grid's voxels.
 */
pos2grid(grid, pos, index)
Grid *grid;
double pos[3];
int index[3];
{
    index[X] = (int)(x2voxel(grid, pos[0]));
    index[Y] = (int)(y2voxel(grid, pos[1]));
    index[Z] = (int)(z2voxel(grid, pos[2]));

    if (index[X] == grid->xsize)
        index[X] = grid->xsize -1;
    if (index[Y] == grid->ysize)
        index[Y] = grid->ysize -1;
    if (index[Z] == grid->zsize)
        index[Z] = grid->zsize -1;

    if (index[X] < 0 || index[X] >= grid->xsize ||
        index[Y] < 0 || index[Y] >= grid->ysize ||
        index[Z] < 0 || index[Z] >= grid->zsize)
        return 0;
    return 1;
}

/*
 * Convert a linked list of objects to a Grid.
 */
list2grid(obj, xsize, ysize, zsize)
Object *obj;
int xsize, ysize, zsize;
{
    Grid *grid;
    Object *otmp;
    ObjList *ltmp, *nltmp;
    int x, y, i;
    extern ObjList *find_bounds();

    grid = (Grid *)Malloc(sizeof(Grid));

    /*
     * Find bounding box of bounded objects and get list of
     * unbounded objects.
     */
    grid->unbounded = find_bounds((ObjList **)&obj->data, obj->bounds);

    grid->xsize = xsize; grid->ysize = ysize; grid->zsize = zsize;

    for (i = 0; i < 3; i++) {
        obj->bounds[LOW][i] -= 2. * EPSILON;
        obj->bounds[HIGH][i] += 2. * EPSILON;
        grid->bounds[LOW][i] = obj->bounds[LOW][i];
        grid->bounds[HIGH][i] = obj->bounds[HIGH][i];
    }
    grid->voxsize[X] = (grid->bounds[HIGH][X]-grid->bounds[LOW][X])/xsize;
    grid->voxsize[Y] = (grid->bounds[HIGH][Y]-grid->bounds[LOW][Y])/ysize;
    grid->voxsize[Z] = (grid->bounds[HIGH][Z]-grid->bounds[LOW][Z])/zsize;

    /*
     * Allocate voxels.
     */
    grid->cells = (ObjList ****)share_malloc(xsize * sizeof(ObjList ***));
    for (x = 0; x < xsize; x++) {
        grid->cells[x] = (ObjList ***)share_malloc(ysize*sizeof(ObjList **));
        for (y = 0; y < ysize; y++)
            grid->cells[x][y] = (ObjList **)share_calloc((unsigned)zsize,
                            sizeof(ObjList *));
    }

    /*
     * obj->data now holds a linked list of bounded objects.
     */
    for(ltmp = (ObjList *)obj->data; ltmp != (ObjList *)0; ltmp = nltmp) {
        otmp = ltmp->data;
        engrid(otmp, grid);
        nltmp = ltmp->next;
        free((char *)ltmp);
    }
    obj->type = GRID;
    obj->data = (char *)grid;
}
#ifdef MULTIMAX

char *
share_calloc(num, siz)
int num;
unsigned int siz;
{
    char *res;

    res = share_malloc(num*siz);
    bzero(res, num*siz);
    return res;
}
#endif