Środek wypukłego wielościanu

Question

Mam zamknięty wielościan wypukły, który jest zdefiniowany przez tablicę wypukłych wielokątów (płaszczyzn), które są zdefiniowane przez tablice wierzchołków w przestrzeni 3D. Próbuję znaleźć środek ciężkości wielościanu, zakładając jednolitą gęstość. W tej chwili kalkuluję to algorytmem w tym pseudokodzie.

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; 
} 

To zasadniczo przyjmuje średnią ważoną centroidów twarzy. Nie jestem w 100% pewien, czy to prawda, ponieważ nie udało mi się znaleźć prawidłowego algorytmu w Internecie. Jeśli ktoś mógłby potwierdzić mój algorytm lub skierować mnie na prawidłowy, byłbym wdzięczny.

Dzięki.

---

[EDIT]

Więc tutaj jest rzeczywisty kod Java używam znaleźć ciężkości. Łamie wielościan w piramidy zbiegające się w dowolnym punkcie wewnątrz wielościanu. Średnia ważona dla centroidów piramidy opiera się na następującej formule.

C _wszystkie = suma _{wszystkie piramidy} (C _piramidy * objętość _piramidy)/objętość _wszystkie

Oto (silnie komentuje kodu):

// 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); 

Proszę, zadaj mi jakiekolwiek pytania, które możesz mieć ab lub wskaż błędy, które widzisz.

Answer 1

Generalnie zależy to od struktury wielościanu. Istnieją 4 możliwe przypadki:

• Tylko wierzchołki mają masę, tj. Twój wielościan jest układem punktów. Następnie można po prostu obliczyć wartość średnią ważoną sumę wszystkich punktów:

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

  Tutaj r_i jest wektorem reprezentującym i-tego wierzchołka, m_i - jego masa. Przypadek równych masach pozostawia nas z prostszym wzorem:

  r_c = sum(r_i)/n 
  

  Gdzie n jest liczbą wierzchołków. Zwróć uwagę, że obie sumy są wektoryzowane.

• Tylko krawędzie mają masę, a wielościan jest w zasadzie tuszy. Ten przypadek można zredukować do poprzedniego, zastępując każdą krawędź wierzchołkiem znajdującym się pośrodku krawędzi i obciążając całą krawędź.

• Tylko twarze mają wagę. Ten przypadek można również zredukować do pierwszego. Każda twarz jest figurą wypukłą 2D, której można znaleźć środek ciężkości. Zastępowanie każdej twarzy jej centroidem przenosi tę sprawę do pierwszej.

• Stały wielościan (twoja sprawa, wywnioskowanie z "zakładając jednolitą gęstość"). Ten problem wymaga bardziej skomplikowanego podejścia.Pierwszym krokiem jest podzielenie wielościanu na czworościany. Oto short description, jak to zrobić. Dla czworościanu centroid znajduje się w punkcie przecięcia się wszystkich jego median. (Mediana czworościanu jest linią, która łączy jej wierzchołek i środek ciężkości przeciwnej ściany). Następnym krokiem jest zastąpienie każdego czworościanu w przegrodzie jego centroidem. Ostatnim krokiem jest znalezienie środka ciężkości wynikowego zestawu ważonych punktów, co jest dokładnie pierwszym przypadkiem.

Answer 2

Dla stałych przypadku, istnieje wiele simpler method niż próby tetrahedralize wielościanu (który ma pitfalls).

Oto pseudo-owski java-owski kod (zakładając godnej wdrażania Vector3):

// 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); 

Uwaga, jeśli mają wyższe twarze stopniu niż trójkątów można trywialnie triangulacji z wentylatorem i będzie nadal działać.

To wygodnie działa, nawet jeśli wielościan nie jest wypukły.

Ja również pisał matlab code