text: /*=========================================================================
  
    Program:   Visualization Toolkit
    Module:    vtkModifiedBSPTree.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.
  
  =========================================================================*/
  
  /*=========================================================================
    This code is derived from an earlier work and is distributed
    with permission from, and thanks to
  
    ------------------------------------------
    Copyright (C) 1997-2000 John Biddiscombe
    Rutherford Appleton Laboratory,
    Chilton, Oxon, England
    ------------------------------------------
    Copyright (C) 2000-2004 John Biddiscombe
    Skipping Mouse Software Ltd,
    Blewbury, England
    ------------------------------------------
    Copyright (C) 2004-2009 John Biddiscombe
    CSCS - Swiss National Supercomputing Centre
    Galleria 2 - Via Cantonale
    CH-6928 Manno, Switzerland
    ------------------------------------
  =========================================================================*/
  /**
   * @class   vtkModifiedBSPTree
   * @brief   Generate axis aligned BBox tree for ray-casting and other Locator based searches
   *
   *
   * vtkModifiedBSPTree creates an evenly balanced BSP tree using a top down
   * implementation. Axis aligned split planes are found which evenly divide
   * cells into two buckets. Generally a split plane will intersect some cells
   * and these are usually stored in both child nodes of the current parent.
   * (Or split into separate cells which we cannot consider in this case).
   * Storing cells in multiple buckets creates problems associated with multiple
   * tests against rays and increases the required storage as complex meshes
   * will have many cells straddling a split plane (and further splits may
   * cause multiple copies of these).
   *
   * During a discussion with Arno Formella in 1998 he suggested using
   * a third child node to store objects which straddle split planes. I've not
   * seen this published (Yes! - see below), but thought it worth trying. This
   * implementation of the BSP tree creates a third child node for storing cells
   * laying across split planes, the third cell may overlap the other two, but the
   * two 'proper' nodes otherwise conform to usual BSP rules.
   *
   * The advantage of this implementation is cells only ever lie in one node
   * and mailbox testing is avoided. All BBoxes are axis aligned and a ray cast
   * uses an efficient search strategy based on near/far nodes and rejects
   * all BBoxes using simple tests.
   *
   * For fast raytracing, 6 copies of cell lists are stored in each leaf node
   * each list is in axis sorted order +/- x,y,z and cells are always tested
   * in the direction of the ray dominant axis. Once an intersection is found
   * any cell or BBox with a closest point further than the I-point can be
   * instantly rejected and raytracing stops as soon as no nodes can be closer
   * than the current best intersection point.
   *
   * The addition of the 'middle' node upsets the optimal balance of the tree,
   * but is a minor overhead during the raytrace. Each child node is contracted
   * such that it tightly fits all cells inside it, enabling further ray/box
   * rejections.
   *
   * This class is intended for persons requiring many ray tests and is optimized
   * for this purpose. As no cell ever lies in more than one leaf node, and parent
   * nodes do not maintain cell lists, the memory overhead of the sorted cell
   * lists is 6*num_cells*4 for 6 lists of ints, each num_cells in length.
   * The memory requirement of the nodes themselves is usually of minor
   * significance.
   *
   * Subdivision is controlled by MaxCellsPerNode - any node with more than
   * this number will be subdivided providing a good split plane can be found and
   * the max depth is not exceeded.
   *
   * The average cells per leaf will usually be around half the MaxCellsPerNode,
   * though the middle node is usually sparsely populated and lowers the average
   * slightly. The middle node will not be created when not needed.
   * Subdividing down to very small cells per node is not generally suggested
   * as then the 6 stored cell lists are effectively redundant.
   *
   * Values of MaxCellsPerNode of around 16->128 depending on dataset size will
   * usually give good results.
   *
   * Cells are only sorted into 6 lists once - before tree creation, each node
   * segments the lists and passes them down to the new child nodes whilst
   * maintaining sorted order. This makes for an efficient subdivision strategy.
   *
   * @warning
   * vtkModifiedBSPTree utilizes the following parent class parameters:
   * - Level                       (default 8)
   * - MaxLevel                    (default 8)
   * - NumberOfCellsPerNode        (default 32)
   * - UseExistingSearchStructure  (default false)
   * - CacheCellBounds             (default true)
   *
   * vtkModifiedBSPTree does NOT utilize the following parameters:
   * - Automatic
   * - Tolerance
   * - RetainCellLists
   *
   * NB. The following reference has been sent to me
   * \code
   *   @Article{formella-1995-ray,
   *     author =     "Arno Formella and Christian Gill",
   *     title =      "{Ray Tracing: A Quantitative Analysis and a New
   *                   Practical Algorithm}",
   *     journal =    "{The Visual Computer}",
   *     year =       "{1995}",
   *     month =       dec,
   *     pages =      "{465--476}",
   *     volume =     "{11}",
   *     number =     "{9}",
   *     publisher =  "{Springer}",
   *     keywords =   "{ray tracing, space subdivision, plane traversal,
   *                    octree, clustering, benchmark scenes}",
   *     annote =     "{We present a new method to accelerate the process of
   *                    finding nearest ray--object intersections in ray
   *                    tracing. The algorithm consumes an amount of memory
   *                    more or less linear in the number of objects. The basic
   *                    ideas can be characterized with a modified BSP--tree
   *                    and plane traversal. Plane traversal is a fast linear
   *                    time algorithm to find the closest intersection point
   *                    in a list of bounding volumes hit by a ray. We use
   *                    plane traversal at every node of the high outdegree
   *                    BSP--tree. Our implementation is competitive to fast
   *                    ray tracing programs. We present a benchmark suite
   *                    which allows for an extensive comparison of ray tracing
   *                    algorithms.}",
   *   }
   * \endcode
   *
   * @par Thanks:
   *  John Biddiscombe for developing and contributing this class
   *
   * @todo
   * -------------
   * Implement intersection heap for testing rays against transparent objects
   *
   * @par Style:
   * --------------
   * This class is currently maintained by J. Biddiscombe who has specially
   * requested that the code style not be modified to the Kitware standard.
   * Please respect the contribution of this class by keeping the style
   * as close as possible to the author's original.
   *
   * @sa
   * vtkAbstractCellLocator vtkCellLocator vtkStaticCellLocator vtkCellTreeLocator vtkOBBTree
   */
  
  #ifndef vtkModifiedBSPTree_h
  #define vtkModifiedBSPTree_h
  
  #include "vtkAbstractCellLocator.h"
  #include "vtkFiltersFlowPathsModule.h" // For export macro
  #include "vtkSmartPointer.h"           // required because it is nice
  
  class Sorted_cell_extents_Lists;
  class BSPNode;
  class vtkGenericCell;
  class vtkIdList;
  class vtkIdListCollection;
  
  class VTKFILTERSFLOWPATHS_EXPORT vtkModifiedBSPTree : public vtkAbstractCellLocator
  {
  public:
    ///@{
    /**
     * Standard methods to print and obtain type-related information.
     */
    vtkTypeMacro(vtkModifiedBSPTree, vtkAbstractCellLocator);
    void PrintSelf(ostream& os, vtkIndent indent) override;
    ///@}
  
    /**
     * Construct with maximum 32 cells per node. (average 16->31)
     */
    static vtkModifiedBSPTree* New();
  
    // Re-use any superclass signatures that we don't override.
    using vtkAbstractCellLocator::FindCell;
    using vtkAbstractCellLocator::IntersectWithLine;
  
    /**
     * Return intersection point (if any) AND the cell which was intersected by
     * the finite line. The cell is returned as a cell id and as a generic cell.
     *
     * For other IntersectWithLine signatures, see vtkAbstractCellLocator.
     */
    int IntersectWithLine(const double p1[3], const double p2[3], double tol, double& t, double x[3],
      double pcoords[3], int& subId, vtkIdType& cellId, vtkGenericCell* cell) override;
  
    /**
     * Take the passed line segment and intersect it with the data set.
     * The return value of the function is 0 if no intersections were found.
     * For each intersection with the bounds of a cell or with a cell (if a cell is provided),
     * the points and cellIds have the relevant information added sorted by t.
     * If points or cellIds are nullptr pointers, then no information is generated for that list.
     *
     * For other IntersectWithLine signatures, see vtkAbstractCellLocator.
     */
    int IntersectWithLine(const double p1[3], const double p2[3], const double tol, vtkPoints* points,
      vtkIdList* cellIds, vtkGenericCell* cell) override;
  
    /**
     * Take the passed line segment and intersect it with the data set.
     * For each intersection with the bounds of a cell, the cellIds
     * have the relevant information added sort by t. If cellIds is nullptr
     * pointer, then no information is generated for that list.
     *
     * Reimplemented from vtkAbstractCellLocator to showcase that it's a supported function.
     */
    void FindCellsAlongLine(
      const double p1[3], const double p2[3], double tolerance, vtkIdList* cellsIds) override
    {
      this->Superclass::FindCellsAlongLine(p1, p2, tolerance, cellsIds);
    }
  
    /**
     * Find the cell containing a given point. returns -1 if no cell found
     * the cell parameters are copied into the supplied variables, a cell must
     * be provided to store the information.
     *
     * For other FindCell signatures, see vtkAbstractCellLocator.
     */
    vtkIdType FindCell(double x[3], double vtkNotUsed(tol2), vtkGenericCell* GenCell, int& subId,
      double pcoords[3], double* weights) override;
  
    /**
     * After subdivision has completed, one may wish to query the tree to find
     * which cells are in which leaf nodes. This function returns a list
     * which holds a cell Id list for each leaf node.
     */
    vtkIdListCollection* GetLeafNodeCellInformation();
  
    /**
     * Generate BBox representation of all leaf nodes
     */
    virtual void GenerateRepresentationLeafs(vtkPolyData* pd);
  
    ///@{
    /**
     * Satisfy vtkLocator abstract interface.
     */
    void GenerateRepresentation(int level, vtkPolyData* pd) override;
    void FreeSearchStructure() override;
    void BuildLocator() override;
    void ForceBuildLocator() override;
    ///@}
  
    /**
     * Shallow copy of a vtkModifiedBSPTree.
     */
    void ShallowCopy(vtkAbstractCellLocator* locator) override;
  
  protected:
    vtkModifiedBSPTree();
    ~vtkModifiedBSPTree() override;
  
    void BuildLocatorInternal() override;
    std::shared_ptr<BSPNode> mRoot; // bounding box root node
    int npn;
    int nln;
    int tot_depth;
  
    // The main subdivision routine
    void Subdivide(BSPNode* node, Sorted_cell_extents_Lists* lists, vtkDataSet* dataSet,
      vtkIdType nCells, int depth, int maxlevel, vtkIdType maxCells, int& MaxDepth);
  
  private:
    vtkModifiedBSPTree(const vtkModifiedBSPTree&) = delete;
    void operator=(const vtkModifiedBSPTree&) = delete;
  };
  
  ///////////////////////////////////////////////////////////////////////////////
  // BSP Node
  // A BSP Node is a BBox - axis aligned etc etc
  ///////////////////////////////////////////////////////////////////////////////
  #ifndef DOXYGEN_SHOULD_SKIP_THIS
  
  class BSPNode
  {
  public:
    // Constructor
    BSPNode(void)
    {
      mChild[0] = mChild[1] = mChild[2] = nullptr;
      for (int i = 0; i < 6; i++)
        sorted_cell_lists[i] = nullptr;
      for (int i = 0; i < 3; i++)
      {
        this->Bounds[i * 2] = VTK_FLOAT_MAX;
        this->Bounds[i * 2 + 1] = -VTK_FLOAT_MAX;
      }
    }
    // Destructor
    ~BSPNode(void)
    {
      for (int i = 0; i < 3; i++)
        delete mChild[i];
      for (int i = 0; i < 6; i++)
        delete[] sorted_cell_lists[i];
    }
    // Set min box limits
    void setMin(double minx, double miny, double minz)
    {
      this->Bounds[0] = minx;
      this->Bounds[2] = miny;
      this->Bounds[4] = minz;
    }
    // Set max box limits
    void setMax(double maxx, double maxy, double maxz)
    {
      this->Bounds[1] = maxx;
      this->Bounds[3] = maxy;
      this->Bounds[5] = maxz;
    }
    //
    bool Inside(double point[3]) const;
    // BBox
    double Bounds[6];
  
  protected:
    // The child nodes of this one (if present - nullptr otherwise)
    BSPNode* mChild[3];
    // The axis we subdivide this voxel along
    int mAxis;
    // Just for reference
    int depth;
    // the number of cells in this node
    int num_cells;
    // 6 lists, sorted after the 6 dominant axes
    vtkIdType* sorted_cell_lists[6];
    // Order nodes as near/mid far relative to ray
    void Classify(const double origin[3], const double dir[3], double& rDist, BSPNode*& Near,
      BSPNode*& Mid, BSPNode*& Far) const;
    friend class vtkModifiedBSPTree;
  
  public:
    static int VTKFILTERSFLOWPATHS_EXPORT getDominantAxis(const double dir[3]);
  };
  
  #endif /* DOXYGEN_SHOULD_SKIP_THIS */
  
  #endif
  