import java.util.Vector;

/**
 * Uniform spatial subdivision grid
 * Uses Jevans/Cleary traversal method
 * Refs: "Object Space Temporal Coherence for Ray Tracing"
 * by David A. Jevans, Graphics Interface, 1992
 * "Adaptive Voxel Subdivision for Ray Tracing"
 * by David A. Jevans and Brian Wyvill, Graphics Interface, 1989
 * "Analysis of an Algorithm for Fast Ray Tracing Using
 * Uniform Space Subdivision" by John Cleary and Geoff Wyvill, 1988
 * @author: Phil Gage
 */
class Grid {

    /** Grid cells,left null until used to save memory */
    Voxel voxel[][][];

    /** Number of grid divisions for each axis */
    VoxelIndex size;

    /** Minimum and maximum values of whole grid */
    private Extent extent;

    // Temp locals
    private VoxelIndex min = new VoxelIndex ();
    private VoxelIndex max = new VoxelIndex ();
    private VoxelIndex index = new VoxelIndex ();
    double origin[] = new double[3];
    double width[] = new double[3];
    // Grid traversal temp locals
    private VoxelIndex tempIndex = new VoxelIndex ();
    Box boundBox;
    Point tempPoint = new Point();
    Intersection tempIntersection = new Intersection();
    double delta[] = new double[3];
    double d[] = new double[3];
    double dir[] = new double[3];
    double orig[] = new double[3];
    int p[] = new int[3];

    /** Create grid with specified spatial extent and size */
    Grid (Extent extent, VoxelIndex size) {
//System.out.println("Grid extent="+extent);
//System.out.println("Grid size="+size);
        this.size = new VoxelIndex(size);
        this.extent = new Extent(extent);
        // Ugh, I regret mixing xyz and array notations...
        // (tbd fix messy point to array conversion:)
        origin[0] = extent.min.x;
        origin[1] = extent.min.y;
        origin[2] = extent.min.z;
        width[0] = (extent.max.x - extent.min.x) / size.xyz[0];
        width[1] = (extent.max.y - extent.min.y) / size.xyz[1];
        width[2] = (extent.max.z - extent.min.z) / size.xyz[2];
        // Allocate 3D array of references to all grid cells
        // Only creates pointers left null until used to save memory
        voxel = new Voxel[size.xyz[0]][size.xyz[1]][size.xyz[2]];
        // Create bounding box object for traverse camera off-grid test
        boundBox = new Box (extent, Color.BLACK);
    }

    /** Return grid indices of world point */
    void getVoxel (Point p, VoxelIndex index) {
        index.xyz[0] = (int)((double)size.xyz[0] *
                             (p.x - extent.min.x) /
                             (extent.max.x - extent.min.x));
        index.xyz[1] = (int)((double)size.xyz[1] *
                             (p.y - extent.min.y) /
                             (extent.max.y - extent.min.y));
        index.xyz[2] = (int)((double)size.xyz[2] *
                             (p.z - extent.min.z) /
                             (extent.max.z - extent.min.z));
    }

    /** Convert object extent to voxels and clip to grid extent */
    void getVoxelRange (Extent extent, VoxelIndex min, VoxelIndex max) {
        getVoxel (extent.min, min);
        getVoxel (extent.max, max);
        for (int i=0; i<3; i++) {
            if (min.xyz[i] < 0)
                min.xyz[i] = 0;
            if (max.xyz[i] > size.xyz[i]-1)
                max.xyz[i] = size.xyz[i]-1;
        }
    }

    /** Add object to all voxels that its extent overlaps */
    void addObject (AbstractObject object, Extent extent) {
//System.out.println("addObject extent="+extent);
        getVoxelRange (extent, min, max);
        for (int x=min.xyz[0]; x<=max.xyz[0]; x++) {
            for (int y=min.xyz[1]; y<=max.xyz[1]; y++) {
                for (int z=min.xyz[2]; z<=max.xyz[2]; z++) {
                    if (voxel[x][y][z] == null)
                        voxel[x][y][z] = new Voxel();
//TBD if (object.intersect(voxel))? here later...?
                    voxel[x][y][z].objects.addElement(object);
                    voxel[x][y][z].changed = true;
                }
            }
        }
    }

    /** Delete object from all voxels that its extent overlaps */
    void deleteObject (AbstractObject object, Extent extent) {
//System.out.println("deleteObject extent="+extent);
        getVoxelRange (extent, min, max);
        for (int x=min.xyz[0]; x<=max.xyz[0]; x++) {
            for (int y=min.xyz[1]; y<=max.xyz[1]; y++) {
                for (int z=min.xyz[2]; z<=max.xyz[2]; z++) {
                    voxel[x][y][z].objects.removeElement(object);
                    voxel[x][y][z].changed = true;
                }
            }
        }
    }

    //could combine both for efficiency?
//    void updateObject (AbstractObject object, Extent oldExtent,
//                       Extent newExtent) {
//    }

    /** Clear all voxel changed flags in all voxels */
    void clearChanged () {
        for (int x=0; x<size.xyz[0]; x++) {
            for (int y=0; y<size.xyz[1]; y++) {
                for (int z=0; z<size.xyz[2]; z++) {
                    if (voxel[x][y][z] != null)
                        voxel[x][y][z].changed = false;
                }
            }
        }
    }


    // Grid Traversal

    /** Traverse voxels along ray path and return closest intersection */
    double traverse (Ray ray, long rayId, AbstractObject shadowObject,
                     TemporalBitmap bitmap, Intersection intersection) {
//System.out.println("traverse ray="+ray);
        double dist, t, gridDist = 0;
        double c;
        int small;
        intersection.obj = null;
        tempPoint.set(ray.origin);

        // If ray origin (camera) off grid, move origin to grid edge
        // Save distance to grid intersection to add back later
        if (!extent.inside(ray.origin)) {
            // Intersect with bounding box around whole grid
            gridDist = boundBox.intersect (ray, tempIntersection);
            // If no intersection, return miss, else move origin
            if (gridDist <= 0.0)
                return 0.0;
            else
                ray.extrapolate (gridDist+Constants.EPSILON,tempPoint);
        }

        getVoxel (ray.origin, index);
//System.out.println("traverse index="+index);
        dir[0] = ray.direction.x;
        dir[1] = ray.direction.y;
        dir[2] = ray.direction.z;
        orig[0] = tempPoint.x;
        orig[1] = tempPoint.y;
        orig[2] = tempPoint.z;

        // Initialize Grid Traversal values using Jevans/Cleary method
        for (int i=0; i<3; i++) {
            c = dir[i];    // Ray direction equivalent to dir cosine
            if (c == 0.0)  // no change along this axis, can't increment
                d[i] = Constants.INFINITY;
            else if (c > 0.0) {  // positive along this axis
                delta[i] = width[i] / c;
                d[i] = (origin[i]+(index.xyz[i]+1)*width[i]-orig[i]) / c;
                p[i] = 1;
            }
            else {               // negative along this axis
                delta[i] = -width[i] / c;
                d[i] = -(orig[i]-(origin[i]+index.xyz[i]*width[i])) / c;
                p[i] = -1;
            }
        }

        // Loop through voxels until an object intersection is found
        // or the traversed ray exits the grid
        for (;;) {
//System.out.println("traverse index="+index);

            // temporal coherence acceleration
            if (bitmap != null)
                bitmap.set (index);

            AbstractObject obj;
            dist = -1;
            t = Constants.INFINITY;

            // Get current voxel and check its objects for intersection
            // Even if a good intersection is found, must check all remaining
            // objects in this voxel for a possible closer intersection
            Voxel vox = voxel[index.xyz[0]][index.xyz[1]][index.xyz[2]];

            if (vox != null && vox.objects != null) {
                for (int i=0; i<vox.objects.size(); i++) {
                    obj = (AbstractObject)vox.objects.elementAt(i);
                    // If this is a shadow ray, skip self-intersection
                    if (shadowObject != null && obj == shadowObject)
                        continue;   // skip to next i loop iteration
                    // Check mailbox for previous obj intersection
                    if (rayId == obj.rayId) {
                        dist = obj.rayDistance;
                        //tbd should only need saved dist, extrapolate
//                        ray.extrapolate (dist,tempIntersection.point); //save
//                        obj.normal(tempIntersection.point,tempIntersection.normal); //save
                        //tbd but Intersection has normal in it now
                        //tbd so copy Intersection, fix this later...
                        tempIntersection.set (obj.rayIntersection);
                    }
                    else
                        dist = obj.intersect (ray,tempIntersection);
                    // If a closer intersection is found, check it out
                    if (dist > Constants.EPSILON && dist < t) {
                        // If this is a shadow ray, can quit early
                        // on any intersection, even if not closest
                        // or intersection not in current voxel
                        // (if light sources are in scene and not just vectors,
                        // should check that intersection distance is closer
                        // than light distance here before quitting early...)
                        if (shadowObject != null) {
                            intersection.set(tempIntersection);
                            intersection.obj = obj;
                            return dist + gridDist;
                        }
                        // If a closer intersection has been found,
                        // check if it is in current voxel before saving
                        // or could miss a possible closer intersection
                        getVoxel (tempIntersection.point, tempIndex);
                        if (index.equals(tempIndex)) {
                            t = dist;
                            intersection.set(tempIntersection);
                            intersection.obj = obj;
                        }
                        // Else set mailbox data for later check
                        else {
                            obj.rayId = rayId;
                            obj.rayDistance = dist;
                            obj.rayIntersection.set (tempIntersection);
                        }
                    }
                }
                // If valid intersection found in this voxel, return distance
                if (intersection.obj != null)
                    return t + gridDist;
            }

            // Advance to next voxel along the ray
            // Find axis with smallest distance to next voxel
            if (d[0] < d[1])
                small = 0;
            else
                small = 1;
            if (d[2] < d[small])
                small = 2;
            // Increment/decrement this axis index into the next voxel
            index.xyz[small] += p[small];
            // If the traversed ray has exited the spatial grid, quit
            if (index.xyz[small] < 0 || index.xyz[small] >= size.xyz[small])
                break;
            // Increment distance to next voxel intersection along this axis
            d[small] += delta[small];
        }
        return 0.0;  // no intersection found, return zero distance
    }
}