/**********************************************************************************************************************/
/*                                                GRAPH TRAVERSAL                                                     */
/**********************************************************************************************************************/

/************************************************ dwSimpleTraversal ***************************************************/
// traverse graph to render visible objects - init                                                                      
// 22/04/01, M                                                                                                          
// in : current camera,current frame number                                                                             
// out: number of nodes traversed                                                                                       
// rem: simply follow the tree, no portals                                                                              
/**********************************************************************************************************************/

DWORD CGraphNode::dwSimpleTraversal(const CCamera* lpCamera,const DWORD dwFrame)
  {
  DWORD dwNodes = 0;
  vSimpleTraversal(lpCamera,dwFrame,&dwNodes);
  return dwNodes;
  }

/************************************************ vSimpleTraversal ****************************************************/
// traverse node & children (recursively)                                                                               
// 22/04/01, M                                                                                                          
// in : current camera,current frame number,node counter address                                                        
// out:                                                                                                                 
// rem: simply follow the tree, no portals                                                                              
/**********************************************************************************************************************/

void CGraphNode::vSimpleTraversal(const CCamera* lpCamera,const DWORD dwFrame,DWORD* lpdwNodes)
  {
  CCamera* lpCam   = const_cast<CCamera*>(lpCamera);
//  if(m_dwTraversalSee == dwFrame) return;                   // already traversed; avoid infinite loop
  m_dwTraversalSee = dwFrame;
  (*lpdwNodes)++;

  // traverse node

  hrDraw(lpCamera);

  // traverse children

  listNodeIterator itChild = m_listChildren.begin();        // DON'T use lpGetFirstChild because of shared iterator !

  while(itChild != m_listChildren.end())
    {
    CGraphNode* lpChild  = *itChild;
    CBVbase*    lpBVNode = lpChild->lpGetBoundingVol();
    CMat4x4     m4Node2World;

    if(lpBVNode)
      {
      if(lpChild->boGetWorldMatrix(&m4Node2World))
        lpBVNode->vSetTrf2World(&m4Node2World);
      }

    lpChild->vSimpleTraversal(lpCamera,dwFrame,lpdwNodes);
    itChild++;
    }

  // traverse visitors

  setNodeIterator itVisitor = m_setVisitors.begin();

  while(itVisitor != m_setVisitors.end())
    {
    CGraphNode* lpVisitor = *itVisitor;
    CBVbase*    lpBVNode  = lpVisitor->lpGetBoundingVol();
    CMat4x4     m4Node2World;

    if(lpBVNode)
      {
      if(lpVisitor->boGetWorldMatrix(&m4Node2World))
        lpBVNode->vSetTrf2World(&m4Node2World);
      }

    lpVisitor->vSimpleTraversal(lpCamera,dwFrame,lpdwNodes);
    itVisitor++;
    }
  }

/************************************************ dwTraversal *********************************************************/
// traverse graph to render visible objects - init                                                                      
// 27/04/00, M                                                                                                          
// in : current camera,current frame number                                                                             
// out: number of nodes traversed                                                                                       
/**********************************************************************************************************************/

DWORD CGraphNode::dwTraversal(const CCamera* lpCamera,const DWORD dwFrame)
  {
  lpCamera->lpGetBVPlanes()->vSetTrf2World(lpCamera->lpm4Get2WorldMatrix());
  lpCamera->lpGetBVPlanes()->vRemoveAll();                  // planes are in camera space

  DWORD dwNodes = 0;
  vTraversal(lpCamera,dwFrame,&dwNodes);
  return dwNodes;
  }

/************************************************ vTraversal **********************************************************/
// traverse node & children (recursively)                                                                               
// 27/04/00, M                                                                                                          
// in : current camera,current frame number,node counter address                                                        
// out:                                                                                                                 
/**********************************************************************************************************************/

void CGraphNode::vTraversal(const CCamera* lpCamera,const DWORD dwFrame,DWORD* lpdwNodes)
  {
  CCamera* lpCam   = const_cast<CCamera*>(lpCamera);
//  if(m_dwTraversalSee == dwFrame) return;                   // already traversed; avoid infinite loop
  m_dwTraversalSee = dwFrame;
  (*lpdwNodes)++;

  // traverse portals

  listPortalIterator itPortal = m_listPortals.begin();        // DON'T use lpGetFirstPortal because of shared iterator !

  while(itPortal != m_listPortals.end())
    {
    CGraphPortal* lpPortal   = *itPortal;
    CGraphPortal* lpGoal     = lpPortal->lpGetGoal();
    if(!lpGoal)
      {
      if(lpPortal->dwGetType() == CGraphPortal::_MIRROR_)
        lpGoal = lpPortal;
      else
        {
        itPortal++;
        continue;
        }
      }

    CGraphNode  * lpNode     = lpGoal  ->lpGetParentNode();
    CBVbase     * lpBVPortal = lpPortal->lpGetBoundingVol();

    // set portal->world trf

    CMat4x4 m4Portal2World;
    if(lpBVPortal && lpPortal->boGetWorldMatrix(&m4Portal2World))
      lpBVPortal->vSetTrf2World(&m4Portal2World);

    // transform camera position to portal repere

    CVect3D  v3CamWorldPos;
    CVect3D  v3CamPortalPos;

    // portal in camera frustum ?

    if(lpPortal->boIsEnabled() && lpCam->dwIsInFrustum(lpPortal))
      {
      // test against previous portals
      // rem: planes are in camera space (to be node-independent)

      CBVPlanes* lpPlanes = lpCam->lpGetBVPlanes();

      if(lpBVPortal && (lpPlanes->hrIntersection(lpBVPortal) != CBVbase::_OUTSIDE_))
        {
        if(lpCam->boGetNodeWorldPos(&v3CamWorldPos) && lpPortal->boTransformToRepere(&v3CamPortalPos,v3CamWorldPos))
          {
          if(v3CamPortalPos[_Z_] > 0.f)
            {                                               // portal facing the camera
            // test : draw portal (mesh) to stencil

            if(m_lpRenderer->boAllowStencil())
              {
              m_lpRenderer->vSetStencilWrite();
              hrDraw(lpCamera);
              m_lpRenderer->vSetStencilTest();
              }

            // push planes

            DWORD dwPlaneNum[4];

            if(lpBVPortal && m_boPortalCulling)
              {
              CBVAABB* lpPortalAABB = reinterpret_cast<CBVAABB*>(lpBVPortal);
              CVect3D  v3Min,v3Max;
              lpPortalAABB->vGet(&v3Min,&v3Max);

              CVect3D  v3Corner[4];                         // build corners (portal seen front => X to the left)
              v3Corner[0].vSet(v3Max[_X_],v3Min[_Y_],0.f);
              v3Corner[1].vSet(v3Max[_X_],v3Max[_Y_],0.f);
              v3Corner[2].vSet(v3Min[_X_],v3Max[_Y_],0.f);
              v3Corner[3].vSet(v3Min[_X_],v3Min[_Y_],0.f);

//              CMat4x4  m4World2Cam;
//              lpCam->boGetNodeWorldMatrixI(&m4World2Cam);
//              CMat4x4  m4Portal2Cam = m4World2Cam*m4Portal2World;
              CMat4x4  m4Portal2Cam = (*lpCam->lpm4Get2CamMatrix()) * m4Portal2World;

              CVect3D  v3Proj[5];                           // trf to camera space
              v3Proj[0].vSet(m4Portal2Cam*v3Corner[0],_W_);
              v3Proj[1].vSet(m4Portal2Cam*v3Corner[1],_W_);
              v3Proj[2].vSet(m4Portal2Cam*v3Corner[2],_W_);
              v3Proj[3].vSet(m4Portal2Cam*v3Corner[3],_W_);
              v3Proj[4].vSet(v3Proj[0]);

              // build plane eq

              for(DWORD dwPlane = 0; dwPlane < 4; dwPlane++)
                {
                CVect3D v3_01(v3Proj[dwPlane+1]-v3Proj[dwPlane]);
                CVect3D v3N  (v3Proj[dwPlane]  ^v3_01);
                if(lpCam->boIsLeftHanded()) v3N = -v3N;
                CVect4D v4Eq (v3N,0.f);

                dwPlaneNum[dwPlane] = lpPlanes->dwAddPlane(v4Eq);
                }
              }

            // portal changes camera parameters

            if(lpPortal->boUseSpecial())
              {
              // trf to portal space

              CMat4x4 m4I;
              lpPortal->boGetWorldMatrixI(&m4I);
              m4I[_X_][_W_] = m4I[_Y_][_W_] = m4I[_Z_][_W_] = 0.f;

              CVect3D v3CamWorldDir,v3CamWorldUp;
              lpCam->boGetNodeWorldDir(&v3CamWorldDir);
              lpCam->boGetNodeWorldUp (&v3CamWorldUp);

              CVect3D v3CamPortalDir(m4I*v3CamWorldDir,_W_);
              CVect3D v3CamPortalUp (m4I*v3CamWorldUp ,_W_);

              // apply special trf (no translation)

              CMat4x4* lpm4Trf = lpPortal->lpm4GetSpecialTrf();
              v3CamPortalDir.vSet((*lpm4Trf)*v3CamPortalDir,_W_);
              v3CamPortalUp .vSet((*lpm4Trf)*v3CamPortalUp ,_W_);
              v3CamPortalPos.vSet((*lpm4Trf)*v3CamPortalPos,_W_);

              // back to world space

              CMat4x4 m4M;
              lpPortal->boGetWorldMatrix(&m4M);
              m4M[_X_][_W_] = m4M[_Y_][_W_] = m4M[_Z_][_W_] = 0.f;

              v3CamWorldDir.vSet(m4M*v3CamPortalDir,_W_);
              v3CamWorldUp .vSet(m4M*v3CamPortalUp ,_W_);
              lpPortal->boTransformToWorld(&v3CamWorldPos,v3CamPortalPos);

              // new camera

              CGraphNode nodNew;
              CCamera    camNew(*lpCam);
              nodNew.vSetAutoDelete(false);                 // local vars can't delete themselves
              camNew.vSetAutoDelete(false);

              nodNew.boAttachObject (&camNew);
              nodNew.vSetPosition   (v3CamWorldPos);
              nodNew.vSetOrientation(v3CamWorldDir,v3CamWorldUp);

              camNew.vSetLeftHanded(!lpCam->boIsLeftHanded());
              camNew.boCalcTrfMatrix();

              // copy BV planes

              DWORD      dwPlanes    = lpPlanes->dwGetNbPlanes();
              CBVPlanes* lpNewPlanes = camNew.lpGetBVPlanes();
//              CMat4x4    m4Cam2World;
//              camNew.boGetNodeWorldMatrix(&m4Cam2World);
//              lpNewPlanes->vSetTrf2World (&m4Cam2World);
              lpNewPlanes->vSetTrf2World(camNew.lpm4Get2WorldMatrix());

              for(DWORD dwPlane = 0; dwPlane < dwPlanes; dwPlane++)
                {
                lpNewPlanes->dwAddPlane(lpPlanes->v4GetPlane(dwPlane,NULL));
                }

              // recurse

              m_lpRenderer->boBegin3D(&camNew);             // new cam->world trf

              m_lpRenderer->vSetCullMode(camNew.boIsLeftHanded());
              lpNode->vTraversal(&camNew,dwFrame,lpdwNodes);
              m_lpRenderer->vSetCullMode(!camNew.boIsLeftHanded());

              m_lpRenderer->boBegin3D(lpCam);               // restore
              nodNew.boDetachObject(&camNew);               // don't forget that, the camera could be destroyed before the node
              }

            // same camera

            else
              {
              lpNode->vTraversal(lpCamera,dwFrame,lpdwNodes);
              }

            // pop planes

            if(lpBVPortal && m_boPortalCulling)
              {
              lpPlanes->boRemovePlane(dwPlaneNum[0]);
              lpPlanes->boRemovePlane(dwPlaneNum[1]);
              lpPlanes->boRemovePlane(dwPlaneNum[2]);
              lpPlanes->boRemovePlane(dwPlaneNum[3]);
              }

            // disable stencil

            if(m_lpRenderer->boAllowStencil())
              {
              m_lpRenderer->vSetStencilOff();
              }
            }
          }
        }
      }

    itPortal++;
    }

  // traverse node

  hrDraw(lpCamera);

  // traverse children

  listNodeIterator itChild = m_listChildren.begin();        // DON'T use lpGetFirstChild because of shared iterator !

  while(itChild != m_listChildren.end())
    {
    CGraphNode* lpChild  = *itChild;
    CBVPlanes*  lpPlanes = lpCam  ->lpGetBVPlanes();
    CBVbase*    lpBVNode = lpChild->lpGetBoundingVol();
    CMat4x4     m4Node2World;

    if(lpBVNode)
      {
      if(lpChild->boGetWorldMatrix(&m4Node2World))
        lpBVNode->vSetTrf2World(&m4Node2World);
      }

//!!!    if(!lpBVNode || (lpPlanes->hrIntersection(lpBVNode) != CBVbase::_OUTSIDE_))
      {
      lpChild->vTraversal(lpCamera,dwFrame,lpdwNodes);
      }

    itChild++;
    }

  // traverse visitors

  setNodeIterator itVisitor = m_setVisitors.begin();

  while(itVisitor != m_setVisitors.end())
    {
    CGraphNode* lpVisitor = *itVisitor;
    CBVbase*    lpBVNode  = lpVisitor->lpGetBoundingVol();
    CMat4x4     m4Node2World;

    if(lpBVNode)
      {
      if(lpVisitor->boGetWorldMatrix(&m4Node2World))
        lpBVNode->vSetTrf2World(&m4Node2World);
      }

    lpVisitor->vTraversal(lpCamera,dwFrame,lpdwNodes);
    itVisitor++;
    }
  }

/**********************************************************************************************************************/
/*                                                OVERRIDABLES                                                        */
/**********************************************************************************************************************/

/************************************************ hrDraw **************************************************************/
// draw all objects in node                                                                                             
// 28/04/00, M - 05/10/00 visibility test                                                                               
// in : current camera                                                                                                  
// out: _OK_ or error ID                                                                                                
/**********************************************************************************************************************/

HRESULT CGraphNode::hrDraw(const CCamera* lpCamera)
  {
  if(!lpCamera) return _ERR_(_GLOBERR_BADPARAM_);
  CCamera*   lpCam    = const_cast<CCamera*>(lpCamera);
  CBVPlanes* lpPlanes = lpCam->lpGetBVPlanes();

  // objects

  listObjIterator itObj = m_listObjects.begin();
  if(itObj != m_listObjects.end())
    {
    vUpdateBaseLights();                                    // update node's list of lights
    m_lpRenderer->boUpdateLights(this);                     // enable/disable renderer lights
    }

  while(itObj != m_listObjects.end())
    {
    CGraphObj* lpObj  = *itObj;
    bool       boDraw = true;
    bool       boAddV = false;

    if(lpObj->boIsVisitor())
      {
      if(lpCam->boAlreadyDrawn(lpObj)) boDraw = false;
      else                             boAddV = true;
      }

    boDraw &= lpObj->boIsVisible();

    if(boDraw)
      {
      CMat4x4  m4Obj2World;
      CBVbase* lpBV = lpObj->lpGetBoundingVol();
      if(lpBV && boGetWorldMatrix(&m4Obj2World))
        lpBV->vSetTrf2World(&m4Obj2World);

      if(lpCam->dwIsInFrustum(lpObj))
        {
        lpObj->vSetCurrentCamera(lpCamera);
        if(!lpBV || (lpPlanes->hrIntersection(lpBV) != CBVbase::_OUTSIDE_))
          {
          lpObj->hrDraw();
          if(boAddV) lpCam->boAddVisitor(lpObj);            // only when it's really drawn !
          }
        if(lpBV) lpBV->hrDraw(this);
        }
      }

    itObj++;
    }

  // node's BV

  CBVbase* lpBV = lpGetBoundingVol();
  if(lpBV) lpBV->hrDraw(this);
  return _ERR_(_OK_);
  }