Centroid of convex polyhedron

问题:

I have a closed convex polyhedron which is defined by an array of convex polygons (faces) which are defined by arrays of vertices in 3D space. I'm trying to find the centroid of the polyhedron, assuming uniform density. At the moment I calculate it with the algorithm in this pseudo-code.

public Vector3 getCentroid() {
    Vector3 centroid = (0, 0, 0);
    for (face in faces) {
        Vector3 point = face.centroid;
        point.multiply(face.area());
        centroid.add(point);
    }
    centroid.divide(faces.size());
    return centroid;
}

This essentially takes the weighted average of the centroids of the faces. I'm not 100% sure this is correct as I haven't been able to find a correct algorithm online. If someone could either confirm my algorithm or refer me to a correct one I would appreciate it.

Thanks.

---

[EDIT]

So here is the actual Java code I am using to find the centroid. It breaks the polyhedron into pyramids converging on an arbitrary point inside the polyhedron. The weighted average for the pyramid centroids is based on the following formula.

C_all = SUM_{all pyramids}(C_pyramid * volume_pyramid) / volume_all

Here is the (heavily commented code):

    // Compute the average of the facial centroids.
    // This gives an arbitrary point inside the polyhedron.
    Vector3 avgPoint = new Vector3(0, 0, 0);
    for (int i = 0; i < faces.size(); i++) {
        avgPoint.add(faces.get(i).centroid);
    }
    avgPoint.divide(faces.size());

    // Initialise the centroid and the volume.
    centroid = new Vector3(0, 0, 0);
    volume = 0;

    // Loop through each face.
    for (int i = 0; i < faces.size(); i++) {
        Face face = faces.get(i);

        // Find a vector from avgPoint to the centroid of the face.
        Vector3 avgToCentroid = face.centroid.clone();
        avgToCentroid.sub(avgPoint);

        // Gives the unsigned minimum distance between the face and a parallel plane on avgPoint.
        float distance = avgToCentroid.scalarProjection(face.getNormal());

        // Finds the volume of the pyramid using V = 1/3 * B * h
        // where:   B = area of the pyramid base.
        //          h = pyramid height.
        float pyramidVolume = face.getArea() * distance / 3;

        // Centroid of a pyramid is 1/4 of the height up from the base.
        // Using 3/4 here because vector is travelling 'down' the pyramid.
        avgToCentroid.multiply(0.75f);
        avgToCentroid.add(avgPoint);
        // avgToCentroid is now the centroid of the pyramid.

        // Weight it by the volume of the pyramid.
        avgToCentroid.multiply(pyramidVolume);

        volume += pyramidVolume;
    }

    // Average the weighted sum of pyramid centroids.
    centroid.divide(volume);

Please feel free to ask me any questions you may have about it or point out any errors you see.

回答1:

Generally that depends on the structure of your polyhedron. There are 4 possible cases:

• Only vertices have weight, i.e. your polyhedron is the system of points. Then you can just calculate the mean value of the weighted sum of all the points:

  r_c = sum(r_i * m_i) / sum(m_i)
  

  Here r_i is the vector representing the i-th vertex, m_i - its mass. Case of equal masses leaves us with the simpler formula:

  r_c = sum(r_i) / n
  

  Where n is the number of vertices. Note that both sums are vectorized.

• Only edges have weight, and polyhedron is essentially a carcass. This case can be reduced to the previous one by substituting each edge with vertex situated right in the middle of the edge and have the weight of the whole edge.

• Only faces have weight. This case can be reduced to the first one as well. Each face is a 2D convex figure, of which the centroid can be found. Substituting each face with its centroid brings this case to the first one.

• Solid polyhedron (your case, inferring from the "assuming uniform density"). This problem requires a more complicated approach. First step is to split polyhedron into tetrahedrons. Here is the short description on how to do this. For a tetrahedron centroid is situated in the point where all its medians intersect. (Median of a tetrahedron is the line that connects its vertex and the centroid of the opposite face.) The next step is to substitute each tetrahedron in the partition with its centroid. And the last step is to find the centroid of the resulting set of weighted points, which is exactly the first case.

回答2:

For the solid case, there's a much simpler method than trying to tetrahedralize the polyhedron (which has pitfalls).

Here's pseudo-ish java-ish code (assuming decent Vector3 implementation):

// running sum for total volume
double vol = 0;
// running sum for centroid
Vector3 centroid = (0, 0, 0);
for each triangle (a,b,c)
{
  // Compute area-magnitude normal
  Vector3 n = (b-a).cross(c-a);
  vol += a.dot(n)/6.;
  // Compute contribution to centroid integral for each dimension
  for(int d = 0;d<3;d++)
    centroid[d] += n[d] * ((a[d]+b[d])^2 + (b[d]+c[d])^2 + (c[d]+a[d])^2);
}
// final scale by inverse volume
centroid *= 1./(24.*2.*vol);

Note, if you have higher degree faces than triangles you can trivially triangulate with a fan and this will still work.

This conveniently works even if the polyhedron is not convex.

I've also posted matlab code