Changeset 70c4567 for molecuilder/src/tesselation.cpp

Timestamp:

Aug 10, 2009, 4:11:47 PM (16 years ago)

Author:

Frederik Heber <heber@…>

Children:

ada6d2

Parents:

0cf171

Message:

New function ConvexizeNonconvexEnvelope() to calculate the volume of a non-convex envelope.

The central idea is that the volume of a convex envelope is easy to determine as a sum of pyramids with respect to a center inside the envelope. Hence, if we can "reduce" the non-convex envelope to a convex one in such a way that we know the added volume, we may determine the volume of a non-convex envelope.
The nice side effect is that we may use our Find_non_convex_border() algorithm to calculate also the convex envelope.

• We go through all BoundaryPoints and check whether one of its Baselines does not fulfill the ConvexCriterion. If so, we remove it, as it can not be a boundary point on the convex envelope, and re-construct the attached triangles. The added volume is a general tetraeder, whose formula is known.
• FIX: Find_convex_border() - We check whether AddPoint is successful or not.
• builder.cpp: case 'o' - changed to use ConvexizeNonconvexEnvelope() instead of Find_convex_border()
• Tesselation:AddPoint() - now takes second argument which is the index for BPS and always set BPS to either the newly created or the already present point. Return argument discerns between new and already present point.
• Tesselation::BPS, BLS, BTS are now public not private. We have to access them from ConvexizeNonconvexEnvelope()

File:

• molecuilder/src/tesselation.cpp (modified) (3 diffs)

molecuilder/src/tesselation.cpp

@@ -208 +208 @@
  * \return NULL - if endpoint not contained in BoundaryLineSet, or pointer to BoundaryPointSet otherwise
  */
-inline class BoundaryPointSet *BoundaryLineSet::GetOtherEndpoint(class BoundaryPointSet *point)
+class BoundaryPointSet *BoundaryLineSet::GetOtherEndpoint(class BoundaryPointSet *point)
 {
   if (endpoints[0] == point)
@@ -1044 +1044 @@
         // add Walker to boundary points
         *out << Verbose(2) << "Adding " << *Walker << " to BoundaryPoints." << endl;
-        AddPoint(Walker);
-        if (BPS[0] != NULL)
+        if (AddPoint(Walker,0))
           NewPoint = BPS[0];
         else
@@ -1100 +1099 @@
 /** Adds an point to the tesselation::PointsOnBoundary list.
  * \param *Walker point to add
- */
-void
-Tesselation::AddPoint(TesselPoint *Walker)
+ * \param n TesselStruct::BPS index to put pointer into
+ * \return true - new point was added, false - point already present
+ */
+bool
+Tesselation::AddPoint(TesselPoint *Walker, int n)
 {
   PointTestPair InsertUnique;
-  BPS[0] = new class BoundaryPointSet(Walker);
-  InsertUnique = PointsOnBoundary.insert(PointPair(Walker->nr, BPS[0]));
-  if (InsertUnique.second) // if new point was not present before, increase counter
+  BPS[n] = new class BoundaryPointSet(Walker);
+  InsertUnique = PointsOnBoundary.insert(PointPair(Walker->nr, BPS[n]));
+  if (InsertUnique.second) { // if new point was not present before, increase counter
     PointsOnBoundaryCount++;
-  else {
-    delete(BPS[0]);
-    BPS[0] = NULL;
+    return true;
+  } else {
+    delete(BPS[n]);
+    BPS[n] = InsertUnique.first->second;
+    return false;
   }
 }