src/math/ConvexHull.cpp

/* Copyright (c) 2006 The University of Notre Dame. All Rights Reserved.
 *
 * The University of Notre Dame grants you ("Licensee") a
 * non-exclusive, royalty free, license to use, modify and
 * redistribute this software in source and binary code form, provided
 * that the following conditions are met:
 *
 * 1. Acknowledgement of the program authors must be made in any
 *    publication of scientific results based in part on use of the
 *    program.  An acceptable form of acknowledgement is citation of
 *    the article in which the program was described (Matthew
 *    A. Meineke, Charles F. Vardeman II, Teng Lin, Christopher
 *    J. Fennell and J. Daniel Gezelter, "OOPSE: An Object-Oriented
 *    Parallel Simulation Engine for Molecular Dynamics,"
 *    J. Comput. Chem. 26, pp. 252-271 (2005))
 *
 * 2. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 3. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the
 *    distribution.
 *
 * This software is provided "AS IS," without a warranty of any
 * kind. All express or implied conditions, representations and
 * warranties, including any implied warranty of merchantability,
 * fitness for a particular purpose or non-infringement, are hereby
 * excluded.  The University of Notre Dame and its licensors shall not
 * be liable for any damages suffered by licensee as a result of
 * using, modifying or distributing the software or its
 * derivatives. In no event will the University of Notre Dame or its
 * licensors be liable for any lost revenue, profit or data, or for
 * direct, indirect, special, consequential, incidental or punitive
 * damages, however caused and regardless of the theory of liability,
 * arising out of the use of or inability to use software, even if the
 * University of Notre Dame has been advised of the possibility of
 * such damages.
 *
 *
 *  ConvexHull.cpp
 *
 *  Purpose: To calculate convexhull, hull volume libqhull.
 *
 *  Created by Charles F. Vardeman II on 11 Dec 2006.
 *  @author  Charles F. Vardeman II
 *  @version $Id: ConvexHull.cpp,v 1.8 2008-09-14 01:32:25 chuckv Exp $
 *
 */

/* Standard includes independent of library */
#include <iostream>
#include <fstream>
#include <list>
#include <algorithm>
#include <iterator>
#include "math/ConvexHull.hpp"
#include "utils/simError.h"


using namespace oopse;

/* CGAL version of convex hull first then QHULL */
#ifdef HAVE_CGAL
//#include <CGAL/Homogeneous.h>
#include <CGAL/basic.h>
//#include <CGAL/Simple_cartesian.h>
#include <CGAL/Cartesian.h>
#include <CGAL/Origin.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Convex_hull_traits_3.h>
#include <CGAL/convex_hull_3.h>
#include <CGAL/Polyhedron_traits_with_normals_3.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/double.h>
#include <CGAL/number_utils.h>


//#include <CGAL/Quotient.h>
#include <CGAL/MP_Float.h>
//#include <CGAL/Lazy_exact_nt.h>


typedef CGAL::MP_Float RT;
//typedef double RT;
//typedef CGAL::Homogeneous<RT>                     K;
typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef K::Vector_3                               Vector_3;
//typedef CGAL::Convex_hull_traits_3<K>             Traits;
typedef CGAL::Polyhedron_traits_with_normals_3<K> Traits;
//typedef Traits::Polyhedron_3                      Polyhedron_3;
typedef CGAL::Polyhedron_3<Traits>                     Polyhedron_3;
typedef K::Point_3                                Point_3;


typedef Polyhedron_3::HalfedgeDS             HalfedgeDS;
typedef Polyhedron_3::Facet_iterator                   Facet_iterator;
typedef Polyhedron_3::Halfedge_around_facet_circulator Halfedge_facet_circulator;
typedef Polyhedron_3::Halfedge_handle Halfedge_handle;
typedef Polyhedron_3::Facet_iterator Facet_iterator;
typedef Polyhedron_3::Plane_iterator Plane_iterator;
typedef Polyhedron_3::Vertex_iterator Vertex_iterator;
typedef Polyhedron_3::Vertex_handle Vertex_handle;
typedef Polyhedron_3::Point_iterator Point_iterator;
 

class Enriched_Point_3 : public K::Point_3{
public:
  Enriched_Point_3(double x,double y,double z) : K::Point_3(x,y,z), yupMyPoint(false), mySD(NULL) {}

  bool isMyPoint() const{ return yupMyPoint; }
  void myPoint(){ yupMyPoint = true; }
  void setSD(StuntDouble* SD){mySD = SD;}
  StuntDouble* getStuntDouble(){return mySD;}
private:
  bool yupMyPoint;
  StuntDouble* mySD;

};


    // compare Point_3's... used in setting up the STL map from points to indices
template <typename Pt3>
struct Point_3_comp {
  bool operator() (const Pt3 & p, const Pt3 & q) const {
    return CGAL::lexicographically_xyz_smaller(p,q); // this is defined inline & hence we had to create fn object & not ptrfun
  }
};

// coordinate-based hashing inefficient but can we do better if pts are copied?
typedef std::map<Point_3, StuntDouble* ,Point_3_comp<Point_3> > ptMapType;

#ifdef IS_MPI
struct {
  double x,y,z;
} surfacePt;
#endif

ConvexHull::ConvexHull() : Hull(){
  //If we are doing the mpi version, set up some vectors for data communication
#ifdef IS_MPI


 nproc_ = MPI::COMM_WORLD.Get_size();
 myrank_ = MPI::COMM_WORLD.Get_rank();
 NstoProc_ = new int[nproc_];
 displs_   = new int[nproc_];

 // Create a surface point type in MPI to send
 surfacePtType = MPI::DOUBLE.Create_contiguous(3);
 surfacePtType.Commit();
 

#endif
}

void ConvexHull::computeHull(std::vector<StuntDouble*> bodydoubles)
{
 
  std::vector<Enriched_Point_3> points;
  ptMapType myMap;
  Point_iterator   hc;
  
  // Copy the positon vector into a points vector for cgal.
  std::vector<StuntDouble*>::iterator SD;

    for (SD =bodydoubles.begin(); SD != bodydoubles.end(); ++SD)
    {
      Vector3d pos = (*SD)->getPos();
      Enriched_Point_3* pt = new Enriched_Point_3(pos.x(),pos.y(),pos.z());
      pt->setSD(*SD);     
      points.push_back(*pt);
      // myMap[pt]=(*SD);
    }
  
  // define object to hold convex hull
  CGAL::Object ch_object_;
  Polyhedron_3 polyhedron;

  // compute convex hull
  
  std::vector<Enriched_Point_3>::iterator testpt;
  
  
  CGAL::convex_hull_3(points.begin(), points.end(), polyhedron);
 

  Ns_ = polyhedron.size_of_vertices();

#ifdef IS_MPI
  /* Gather an array of the number of verticies on each processor */
  

  surfacePtsGlobal_.clear();
  surfacePtsLocal_.clear();

  MPI::COMM_WORLD.Allgather(&Ns_,1,MPI::INT,&NstoProc_[0],1,MPI::INT);

  for (int i = 0; i < nproc_; i++){
    Nsglobal_ += NstoProc_[i];
  }
  /*Reminder ideally, we would like to reserve size for the vectors here*/
  surfacePtsLocal_.reserve(Ns_);
  surfacePtsGlobal_.resize(Nsglobal_);
  //  std::fill(surfacePtsGlobal_.begin(),surfacePtsGlobal_.end(),0);

  /* Build a displacements array */
  for (int i = 1; i < nproc_; i++){
    displs_[i] = displs_[i-1] + NstoProc_[i-1];
  }
  
  int noffset = displs_[myrank_];
  /* gather the potential hull */
  
  
  for (hc =polyhedron.points_begin();hc != polyhedron.points_end(); ++hc){
    Point_3 mypoint = *hc;
    surfacePt_ mpiSurfacePt;
    mpiSurfacePt.x = CGAL::to_double(mypoint.x());
    mpiSurfacePt.y = CGAL::to_double(mypoint.y());
    mpiSurfacePt.z = CGAL::to_double(mypoint.z());
    surfacePtsLocal_.push_back(mpiSurfacePt);
  }

  MPI::COMM_WORLD.Allgatherv(&surfacePtsLocal_[0],Ns_,surfacePtType,&surfacePtsGlobal_[0],NstoProc_,displs_,surfacePtType);
  std::vector<surfacePt_>::iterator spt;
  std::vector<Enriched_Point_3> gblpoints;

  int mine = 0;
  int pointidx = 0;
  for (spt = surfacePtsGlobal_.begin(); spt != surfacePtsGlobal_.end(); ++spt)
    {     
      surfacePt_ thispos = *spt;
      Enriched_Point_3 ept(thispos.x,thispos.y,thispos.z);
      if (mine >= noffset && mine < noffset + Ns_){
        ept.myPoint();
        ept.setSD(points[pointidx].getStuntDouble());
        pointidx++;
      }
      gblpoints.push_back(ept);

      mine++;
    }

  /* Compute the global hull */
  polyhedron.clear();
  CGAL::convex_hull_3(gblpoints.begin(), gblpoints.end(), polyhedron);


#endif


  /* Loop over all of the surface triangles and build data structures for atoms and normals*/
  Facet_iterator j;
  area_ = 0;
  for ( j = polyhedron.facets_begin(); j !=polyhedron.facets_end(); ++j) {
    Halfedge_handle h = j->halfedge();

    Point_3 r0=h->vertex()->point();
    Point_3 r1=h->next()->vertex()->point();
    Point_3 r2=h->next()->next()->vertex()->point();

    Point_3* pr0 = &r0;
    Point_3* pr1 = &r1;
    Point_3* pr2 = &r2;

    Enriched_Point_3* er0 = static_cast<Enriched_Point_3*>(pr0);
    Enriched_Point_3* er1 = static_cast<Enriched_Point_3*>(pr1);
    Enriched_Point_3* er2 = static_cast<Enriched_Point_3*>(pr2);

    // StuntDouble* sd = er0->getStuntDouble();
    std::cerr << "sd globalIndex = " << to_double(er0->x()) << "\n";
   
    Point_3 thisCentroid = CGAL::centroid(r0,r1,r2);

    Vector_3 normal = CGAL::cross_product(r1-r0,r2-r0);

    Triangle* face = new Triangle();
    Vector3d V3dNormal(CGAL::to_double(normal.x()),CGAL::to_double(normal.y()),CGAL::to_double(normal.z()));
    Vector3d V3dCentroid(CGAL::to_double(thisCentroid.x()),CGAL::to_double(thisCentroid.y()),CGAL::to_double(thisCentroid.z()));
    face->setNormal(V3dNormal);
    face->setCentroid(V3dCentroid);
    RealType faceArea = 0.5*V3dNormal.length();
    face->setArea(faceArea);
    area_ += faceArea;
    Triangles_.push_back(face);
    //    ptMapType::const_iterator locn=myMap.find(mypoint);
    //    int myIndex = locn->second;

  }
  
  std::cout << "Number of surface atoms is: " << Ns_ << std::endl;
  

}
void ConvexHull::printHull(const std::string& geomFileName)
{
  /*
  std::ofstream newGeomFile;
  
  //create new .md file based on old .md file
  newGeomFile.open("testhull.off");
  
  // Write polyhedron in Object File Format (OFF).
  CGAL::set_ascii_mode( std::cout);
  newGeomFile << "OFF" << std::endl << polyhedron.size_of_vertices() << ' '
              << polyhedron.size_of_facets() << " 0" << std::endl;
  std::copy( polyhedron.points_begin(), polyhedron.points_end(),
             std::ostream_iterator<Point_3>( newGeomFile, "\n"));
  for (  Facet_iterator i = polyhedron.facets_begin(); i != polyhedron.facets_end(); ++i) {
    Halfedge_facet_circulator j = i->facet_begin();
    // Facets in polyhedral surfaces are at least triangles.
    CGAL_assertion( CGAL::circulator_size(j) >= 3);
    newGeomFile << CGAL::circulator_size(j) << ' ';
    do {
      newGeomFile << ' ' << std::distance(polyhedron.vertices_begin(), j->vertex());
    } while ( ++j != i->facet_begin());
    newGeomFile << std::endl;
  }
  
  newGeomFile.close();
  */
/*
  std::ofstream newGeomFile;

  //create new .md file based on old .md file
  newGeomFile.open(geomFileName.c_str());

  // Write polyhedron in Object File Format (OFF).
  CGAL::set_ascii_mode( std::cout);
  newGeomFile << "OFF" << std::endl << ch_polyhedron.size_of_vertices() << ' '
  << ch_polyhedron.size_of_facets() << " 0" << std::endl;
  std::copy( ch_polyhedron.points_begin(), ch_polyhedron.points_end(),
             std::ostream_iterator<Point_3>( newGeomFile, "\n"));
  for (  Facet_iterator i = ch_polyhedron.facets_begin(); i != ch_polyhedron.facets_end(); ++i)
    {
      Halfedge_facet_circulator j = i->facet_begin();
      // Facets in polyhedral surfaces are at least triangles.
      CGAL_assertion( CGAL::circulator_size(j) >= 3);
      newGeomFile << CGAL::circulator_size(j) << ' ';
      do
        {
          newGeomFile << ' ' << std::distance(ch_polyhedron.vertices_begin(), j->vertex());
        }
      while ( ++j != i->facet_begin());
      newGeomFile << std::endl;
    }

  newGeomFile.close();
*/

}


#else
#ifdef HAVE_QHULL
/* Old options Qt Qu Qg QG0 FA */
ConvexHull::ConvexHull() : Hull(), dim_(3), options_("qhull Qt  Qci Tcv Pp") {
  //If we are doing the mpi version, set up some vectors for data communication
#ifdef IS_MPI


 nproc_ = MPI::COMM_WORLD.Get_size();
 myrank_ = MPI::COMM_WORLD.Get_rank();
 NstoProc_ = new int[nproc_];
 displs_   = new int[nproc_];

 // Create a surface point type in MPI to send
 surfacePtType = MPI::DOUBLE.Create_contiguous(3);
 surfacePtType.Commit();
 

#endif
}


void ConvexHull::computeHull(std::vector<StuntDouble*> bodydoubles)
{
  
  std::vector<int> surfaceIDs;
  std::vector<int> surfaceIDsGlobal;
  std::vector<int> localPtsMap;
  int numpoints = bodydoubles.size();

  //coordT* pt_array;
  coordT* surfpt_array;
  vertexT *vertex, **vertexp;
  facetT *facet;
  setT *vertices;
  int curlong,totlong;
  int id;
  
  coordT *point,**pointp;


  FILE *outdummy = NULL;
  FILE *errdummy = NULL;
  
  //pt_array = (coordT*) malloc(sizeof(coordT) * (numpoints * dim_));

  double* ptArray = new double[numpoints * 3];
  std::vector<bool> isSurfaceID(numpoints); 

  // Copy the positon vector into a points vector for qhull.
  std::vector<StuntDouble*>::iterator SD;
  int i = 0;
  for (SD =bodydoubles.begin(); SD != bodydoubles.end(); ++SD)
    {
      Vector3d pos = (*SD)->getPos();
      
      ptArray[dim_ * i] = pos.x();
      ptArray[dim_ * i + 1] = pos.y();
      ptArray[dim_ * i + 2] = pos.z();
      i++;
    }
  

  boolT ismalloc = False;
  Triangles_.clear();
  surfaceSDs_.clear();
  
  if (qh_new_qhull(dim_, numpoints, ptArray, ismalloc,
                    const_cast<char *>(options_.c_str()), NULL, stderr)) {

      sprintf(painCave.errMsg, "ConvexHull: Qhull failed to compute convex hull");
      painCave.isFatal = 0;
      simError();
      
  } //qh_new_qhull


#ifdef IS_MPI
  std::vector<double> localPts;
  int localPtArraySize;
  
  std::fill(isSurfaceID.begin(),isSurfaceID.end(),false);

  FORALLfacets {
    
    if (!facet->simplicial){
      // should never happen with Qt
      sprintf(painCave.errMsg, "ConvexHull: non-simplicaial facet detected");
      painCave.isFatal = 0;
      simError();
    }
    
    
    vertices = qh_facet3vertex(facet);
    FOREACHvertex_(vertices){
      id = qh_pointid(vertex->point);

      if( !isSurfaceID[id] ){
        isSurfaceID[id] = true;
      }
    }      
    qh_settempfree(&vertices);      
      
  } //FORALLfacets

 
  /*
  std::sort(surfaceIDs.begin(),surfaceIDs.end());
  surfaceIDs.erase(std::unique(surfaceIDs.begin(), surfaceIDs.end()), surfaceIDs.end());
  int localPtArraySize = surfaceIDs.size() * 3;
  */

  localPts.resize(localPtArraySize);
  //  std::fill(localPts.begin(),globalPts.end(),0.0);


  int idx = 0;
  // Copy the surface points into an array.
  for(std::vector<bool>::iterator list_iter = isSurfaceID.begin(); 
      list_iter != isSurfaceID.end(); list_iter++)
    {
      bool isIt = *list_iter;
      if (isIt){
        localPts.push_back(ptArray[dim_ * idx]);     
        localPts.push_back(ptArray[dim_ * idx + 1]); 
        localPts.push_back(ptArray[dim_ * idx + 2]); 
        localPtsMap.push_back(idx);
      } //Isit
      idx++;
    } //isSurfaceID
  

  localPtArraySize = localPts.size();
  MPI::COMM_WORLD.Allgather(&localPtArraySize,1,MPI::INT,&NstoProc_[0],1,MPI::INT);

  for (int i = 0; i < nproc_; i++){
    Nsglobal_ += NstoProc_[i];
  }

  std::vector<double> globalPts;
  globalPts.resize(Nsglobal_);
  isSurfaceID.resize(int(Nsglobal_/3));
  std::fill(globalPts.begin(),globalPts.end(),0.0);
  /* Build a displacements array */
  for (int i = 1; i < nproc_; i++){
    displs_[i] = displs_[i-1] + NstoProc_[i-1];
  }
  
  int noffset = displs_[myrank_];
  /* gather the potential hull */
  
  MPI::COMM_WORLD.Allgatherv(&localPts[0],localPtArraySize,MPI::DOUBLE,&globalPts[0],NstoProc_,displs_,MPI::DOUBLE);


  // Free previous hull
  qh_freeqhull(!qh_ALL);
  qh_memfreeshort(&curlong, &totlong);
  if (curlong || totlong)
    std::cerr << "qhull internal warning (main): did not free %d bytes of long memory (%d pieces) "
              << totlong << curlong << std::endl;

  if (qh_new_qhull(dim_, numpoints, &globalPts[0], ismalloc,
                    const_cast<char *>(options_.c_str()), NULL, stderr)){

      sprintf(painCave.errMsg, "ConvexHull: Qhull failed to compute global convex hull");
      painCave.isFatal = 0;
      simError();
      
  } //qh_new_qhull

#endif


    unsigned int nf = qh num_facets;
    
    /* Build Surface SD list first */

    std::fill(isSurfaceID.begin(),isSurfaceID.end(),false);

    FORALLfacets {
      
      if (!facet->simplicial){
      // should never happen with Qt
        sprintf(painCave.errMsg, "ConvexHull: non-simplicaial facet detected");
        painCave.isFatal = 0;
        simError();
      } //simplicical
      
      Triangle* face = new Triangle();
      Vector3d  V3dNormal(facet->normal[0],facet->normal[1],facet->normal[2]);
      face->setNormal(V3dNormal);
      //face->setCentroid(V3dCentroid);
      RealType faceArea = 0.5*V3dNormal.length();
      face->setArea(faceArea);


      vertices = qh_facet3vertex(facet);
      FOREACHvertex_(vertices){
        id = qh_pointid(vertex->point);
        face->addVertex(bodydoubles[id]);
        if( !isSurfaceID[id] ){
          isSurfaceID[id] = true;
          surfaceSDs_.push_back(bodydoubles[id]);
        } //IF isSurfaceID
      } //Foreachvertex


      Triangles_.push_back(face);
      qh_settempfree(&vertices);      
      
    } //FORALLfacets
                

    /*
  std::sort(surfaceIDs.begin(),surfaceIDs.end());
  surfaceIDs.erase(std::unique(surfaceIDs.begin(), surfaceIDs.end()), surfaceIDs.end());
  for(std::vector<int>::iterator list_iter = surfaceIDs.begin(); 
      list_iter != surfaceIDs.end(); list_iter++)
    {
    int i = *list_iter;
    surfaceSDs_.push_back(bodydoubles[i]);
    }
    */


  Ns_ = surfaceSDs_.size();


  qh_getarea(qh facet_list);
  volume_ = qh totvol;
  area_ = qh totarea;

  
  qh_freeqhull(!qh_ALL);
  qh_memfreeshort(&curlong, &totlong);
  if (curlong || totlong)
    std::cerr << "qhull internal warning (main): did not free %d bytes of long memory (%d pieces) "
              << totlong << curlong << std::endl;
  
  
  // free(pt_array);
  
}


void ConvexHull::printHull(const std::string& geomFileName)
{

  FILE *newGeomFile;
  
  //create new .md file based on old .md file
  newGeomFile = fopen(geomFileName.c_str(), "w");
  qh_findgood_all(qh facet_list);
  for (int i = 0; i < qh_PRINTEND; i++)
    qh_printfacets(newGeomFile, qh PRINTout[i], qh facet_list, NULL, !qh_ALL);
  
  fclose(newGeomFile);
}
#endif //QHULL
#endif //CGAL


Revision:	1293
Committed:	Sun Sep 14 01:32:26 2008 UTC (17 years, 1 month ago) by chuckv
File size:	18374 byte(s)
Log Message:	Added large quantities of code for convex hull and constant pressure langevin dynamics.
#	User	Rev	Content
1	chuckv	1097	/* Copyright (c) 2006 The University of Notre Dame. All Rights Reserved.
2			*
3			* The University of Notre Dame grants you ("Licensee") a
4			* non-exclusive, royalty free, license to use, modify and
5			* redistribute this software in source and binary code form, provided
6			* that the following conditions are met:
7			*
8			* 1. Acknowledgement of the program authors must be made in any
9			* publication of scientific results based in part on use of the
10			* program. An acceptable form of acknowledgement is citation of
11			* the article in which the program was described (Matthew
12			* A. Meineke, Charles F. Vardeman II, Teng Lin, Christopher
13			* J. Fennell and J. Daniel Gezelter, "OOPSE: An Object-Oriented
14			* Parallel Simulation Engine for Molecular Dynamics,"
15			* J. Comput. Chem. 26, pp. 252-271 (2005))
16			*
17			* 2. Redistributions of source code must retain the above copyright
18			* notice, this list of conditions and the following disclaimer.
19			*
20			* 3. Redistributions in binary form must reproduce the above copyright
21			* notice, this list of conditions and the following disclaimer in the
22			* documentation and/or other materials provided with the
23			* distribution.
24			*
25			* This software is provided "AS IS," without a warranty of any
26			* kind. All express or implied conditions, representations and
27			* warranties, including any implied warranty of merchantability,
28			* fitness for a particular purpose or non-infringement, are hereby
29			* excluded. The University of Notre Dame and its licensors shall not
30			* be liable for any damages suffered by licensee as a result of
31			* using, modifying or distributing the software or its
32			* derivatives. In no event will the University of Notre Dame or its
33			* licensors be liable for any lost revenue, profit or data, or for
34			* direct, indirect, special, consequential, incidental or punitive
35			* damages, however caused and regardless of the theory of liability,
36			* arising out of the use of or inability to use software, even if the
37			* University of Notre Dame has been advised of the possibility of
38			* such damages.
39			*
40			*
41			* ConvexHull.cpp
42			*
43	chuckv	1137	* Purpose: To calculate convexhull, hull volume libqhull.
44	chuckv	1097	*
45			* Created by Charles F. Vardeman II on 11 Dec 2006.
46			* @author Charles F. Vardeman II
47	chuckv	1293	* @version $Id: ConvexHull.cpp,v 1.8 2008-09-14 01:32:25 chuckv Exp $
48	chuckv	1097	*
49			*/
50
51	chuckv	1242	/* Standard includes independent of library */
52	chuckv	1097	#include <iostream>
53			#include <fstream>
54	chuckv	1188	#include <list>
55			#include <algorithm>
56			#include <iterator>
57	chuckv	1141	#include "math/ConvexHull.hpp"
58	chuckv	1188	#include "utils/simError.h"
59	chuckv	1293
60
61	chuckv	1097	using namespace oopse;
62
63	chuckv	1242	/* CGAL version of convex hull first then QHULL */
64			#ifdef HAVE_CGAL
65	chuckv	1293	//#include <CGAL/Homogeneous.h>
66	chuckv	1242	#include <CGAL/basic.h>
67	chuckv	1293	//#include <CGAL/Simple_cartesian.h>
68			#include <CGAL/Cartesian.h>
69			#include <CGAL/Origin.h>
70			#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
71	chuckv	1242	#include <CGAL/Convex_hull_traits_3.h>
72			#include <CGAL/convex_hull_3.h>
73	chuckv	1293	#include <CGAL/Polyhedron_traits_with_normals_3.h>
74			#include <CGAL/Polyhedron_3.h>
75	chuckv	1242	#include <CGAL/double.h>
76	chuckv	1293	#include <CGAL/number_utils.h>
77	chuckv	1188
78	chuckv	1293
79			//#include <CGAL/Quotient.h>
80	chuckv	1242	#include <CGAL/MP_Float.h>
81	chuckv	1293	//#include <CGAL/Lazy_exact_nt.h>
82	chuckv	1188
83	chuckv	1293
84
85			typedef CGAL::MP_Float RT;
86			//typedef double RT;
87			//typedef CGAL::Homogeneous<RT> K;
88			typedef CGAL::Exact_predicates_exact_constructions_kernel K;
89			typedef K::Vector_3 Vector_3;
90			//typedef CGAL::Convex_hull_traits_3<K> Traits;
91			typedef CGAL::Polyhedron_traits_with_normals_3<K> Traits;
92			//typedef Traits::Polyhedron_3 Polyhedron_3;
93			typedef CGAL::Polyhedron_3<Traits> Polyhedron_3;
94	chuckv	1261	typedef K::Point_3 Point_3;
95	chuckv	1188
96
97	chuckv	1293	typedef Polyhedron_3::HalfedgeDS HalfedgeDS;
98			typedef Polyhedron_3::Facet_iterator Facet_iterator;
99			typedef Polyhedron_3::Halfedge_around_facet_circulator Halfedge_facet_circulator;
100			typedef Polyhedron_3::Halfedge_handle Halfedge_handle;
101			typedef Polyhedron_3::Facet_iterator Facet_iterator;
102			typedef Polyhedron_3::Plane_iterator Plane_iterator;
103			typedef Polyhedron_3::Vertex_iterator Vertex_iterator;
104			typedef Polyhedron_3::Vertex_handle Vertex_handle;
105			typedef Polyhedron_3::Point_iterator Point_iterator;
106
107	chuckv	1188
108	chuckv	1293
109			class Enriched_Point_3 : public K::Point_3{
110			public:
111			Enriched_Point_3(double x,double y,double z) : K::Point_3(x,y,z), yupMyPoint(false), mySD(NULL) {}
112
113			bool isMyPoint() const{ return yupMyPoint; }
114			void myPoint(){ yupMyPoint = true; }
115			void setSD(StuntDouble* SD){mySD = SD;}
116			StuntDouble* getStuntDouble(){return mySD;}
117			private:
118			bool yupMyPoint;
119			StuntDouble* mySD;
120
121			};
122
123
124
125
126
127			// compare Point_3's... used in setting up the STL map from points to indices
128			template <typename Pt3>
129			struct Point_3_comp {
130			bool operator() (const Pt3 & p, const Pt3 & q) const {
131			return CGAL::lexicographically_xyz_smaller(p,q); // this is defined inline & hence we had to create fn object & not ptrfun
132			}
133			};
134
135			// coordinate-based hashing inefficient but can we do better if pts are copied?
136			typedef std::map<Point_3, StuntDouble* ,Point_3_comp<Point_3> > ptMapType;
137
138			#ifdef IS_MPI
139			struct {
140			double x,y,z;
141			} surfacePt;
142			#endif
143
144			ConvexHull::ConvexHull() : Hull(){
145			//If we are doing the mpi version, set up some vectors for data communication
146			#ifdef IS_MPI
147
148
149			nproc_ = MPI::COMM_WORLD.Get_size();
150			myrank_ = MPI::COMM_WORLD.Get_rank();
151			NstoProc_ = new int[nproc_];
152			displs_ = new int[nproc_];
153
154			// Create a surface point type in MPI to send
155			surfacePtType = MPI::DOUBLE.Create_contiguous(3);
156			surfacePtType.Commit();
157
158
159			#endif
160			}
161
162			void ConvexHull::computeHull(std::vector<StuntDouble*> bodydoubles)
163	chuckv	1242	{
164	chuckv	1293
165			std::vector<Enriched_Point_3> points;
166			ptMapType myMap;
167			Point_iterator hc;
168	chuckv	1242
169			// Copy the positon vector into a points vector for cgal.
170	chuckv	1293	std::vector<StuntDouble*>::iterator SD;
171
172			for (SD =bodydoubles.begin(); SD != bodydoubles.end(); ++SD)
173	chuckv	1242	{
174	chuckv	1293	Vector3d pos = (*SD)->getPos();
175			Enriched_Point_3* pt = new Enriched_Point_3(pos.x(),pos.y(),pos.z());
176			pt->setSD(*SD);
177			points.push_back(*pt);
178			// myMap[pt]=(*SD);
179	chuckv	1242	}
180
181			// define object to hold convex hull
182	chuckv	1261	CGAL::Object ch_object_;
183			Polyhedron_3 polyhedron;
184
185	chuckv	1242	// compute convex hull
186	chuckv	1293
187			std::vector<Enriched_Point_3>::iterator testpt;
188
189
190
191			CGAL::convex_hull_3(points.begin(), points.end(), polyhedron);
192
193	chuckv	1261
194	chuckv	1293
195			Ns_ = polyhedron.size_of_vertices();
196
197			#ifdef IS_MPI
198			/* Gather an array of the number of verticies on each processor */
199
200
201			surfacePtsGlobal_.clear();
202			surfacePtsLocal_.clear();
203
204			MPI::COMM_WORLD.Allgather(&Ns_,1,MPI::INT,&NstoProc_[0],1,MPI::INT);
205
206			for (int i = 0; i < nproc_; i++){
207			Nsglobal_ += NstoProc_[i];
208			}
209			/Reminder ideally, we would like to reserve size for the vectors here/
210			surfacePtsLocal_.reserve(Ns_);
211			surfacePtsGlobal_.resize(Nsglobal_);
212			// std::fill(surfacePtsGlobal_.begin(),surfacePtsGlobal_.end(),0);
213
214			/* Build a displacements array */
215			for (int i = 1; i < nproc_; i++){
216			displs_[i] = displs_[i-1] + NstoProc_[i-1];
217			}
218
219			int noffset = displs_[myrank_];
220			/* gather the potential hull */
221
222
223			for (hc =polyhedron.points_begin();hc != polyhedron.points_end(); ++hc){
224			Point_3 mypoint = *hc;
225			surfacePt_ mpiSurfacePt;
226			mpiSurfacePt.x = CGAL::to_double(mypoint.x());
227			mpiSurfacePt.y = CGAL::to_double(mypoint.y());
228			mpiSurfacePt.z = CGAL::to_double(mypoint.z());
229			surfacePtsLocal_.push_back(mpiSurfacePt);
230			}
231
232			MPI::COMM_WORLD.Allgatherv(&surfacePtsLocal_[0],Ns_,surfacePtType,&surfacePtsGlobal_[0],NstoProc_,displs_,surfacePtType);
233			std::vector<surfacePt_>::iterator spt;
234			std::vector<Enriched_Point_3> gblpoints;
235
236			int mine = 0;
237			int pointidx = 0;
238			for (spt = surfacePtsGlobal_.begin(); spt != surfacePtsGlobal_.end(); ++spt)
239			{
240			surfacePt_ thispos = *spt;
241			Enriched_Point_3 ept(thispos.x,thispos.y,thispos.z);
242			if (mine >= noffset && mine < noffset + Ns_){
243			ept.myPoint();
244			ept.setSD(points[pointidx].getStuntDouble());
245			pointidx++;
246			}
247			gblpoints.push_back(ept);
248
249			mine++;
250	chuckv	1261	}
251
252	chuckv	1293	/* Compute the global hull */
253			polyhedron.clear();
254			CGAL::convex_hull_3(gblpoints.begin(), gblpoints.end(), polyhedron);
255
256
257			#endif
258
259
260
261			/* Loop over all of the surface triangles and build data structures for atoms and normals*/
262			Facet_iterator j;
263			area_ = 0;
264			for ( j = polyhedron.facets_begin(); j !=polyhedron.facets_end(); ++j) {
265			Halfedge_handle h = j->halfedge();
266
267			Point_3 r0=h->vertex()->point();
268			Point_3 r1=h->next()->vertex()->point();
269			Point_3 r2=h->next()->next()->vertex()->point();
270
271			Point_3* pr0 = &r0;
272			Point_3* pr1 = &r1;
273			Point_3* pr2 = &r2;
274
275			Enriched_Point_3* er0 = static_cast<Enriched_Point_3*>(pr0);
276			Enriched_Point_3* er1 = static_cast<Enriched_Point_3*>(pr1);
277			Enriched_Point_3* er2 = static_cast<Enriched_Point_3*>(pr2);
278
279			// StuntDouble* sd = er0->getStuntDouble();
280			std::cerr << "sd globalIndex = " << to_double(er0->x()) << "\n";
281
282			Point_3 thisCentroid = CGAL::centroid(r0,r1,r2);
283
284			Vector_3 normal = CGAL::cross_product(r1-r0,r2-r0);
285
286			Triangle* face = new Triangle();
287			Vector3d V3dNormal(CGAL::to_double(normal.x()),CGAL::to_double(normal.y()),CGAL::to_double(normal.z()));
288			Vector3d V3dCentroid(CGAL::to_double(thisCentroid.x()),CGAL::to_double(thisCentroid.y()),CGAL::to_double(thisCentroid.z()));
289			face->setNormal(V3dNormal);
290			face->setCentroid(V3dCentroid);
291			RealType faceArea = 0.5*V3dNormal.length();
292			face->setArea(faceArea);
293			area_ += faceArea;
294			Triangles_.push_back(face);
295			// ptMapType::const_iterator locn=myMap.find(mypoint);
296			// int myIndex = locn->second;
297
298			}
299
300			std::cout << "Number of surface atoms is: " << Ns_ << std::endl;
301
302
303
304			}
305			void ConvexHull::printHull(const std::string& geomFileName)
306			{
307	chuckv	1261	/*
308	chuckv	1293	std::ofstream newGeomFile;
309
310			//create new .md file based on old .md file
311			newGeomFile.open("testhull.off");
312
313			// Write polyhedron in Object File Format (OFF).
314			CGAL::set_ascii_mode( std::cout);
315			newGeomFile << "OFF" << std::endl << polyhedron.size_of_vertices() << ' '
316			<< polyhedron.size_of_facets() << " 0" << std::endl;
317			std::copy( polyhedron.points_begin(), polyhedron.points_end(),
318			std::ostream_iterator<Point_3>( newGeomFile, "\n"));
319			for ( Facet_iterator i = polyhedron.facets_begin(); i != polyhedron.facets_end(); ++i) {
320			Halfedge_facet_circulator j = i->facet_begin();
321			// Facets in polyhedral surfaces are at least triangles.
322			CGAL_assertion( CGAL::circulator_size(j) >= 3);
323			newGeomFile << CGAL::circulator_size(j) << ' ';
324			do {
325			newGeomFile << ' ' << std::distance(polyhedron.vertices_begin(), j->vertex());
326			} while ( ++j != i->facet_begin());
327			newGeomFile << std::endl;
328	chuckv	1242	}
329	chuckv	1293
330			newGeomFile.close();
331	chuckv	1261	*/
332	chuckv	1293	/*
333			std::ofstream newGeomFile;
334
335			//create new .md file based on old .md file
336			newGeomFile.open(geomFileName.c_str());
337
338			// Write polyhedron in Object File Format (OFF).
339			CGAL::set_ascii_mode( std::cout);
340			newGeomFile << "OFF" << std::endl << ch_polyhedron.size_of_vertices() << ' '
341			<< ch_polyhedron.size_of_facets() << " 0" << std::endl;
342			std::copy( ch_polyhedron.points_begin(), ch_polyhedron.points_end(),
343			std::ostream_iterator<Point_3>( newGeomFile, "\n"));
344			for ( Facet_iterator i = ch_polyhedron.facets_begin(); i != ch_polyhedron.facets_end(); ++i)
345			{
346			Halfedge_facet_circulator j = i->facet_begin();
347			// Facets in polyhedral surfaces are at least triangles.
348			CGAL_assertion( CGAL::circulator_size(j) >= 3);
349			newGeomFile << CGAL::circulator_size(j) << ' ';
350			do
351			{
352			newGeomFile << ' ' << std::distance(ch_polyhedron.vertices_begin(), j->vertex());
353			}
354			while ( ++j != i->facet_begin());
355			newGeomFile << std::endl;
356			}
357
358			newGeomFile.close();
359			*/
360
361	chuckv	1242	}
362	chuckv	1188
363
364
365	chuckv	1293
366
367
368
369	chuckv	1242	#else
370			#ifdef HAVE_QHULL
371			/* Old options Qt Qu Qg QG0 FA */
372	chuckv	1293	ConvexHull::ConvexHull() : Hull(), dim_(3), options_("qhull Qt Qci Tcv Pp") {
373			//If we are doing the mpi version, set up some vectors for data communication
374			#ifdef IS_MPI
375	chuckv	1188
376	chuckv	1293
377			nproc_ = MPI::COMM_WORLD.Get_size();
378			myrank_ = MPI::COMM_WORLD.Get_rank();
379			NstoProc_ = new int[nproc_];
380			displs_ = new int[nproc_];
381
382			// Create a surface point type in MPI to send
383			surfacePtType = MPI::DOUBLE.Create_contiguous(3);
384			surfacePtType.Commit();
385
386
387			#endif
388			}
389
390
391
392			void ConvexHull::computeHull(std::vector<StuntDouble*> bodydoubles)
393	chuckv	1242	{
394
395	chuckv	1293	std::vector<int> surfaceIDs;
396			std::vector<int> surfaceIDsGlobal;
397			std::vector<int> localPtsMap;
398			int numpoints = bodydoubles.size();
399
400			//coordT* pt_array;
401			coordT* surfpt_array;
402			vertexT vertex, *vertexp;
403			facetT *facet;
404			setT *vertices;
405			int curlong,totlong;
406			int id;
407	chuckv	1242
408	chuckv	1293	coordT point,*pointp;
409
410
411	chuckv	1242	FILE *outdummy = NULL;
412			FILE *errdummy = NULL;
413
414	chuckv	1293	//pt_array = (coordT) malloc(sizeof(coordT) (numpoints * dim_));
415
416			double* ptArray = new double[numpoints * 3];
417			std::vector<bool> isSurfaceID(numpoints);
418
419			// Copy the positon vector into a points vector for qhull.
420			std::vector<StuntDouble*>::iterator SD;
421			int i = 0;
422			for (SD =bodydoubles.begin(); SD != bodydoubles.end(); ++SD)
423			{
424			Vector3d pos = (*SD)->getPos();
425
426			ptArray[dim_ * i] = pos.x();
427			ptArray[dim_ * i + 1] = pos.y();
428			ptArray[dim_ * i + 2] = pos.z();
429			i++;
430			}
431	chuckv	1242
432	chuckv	1293
433	chuckv	1242
434
435
436
437	chuckv	1293	boolT ismalloc = False;
438			Triangles_.clear();
439			surfaceSDs_.clear();
440	chuckv	1242
441	chuckv	1293	if (qh_new_qhull(dim_, numpoints, ptArray, ismalloc,
442			const_cast<char *>(options_.c_str()), NULL, stderr)) {
443	chuckv	1188
444	chuckv	1293	sprintf(painCave.errMsg, "ConvexHull: Qhull failed to compute convex hull");
445			painCave.isFatal = 0;
446			simError();
447
448			} //qh_new_qhull
449
450
451			#ifdef IS_MPI
452			std::vector<double> localPts;
453			int localPtArraySize;
454	chuckv	1242
455	chuckv	1293	std::fill(isSurfaceID.begin(),isSurfaceID.end(),false);
456
457			FORALLfacets {
458	chuckv	1242
459	chuckv	1293	if (!facet->simplicial){
460	chuckv	1242	// should never happen with Qt
461			sprintf(painCave.errMsg, "ConvexHull: non-simplicaial facet detected");
462			painCave.isFatal = 0;
463			simError();
464	chuckv	1293	}
465
466
467			vertices = qh_facet3vertex(facet);
468			FOREACHvertex_(vertices){
469	chuckv	1242	id = qh_pointid(vertex->point);
470	chuckv	1293
471			if( !isSurfaceID[id] ){
472			isSurfaceID[id] = true;
473	chuckv	1242	}
474	chuckv	1293	}
475			qh_settempfree(&vertices);
476	chuckv	1242
477	chuckv	1293	} //FORALLfacets
478	chuckv	1188
479	chuckv	1293
480	chuckv	1188
481	chuckv	1293	/*
482			std::sort(surfaceIDs.begin(),surfaceIDs.end());
483			surfaceIDs.erase(std::unique(surfaceIDs.begin(), surfaceIDs.end()), surfaceIDs.end());
484			int localPtArraySize = surfaceIDs.size() * 3;
485			*/
486	chuckv	1188
487	chuckv	1293	localPts.resize(localPtArraySize);
488			// std::fill(localPts.begin(),globalPts.end(),0.0);
489	chuckv	1188
490	chuckv	1293
491			int idx = 0;
492			// Copy the surface points into an array.
493			for(std::vector<bool>::iterator list_iter = isSurfaceID.begin();
494			list_iter != isSurfaceID.end(); list_iter++)
495			{
496			bool isIt = *list_iter;
497			if (isIt){
498			localPts.push_back(ptArray[dim_ * idx]);
499			localPts.push_back(ptArray[dim_ * idx + 1]);
500			localPts.push_back(ptArray[dim_ * idx + 2]);
501			localPtsMap.push_back(idx);
502			} //Isit
503			idx++;
504			} //isSurfaceID
505	chuckv	1242
506	chuckv	1293
507			localPtArraySize = localPts.size();
508			MPI::COMM_WORLD.Allgather(&localPtArraySize,1,MPI::INT,&NstoProc_[0],1,MPI::INT);
509
510			for (int i = 0; i < nproc_; i++){
511			Nsglobal_ += NstoProc_[i];
512			}
513
514			std::vector<double> globalPts;
515			globalPts.resize(Nsglobal_);
516			isSurfaceID.resize(int(Nsglobal_/3));
517			std::fill(globalPts.begin(),globalPts.end(),0.0);
518			/* Build a displacements array */
519			for (int i = 1; i < nproc_; i++){
520			displs_[i] = displs_[i-1] + NstoProc_[i-1];
521			}
522	chuckv	1242
523	chuckv	1293	int noffset = displs_[myrank_];
524			/* gather the potential hull */
525	chuckv	1242
526	chuckv	1293	MPI::COMM_WORLD.Allgatherv(&localPts[0],localPtArraySize,MPI::DOUBLE,&globalPts[0],NstoProc_,displs_,MPI::DOUBLE);
527
528
529
530
531			// Free previous hull
532	chuckv	1242	qh_freeqhull(!qh_ALL);
533			qh_memfreeshort(&curlong, &totlong);
534			if (curlong \|\| totlong)
535			std::cerr << "qhull internal warning (main): did not free %d bytes of long memory (%d pieces) "
536			<< totlong << curlong << std::endl;
537	chuckv	1293
538			if (qh_new_qhull(dim_, numpoints, &globalPts[0], ismalloc,
539			const_cast<char *>(options_.c_str()), NULL, stderr)){
540
541			sprintf(painCave.errMsg, "ConvexHull: Qhull failed to compute global convex hull");
542			painCave.isFatal = 0;
543			simError();
544
545			} //qh_new_qhull
546
547			#endif
548
549
550
551
552
553
554			unsigned int nf = qh num_facets;
555
556			/* Build Surface SD list first */
557
558			std::fill(isSurfaceID.begin(),isSurfaceID.end(),false);
559
560			FORALLfacets {
561
562			if (!facet->simplicial){
563			// should never happen with Qt
564			sprintf(painCave.errMsg, "ConvexHull: non-simplicaial facet detected");
565			painCave.isFatal = 0;
566			simError();
567			} //simplicical
568
569			Triangle* face = new Triangle();
570			Vector3d V3dNormal(facet->normal[0],facet->normal[1],facet->normal[2]);
571			face->setNormal(V3dNormal);
572			//face->setCentroid(V3dCentroid);
573			RealType faceArea = 0.5*V3dNormal.length();
574			face->setArea(faceArea);
575
576
577			vertices = qh_facet3vertex(facet);
578			FOREACHvertex_(vertices){
579			id = qh_pointid(vertex->point);
580			face->addVertex(bodydoubles[id]);
581			if( !isSurfaceID[id] ){
582			isSurfaceID[id] = true;
583			surfaceSDs_.push_back(bodydoubles[id]);
584			} //IF isSurfaceID
585			} //Foreachvertex
586
587
588			Triangles_.push_back(face);
589			qh_settempfree(&vertices);
590
591			} //FORALLfacets
592
593
594
595
596			/*
597			std::sort(surfaceIDs.begin(),surfaceIDs.end());
598			surfaceIDs.erase(std::unique(surfaceIDs.begin(), surfaceIDs.end()), surfaceIDs.end());
599			for(std::vector<int>::iterator list_iter = surfaceIDs.begin();
600			list_iter != surfaceIDs.end(); list_iter++)
601	chuckv	1242	{
602			int i = *list_iter;
603	chuckv	1293	surfaceSDs_.push_back(bodydoubles[i]);
604	chuckv	1242	}
605	chuckv	1293	*/
606	chuckv	1188
607
608
609	chuckv	1097
610	chuckv	1143
611	chuckv	1188
612	chuckv	1293	Ns_ = surfaceSDs_.size();
613
614
615			qh_getarea(qh facet_list);
616			volume_ = qh totvol;
617			area_ = qh totarea;
618
619
620
621			qh_freeqhull(!qh_ALL);
622			qh_memfreeshort(&curlong, &totlong);
623			if (curlong \|\| totlong)
624			std::cerr << "qhull internal warning (main): did not free %d bytes of long memory (%d pieces) "
625			<< totlong << curlong << std::endl;
626
627
628			// free(pt_array);
629
630	chuckv	1097	}
631
632	chuckv	1293
633
634			void ConvexHull::printHull(const std::string& geomFileName)
635	chuckv	1188	{
636	chuckv	1137
637	chuckv	1242	FILE *newGeomFile;
638
639			//create new .md file based on old .md file
640			newGeomFile = fopen(geomFileName.c_str(), "w");
641			qh_findgood_all(qh facet_list);
642			for (int i = 0; i < qh_PRINTEND; i++)
643			qh_printfacets(newGeomFile, qh PRINTout[i], qh facet_list, NULL, !qh_ALL);
644
645			fclose(newGeomFile);
646	chuckv	1097	}
647	chuckv	1242	#endif //QHULL
648			#endif //CGAL
649	chuckv	1097
650	chuckv	1188
651