/
introduktion.tex
49 lines (35 loc) · 4.73 KB
/
introduktion.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
% -*- coding: utf-8 -*-
\section{Introduction}
\label{introduction}
The area of protein folding (and from this the creation of newer and better drugs) with the aid of computers, has since the 60's been an area of much research and experimentation. It is clear that any improvement in the run time for protein folding would accelerate the creation of life saving drugs and treatments. One obvious area to improve is the time required for protein overlap detection.
Since proteins cannot physically overlap with parts of itself, it is necessary that each conformation is tested for overlap before it the model commits to it. It is therefore critical that the overlap tests can be done quickly.
One method for detecting collisions is Bounding Volumes Hierarchy (BVH), using a Bounding Volume (BV), where each node in the BVH is enveloped by a BV that covers all the children of the nodes\footnote{The leafs of the node is a small group of atoms}. If a BV does not intersect any other BV, then it is clear that the attempted conformation is legal, and it can take place. If there is a overlap between two, or more, BVs, then further overlap checks (lower in the BVH) are needed, in order to validate whether a part of the protein truly overlaps another.
\begin{figure}
\centering
\includegraphics[width=0.5\textwidth]{figures/rss}
\caption{\label{rss-example-figure}An example of a RSS}
\end{figure}
One possible BV is the Rectangular Swept Sphere (RSS), which is generated by sweeping the center point of a sphere over a rectangle in 3D space. The resulting volume looks something like a pillow. An illustration is given in figure \ref{rss-example-figure}. The RSS is interesting for many reasons. The first reason is that it is the logical progression from Point Swept Sphere and Linear Swept Sphere (both of which are described in the next section), but also because the RSS seems like a possible hybrid between Oriented Bounding Boxes (also explained in the next section), and Linear Swept Spheres, possibly proving an effective alternative to both. \Sfixme{make better}
\subsection{Scope and Limitations}
\label{scope}
I will in this project attempt to implement a RSS BV in the ProGAL framework. The RSS BV will contain the following 3 methods:
\begin{description}
\item[Overlap detection:] In order to make it a viable BV for use in a BVH for protein folding, I will implement the overlap detection, which I have introduced in the last section.
\item[Creation of RSS from a set of points:] In order to make the RSS viable for both testing and the BVH, I will implement a method that can construct a RSS from a set of points.
\item[Encapsulating RSS:] Lastly I will implement a method that will create a new RSS from any two given RSS'. This method is needed in for fast updates of the BVH, when a conformation is committed to.
\end{description}
Of these 3 methods it is primarily for the Overlap and Encapsulating method where speed is of the essence. For the create of RSS' from a set of points it is more important that the volume is as small as possible.
I will not try to implement the RSS in the BVH. I feel my time is better spent on making the core methods of the RSS working. It will however mean that I will not be able to test my implementation by actively folding of proteins. I will however test the methods on provided real world data.
\subsection{Expectations to the reader}
I expect the reader to have a good grasp of computational geometry, vector manipulations, and algorithms in general.
\subsection{Terminology}
In this report I will use the term ``good fit'' to mean that the Bounding Volume around a point-set contains all the points within it, and that it has as little wasted space - i.e. regions of the BV with no points in it as possible. BV A is a better fit than BV B, if both BV's a given set of points but A has a smaller volume than B.
\subsection{Guide to this report}
\begin{description}
\item[Section \ref{introduction}] The introduction to the report, which will introduce the subject and explain my goals
\item[Section \ref{rss}] A description of the Rectangular Swept Spheres - how they are defined in theory, and how I have chosen to represent them. This section will also contain a critique of the literature I used in this report.
\item[Section \ref{algorithms}] The algorithms that work on the RSSs, and an analysis of their run time.
\item[Section \ref{implementation}] Notes on the implementation of the algorithms from the previous section and the RSS itself in ProGAL.
\item[Section \ref{results}] I will discus about the results and a comparison with Oriented Bounding Boxes.
\item[Section \ref{conclusion}] The conclusion of the report, where I will report the status of the project, sum up my findings and point to point to possible future work and research.
\end{description}