/*=========================================================================

  Program:   Visualization Toolkit
  Module:    $RCSfile: vtkUnstructuredGridBunykRayCastFunction.h,v $

  Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
  All rights reserved.
  See Copyright.txt or http://www.kitware.com/Copyright.htm for details.

     This software is distributed WITHOUT ANY WARRANTY; without even
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
     PURPOSE.  See the above copyright notice for more information.

=========================================================================*/

// .NAME vtkUnstructuredGridBunykRayCastFunction - a superclass for ray casting functions

// .SECTION Description
// vtkUnstructuredGridBunykRayCastFunction is a concrete implementation of a
// ray cast function for unstructured grid data. This class was based on the
// paper "Simple, Fast, Robust Ray Casting of Irregular Grids" by Paul Bunyk,
// Arie Kaufmna, and Claudio Silva. This method is quite memory intensive 
// (with extra explicit copies of the data) and therefore should not be used
// for very large data. This method assumes that the input data is composed
// entirely of tetras - use vtkDataSetTriangleFilter before setting the input
// on the mapper.
//
// The basic idea of this method is as follows:
//
//   1) Enumerate the triangles. At each triangle have space for some 
//      information that will be used during rendering. This includes 
//      which tetra the triangles belong to, the plane equation and the  
//      Barycentric coefficients.
//
//   2) Keep a reference to all four triangles for each tetra.
//
//   3) At the beginning of each render, do the precomputation. This 
//      includes creating an array of transformed points (in view 
//      coordinates) and computing the view dependent info per triangle
//      (plane equations and barycentric coords in view space)
//
//   4) Find all front facing boundary triangles (a triangle is on the
//      boundary if it belongs to only one tetra). For each triangle,
//      find all pixels in the image that intersect the triangle, and
//      add this to the sorted (by depth) intersection list at each 
//      pixel.
//
//   5) For each ray cast, traverse the intersection list. At each
//      intersection, accumulate opacity and color contribution
//      per tetra along the ray until you reach an exiting triangle
//      (on the boundary). 
//

// .SECTION See Also
// vtkUnstructuredGridVolumeRayCastMapper

#ifndef __vtkUnstructuredGridBunykRayCastFunction_h
#define __vtkUnstructuredGridBunykRayCastFunction_h

#include "vtkUnstructuredGridVolumeRayCastFunction.h"

class vtkRenderer;
class vtkVolume;
class vtkUnstructuredGridVolumeRayCastMapper;
class vtkMatrix4x4;
class vtkPiecewiseFunction;
class vtkColorTransferFunction;
class vtkUnstructuredGrid;
class vtkIdList;
class vtkDoubleArray;
class vtkDataArray;

// We manage the memory for the list of intersections ourself - this is the
// storage used. We keep 10,000 elements in each array, and we can have up to 
// 1,000 arrays.
#define VTK_BUNYKRCF_MAX_ARRAYS 10000
#define VTK_BUNYKRCF_ARRAY_SIZE 10000

class VTK_VOLUMERENDERING_EXPORT vtkUnstructuredGridBunykRayCastFunction : public vtkUnstructuredGridVolumeRayCastFunction
{ 
public:
  static vtkUnstructuredGridBunykRayCastFunction *New();
  vtkTypeRevisionMacro(vtkUnstructuredGridBunykRayCastFunction,vtkUnstructuredGridVolumeRayCastFunction);
  virtual void PrintSelf(ostream& os, vtkIndent indent);

//BTX
  // Description:
  // Called by the ray cast mapper at the start of rendering
  virtual void Initialize( vtkRenderer *ren, vtkVolume   *vol );
  
  // Description:
  // Called by the ray cast mapper at the end of rendering
  virtual void Finalize();

  virtual vtkUnstructuredGridVolumeRayCastIterator *NewIterator();

  // Used to store each triangle - made public because of the 
  // templated function
  class Triangle {
  public:
    vtkIdType PointIndex[3];
    vtkIdType ReferredByTetra[2];
    double    P1X, P1Y;
    double    P2X, P2Y;
    double    Denominator;
    double    A, B, C, D;
    Triangle *Next; 
  };
  
  // Used to store each intersection for the pixel rays - made
  // public because of the templated function
  class Intersection {
  public:
    Triangle     *TriPtr;
    double        Z;
    Intersection *Next;
  };
  
  // Description:
  // Is the point x, y, in the given triangle? Public for
  // access from the templated function.
  int  InTriangle( double x, double y,
                   Triangle *triPtr );
  

  // Description:
  // Access to an internal structure for the templated method.  
  double *GetPoints() {return this->Points;}
  
  // Description:
  // Access to an internal structure for the templated method.
  vtkGetObjectMacro( ViewToWorldMatrix, vtkMatrix4x4 );
  
  // Description:
  // Access to an internal structure for the templated method.
  vtkGetVectorMacro( ImageOrigin, int, 2 );

  // Description:
  // Access to an internal structure for the templated method.
  vtkGetVectorMacro( ImageViewportSize, int, 2 );

  // Description:
  // Access to an internal structure for the templated method.
  Triangle **GetTetraTriangles () {return this->TetraTriangles;}
  
  // Description:
  // Access to an internal structure for the templated method.
  Intersection *GetIntersectionList( int x, int y ) { return this->Image[y*this->ImageSize[0] + x]; }

//ETX
  
protected:
  vtkUnstructuredGridBunykRayCastFunction();
  ~vtkUnstructuredGridBunykRayCastFunction();

  // These are cached during the initialize method so that they do not
  // need to be passed into subsequent CastRay calls.
  vtkRenderer                             *Renderer;
  vtkVolume                               *Volume;
  vtkUnstructuredGridVolumeRayCastMapper  *Mapper;
  
  // Computed during the initialize method - if something is
  // wrong (no mapper, no volume, no input, etc.) then no rendering
  // will actually be performed.
  int                                      Valid;

  // These are the transformed points
  int      NumberOfPoints;
  double  *Points;

  // This is the matrix that will take a transformed point back
  // to world coordinates
  vtkMatrix4x4 *ViewToWorldMatrix;


  // This is the intersection list per pixel in the image
  Intersection    **Image;
  
  // This is the size of the image we are computing (which does
  // not need to match the screen size)
  int               ImageSize[2];
  
  // Since we may only be computing a subregion of the "full" image,
  // this is the origin of the region we are computing. We must
  // subtract this origin from any pixel (x,y) locations before 
  // accessing the pixel in this->Image (which represents only the
  // subregion)
  int               ImageOrigin[2];
  
  // This is the full size of the image
  int               ImageViewportSize[2];

  // These are values saved for the building of the TriangleList. Basically
  // we need to check if the data has changed in some way.
  vtkUnstructuredGrid       *SavedTriangleListInput;
  vtkTimeStamp               SavedTriangleListMTime;
 
//BTX  
  // This is a memory intensive algorithm! For each tetra in the 
  // input data we create up to 4 triangles (we don't create duplicates)
  // This is the TriangleList. Then, for each tetra we keep track of
  // the pointer to each of its four triangles - this is the 
  // TetraTriangles. We also keep a duplicate list of points 
  // (transformed into view space) - these are the Points. 
  Triangle **TetraTriangles;
  Triangle  *TriangleList;

  // Compute whether a boundary triangle is front facing by
  // looking at the fourth point in the tetra to see if it is
  // in front (triangle is backfacing) or behind (triangle is
  // front facing) the plane containing the triangle.
  int  IsTriangleFrontFacing( Triangle *triPtr, vtkIdType tetraIndex );
  
  // The image contains lists of intersections per pixel - we
  // need to clear this during the initialization phase for each
  // render.
  void ClearImage();
  
  // This is the memory buffer used to build the intersection
  // lists. We do our own memory management here because allocating
  // a bunch of small elements during rendering is too slow.
  Intersection *IntersectionBuffer[VTK_BUNYKRCF_MAX_ARRAYS];
  int           IntersectionBufferCount[VTK_BUNYKRCF_MAX_ARRAYS];
  
  // This method replaces new for creating a new element - it
  // returns one from the big block already allocated (it 
  // allocates another big block if necessary)
  void         *NewIntersection();  

  // This method is used during the initialization process to
  // check the validity of the objects - missing information
  // such as the volume, renderer, mapper, etc. will be flagged
  // and reported.
  int          CheckValidity(vtkRenderer *ren,
                             vtkVolume   *vol);
  
  // This method is used during the initialization process to
  // transform the points to view coordinates
  void          TransformPoints();

  // This method is used during the initialization process to 
  // create the list of triangles if the data has changed
  void          UpdateTriangleList();
  
  // This method is used during the initialization process to
  // update the view dependent information in the triangle list
  void          ComputeViewDependentInfo();
  
  // This method is used during the initialization process to
  // compute the intersections for each pixel with the boundary
  // triangles.
  void          ComputePixelIntersections();
  
//ETX
  
private:
  vtkUnstructuredGridBunykRayCastFunction(const vtkUnstructuredGridBunykRayCastFunction&);  // Not implemented.
  void operator=(const vtkUnstructuredGridBunykRayCastFunction&);  // Not implemented.
};

#endif