Grid.h

Go to the documentation of this file.

/***************************************************************************
 *   Copyright (c) 2005 Imetric 3D GmbH                                    *
 *                                                                         *
 *   This file is part of the FreeCAD CAx development system.              *
 *                                                                         *
 *   This library is free software; you can redistribute it and/or         *
 *   modify it under the terms of the GNU Library General Public           *
 *   License as published by the Free Software Foundation; either          *
 *   version 2 of the License, or (at your option) any later version.      *
 *                                                                         *
 *   This library  is distributed in the hope that it will be useful,      *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU Library General Public License for more details.                  *
 *                                                                         *
 *   You should have received a copy of the GNU Library General Public     *
 *   License along with this library; see the file COPYING.LIB. If not,    *
 *   write to the Free Software Foundation, Inc., 59 Temple Place,         *
 *   Suite 330, Boston, MA  02111-1307, USA                                *
 *                                                                         *
 ***************************************************************************/


#ifndef MESH_GRID_H
#define MESH_GRID_H

#include <set>

#include "MeshKernel.h"
#include <Base/Vector3D.h>
#include <Base/BoundBox.h>

#define  MESH_CT_GRID          256     // Default value for number of elements per grid
#define  MESH_MAX_GRIDS        100000  // Default value for maximum number of grids
#define  MESH_CT_GRID_PER_AXIS 20


namespace MeshCore {

class MeshKernel;
class MeshGeomFacet;
class MeshGrid;

//#define MESHGRID_BBOX_EXTENSION 1.0e-3f
#define MESHGRID_BBOX_EXTENSION 10.0f

class MeshExport MeshGrid
{
protected:

  MeshGrid (const MeshKernel &rclM);
  MeshGrid (void);

public:
  virtual ~MeshGrid (void) { }

public:
  virtual void Attach (const MeshKernel &rclM);
  virtual void Rebuild (unsigned long ulPerGrid = MESH_CT_GRID, unsigned long ulMaxGrid = MESH_MAX_GRIDS);
  virtual void Rebuild (int iCtGridPerAxis = MESH_CT_GRID_PER_AXIS);
  virtual void Rebuild (unsigned long ulX, unsigned long ulY, unsigned long ulZ);

  virtual unsigned long Inside (const Base::BoundBox3f &rclBB, std::vector<unsigned long> &raulElements, bool bDelDoubles = true) const;
  virtual unsigned long Inside (const Base::BoundBox3f &rclBB, std::set<unsigned long> &raulElementss) const;
  virtual unsigned long Inside (const Base::BoundBox3f &rclBB, std::vector<unsigned long> &raulElements,
                                const Base::Vector3f &rclOrg, float fMaxDist, bool bDelDoubles = true) const;
  void SearchNearestFromPoint (const Base::Vector3f &rclPt, std::set<unsigned long> &rclInd) const;

  unsigned long GetElements (unsigned long ulX, unsigned long ulY, unsigned long ulZ,  std::set<unsigned long> &raclInd) const;
  unsigned long GetElements (const Base::Vector3f &rclPoint, std::vector<unsigned long>& aulFacets) const;

  virtual void  GetGridLengths (float &rfLenX, float &rfLenY, float &rfLenZ) const
  { rfLenX = _fGridLenX; rfLenY = _fGridLenY; rfLenZ = _fGridLenZ; }
  virtual void GetCtGrids (unsigned long &rulX, unsigned long &rulY, unsigned long &rulZ) const
  { rulX = _ulCtGridsX;  rulY = _ulCtGridsY;  rulZ = _ulCtGridsZ; }

  inline Base::BoundBox3f  GetBoundBox (unsigned long ulX, unsigned long ulY, unsigned long ulZ) const;
  inline Base::BoundBox3f  GetBoundBox     (void) const;
  inline Base::BoundBox3f  GetMeshBoundBox (void) const;

  unsigned long GetIndexToPosition(unsigned long ulX, unsigned long ulY, unsigned long ulZ) const;
  bool GetPositionToIndex(unsigned long id, unsigned long& ulX, unsigned long& ulY, unsigned long& ulZ) const;
  unsigned long GetCtElements(unsigned long ulX, unsigned long ulY, unsigned long ulZ) const
  { return _aulGrid[ulX][ulY][ulZ].size(); }
  virtual void Validate (const MeshKernel &rclM) = 0;
  virtual bool Verify() const = 0;
  bool CheckPosition (const Base::Vector3f &rclPoint, unsigned long &rulX, unsigned long &rulY, unsigned long &rulZ) const;
  virtual void Position (const Base::Vector3f &rclPoint, unsigned long &rulX, unsigned long &rulY, unsigned long &rulZ) const;
  inline bool CheckPos (unsigned long ulX, unsigned long ulY, unsigned long ulZ) const;
  void GetHull (unsigned long ulX, unsigned long ulY, unsigned long ulZ, unsigned long ulDistance, std::set<unsigned long> &raclInd) const;

protected:
  virtual void InitGrid (void);
  virtual void Clear (void);
  virtual void CalculateGridLength (unsigned long ulCtGrid, unsigned long ulMaxGrids);
  virtual void CalculateGridLength (int    iCtGridPerAxis);
  virtual void RebuildGrid (void) = 0;
  virtual unsigned long HasElements (void) const = 0;

protected:
  std::vector<std::vector<std::vector<std::set<unsigned long> > > >  _aulGrid;   
  const MeshKernel* _pclMesh;     
  unsigned long     _ulCtElements;
  unsigned long     _ulCtGridsX;  
  unsigned long     _ulCtGridsY;  
  unsigned long     _ulCtGridsZ;  
  float             _fGridLenX;   
  float             _fGridLenY;   
  float             _fGridLenZ;   
  float             _fMinX;       
  float             _fMinY;       
  float             _fMinZ;       
  // friends
  friend class MeshGridIterator;
};

class MeshExport MeshFacetGrid: public MeshGrid
{
public:

  MeshFacetGrid (const MeshKernel &rclM);
  MeshFacetGrid (void) : MeshGrid() { }
  MeshFacetGrid (const MeshKernel &rclM, unsigned long ulX, unsigned long ulY, unsigned long ulZ);
  MeshFacetGrid (const MeshKernel &rclM, int   iCtGridPerAxis);
  MeshFacetGrid (const MeshKernel &rclM, float fGridLen);
  virtual ~MeshFacetGrid (void) { }
 
  unsigned long SearchNearestFromPoint (const Base::Vector3f &rclPt) const;
  unsigned long SearchNearestFromPoint (const Base::Vector3f &rclPt, float fMaxSearchArea) const;
  void SearchNearestFacetInGrid(unsigned long ulX, unsigned long ulY, unsigned long ulZ, const Base::Vector3f &rclPt,
                                float &rfMinDist, unsigned long &rulFacetInd) const;
  void SearchNearestFacetInHull (unsigned long ulX, unsigned long ulY, unsigned long ulZ, unsigned long ulDistance, 
                                 const Base::Vector3f &rclPt, unsigned long &rulFacetInd, float &rfMinDist) const;

  virtual void Validate (const MeshKernel &rclM);
  virtual void Validate (void);
  virtual bool Verify() const;

protected:
  inline void Pos (const Base::Vector3f &rclPoint, unsigned long &rulX, unsigned long &rulY, unsigned long &rulZ) const;
  inline void PosWithCheck (const Base::Vector3f &rclPoint, unsigned long &rulX, unsigned long &rulY, unsigned long &rulZ) const;
  inline void AddFacet (const MeshGeomFacet &rclFacet, unsigned long ulFacetIndex, float fEpsilon = 0.0f);
  unsigned long HasElements (void) const
  { return _pclMesh->CountFacets(); }
  virtual void RebuildGrid (void);
};

class MeshExport MeshPointGrid: public MeshGrid
{
public:

  MeshPointGrid (void);
  MeshPointGrid (const MeshKernel &rclM);
  MeshPointGrid (const MeshKernel &rclM, int   iCtGridPerAxis);
  MeshPointGrid (const MeshKernel &rclM, float fGridLen);
  MeshPointGrid (const MeshKernel &rclM, unsigned long ulX, unsigned long ulY, unsigned long ulZ);
  virtual ~MeshPointGrid (void) {}

  unsigned long FindElements(const Base::Vector3f &rclPoint, std::set<unsigned long>& aulElements) const;
  virtual void Validate (const MeshKernel &rclM);
  virtual void Validate (void);
  virtual bool Verify() const;

protected:
  void AddPoint (const MeshPoint &rclPt, unsigned long ulPtIndex, float fEpsilon = 0.0f);
  void Pos(const Base::Vector3f &rclPoint, unsigned long &rulX, unsigned long &rulY, unsigned long &rulZ) const;
  unsigned long HasElements (void) const
  { return _pclMesh->CountPoints(); }
  virtual void RebuildGrid (void);
};

class MeshExport MeshGridIterator
{
public:
  MeshGridIterator (const MeshGrid &rclG);
  Base::BoundBox3f GetBoundBox (void) const
  { return _rclGrid.GetBoundBox(_ulX, _ulY, _ulZ); }
  void GetElements (std::vector<unsigned long> &raulElements) const
  {
    raulElements.insert(raulElements.end(), _rclGrid._aulGrid[_ulX][_ulY][_ulZ].begin(), _rclGrid._aulGrid[_ulX][_ulY][_ulZ].end());
  }
  unsigned long GetCtElements() const
  {
    return _rclGrid.GetCtElements(_ulX, _ulY, _ulZ);
  }
  void  Init (void)
  { _ulX = _ulY = _ulZ = 0; }
  bool  More (void) const
  { return (_ulZ < _rclGrid._ulCtGridsZ); }
  void  Next (void)
  {
    if (++_ulX >= (_rclGrid._ulCtGridsX)) _ulX = 0; else return;
    if (++_ulY >= (_rclGrid._ulCtGridsY)) { _ulY = 0; _ulZ++; } else return;
  }

  bool InitOnRay (const Base::Vector3f &rclPt, const Base::Vector3f &rclDir, std::vector<unsigned long> &raulElements);
  bool InitOnRay (const Base::Vector3f &rclPt, const Base::Vector3f &rclDir, float fMaxSearchArea, std::vector<unsigned long> &raulElements);
  bool NextOnRay (std::vector<unsigned long> &raulElements);
  
  void GetGridPos (unsigned long &rulX, unsigned long &rulY, unsigned long &rulZ) const
  { rulX = _ulX; rulY = _ulY; rulZ = _ulZ; }

protected:
  const MeshGrid& _rclGrid; 
  unsigned long   _ulX;     
  unsigned long   _ulY;     
  unsigned long   _ulZ;     
  Base::Vector3f        _clPt;    
  Base::Vector3f        _clDir;   
  bool            _bValidRay; 
  float           _fMaxSearchArea;
  struct GridElement 
  {
    GridElement( unsigned long x, unsigned long y, unsigned long z)
    { this->x = x; this->y = y; this->z = z; }
    bool operator < (const GridElement& pos) const
    {
      if ( x == pos.x)
      { if ( y == pos.y) return z < pos.z; else return y < pos.y; }
      else 
      { return x < pos.x; }
    }
  private:
    unsigned long x,y,z;
  };
  std::set<GridElement> _cSearchPositions;
};

// --------------------------------------------------------------

inline Base::BoundBox3f  MeshGrid::GetBoundBox (unsigned long ulX, unsigned long ulY, unsigned long ulZ) const
{
  float fX, fY, fZ;
  
  fX = _fMinX + (float(ulX) * _fGridLenX);
  fY = _fMinY + (float(ulY) * _fGridLenY);
  fZ = _fMinZ + (float(ulZ) * _fGridLenZ);

  return Base::BoundBox3f(fX, fY, fZ, fX + _fGridLenX, fY + _fGridLenY, fZ + _fGridLenZ);
}

inline Base::BoundBox3f  MeshGrid::GetBoundBox (void) const
{
  return Base::BoundBox3f(_fMinX, _fMinY, _fMinZ, _fMinX + (_fGridLenX * float(_ulCtGridsX)),
                    _fMinY + (_fGridLenY * float(_ulCtGridsY)), _fMinZ + (_fGridLenZ * float(_ulCtGridsZ)));
}

inline Base::BoundBox3f  MeshGrid::GetMeshBoundBox (void) const
{
  Base::BoundBox3f clBBenlarged = _pclMesh->GetBoundBox();
  clBBenlarged.Enlarge(MESHGRID_BBOX_EXTENSION);

  return clBBenlarged;
}

inline bool MeshGrid::CheckPos (unsigned long ulX, unsigned long ulY, unsigned long ulZ) const
{
  return ((ulX < _ulCtGridsX) && (ulY < _ulCtGridsY) && (ulZ < _ulCtGridsZ));
}

// --------------------------------------------------------------

inline void MeshFacetGrid::Pos (const Base::Vector3f &rclPoint, unsigned long &rulX, unsigned long &rulY, unsigned long &rulZ) const
{
  rulX = (unsigned long)((rclPoint.x - _fMinX) / _fGridLenX);
  rulY = (unsigned long)((rclPoint.y - _fMinY) / _fGridLenY);
  rulZ = (unsigned long)((rclPoint.z - _fMinZ) / _fGridLenZ);

  assert((rulX < _ulCtGridsX) && (rulY < _ulCtGridsY) && (rulZ < _ulCtGridsZ));
}

inline void MeshFacetGrid::PosWithCheck (const Base::Vector3f &rclPoint, unsigned long &rulX, unsigned long &rulY, unsigned long &rulZ) const
{
  if ( rclPoint.x < _fMinX)
    rulX = 0;
  else
  {
    rulX = (unsigned long)((rclPoint.x - _fMinX) / _fGridLenX);
    if (rulX >= _ulCtGridsX)
      rulX = (_ulCtGridsX-1);
  }

  if ( rclPoint.y < _fMinY)
    rulY = 0;
  else
  {
    rulY = (unsigned long)((rclPoint.y - _fMinY) / _fGridLenY);
    if (rulY >= _ulCtGridsY)
      rulY = (_ulCtGridsY-1);
  }

  if ( rclPoint.z < _fMinZ)
    rulZ = 0;
  else
  {
    rulZ = (unsigned long)((rclPoint.z - _fMinZ) / _fGridLenZ);
    if (rulZ >= _ulCtGridsZ)
      rulZ = (_ulCtGridsZ-1);
  }

  assert((rulX < _ulCtGridsX) && (rulY < _ulCtGridsY) && (rulZ < _ulCtGridsZ));
}

inline void MeshFacetGrid::AddFacet (const MeshGeomFacet &rclFacet, unsigned long ulFacetIndex, float fEpsilon)
{
#if 0
  unsigned long  i, ulX, ulY, ulZ, ulX1, ulY1, ulZ1, ulX2, ulY2, ulZ2;
  
  ulX1 = ulY1 = ulZ1 = ULONG_MAX;
  ulX2 = ulY2 = ulZ2 = 0;

  for (i = 0; i < 3; i++)
  {
    Pos(rclFacet._aclPoints[i], ulX, ulY, ulZ);
    _aulGrid[ulX][ulY][ulZ].insert(ulFacetIndex);
    ulX1 = RSmin<unsigned long>(ulX1, ulX); ulY1 = RSmin<unsigned long>(ulY1, ulY); ulZ1 = RSmin<unsigned long>(ulZ1, ulZ);
    ulX2 = RSmax<unsigned long>(ulX2, ulX); ulY2 = RSmax<unsigned long>(ulY2, ulY); ulZ2 = RSmax<unsigned long>(ulZ2, ulZ);
  }
  
  // falls Facet ueber mehrere BB reicht
  if ((ulX1 < ulX2) || (ulY1 < ulY2) || (ulZ1 < ulZ2))
  {
    for (ulX = ulX1; ulX <= ulX2; ulX++)
    {
      for (ulY = ulY1; ulY <= ulY2; ulY++)
      {
        for (ulZ = ulZ1; ulZ <= ulZ2; ulZ++)
        {
          if (CMeshFacetFunc::BBoxContainFacet(GetBoundBox(ulX, ulY, ulZ), rclFacet) == TRUE)
            _aulGrid[ulX][ulY][ulZ].insert(ulFacetIndex);
        }
      }
    }
  }
#else
  unsigned long ulX, ulY, ulZ;

  unsigned long ulX1, ulY1, ulZ1, ulX2, ulY2, ulZ2;

  Base::BoundBox3f clBB;

  clBB &= rclFacet._aclPoints[0];
  clBB &= rclFacet._aclPoints[1];
  clBB &= rclFacet._aclPoints[2];

  //float fDiagonalLength = clBB.CalcDiagonalLength();

  //clBB.Enlarge(fEpsilon*fDiagonalLength);

  Pos(Base::Vector3f(clBB.MinX,clBB.MinY,clBB.MinZ), ulX1, ulY1, ulZ1);
  Pos(Base::Vector3f(clBB.MaxX,clBB.MaxY,clBB.MaxZ), ulX2, ulY2, ulZ2);
  
  /*
  if (ulX1 > 0) ulX1--;
  if (ulY1 > 0) ulY1--;
  if (ulZ1 > 0) ulZ1--;
  
  if (ulX2 < (_ulCtGridsX-1)) ulX2++;
  if (ulY2 < (_ulCtGridsY-1)) ulY2++;
  if (ulZ2 < (_ulCtGridsZ-1)) ulZ2++;
  */

  // falls Facet ueber mehrere BB reicht
  if ((ulX1 < ulX2) || (ulY1 < ulY2) || (ulZ1 < ulZ2))
  {
    for (ulX = ulX1; ulX <= ulX2; ulX++)
    {
      for (ulY = ulY1; ulY <= ulY2; ulY++)
      {
        for (ulZ = ulZ1; ulZ <= ulZ2; ulZ++)
        {
          if ( rclFacet.IntersectBoundingBox( GetBoundBox(ulX, ulY, ulZ) ) )
            _aulGrid[ulX][ulY][ulZ].insert(ulFacetIndex);
        }
      }
    }
  }
  else
    _aulGrid[ulX1][ulY1][ulZ1].insert(ulFacetIndex);

#endif
}

} // namespace MeshCore

#endif // MESH_GRID_H