src/math/ConvexHull.cpp

/* Copyright (c) 2008, 2009 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.16 2009-10-20 20:05:28 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"

#ifdef IS_MPI
#include <mpi.h>
#endif

using namespace oopse;

#ifdef HAVE_QHULL
extern "C"
{
#include <qhull/qhull.h>
#include <qhull/mem.h>
#include <qhull/qset.h>
#include <qhull/geom.h>
#include <qhull/merge.h>
#include <qhull/poly.h>
#include <qhull/io.h>
#include <qhull/stat.h>
}

/* Old options Qt Qu Qg QG0 FA */
/* More old opts Qc Qi Pp*/

ConvexHull::ConvexHull() : Hull(), dim_(3), options_("qhull Qt Pp") {
}

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

  Triangles_.clear();
  
  vertexT *vertex, **vertexp;
  facetT *facet;
  setT *vertices;
  int curlong, totlong;
  
  std::vector<double> ptArray(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;
  /* Clean up memory from previous convex hull calculations*/
  
  if (qh_new_qhull(dim_, numpoints, &ptArray[0], ismalloc,
                   const_cast<char *>(options_.c_str()), NULL, stderr)) {

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


#ifdef IS_MPI
  //If we are doing the mpi version, set up some vectors for data communication
  
  int nproc = MPI::COMM_WORLD.Get_size();
  int myrank = MPI::COMM_WORLD.Get_rank();
  int localHullSites = 0;
  int* hullSitesOnProc = new int[nproc];
  int* coordsOnProc = new int[nproc];
  int* displacements = new int[nproc];
  int* vectorDisplacements = new int[nproc];

  std::vector<double> coords;
  std::vector<double> vels;
  std::vector<int> objectIDs;
  std::vector<double> masses;

  FORALLvertices{
    localHullSites++;
    
    int idx = qh_pointid(vertex->point);
    coords.push_back(ptArray[dim_  * idx]);
    coords.push_back(ptArray[dim_  * idx + 1]);
    coords.push_back(ptArray[dim_  * idx + 2]);

    StuntDouble* sd = bodydoubles[idx];

    Vector3d vel = sd->getVel();
    vels.push_back(vel.x());
    vels.push_back(vel.y());
    vels.push_back(vel.z());

    masses.push_back(sd->getMass());
  }

  MPI::COMM_WORLD.Allgather(&localHullSites, 1, MPI::INT, &hullSitesOnProc[0],
                            1, MPI::INT);

  int globalHullSites = 0;
  for (int iproc = 0; i < nproc; iproc++){
    globalHullSites += hullSitesOnProc[iproc];
    coordsOnProc[iproc] = dim_ * hullSitesOnProc[iproc];
  }

  displacements[0] = 0;
  vectorDisplacements[0] = 0;
  
  for (int iproc = 1; i < nproc; iproc++){
    displacements[iproc] = displacements[iproc-1] + hullSitesOnProc[iproc-1];
    vectorDisplacements[iproc] = vectorDisplacements[iproc-1] + coordsOnProc[iproc-1]; 
  }

  std::vector<double> globalCoords(dim_*globalHullSites);
  std::vector<double> globalVels(dim_*globalHullSites);
  std::vector<double> globalMasses(globalHullSites);
  int count = coordsOnProc[myrank];
  
  MPI::COMM_WORLD.Allgatherv(&coords[0], count, MPI::DOUBLE,
                             &globalCoords[0], &coordsOnProc[0], &vectorDisplacements[0],
                             MPI::DOUBLE);

  MPI::COMM_WORLD.Allgatherv(&vels[0], count, MPI::DOUBLE,
                             &globalVels[0], &coordsOnProc[0], &vectorDisplacements[0],
                             MPI::DOUBLE);

  MPI::COMM_WORLD.Allgatherv(&masses[0], localHullSites, MPI::DOUBLE,
                             &globalMasses[0], &hullSitesOnProc[0], &displacements[0],
                             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_, globalHullSites, &globalCoords[0], ismalloc,
                   const_cast<char *>(options_.c_str()), NULL, stderr)){
    
    sprintf(painCave.errMsg, "ConvexHull: Qhull failed to compute global convex hull");
    painCave.isFatal = 1;
    simError();
    
  } //qh_new_qhull

#endif

  FORALLfacets {  
    Triangle face;

    Vector3d V3dNormal(facet->normal[0], facet->normal[1], facet->normal[2]);
    face.setNormal(V3dNormal);
    
    RealType faceArea = qh_facetarea(facet);
    face.setArea(faceArea);
    
    vertices = qh_facet3vertex(facet);
      
    coordT *center = qh_getcenter(vertices);
    Vector3d V3dCentroid(center[0], center[1], center[2]);
    face.setCentroid(V3dCentroid);

    Vector3d faceVel = V3Zero;
    Vector3d p[3];
    RealType faceMass = 0.0;
    int ver = 0;

    FOREACHvertex_(vertices){
      int id = qh_pointid(vertex->point);
      p[ver][0] = vertex->point[0];
      p[ver][1] = vertex->point[1];
      p[ver][2] = vertex->point[2];
      
      Vector3d vel;
      RealType mass;

#ifdef IS_MPI
      vel = Vector3d(globalVels[dim_ * id],
                     globalVels[dim_ * id + 1], 
                     globalVels[dim_ * id + 2]);
      mass = globalMasses[id];

      // localID will be between 0 and hullSitesOnProc[myrank] if we own this guy.
      int localID = id - displacements[myrank];
      if (id >= 0 && id < hullSitesOnProc[myrank])
        face.addVertexSD(bodydoubles[localID]);
      else
        face.addVertexSD(NULL);
#else
      vel = bodydoubles[id]->getVel();
      mass = bodydoubles[id]->getMass();
      face.addVertexSD(bodydoubles[id]);      
#endif
        
      faceVel = faceVel + vel;
      faceMass = faceMass + mass;
      ver++;      
    } //Foreachvertex

    face.addVertices(p[0], p[1], p[2]);
    face.setFacetMass(faceMass);
    face.setFacetVelocity(faceVel/3.0);
    Triangles_.push_back(face);
    qh_settempfree(&vertices);      

  } //FORALLfacets
  
  qh_getarea(qh facet_list);
  volume_ = qh totvol;
  area_ = qh totarea;

#ifdef IS_MPI
  delete [] hullSitesOnProc;
  delete [] coordsOnProc;
  delete [] displacements;
  delete [] vectorDisplacements;
#endif
  
  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;    
}


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
Revision:	1374
Committed:	Tue Oct 20 20:05:28 2009 UTC (15 years, 6 months ago) by chuckv
File size:	9358 byte(s)
Log Message:	Re-write of ConvexHull.
#	User	Rev	Content
1	chuckv	1365	/* Copyright (c) 2008, 2009 The University of Notre Dame. All Rights Reserved.
2	chuckv	1097	*
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	1374	* @version $Id: ConvexHull.cpp,v 1.16 2009-10-20 20:05:28 chuckv Exp $
48	chuckv	1097	*
49			*/
50
51	chuckv	1242	/* Standard includes independent of library */
52	chuckv	1374
53	chuckv	1097	#include <iostream>
54			#include <fstream>
55	chuckv	1188	#include <list>
56			#include <algorithm>
57			#include <iterator>
58	chuckv	1141	#include "math/ConvexHull.hpp"
59	chuckv	1188	#include "utils/simError.h"
60	chuckv	1293
61			#ifdef IS_MPI
62	chuckv	1374	#include <mpi.h>
63	chuckv	1293	#endif
64
65	chuckv	1374	using namespace oopse;
66	chuckv	1293
67	chuckv	1374	#ifdef HAVE_QHULL
68			extern "C"
69	chuckv	1242	{
70	chuckv	1374	#include <qhull/qhull.h>
71			#include <qhull/mem.h>
72			#include <qhull/qset.h>
73			#include <qhull/geom.h>
74			#include <qhull/merge.h>
75			#include <qhull/poly.h>
76			#include <qhull/io.h>
77			#include <qhull/stat.h>
78	chuckv	1293	}
79
80	chuckv	1242	/* Old options Qt Qu Qg QG0 FA */
81	chuckv	1304	/* More old opts Qc Qi Pp*/
82	chuckv	1188
83	chuckv	1374	ConvexHull::ConvexHull() : Hull(), dim_(3), options_("qhull Qt Pp") {
84			}
85	chuckv	1293
86	chuckv	1374	void ConvexHull::computeHull(std::vector<StuntDouble*> bodydoubles) {
87	chuckv	1293
88	chuckv	1374	int numpoints = bodydoubles.size();
89	chuckv	1293
90	chuckv	1374	Triangles_.clear();
91	chuckv	1242
92	chuckv	1293	vertexT vertex, *vertexp;
93			facetT *facet;
94			setT *vertices;
95	chuckv	1374	int curlong, totlong;
96	chuckv	1242
97	chuckv	1302	std::vector<double> ptArray(numpoints*3);
98	chuckv	1293	std::vector<bool> isSurfaceID(numpoints);
99
100			// Copy the positon vector into a points vector for qhull.
101			std::vector<StuntDouble*>::iterator SD;
102			int i = 0;
103	chuckv	1374	for (SD =bodydoubles.begin(); SD != bodydoubles.end(); ++SD){
104			Vector3d pos = (*SD)->getPos();
105			ptArray[dim_ * i] = pos.x();
106			ptArray[dim_ * i + 1] = pos.y();
107			ptArray[dim_ * i + 2] = pos.z();
108			i++;
109			}
110	chuckv	1242
111	chuckv	1293	boolT ismalloc = False;
112	chuckv	1302	/* Clean up memory from previous convex hull calculations*/
113	chuckv	1308
114	chuckv	1302	if (qh_new_qhull(dim_, numpoints, &ptArray[0], ismalloc,
115	chuckv	1374	const_cast<char *>(options_.c_str()), NULL, stderr)) {
116	chuckv	1188
117	chuckv	1374	sprintf(painCave.errMsg, "ConvexHull: Qhull failed to compute convex hull");
118			painCave.isFatal = 1;
119			simError();
120
121	chuckv	1293	} //qh_new_qhull
122
123
124			#ifdef IS_MPI
125	chuckv	1374	//If we are doing the mpi version, set up some vectors for data communication
126	chuckv	1242
127	chuckv	1374	int nproc = MPI::COMM_WORLD.Get_size();
128			int myrank = MPI::COMM_WORLD.Get_rank();
129			int localHullSites = 0;
130			int* hullSitesOnProc = new int[nproc];
131			int* coordsOnProc = new int[nproc];
132			int* displacements = new int[nproc];
133			int* vectorDisplacements = new int[nproc];
134	chuckv	1293
135	chuckv	1374	std::vector<double> coords;
136			std::vector<double> vels;
137			std::vector<int> objectIDs;
138			std::vector<double> masses;
139
140			FORALLvertices{
141			localHullSites++;
142	chuckv	1242
143	chuckv	1374	int idx = qh_pointid(vertex->point);
144			coords.push_back(ptArray[dim_ * idx]);
145			coords.push_back(ptArray[dim_ * idx + 1]);
146			coords.push_back(ptArray[dim_ * idx + 2]);
147	chuckv	1293
148	chuckv	1374	StuntDouble* sd = bodydoubles[idx];
149	chuckv	1188
150	chuckv	1374	Vector3d vel = sd->getVel();
151			vels.push_back(vel.x());
152			vels.push_back(vel.y());
153			vels.push_back(vel.z());
154	chuckv	1188
155	chuckv	1374	masses.push_back(sd->getMass());
156			}
157	chuckv	1188
158	chuckv	1374	MPI::COMM_WORLD.Allgather(&localHullSites, 1, MPI::INT, &hullSitesOnProc[0],
159			1, MPI::INT);
160	chuckv	1307
161	chuckv	1374	int globalHullSites = 0;
162			for (int iproc = 0; i < nproc; iproc++){
163			globalHullSites += hullSitesOnProc[iproc];
164			coordsOnProc[iproc] = dim_ * hullSitesOnProc[iproc];
165	chuckv	1302	}
166	chuckv	1293
167	chuckv	1374	displacements[0] = 0;
168			vectorDisplacements[0] = 0;
169	chuckv	1316
170	chuckv	1374	for (int iproc = 1; i < nproc; iproc++){
171			displacements[iproc] = displacements[iproc-1] + hullSitesOnProc[iproc-1];
172			vectorDisplacements[iproc] = vectorDisplacements[iproc-1] + coordsOnProc[iproc-1];
173	chuckv	1293	}
174
175	chuckv	1374	std::vector<double> globalCoords(dim_*globalHullSites);
176			std::vector<double> globalVels(dim_*globalHullSites);
177			std::vector<double> globalMasses(globalHullSites);
178			int count = coordsOnProc[myrank];
179	chuckv	1365
180	chuckv	1374	MPI::COMM_WORLD.Allgatherv(&coords[0], count, MPI::DOUBLE,
181			&globalCoords[0], &coordsOnProc[0], &vectorDisplacements[0],
182			MPI::DOUBLE);
183	chuckv	1302
184	chuckv	1374	MPI::COMM_WORLD.Allgatherv(&vels[0], count, MPI::DOUBLE,
185			&globalVels[0], &coordsOnProc[0], &vectorDisplacements[0],
186			MPI::DOUBLE);
187	chuckv	1302
188	chuckv	1374	MPI::COMM_WORLD.Allgatherv(&masses[0], localHullSites, MPI::DOUBLE,
189			&globalMasses[0], &hullSitesOnProc[0], &displacements[0],
190			MPI::DOUBLE);
191	chuckv	1365
192	chuckv	1293	// Free previous hull
193	chuckv	1242	qh_freeqhull(!qh_ALL);
194			qh_memfreeshort(&curlong, &totlong);
195			if (curlong \|\| totlong)
196			std::cerr << "qhull internal warning (main): did not free %d bytes of long memory (%d pieces) "
197			<< totlong << curlong << std::endl;
198	chuckv	1374
199			if (qh_new_qhull(dim_, globalHullSites, &globalCoords[0], ismalloc,
200			const_cast<char *>(options_.c_str()), NULL, stderr)){
201
202			sprintf(painCave.errMsg, "ConvexHull: Qhull failed to compute global convex hull");
203			painCave.isFatal = 1;
204			simError();
205
206	chuckv	1293	} //qh_new_qhull
207
208			#endif
209
210	chuckv	1374	FORALLfacets {
211			Triangle face;
212	chuckv	1293
213	chuckv	1374	Vector3d V3dNormal(facet->normal[0], facet->normal[1], facet->normal[2]);
214			face.setNormal(V3dNormal);
215	chuckv	1371
216	chuckv	1374	RealType faceArea = qh_facetarea(facet);
217			face.setArea(faceArea);
218
219			vertices = qh_facet3vertex(facet);
220	chuckv	1293
221	chuckv	1374	coordT *center = qh_getcenter(vertices);
222			Vector3d V3dCentroid(center[0], center[1], center[2]);
223			face.setCentroid(V3dCentroid);
224	chuckv	1304
225	chuckv	1374	Vector3d faceVel = V3Zero;
226			Vector3d p[3];
227			RealType faceMass = 0.0;
228			int ver = 0;
229	chuckv	1293
230	chuckv	1374	FOREACHvertex_(vertices){
231			int id = qh_pointid(vertex->point);
232			p[ver][0] = vertex->point[0];
233			p[ver][1] = vertex->point[1];
234			p[ver][2] = vertex->point[2];
235
236			Vector3d vel;
237			RealType mass;
238	chuckv	1293
239	chuckv	1302	#ifdef IS_MPI
240	chuckv	1374	vel = Vector3d(globalVels[dim_ * id],
241			globalVels[dim_ * id + 1],
242			globalVels[dim_ * id + 2]);
243			mass = globalMasses[id];
244
245			// localID will be between 0 and hullSitesOnProc[myrank] if we own this guy.
246			int localID = id - displacements[myrank];
247			if (id >= 0 && id < hullSitesOnProc[myrank])
248			face.addVertexSD(bodydoubles[localID]);
249			else
250			face.addVertexSD(NULL);
251	chuckv	1307	#else
252	chuckv	1374	vel = bodydoubles[id]->getVel();
253			mass = bodydoubles[id]->getMass();
254			face.addVertexSD(bodydoubles[id]);
255	chuckv	1302	#endif
256	chuckv	1374
257			faceVel = faceVel + vel;
258			faceMass = faceMass + mass;
259			ver++;
260			} //Foreachvertex
261	chuckv	1302
262	chuckv	1374	face.addVertices(p[0], p[1], p[2]);
263			face.setFacetMass(faceMass);
264			face.setFacetVelocity(faceVel/3.0);
265			Triangles_.push_back(face);
266			qh_settempfree(&vertices);
267
268			} //FORALLfacets
269
270			qh_getarea(qh facet_list);
271			volume_ = qh totvol;
272			area_ = qh totarea;
273
274	chuckv	1302	#ifdef IS_MPI
275	chuckv	1374	delete [] hullSitesOnProc;
276			delete [] coordsOnProc;
277			delete [] displacements;
278			delete [] vectorDisplacements;
279	chuckv	1302	#endif
280	chuckv	1374
281			qh_freeqhull(!qh_ALL);
282			qh_memfreeshort(&curlong, &totlong);
283			if (curlong \|\| totlong)
284			std::cerr << "qhull internal warning (main): did not free %d bytes of long memory (%d pieces) "
285			<< totlong << curlong << std::endl;
286	chuckv	1097	}
287
288	chuckv	1293
289
290	chuckv	1374	void ConvexHull::printHull(const std::string& geomFileName) {
291	chuckv	1242	FILE *newGeomFile;
292
293			//create new .md file based on old .md file
294			newGeomFile = fopen(geomFileName.c_str(), "w");
295			qh_findgood_all(qh facet_list);
296			for (int i = 0; i < qh_PRINTEND; i++)
297			qh_printfacets(newGeomFile, qh PRINTout[i], qh facet_list, NULL, !qh_ALL);
298
299			fclose(newGeomFile);
300	chuckv	1097	}
301	chuckv	1242	#endif //QHULL