/* * 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 * */