Changeset 8544b32 for src/documentation/constructs/tesselation.dox

Timestamp:

Oct 19, 2014, 5:13:11 PM (10 years ago)

Author:

Frederik Heber <heber@…>

Branches:

Action_Thermostats, Add_AtomRandomPerturbation, Add_FitFragmentPartialChargesAction, Add_RotateAroundBondAction, Add_SelectAtomByNameAction, Added_ParseSaveFragmentResults, AddingActions_SaveParseParticleParameters, Adding_Graph_to_ChangeBondActions, Adding_MD_integration_tests, Adding_ParticleName_to_Atom, Adding_StructOpt_integration_tests, AtomFragments, Automaking_mpqc_open, AutomationFragmentation_failures, Candidate_v1.5.4, Candidate_v1.6.0, Candidate_v1.6.1, ChangeBugEmailaddress, ChangingTestPorts, ChemicalSpaceEvaluator, CombiningParticlePotentialParsing, Combining_Subpackages, Debian_Package_split, Debian_package_split_molecuildergui_only, Disabling_MemDebug, Docu_Python_wait, EmpiricalPotential_contain_HomologyGraph, EmpiricalPotential_contain_HomologyGraph_documentation, Enable_parallel_make_install, Enhance_userguide, Enhanced_StructuralOptimization, Enhanced_StructuralOptimization_continued, Example_ManyWaysToTranslateAtom, Exclude_Hydrogens_annealWithBondGraph, FitPartialCharges_GlobalError, Fix_BoundInBox_CenterInBox_MoleculeActions, Fix_ChargeSampling_PBC, Fix_ChronosMutex, Fix_FitPartialCharges, Fix_FitPotential_needs_atomicnumbers, Fix_ForceAnnealing, Fix_IndependentFragmentGrids, Fix_ParseParticles, Fix_ParseParticles_split_forward_backward_Actions, Fix_PopActions, Fix_QtFragmentList_sorted_selection, Fix_Restrictedkeyset_FragmentMolecule, Fix_StatusMsg, Fix_StepWorldTime_single_argument, Fix_Verbose_Codepatterns, Fix_fitting_potentials, Fixes, ForceAnnealing_goodresults, ForceAnnealing_oldresults, ForceAnnealing_tocheck, ForceAnnealing_with_BondGraph, ForceAnnealing_with_BondGraph_continued, ForceAnnealing_with_BondGraph_continued_betteresults, ForceAnnealing_with_BondGraph_contraction-expansion, FragmentAction_writes_AtomFragments, FragmentMolecule_checks_bonddegrees, GeometryObjects, Gui_Fixes, Gui_displays_atomic_force_velocity, ImplicitCharges, IndependentFragmentGrids, IndependentFragmentGrids_IndividualZeroInstances, IndependentFragmentGrids_IntegrationTest, IndependentFragmentGrids_Sole_NN_Calculation, JobMarket_RobustOnKillsSegFaults, JobMarket_StableWorkerPool, JobMarket_unresolvable_hostname_fix, MoreRobust_FragmentAutomation, ODR_violation_mpqc_open, PartialCharges_OrthogonalSummation, PdbParser_setsAtomName, PythonUI_with_named_parameters, QtGui_reactivate_TimeChanged_changes, Recreated_GuiChecks, Rewrite_FitPartialCharges, RotateToPrincipalAxisSystem_UndoRedo, SaturateAtoms_findBestMatching, SaturateAtoms_singleDegree, StoppableMakroAction, Subpackage_CodePatterns, Subpackage_JobMarket, Subpackage_LinearAlgebra, Subpackage_levmar, Subpackage_mpqc_open, Subpackage_vmg, Switchable_LogView, ThirdParty_MPQC_rebuilt_buildsystem, TrajectoryDependenant_MaxOrder, TremoloParser_IncreasedPrecision, TremoloParser_MultipleTimesteps, TremoloParser_setsAtomName, Ubuntu_1604_changes, stable

Children:

991c35

Parents:

e2396e

git-author:

Frederik Heber <heber@…> (10/09/14 08:55:44)

git-committer:

Frederik Heber <heber@…> (10/19/14 17:13:11)

Message:

DOCU: Added extensive explanation how convexization works.

• updated userguide for convex-envelope.

File:

• src/documentation/constructs/tesselation.dox (modified) (3 diffs)

src/documentation/constructs/tesselation.dox

@@ -20 +20 @@
  * to such a surface.
  *
- * \section tesselation-procedure
+ * \section tesselation-procedure Tesselation procedure
  *
  * In the tesselation all atoms act as possible hindrance to a rolling sphere
@@ -34 +34 @@
  * other (although the code for that is not yet fully implemented).
  *
- * \section tesselation-extension
+ * \section tesselation-convexization Making a surface convex
+ *
+ * A closed surface created by the aforementioned procedure can be made convex
+ * by a combination of the following two ways:
+ * -# Removing a point from the surface that is connected to other points only
+ *    by concave lines. This might also be imagined as removing bumps or 
+ *    craters in the surface.
+ * -# flipping a base line or rather adding a general tetrahedron to remove a
+ *    concave line on the surface.
+ *
+ * With the first way one has to pay attention to possible degenerated lines
+ * and triangles. That's why prior to the this convexization procedure all
+ * possible degenerated triangles are removed. Furthermore, when looking at
+ * a removal candidate and its connected points, all these points are split
+ * up into so-called connected paths. The crater to be removed or filled-up
+ * has a low point -- the point to be removed -- and a rim, defined by all
+ * points connected by concave lines to the low point. However, when a point
+ * has degenerated lines attached to it (i.e. two lines with the same
+ * endpoints), it may have multiple rims (imagine two craters on either
+ * side of the surface and the volume being so small/slim that they reach
+ * through to the same low point). We have to discern between these multiple
+ * rims, therefore the connected points are placed into different closed
+ * rings, so-called polygons. The point is the removed and the polygon re-
+ * tesselated which essentially fills the crater.
+ *
+ * With the second way, we have to pay attention that the filled-in tetrahedron
+ * does not intersect already present triangles. The baseline defines two
+ * points and as the tesselated surface is closed, it must be connected to two
+ * triangles. These together define a set of four points that make up the 
+ * tetrahedron. Naturally, two sides of the tetrahedron are always present
+ * already (and will become removed in place of the other two, effectively
+ * adding more volume to the tesselation).
+ * Now first, we only flip base lines that are concave. Second, none of the two
+ * other sides of the tetrahedron must be present. And lastly, we must check
+ * for all surrounding triangles that the new baseline (formed by point 3
+ * and 4) does not intersect these. Essentially, if we imagine a plane
+ * containing this new baseline, then each possibly intersecting triangle shows
+ * up as a brief line segment. We have to make sure that all of these segments
+ * remain below the new baseline in this plane. Also, things are complicated
+ * as the first and last line segment will always intersect with the baseline
+ * at the endpoint. There, we basically have to make sure that the line segment
+ * goes off in the right direction, namely outward.
+ *
+ * \section tesselation-volume Measuring the volume contained
+ *
+ * There is no straight-forward way to measure the volume contained in a
+ * non-convex tesselated surface. However, there is for a convex surface
+ * because convexity means that a line between any inner point and a point on
+ * the boundary will not intersect the surface anywhere else. Hence, we may
+ * use the center of gravity of all boundary points (by the same argument it
+ * must be an inner point) and calculate the volume of the general tetrahedron
+ * by looking at each of the tesselation's triangles in turn and summing up.
+ *
+ * We can calculate the volume of the original non-convex tesselation because
+ * the two ways mentioned above -- removing points and flipping baselines --
+ * both involve just addding general tetrahedron whose volume we may easily
+ * calculate. By bookkeeping of how much volume is added and calculating the
+ * total convex volume in the end, we also get the volume contained in the
+ * prior non-convex surface.
+ *
+ * \section tesselation-extension Issues whebn extended a tesselated surface
  *
  * The main problem for extending the mesh to match with the normal sense is
@@ -47 +107 @@
  * from a combination of spheres with van der Waals radii.
  *
- * \date 2014-03-10
+ * \date 2014-10-09
  *
  */