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

Program:   Visualization Toolkit
Module:    vtkHAVSVolumeMapper.h

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.

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

/* Copyright 2005, 2006 by University of Utah. */

/**
 * @class   vtkHAVSVolumeMapper
 * @brief   Hardware-Assisted Visibility Sorting unstructured grid mapper
 *
 *
 *
 * vtkHAVSVolumeMapper is a class that renders polygonal data
 * (represented as an unstructured grid) using the Hardware-Assisted
 * Visibility Sorting (HAVS) algorithm.  First the unique triangles are sorted
 * in object space, then they are sorted in image space using a fixed size
 * A-buffer implemented on the GPU called the k-buffer.  The HAVS algorithm
 * excels at rendering large datasets quickly.  The trade-off is that the
 * algorithm may produce some rendering artifacts due to an insufficient k
 * size (currently 2 or 6 is supported) or read/write race conditions.
 *
 * A built in level-of-detail (LOD) approach samples the geometry using one of
 * two heuristics (field or area).  If LOD is enabled, the amount of geometry
 * that is sampled and rendered changes dynamically to stay within the target
 * frame rate.  The field sampling method generally works best for datasets
 * with cell sizes that don't vary much in size.  On the contrary, the area
 * sampling approach gives better approximations when the volume has a lot of
 * variation in cell size.
 *
 * The HAVS algorithm uses several advanced features on graphics hardware.
 * The k-buffer sorting network is implemented using framebuffer objects
 * (FBOs) with multiple render targets (MRTs).  Therefore, only cards that
 * support these features can run the algorithm (at least an ATI 9500 or an
 * NVidia NV40 (6600)).
 *
 *
 * @attention
 * Several issues had to be addressed to get the HAVS algorithm working within
 * the vtk framework.  These additions forced the code to forsake speed for
 * the sake of compliance and robustness.
 *
 * @attention
 * The HAVS algorithm operates on the triangles that compose the mesh.
 * Therefore, before rendering, the cells are decomposed into unique triangles
 * and stored on the GPU for efficient rendering.  The use of GPU data
 * structures is only recommended if the entire geometry can fit in graphics
 * memory.  Otherwise this feature should be disabled.
 *
 * @attention
 * Another new feature is the handling of mixed data types (eg., polygonal
 * data with volume data).  This is handled by reading the z-buffer from the
 * current window and copying it into the framebuffer object for off-screen
 * rendering.  The depth test is then enabled so that the volume only appears
 * over the opaque geometry.  Finally, the results of the off-screen rendering
 * are blended into the framebuffer as a transparent, view-aligned texture.
 *
 * @attention
 * Instead of using a preintegrated 3D lookup table for storing the ray
 * integral, this implementation uses partial pre-integration.  This improves
 * the performance of dynamic transfer function updates by avoiding a costly
 * preprocess of the table.
 *
 * @attention
 * A final change to the original algorithm is the handling of non-convexities
 * in the mesh.  Due to read/write hazards that may create undesired artifacts
 * with non-convexities when using a inside/outside toggle in the fragment
 * program, another approach was employed.  To handle non-convexities, the
 * fragment shader determines if a ray-gap is larger than the max cell size
 * and kill the fragment if so.  This approximation performs rather well in
 * practice but may miss small non-convexities.
 *
 * @attention
 * For more information on the HAVS algorithm see:
 *
 * @attention
 *  "Hardware-Assisted Visibility Sorting for Unstructured Volume
 * Rendering" by S. P. Callahan, M. Ikits, J. L. D. Comba, and C. T. Silva,
 * IEEE Transactions of Visualization and Computer Graphics; May/June 2005.
 *
 * @attention
 * For more information on the Level-of-Detail algorithm, see:
 *
 * @attention
 * "Interactive Rendering of Large Unstructured Grids Using Dynamic
 * Level-of-Detail" by S. P. Callahan, J. L. D. Comba, P. Shirley, and
 * C. T. Silva, Proceedings of IEEE Visualization '05, Oct. 2005.
 *
 *
 * @par Acknowledgments:
 * This code was developed by Steven P. Callahan under the supervision
 * of Prof. Claudio T. Silva. The code also contains contributions
 * from Milan Ikits, Linh Ha, Huy T. Vo, Carlos E. Scheidegger, and
 * Joao L. D. Comba.
 *
 * @par Acknowledgments:
 * The work was supported by grants, contracts, and gifts from the
 * National Science Foundation, the Department of Energy, the Army
 * Research Office, and IBM.
 *
 * @par Acknowledgments:
 * The port of HAVS to VTK and ParaView has been primarily supported
 * by Sandia National Labs.
 *
*/

#ifndef vtkHAVSVolumeMapper_h
#define vtkHAVSVolumeMapper_h

#include "vtkRenderingVolumeModule.h" // For export macro
#include "vtkUnstructuredGridVolumeMapper.h"

#define VTK_KBUFFER_SIZE_2 0
#define VTK_KBUFFER_SIZE_6 1
#define VTK_FIELD_LEVEL_OF_DETAIL 0
#define VTK_AREA_LEVEL_OF_DETAIL 1


class vtkUnstructuredGrid;
class vtkDepthRadixSortUnstructuredGrid;
class vtkHAVSSortedFace;

class VTKRENDERINGVOLUME_EXPORT vtkHAVSVolumeMapper : public vtkUnstructuredGridVolumeMapper
{
public:
  static vtkHAVSVolumeMapper *New();
  vtkTypeMacro(vtkHAVSVolumeMapper,
                       vtkUnstructuredGridVolumeMapper);
  void PrintSelf(ostream& os, vtkIndent indent) VTK_OVERRIDE;

  //@{
  /**
   * regions by removing ray segments larger than the max cell size.
   */
  vtkSetMacro(PartiallyRemoveNonConvexities, bool);
  vtkGetMacro(PartiallyRemoveNonConvexities, bool);
  //@}

  //@{
  /**
   * Set/get the desired level of detail target time measured in frames/sec.
   */
  vtkSetMacro(LevelOfDetailTargetTime, float);
  vtkGetMacro(LevelOfDetailTargetTime, float);
  //@}

  //@{
  /**
   * Turn on/off level-of-detail volume rendering
   */
  vtkSetMacro(LevelOfDetail, bool);
  vtkGetMacro(LevelOfDetail, bool);
  //@}

  //@{
  /**
   * Set/get the current level-of-detail method
   */
  void SetLevelOfDetailMethod(int);
  vtkGetMacro(LevelOfDetailMethod, int);
  void SetLevelOfDetailMethodField()
  {this->SetLevelOfDetailMethod(VTK_FIELD_LEVEL_OF_DETAIL);}
  void SetLevelOfDetailMethodArea()
  {this->SetLevelOfDetailMethod(VTK_AREA_LEVEL_OF_DETAIL);}
  //@}

  //@{
  /**
   * Set the kbuffer size
   */
  vtkSetMacro(KBufferSize,int);
  vtkGetMacro(KBufferSize,int);
  void SetKBufferSizeTo2()
  {this->SetKBufferSize(VTK_KBUFFER_SIZE_2);}
  void SetKBufferSizeTo6()
  {this->SetKBufferSize(VTK_KBUFFER_SIZE_6);}
  //@}

  /**
   * Check hardware support for the HAVS algorithm.  Necessary
   * features include off-screen rendering, 32-bit fp textures, multiple
   * render targets, and framebuffer objects.
   * Subclasses must override this method to indicate if supported by Hardware.
   */
  virtual bool SupportedByHardware(vtkRenderer *vtkNotUsed(r))
    {return false; }

  //@{
  /**
   * Set/get whether or not the data structures should be stored on the GPU
   * for better peformance.
   */
  virtual void SetGPUDataStructures(bool) = 0;
  vtkGetMacro(GPUDataStructures, bool);
  //@}

protected:
  vtkHAVSVolumeMapper();
  ~vtkHAVSVolumeMapper() VTK_OVERRIDE;

  virtual void Initialize(vtkRenderer *ren, vtkVolume *vol) = 0;
  void InitializePrimitives(vtkVolume *vol);
  void InitializeScalars();
  void InitializeLevelOfDetail();
  void InitializeLookupTables(vtkVolume *vol);

  void FRadixSort(vtkHAVSSortedFace *array, vtkHAVSSortedFace *temp, int lo, int up);
  void FRadix(int byte, int len, vtkHAVSSortedFace *source, vtkHAVSSortedFace *dest, int *count);

  void UpdateLevelOfDetail(float targetTime);
  void PartialVisibilitySort(float *eye);
  bool CheckInitializationError();

  enum
  {
    NO_INIT_ERROR=0,
    NON_TETRAHEDRA=1,
    UNSUPPORTED_EXTENSIONS=2,
    NO_SCALARS=3,
    CELL_DATA=4,
    NO_CELLS=5
  };

  // Mesh
  float *Vertices;
  float *Scalars;
  double ScalarRange[2];
  unsigned int *Triangles;
  unsigned int *OrderedTriangles;
  vtkHAVSSortedFace *SortedFaces;
  vtkHAVSSortedFace *RadixTemp;
  float *Centers;
  unsigned int NumberOfVertices;
  unsigned int NumberOfCells;
  unsigned int NumberOfScalars;
  unsigned int NumberOfTriangles;

  // Level-Of-Detail
  unsigned int NumberOfBoundaryTriangles;
  unsigned int NumberOfInternalTriangles;
  unsigned int *BoundaryTriangles;
  unsigned int *InternalTriangles;
  unsigned int LevelOfDetailTriangleCount;
  float CurrentLevelOfDetail;
  float LevelOfDetailTargetTime;
  bool LevelOfDetail;
  int LevelOfDetailMethod;

  // K-Buffer
  int KBufferState;
  float MaxEdgeLength;
  float LevelOfDetailMaxEdgeLength;
  float UnitDistance;
  bool GPUDataStructures;
  float Diagonal;
  bool PartiallyRemoveNonConvexities;
  int KBufferSize;

  // Lookup Tables
  float *TransferFunction;
  int TransferFunctionSize;

  // State and Timing Stats
  bool Initialized;
  int InitializationError;
  int FrameNumber;
  float TotalRenderTime;
  vtkTimeStamp ColorTransferFunctionMTime;
  vtkTimeStamp AlphaTransferFunctionMTime;
  vtkTimeStamp UnstructuredGridMTime;
  vtkTimeStamp ScalarsMTime;
  vtkVolume *LastVolume;

private:
  vtkHAVSVolumeMapper(const vtkHAVSVolumeMapper&) VTK_DELETE_FUNCTION;
  void operator=(const vtkHAVSVolumeMapper&) VTK_DELETE_FUNCTION;
};
#endif
