/*
0         1         2         3         4         5         6         7
01234567890123456789012345678901234567890123456789012345678901234567890123456789
--------------------------------------------------------------------------------
-- Description : Geometric object octree part
--------------------------------------------------------------------------------
-- Creation date : 06 nov 1996               Author : FPI
--------------------------------------------------------------------------------
*/
 
#include "acp_base.h"
#include "MTH.h"
#include "MEC.h"
#include "GMT.h"
#include "GEO.h"
#include "GLI.h"
#include "TMP.h"
 
#include "COL/OctreeGO.h"
 
/*
--------------------------------------------------------------------------------
-- Description : Global variables
--------------------------------------------------------------------------------
*/
 
/*
--------------------------------------------------------------------------------
-- Description : Octree construction
--------------------------------------------------------------------------------
*/
 
/* limite du nombre de faces dans une partition */
ACP_tdxIndex COL_g_xNumberOfFacesLimit;
 
/* limite du nombre de faces totales */
ACP_tdxIndex COL_g_xTotalNumberOfFacesLimit;
 
/* profondeur maximale de l octree */
ACP_tdxIndex COL_g_xOctreeMaxDepth;
 
/* profondeur */
ACP_tdxIndex COL_g_xDepth;
 
/* statistiques */
/* compteur de noeuds */
ACP_tdxIndex COL_g_xNodeCounter;
/* compteur de feuilles */
ACP_tdxIndex COL_g_xFinalNodeCounter;
/* memoire allouee */
long COL_g_lMemory;
/* nb faces mises en liste */
long COL_g_lFacesInList;
/* profondeur du noeud */
ACP_tdxIndex COL_g_xSelectedDepth;
 
 
/* ANNECY MT - 19/08/98 {*/
long COL_g_lMaxNumberOfTaggedFaces;
 
long COL_g_lFacesTagCounter;
 
long *COL_g_d_lTaggedFacesTable;
/* END ANNECY MT }*/
 
COL_tdxFaceIndex    *COL_g_d_xSelectedFaceIndexList; /* only for script loading*/
 
/*
--------------------------------------------------------------------------------
-- Description : Init global variables
--------------------------------------------------------------------------------
-- Creation date : 19 Aug 1998                Author : MT
--------------------------------------------------------------------------------
*/
void COL_fn_vOctreeGlobalInit()
{
	COL_g_lMaxNumberOfTaggedFaces	= 0;
 
	COL_g_d_lTaggedFacesTable		= NULL;
 
/* ANNECY MT - 14/09/98 {*/
    COL_g_d_xSelectedFaceIndexList  = NULL;  /* only for script loading*/
/* END ANNECY MT }*/
}
 
/*
--------------------------------------------------------------------------------
-- Description : Alloc global variables
--------------------------------------------------------------------------------
-- Creation date : 19 Aug 1998                Author : MT
--------------------------------------------------------------------------------
*/
void COL_fn_vOctreeGlobalsCompute()
{
	if(COL_g_lMaxNumberOfTaggedFaces)
	{
		MMG_fn_vAddMemoryInfo (MMG_C_lTypeOctree , MMG_C_lSubTypeTaggedFaceTable , NULL);
		GEO_M_CPAMalloc ( COL_g_d_lTaggedFacesTable, long *, COL_g_lMaxNumberOfTaggedFaces*sizeof(long), E_uwGEONotEnoughtMemory );
/*		if(COL_g_d_lTaggedFacesTable)
			memset(COL_g_d_lTaggedFacesTable , 0L , COL_g_lMaxNumberOfTaggedFaces*sizeof(long)); */ /*AR9904 Already done in alloc function */
	}
}
 
/*
--------------------------------------------------------------------------------
-- Description : DesInit global variables
--------------------------------------------------------------------------------
-- Creation date : 19 Aug 1998                Author : MT
--------------------------------------------------------------------------------
*/
/*
void COL_fn_vOctreeGlobalDesInit()
{
	COL_g_lMaxNumberOfTaggedFaces	= 0;
 
	if(COL_g_d_lTaggedFacesTable)
	{
		MMG_fn_vAddMemoryInfo (MMG_C_lTypeOctree , MMG_C_lSubTypeTaggedFaceTable , NULL);
		GEO_M_CPAFree(COL_g_d_lTaggedFacesTable);
	}
}
*/
/*
--------------------------------------------------------------------------------
-- Description : Compute element bases table
--------------------------------------------------------------------------------
-- Creation date : 21 oct 1997               Author : FPI
--------------------------------------------------------------------------------
*/
 
/* calcul de la table des bases d element */
/* used*/
void COL_fn_vComputeElementBasesTable ( GEO_tdstGeometricObject *p_stGeomObj,
                                        COL_tdpstOctree p_stOctree )
{
  ACP_tdxIndex xElementIndex;
  GEO_tdstElementIndexedTriangles *p_stElementIndexedTriangles;
/*  GEO_tdstElementFaceMapDescriptors *p_stElementFaceMapDescriptors;*/
  GEO_tdstElementSpheres *p_stElementSpheres;
  GEO_tdstElementAlignedBoxes *p_stElementAlignedBoxes;
 
  /* init des compteurs */
  p_stOctree->xNbFaces = 0;
 
  /* passe sur les elements */
  for ( xElementIndex = 0 ; xElementIndex < p_stGeomObj->xNbElements ; xElementIndex++ )
  {
    switch ( p_stGeomObj->d_xListOfElementsTypes[xElementIndex] )
    {
      case GEO_C_xElementIndexedTriangles :
        p_stElementIndexedTriangles = (GEO_tdstElementIndexedTriangles *)(p_stGeomObj->d_stListOfElements[xElementIndex]);
 
        /* init des bases */
        p_stOctree->d_xElementBasesTable[xElementIndex] = (COL_tdxFaceIndexDouble)(p_stOctree->xNbFaces);
 
        /* nbfaces */
        p_stOctree->xNbFaces += p_stElementIndexedTriangles->xNbFaces;
      break;
      case GEO_C_xElementSpheres :
        p_stElementSpheres = (GEO_tdstElementSpheres *)(p_stGeomObj->d_stListOfElements[xElementIndex]);
 
        /* init des bases */
        p_stOctree->d_xElementBasesTable[xElementIndex] = (COL_tdxFaceIndexDouble)(p_stOctree->xNbFaces);
 
        /* nbfaces */
        p_stOctree->xNbFaces += p_stElementSpheres->xNbSpheres;
      break;
 
      case GEO_C_xElementAlignedBoxes :
        p_stElementAlignedBoxes = (GEO_tdstElementAlignedBoxes *)(p_stGeomObj->d_stListOfElements[xElementIndex]);
 
        /* init des bases */
        p_stOctree->d_xElementBasesTable[xElementIndex] = (COL_tdxFaceIndexDouble)(p_stOctree->xNbFaces);
 
        /* nbfaces */
        p_stOctree->xNbFaces += p_stElementAlignedBoxes->xNbAlignedBoxes;
      break;
 
      default :
      break;
    }
  }
}
 
 
/*
--------------------------------------------------------------------------------
-- Description : Init tagged points table
--------------------------------------------------------------------------------
-- Creation date : 21 oct 1997               Author : FPI
--------------------------------------------------------------------------------
*/
 
 
 
/*
--------------------------------------------------------------------------------
-- Description : Create tags table of points and faces
--------------------------------------------------------------------------------
-- Creation date : 22 aug 1996               Author : FPI
--------------------------------------------------------------------------------
modif by FBF 29/04/98 : separation from TMP temporary allocation and GEO definitive allocation
*/
 
/* creation des tableaux de tags */
/* used*/
void COL_fn_vCreateTagsTables ( GEO_tdstGeometricObject *p_stGeomObj,
                                COL_tdpstOctree p_stOctree )
{
	/* allocation du tableau de bases des elements */
	/* create element base table, TMP alloc */
    MMG_fn_vAddMemoryInfo (MMG_C_lTypeOctree , MMG_C_lSubTypeElementBaseTable , NULL);
	p_stOctree->d_xElementBasesTable = (COL_tdxFaceIndexDouble *) TMP_M_p_Malloc ( (p_stGeomObj->xNbElements)*sizeof(COL_tdxFaceIndexDouble) );
	COL_fn_vComputeElementBasesTable ( p_stGeomObj, p_stOctree );
 
	if ( p_stOctree->xNbFaces < COL_g_xTotalNumberOfFacesLimit )
	{
		/* free element base table, TMP free */
		TMP_M_Free( p_stOctree->d_xElementBasesTable);
		p_stOctree->d_xElementBasesTable = NULL;
	}
	else
	{
		COL_tdxFaceIndexDouble *p_xTmpPtr;
		/* save element base table ptr */
		p_xTmpPtr = p_stOctree->d_xElementBasesTable;
		/* allocate real element base table (GEO)*/
        MMG_fn_vAddMemoryInfo (MMG_C_lTypeOctree , MMG_C_lSubTypeFaceIndex , NULL);
		GEO_M_CPAMalloc ( p_stOctree->d_xElementBasesTable, COL_tdxFaceIndexDouble *, (p_stGeomObj->xNbElements)*sizeof(COL_tdxFaceIndexDouble), E_uwGEONotEnoughtMemory );
		COL_g_lMemory += (p_stGeomObj->xNbElements)*sizeof(COL_tdxFaceIndexDouble);
		/* copy tmp element base table in new one */
		memcpy(p_stOctree->d_xElementBasesTable,p_xTmpPtr,(p_stGeomObj->xNbElements)*sizeof(COL_tdxFaceIndexDouble));
		/* and delete tmp element base table */
		TMP_M_Free( p_xTmpPtr );
 
		COL_g_lMemory += (p_stGeomObj->xNbPoints)*sizeof(long);
 
		COL_g_lMaxNumberOfTaggedFaces = max(COL_g_lMaxNumberOfTaggedFaces,p_stOctree->xNbFaces);
		COL_g_lMemory += (p_stOctree->xNbFaces)*sizeof(long);
	}
}
 
 
/*
--------------------------------------------------------------------------------
-- Description : Calculate the number of faces in a box
--------------------------------------------------------------------------------
-- Creation date : 22 aug 1996               Author : FPI
--------------------------------------------------------------------------------
*/
/* InZeFunctionFunction to factorize code*/
/* used*/
	COL_tdxFaceIndex *fn_xAddInTable(
			COL_tdxFaceIndex *p_xSelectionIndex,
			ACP_tdxIndex xElementIndex,
			ACP_tdxIndex xDataElementIndex,
			ACP_tdxIndex *p_xSuppIndex )
	{
    /* index de l element */
    if(xElementIndex<COL_C_MaxIndex)
    {
      *p_xSelectionIndex = (COL_tdxFaceIndex)xElementIndex;
      p_xSelectionIndex++;
    }
    else
    {
      *p_xSelectionIndex++ = (COL_C_OverflowIndex + xElementIndex) >> 8;
			*p_xSelectionIndex++ = xElementIndex & 0xFF;
      (*p_xSuppIndex)++;
    }
    /* index de la face */
    if(xDataElementIndex<COL_C_MaxIndex)
    {
			*p_xSelectionIndex = (COL_tdxFaceIndex)xDataElementIndex;
			p_xSelectionIndex++;
    }
    else
    {
      *p_xSelectionIndex++ = (COL_C_OverflowIndex + xDataElementIndex) >> 8;
			*p_xSelectionIndex++ = xDataElementIndex & 0xFF;
			(*p_xSuppIndex)++;
    }
 
    /* increment du compteur */
    (*(COL_tdxFaceIndexDouble*)COL_g_d_xSelectedFaceIndexList)++;
 
		return p_xSelectionIndex;
	}
/* EndOfInZeFunctionFunction*/
 
 
 
 
/* compte le nombre de faces dans la boite */
/* used*/
ACP_tdxIndex COL_fn_xNumberOfFacesInBox ( GEO_tdstGeometricObject *p_stGeomObj,
                                          COL_tdpstOctree p_stOctree,
                                          MTH3D_tdstVector *p_stPartitionMinPoint,
                                          MTH3D_tdstVector *p_stPartitionMaxPoint,
                                          ACP_tdxIndex *p_xSuppIndex )
{
  COL_tdxFaceIndex *p_xSelectionIndex;
 
  ACP_tdxIndex xElementIndex;
  ACP_tdxIndex xDataElementIndex;
/*  ACP_tdxIndex xAtomIndex;*/
/*  ACP_tdxIndex xIndex;*/
 
  GEO_tdstElementIndexedTriangles *p_stElementIndexedTriangles;
/*  GEO_tdstElementFaceMapDescriptors *p_stElementFaceMapDescriptors;*/
/*  GEO_tdstElementTMeshes *p_stElementTMeshes;*/
  GEO_tdstElementSpheres *p_stElementSpheres;
  GEO_tdstElementAlignedBoxes *p_stElementAlignedBoxes;
 
  GEO_tdstIndexedSphere *p_stIndexedSphere;
  GEO_tdstIndexedAlignedBox *p_stIndexedAlignedBox;
 
  MTH3D_tdstVector *p_stVertex1;
  MTH3D_tdstVector *p_stVertex2;
  MTH3D_tdstVector *p_stVertex3;
  MTH3D_tdstVector *p_stNormal;
  MTH3D_tdstVector *p_stCenter;
  MTH3D_tdstVector *p_stMinPoint;
  MTH3D_tdstVector *p_stMaxPoint;
 
  /* init compteur */
  p_xSelectionIndex = COL_g_d_xSelectedFaceIndexList;
 
  /* le premier numero de face est en fait le nombre de faces de la liste */
#if !defined(U64)	/* Oliv' for alignment*/
  *((COL_tdxFaceIndexDouble*)p_xSelectionIndex) = 0;
  ((COL_tdxFaceIndexDouble*)p_xSelectionIndex)++;
#else  /* U64 */
	*p_xSelectionIndex++ = 0;
	*p_xSelectionIndex++ = 0;
#endif /* U64 */
  *p_xSuppIndex = 1;
 
 
  /* passe sur les elements */
  for ( xElementIndex = 0 ; xElementIndex < p_stGeomObj->xNbElements ; xElementIndex++ )
  {
    switch ( p_stGeomObj->d_xListOfElementsTypes[xElementIndex] )
    {
      case GEO_C_xElementIndexedTriangles :
        p_stElementIndexedTriangles = (GEO_tdstElementIndexedTriangles *)(p_stGeomObj->d_stListOfElements[xElementIndex]);
 
        /* pour les triangles */
        for ( xDataElementIndex = 0 ; xDataElementIndex < p_stElementIndexedTriangles->xNbFaces ; xDataElementIndex++ )
        {
          /* points du triangle */
          p_stVertex1 = p_stGeomObj->d_stListOfPoints + (p_stElementIndexedTriangles->d_stListOfFacesTripled + xDataElementIndex)->a3_xIndex[0];
          p_stVertex2 = p_stGeomObj->d_stListOfPoints + (p_stElementIndexedTriangles->d_stListOfFacesTripled + xDataElementIndex)->a3_xIndex[1];
          p_stVertex3 = p_stGeomObj->d_stListOfPoints + (p_stElementIndexedTriangles->d_stListOfFacesTripled + xDataElementIndex)->a3_xIndex[2];
 
          /* calcul de la normale */
          p_stNormal = p_stElementIndexedTriangles->d_stListOfFacesNormals + xDataElementIndex;
 
          /* if face in box */
          if ( INT_fn_bIntersectTriangleWithBoxWithHit ( p_stVertex1, p_stVertex2, p_stVertex3, p_stNormal, p_stPartitionMinPoint, p_stPartitionMaxPoint,NULL ) )
          {
/* Oliv' - factorize code - 24/09/1998*/
						p_xSelectionIndex = fn_xAddInTable( p_xSelectionIndex, xElementIndex, xDataElementIndex, p_xSuppIndex );
/* EndOfOliv'*/
          }
        }
      break;
 
 
      case GEO_C_xElementSpheres :
        p_stElementSpheres = (GEO_tdstElementSpheres *)(p_stGeomObj->d_stListOfElements[xElementIndex]);
 
        /* pour les spheres */
        for ( xDataElementIndex = 0 ; xDataElementIndex < p_stElementSpheres->xNbSpheres ; xDataElementIndex++ )
        {
          /* sphere */
          p_stIndexedSphere = p_stElementSpheres->d_stListOfSpheres + xDataElementIndex;
 
          /* centre de la sphere */
          p_stCenter = p_stGeomObj->d_stListOfPoints + p_stIndexedSphere->xCenterPoint;
 
          /* intersection sphere - boite */
          if ( INT_fn_bIntersectSphereWithBox ( p_stCenter, p_stIndexedSphere->xRadius, p_stPartitionMinPoint, p_stPartitionMaxPoint ) )
          {
/* Oliv' - factorize code - 24/09/1998*/
						p_xSelectionIndex = fn_xAddInTable( p_xSelectionIndex, xElementIndex, xDataElementIndex, p_xSuppIndex );
/* EndOfOliv'*/
          }
        }
      break;
 
      case GEO_C_xElementAlignedBoxes :
        p_stElementAlignedBoxes = (GEO_tdstElementAlignedBoxes *)(p_stGeomObj->d_stListOfElements[xElementIndex]);
 
        /* pour les boites */
        for ( xDataElementIndex = 0 ; xDataElementIndex < p_stElementAlignedBoxes->xNbAlignedBoxes ; xDataElementIndex++ )
        {
          /* boite */
          p_stIndexedAlignedBox = p_stElementAlignedBoxes->d_stListOfAlignedBoxes + xDataElementIndex;
 
          /* points de la boite */
          p_stMinPoint = p_stGeomObj->d_stListOfPoints + p_stIndexedAlignedBox->xMinPoint;
          p_stMaxPoint = p_stGeomObj->d_stListOfPoints + p_stIndexedAlignedBox->xMaxPoint;
 
          /* intersection boite - boite */
          if ( INT_fn_bIntersectBoxWithBox ( p_stMinPoint, p_stMaxPoint, p_stPartitionMinPoint, p_stPartitionMaxPoint ) )
          {
/* Oliv' - factorize code - 24/09/1998*/
						p_xSelectionIndex = fn_xAddInTable( p_xSelectionIndex, xElementIndex, xDataElementIndex, p_xSuppIndex );
/* EndOfOliv'*/
          }
        }
      break;
 
      default :
      break;
    }
  }
 
/* ANNECY MT - 14/09/98 {*/
  return (ACP_tdxIndex)(*((COL_tdxFaceIndexDouble*)COL_g_d_xSelectedFaceIndexList));
/* END ANNECY MT }*/
 
}
 
/*
--------------------------------------------------------------------------------
-- Description : Compute the midpoint of a box
--------------------------------------------------------------------------------
-- Creation date : 22 aug 1996               Author : FPI
--------------------------------------------------------------------------------
*/
 
/* calcule le milieu de la boite */
/* used*/
void COL_fn_vComputeMidBox ( MTH3D_tdstVector *p_stMinPoint,
                             MTH3D_tdstVector *p_stMaxPoint,
                             MTH3D_tdstVector *p_stSeparationPoint )
{
  MTH3D_M_vMiddleVector ( p_stSeparationPoint, p_stMinPoint, p_stMaxPoint );
}
 
/*
--------------------------------------------------------------------------------
-- Description : Calculate the separation point of a partition
--------------------------------------------------------------------------------
-- Creation date : 22 aug 1996               Author : FPI
--------------------------------------------------------------------------------
*/
 
/* calcule le point de separation d une partition */
/* used*/
void COL_fn_vComputeSeparationPoint ( GEO_tdstGeometricObject *p_stGeomObj,
                                      MTH3D_tdstVector *p_stMinPoint,
                                      MTH3D_tdstVector *p_stMaxPoint,
                                      MTH3D_tdstVector *p_stSeparationPoint )
{
  ACP_tdxIndex xVertexIndex;
  ACP_tdxIndex xNumberOfVertices;
 
  MTH3D_M_vNullVector ( p_stSeparationPoint );
 
  xNumberOfVertices = 0;
  for ( xVertexIndex = 0 ; xVertexIndex < p_stGeomObj->xNbPoints ; xVertexIndex++ )
  {
    if ( INT_fn_bGetInclusionPointInBox ( &(p_stGeomObj->d_stListOfPoints[xVertexIndex]), p_stMinPoint, p_stMaxPoint ) )
    {
      MTH3D_M_vAddVector ( p_stSeparationPoint, p_stSeparationPoint, &(p_stGeomObj->d_stListOfPoints[xVertexIndex]) );
      xNumberOfVertices++;
    }
  }
 
  /* si nombre de points < 2 prendre le milieu */
  if ( xNumberOfVertices < 2 )
  {
    COL_fn_vComputeMidBox ( p_stMinPoint, p_stMaxPoint, p_stSeparationPoint );
  }
  else
  {
    MTH3D_M_vDivScalarVector ( p_stSeparationPoint, p_stSeparationPoint, MTH_M_xLongToReal ( xNumberOfVertices ) );
  }
}
 
/*
--------------------------------------------------------------------------------
-- Description : Calculate one the eight under-partition of a partition
--------------------------------------------------------------------------------
-- Creation date : 22 aug 1996               Author : FPI
--------------------------------------------------------------------------------
*/
 
/* calcule les coordonnees de la sous-boite */
/* used*/
void COL_fn_vComputePartitionBox ( MTH3D_tdstVector *p_stMinPart,
                                   MTH3D_tdstVector *p_stMaxPart,
                                   MTH3D_tdstVector *p_stMinPoint,
                                   MTH3D_tdstVector *p_stMaxPoint,
                                   MTH3D_tdstVector *p_stSeparationPoint,
                                   ACP_tdxIndex xBoxPosition )
{
  switch ( xBoxPosition )
  {
    case COL_C_xXMinYMinZMin :
      MTH3D_M_vSetVectorElements ( p_stMinPart, p_stMinPoint->xX, p_stMinPoint->xY, p_stMinPoint->xZ );
      MTH3D_M_vSetVectorElements ( p_stMaxPart, p_stSeparationPoint->xX, p_stSeparationPoint->xY, p_stSeparationPoint->xZ );
    break;
    case COL_C_xXMinYMinZMax :
      MTH3D_M_vSetVectorElements ( p_stMinPart, p_stMinPoint->xX, p_stMinPoint->xY, p_stSeparationPoint->xZ );
      MTH3D_M_vSetVectorElements ( p_stMaxPart, p_stSeparationPoint->xX, p_stSeparationPoint->xY, p_stMaxPoint->xZ );
    break;
    case COL_C_xXMinYMaxZMin :
      MTH3D_M_vSetVectorElements ( p_stMinPart, p_stMinPoint->xX, p_stSeparationPoint->xY, p_stMinPoint->xZ );
      MTH3D_M_vSetVectorElements ( p_stMaxPart, p_stSeparationPoint->xX, p_stMaxPoint->xY, p_stSeparationPoint->xZ );
    break;
    case COL_C_xXMinYMaxZMax :
      MTH3D_M_vSetVectorElements ( p_stMinPart, p_stMinPoint->xX, p_stSeparationPoint->xY, p_stSeparationPoint->xZ );
      MTH3D_M_vSetVectorElements ( p_stMaxPart, p_stSeparationPoint->xX, p_stMaxPoint->xY, p_stMaxPoint->xZ );
    break;
    case COL_C_xXMaxYMinZMin :
      MTH3D_M_vSetVectorElements ( p_stMinPart, p_stSeparationPoint->xX, p_stMinPoint->xY, p_stMinPoint->xZ );
      MTH3D_M_vSetVectorElements ( p_stMaxPart, p_stMaxPoint->xX, p_stSeparationPoint->xY, p_stSeparationPoint->xZ );
    break;
    case COL_C_xXMaxYMinZMax :
      MTH3D_M_vSetVectorElements ( p_stMinPart, p_stSeparationPoint->xX, p_stMinPoint->xY, p_stSeparationPoint->xZ );
      MTH3D_M_vSetVectorElements ( p_stMaxPart, p_stMaxPoint->xX, p_stSeparationPoint->xY, p_stMaxPoint->xZ );
    break;
    case COL_C_xXMaxYMaxZMin :
      MTH3D_M_vSetVectorElements ( p_stMinPart, p_stSeparationPoint->xX, p_stSeparationPoint->xY, p_stMinPoint->xZ );
      MTH3D_M_vSetVectorElements ( p_stMaxPart, p_stMaxPoint->xX, p_stMaxPoint->xY, p_stSeparationPoint->xZ );
    break;
    case COL_C_xXMaxYMaxZMax :
      MTH3D_M_vSetVectorElements ( p_stMinPart, p_stSeparationPoint->xX, p_stSeparationPoint->xY, p_stSeparationPoint->xZ );
      MTH3D_M_vSetVectorElements ( p_stMaxPart, p_stMaxPoint->xX, p_stMaxPoint->xY, p_stMaxPoint->xZ );
    break;
 
    default :
    break;
  }
}
 
/*
--------------------------------------------------------------------------------
-- Description : Recursive function of an octree node construction
--------------------------------------------------------------------------------
-- Creation date : 22 aug 1996               Author : FPI
--------------------------------------------------------------------------------
*/
 
/* construction recursive d un noeud */
/* used*/
COL_tdpstOctreeNode COL_fn_pstConstructRecursiveOctree ( GEO_tdstGeometricObject *p_stGeomObj,
                                                         MTH3D_tdstVector *p_stMinPoint,
                                                         MTH3D_tdstVector *p_stMaxPoint )
{
  COL_tdpstOctreeNode p_stNodeToBeConstructed;
  ACP_tdxIndex xNumberOfFaces,xOverflowSize;
  MTH3D_tdstVector stMinPart;
  MTH3D_tdstVector stMaxPart;
  MTH3D_tdstVector stSeparationPoint;
 
  COL_g_xDepth++;
 
  /* allocation du noeud */
  MMG_fn_vAddMemoryInfo (MMG_C_lTypeOctree , MMG_C_lSubTypeOctreeNode , NULL);
  GEO_M_CPAMalloc ( p_stNodeToBeConstructed, COL_tdpstOctreeNode, sizeof(COL_tdstOctreeNode), E_uwGEONotEnoughtMemory );
  COL_g_lMemory += sizeof(COL_tdstOctreeNode);
 
  /* partition du noeud se prend la boite */
  MTH3D_M_vCopyVector ( &(p_stNodeToBeConstructed->stMinPart) , p_stMinPoint );
  MTH3D_M_vCopyVector ( &(p_stNodeToBeConstructed->stMaxPart) , p_stMaxPoint );
 
  /* mise a jour du compteur */
  COL_g_xNodeCounter++;
 
  /* si nombre de faces > limite et profondeur < limite */
  if
    (
      ( (xNumberOfFaces = COL_fn_xNumberOfFacesInBox ( p_stGeomObj, p_stGeomObj->p_stOctree, p_stMinPoint, p_stMaxPoint, &xOverflowSize )) > COL_g_xNumberOfFacesLimit ) &&
      ( COL_g_xDepth < COL_g_xOctreeMaxDepth )
    )
  {
    /* mise a nul de la liste de faces */
    p_stNodeToBeConstructed->d_xFaceIndexList = NULL;
    /* allocation des fils */
    MMG_fn_vAddMemoryInfo (MMG_C_lTypeOctree , MMG_C_lSubTypeOctreeNode , NULL);
    GEO_M_CPAMalloc ( p_stNodeToBeConstructed->p_pstChildList, COL_tdpstOctreeNode *, COL_C_xNbVerticesPerBox*sizeof(COL_tdpstOctreeNode), E_uwGEONotEnoughtMemory );
    COL_g_lMemory += COL_C_xNbVerticesPerBox*sizeof(COL_tdpstOctreeNode);
    /* calcul du point de separation */
    COL_fn_vComputeSeparationPoint ( p_stGeomObj, p_stMinPoint, p_stMaxPoint, &stSeparationPoint );
    /* calcul des boites et discretisation */
    COL_fn_vComputePartitionBox ( &stMinPart, &stMaxPart, p_stMinPoint, p_stMaxPoint, &stSeparationPoint, COL_C_xXMinYMinZMin );
    p_stNodeToBeConstructed->p_pstChildList[COL_C_xXMinYMinZMin] = COL_fn_pstConstructRecursiveOctree ( p_stGeomObj, &stMinPart, &stMaxPart );
    COL_fn_vComputePartitionBox ( &stMinPart, &stMaxPart, p_stMinPoint, p_stMaxPoint, &stSeparationPoint, COL_C_xXMinYMinZMax );
    p_stNodeToBeConstructed->p_pstChildList[COL_C_xXMinYMinZMax] = COL_fn_pstConstructRecursiveOctree ( p_stGeomObj, &stMinPart, &stMaxPart );
    COL_fn_vComputePartitionBox ( &stMinPart, &stMaxPart, p_stMinPoint, p_stMaxPoint, &stSeparationPoint, COL_C_xXMinYMaxZMin );
    p_stNodeToBeConstructed->p_pstChildList[COL_C_xXMinYMaxZMin] = COL_fn_pstConstructRecursiveOctree ( p_stGeomObj, &stMinPart, &stMaxPart );
    COL_fn_vComputePartitionBox ( &stMinPart, &stMaxPart, p_stMinPoint, p_stMaxPoint, &stSeparationPoint, COL_C_xXMinYMaxZMax );
    p_stNodeToBeConstructed->p_pstChildList[COL_C_xXMinYMaxZMax] = COL_fn_pstConstructRecursiveOctree ( p_stGeomObj, &stMinPart, &stMaxPart );
    COL_fn_vComputePartitionBox ( &stMinPart, &stMaxPart, p_stMinPoint, p_stMaxPoint, &stSeparationPoint, COL_C_xXMaxYMinZMin );
    p_stNodeToBeConstructed->p_pstChildList[COL_C_xXMaxYMinZMin] = COL_fn_pstConstructRecursiveOctree ( p_stGeomObj, &stMinPart, &stMaxPart );
    COL_fn_vComputePartitionBox ( &stMinPart, &stMaxPart, p_stMinPoint, p_stMaxPoint, &stSeparationPoint, COL_C_xXMaxYMinZMax );
    p_stNodeToBeConstructed->p_pstChildList[COL_C_xXMaxYMinZMax] = COL_fn_pstConstructRecursiveOctree ( p_stGeomObj, &stMinPart, &stMaxPart );
    COL_fn_vComputePartitionBox ( &stMinPart, &stMaxPart, p_stMinPoint, p_stMaxPoint, &stSeparationPoint, COL_C_xXMaxYMaxZMin );
    p_stNodeToBeConstructed->p_pstChildList[COL_C_xXMaxYMaxZMin] = COL_fn_pstConstructRecursiveOctree ( p_stGeomObj, &stMinPart, &stMaxPart );
    COL_fn_vComputePartitionBox ( &stMinPart, &stMaxPart, p_stMinPoint, p_stMaxPoint, &stSeparationPoint, COL_C_xXMaxYMaxZMax );
    p_stNodeToBeConstructed->p_pstChildList[COL_C_xXMaxYMaxZMax] = COL_fn_pstConstructRecursiveOctree ( p_stGeomObj, &stMinPart, &stMaxPart );
  }
  else
  {
    /* mise a jour du compteur */
    COL_g_xFinalNodeCounter++;
    /* mise a nul de la liste de fils */
    p_stNodeToBeConstructed->p_pstChildList = NULL;
    /* mise a nulle de la liste de faces pour xNumberOfFaces=0 */
    if ( xNumberOfFaces != 0 )
    {
      /* allocation de la liste de faces */
      MMG_fn_vAddMemoryInfo (MMG_C_lTypeOctree , MMG_C_lSubTypeFaceIndexList , NULL);
      GEO_M_CPAMalloc ( p_stNodeToBeConstructed->d_xFaceIndexList, COL_tdxFaceIndex *, (1+2*xNumberOfFaces)*sizeof(COL_tdxFaceIndex)+xOverflowSize, E_uwGEONotEnoughtMemory );
      COL_g_lMemory += (1+2*xNumberOfFaces)*sizeof(COL_tdxFaceIndex)+xOverflowSize;
      COL_g_lFacesInList += xNumberOfFaces;
 
      /* copie de la liste de faces */
	  memcpy ( p_stNodeToBeConstructed->d_xFaceIndexList, COL_g_d_xSelectedFaceIndexList, sizeof ( COL_tdxFaceIndex ) * (1+2*xNumberOfFaces)+xOverflowSize );	  
    }
    else
    {
      /* pas de liste */
      p_stNodeToBeConstructed->d_xFaceIndexList = NULL;
    }
  }
 
  COL_g_xDepth--;
 
  return p_stNodeToBeConstructed;
}
 
/*
--------------------------------------------------------------------------------
-- Description : Create the octree of an geometric object
--------------------------------------------------------------------------------
-- Creation date : 22 aug 1996               Author : FPI
--------------------------------------------------------------------------------
*/
 
/* creation - construction - calcul d un octree */
/* un octree est attache a un objet geometrique */
/* used*/
ACP_tdxBool COL_fn_bCreateOctree ( GEO_tdstGeometricObject *p_stGeomObj,
                                   ACP_tdxIndex xNbOfFacesLimit,
                                   ACP_tdxIndex xTotalNbOfFacesLimit,
                                   ACP_tdxIndex xOctMaxDepth )
{
	COL_tdstOctree *p_stOctree;
 
	/* init des variables module octree */
	COL_g_xNumberOfFacesLimit = xNbOfFacesLimit;
	COL_g_xTotalNumberOfFacesLimit = xTotalNbOfFacesLimit;
	COL_g_xOctreeMaxDepth = xOctMaxDepth;
 
	/* init des stats */
	COL_g_xDepth = 0;
	COL_g_xNodeCounter = 0;
	COL_g_xFinalNodeCounter = 0;
	COL_g_lMemory = 0;
	COL_g_lFacesInList = 0;
 
	GEO_vCreateObjectListOfPointsMaterial ( p_stGeomObj );
	GEO_vComputeObjectListOfPointsMaterial ( p_stGeomObj );
 
	if ( p_stGeomObj->p_stOctree == NULL && p_stGeomObj->xNbElements != 0)
	{
		/* allocation de la structure octree */
		/* temporary alloc TMP */
        MMG_fn_vAddMemoryInfo (MMG_C_lTypeOctree , MMG_C_lSubTypeOctreeStructure , NULL);
		p_stGeomObj->p_stOctree = (COL_tdpstOctree)TMP_M_p_Malloc( sizeof(COL_tdstOctree) );
		p_stOctree = p_stGeomObj->p_stOctree;
 
		/* init des champs de la structure */
 
		/* allocation et init des tableaux de tags */
		COL_fn_vCreateTagsTables ( p_stGeomObj, p_stOctree );
 
		if ( p_stOctree->xNbFaces < COL_g_xTotalNumberOfFacesLimit )
		{
			/* desalloc */
            MMG_fn_vAddMemoryInfo (MMG_C_lTypeOctree , MMG_C_lSubTypeOctreeStructure , NULL);
			TMP_M_Free( p_stGeomObj->p_stOctree );
			p_stGeomObj->p_stOctree = NULL;
			p_stOctree = NULL;
 
			GEO_xCreateObjectListOfEdges ( p_stGeomObj );
			GEO_xComputeObjectListOfEdges ( p_stGeomObj );
 
			return FALSE;
		}
		else
		{
			struct COL_tdstOctree_ *p_oTmpPtr;
 
			/* save octree ptr */
			p_oTmpPtr = p_stGeomObj->p_stOctree;
			/* allocate real octree (GEO)*/
            MMG_fn_vAddMemoryInfo (MMG_C_lTypeOctree , MMG_C_lSubTypeOctreeStructure , NULL);
			GEO_M_CPAMalloc ( p_stGeomObj->p_stOctree, COL_tdpstOctree, sizeof(COL_tdstOctree), E_uwGEONotEnoughtMemory );
			COL_g_lMemory += sizeof(COL_tdstOctree);
			/* copy tmp octree in new one */
			memcpy(p_stGeomObj->p_stOctree,p_oTmpPtr,sizeof(COL_tdstOctree));
			p_stOctree = p_stGeomObj->p_stOctree;
			/* and delete tmp element base table */
            MMG_fn_vAddMemoryInfo (MMG_C_lTypeOctree , MMG_C_lSubTypeOctreeStructure , NULL);
			TMP_M_Free( p_oTmpPtr );
 
			/* calcul de la bounding box */
			COL_fn_vComputeBoundingBoxOfGeometricObject ( &(p_stOctree->stMinBoundingBox), &(p_stOctree->stMaxBoundingBox), p_stGeomObj );
 
			/* allocation et init d une liste de selection des faces */
            MMG_fn_vAddMemoryInfo (MMG_C_lTypeOctree , MMG_C_lSubTypeFaceIndexList , NULL);
            COL_g_d_xSelectedFaceIndexList  = (COL_tdxFaceIndex *)TMP_M_p_Malloc ( (1+2*(p_stOctree->xNbFaces))*sizeof(COL_tdxFaceIndexDouble) );
            *COL_g_d_xSelectedFaceIndexList = 0;
 
			/* construction de l arbre */
			p_stOctree->p_stOctreeRoot = COL_fn_pstConstructRecursiveOctree ( p_stGeomObj, &(p_stOctree->stMinBoundingBox), &(p_stOctree->stMaxBoundingBox) );
            TMP_M_Free ( COL_g_d_xSelectedFaceIndexList );
			return TRUE;
		}
	}
	else
	{
		return FALSE;
	}
}
 
/*
--------------------------------------------------------------------------------
-- Description : Recursive function of an octree node destruction
--------------------------------------------------------------------------------
-- Creation date : 22 aug 1996               Author : FPI
--------------------------------------------------------------------------------
*/
 
/* destruction recursive d un noeud */
/*
void COL_fn_vDestructRecursiveOctree ( COL_tdstOctreeNode *p_stNodeToBeDestructed )
{
  // branche ou feuille 
  if ( p_stNodeToBeDestructed->p_pstChildList != NULL )
  {
    // branche 
    COL_fn_vDestructRecursiveOctree ( p_stNodeToBeDestructed->p_pstChildList[COL_C_xXMinYMinZMin] );
    COL_fn_vDestructRecursiveOctree ( p_stNodeToBeDestructed->p_pstChildList[COL_C_xXMinYMinZMax] );
    COL_fn_vDestructRecursiveOctree ( p_stNodeToBeDestructed->p_pstChildList[COL_C_xXMinYMaxZMin] );
    COL_fn_vDestructRecursiveOctree ( p_stNodeToBeDestructed->p_pstChildList[COL_C_xXMinYMaxZMax] );
    COL_fn_vDestructRecursiveOctree ( p_stNodeToBeDestructed->p_pstChildList[COL_C_xXMaxYMinZMin] );
    COL_fn_vDestructRecursiveOctree ( p_stNodeToBeDestructed->p_pstChildList[COL_C_xXMaxYMinZMax] );
    COL_fn_vDestructRecursiveOctree ( p_stNodeToBeDestructed->p_pstChildList[COL_C_xXMaxYMaxZMin] );
    COL_fn_vDestructRecursiveOctree ( p_stNodeToBeDestructed->p_pstChildList[COL_C_xXMaxYMaxZMax] );
    // desallocation de la liste de fils 
    MMG_fn_vAddMemoryInfo (MMG_C_lTypeOctree , MMG_C_lSubTypeOctreeNode , NULL);
    GEO_M_CPAFree ( p_stNodeToBeDestructed->p_pstChildList );
  }
  else
  {
    // feuille 
    // desallocation de la liste de faces 
    MMG_fn_vAddMemoryInfo (MMG_C_lTypeOctree , MMG_C_lSubTypeFaceIndexList , NULL);
    GEO_M_CPAFree ( p_stNodeToBeDestructed->d_xFaceIndexList );
  }
 
  // desallocation du noeud 
  MMG_fn_vAddMemoryInfo (MMG_C_lTypeOctree , MMG_C_lSubTypeOctreeNode , NULL);
  GEO_M_CPAFree ( p_stNodeToBeDestructed );
}
*/
/*
--------------------------------------------------------------------------------
-- Description : Delete the octree of an object
--------------------------------------------------------------------------------
-- Creation date : 22 aug 1996               Author : FPI
--------------------------------------------------------------------------------
*/
 
/* effacement - destruction d un octree */
 
/*
void COL_fn_vDeleteOctree ( GEO_tdstGeometricObject *p_stGeomObj )
{
  if ( p_stGeomObj->p_stOctree != NULL )
  {
    // destruction de l octree 
    COL_fn_vDestructRecursiveOctree ( (p_stGeomObj->p_stOctree)->p_stOctreeRoot );
 
    // destruction du tableau de tags de points 
    //GEO_M_CPAFree ( (p_stGeomObj->p_stOctree)->d_lTaggedPointsTable );
 
    // destruction du tableau de tags de faces 
    //GEO_M_CPAFree ( (p_stGeomObj->p_stOctree)->d_lTaggedFacesTable );
 
    // destruction du tableau des bases des elements 
	GEO_M_CPAFree ( (p_stGeomObj->p_stOctree)->d_xElementBasesTable );
 
    // destruction de la liste de faces selectionnees 
    //GEO_M_CPAFree ( (p_stGeomObj->p_stOctree)->d_xSelectedFaceIndexList );
 
    // destruction de la structure octree 
	GEO_M_CPAFree ( p_stGeomObj->p_stOctree );
    p_stGeomObj->p_stOctree = NULL;
  }
}
*/
 
 
/*
--------------------------------------------------------------------------------
-- Description : Recursive function of an octree node exploration
--------------------------------------------------------------------------------
-- Creation date : 22 aug 1996               Author : FPI
--------------------------------------------------------------------------------
*/
 
/* exploration recursive d un noeud */
/* used*/
void COL_fn_vExploreRecursiveOctreeWithBox ( COL_tdpstOctreeNode p_stNodeToBeExplored,
                                             MTH3D_tdstVector *p_stMinSituation,
                                             MTH3D_tdstVector *p_stMaxSituation,
                                             COL_tdpstOctreeNode *d_pstSelectedNode,
                                             ACP_tdxIndex *p_xNumberOfSelectedNodes )
{
  COL_g_xDepth++;
  /* si dans partition */
  if ( INT_fn_bIntersectBoxWithBox ( p_stMinSituation, p_stMaxSituation,
                                     &(p_stNodeToBeExplored->stMinPart), &(p_stNodeToBeExplored->stMaxPart) ) )
  {
    /* si liste de fils est diff de nul */
    if ( p_stNodeToBeExplored->p_pstChildList != NULL )
    {
      /* on descend */
      COL_fn_vExploreRecursiveOctreeWithBox ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMinYMinZMin], p_stMinSituation, p_stMaxSituation, d_pstSelectedNode, p_xNumberOfSelectedNodes );
      COL_fn_vExploreRecursiveOctreeWithBox ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMinYMinZMax], p_stMinSituation, p_stMaxSituation, d_pstSelectedNode, p_xNumberOfSelectedNodes );
      COL_fn_vExploreRecursiveOctreeWithBox ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMinYMaxZMin], p_stMinSituation, p_stMaxSituation, d_pstSelectedNode, p_xNumberOfSelectedNodes );
      COL_fn_vExploreRecursiveOctreeWithBox ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMinYMaxZMax], p_stMinSituation, p_stMaxSituation, d_pstSelectedNode, p_xNumberOfSelectedNodes );
      COL_fn_vExploreRecursiveOctreeWithBox ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMaxYMinZMin], p_stMinSituation, p_stMaxSituation, d_pstSelectedNode, p_xNumberOfSelectedNodes );
      COL_fn_vExploreRecursiveOctreeWithBox ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMaxYMinZMax], p_stMinSituation, p_stMaxSituation, d_pstSelectedNode, p_xNumberOfSelectedNodes );
      COL_fn_vExploreRecursiveOctreeWithBox ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMaxYMaxZMin], p_stMinSituation, p_stMaxSituation, d_pstSelectedNode, p_xNumberOfSelectedNodes );
      COL_fn_vExploreRecursiveOctreeWithBox ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMaxYMaxZMax], p_stMinSituation, p_stMaxSituation, d_pstSelectedNode, p_xNumberOfSelectedNodes );
    }
    else
    {
      if ( p_stNodeToBeExplored->d_xFaceIndexList != NULL )
      {
        /* on recupere les noeuds */
        if ( *p_xNumberOfSelectedNodes < COL_C_xMaxSelectedNodes )
        {
          d_pstSelectedNode[*p_xNumberOfSelectedNodes] = p_stNodeToBeExplored;
          (*p_xNumberOfSelectedNodes) ++;
          COL_g_xSelectedDepth = COL_g_xDepth;
        }
      }
    }
  }
  COL_g_xDepth--;
}
 
/*
--------------------------------------------------------------------------------
-- Description : Explore the octree of an object with a box
--------------------------------------------------------------------------------
-- Creation date : 22 aug 1996               Author : FPI
--------------------------------------------------------------------------------
*/
 
/* exploration d un octree */
/* used*/
void COL_fn_vExploreOctreeWithBox ( COL_tdpstOctree p_stOctree,
                                    MTH3D_tdstVector *p_stMinPoint,
                                    MTH3D_tdstVector *p_stMaxPoint,
                                    COL_tdpstOctreeNode *d_pstSelectedNode,
                                    ACP_tdxIndex *p_xNumberOfSelectedNodes )
{
  /* init les noeuds selectionnes */
  *p_xNumberOfSelectedNodes = 0;
  COL_g_xSelectedDepth = 0;
  COL_g_xDepth = 0;
 
  if ( p_stOctree != NULL )
  {
    /* exploration */
    COL_fn_vExploreRecursiveOctreeWithBox ( p_stOctree->p_stOctreeRoot, p_stMinPoint, p_stMaxPoint,
                                            d_pstSelectedNode, p_xNumberOfSelectedNodes );
  }
}
 
/*
--------------------------------------------------------------------------------
-- Description : View and add a selected node
--------------------------------------------------------------------------------
-- Creation date : 02 dec 1996               Author : YLG-FPI
--------------------------------------------------------------------------------
*/
/* used*/
void COL_fn_vViewAndAddSelectedNode ( COL_tdpstOctreeNode p_stNodeToBeExplored,
                                      MTH_tdxReal xT,
                                      COL_tdpstOctreeNode *d_pstSelectedNode,
                                      MTH_tdxReal *d_xSelectedT,
                                      ACP_tdxIndex *p_xNumberOfSelectedNodes )
{
  ACP_tdxIndex xNodeIndex;
 
  /* index sur le dernier element */
  xNodeIndex = *p_xNumberOfSelectedNodes;
  while ( ( 0 < xNodeIndex ) && ( xT < d_xSelectedT[xNodeIndex-1] ) )
  {
    if ( xNodeIndex < COL_C_xMaxSelectedNodes )
    {
      /* passe dans la liste xIndex <- xIndex-1 */
      d_pstSelectedNode[xNodeIndex] = d_pstSelectedNode[xNodeIndex-1];
      d_xSelectedT[xNodeIndex] = d_xSelectedT[xNodeIndex-1];
    }
    xNodeIndex--;
  }
 
  if ( xNodeIndex < COL_C_xMaxSelectedNodes )
  {
    /* ajout ds liste xIndex */
    d_pstSelectedNode[xNodeIndex] = p_stNodeToBeExplored;
    d_xSelectedT[xNodeIndex] = xT;
    if ( *p_xNumberOfSelectedNodes < COL_C_xMaxSelectedNodes )
    {
      (*p_xNumberOfSelectedNodes) ++;
    }
  }
}
 
/*
--------------------------------------------------------------------------------
-- Description : Recursive function of an octree node exploration
--------------------------------------------------------------------------------
-- Creation date : 02 dec 1996               Author : YLG-FPI
--------------------------------------------------------------------------------
*/
 
/* exploration recursive d un noeud */
/* used*/
void COL_fn_vExploreRecursiveOctreeWithSegment ( COL_tdpstOctreeNode p_stNodeToBeExplored,
                                                 MTH3D_tdstVector *p_stVertexA,
                                                 MTH3D_tdstVector *p_stVectAB,
                                                 COL_tdpstOctreeNode *d_pstSelectedNode,
                                                 MTH_tdxReal *d_xSelectedT,
                                                 ACP_tdxIndex *p_xNumberOfSelectedNodes )
{
  MTH_tdxReal xT;
 
  COL_g_xDepth++;
  /* si dans partition */
  if ( INT_fn_bDetectIntersectSegmentWithBox ( p_stVertexA, p_stVectAB,
                                                  &(p_stNodeToBeExplored->stMinPart),
                                                  &(p_stNodeToBeExplored->stMaxPart), &xT ) )
  {
    /* si liste de fils est diff de nul */
    if ( p_stNodeToBeExplored->p_pstChildList != NULL )
    {
      /* on descend */
      COL_fn_vExploreRecursiveOctreeWithSegment ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMinYMinZMin], p_stVertexA, p_stVectAB, d_pstSelectedNode, d_xSelectedT, p_xNumberOfSelectedNodes );
      COL_fn_vExploreRecursiveOctreeWithSegment ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMinYMinZMax], p_stVertexA, p_stVectAB, d_pstSelectedNode, d_xSelectedT, p_xNumberOfSelectedNodes );
      COL_fn_vExploreRecursiveOctreeWithSegment ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMinYMaxZMin], p_stVertexA, p_stVectAB, d_pstSelectedNode, d_xSelectedT, p_xNumberOfSelectedNodes );
      COL_fn_vExploreRecursiveOctreeWithSegment ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMinYMaxZMax], p_stVertexA, p_stVectAB, d_pstSelectedNode, d_xSelectedT, p_xNumberOfSelectedNodes );
      COL_fn_vExploreRecursiveOctreeWithSegment ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMaxYMinZMin], p_stVertexA, p_stVectAB, d_pstSelectedNode, d_xSelectedT, p_xNumberOfSelectedNodes );
      COL_fn_vExploreRecursiveOctreeWithSegment ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMaxYMinZMax], p_stVertexA, p_stVectAB, d_pstSelectedNode, d_xSelectedT, p_xNumberOfSelectedNodes );
      COL_fn_vExploreRecursiveOctreeWithSegment ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMaxYMaxZMin], p_stVertexA, p_stVectAB, d_pstSelectedNode, d_xSelectedT, p_xNumberOfSelectedNodes );
      COL_fn_vExploreRecursiveOctreeWithSegment ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMaxYMaxZMax], p_stVertexA, p_stVectAB, d_pstSelectedNode, d_xSelectedT, p_xNumberOfSelectedNodes );
    }
    else
    {
      if ( p_stNodeToBeExplored->d_xFaceIndexList != NULL )
      {
        /* on recupere les noeuds */
        COL_fn_vViewAndAddSelectedNode ( p_stNodeToBeExplored, xT, d_pstSelectedNode, d_xSelectedT, p_xNumberOfSelectedNodes );
        COL_g_xSelectedDepth = COL_g_xDepth;
      }
    }
  }
  COL_g_xDepth--;
}
 
/*
--------------------------------------------------------------------------------
-- Description : Explore the octree of an object with a segment
--------------------------------------------------------------------------------
-- Creation date : 02 dec 1996               Author : YLG-FPI
--------------------------------------------------------------------------------
*/
 
/* exploration d un octree */
/* used*/
void COL_fn_vExploreOctreeWithSegment ( COL_tdpstOctree p_stOctree,
                                        MTH3D_tdstVector *p_stVertexA,
                                        MTH3D_tdstVector *p_stVectAB,
                                        COL_tdpstOctreeNode *d_pstSelectedNode,
                                        MTH_tdxReal *d_xSelectedT,
                                        ACP_tdxIndex *p_xNumberOfSelectedNodes )
{
  /* init les noeuds selectionnes */
  *p_xNumberOfSelectedNodes = 0;
  COL_g_xSelectedDepth = 0;
  COL_g_xDepth = 0;
 
  if ( p_stOctree != NULL )
  {
    /* exploration */
    COL_fn_vExploreRecursiveOctreeWithSegment ( p_stOctree->p_stOctreeRoot, p_stVertexA, p_stVectAB,
                                                d_pstSelectedNode, d_xSelectedT, p_xNumberOfSelectedNodes );
  }
}
 
/*
--------------------------------------------------------------------------------
-- Description : Recursive function of an octree node exploration
--------------------------------------------------------------------------------
-- Creation date : 02 dec 1996               Author : YLG-FPI
--------------------------------------------------------------------------------
*/
#ifdef ACTIVE_EDITOR
/* active editor only*/
/* exploration recursive d un noeud */
void COL_fn_vExploreRecursiveOctreeWithSemiAxe ( COL_tdpstOctreeNode p_stNodeToBeExplored,
                                                 MTH3D_tdstVector *p_stVertexA,
                                                 MTH3D_tdstVector *p_stVertexB,
                                                 MTH3D_tdstVector *p_stVectAB,
                                                 COL_tdpstOctreeNode *d_pstSelectedNode,
                                                 MTH_tdxReal *d_xSelectedT,
                                                 ACP_tdxIndex *p_xNumberOfSelectedNodes )
{
  MTH_tdxReal xT;
  ACP_tdxBool bBack;
 
  COL_g_xDepth++;
  /* si dans partition */
  if ( INT_fn_bIntersectSemiAxeWithBoxForOctree ( p_stVertexA, p_stVertexB, p_stVectAB,
                                                  &(p_stNodeToBeExplored->stMinPart),
                                                  &(p_stNodeToBeExplored->stMaxPart), &bBack, &xT ) )
  {
    /* si liste de fils est diff de nul */
    if ( p_stNodeToBeExplored->p_pstChildList != NULL )
    {
      /* on descend */
      COL_fn_vExploreRecursiveOctreeWithSemiAxe ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMinYMinZMin], p_stVertexA, p_stVertexB, p_stVectAB, d_pstSelectedNode, d_xSelectedT, p_xNumberOfSelectedNodes );
      COL_fn_vExploreRecursiveOctreeWithSemiAxe ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMinYMinZMax], p_stVertexA, p_stVertexB, p_stVectAB, d_pstSelectedNode, d_xSelectedT, p_xNumberOfSelectedNodes );
      COL_fn_vExploreRecursiveOctreeWithSemiAxe ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMinYMaxZMin], p_stVertexA, p_stVertexB, p_stVectAB, d_pstSelectedNode, d_xSelectedT, p_xNumberOfSelectedNodes );
      COL_fn_vExploreRecursiveOctreeWithSemiAxe ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMinYMaxZMax], p_stVertexA, p_stVertexB, p_stVectAB, d_pstSelectedNode, d_xSelectedT, p_xNumberOfSelectedNodes );
      COL_fn_vExploreRecursiveOctreeWithSemiAxe ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMaxYMinZMin], p_stVertexA, p_stVertexB, p_stVectAB, d_pstSelectedNode, d_xSelectedT, p_xNumberOfSelectedNodes );
      COL_fn_vExploreRecursiveOctreeWithSemiAxe ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMaxYMinZMax], p_stVertexA, p_stVertexB, p_stVectAB, d_pstSelectedNode, d_xSelectedT, p_xNumberOfSelectedNodes );
      COL_fn_vExploreRecursiveOctreeWithSemiAxe ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMaxYMaxZMin], p_stVertexA, p_stVertexB, p_stVectAB, d_pstSelectedNode, d_xSelectedT, p_xNumberOfSelectedNodes );
      COL_fn_vExploreRecursiveOctreeWithSemiAxe ( p_stNodeToBeExplored->p_pstChildList[COL_C_xXMaxYMaxZMax], p_stVertexA, p_stVertexB, p_stVectAB, d_pstSelectedNode, d_xSelectedT, p_xNumberOfSelectedNodes );
    }
    else
    {
      if ( p_stNodeToBeExplored->d_xFaceIndexList != NULL )
      {
        /* on recupere les noeuds */
        if ( bBack )
        {
          xT = 0;
        }
        COL_fn_vViewAndAddSelectedNode ( p_stNodeToBeExplored, xT, d_pstSelectedNode, d_xSelectedT, p_xNumberOfSelectedNodes );
        COL_g_xSelectedDepth = COL_g_xDepth;
      }
    }
  }
  COL_g_xDepth--;
}
 
#endif
/*
--------------------------------------------------------------------------------
-- Description : Explore the octree of an object with a semi-axe
--------------------------------------------------------------------------------
-- Creation date : 02 dec 1996               Author : YLG-FPI
--------------------------------------------------------------------------------
*/
 
#ifdef ACTIVE_EDITOR
/* active editor only*/
/* exploration d un octree */
void COL_fn_vExploreOctreeWithSemiAxe ( COL_tdpstOctree p_stOctree,
                                        MTH3D_tdstVector *p_stVertexA,
                                        MTH3D_tdstVector *p_stVertexB,
                                        MTH3D_tdstVector *p_stVectAB,
                                        COL_tdpstOctreeNode *d_pstSelectedNode,
                                        MTH_tdxReal *d_xSelectedT,
                                        ACP_tdxIndex *p_xNumberOfSelectedNodes )
{
  /* init les noeuds selectionnes */
  *p_xNumberOfSelectedNodes = 0;
  COL_g_xSelectedDepth = 0;
  COL_g_xDepth = 0;
 
  if ( p_stOctree != NULL )
  {
    /* exploration */
    COL_fn_vExploreRecursiveOctreeWithSemiAxe ( p_stOctree->p_stOctreeRoot, p_stVertexA, p_stVertexB, p_stVectAB,
                                                d_pstSelectedNode, d_xSelectedT, p_xNumberOfSelectedNodes );
  }
}
 
#endif
