This weekend I was going through a section in Real-Time Collision Detection on computing the covariance matrix from a set of points (from hereon “point cloud”). Of course, while working through the implementation it’s always good to have an example or two to help solidify the concept, so I found myself working through a few samples for my unit tests and decided to post them here.

Example 1

Let’s start with a simple, somewhat uninteresting example where we have a single point on each of the cardinal axes.

+x:  1.0,  0.0,  0.0
+y:  0.0,  1.0,  0.0
+z:  0.0,  0.0,  1.0
-x: -1.0,  0.0,  0.0
-y:  0.0, -1.0,  0.0
-z:  0.0,  0.0, -1.0

Covariance Matrix:

0.333333,  0.0,  0.0
0.0,  0.333333,  0.0
0.0,  0.0,  0.333333

This is what we would expect because the spread is even along all the axes.

Example 2

Now, let’s look at a rotated version of the point cloud used in Example 1. Rotate the points 45 deg about the y-axis. I’m going to use 0.5 instead of sqrt(2)/2 to illustrate what happens when there is a dominant axis.

+x:  1.0,  0.0,  0.0   ->    0.5,  0.0,  0.5
+y:  0.0,  1.0,  0.0   ->    0.0,  1.0,  0.0  (stays the same)
+z:  0.0,  0.0,  1.0   ->   -0.5,  0.0,  0.5
-x: -1.0,  0.0,  0.0   ->   -0.5,  0.0, -0.5
-y:  0.0, -1.0,  0.0   ->    0.0, -1.0,  0.0  (stays the same)
-z:  0.0,  0.0, -1.0   ->    0.5,  0.0, -0.5

Covariance Matrix:

0.166667,  0.0,  0.0
0.0,  0.333333,  0.0
0.0,  0.0,  0.166667

This result should make sense because the x- and z-axis are no longer as spread as wide as the two points on the y-axis. As a result, the y component of the diagonal is larger than the x and z counterparts.

Also, it should be noted that even though the points in the xz-plane were not on the cardinal axes, the result is still a diagonal matrix. This is because the point cloud in this example is symmetric, such that each point cloud point in the xz-plane has a corresponding point (x,y) -> (-x,-y).

Example 3

In this example, we use the same point cloud as in Example 2, but translate the points all by 1.1, -0.4, 0.7.

 1.6, -0.4,  1.2
 1.1,  0.6,  0.7
 0.6, -0.4,  1.2
 0.6, -0.4,  0.2
 1.1, -1.4,  0.7
 1.6, -0.4,  0.2

Covariance Matrix:

0.166667,  0.0,  0.0
0.0,  0.333333,  0.0
0.0,  0.0,  0.166667

This example is a test to confirm a covariance matrix property: the covariance matrix remains the same if the point cloud is translated.

Example 4

Okay, so now let’s just take an arbitrary point cloud of eight points. The example here has no built-in symmetry, nor is it centered at the origin.

 1.2,  1.2,  1.2
-0.8, -0.8, -0.8
 0.7,  0.7,  0.5
 0.3,  0.4, -0.7
-0.2,  1.1,  0.5
 1.3, -0.8,  0.9
-0.1, -0.1, -0.3
 0.4, -0.5, -0.7

Centroid: 0.35, 0.15, 0.075

Covariance Matrix:

0.447500,  0.102500,  0.353750
0.102500,  0.582500,  0.283750
0.353750,  0.283750,  0.551875

Implementation Notes

The covariance matrix is symmetric. Therefore, only the upper triangular entries (including the diagonal) must be computed.

I included the centroid in the final example since it is subtracted off the points in the point cloud before computing the covariance matrix entries. We do this because we want our result to reflect the spread of the points in the local space of the point cloud.