From 8ab8fbfb505b6bc5d05a8539e926d9bd7304136f Mon Sep 17 00:00:00 2001 From: eap Date: Mon, 15 Oct 2012 14:29:45 +0000 Subject: [PATCH] 0021543: EDF 1978 SMESH: Viscous layer for 2D meshes Derive SMESH_Octree from SMESH_Tree + SMESH_Tree.hxx \ + SMESH_Quadtree.hxx \ --- src/SMESHUtils/Makefile.am | 3 + src/SMESHUtils/SMESH_Quadtree.cxx | 76 +++++++++ src/SMESHUtils/SMESH_Quadtree.hxx | 73 ++++++++ src/SMESHUtils/SMESH_Tree.hxx | 275 ++++++++++++++++++++++++++++++ 4 files changed, 427 insertions(+) create mode 100644 src/SMESHUtils/SMESH_Quadtree.cxx create mode 100644 src/SMESHUtils/SMESH_Quadtree.hxx create mode 100644 src/SMESHUtils/SMESH_Tree.hxx diff --git a/src/SMESHUtils/Makefile.am b/src/SMESHUtils/Makefile.am index 0e5f87624..a90736ca5 100644 --- a/src/SMESHUtils/Makefile.am +++ b/src/SMESHUtils/Makefile.am @@ -26,7 +26,9 @@ include $(top_srcdir)/adm_local/unix/make_common_starter.am salomeinclude_HEADERS = \ SMESH_Block.hxx \ SMESH_TypeDefs.hxx \ + SMESH_Tree.hxx \ SMESH_Octree.hxx \ + SMESH_Quadtree.hxx \ SMESH_OctreeNode.hxx \ SMESH_Comment.hxx \ SMESH_ComputeError.hxx \ @@ -39,6 +41,7 @@ lib_LTLIBRARIES = libSMESHUtils.la dist_libSMESHUtils_la_SOURCES = \ SMESH_Block.cxx \ + SMESH_Quadtree.cxx \ SMESH_Octree.cxx \ SMESH_OctreeNode.cxx \ SMESH_File.cxx diff --git a/src/SMESHUtils/SMESH_Quadtree.cxx b/src/SMESHUtils/SMESH_Quadtree.cxx new file mode 100644 index 000000000..680c4db0a --- /dev/null +++ b/src/SMESHUtils/SMESH_Quadtree.cxx @@ -0,0 +1,76 @@ +// Copyright (C) 2007-2012 CEA/DEN, EDF R&D, OPEN CASCADE +// +// Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, +// CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS +// +// This library is free software; you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public +// License as published by the Free Software Foundation; either +// version 2.1 of the License. +// +// 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 +// Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public +// License along with this library; if not, write to the Free Software +// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +// +// See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com +// + +// SMESH_Quadtree : Quartree implementation +// File : SMESH_Quadtree.cxx +// Module : SMESH +// +#include "SMESH_Quadtree.hxx" + +//=========================================================================== +/*! + * Constructor. limit must be provided at tree root construction. + * limit will be deleted by SMESH_Quadtree. + */ +//=========================================================================== + +SMESH_Quadtree::SMESH_Quadtree (SMESH_TreeLimit* limit): TBaseTree( limit ) +{ +} + +//================================================================= +/*! + * \brief Allocate a bndbox according to childIndex. childIndex is zero based + */ +//================================================================= + +Bnd_B2d* SMESH_Quadtree::newChildBox(int childIndex) const +{ + gp_XY min = getBox()->CornerMin(); + gp_XY max = getBox()->CornerMax(); + gp_XY HSize = (max - min)/2.; + gp_XY childHsize = HSize/2.; + + gp_XY minChild( min.X() + childIndex%2 * HSize.X(), + min.Y() + ( childIndex<2 ) * HSize.Y()); + + return new Bnd_B2d(minChild+childHsize,childHsize); +} + +//=========================================================================== +/*! + * \brief Compute the bigger dimension of my box + */ +//=========================================================================== + +double SMESH_Quadtree::maxSize() const +{ + if ( getBox() && !getBox()->IsVoid() ) + { + gp_XY min = getBox()->CornerMin(); + gp_XY max = getBox()->CornerMax(); + gp_XY Size = (max - min); + double returnVal = (Size.X()>Size.Y())?Size.X():Size.Y(); + return returnVal; + } + return 0.; +} diff --git a/src/SMESHUtils/SMESH_Quadtree.hxx b/src/SMESHUtils/SMESH_Quadtree.hxx new file mode 100644 index 000000000..bb69a9705 --- /dev/null +++ b/src/SMESHUtils/SMESH_Quadtree.hxx @@ -0,0 +1,73 @@ +// Copyright (C) 2007-2012 CEA/DEN, EDF R&D, OPEN CASCADE +// +// Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, +// CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS +// +// This library is free software; you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public +// License as published by the Free Software Foundation; either +// version 2.1 of the License. +// +// 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 +// Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public +// License along with this library; if not, write to the Free Software +// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +// +// See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com +// + +// SMESH_Quadtree : Quartree implementation +// File : SMESH_Quadtree.hxx +// Module : SMESH +// +#ifndef _SMESH_Quadtree_HXX_ +#define _SMESH_Quadtree_HXX_ + +#include "SMESH_Utils.hxx" +#include "SMESH_Tree.hxx" +#include + +/*! + * \brief 2D tree of anything. + * Methods to implement in a descendant are: + * - Bnd_B2d* buildRootBox(); // box of the whole tree + * - descendant* newChild() const; // a new child instance + * - void buildChildrenData(); // Fill in data of the children + */ +class SMESHUtils_EXPORT SMESH_Quadtree : public SMESH_Tree< Bnd_B2d, 4 > +{ +public: + typedef SMESH_Tree< Bnd_B2d, 4> TBaseTree; + + // Constructor. limit must be provided at tree root construction. + // limit will be deleted by SMESH_Quadtree + SMESH_Quadtree (SMESH_TreeLimit* limit=0); + + // Compute the bigger dimension of my box + double maxSize() const; + + // Return index of a child the given point is in + //inline int getChildIndex(double x, double y, const gp_XY& boxMiddle)const; + + protected: + + // Allocate a bndbox according to childIndex. childIndex is zero based + virtual Bnd_B2d* newChildBox(int childIndex) const; +}; + +//================================================================================ +/*! + * \brief Return index of a child the given point is in + */ +//================================================================================ + +// inline int SMESH_Quadtree::getChildIndex(double x, double y, const gp_XY& mid) const +// { +// return (x > mid.X()) + ( y > mid.Y())*2 + (z > mid.Z())*4; +// } + +#endif diff --git a/src/SMESHUtils/SMESH_Tree.hxx b/src/SMESHUtils/SMESH_Tree.hxx new file mode 100644 index 000000000..9165a52c4 --- /dev/null +++ b/src/SMESHUtils/SMESH_Tree.hxx @@ -0,0 +1,275 @@ +// Copyright (C) 2007-2012 CEA/DEN, EDF R&D, OPEN CASCADE +// +// Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, +// CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS +// +// This library is free software; you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public +// License as published by the Free Software Foundation; either +// version 2.1 of the License. +// +// 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 +// Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public +// License along with this library; if not, write to the Free Software +// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +// +// See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com +// + +// SMESH SMESH_Tree : tree implementation +// File : SMESH_Tree.hxx +// Created : Tue Jan 16 16:00:00 2007 +// Author : Nicolas Geimer & Aurélien Motteux (OCC) +// Module : SMESH +// +#ifndef _SMESH_Tree_HXX_ +#define _SMESH_Tree_HXX_ + +#include "SMESH_Utils.hxx" + +//================================================================================ +// Data limiting the tree height +struct SMESH_TreeLimit { + // MaxLevel of the Tree + int myMaxLevel; + // Minimal size of the Box + double myMinBoxSize; + + // Default: + // maxLevel-> 8^8 = 16777216 terminal trees at most + // minSize -> box size not checked + SMESH_TreeLimit(int maxLevel=8, double minSize=0.):myMaxLevel(maxLevel),myMinBoxSize(minSize) {} + virtual ~SMESH_TreeLimit() {} // it can be inherited +}; + +//================================================================================ +/*! + * \brief Base class for 2D and 3D trees + */ +//================================================================================ + +template< class BND_BOX, + int NB_CHILDREN> +class SMESHUtils_EXPORT SMESH_Tree +{ + public: + + typedef BND_BOX box_type; + + // Constructor. limit must be provided at tree root construction. + // limit will be deleted by SMESH_Tree + SMESH_Tree (SMESH_TreeLimit* limit=0); + + // Destructor + virtual ~SMESH_Tree (); + + // Compute the Tree. Must be called by constructor of inheriting class + void compute(); + + // Tell if Tree is a leaf or not. + // An inheriting class can influence it via myIsLeaf protected field + bool isLeaf() const; + + // Return its level + int level() const { return myLevel; } + + // Return Bounding Box of the Tree + const box_type* getBox() const { return myBox; } + + // Return height of the tree, full or from this level to topest leaf + int getHeight(const bool full=true) const; + + static int nbChildren() { return NB_CHILDREN; } + + // Compute the bigger dimension of my box + virtual double maxSize() const = 0; + +protected: + // Return box of the whole tree + virtual box_type* buildRootBox() = 0; + + // Allocate a child + virtual SMESH_Tree* newChild() const = 0; + + // Allocate a bndbox according to childIndex. childIndex is zero based + virtual box_type* newChildBox(int childIndex) const = 0; + + // Fill in data of the children + virtual void buildChildrenData() = 0; + + // members + + // Array of children + SMESH_Tree** myChildren; + + // Point the father, NULL for the level 0 + SMESH_Tree* myFather; + + // Tell us if the Tree is a leaf or not + bool myIsLeaf; + + // Tree limit + const SMESH_TreeLimit* myLimit; + +private: + // Build the children recursively + void buildChildren(); + + // Level of the Tree + int myLevel; + + box_type* myBox; +}; + +//=========================================================================== +/*! + * Constructor. limit must be provided at tree root construction. + * limit will be deleted by SMESH_Tree. + */ +//=========================================================================== + +template< class BND_BOX, int NB_CHILDREN> +SMESH_Tree::SMESH_Tree (SMESH_TreeLimit* limit): + myChildren(0), + myFather(0), + myIsLeaf( false ), + myLimit( limit ), + myLevel(0), + myBox(0) +{ + if ( !myLimit ) myLimit = new SMESH_TreeLimit(); +} + +//================================================================================ +/*! + * \brief Compute the Tree + */ +//================================================================================ + +template< class BND_BOX, int NB_CHILDREN> +void SMESH_Tree::compute() +{ + if ( myLevel==0 ) + { + myBox = buildRootBox(); + if ( myLimit->myMinBoxSize > 0. && maxSize() <= myLimit->myMinBoxSize ) + myIsLeaf = true; + else + buildChildren(); + } +} + +//====================================== +/*! + * \brief SMESH_Tree Destructor + */ +//====================================== + +template< class BND_BOX, int NB_CHILDREN> +SMESH_Tree::~SMESH_Tree () +{ + if ( myChildren ) + { + if ( !isLeaf() ) + { + for(int i = 0; i +void SMESH_Tree::buildChildren() +{ + if ( isLeaf() ) return; + + myChildren = new SMESH_Tree*[NB_CHILDREN]; + + // get the whole model size + double rootSize = 0; + { + SMESH_Tree* root = this; + while ( root->myLevel > 0 ) + root = root->myFather; + rootSize = root->maxSize(); + } + for (int i = 0; i < NB_CHILDREN; i++) + { + // The child is of the same type than its father (For instance, a SMESH_OctreeNode) + // We allocate the memory we need for the child + myChildren[i] = newChild(); + // and we assign to him its box. + myChildren[i]->myFather = this; + myChildren[i]->myLimit = myLimit; + myChildren[i]->myLevel = myLevel + 1; + myChildren[i]->myBox = newChildBox( i ); + myChildren[i]->myBox->Enlarge( rootSize * 1e-10 ); + if ( myLimit->myMinBoxSize > 0. && myChildren[i]->maxSize() <= myLimit->myMinBoxSize ) + myChildren[i]->myIsLeaf = true; + } + + // After building the NB_CHILDREN boxes, we put the data into the children. + buildChildrenData(); + + //After we pass to the next level of the Tree + for (int i = 0; ibuildChildren(); +} + +//================================================================================ +/*! + * \brief Tell if Tree is a leaf or not + * An inheriting class can influence it via myIsLeaf protected field + */ +//================================================================================ + +template< class BND_BOX, int NB_CHILDREN> +bool SMESH_Tree::isLeaf() const +{ + return myIsLeaf || ((myLimit->myMaxLevel > 0) ? (level() >= myLimit->myMaxLevel) : false ); +} + +//================================================================================ +/*! + * \brief Return height of the tree, full or from this level to topest leaf + */ +//================================================================================ + +template< class BND_BOX, int NB_CHILDREN> +int SMESH_Tree::getHeight(const bool full) const +{ + if ( full && myFather ) + return myFather->getHeight( true ); + + if ( isLeaf() ) + return 1; + + int heigth = 0; + for (int i = 0; igetHeight( false ); + if ( h > heigth ) + heigth = h; + } + return heigth + 1; +} + +#endif -- 2.39.2