| 1 | /*
|
|---|
| 2 | * Project: MoleCuilder
|
|---|
| 3 | * Description: creates and alters molecular systems
|
|---|
| 4 | * Copyright (C) 2010 University of Bonn. All rights reserved.
|
|---|
| 5 | * Please see the LICENSE file or "Copyright notice" in builder.cpp for details.
|
|---|
| 6 | */
|
|---|
| 7 |
|
|---|
| 8 | /**
|
|---|
| 9 | * \file tesselation.dox
|
|---|
| 10 | *
|
|---|
| 11 | * Created on: Oct 28, 2011
|
|---|
| 12 | * Author: heber
|
|---|
| 13 | */
|
|---|
| 14 |
|
|---|
| 15 | /** \page tesselation Tesselation
|
|---|
| 16 | *
|
|---|
| 17 | * Tesselation is a first step towards recognizing molecular surfaces.
|
|---|
| 18 | *
|
|---|
| 19 | * Within the code it is used for calculating correlation functions with regard
|
|---|
| 20 | * to such a surface.
|
|---|
| 21 | *
|
|---|
| 22 | * \section tesselation-procedure Tesselation procedure
|
|---|
| 23 | *
|
|---|
| 24 | * In the tesselation all atoms act as possible hindrance to a rolling sphere
|
|---|
| 25 | * that moves in from infinity. Whenever it rests uniquely on three distinct
|
|---|
| 26 | * points (atoms) a triangle is created. The algorithm continues by pushing the
|
|---|
| 27 | * sphere over one of the triangle's edges to eventually obtain a closed,
|
|---|
| 28 | * tesselated surface of the whole molecule.
|
|---|
| 29 | *
|
|---|
| 30 | * \note This mesh is different to the usual sense of a molecular surface as
|
|---|
| 31 | * atoms are directly located on it. Normally, one considers a so-called
|
|---|
| 32 | * Van-der-Waals sphere around the atoms and tesselates over these.
|
|---|
| 33 | * \todo However, the mesh can easily be modified and even expanded to match the
|
|---|
| 34 | * other (although the code for that is not yet fully implemented).
|
|---|
| 35 | *
|
|---|
| 36 | * \section tesselation-convexization Making a surface convex
|
|---|
| 37 | *
|
|---|
| 38 | * A closed surface created by the aforementioned procedure can be made convex
|
|---|
| 39 | * by a combination of the following two ways:
|
|---|
| 40 | * -# Removing a point from the surface that is connected to other points only
|
|---|
| 41 | * by concave lines. This might also be imagined as removing bumps or
|
|---|
| 42 | * craters in the surface.
|
|---|
| 43 | * -# flipping a base line or rather adding a general tetrahedron to remove a
|
|---|
| 44 | * concave line on the surface.
|
|---|
| 45 | *
|
|---|
| 46 | * With the first way one has to pay attention to possible degenerated lines
|
|---|
| 47 | * and triangles. That's why prior to the this convexization procedure all
|
|---|
| 48 | * possible degenerated triangles are removed. Furthermore, when looking at
|
|---|
| 49 | * a removal candidate and its connected points, all these points are split
|
|---|
| 50 | * up into so-called connected paths. The crater to be removed or filled-up
|
|---|
| 51 | * has a low point -- the point to be removed -- and a rim, defined by all
|
|---|
| 52 | * points connected by concave lines to the low point. However, when a point
|
|---|
| 53 | * has degenerated lines attached to it (i.e. two lines with the same
|
|---|
| 54 | * endpoints), it may have multiple rims (imagine two craters on either
|
|---|
| 55 | * side of the surface and the volume being so small/slim that they reach
|
|---|
| 56 | * through to the same low point). We have to discern between these multiple
|
|---|
| 57 | * rims, therefore the connected points are placed into different closed
|
|---|
| 58 | * rings, so-called polygons. The point is the removed and the polygon re-
|
|---|
| 59 | * tesselated which essentially fills the crater.
|
|---|
| 60 | *
|
|---|
| 61 | * With the second way, we have to pay attention that the filled-in tetrahedron
|
|---|
| 62 | * does not intersect already present triangles. The baseline defines two
|
|---|
| 63 | * points and as the tesselated surface is closed, it must be connected to two
|
|---|
| 64 | * triangles. These together define a set of four points that make up the
|
|---|
| 65 | * tetrahedron. Naturally, two sides of the tetrahedron are always present
|
|---|
| 66 | * already (and will become removed in place of the other two, effectively
|
|---|
| 67 | * adding more volume to the tesselation).
|
|---|
| 68 | * Now first, we only flip base lines that are concave. Second, none of the two
|
|---|
| 69 | * other sides of the tetrahedron must be present. And lastly, we must check
|
|---|
| 70 | * for all surrounding triangles that the new baseline (formed by point 3
|
|---|
| 71 | * and 4) does not intersect these. Essentially, if we imagine a plane
|
|---|
| 72 | * containing this new baseline, then each possibly intersecting triangle shows
|
|---|
| 73 | * up as a brief line segment. We have to make sure that all of these segments
|
|---|
| 74 | * remain below the new baseline in this plane. Also, things are complicated
|
|---|
| 75 | * as the first and last line segment will always intersect with the baseline
|
|---|
| 76 | * at the endpoint. There, we basically have to make sure that the line segment
|
|---|
| 77 | * goes off in the right direction, namely outward.
|
|---|
| 78 | *
|
|---|
| 79 | * \section tesselation-volume Measuring the volume contained
|
|---|
| 80 | *
|
|---|
| 81 | * There is no straight-forward way to measure the volume contained in a
|
|---|
| 82 | * non-convex tesselated surface. However, there is for a convex surface
|
|---|
| 83 | * because convexity means that a line between any inner point and a point on
|
|---|
| 84 | * the boundary will not intersect the surface anywhere else. Hence, we may
|
|---|
| 85 | * use the center of gravity of all boundary points (by the same argument it
|
|---|
| 86 | * must be an inner point) and calculate the volume of the general tetrahedron
|
|---|
| 87 | * by looking at each of the tesselation's triangles in turn and summing up.
|
|---|
| 88 | *
|
|---|
| 89 | * We can calculate the volume of the original non-convex tesselation because
|
|---|
| 90 | * the two ways mentioned above -- removing points and flipping baselines --
|
|---|
| 91 | * both involve just addding general tetrahedron whose volume we may easily
|
|---|
| 92 | * calculate. By bookkeeping of how much volume is added and calculating the
|
|---|
| 93 | * total convex volume in the end, we also get the volume contained in the
|
|---|
| 94 | * prior non-convex surface.
|
|---|
| 95 | *
|
|---|
| 96 | * \section tesselation-extension Issues whebn extended a tesselated surface
|
|---|
| 97 | *
|
|---|
| 98 | * The main problem for extending the mesh to match with the normal sense is
|
|---|
| 99 | * that triangles may suddenly intersect others when we have the case of a non-
|
|---|
| 100 | * convex mesh (which is rather the normal case). And this has to be
|
|---|
| 101 | * specifically treated. Also, it is not sure whether the procedure of
|
|---|
| 102 | * expanding our current surface is optimal and one should not start on a
|
|---|
| 103 | * different set of nodes created from virtual points resting on the
|
|---|
| 104 | * van-der-Waals spheres.
|
|---|
| 105 | *
|
|---|
| 106 | * Note that it is possible to select a number of atoms and create a bounding box
|
|---|
| 107 | * from a combination of spheres with van der Waals radii.
|
|---|
| 108 | *
|
|---|
| 109 | * \date 2014-10-09
|
|---|
| 110 | *
|
|---|
| 111 | */
|
|---|
