Oriented Bounding Box (OBB)
The oriented bounding box (OBB) gives a closer approximation of the underlying mesh geometry compared to the AABB and the sphere. An OBB can be thought of as a rotated AABB, whose axes are aligned along mutually orthogonal principal directions of variance of the points with respect to the centroid. If the vertices of a mesh object are given by {xi, yi, zi}, i = 0 ••• n— 1, we can compute their centroid (x, y, z), and form the following matrix:
The scatter (or covariance) matrix C is a 3 x 3 symmetric matrix given by
where ax2 denotes the variance of the vector {x;}, axy the covariance between the vectors {x;}, {y;}, and so on.
Fig. 9.5 (a) The eigenvalues and the eigenvectors of the covariance matrix can be used to compute an ellipse with axes along directions of maximum and minimum variance. (b) The oriented bounding box uses the ellipse’s parameters
The above matrix therefore has real eigenvalues A1, 12, 13 and a mutually orthogonal set of eigenvectors v1, v2, v3. The normalization of each of these vectors yields an orthonormal basis e1, e2, e3. Treating the set of mesh vertices {x;, y;, z;}, i = 0… n— 1, as a point cloud, the unit vectors e1, e2, e3 define the principal axes directions of an ellipsoid with corresponding semi-axis lengths V^, and v/^3 (Fig. 9.5a). The OBB also has the same axis directions and half-width extents (Fig. 9.5b). The OBB can thus be completely specified by its centre (x, y, Z), its half-width extents w1 (=^/1^, w2 (=V^2), w3 (=^/^), and unit vectors e1, e2, e3 along its axes.
The matrix M with e1, e2, e3 as the column vectors gives the rotational transformation of the OBB with respect to the coordinate reference frame. The OBB does not always provide a tight fitting bounding box for the point cloud. This is because the covariance matrix depends on the distribution of the whole set of points, not just the points on the boundary that define the shape. Even changes in the locations of vertices that are inside the point cloud can affect the orientation of the OBB. One possible solution to this problem is to consider only the vertices on the convex hull of the mesh for the computation of the OBB. Another method that is used for the construction of the optimal OBB is to select the axis of the smallest eigenvalue, project all points on a plane perpendicular to this axis, and to compute the minimum area bounding rectangle of the projection. The chosen axis and the axes of the rectangle together define the orientation of the OBB. If we assume that 11 > 12 > 13, then e3 is the axis of projection. The points are then projected onto a plane orthogonal to e3, and the minimal rectangle of this set gives the other two axes e1′ and e2′ (Fig. 9.6a).
The minimal rectangle of a set of points on a plane can be obtained using the rotating calipers method. The method uses the convex hull of the points and two orthogonal pairs of support lines (Fig. 9.6b) such that one of the lines is always aligned with an edge of the convex hull.
Fig. 9.6 (a) Computation of the optimal OBB using a projection of the vertices orthogonal to the axis of minimum eigenvalue. (b) The rotating calipers method
The remaining three lines pass through the vertices of the convex hull. The angles 6i (i = 1 ••• 4) made by each support line with the edge of the convex hull in anticlockwise order are computed and the minimum angle is found. All four support lines are rotated about the corresponding vertices of the hull by the minimum angle, and this step aligns one of the lines with another edge of the convex hull. The area of the newly formed rectangle is computed and the minimum area updated. The process is repeated until all edges of the convex hull have been processed. The computation of the convex hull using algorithms such as the Graham’s Scan algorithm takes O(nlogn) time. The rotating calipers method visits all edges of the hull in O(n) time. The overall complexity of the optimal OBB computation algorithm is therefore O(nlogn).
Discrete Oriented Polytope (k-DOP)
A polytope is a general term for a polyhedron in any arbitrary dimension. It is defined as a geometrical object with flat surfaces. Points, line segments, polygons and polyhedrons are respectively zero-, one-, two- and three-dimensional polytopes. In a three-dimensional space, a discrete oriented polytope is a closed convex polyhedron bounded by k/2 pairs of parallel planes, where k is an even integer and k > 6. Each pair of planes has a fixed orientation. Such a polyhedron is often referred to as a k-DOP. An AABB and an OBB are both bounded by three pairs of parallel planes, and are therefore 6-DOPs. A 10-DOP and the associated normal directions are shown in Fig. 9.7a. A k-DOP need not always have k sides. The example in Fig. 9.7b is a 8-DOP with only six sides, with two sides degenerating into points.
The components of the surface normal vectors of a k-DOP are usually chosen from the set {—1,0, +1}. Each pair of parallel sides of a k-DOP has a fixed normal direction nj, j = 0, ••• (k/2)—1. Their positions are determined such that the region between them tightly encloses the mesh vertices (Fig. 9.8a).
Fig. 9.7 (a) A 10-DOP and the normal directions of five of its sides. The remaining five sides are parallel to these and have opposite normal directions. (b) An 8-DOP with degenerate edges
Fig. 9.8 (a) The positions of the planes are determined such that the vertices are tightly packed within each slab. (b) A slab formed by two parallel planes
Now consider two parallel planes T1, T2 having a normal direction nj and passing through points p1, p2 respectively. The region between the parallel planes is called a slab. If a vertex vi belongs to the slab formed by T1, T2, then vi satisfies the equations
In a k-DOP, the values of p1, p2 are determined by the minimum and the maximum positions of the projections of mesh vertices vi, i = 0 • ••n— 1, on the vector ni (Fig. 9.8b):
The k-DOP can be represented by the set {dminj, dmaxj, nj}, j = 0… (k/2)—1, that gives the k/2 intervals and direction vectors. The points p1, p2 were used only for the purpose of explaining the construction of the intervals, and are not stored. For fast overlap tests, it is desirable to have all k-DOPs in an application share surface normal directions from the same set. If the normal directions are pre-defined, then only the minimum and maximum values {dminj, dmaxj}, j = 0… (k/2)—1, need be stored. A point p belongs to a k-DOP if and only if the following conditions are simultaneously satisfied:
Convex Hulls
The key properties of a convex polygon were outlined in Sect. 8.7.1. A convex hull of a set of points in two dimensions is defined as the unique convex polygon containing all the points and whose vertices are only points in the set. It is the minimal convex polygon formed by the intersection of all convex polygons containing the points. The convex hull therefore is the tightest fitting bounding volume. The convex hull can also be defined as the union of all triangles that can be formed using only points of the set. In this section, we will first outline the construction of two-dimensional convex hulls using an incremental hull update algorithm, and then extend the method to three-dimensional hulls.
The 2D incremental hull algorithm builds the hull starting with a triangle formed by joining the first three points in the set (provided they are non-collinear), and then iteratively adds one point at a time to the existing hull and updates it if necessary. If the vertices of the initial triangle are oriented in the anticlockwise sense, then the vertices of the convex hulls constructed in subsequent steps will also be oriented in the anticlockwise sense. Assume that the given set of points is Sn = {P0, P1, …, Pn-1}, and the algorithmhas constructed the convex hull of the first i points S; = {P0, P1, …, P;-1} (3 < i < n). We denote this convex hull by C, = {Q0,… Qk-1} Ç s,. When the next point p, is added, the convex hull c, is traversed to check if the point is within the hull. This can be done by computing the signed area of the triangle QjQj+p-, j = 0… k— 1, (Qk = Q0) is positive (Eq. 2.9) for all j. If the point P, is inside or on the hull, it is not updated, i.e., C,+1 = C,. If the point is outside the hull, the signed area changes sign from positive to negative at some vertex on the hull, and from negative back to positive at some other vertex. These vertices are called the split vertex and the merge vertex respectively (Fig. 9.9). Existing edges between these vertices are removed, and the point P, are connected to these vertices to form the new convex hull C,C 1. The vertex set C, is updated to C,+1 by removing the vertices between the split and the merge vertices and adding P,.
At each step, the algorithm requires the traversal of the hull vertices to determine the locations of the split and merge vertices. The overall time complexity of the algorithm is therefore O(n2) for a naive implementation. O(nlogn) implementations exist, but they cannot be directly extended to the three-dimensional convex hull algorithm. One of the popular algorithms in this class is the Graham Scan, which is the same as the Three-Coins algorithm (Sect. 8.7.3) with a pre-processing phase where the points Pi are initially sorted in the ascending order of the angles between the vectorspi = Pi—P0 and the x-axis.
Fig. 9.9 Incremental construction of a two-dimensional convex hull
Fig. 9.10 Incremental construction of a three-dimensional convex hull
A natural extension of the incremental algorithm described above to a threedimensional data set Sn consisting of n mesh vertices can be easily formulated. The algorithm begins with the construction of a tetrahedron from four non-coplanar points of the set Sn . The point inclusion test in the three-dimensional case uses signed distances (Eq. 2.24) instead of signed areas to determine if a new point Pi is within the existing convex hull. If the surface normal vectors of the triangles of the convex hull are all specified in the outward direction, then for any point inside the hull, the signed distance with respect to every triangle of the hull is negative. Otherwise, the point is outside the hull, and we can determine the edges between triangles where the transition from negative to positive takes place. These edges are called silhouette edges. Every triangle for which the signed distance is positive is visible with respect to the point Pi. These triangles are removed, and the point P, is connected to the end points of every silhouette edge to form new triangles of the updated convex hull (Fig. 9.10).
At each step, the point inclusion step and the hull update step take O(n) time. The total time complexity of the 3D incremental hull discussed above is thus O(n2).
