// -*- C++ -*-
#ifndef RIBBOXHIERARCHY_H
#define RIBBOXHIERARCHY_H
/* Copyright 1996 
 * Thu Mar 27 10:28:13 1997  Brian Edward Smits  (bes@burn.cs.utah.edu)
 * 
 * RiBBoxHierarchy.H
 * 
 *	
 * 
 * $Id: RiBBoxHierarchy.H,v 1.2 1999/07/15 00:07:02 bes Exp $ 
 * 
 */
#ifndef RICOMMON_H
#include <RiCommon.H>
#endif

#ifndef RIBBOX_H
#include <RiBBox.H>
#endif

#ifndef RIRAYOBJECT_H
#include <RiRayObject.H>
#endif

/***************************************************************
CLASS
    RiBBoxHierarchyBuilder
    Builder for Bounding Box Hierarchies
    
DESCRIPTION
     <Detailed description with any warnings>

     
THEORY
    in case you actually want to know how it is being built
    from Arvo & Kirk Survey of Ray Tracing Acceleration (in Glassners Ray Tracing Book)
    based on the Goldsmith and Salmon article
    EXAMPLE
       IC(A) = Sum( EC(Bi) + (Area(Bi) / Area(A)) * IC(Bi) )
       IC(A) = Sum( EC(Bi) ) + (1 / Area(A)) * Sum( Area(Bi) * IC(Bi) )
       IC(A) = Sum( EC(Bi) ) + (1 / Area(A)) * Sum( AIC(Bi) )
       IC(A) = sum_EC  + (1 / Area(A)) * sum_AIC

       AIC(A) = Area(A) * IC(A)
       AIC(A) = Area(A) * Sum( EC(Bi) + (Area(Bi) / Area(A)) * IC(Bi) )
       AIC(A) = Area(A) * Sum( EC(Bi) ) +  Sum( Area(Bi) * IC(Bi) )
       AIC(A) = Area(A) * Sum( EC(Bi) ) + Sum( AIC(Bi) )
       AIC(A) = Area(A) * sum_EC  + sum_AIC
    END

     
PATTERN
      Builder
      
****************************************************************/
 
class RiBBoxHierarchyBuilder : public RiRayAcceleratorBuilder {
  public:
				//// Default Constructor
    RiBBoxHierarchyBuilder();
				//// Free all memory
    virtual ~RiBBoxHierarchyBuilder();
				//// Insert another object into the future RiBBoxHierarchy
    virtual void 	 AddObject(RiRayObject *);
				//// Build the RiRayObject and return it.
				// Each call to Build will build and return the next object.
    virtual RiRayObject *Build();
				//// Some situations result in a RiRayObjectBuilder
				// building more than a single object.  As long as IsDone
				// returns false, there are more objects that need to be built
    virtual bool	 IsDone();
				//// Cull box is intersected against the bounding box of all primitives
				// useful for bboxes nested inside grids.
    void   SetCullBBox(const RiBBox &cull);
  private:
    RiBBoxNode  *NewBBox();
    RiRayObject	*BuildBAB();
    void  	 AddBBoxNode(RiBBoxNode *root, RiBBoxNode *child);
    bool  	 FindBestParent(RiBBoxNode *root, RiBBoxNode *&parent,
				RiBBoxNode *obj, RiReal &bound, bool &amkchild);
    RiRayObject	*BuildSpacePartition();
    void  	 PartitionAndBound(RiBBoxNode *root, RiBBoxNode *bboxes,
				   int len, int lastAxis);
    RiRayObject *CopyAndBuild();
    //  GROUP: Holds objects on their way in.
    RiRayObject	**alist;
    int		  numObjs;
    int		  maxObjs;

    // GROUP: Mempool of BBoxes
    RiBBoxNode	*bbox;
    int		 curNewBox;
    int		 numBBoxes;
				////
    RiBBoxNode	*rootNode;
				////  final bbox is bounding box intersect cullBox
    RiBBox	 cullBox;
				////
    bool	 done;
};





class RiBBoxHierarchy : public RiRayObject {
  public:
				////
    RiBBoxHierarchy() {array = NULL;}
				////
    RiBBoxHierarchy(RiBBoxArray *array);
	        // GROUP: Members
		//// General interface for acceleration querries such
		// as bounding boxes and spheres.
    virtual RiInterval  GetMinMax(const RiUnitVector3 &) const;
		//// Does the ray hit the object.  Nothing more.
    virtual bool	Shadow(RiRay3 &) const;
		//// Compute an intersection and return it and any other
		//   data in the RiRayHit structure.
    virtual bool	Intersect(RiRay3 &, RiRayHit &);
				//// Accept a visitor to perform (structure preserving)
				// actions on the hierarchy
    virtual void	 Accept(RiRayObjectVisitor &visitor);
				////
    RiBBoxHierarchy& operator=(RiBBoxHierarchy &b) {array = b.array; b.array = NULL; return *this;}
  private:
    RiBBoxArray *array;  
};



#endif /* RIBBOXHIERARCHY_H */