Why not use a convex hull as the projection function?

[zalo]

The fit function might require a library, but it will be tighter and the projection function is the same (just a series of plane constraints).

Also, just wanted to say that this is a super neat trick, and I appreciate your writing style of including snippets in the posts; I try do something similar in my interactive posts.

( @orangeduck in-case the notifications aren't set up)

[orangeduck]

Yeah it is a great idea, definitely if there is a relatively simple fitting function for the convex hull that could fit in the blog post. It's a long time since I did anything related to that!

[zalo]

Hrm, there probably aren't any robust 3D convex hull implementations under a few hundred lines. I tried once to write a "short" implementation, but it ended up only working on some point clouds. One's best bet is to use a battle-tested header-only library like Stan Melax's QuickHull.

I did a quick check for possible direct methods (for projecting points to the hull of a point cloud), but the quadratic programming and winding number approaches may be even further outside the scope of the article (not to mention dramatically more expensive).

[orangeduck]

I wonder if there is a middle ground kind of heuristic method where you can somehow extract the largest N triangles (by area) from the convex hull and use their normals as the axes in the kdop fitting.

[zalo]

I wish... QuickHull is a good approximate method that will converge on the true convex hull after enough time (and then traditional mesh simplification approaches can be used to simplify it), but the approximate implementation is as long as the full one 🙃

There is another trick that might help here...

K-Means is an elegant algorithm for dividing up a point cloud into a number of roughly equal-sized chunks:

List<Vector3>[] getKMeansClusters(Vector3[] pointsArray, int numClusters, int numIterations = 10) {
       Vector3 [] clusterCentroids = new Vector3[numClusters];
  List<Vector3>[] pointsInCluster  = new List<Vector3>[numClusters];
  
  // Randomly initialize clusters
  for(int i = 0; i < numClusters; i++) { 
      clusterCentroids[i] = new Vector3(Random(), Random(), Random());  }
  
  // Compute Clusters
  for(int iter = 0; iter < numIterations; iter++){
    // Clear Cluster Lists
    for(int i = 0; i < numClusters; i++) { pointsInCluster [i].Clear();  }

    // Assign points to closest cluster centroid
    for(int j = 0; j < pointsArray.Length; j++) {
        float closestDistance = float.MaxFloat; int closestIndex = -1;
        for(int i = 0; i < numClusters; i++) {
          if(Vector3.Distance(pointsArray[j], clusterCentroids[i]) < closestDistance){
            closestDistance = Vector3.Distance(pointsArray[j], clusterCentroids[i]);
            closestIndex = i;
          }
        }
        pointsInCluster[closestIndex].add(pointsArray[j]);
    }
    
    // Set cluster centroid to be the mean of the points in the cluster
    for(int i = 0; i < numClusters; i++) {
        Vector3 sumPosition = Vector3.zero;
        for(int j = 0; j < pointsArray.Length; j++) { sumPosition += pointsArray[j]; }
        clusterCentroids[i] = sumPosition / pointsArray.Length;
    }
  }

  return pointsInCluster;
}

It looks like this:

Fitting OBBs or K-Dops to K-Means clusters would be a simple/low-additional-code way of improving the quality of the fit.