Collision detection is a field of much research, but also with a huge number of practical applications. Typical examples of applications are flight simulators, surgery simulation, virtual reality and probably the most significant, computer games. In these applications, real-time performance of the collision detection algorithms is needed. Space partition methods are often used to achieve this kind of performance. Hence, a large number of different ways to present 3D data in performance enhancing hierarchies exist. Examples are octrees [188], kD-trees [20], and binary space partitioning kD-trees (BSP-kD-trees) [102]. These spatial partitioning algorithms are often used to represent fixed environments, in which other objects navigate. In our case, parts of a hearing aid move inside an ear canal. It would therefore be obvious to use some kind of space partitioning of the ear canal.
When the collision occurs between two or more objects a number of ways to represent the object exists. One way is to represent an object using a hierarchy of axis-aligned bounding boxes (AABB-trees) [21] or the slightly more advanced oriented bounding boxes (OBB-Trees) [112]. However, biological objects are sometimes not well approximated by rectangular boxes. Hubbard proposes an alternative method that represents an object as a hierarchy of spheres [137, 138].
The set of spheres approximating an object is calculated using a stable Voronoi diagram method [139]. Another alternative is the discrete orientation polytopes (DOPs) approach [124, 165, 166, 167]. Ak-DOP approximates the convex hull of an object, where k indicates the number of planes that are used. Hence, a 6-DOP is equal to rectangular box, while higher orderk-DOPs provide a tighter approximation of the convex hull.
Collision detection algorithms are often specially crafted to each application
6.2 Collision Detection 53
(a) Point Cloud (b) Polar Balls
(c) Medial Sheet (d) Medial Sheet and Surface
Figure 6.1: The approximation of the medial axis transformation of an ear canal.
It is seen that the collection of polar balls approximates the volume spanned by the point cloud. The medial sheet is colour coded according to the radii of the medial balls. The large ball is placed at the opening of the ear canal. Scale is in millimetres.
Figure 6.2: The centres of the outer balls colour coded according to their radii.
It is seen that the balls are enclosed in a bounding volume much larger than the actual ear canal.
since the nature of the scene determines the optimal approach. Our case is somewhat special since we need to check if a component is completely inside the ear canal. In addition, it is necessary to calculate the amount of penetration so a measure of severity of the collision can be given.
To determine the volume of the intersection a technique known asconstructive solid geometry (CSG) can be used [91, 136, 171]. One problem using CSG is that it is required that the objects are closed and that is not the case with the ear canal. Tricks can be made to make it a closed object, but that is not optimal. Finally, a combination of methods, were chosen. These are described in the next section.
6.2.1 Collision Detection in the Ear Canal
The chosen approach is customised to the problem at hand. It is based on the spherical decomposition technique [137, 138] and OBB-trees [112].
A component is represented as an OBB-tree as seen in Figure 6.3. To build the OBB, a recursive, top-down process is used. Initially, the root bounding-box is found by calculating the eigenvectors of the covariance matrix of the points from the object. These three orthogonal vectors define the tightest fitting bounding box. The two children of this bounding box are found by a plane that approximately divides the object in half. These two point clouds are then used to compute the two child OBBs. This process continues until the desired tree-depth is reached or no splitting is possible.
As described in Section 6.1, the Power Crust computes a medial sheet consisting
6.2 Collision Detection 55
Figure 6.3: OBB-Tree representation of a collection of components. From right to left the OBB-tree level 0, 1, 2, and 4.
of a collection of connected vertices. Each vertex in this sheet also represents a medial ball (also called a polar ball) that touches the sides of the reconstructed surface. The collection of medial balls is thus a very good approximation to the object enclosed by the surface as seen in Figure 6.1. In addition, a medial sheet representing the spaceoutside the object is produced. This sheet is bounded by a box much larger than the object as seen in Figure 6.2. Since it is very easy to determine if a point lies inside or outside a sphere, the collection of medial balls can be used to determine if given points lie inside or outside the object approximated by the balls. This method resembles the method by Hubbard [137, 138]. To check if a point from the component is placed inside or outside the shell, there are two possibilities. The first is to examine if the point is contained in any inner medial ball, if not it must be outside. The second is to examine if an outer medial ball contains the point, which would also mean that it is outside.
As motivated later, we use the outer medial balls to determine if there is a collision. Moreover, a temporal caching technique is used to speed up collision detection involving objects that only moves a little from frame to frame. A list of medial balls containing colliding points is kept and used to check if the point is still colliding with these balls in the next frame. Furthermore, collisions between balls and points are checked in the order of the size of the balls, with the largest balls being checked first. The level of OBB-tree used to represent the components is chosen dynamically. In the final iterations all the points from the polygonal representation of the component is used. A collision between a CIC and an ear canal detected by this method is seen in Figure 6.4.
The penetration depth is formally defined as the minimum translation distance needed to separate two objects. However, the calculation of the true penetration depth is very difficult [162] and outside the scope of this thesis. Instead, an ad hoc method for the estimation of the penetration depth is adopted. The penetration depth is defined for a point as being the distance to the nearest point on the surface. This distance can be calculated using the technique described in Section 6.4, but this method is very slow. Hence, an alternative method that provides a quick approximation to the distance is used. The penetration depth
Figure 6.4: Collision between a CIC and an ear canal detected using the medial balls. The red areas of the CIC are where the CIC is colliding with the ear canal.
of a given point is computed using the outer, medial balls. When an outer medial ball contains a point,P, acollision vector can be calculated as
vcol=r(P−C)
kP−Ck, (6.1)
where r is the radius and C is the centre of the ball. This is illustrated in Figure 6.5. All collision vectors can be calculated by finding all the balls that contain the point. Averaging these vectors yields an estimate of the direction of the true penetration vector. The penetration depth is calculated as d = maxkvcol,i·vcolkand an approximated penetration vector as v=dvcol, where vcol is the normalised, average collision vector. The collision and penetration vectors from a set of vertices can be seen in Figure 6.6. Finally, the severity of a collision between a component and the ear canal is calculated as the sum of penetration depths of all vertices in the component,Fcollision=P
idi.
The method contains several weaknesses. First, it ignores the origin of the points. When a point is part of a larger object, the positions of the remain-ing parts of the object should be taken into account. Secondly, there is no proof that the method actually estimates the minimum distance to the surface.
Nevertheless, the method has proven to work well with our data.