/* Copyright (C) 1999-2004 by Peter Eastman

   This program is free software; you can redistribute it and/or modify it under the
   terms of the GNU General Public License as published by the Free Software
   Foundation; either version 2 of the License, or (at your option) any later version.

   This program is distributed in the hope that it will be useful, but WITHOUT ANY 
   WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A 
   PARTICULAR PURPOSE.  See the GNU General Public License for more details. */

package artofillusion.raytracer;

import artofillusion.*;
import artofillusion.image.*;
import artofillusion.material.*;
import artofillusion.math.*;
import artofillusion.object.*;
import artofillusion.texture.*;
import artofillusion.ui.*;
import buoy.event.*;
import buoy.widget.*;
import java.awt.*;
import java.awt.image.*;
import java.util.*;
import java.util.prefs.*;

/** Raytracer is a Renderer which generates images by raytracing. */

public class Raytracer implements Runnable
{
  RTObject sceneObject[];
  ObjectInfo light[];
  OctreeNode rootNode, cameraNode, lightNode[];
  ColumnContainer configPanel;
  BCheckBox depthBox, glossBox, shadowBox, causticsBox, transparentBox, hdrBox, adaptiveBox, rouletteBox;
  BComboBox aliasChoice, maxRaysChoice, minRaysChoice, giModeChoice;
  ValueField errorField, rayDepthField, rayCutoffField, smoothField, stepSizeField;
  ValueField extraGIField, extraGIEnvField;
  ValueField globalPhotonsField, globalNeighborPhotonsField, causticsPhotonsField, causticsNeighborPhotonsField;
  int pixel[], width, height, rtWidth, rtHeight, maxRayDepth, minRays, maxRays, antialiasLevel;
  MemoryImageSource imageSource;
  SceneRenderInfoProvider theScene;
  Camera theCamera;
  RenderListener listener;
  Image img;
  Thread renderThread;
  Ray ray[];
  RGBColor color[], rayIntensity[], tempColor, tempColor2, ambColor, envColor, fogColor;
  double transparency[], envParamValue[];
  TextureMapping envMapping;
  int envMode;
  Intersection intersect;
  MaterialIntersection matChange[];
  TextureSpec surfSpec[];
  MaterialSpec matSpec;
  Vec3 pos[], normal[], trueNormal[], hvec, vvec, center, viewpoint, cameraDir;
  double time, dofScale, depthOfField, focalDist, fogDist, surfaceError, stepSize;
  double smoothing, smoothScale, extraGISmoothing, extraGIEnvSmoothing;
  int giMode, globalPhotons, globalNeighborPhotons, causticsPhotons, causticsNeighborPhotons;
  float minRayIntensity = 0.01f, floatImage[][], depthImage[];
  boolean fog, depth, gloss, penumbra, caustics, transparentBackground, generateHDR, adaptive, roulette;
  Random random;
  PhotonMap globalMap, causticsMap;
  int startDelay;

  public static final double TOL = 1e-12;
  
  public static final int GI_NONE = 0;
  public static final int GI_MONTE_CARLO = 1;
  public static final int GI_PHOTON = 2;
  public static final int GI_HYBRID = 3;
  
  public static final float COLOR_THRESH_ABS = 1.0f/128.0f;
  public static final float COLOR_THRESH_REL = 1.0f/32.0f;
  
  public static final int distrib1[] = {0, 3, 1, 2, 1, 2, 0, 3, 2, 0, 3, 1, 3, 1, 2, 0};
  public static final int distrib2[] = {0, 1, 2, 3, 3, 0, 1, 2, 1, 2, 3, 0, 0, 1, 2, 3};

  /** When a ray is traced to determine what objects it intersects, an Intersection object 
     is used for returning the results.  To avoid creating excess objects, only one 
     Intersection object is created and used for all rays. */

  class Intersection
  {
    RTObject first, second;
    double dist;
    
    public Intersection()
    {
    }
  }

  /** When a shadow ray is traced to determine whether a light is blocked, MaterialIntersection
     objects are used to keep track of where the ray enters or exits materials. */

  class MaterialIntersection
  {
    MaterialMapping mat;
    Mat4 toLocal;
    double dist;
    boolean entered;
    OctreeNode node;
    
    public MaterialIntersection()
    {
    }
  }

  public Raytracer()
  {
    startDelay=100;
  }
  
  /** Methods from the Renderer interface. */

  public synchronized void renderScene(SceneRenderInfoProvider theScene, Camera theCamera, RenderListener rl, SceneCamera sceneCamera)
  {
    Dimension dim = theCamera.getSize();

    listener = rl;
    this.theScene = theScene;
    this.theCamera = theCamera;
    if (sceneCamera == null)
      {
        depthOfField = 0.0;
        focalDist = theCamera.getDistToScreen();
      }
    else
      {
        depthOfField = sceneCamera.getDepthOfField();
        focalDist = sceneCamera.getFocalDistance();
      }
    time = theScene.getTime();
    if (pixel == null || width != dim.width || height != dim.height)
      {
	width = dim.width;
	height = dim.height;
	pixel = new int [width*height];
	imageSource = new MemoryImageSource(width, height, pixel, 0, width);
	imageSource.setAnimated(true);
	img = Toolkit.getDefaultToolkit().createImage(imageSource);
      }
    int requiredComponents = (sceneCamera == null ? 0 : sceneCamera.getComponentsForFilters());
    if (generateHDR || (requiredComponents&(ComplexImage.RED+ComplexImage.GREEN+ComplexImage.BLUE)) != 0)
      {
        if (floatImage == null || floatImage.length != width*height)
          floatImage = new float [4][width*height];
      }
    else
      floatImage = null;
    if ((requiredComponents&ComplexImage.DEPTH) != 0)
      depthImage = new float [width*height];
    else
      depthImage = null;
    ray = new Ray [maxRayDepth+1];
    color = new RGBColor [maxRayDepth+1];
    transparency = new double [maxRayDepth+1];
    rayIntensity = new RGBColor [maxRayDepth+1];
    surfSpec = new TextureSpec [maxRayDepth+1];
    pos = new Vec3 [maxRayDepth+1];
    normal = new Vec3 [maxRayDepth+1];
    trueNormal = new Vec3 [maxRayDepth+1];
    for (int i = 0; i < maxRayDepth+1; i++)
      {
	ray[i] = new Ray();
	color[i] = new RGBColor(0.0f, 0.0f, 0.0f);
	rayIntensity[i] = new RGBColor(0.0f, 0.0f, 0.0f);
	surfSpec[i] = new TextureSpec();
	pos[i] = new Vec3();
	normal[i] = new Vec3();
	trueNormal[i] = new Vec3();
      }
    matSpec = new MaterialSpec();
    intersect = new Intersection();
    tempColor = new RGBColor(0.0f, 0.0f, 0.0f);
    tempColor2 = new RGBColor(0.0f, 0.0f, 0.0f);
    matChange = new MaterialIntersection [64];
    for (int i = 0; i < matChange.length; i++)
      matChange[i] = new MaterialIntersection();
    random = new Random(0);
    renderThread = new Thread(this);
    renderThread.start();
//    System.out.println("Raytracer.renderScene  thread started");
  }

  public synchronized void cancelRendering(SceneRenderInfoProvider sc)
  {
    Thread t = null;
    RenderListener rl = null;
    
    if (theScene != sc)
      return;

    t = renderThread;
    rl = listener;

    cancelRenderingAsync(sc);
//    renderThread = null;
    if (t == null)
      return;
    t.interrupt();
    try
      {
        t.join();
//        while (t.isAlive())
//          {
//            Thread.sleep(100);
//          }
      }
    catch (InterruptedException ex)
      {
      }
    
//    listener = null;
    if (rl != null)
      rl.renderingCanceled();
    finish();
  }

  public synchronized void cancelRenderingAsync(final SceneRenderInfoProvider sc)
  {
    if (theScene != sc)
      return;
    setAllNull();
    
//    final Thread rt = renderThread;
//    if (theScene != sc)
//      return;
//    Thread t = new Thread(new Runnable() {
//      public void run()
//      {
//        cancelRendering(sc, rt);
//      }
//    } );
//    
//    t.start();
  }
  
  public Widget getConfigPanel()
  {
    if (configPanel == null)
    {
      configPanel = new ColumnContainer();
      FormContainer choicesPanel = new FormContainer(2, 4);
      configPanel.add(choicesPanel);
      LayoutInfo leftLayout = new LayoutInfo(LayoutInfo.EAST, LayoutInfo.NONE, new Insets(0, 0, 0, 5), null);
      LayoutInfo rightLayout = new LayoutInfo(LayoutInfo.WEST, LayoutInfo.NONE, null, null);
      choicesPanel.add(Translate.label("surfaceAccuracy"), 0, 0, leftLayout);
      choicesPanel.add(new BLabel(Translate.text("Antialiasing")+":"), 0, 1, leftLayout);
      choicesPanel.add(Translate.label("minRaysPixel"), 0, 2, leftLayout);
      choicesPanel.add(Translate.label("maxRaysPixel"), 0, 3, leftLayout);
      choicesPanel.add(errorField = new ValueField(0.02, ValueField.POSITIVE, 6), 1, 0, rightLayout);
      choicesPanel.add(aliasChoice = new BComboBox(new String [] {
        Translate.text("none"),
        Translate.text("Medium"),
        Translate.text("Maximum")
      }), 1, 1, rightLayout);
      choicesPanel.add(minRaysChoice = new BComboBox(), 1, 2, rightLayout);
      choicesPanel.add(maxRaysChoice = new BComboBox(), 1, 3, rightLayout);
      for (int i = 4; i <= 1024; i *= 2)
      {
        minRaysChoice.add(Integer.toString(i));
        maxRaysChoice.add(Integer.toString(i));
      }
      minRaysChoice.setSelectedIndex(0);
      maxRaysChoice.setSelectedIndex(2);
      ColumnContainer boxes = new ColumnContainer();
      configPanel.add(boxes);
      boxes.setDefaultLayout(new LayoutInfo(LayoutInfo.WEST, LayoutInfo.NONE, null, null));
      boxes.add(depthBox = new BCheckBox(Translate.text("depthOfField"), false));
      boxes.add(glossBox = new BCheckBox(Translate.text("glossTranslucency"), false));
      boxes.add(shadowBox = new BCheckBox(Translate.text("softShadows"), false));

      // Create components for the Illumination Options window.

      RowContainer buttons = new RowContainer();
      configPanel.add(buttons);
      buttons.add(Translate.button("illumination", this, "showIlluminationWindow"));
      giModeChoice = new BComboBox(new String [] {
        Translate.text("none"),
        Translate.text("monteCarlo"),
        Translate.text("photonMapping"),
        Translate.text("hybrid")
      });
      globalPhotonsField = new ValueField(10000.0, ValueField.POSITIVE+ValueField.INTEGER, 7);
      globalNeighborPhotonsField = new ValueField(200.0, ValueField.POSITIVE+ValueField.INTEGER, 4);
      causticsPhotonsField = new ValueField(10000.0, ValueField.POSITIVE+ValueField.INTEGER, 7);
      causticsNeighborPhotonsField = new ValueField(100.0, ValueField.POSITIVE+ValueField.INTEGER, 4);
      causticsBox = new BCheckBox(Translate.text("useCausticsMap"), false);
      Object illumListener = new Object() {
        void processEvent()
        {
          int mode = giModeChoice.getSelectedIndex();
          globalPhotonsField.setEnabled(mode == GI_PHOTON || mode == GI_HYBRID);
          globalNeighborPhotonsField.setEnabled(mode == GI_PHOTON || mode == GI_HYBRID);
          causticsPhotonsField.setEnabled(causticsBox.getState());
          causticsNeighborPhotonsField.setEnabled(causticsBox.getState());
        }
      };
      giModeChoice.addEventLink(ValueChangedEvent.class, illumListener);
      causticsBox.addEventLink(ValueChangedEvent.class, illumListener);
      causticsBox.dispatchEvent(new ValueChangedEvent(causticsBox));

      // Create components for the Output Options window.

      buttons.add(Translate.button("output", this, "showOutputOptionsWindow"));
      transparentBox = new BCheckBox(Translate.text("transparentBackground"), false);
      hdrBox = new BCheckBox(Translate.text("generateHDR"), true);

      // Create components for the Advanced Options window.

      buttons.add(Translate.button("advanced", this, "showAdvancedOptionsWindow"));
      rayDepthField = new ValueField(8.0, ValueField.POSITIVE+ValueField.INTEGER);
      rayCutoffField = new ValueField(0.01, ValueField.NONNEGATIVE);
      smoothField = new ValueField(1.0, ValueField.NONNEGATIVE);
      extraGIField = new ValueField(10.0, ValueField.POSITIVE);
      extraGIEnvField = new ValueField(100.0, ValueField.POSITIVE);
      stepSizeField = new ValueField(1.0, ValueField.POSITIVE);
      adaptiveBox = new BCheckBox(Translate.text("reduceAccuracyForDistant"), true);
      rouletteBox = new BCheckBox(Translate.text("russianRoulette"), false);

      // Set up a listener for all of the checkboxes that affect the number of rays required.

      Object raysListener = new Object() {
        void processEvent(WidgetEvent ev)
        {
          boolean multi = (aliasChoice.getSelectedIndex() > 0);

          depthBox.setEnabled(multi);
          glossBox.setEnabled(multi);
          shadowBox.setEnabled(multi);
          minRaysChoice.setEnabled(multi);
          maxRaysChoice.setEnabled(multi);
          if (minRaysChoice.getSelectedIndex() > maxRaysChoice.getSelectedIndex())
          {
            if (ev.getWidget() == maxRaysChoice)
              minRaysChoice.setSelectedIndex(maxRaysChoice.getSelectedIndex());
            else
              maxRaysChoice.setSelectedIndex(minRaysChoice.getSelectedIndex());
          }
        }
      };
      aliasChoice.addEventLink(ValueChangedEvent.class, raysListener);
      minRaysChoice.addEventLink(ValueChangedEvent.class, raysListener);
      maxRaysChoice.addEventLink(ValueChangedEvent.class, raysListener);
      aliasChoice.dispatchEvent(new ValueChangedEvent(aliasChoice));
    }
    return configPanel;
  }
  
  private void showAdvancedOptionsWindow(WidgetEvent ev)
  {
    // Layout the window.
    
    FormContainer content = new FormContainer(2, 9);
    content.setColumnWeight(0, 0.0);
    LayoutInfo leftLayout = new LayoutInfo(LayoutInfo.EAST, LayoutInfo.NONE, new Insets(0, 0, 0, 5), null);
    LayoutInfo rightLayout = new LayoutInfo(LayoutInfo.WEST, LayoutInfo.HORIZONTAL, null, null);
    content.add(Translate.label("maxRayTreeDepth"), 0, 0, leftLayout);
    content.add(Translate.label("minRayIntensity"), 0, 1, leftLayout);
    content.add(Translate.label("matStepSize"), 0, 3, leftLayout);
    content.add(Translate.label("texSmoothing"), 0, 4, leftLayout);
    content.add(rayDepthField, 1, 0, rightLayout);
    content.add(rayCutoffField, 1, 1, rightLayout);
    content.add(stepSizeField, 1, 3, rightLayout);
    content.add(smoothField, 1, 4, rightLayout);
    content.add(Translate.label("extraGISmoothing"), 0, 5, 2, 1, rightLayout);
    RowContainer row = new RowContainer();
    content.add(row, 0, 6, 2, 1);
    row.add(new BLabel(Translate.text("Textures")+":"));
    row.add(extraGIField);
    row.add(new BLabel(Translate.text("environment")+":"));
    row.add(extraGIEnvField);
    content.add(adaptiveBox, 0, 7, 2, 1, rightLayout);
    content.add(rouletteBox, 0, 8, 2, 1, rightLayout);

    // Record the current settings.

    maxRayDepth = (int) rayDepthField.getValue();
    minRayIntensity = (float) rayCutoffField.getValue();
    stepSize = stepSizeField.getValue();
    smoothing = smoothField.getValue();
    extraGISmoothing = extraGIField.getValue();
    extraGIEnvSmoothing = extraGIEnvField.getValue();
    adaptive = adaptiveBox.getState();
    roulette = rouletteBox.getState();
    
    // Show the window.
    
    WindowWidget parent = UIUtilities.findWindow(ev.getWidget());
    PanelDialog dlg;
    if (parent instanceof BDialog)
      dlg = new PanelDialog((BDialog) parent, Translate.text("advancedOptions"), content);
    else
      dlg = new PanelDialog((BFrame) parent, Translate.text("advancedOptions"), content);
    if (!dlg.clickedOk())
    {
      // Reset the components.
      
      rayDepthField.setValue(maxRayDepth);
      rayCutoffField.setValue(minRayIntensity);
      stepSizeField.setValue(stepSize);
      smoothField.setValue(smoothing);
      extraGIField.setValue(extraGISmoothing);
      extraGIEnvField.setValue(extraGIEnvSmoothing);
      adaptiveBox.setState(adaptive);
      rouletteBox.setState(roulette);
    }
  }

  private void showIlluminationWindow(WidgetEvent ev)
  {
    // Layout the window.
    
    ColumnContainer content = new ColumnContainer();
    LayoutInfo indent0 = new LayoutInfo(LayoutInfo.WEST, LayoutInfo.NONE, null, null);
    LayoutInfo indent1 = new LayoutInfo(LayoutInfo.WEST, LayoutInfo.NONE, new Insets(0, 5, 0, 0), null);
    LayoutInfo indent2 = new LayoutInfo(LayoutInfo.WEST, LayoutInfo.NONE, new Insets(0, 10, 0, 0), null);
    RowContainer row;
    content.add(row = new RowContainer(), indent0);
    row.add(Translate.label("globalIllumination"));
    row.add(giModeChoice);
    content.add(Translate.label("giPhotonMap"), indent1);
    content.add(row = new RowContainer(), indent2);
    row.add(Translate.label("totalPhotons"));
    row.add(globalPhotonsField);
    row.add(Translate.label("numToEstimateLight"));
    row.add(globalNeighborPhotonsField);
    content.add(causticsBox, indent0);
    content.add(row = new RowContainer(), indent2);
    row.add(Translate.label("totalPhotons"));
    row.add(causticsPhotonsField);
    row.add(Translate.label("numToEstimateLight"));
    row.add(causticsNeighborPhotonsField);

    // Record the current settings.

    giMode = giModeChoice.getSelectedIndex();
    globalPhotons = (int) globalPhotonsField.getValue();
    globalNeighborPhotons = (int) globalNeighborPhotonsField.getValue();
    caustics = causticsBox.getState();
    causticsPhotons = (int) causticsPhotonsField.getValue();
    causticsNeighborPhotons = (int) causticsNeighborPhotonsField.getValue();
    
    // Show the window.
    
    WindowWidget parent = UIUtilities.findWindow(ev.getWidget());
    PanelDialog dlg;
    if (parent instanceof BDialog)
      dlg = new PanelDialog((BDialog) parent, Translate.text("illuminationOptions"), content);
    else
      dlg = new PanelDialog((BFrame) parent, Translate.text("illuminationOptions"), content);
    if (!dlg.clickedOk())
    {
      // Reset the components.
      
      giModeChoice.setSelectedIndex(giMode);
      globalPhotonsField.setValue(globalPhotons);
      globalNeighborPhotonsField.setValue(globalNeighborPhotons);
      causticsBox.setState(caustics);
      causticsPhotonsField.setValue(causticsPhotons);
      causticsNeighborPhotonsField.setValue(causticsNeighborPhotons);
    }
  }

  private void showOutputOptionsWindow(WidgetEvent ev)
  {
    // Record the current settings.

    transparentBackground = transparentBox.getState();
    generateHDR = hdrBox.getState();
    
    // Show the window.
    
    WindowWidget parent = UIUtilities.findWindow(ev.getWidget());
    ComponentsDialog dlg;
    if (parent instanceof BDialog)
      dlg = new ComponentsDialog((BDialog) parent, Translate.text("outputOptions"), new Widget [] {transparentBox, hdrBox}, new String [] {"", ""});
    else
      dlg = new ComponentsDialog((BFrame) parent, Translate.text("outputOptions"), new Widget [] {transparentBox, hdrBox}, new String [] {"", ""});
    if (!dlg.clickedOk())
    {
      // Reset the components.
      
      transparentBox.setState(transparentBackground);
      hdrBox.setState(generateHDR);
    }
  }

  public boolean recordConfiguration()
  {
    maxRayDepth = (int) rayDepthField.getValue();
    minRayIntensity = (float) rayCutoffField.getValue();
    stepSize = stepSizeField.getValue();
    smoothing = smoothField.getValue();
    extraGISmoothing = extraGIField.getValue();
    extraGIEnvSmoothing = extraGIEnvField.getValue();
    adaptive = adaptiveBox.getState();
    roulette = rouletteBox.getState();
    surfaceError = errorField.getValue();
    antialiasLevel = aliasChoice.getSelectedIndex();
    depth = depthBox.getState();
    gloss = glossBox.getState();
    penumbra = shadowBox.getState();
    minRays = Integer.parseInt((String) minRaysChoice.getSelectedValue());
    maxRays = Integer.parseInt((String) maxRaysChoice.getSelectedValue());
    if (antialiasLevel == 0)
      minRays = maxRays = 1;
    transparentBackground = transparentBox.getState();
    generateHDR = hdrBox.getState();
    giMode = giModeChoice.getSelectedIndex();
    globalPhotons = (int) globalPhotonsField.getValue();
    globalNeighborPhotons = (int) globalNeighborPhotonsField.getValue();
    caustics = causticsBox.getState();
    causticsPhotons = (int) causticsPhotonsField.getValue();
    causticsNeighborPhotons = (int) causticsNeighborPhotonsField.getValue();
    return true;
  }
  
  /** Makes the configuration of this renderer identical to another one. */
  public synchronized void makeEqualConfig(Raytracer r)
  {
    maxRayDepth = r.maxRayDepth;
    minRayIntensity = r.minRayIntensity;
    stepSize = r.stepSize;
    smoothing = r.smoothing;
    extraGISmoothing = r.extraGISmoothing;
    extraGIEnvSmoothing = r.extraGIEnvSmoothing;
    adaptive = r.adaptive;
    roulette = r.roulette;
    surfaceError = r.surfaceError;
    antialiasLevel = r.antialiasLevel;
    depth = r.depth;
    gloss = r.gloss;
    penumbra = r.penumbra;
    minRays = r.minRays;
    maxRays = r.maxRays;
    if (antialiasLevel == 0)
      minRays = maxRays = 1;
    transparentBackground = r.transparentBackground;
    generateHDR = r.generateHDR;
    giMode = r.giMode;
    globalPhotons = r.globalPhotons;
    globalNeighborPhotons = r.globalNeighborPhotons;
    caustics = r.caustics;
    causticsPhotons = r.causticsPhotons;
    causticsNeighborPhotons = r.causticsNeighborPhotons;
  }
  
  
  
  public Map getConfiguration()
  {
    HashMap map = new HashMap();
    map.put("maxRayDepth", new Integer(maxRayDepth));
    map.put("minRayIntensity", new Float(minRayIntensity));
    map.put("materialStepSize", new Double(stepSize));
    map.put("textureSmoothing", new Double(smoothing));
    map.put("extraGISmoothing", new Double(extraGISmoothing));
    map.put("extraGIEnvSmoothing", new Double(extraGIEnvSmoothing));
    map.put("reduceAccuracyForDistant", new Boolean(adaptive));
    map.put("russianRouletteSampling", new Boolean(roulette));
    map.put("maxSurfaceError", new Double(surfaceError));
    map.put("antialiasing", new Integer(antialiasLevel));
    map.put("depthOfField", new Boolean(depth));
    map.put("gloss", new Boolean(gloss));
    map.put("softShadows", new Boolean(penumbra));
    map.put("minRaysPerPixel", new Integer(minRays));
    map.put("maxRaysPerPixel", new Integer(maxRays));
    map.put("transparentBackground", new Boolean(transparentBackground));
    map.put("highDynamicRange", new Boolean(generateHDR));
    map.put("globalIlluminationMode", new Integer(giMode));
    map.put("globalIlluminationPhotons", new Integer(globalPhotons));
    map.put("globalIlluminationPhotonsInEstimate", new Integer(globalNeighborPhotons));
    map.put("caustics", new Boolean(caustics));
    map.put("causticsPhotons", new Integer(causticsPhotons));
    map.put("causticsPhotonsInEstimate", new Integer(causticsNeighborPhotons));
    return map;
  }
  
  public void setConfiguration(String property, Object value)
  {
    if ("maxRayDepth".equals(property))
      maxRayDepth = ((Integer) value).intValue();
    else if ("minRayIntensity".equals(property))
      minRayIntensity = ((Number) value).floatValue();
    else if ("materialStepSize".equals(property))
      stepSize = ((Number) value).doubleValue();
    else if ("textureSmoothing".equals(property))
      smoothing = ((Number) value).doubleValue();
    else if ("extraGISmoothing".equals(property))
      extraGISmoothing = ((Number) value).doubleValue();
    else if ("extraGIEnvSmoothing".equals(property))
      extraGIEnvSmoothing = ((Number) value).doubleValue();
    else if ("reduceAccuracyForDistant".equals(property))
      adaptive = ((Boolean) value).booleanValue();
    else if ("russianRouletteSampling".equals(property))
      roulette = ((Boolean) value).booleanValue();
    else if ("maxSurfaceError".equals(property))
      surfaceError = ((Number) value).doubleValue();
    else if ("antialiasing".equals(property))
      antialiasLevel = ((Integer) value).intValue();
    else if ("depthOfField".equals(property))
      depth = ((Boolean) value).booleanValue();
    else if ("gloss".equals(property))
      depth = ((Boolean) value).booleanValue();
    else if ("softShadows".equals(property))
      penumbra = ((Boolean) value).booleanValue();
    else if ("minRaysPerPixel".equals(property))
      minRays = ((Integer) value).intValue();
    else if ("maxRaysPerPixel".equals(property))
      maxRays = ((Integer) value).intValue();
    else if ("transparentBackground".equals(property))
      transparentBackground = ((Boolean) value).booleanValue();
    else if ("highDynamicRange".equals(property))
      generateHDR = ((Boolean) value).booleanValue();
    else if ("globalIlluminationMode".equals(property))
      giMode = ((Integer) value).intValue();
    else if ("globalIlluminationPhotons".equals(property))
      globalPhotons = ((Integer) value).intValue();
    else if ("globalIlluminationPhotonsInEstimate".equals(property))
      globalNeighborPhotons = ((Integer) value).intValue();
    else if ("caustics".equals(property))
      caustics = ((Boolean) value).booleanValue();
    else if ("causticsPhotons".equals(property))
      causticsPhotons = ((Integer) value).intValue();
    else if ("causticsPhotonsInEstimate".equals(property))
      causticsNeighborPhotons = ((Integer) value).intValue();
  }
  
  public void configurePreview()
  {
    maxRayDepth = 6;
    minRayIntensity = 0.02f;
    antialiasLevel = 0;
    depth = gloss = penumbra = transparentBackground = generateHDR = false;
    minRays = maxRays = 1;
    stepSize = 1.0;
    smoothing = 1.0;
    extraGISmoothing = 10.0;
    extraGIEnvSmoothing = 100.0;
    adaptive = true;
    roulette = false;
    surfaceError = 0.02;
    giMode = GI_NONE;
    caustics = false;
  }

  /** Construct the list of RTObjects and lights in the scene. */

  void buildScene(SceneRenderInfoProvider theScene, Camera theCamera)
  {
    Vector obj = new Vector(), lt = new Vector();
    Vec3 orig = theCamera.getCameraCoordinates().getOrigin();
    double distToScreen = theCamera.getDistToScreen();
    Thread thisThread = Thread.currentThread();
    ObjectInfo info;
    int i;
    
    for (i = 0; i < theScene.getNumObjects(); i++)
      {
	info = theScene.getObject(i);
	if (info.visible)
	  addObject(obj, lt, info, orig, distToScreen, info.coords.toLocal(), info.coords.fromLocal());
	if (renderThread != thisThread)
	  return;
      }
    sceneObject = new RTObject [obj.size()];
    for (i = 0; i < sceneObject.length; i++)
      sceneObject[i] = (RTObject) obj.elementAt(i);
    light = new ObjectInfo [lt.size()];
    for (i = 0; i < light.length; i++)
      light[i] = (ObjectInfo) lt.elementAt(i);
    ambColor = theScene.getAmbientColor();
    envColor = theScene.getEnvironmentColor();
    envMapping = theScene.getEnvironmentMapping();
    envMode = theScene.getEnvironmentMode();
    fogColor = theScene.getFogColor();
    fog = theScene.getFogState();
    fogDist = theScene.getFogDistance();
    ParameterValue envParam[] = theScene.getEnvironmentParameterValues();
    envParamValue = new double [envParam.length];
    for (i = 0; i < envParamValue.length; i++)
      envParamValue[i] = envParam[i].getAverageValue();
  }
  
  /** Add a single object to the scene. */
  
  void addObject(Vector obj, Vector lt, ObjectInfo info, Vec3 orig, double distToScreen, 
		Mat4 toLocal, Mat4 fromLocal)
  {
    Thread thisThread = Thread.currentThread();
    double dist;
    ObjectInfo objects[];
    Object3D theObject = info.object;
    boolean displaced = false;
    double tol;
    int i;
    
    if (renderThread != thisThread)
      return;
    if (theObject instanceof Light)
      {
	lt.addElement(info);
	return;
      }
    if (theObject instanceof ObjectCollection)
      {
        Enumeration objenum = ((ObjectCollection) theObject).getObjects(info, false, theScene);
        while (objenum.hasMoreElements())
          {
            ObjectInfo elem = (ObjectInfo) objenum.nextElement();
            if (!elem.visible)
              continue;
            CoordinateSystem coords = elem.coords.duplicate();
            coords.transformCoordinates(fromLocal);
            addObject(obj, lt, elem, orig, distToScreen, coords.toLocal(), coords.fromLocal());
          }
        return;
      }
    if (adaptive)
      {
	dist = info.getBounds().distanceToPoint(toLocal.times(orig));
	if (dist < distToScreen)
	  tol = surfaceError;
	else
	  tol = surfaceError*dist/distToScreen;
      }
    else
      tol = surfaceError;
    Texture tex = theObject.getTexture();
    if (tex != null && tex.hasComponent(Texture.DISPLACEMENT_COMPONENT) == true)
      {
	displaced = true;
	if (theObject.canConvertToTriangleMesh() != Object3D.CANT_CONVERT)
	  {
	    TriangleMesh tm = theObject.convertToTriangleMesh(tol);
	    tm.setTexture(tex, theObject.getTextureMapping().duplicate());
	    if (theObject.getMaterialMapping() != null)
              tm.setMaterial(theObject.getMaterial(), theObject.getMaterialMapping().duplicate());
	    theObject = tm;
	  }
      }
    if (!info.isDistorted())
      {
        if (theObject instanceof Sphere)
          {
            Vec3 rad = ((Sphere) theObject).getRadii();
            if (rad.x == rad.y && rad.x == rad.z)
              {
                obj.addElement(new RTSphere((Sphere) theObject, fromLocal, toLocal, time, info.object.getAverageParameterValues()));
                return;
              }
            else
              {
                obj.addElement(new RTEllipsoid((Sphere) theObject, fromLocal, toLocal, time, info.object.getAverageParameterValues()));
                return;
              }
          }
        else if (theObject instanceof Cylinder)
          {
            obj.addElement(new RTCylinder((Cylinder) theObject, fromLocal, toLocal, time, info.object.getAverageParameterValues()));
            return;
          }
        else if (theObject instanceof Cube)
          {
            obj.addElement(new RTCube((Cube) theObject, fromLocal, toLocal, time, info.object.getAverageParameterValues()));
            return;
          }
      }
    RenderingMesh mesh = info.getRenderingMesh(tol);
    if (mesh == null)
      return;
    mesh.transformMesh(fromLocal);
    Vec3 vert[] = mesh.vert;
    Vec3 norm[] = mesh.norm;
    RenderingTriangle t[] = mesh.triangle;
    if (displaced)
      {
        double vertTol[] = new double [vert.length];
        if (adaptive)
          for (i = 0; i < vert.length; i++)
            {
              double vertDist = orig.distance(vert[i]);
              vertTol[i] = (vertDist < distToScreen ? surfaceError : surfaceError*vertDist/distToScreen);
            }
        for (i = 0; i < t.length; i++)
          {
            RenderingTriangle tri = mesh.triangle[i];
            if (vert[tri.v1].distance(vert[tri.v2]) < TOL)
              continue;
            if (vert[tri.v1].distance(vert[tri.v3]) < TOL)
              continue;
            if (vert[tri.v2].distance(vert[tri.v3]) < TOL)
              continue;
            double localTol;
            if (adaptive)
              {
                localTol = vertTol[tri.v1];
                if (vertTol[tri.v2] < localTol)
                  localTol = vertTol[tri.v2];
                if (vertTol[tri.v3] < localTol)
                  localTol = vertTol[tri.v3];
              }
            else
              localTol = tol;
            RTDisplacedTriangle dispTri = new RTDisplacedTriangle(mesh, i, fromLocal, toLocal, localTol, time);
            RTObject dt = dispTri;
            if (!dispTri.isReallyDisplaced())
              dt = new RTTriangle(mesh, i, fromLocal, toLocal, time);
            obj.addElement(dt);
            if (adaptive && dt instanceof RTDisplacedTriangle)
              {
                dist = dt.getBounds().distanceToPoint(orig);
                if (dist < distToScreen)
                  ((RTDisplacedTriangle) dt).setTolerance(surfaceError);
                else
                  ((RTDisplacedTriangle) dt).setTolerance(surfaceError*dist/distToScreen);
              }
            if (renderThread != thisThread)
              return;
          }
      }
    else
      for (i = 0; i < t.length; i++)
	{
	  RenderingTriangle tri = mesh.triangle[i];
	  if (vert[tri.v1].distance(vert[tri.v2]) < TOL)
	    continue;
	  if (vert[tri.v1].distance(vert[tri.v3]) < TOL)
	    continue;
	  if (vert[tri.v2].distance(vert[tri.v3]) < TOL)
	    continue;
	  obj.addElement(new RTTriangle(mesh, i, fromLocal, toLocal, time));
	}
  }
  
  /** Build the octree. */
  
  void buildTree()
  {
    BoundingBox objBounds[] = new BoundingBox [sceneObject.length];
    double minx, maxx, miny, maxy, minz, maxz;
    int i;
    
    // Find the bounding boxes for each object, and for the entire scene.

    minx = miny = minz = Double.MAX_VALUE;
    maxx = maxy = maxz = -Double.MAX_VALUE;
    for (i = 0; i < sceneObject.length; i++)
      {
	objBounds[i] = sceneObject[i].getBounds();
	if (objBounds[i].minx < minx)
	  minx = objBounds[i].minx;
	if (objBounds[i].maxx > maxx)
	  maxx = objBounds[i].maxx;
	if (objBounds[i].miny < miny)
	  miny = objBounds[i].miny;
	if (objBounds[i].maxy > maxy)
	  maxy = objBounds[i].maxy;
	if (objBounds[i].minz < minz)
	  minz = objBounds[i].minz;
	if (objBounds[i].maxz > maxz)
	  maxz = objBounds[i].maxz;
      }
    minx -= TOL;
    miny -= TOL;
    minz -= TOL;
    maxx += TOL;
    maxy += TOL;
    maxz += TOL;
    
    // Create the octree.

    rootNode = new OctreeNode(minx, maxx, miny, maxy, minz, maxz, sceneObject, objBounds, null);

    // Find the nodes which contain the camera and the lights.

    cameraNode = rootNode.findNode(theCamera.getCameraCoordinates().getOrigin());
    lightNode = new OctreeNode [light.length];
    for (i = 0; i < light.length; i++)
      {
	if (light[i].object instanceof DirectionalLight)
	  lightNode[i] = null;
	else
	  lightNode[i] = rootNode.findNode(light[i].coords.getOrigin());
      }
  }
  
  /** Build the photon maps. */
  
  private void buildPhotonMap()
  {
    if (giMode == GI_PHOTON)
      {
        listener.statusChanged("Building Global Photon Map");
        globalMap = new PhotonMap(globalPhotons, globalNeighborPhotons, false, false, true, this, rootNode, 1, null);
        generatePhotons(globalMap);
      }
    else if (giMode == GI_HYBRID)
      {
        listener.statusChanged("Building Global Photon Map");
        globalMap = new PhotonMap(globalPhotons, globalNeighborPhotons, true, true, true, this, rootNode, 0, null);
        generatePhotons(globalMap);
      }
    if (caustics)
      {
        // Find a bounding box around all objects that can generate caustics.
        
        BoundingBox bounds = null;
        for (int i = 0; i < sceneObject.length; i++)
          {
            Texture tex = sceneObject[i].getTextureMapping().getTexture();
            MaterialMapping mm = sceneObject[i].getMaterialMapping();
            if (tex.hasComponent(Texture.SPECULAR_COLOR_COMPONENT) || (tex.hasComponent(Texture.TRANSPARENT_COLOR_COMPONENT) && mm != null && mm.getMaterial().indexOfRefraction() != 1.0))
              {
                if (bounds == null)
                  bounds = sceneObject[i].getBounds();
                else
                  bounds = bounds.merge(sceneObject[i].getBounds());
              }
          }
        if (bounds == null)
          bounds = new BoundingBox(0, 0, 0, 0, 0, 0);
        listener.statusChanged("Building Caustics Photon Map");
        causticsMap = new PhotonMap(causticsPhotons, causticsNeighborPhotons, true, false, false, this, bounds, 2, null);
        generatePhotons(causticsMap);
      }
  }

  /** Find all the photon sources in the scene, and generate the photons in a PhotonMap. */
  
  private void generatePhotons(PhotonMap map)
  {
    BoundingBox bounds = map.getBounds();
    Vector sources = new Vector();
    for (int i = 0; i < light.length; i++)
      {
        if (light[i].object instanceof DirectionalLight)
          sources.addElement(new DirectionalPhotonSource((DirectionalLight) light[i].object, light[i].coords, bounds));
        else if (light[i].object instanceof PointLight)
          sources.addElement(new PointPhotonSource((PointLight) light[i].object, light[i].coords, bounds));
        else if (light[i].object instanceof SpotLight)
          sources.addElement(new SpotlightPhotonSource((SpotLight) light[i].object, light[i].coords, bounds));
      }
    for (int i = 0; i < sceneObject.length; i++)
      {
        if (!sceneObject[i].getTextureMapping().getTexture().hasComponent(Texture.EMISSIVE_COLOR_COMPONENT))
          continue;
        PhotonSource src;
        if (sceneObject[i] instanceof RTTriangle)
          src = new TrianglePhotonSource((RTTriangle) sceneObject[i], this);
        else if (sceneObject[i] instanceof RTDisplacedTriangle)
          src = new DisplacedTrianglePhotonSource((RTDisplacedTriangle) sceneObject[i], this);
        else if (sceneObject[i] instanceof RTEllipsoid)
          src = new EllipsoidPhotonSource((RTEllipsoid) sceneObject[i], this);
        else if (sceneObject[i] instanceof RTSphere)
          src = new EllipsoidPhotonSource((RTSphere) sceneObject[i], this);
        else if (sceneObject[i] instanceof RTCylinder)
          src = new CylinderPhotonSource((RTCylinder) sceneObject[i], this);
        else
          continue;
        if (src.getTotalIntensity() > 0.0)
          sources.addElement(src);
      }
    sources.addElement(new EnvironmentPhotonSource(theScene, bounds));
    PhotonSource src[] = new PhotonSource [sources.size()];
    sources.copyInto(src);
    map.generatePhotons(src);
  }
  
  /** Main method in which the image is rendered. */

  public void run()
  {
    try
    {
      PixelInfo tempPixel = new PixelInfo();
      RGBColor col = color[0];
      int count, lastUpdated = 0;
      long updateTime = System.currentTimeMillis();
      Thread thisThread = Thread.currentThread();

      listener.statusChanged("Processing Scene");
      buildScene(theScene, theCamera);
      if (renderThread != thisThread)
        return;
      buildTree();
      buildPhotonMap();
      listener.statusChanged("Rendering");
      for (int i = 0; i < pixel.length; i++)
        pixel[i] = 0;

      // First construct vectors to define the view.

      viewpoint = theCamera.getCameraCoordinates().getOrigin();
      Point p = new Point(width/2, height/2);
      center = theCamera.convertScreenToWorld(p, focalDist);
      cameraDir = center.minus(viewpoint);
      cameraDir.normalize();
      p.x++;
      hvec = theCamera.convertScreenToWorld(p, focalDist).minus(center);
      p.x--;
      p.y++;
      vvec = theCamera.convertScreenToWorld(p, focalDist).minus(center);
      p.y--;
      smoothScale = smoothing*hvec.length()/focalDist;
      dofScale = (depthOfField == 0.0 ? 0.0 : 0.25*0.01*height*focalDist/depthOfField);

      // If we are only using one ray/pixel, everything is simple.

      if (maxRays == 1)
        {
          rtWidth = width;
          rtHeight = height;
          for (int i = 0; i < height; i++)
            {
              for (int j = 0; j < width; j++)
                {
                  tempPixel.clear();
                  tempPixel.depth = (float) spawnEyeRay(j, i, 0, 1);
                  tempPixel.add(col, (float) transparency[0]);
                  recordPixel(j, i, tempPixel);
                  if (renderThread != thisThread)
                    return;
                }
              if (System.currentTimeMillis()-updateTime > 5000)
                {
                  imageSource.newPixels();
                  listener.imageUpdated(img);
                  lastUpdated = i;
                  updateTime = System.currentTimeMillis();
                }
            }
          imageSource.newPixels();
          finish();
          return;
        }

      // We need to adaptively decide how many rays to use for each pixel.  To save memory,
      // we only deal with six rows at a time.  Begin by sending minRays for each pixel.  If
      // the results are not sufficiently converged for a given pixel, double the number of
      // rays for that pixel, and every adjacent pixel.  Repeat until everything converges,
      // or we reach maxRays.

      rtWidth = 2*width+2;
      rtHeight = 2*height+2;
      hvec.scale(0.5);
      vvec.scale(0.5);
      smoothScale *= 0.5;
      dofScale *= 2.0;
      PixelInfo pix[][] = new PixelInfo [6][rtWidth];
      for (int i = 0; i < pix.length; i++)
        for (int j = 0; j < pix[i].length; j++)
          pix[i][j] = new PixelInfo();
      int minPerSubpixel = minRays/4, maxPerSubpixel = maxRays/4;
      for (int i = 0; i < height-1; i++)
        {
          // Keep refining the pixels in the current set of six rows until they converge, or
          // we reach maxRays.

          boolean done = false;
          for (count = minPerSubpixel; count <= maxPerSubpixel && !done; count *= 2)
            {
              // Send out more rays through any pixels which are marked as needing it.

              for (int m = 0; m < 6; m++)
                for (int j = 0; j < rtWidth; j++)
                  {
                    PixelInfo thisPixel = pix[m][j];
                    thisPixel.converged = true;
                    if (thisPixel.needsMore)
                      {
                        tempPixel.clear();
                        int baseNum = (m&1)*8+(j&1)*4;
                        int numNeeded = count-thisPixel.raysSent;
                        for (int k = thisPixel.raysSent; k < count; k++)
                          {
                            float dist = (float) spawnEyeRay(j, 2*i+m, baseNum+k, numNeeded);
                            if (k < count/2)
                            {
                              thisPixel.add(col, (float) transparency[0]);
                              if (dist < thisPixel.depth)
                                thisPixel.depth = dist;
                            }
                            else
                            {
                              tempPixel.add(col, (float) transparency[0]);
                              if (dist < tempPixel.depth)
                                tempPixel.depth = dist;
                            }
                          }
                        if (count > 1)
                          thisPixel.converged = thisPixel.matches(tempPixel, COLOR_THRESH_ABS, COLOR_THRESH_REL);
                        thisPixel.add(tempPixel);
                        if (renderThread != thisThread)
                          return;
                      }
                  }

              // If we have only sent out one ray per subpixel, we cannot yet judge the convergence of
              // each one.  Instead, compare each pixel to its neighbors and use that to decide where
              // we need more.

              if (count == 1)
                for (int m = 0; m < 5; m++)
                  for (int j = 0; j < rtWidth-1; j++)
                    {
                      if (!pix[m][j].matches(pix[m+1][j], COLOR_THRESH_ABS, COLOR_THRESH_REL))
                        pix[m][j].converged = pix[m+1][j].converged = false;
                      if (!pix[m][j].matches(pix[m][j+1], COLOR_THRESH_ABS, COLOR_THRESH_REL))
                        pix[m][j].converged = pix[m][j+1].converged = false;
                    }

              // If a pixel has not yet converged, mark that pixel and all of its neighbors
              // to get more rays.

              for (int m = 0; m < 6; m++)
                for (int j = 0; j < rtWidth; j++)
                  pix[m][j].needsMore = false;
              done = true;
              for (int m = 0; m < 6; m++)
                for (int j = 0; j < rtWidth; j++)
                  if (!pix[m][j].converged)
                    {
                      done = false;
                      pix[m][j].needsMore = true;
                      if (m > 0)
                        pix[m-1][j].needsMore = true;
                      if (m < 5)
                        pix[m+1][j].needsMore = true;
                      if (j > 0)
                        pix[m][j-1].needsMore = true;
                      if (j < rtWidth-1)
                        pix[m][j+1].needsMore = true;
                    }
            }

          // Copy the colors into the image, and update the image if enough time has elapsed.

          recordRow(pix, tempPixel, i);
          if (System.currentTimeMillis()-updateTime > 5000)
            {
              imageSource.newPixels();
              listener.imageUpdated(img);
              lastUpdated = i;
              updateTime = System.currentTimeMillis();
            }

          // Rotate the temporary pixel buffer by two rows.

          PixelInfo temp1[] = pix[0], temp2[] = pix[1];
          for (int j = 0; j < 4; j++)
            pix[j] = pix[j+2];
          pix[4] = temp1;
          pix[5] = temp2;
          for (int j = 0; j < rtWidth; j++)
            {
              pix[4][j].clear();
              pix[5][j].clear();
            }
          done = false;
        }

      // Copy the final row of pixels into the image.

      recordRow(pix, tempPixel, height-1);

      // All done.  Send the final image.

      imageSource.newPixels();
      finish();
    }
    catch(NullPointerException npe)
    {
      // npe.printStackTrace();
      setAllNull();
    }
    catch(Throwable e)
    {
      e.printStackTrace();
      //finish();
      setAllNull();
    }

  }
  
  /** Record a row of pixels into the image. */
  
  private void recordRow(PixelInfo pix[][], PixelInfo tempPixel, int row)
  {
    for (int i = 0; i < width; i++)
      {
        int x = i*2+1;
        tempPixel.copy(pix[1][x]);
        tempPixel.add(pix[1][x+1]);
        tempPixel.add(pix[2][x]);
        tempPixel.add(pix[2][x+1]);
        if (antialiasLevel == 2)
          {
            tempPixel.add(tempPixel);
            tempPixel.add(pix[0][x]);
            tempPixel.add(pix[0][x+1]);
            tempPixel.add(pix[3][x]);
            tempPixel.add(pix[3][x+1]);
            tempPixel.add(pix[1][x-1]);
            tempPixel.add(pix[2][x-1]);
            tempPixel.add(pix[1][x+2]);
            tempPixel.add(pix[2][x+2]);
          }
        recordPixel(i, row, tempPixel);
      }
  }

  private void recordPixel(int x, int y, PixelInfo pix)
  {
    int index = x+y*width;
    pixel[index] = pix.calcARGB();
    if (floatImage == null)
      return;
    float ninv = 1.0f/pix.raysSent;
    floatImage[0][index] = pix.red*ninv;
    floatImage[1][index] = pix.green*ninv;
    floatImage[2][index] = pix.blue*ninv;
    floatImage[3][index] = 1.0f-pix.transparency*ninv;
    if (depthImage != null)
      depthImage[index] = pix.depth;
  }

  /** This routine is called when rendering is finished.  It sets variables to null and
     runs a garbage collection. */

  private void finish()
  {
    RenderListener rl = listener;
    setAllNull();
    System.out.println("Raytracer.finish "+this+" "+rl);
    if (rl != null)
      {
        ComplexImage im = new ComplexImage(img);
        if (floatImage != null)
          {
            im.setComponentValues(ComplexImage.RED, floatImage[0]);
            im.setComponentValues(ComplexImage.GREEN, floatImage[1]);
            im.setComponentValues(ComplexImage.BLUE, floatImage[2]);
            im.setComponentValues(ComplexImage.ALPHA, floatImage[3]);
          }
        if (depthImage != null)
          im.setComponentValues(ComplexImage.DEPTH, depthImage);
//        RenderListener rl = listener;
//        listener = null;
        rl.imageComplete(im);
      }
    System.gc();
  }

  /** This methods sets variables of the renderer to null. */
  
  protected void setAllNull()
  {
    sceneObject = null;
    light = null;
    rootNode = null;
    cameraNode = null;
    lightNode = null;
    theScene = null;
    theCamera = null;
    envMapping = null;
    renderThread = null;
    intersect = null;
    matChange = null;
    globalMap = null;
    causticsMap = null;
//    imageSource = null;
  }

  
  /** This routine sends out a new ray, starting from the viewpoint and passing through
     pixel (i, j).  Number indicates which ray this is within the pixel, and is used for
     distribution ray tracing.  The light color is returned in color[0], and the
     transparency in transparency[0]. */
  
  private double spawnEyeRay(int i, int j, int number, int outOf)
  {
    Vec3 orig = ray[0].getOrigin(), dir = ray[0].getDirection();
    double h = i-rtWidth*0.5+0.5, v = j-rtHeight*0.5+0.5;
    OctreeNode node;

    if (antialiasLevel > 0)
      {
        int rows = (int) Math.ceil(Math.sqrt(outOf));
        int cols = outOf/rows;
        int num = number%outOf;
        int row = num/cols;
        int col = num-row*cols;
        h += (col+random.nextDouble())/cols-0.5;
        v += (row+random.nextDouble())/rows-0.5;
      }
    orig.set(viewpoint);
    if (depth)
      {
	double angle, radius, dh, dv;
	
	angle = (random.nextDouble()+distrib1[number&15])*Math.PI*0.5;
	radius = (random.nextDouble()+distrib2[number&15])*dofScale;
	dh = radius*Math.cos(angle);
	dv = radius*Math.sin(angle);
	orig.x += dh*hvec.x + dv*vvec.x;
	orig.y += dh*hvec.y + dv*vvec.y;
	orig.z += dh*hvec.z + dv*vvec.z;
      }
    rayIntensity[0].setRGB(1.0f, 1.0f, 1.0f);
    dir.x = center.x + h*hvec.x + v*vvec.x - orig.x;
    dir.y = center.y + h*hvec.y + v*vvec.y - orig.y;
    dir.z = center.z + h*hvec.z + v*vvec.z - orig.z;
    dir.normalize();
    ray[0].newID();
    double distScale = 1.0/dir.dot(cameraDir);
    if (cameraNode != null)
      return distScale*spawnRay(0, cameraNode, null, null, null, null, null, number, 0.0, true, false);
    node = rootNode.findFirstNode(ray[0]);
    if (node == null)
      {
        if (transparentBackground)
          {
            transparency[0] = 1.0;
            color[0].setRGB(0.0f, 0.0f, 0.0f);
            return Float.MAX_VALUE;
          }
        if (envMode == SceneRenderInfoProvider.ENVIRON_SOLID)
          {
            color[0].copy(envColor);
            return Float.MAX_VALUE;
          }
        envMapping.getTextureSpec(ray[0].direction, surfSpec[0], 1.0, smoothScale, time, envParamValue);
        if (envMode == SceneRenderInfoProvider.ENVIRON_DIFFUSE)
          color[0].copy(surfSpec[0].diffuse);
        else
          color[0].copy(surfSpec[0].emissive);
        return Float.MAX_VALUE;
      }
    return distScale*spawnRay(0, node, null, null, null, null, null, number, 0.0, true, false);
  }

  /** This routine is called recursively to spawn new rays.  It traces the ray, spawning
      still other rays as necessary, and returns the total light incident on the ray origin
      from the specified direction.  The appropriate Ray object should be set up before 
      calling this method, and the light color is returned in the appropriate RGBColor 
      object.
     
      @param treeDepth          the depth of this ray within the ray tree
      @param node               the first octree node which the ray intersects
      @param first              the first object which the ray intersects, or null if this is not known
      @param currentMaterial    the MaterialMapping at the ray's origin (may be null)
      @param prevMaterial       the MaterialMapping the ray was passing through before entering currentMaterial
      @param currentMatTrans    the transform to local coordinates for the current material
      @param prevMatTrans       the transform to local coordinates for the previous material
      @param rayNumber          the number of the ray within the pixel (for distribution ray tracing)
      @param totalDist          the distance traveled from the viewpoint
      @param transmitted        true if this ray has only been transmitted (not reflected) since leaving the eye
      @param diffuse            true if this ray has been diffusely reflected since leaving the eye
      @return the distance to the first object hit by the ray
  */

  private double spawnRay(int treeDepth, OctreeNode node, RTObject first, MaterialMapping currentMaterial, MaterialMapping prevMaterial, Mat4 currentMatTrans, Mat4 prevMatTrans, int rayNumber, double totalDist, boolean transmitted, boolean diffuse)
  {
    RTObject second = null;
    double dist, dot, truedot, n, beta = 0.0, d;
    float fract = 0.0f;
    Vec3 intersectionPoint = pos[treeDepth], norm = normal[treeDepth], trueNorm = trueNormal[treeDepth], temp;
    boolean totalReflect = false;
    Ray r = ray[treeDepth];
    TextureSpec spec = surfSpec[treeDepth];
    MaterialMapping nextMaterial, oldMaterial;
    Mat4 nextMatTrans, oldMatTrans = null;
    RGBColor col;
    OctreeNode nextNode;

    // Find the intersection between the ray and the first object it hits.

    transparency[treeDepth] = 0.0;
    if (first != null && first.intersects(r))
      {
	first.intersectionPoint(0, intersectionPoint);
	nextNode = rootNode.findNode(intersectionPoint);
      }
    else
      {
	nextNode = traceRay(r, node);
	if (nextNode == null)
	  {
	    if (transmitted && transparentBackground)
	      {
		color[treeDepth].setRGB(0.0f, 0.0f, 0.0f);
		transparency[treeDepth] = Math.min(Math.min(rayIntensity[treeDepth].getRed(), rayIntensity[treeDepth].getGreen()), rayIntensity[treeDepth].getBlue());
		return Float.MAX_VALUE;
	      }
	    if (envMode == SceneRenderInfoProvider.ENVIRON_SOLID)
	      {
		color[treeDepth].copy(envColor);
		color[treeDepth].multiply(rayIntensity[treeDepth]);
		return Float.MAX_VALUE;
	      }
            double envSmoothing = (diffuse ? smoothScale*extraGIEnvSmoothing : smoothScale);
	    envMapping.getTextureSpec(r.direction, spec, 1.0, smoothing*envSmoothing, time, envParamValue);
	    if (envMode == SceneRenderInfoProvider.ENVIRON_DIFFUSE)
	      color[treeDepth].copy(spec.diffuse);
	    else
	      color[treeDepth].copy(spec.emissive);
	    color[treeDepth].multiply(rayIntensity[treeDepth]);
	    return Float.MAX_VALUE;
	  }
	first = intersect.first;
	second = intersect.second;
	first.intersectionPoint(0, intersectionPoint);
      }
    dist = first.intersectionDist(0);
    totalDist += dist;
    first.trueNormal(trueNorm);
    truedot = trueNorm.dot(r.getDirection());
    double texSmoothing = (diffuse ? smoothScale*extraGISmoothing : smoothScale);
    if (truedot > 0.0)
      first.intersectionProperties(spec, norm, r.getDirection(), totalDist*texSmoothing*3.0/(2.0+truedot));
    else
      first.intersectionProperties(spec, norm, r.getDirection(), totalDist*texSmoothing*3.0/(2.0-truedot));
    
    // Get the direct lighting contribution, and adjust the ray intensity based on the 
    // material it is passing through.
    
    getDirectLight(intersectionPoint, norm, (truedot<0.0), r.getDirection(), treeDepth, nextNode, rayNumber, totalDist, currentMaterial, prevMaterial, currentMatTrans, prevMatTrans, diffuse);
    if (currentMaterial != null)
      {
        propagateRay(r, node, dist, currentMaterial, prevMaterial, currentMatTrans, prevMatTrans, tempColor, rayIntensity[treeDepth], treeDepth, totalDist);
        color[treeDepth].multiply(rayIntensity[treeDepth]);
	color[treeDepth].add(tempColor);
      }
    else if (fog)
      {
	fract = (float) Math.exp(-dist/fogDist);
	rayIntensity[treeDepth].scale(fract);
        color[treeDepth].multiply(rayIntensity[treeDepth]);
	tempColor.copy(fogColor);
	tempColor.scale(1.0f-fract);
	color[treeDepth].add(tempColor);
      }
    else
      color[treeDepth].multiply(rayIntensity[treeDepth]);

    // Determine which types of rays to spawn.
    
    if (treeDepth == maxRayDepth-1)
      return dist;
    boolean spawnSpecular = false, spawnTransmitted = false, spawnDiffuse = false;
    float specularScale = 1.0f, transmittedScale = 1.0f, diffuseScale = 1.0f;
    col = rayIntensity[treeDepth];
    if (roulette)
      {
        // Russian Roulette sampling is enabled: randomly decide whether to spawn a
        // ray of each type.
        
        float prob = (col.getRed()*spec.specular.getRed() +
            col.getGreen()*spec.specular.getGreen() +
            col.getBlue()*spec.specular.getBlue())/3.0f;
        if (prob > random.nextFloat())
          {
            spawnSpecular = true;
            specularScale = 1.0f/prob;
          }
        prob = (col.getRed()*spec.transparent.getRed() +
            col.getGreen()*spec.transparent.getGreen() +
            col.getBlue()*spec.transparent.getBlue())/3.0f;
        if (prob > random.nextFloat())
          {
            spawnTransmitted = true;
            transmittedScale = 1.0f/prob;
          }
        if (giMode == GI_MONTE_CARLO || (giMode == GI_HYBRID && !diffuse))
          {
            prob = (col.getRed()*spec.diffuse.getRed() +
                col.getGreen()*spec.diffuse.getGreen() +
                col.getBlue()*spec.diffuse.getBlue())/3.0f;
            if (prob > random.nextFloat())
              {
                spawnDiffuse = true;
                diffuseScale = 1.0f/prob;
              }
          }
      }
    else
      {
        // Russian Roulette sampling is disabled.  Always spawn rays whenever appropriate.
        
        spawnSpecular = (col.getRed()*spec.specular.getRed() > minRayIntensity ||
            col.getGreen()*spec.specular.getGreen() > minRayIntensity ||
            col.getBlue()*spec.specular.getBlue() > minRayIntensity);
        spawnTransmitted = (col.getRed()*spec.transparent.getRed() > minRayIntensity ||
            col.getGreen()*spec.transparent.getGreen() > minRayIntensity ||
            col.getBlue()*spec.transparent.getBlue() > minRayIntensity);
        if (giMode == GI_MONTE_CARLO || (giMode == GI_HYBRID && !diffuse))
          spawnDiffuse = (col.getRed()*spec.diffuse.getRed() > minRayIntensity ||
              col.getGreen()*spec.diffuse.getGreen() > minRayIntensity ||
              col.getBlue()*spec.diffuse.getBlue() > minRayIntensity);
      }
    
    // Now spawn the rays.
    
    dot = norm.dot(r.getDirection());
    col = rayIntensity[treeDepth+1];
    if (spawnTransmitted)
      {
        // Spawn a transmitted ray.

        col.copy(rayIntensity[treeDepth]);
        col.multiply(spec.transparent);
        col.scale(transmittedScale);
        ray[treeDepth+1].getOrigin().set(intersectionPoint);
        temp = ray[treeDepth+1].getDirection();
        if (first.getMaterialMapping() == null)
          {
            // Not a solid object, so the bulk material does not change.
            
            temp.set(r.getDirection());
            nextMaterial = currentMaterial;
            nextMatTrans = currentMatTrans;
            oldMaterial = prevMaterial;
            oldMatTrans = prevMatTrans;
          }
        else if (dot < 0.0)
          {
            // Entering an object.

            nextMaterial = first.getMaterialMapping();
            nextMatTrans = first.toLocal();
            oldMaterial = currentMaterial;
            oldMatTrans = currentMatTrans;
            if (currentMaterial == null)
              n = nextMaterial.indexOfRefraction()/1.0;
            else
              n = nextMaterial.indexOfRefraction()/currentMaterial.indexOfRefraction();
            beta = -(dot+Math.sqrt(n*n-1.0+dot*dot));
            temp.set(norm);
            temp.scale(beta);
            temp.add(r.getDirection());
            temp.scale(1.0/n);
          }
        else
          {
            // Exiting an object.

            if (currentMaterial == first.getMaterialMapping())
              {
                nextMaterial = prevMaterial;
                nextMatTrans = prevMatTrans;
                oldMaterial = null;
                if (nextMaterial == null)
                  n = 1.0/currentMaterial.indexOfRefraction();
                else
                  n = nextMaterial.indexOfRefraction()/currentMaterial.indexOfRefraction();
              }
            else
              {
                nextMaterial = currentMaterial;
                nextMatTrans = currentMatTrans;
                if (prevMaterial == first.getMaterialMapping())
                  oldMaterial = null;
                else
                  {
                    oldMaterial = prevMaterial;
                    oldMatTrans = prevMatTrans;
                  }
                n = 1.0;
              }
            beta = dot-Math.sqrt(n*n-1.0+dot*dot);
            temp.set(norm);
            temp.scale(-beta);
            temp.add(r.getDirection());
            temp.scale(1.0/n);
          }
        if (Double.isNaN(beta))
          totalReflect = true;
        else
          {
            d = (truedot > 0.0 ? temp.dot(trueNorm) : -temp.dot(trueNorm));
            if (d < 0.0)
              {
                // Make sure it comes out the correct side.
            
                d += TOL;
                temp.x -= d*trueNorm.x;
                temp.y -= d*trueNorm.y;
                temp.z -= d*trueNorm.z;
                temp.normalize();
              }
            ray[treeDepth+1].newID();
            if (gloss)
              randomizeDirection(temp, norm, spec.cloudiness, rayNumber+treeDepth+1);
            spawnRay(treeDepth+1, nextNode, second, nextMaterial, oldMaterial, nextMatTrans, oldMatTrans, rayNumber, totalDist, transmitted, diffuse);
            color[treeDepth].add(color[treeDepth+1]);
            if (transmitted && transparentBackground)
              transparency[treeDepth] = transparency[treeDepth+1];
          }
      }
    if (spawnSpecular || totalReflect)
      {
        // Spawn a reflection ray.

        col.copy(spec.specular);
        col.scale(specularScale);
        if (totalReflect)
          col.add(spec.transparent.getRed()*transmittedScale, spec.transparent.getGreen()*transmittedScale, spec.transparent.getBlue()*transmittedScale);
        col.multiply(rayIntensity[treeDepth]);
        temp = ray[treeDepth+1].getDirection();
        temp.set(norm);
        temp.scale(-2.0*dot);
        temp.add(r.getDirection());
        d = (truedot > 0.0 ? temp.dot(trueNorm) : -temp.dot(trueNorm));
        if (d >= 0.0)
          {
            // Make sure it comes out the correct side.
            
            d += TOL;
            temp.x += d*trueNorm.x;
            temp.y += d*trueNorm.y;
            temp.z += d*trueNorm.z;
            temp.normalize();
          }
        ray[treeDepth+1].getOrigin().set(intersectionPoint);
        ray[treeDepth+1].newID();
        if (gloss)
          randomizeDirection(temp, norm, spec.roughness, rayNumber+treeDepth+1);
        spawnRay(treeDepth+1, nextNode, null, currentMaterial, prevMaterial, currentMatTrans, prevMatTrans, rayNumber, totalDist, false, diffuse);
        color[treeDepth].add(color[treeDepth+1]);
      }
    if (spawnDiffuse)
      {
        // Spawn a diffusely reflected ray.

        col.copy(spec.diffuse);
        col.multiply(rayIntensity[treeDepth]);
        col.scale(0.5f*diffuseScale);
        temp = ray[treeDepth+1].getDirection();
        do
          {
            temp.set(0.0, 0.0, 0.0);
            randomizePoint(temp, 1.0, rayNumber+treeDepth+1);
            temp.normalize();
            d = temp.dot(trueNorm) * (truedot > 0.0 ? 1.0 : -1.0);
          } while (random.nextDouble() > (d < 0.0 ? -d : d));
        if (d > 0.0)
          {
            // Make sure it comes out the correct side.
            
            temp.scale(-1.0);
          }
        ray[treeDepth+1].getOrigin().set(intersectionPoint);
        ray[treeDepth+1].newID();
        spawnRay(treeDepth+1, nextNode, null, currentMaterial, prevMaterial, currentMatTrans, prevMatTrans, rayNumber, totalDist, false, true);
        color[treeDepth].add(color[treeDepth+1]);
      }
    return dist;
  }

  /** Find the direct lighting contribution to the surface color.  The surface properties for the given point
      should be in surfSpec[treeDepth], and the resulting color is returned in color[treeDepth].
      @param pos                the point for which light is being calculated
      @param normal             the local surface normal
      @param front              true if the surface is being viewed from the front
      @param viewDir            the direction from which the surface is being viewed
      @param treeDepth          the current ray tree depth
      @param node               the octree node containing pos
      @param rayNumber          the number of the ray within the pixel (for distribution ray tracing)
      @param totalDist          the distance traveled from the viewpoint
      @param currentMaterial    the MaterialMapping at the point (may be null)
      @param prevMaterial       the MaterialMapping the ray was passing through before entering currentMaterial
      @param currentMatTrans    the transform to local coordinates for the current material
      @param prevMatTrans       the transform to local coordinates for the previous material
      @param diffuse            true if this ray has been diffusely reflected since leaving the eye
  */

  void getDirectLight(Vec3 pos, Vec3 normal, boolean front, Vec3 viewDir, int treeDepth, OctreeNode node, int rayNumber, double totalDist, MaterialMapping currentMaterial, MaterialMapping prevMaterial, Mat4 currentMatTrans, Mat4 prevMatTrans, boolean diffuse)
  {
    int i;
    RGBColor lightColor = color[treeDepth+1], finalColor = color[treeDepth];
    TextureSpec spec = surfSpec[treeDepth];
    Vec3 h, lightPos, dir;
    Ray r = ray[treeDepth+1];
    double sign, dist, distToLight = 0.0, fatt = 0.0, dot;
    boolean hilight;
    Light lt;

    // Start with the ambient and emissive contributions.

    finalColor.copy(ambColor);
    finalColor.multiply(spec.diffuse);
    finalColor.add(spec.emissive);
    
    // If appropriate, get the light from photon maps.
    
    if (giMode == GI_HYBRID && diffuse)
      {
        globalMap.getLight(pos, spec, normal, viewDir, front, lightColor);
        finalColor.add(lightColor);
        return;
      }
    if (giMode == GI_PHOTON)
      {
        globalMap.getLight(pos, spec, normal, viewDir, front, lightColor);
        finalColor.add(lightColor);
      }
    if (caustics)
      {
        causticsMap.getLight(pos, spec, normal, viewDir, front, lightColor);
        finalColor.add(lightColor);
      }

    // Now loop over the list of lights.

    r.getOrigin().set(pos);
    dir = r.getDirection();
    sign = front ? 1.0 : -1.0;
    hilight = (spec.hilight.getRed() != 0.0 || spec.hilight.getGreen() != 0.0 || spec.hilight.getBlue() != 0.0);
    for (i = light.length-1; i >= 0; i--)
      {
	lt = (Light) light[i].object;
	lightPos = light[i].coords.getOrigin();
	if (lt instanceof PointLight)
	  {
	    dir.set(lightPos);
	    if (penumbra)
	      randomizePoint(dir, ((PointLight) lt).getRadius(), rayNumber+treeDepth+1);
	    dir.subtract(pos);
	    distToLight = dir.length();
	    dir.normalize();
	  }
	else if (lt instanceof SpotLight)
	  {
	    dir.set(lightPos);
	    if (penumbra)
	      randomizePoint(dir, ((SpotLight) lt).getRadius(), rayNumber+treeDepth+1);
	    dir.subtract(pos);
	    distToLight = dir.length();
	    dir.normalize();
	    fatt = -dir.dot(light[i].coords.getZDirection());
	    if (fatt < ((SpotLight) lt).getAngleCosine())
	      continue;
	  }
	else if (lt instanceof DirectionalLight)
	  {
	    dir.set(light[i].coords.getZDirection());
	    dir.scale(-1.0);
	    distToLight = Double.MAX_VALUE;
	  }
	r.newID();

	// Now scan through the list of objects, and see if the light is blocked.

	if (lt.isAmbient())
	  dot = 1.0;
	else
	  dot = sign*dir.dot(normal);
	if (dot > 0.0)
          {
	    lt.getLight(lightColor, (float) distToLight);
            if (lt instanceof SpotLight)
              lightColor.scale(Math.pow(fatt, ((SpotLight) lt).getExponent()));
            if (lightColor.getRed()*(spec.diffuse.getRed()*dot+spec.hilight.getRed()) < minRayIntensity &&
                lightColor.getGreen()*(spec.diffuse.getGreen()*dot+spec.hilight.getGreen()) < minRayIntensity &&
                lightColor.getBlue()*(spec.diffuse.getBlue()*dot+spec.hilight.getBlue()) < minRayIntensity)
              continue;
            if (lt.isAmbient() || traceLightRay(r, lt, treeDepth+1, node, lightNode[i], distToLight, totalDist, currentMaterial, prevMaterial, currentMatTrans, prevMatTrans))
              {
                tempColor.copy(lightColor);
                tempColor.multiply(spec.diffuse);
                tempColor.scale(dot);
                finalColor.add(tempColor);
                if (hilight)
                  {
                    dir.subtract(viewDir);
                    dir.normalize();
                    dot = sign*dir.dot(normal);
                    if (dot > 0.0)
                      {
                        tempColor.copy(lightColor);
                        tempColor.multiply(spec.hilight);
                        tempColor.scale(Math.pow(dot, (1.0-spec.roughness)*128.0+1.0));
                        finalColor.add(tempColor);
                      }
                  }
              }
          }
      }
  }

  /** Trace a ray, and determine the first object it intersects.  If it is immediately followed
     by a second object, both are returned.  To avoid creating excess objects, the results
     are returned in the global Intersection object.  node is the first octree node which
     the ray intersects.  If an intersection is found, the octree node containing the
     intersection point is returned.  Otherwise, the return value is null. */
  
  OctreeNode traceRay(Ray r, OctreeNode node)
  {
    RTObject first = null, second = null, obj[];
    double dist, firstDist = Double.MAX_VALUE, secondDist = Double.MAX_VALUE;
    Vec3 intersectionPoint = pos[maxRayDepth];
    int i;
    
    while (first == null)
      {
	obj = node.getObjects();
	for (i = obj.length-1; i >= 0; i--)
	  if (obj[i].intersects(r))
	    {
	      obj[i].intersectionPoint(0, intersectionPoint);
	      if (node.contains(intersectionPoint))
		{
		  dist = obj[i].intersectionDist(0);
		  if (dist < firstDist)
		    {
		      secondDist = firstDist;
		      second = first;
		      firstDist = dist;
		      first = obj[i];
		    }
		  else if (dist < secondDist)
		    {
		      secondDist = dist;
		      second = obj[i];
		    }
		}
	    }
	if (first == null)
	  {
	    node = node.findNextNode(r);
	    if (node == null)
	      return null;
	  }
      }
    intersect.first = first;
    intersect.dist = firstDist;
    if (secondDist-firstDist < TOL)
      intersect.second = second;
    else
      intersect.second = null;
    return node;
  }

  /** Trace a ray to a light source, and determine which objects it intersects.  If the ray
     is completely blocked, such that no light from the light source reaches the ray origin,
     return false.  Otherwise, return true, and reduce the intensity of color[treeDepth] to
     give the amount of light which reaches the ray origin.  Arguments are:
     
     r: the ray to trace
     lt: the Light to which r points
     treeDepth: the current ray tree depth
     node: the octree node containing the ray origin
     endNode: the node containing the Light, or null if the light is outside the octree
     distToLight: the distance from the ray origin to the light
     totalDist: the distance traveled from the viewpoint 
     currentMaterial: the MaterialMapping at the ray's origin (may be null)
     prevMaterial: the MaterialMapping the ray was passing through before entering currentMaterial
     currentMatTrans: the transform to local coordinates for the current material
     prevMatTrans: the transform to local coordinates for the previous material */

  boolean traceLightRay(Ray r, Light lt, int treeDepth, OctreeNode node, OctreeNode endNode, double distToLight, double totalDist, MaterialMapping currentMaterial, MaterialMapping prevMaterial, Mat4 currentMatTrans, Mat4 prevMatTrans)
  {
    RGBColor lightColor = color[treeDepth], transColor = surfSpec[treeDepth].transparent;
    double dist, fatt;
    Vec3 intersectionPoint = pos[maxRayDepth], norm = normal[maxRayDepth], trueNorm = trueNormal[maxRayDepth];
    RTObject obj[];
    int i, j, matCount = 0;
    MaterialMapping mat;
    
    do
      {
	obj = node.getObjects();
	for (i = obj.length-1; i >= 0; i--)
	  if (obj[i].intersects(r))
	    for (j = 0; ; j++)
	      {
                obj[i].intersectionPoint(j, intersectionPoint);
                if (node.contains(intersectionPoint))
                  {
                    dist = obj[i].intersectionDist(j);
                    if (dist < distToLight)
                      {
                        obj[i].trueNormal(trueNorm);
                        double angle = -trueNorm.dot(r.getDirection());
                        obj[i].intersectionTransparency(j, transColor, angle, (totalDist+dist)*smoothScale);
                        lightColor.multiply(transColor);
                        if (lightColor.getRed() < minRayIntensity && lightColor.getGreen() < minRayIntensity && lightColor.getBlue() < minRayIntensity)
                          return false;
                        mat = obj[i].getMaterialMapping();
                        if (mat != null && mat.castsShadows())
                          {
		 	    matChange[matCount].mat = mat;
		 	    matChange[matCount].toLocal = obj[i].toLocal();
			    matChange[matCount].dist = dist;
			    matChange[matCount].node = node;
		            if (matCount == 0)
			      matChange[matCount].entered = (angle > 0.0);
			    else
			      matChange[matCount].entered = !matChange[matCount-1].entered;
			    matCount++;
			  }
		      }
		  }
		if (j >= obj[i].numIntersections()-1)
		  break;
	      }
	if (node == endNode)
	  break;
	node = node.findNextNode(r);
      } while (node != null);
    if (currentMaterial == null && matCount == 0)
      return true;
    
    // The ray passes through one or more Materials, so attenuate it accordingly.
    
    sortMaterialList(matCount);
    matChange[matCount++].dist = distToLight;
    dist = 0.0;
    for (i = 0; i < matCount; i++)
      {
        if (currentMaterial != null && currentMaterial.castsShadows())
          {
            propagateLightRay(r, node, dist, matChange[i].dist, currentMaterial, lightColor, currentMatTrans, totalDist);
	    if (lightColor.getRed() < minRayIntensity && lightColor.getGreen() < minRayIntensity && lightColor.getBlue() < minRayIntensity)
	      return false;
	  }
        double n1 = (currentMaterial == null ? 1.0 : currentMaterial.indexOfRefraction());
	if (matChange[i].entered)
          {
            if (matChange[i].mat != currentMaterial)
              {
                prevMaterial = currentMaterial;
                prevMatTrans = currentMatTrans;
                currentMaterial = matChange[i].mat;
                currentMatTrans = matChange[i].toLocal;
              }
          }
        else if (matChange[i].mat == currentMaterial)
          {
            currentMaterial = prevMaterial;
            currentMatTrans = prevMatTrans;
            prevMaterial = null;
          }
        else if (matChange[i].mat == prevMaterial)
          prevMaterial = null;
        if (caustics)
          {
            double n2 = (currentMaterial == null ? 1.0 : currentMaterial.indexOfRefraction());
            if (n1 != n2)
              return false;
          }
        node = matChange[i].node;
        dist = matChange[i].dist;
      }
    return true;
  }

  /** Propagate a ray through a material, and determine how much light is removed (due to
     absorption and outscattering) and added (due to emission and inscattering). 

     r: the ray being propagated
     node: the octree node containing the ray origin
     dist: the distance between the ray origin and the endpoint
     material: the MaterialMapping through which the ray is being propagated
     prevMaterial: the MaterialMapping the ray was passing through before entering material
     currentMatTrans: the transform to local coordinates for the current material
     prevMatTrans: the transform to local coordinates for the previous material
     emitted: on exit, this contains the light emitted from the material
     filter: on exit, this is multiplied by the attenuation factor
     treeDepth: the current ray tree depth
     totalDist: the distance traveled from the viewpoint
     
     On exit, color[treeDepth] is set equal to the emitted color, and rayIntensity[treeDepth]
     is reduced by the appropriate factor to account for the absorbed light. */

  void propagateRay(Ray r, OctreeNode node, double dist, MaterialMapping material, MaterialMapping prevMaterial, Mat4 currentMatTrans, Mat4 prevMatTrans, RGBColor emitted, RGBColor filter, int treeDepth, double totalDist)
  {
    boolean scattering = material.isScattering();
    float re, ge, be, rs, gs, bs;
    float rf = filter.getRed(), gf = filter.getGreen(), bf = filter.getBlue();
    
    if (material instanceof UniformMaterialMapping && !scattering)
      {
        // The effects of the material can be computed exactly.
        
        material.getMaterialSpec(r.origin, matSpec, 0.0, time);
        RGBColor trans = matSpec.transparency, blend = matSpec.color;
        float d = (float) dist;
        
        if (trans.getRed() == 1.0f)
          rs = 1.0f;
        else
          rs = (float) Math.pow(trans.getRed(), d);
        if (trans.getGreen() == 1.0f)
          gs = 1.0f;
        else
          gs = (float) Math.pow(trans.getGreen(), d);
        if (trans.getBlue() == 1.0f)
          bs = 1.0f;
        else
          bs = (float) Math.pow(trans.getBlue(), d);
        re = blend.getRed()*rf*(1.0f-rs);
        ge = blend.getGreen()*gf*(1.0f-gs);
        be = blend.getBlue()*bf*(1.0f-bs);
        rf *= rs;
        gf *= gs;
        bf *= bs;
      }
    else
      {
        // Integrate the material properties by stepping along the ray.
        
        Vec3 v = ray[treeDepth+1].origin, origin = r.origin, direction = r.direction;
        double x = 0.0, newx, dx, distToScreen = theCamera.getDistToScreen(), step;
        double origx, origy, origz, dirx, diry, dirz; 

	// Find the ray origin and direction in the object's local coordinates.

	v.set(origin);
	currentMatTrans.transform(v);
	origx = v.x;
	origy = v.y;
	origz = v.z;
	v.set(direction);
	currentMatTrans.transformDirection(v);
	dirx = v.x;
	diry = v.y;
	dirz = v.z;
	
	// Do the integration.
	
        re = ge = be = 0.0f;
        step = stepSize*material.getStepSize();
        do
          {
            // Find the new point along the ray.
            
            if (antialiasLevel > 0)
              dx = step*(1.5*random.nextDouble());
            else
              dx = step;
            if (adaptive && totalDist > distToScreen)
              dx *= totalDist/distToScreen;
            newx = x+dx;
            if (newx > dist)
              {
                dx = dist-x;
                x = dist;
              }
            else
              x = newx;
            totalDist += dx;
            v.set(origx+dirx*x, origy+diry*x, origz+dirz*x);
            
            // Find the material properties at that point.

            material.getMaterialSpec(v, matSpec, dx, time);
            RGBColor trans = matSpec.transparency, blend = matSpec.color;
            
            // Update the total emission and transmission.
            
            if (trans.getRed() == 1.0f)
              rs = 1.0f;
            else
              rs = (float) Math.pow(trans.getRed(), dx);
            if (trans.getGreen() == 1.0f)
              gs = 1.0f;
            else
              gs = (float) Math.pow(trans.getGreen(), dx);
            if (trans.getBlue() == 1.0f)
              bs = 1.0f;
            else
              bs = (float) Math.pow(trans.getBlue(), dx);
            re += blend.getRed()*rf*(1.0f-rs);
            ge += blend.getGreen()*gf*(1.0f-gs);
            be += blend.getBlue()*bf*(1.0f-bs);
            if (scattering)
              {
                v.set(origin.x+direction.x*x, origin.y+direction.y*x, origin.z+direction.z*x);
                while (!node.contains(v))
                  {
                    OctreeNode nextNode = node.findNextNode(r);
                    if (nextNode == null)
                      break;
                    node = nextNode;
                  }
                rayIntensity[treeDepth+1].setRGB(rf*((float) dx), gf*((float) dx), bf*((float) dx));
                rayIntensity[treeDepth+1].multiply(matSpec.scattering);
                if (rayIntensity[treeDepth+1].getRed() > minRayIntensity || 
                    rayIntensity[treeDepth+1].getGreen() > minRayIntensity || 
                    rayIntensity[treeDepth+1].getBlue() > minRayIntensity)
                  {
                    getScatteredLight(treeDepth+1, node, matSpec.eccentricity, totalDist, material, prevMaterial, currentMatTrans, prevMatTrans);
                    re += color[treeDepth+1].getRed();
                    ge += color[treeDepth+1].getGreen();
                    be += color[treeDepth+1].getBlue();
                  }
              }
            rf *= rs;
            gf *= gs;
            bf *= bs;
            if (rf < minRayIntensity && gf < minRayIntensity && bf < minRayIntensity)
              {
                // Everything beyond this point makes an insignificant contribution, so
                // just stop now.
              
                rf = gf = bf = 0.0f;
                break;
              }
          } while (x < dist);
      }
    
    // Set the output colors and return.
    
    emitted.setRGB(re, ge, be);
    filter.setRGB(rf, gf, bf);
  }

  /** Propagate a light ray through a Material, and determine how much light is removed.
     Arugments are:
     
     r: the ray being traced
     node: the octree node containing the point at which to start propagating
     startDist: the distance along the ray at which to start propagating
     endDist: the distance along the ray at which to stop propagating
     material: the MaterialMapping through which the ray is passing
     filter: on exit, this is multiplied by the attenuation factor
     toLocal: the transformation from world coordinates to the material's local coordinates.
     totalDist: the distance traveled from the viewpoint */

  void propagateLightRay(Ray r, OctreeNode node, double startDist, double endDist, MaterialMapping material, RGBColor filter, Mat4 toLocal, double totalDist)
  {
    float  rs, gs, bs;
    float rf = filter.getRed(), gf = filter.getGreen(), bf = filter.getBlue();
    
    if (material instanceof UniformMaterialMapping)
      {
        // The effects of the material can be computed exactly.
        
        material.getMaterialSpec(r.origin, matSpec, 0.0, time);
        RGBColor trans = matSpec.transparency;
        float d = (float) (endDist-startDist);
        
        if (trans.getRed() != 1.0f)
          rf *= (float) Math.pow(trans.getRed(), d);
        if (trans.getGreen() != 1.0f)
          gf *= (float) Math.pow(trans.getGreen(), d);
        if (trans.getBlue() != 1.0f)
          bf *= (float) Math.pow(trans.getBlue(), d);
      }
    else
      {
        // Integrate the material properties by stepping along the ray.
        
        Vec3 v = ray[maxRayDepth].origin;
        double x = startDist, newx, dx, distToScreen = theCamera.getDistToScreen(), step;
        double origx, origy, origz, dirx, diry, dirz; 

	// Find the ray origin and direction in the object's local coordinates.

	v.set(r.origin);
	toLocal.transform(v);
	origx = v.x;
	origy = v.y;
	origz = v.z;
	v.set(r.direction);
	toLocal.transformDirection(v);
	dirx = v.x;
	diry = v.y;
	dirz = v.z;
	
	// Do the integration.
	
        step = stepSize*material.getStepSize();
        do
          {
            // Find the new point along the ray.
            
            if (antialiasLevel > 0)
              dx = step*(1.5*random.nextDouble());
            else
              dx = step;
            if (adaptive && totalDist > distToScreen)
              dx *= totalDist/distToScreen;
            newx = x+dx;
            if (newx > endDist)
              {
                dx = endDist-x;
                x = endDist;
              }
            else
              x = newx;
            totalDist += dx;
            v.set(origx+dirx*x, origy+diry*x, origz+dirz*x);
            
            // Find the material properties at that point.

            material.getMaterialSpec(v, matSpec, dx, time);
            RGBColor trans = matSpec.transparency;
            
            // Update the total emission and transmission.
            
            if (trans.getRed() != 1.0f)
              rf *= (float) Math.pow(trans.getRed(), dx);
            if (trans.getGreen() != 1.0f)
              gf *= (float) Math.pow(trans.getGreen(), dx);
            if (trans.getBlue() != 1.0f)
              bf *= (float) Math.pow(trans.getBlue(), dx);
            if (rf < minRayIntensity && gf < minRayIntensity && bf < minRayIntensity)
              {
                // Everything beyond this point makes an insignificant contribution, so
                // just stop now.
              
                rf = gf = bf = 0.0f;
                break;
              }
          } while (x < endDist);
      }
    
    // Set the output colors and return.
    
    filter.setRGB(rf, gf, bf);
  }
  
  /** Find the light being scattered by a point in scattering material.  Arguments are:

     treeDepth: the current ray tree depth
     node: the octree node containing the point
     rayNumber: the number of the ray within the pixel (for distribution ray tracing)
     totalDist: the distance traveled from the viewpoint
     currentMaterial: the MaterialMapping through which the ray is being propagated
     prevMaterial: the MaterialMapping the ray was passing through before entering material
     currentMatTrans: the transform to local coordinates for the current material
     prevMatTrans: the transform to local coordinates for the previous material
     
     The surface properties for the given point should be in surfSpec[treeDepth-1], and 
     the resulting color is returned in color[treeDepth-1]. */

  void getScatteredLight(int treeDepth, OctreeNode node, double eccentricity, double totalDist, MaterialMapping currentMaterial, MaterialMapping prevMaterial, Mat4 currentMatTrans, Mat4 prevMatTrans)
  {
    int i;
    RGBColor filter = rayIntensity[treeDepth], lightColor = color[treeDepth];
    Ray r = ray[treeDepth];
    Vec3 lightPos, dir, pos = r.origin, viewDir = ray[treeDepth-1].direction;
    double dist, distToLight = 0.0, fatt = 0.0, dot;
    double ec2 = eccentricity*eccentricity;
    boolean specular;
    Light lt;

    tempColor2.setRGB(0.0f, 0.0f, 0.0f);
    dir = r.getDirection();
    for (i = light.length-1; i >= 0; i--)
      {
	lt = (Light) light[i].object;
	lightPos = light[i].coords.getOrigin();
	if (lt instanceof PointLight)
	  {
	    dir.set(lightPos);
	    dir.subtract(pos);
	    distToLight = dir.length();
	    dir.normalize();
	  }
	else if (lt instanceof SpotLight)
	  {
	    dir.set(lightPos);
	    dir.subtract(pos);
	    distToLight = dir.length();
	    dir.normalize();
	    fatt = -dir.dot(light[i].coords.getZDirection());
	    if (fatt < ((SpotLight) lt).getAngleCosine())
	      continue;
	  }
	else if (lt instanceof DirectionalLight)
	  {
	    dir.set(light[i].coords.getZDirection());
	    dir.scale(-1.0);
	    distToLight = Double.MAX_VALUE;
	  }
	r.newID();

	// Now scan through the list of objects, and see if the light is blocked.

        lt.getLight(lightColor, (float) distToLight);
        lightColor.multiply(filter);
        if (lt instanceof SpotLight)
          lightColor.scale(Math.pow(fatt, ((SpotLight) lt).getExponent()));
        if (eccentricity != 0.0 && !lt.isAmbient())
          {
            dot = dir.dot(viewDir);
            fatt = (1.0-ec2)/Math.pow(1.0+ec2+2.0*eccentricity*dot, 1.5);
            lightColor.scale(fatt);
          }
        if (lightColor.getRed() < minRayIntensity && lightColor.getGreen() < minRayIntensity &&
            lightColor.getBlue() < minRayIntensity)
          continue;
	if (lt.isAmbient() || traceLightRay(r, lt, treeDepth, node, lightNode[i], distToLight, totalDist, currentMaterial, prevMaterial, currentMatTrans, prevMatTrans))
	  tempColor2.add(lightColor);
      }
    color[treeDepth].copy(tempColor2);
  }

  /** Add a random displacement to a vector.  The displacements are uniformly distributed
     over the volume of a sphere whose radius is given by size.  number is used for 
     distributing the displacements evenly. */

  void randomizePoint(Vec3 pos, double size, int number)
  {
    double x, y, z;
    int d;

    if (size == 0.0)
      return;

    // Pick a random vector within an octant of the unit sphere.

    do
      {
	x = random.nextDouble();
	y = random.nextDouble();
	z = random.nextDouble();
      } while (x*x + y*y + z*z > 1.0);
    x *= size;
    y *= size;
    z *= size;

    // Decide which octant of the sphere to use for this ray.

    d = distrib1[number&15];
    if (d < 2)
      x *= -1.0;
    if (d == 1 || d == 2)
      y *= -1.0;
    if ((distrib2[number&15]&1) == 0)
      z *= -1.0;  
    pos.x += x;
    pos.y += y;
    pos.z += z;
  }

  /** Given a reflected or transmitted ray, randomly alter its direction to create gloss and
     translucency effects.  dir is a unit vector in the "ideal" reflected or refracted
     direction, which on exit is overwritten with the new direction.  norm is the local
     surface normal, roughness determines how much the ray direction is altered, and number
     is used for distributing rays evenly. */

  void randomizeDirection(Vec3 dir, Vec3 norm, double roughness, int number)
  {
    double x, y, z, scale, dot1, dot2;
    int d;
    
    if (roughness == 0.0)
      return;

    // Pick a random vector within an octant of the unit sphere.

    do
      {
	x = random.nextDouble();
	y = random.nextDouble();
	z = random.nextDouble();
      } while (x*x + y*y + z*z > 1.0);
    scale = Math.pow(roughness, 1.7)*0.5;
    x *= scale;
    y *= scale;
    z *= scale;

    // Decide which octant of the sphere to use for this ray.

    d = distrib1[number&15];
    if (d < 2)
      x *= -1.0;
    if (d == 1 || d == 2)
      y *= -1.0;
    if ((distrib2[number&15]&1) == 0)
      z *= -1.0;
    dot1 = dir.dot(norm);
    dir.x += x;
    dir.y += y;
    dir.z += z;
    dot2 = 2.0*dir.dot(norm);

    // If the ray is on the wrong side of the surface, flip it back.

    if (dot1 < 0.0 && dot2 > 0.0)
      {
	dir.x -= dot2*norm.x;
	dir.y -= dot2*norm.y;
	dir.z -= dot2*norm.z;
      }
    else if (dot1 > 0.0 && dot2 < 0.0)
      {
	dir.x += dot2*norm.x;
	dir.y += dot2*norm.y;
	dir.z += dot2*norm.z;
      }
    dir.normalize();
  }
  
  /** Sort the list of MaterialIntersection objects by position along a shadow ray. 
      This is done with a simple insertion sort.  Because the list tends to be very
      short, and is in close to the correct order to begin with, this will generally
      be very fast. */
  
  private void sortMaterialList(int count)
  {
    for (int i = 1; i < count; i++)
      for (int j = i; j > 0 && matChange[j].dist < matChange[j-1].dist; j--)
        {
          MaterialIntersection temp = matChange[j-1];
          matChange[j-1] = matChange[j];
          matChange[j] = temp;
        }
  }
}