source: src/documentation/constructs/tesselation.dox@ 89c71f

/*
 * Project: MoleCuilder
 * Description: creates and alters molecular systems
 * Copyright (C)  2010 University of Bonn. All rights reserved.
 * Please see the LICENSE file or "Copyright notice" in builder.cpp for details.
 */

/**
 * \file tesselation.dox
 *
 * Created on: Oct 28, 2011
 *    Author: heber
 */

/** \page tesselation Tesselation
 *
 * Tesselation is a first step towards recognizing molecular surfaces.
 *
 * Within the code it is used for calculating correlation functions with regard
 * to such a surface.
 *
 * \section tesselation-procedure Tesselation procedure
 *
 * In the tesselation all atoms act as possible hindrance to a rolling sphere
 * that moves in from infinity. Whenever it rests uniquely on three distinct
 * points (atoms) a triangle is created. The algorithm continues by pushing the
 * sphere over one of the triangle's edges to eventually obtain a closed,
 * tesselated surface of the whole molecule.
 *
 * \note This mesh is different to the usual sense of a molecular surface as
 * atoms are directly located on it. Normally, one considers a so-called
 * Van-der-Waals sphere around the atoms and tesselates over these. 
 * \todo However, the mesh can easily be modified and even expanded to match the 
 * other (although the code for that is not yet fully implemented).
 *
 * \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
 * that triangles may suddenly intersect others when we have the case of a non-
 * convex mesh (which is rather the normal case). And this has to be
 * specifically treated. Also, it is not sure whether the procedure of
 * expanding our current surface is optimal and one should not start on a
 * different set of nodes created from virtual points resting on the
 * van-der-Waals spheres.
 *
 * Note that it is possible to select a number of atoms and create a bounding box
 * from a combination of spheres with van der Waals radii.
 *
 * \date 2014-10-09
 *
 */