Un metodo per calcolare il centro di massa da un file .stl (stereo litografia)?

Question

Sto provando a calcolare le coordinate del centro di massa (x, y, z) di un oggetto definito in un file STL (litografia stereo, da non confondere con la libreria modello standard). Il file STL contiene un oggetto (o oggetti) chiuso definito da un limite costituito da triangoli. I triangoli stessi non sono necessariamente in ordine, il file è semplicemente le coordinate 3 vertici di ogni triangolo fluttuante nello spazio 3D più un vettore normale al triangolo (il normale dovrebbe essere ignorato in quanto non sempre viene eseguito correttamente). Non c'è nulla che collega ogni triangolo tra loro, si presume che l'oggetto sia chiuso.

Un approccio semplice sarebbe quello di dividere un volume (in questo caso una scatola) in milioni di elementi e determinare se ciascun elemento si trova all'interno dell'oggetto definito nel file STL o meno, quindi riassumere i momenti e calcolare il centro di massa. Questo funzionerebbe ma è tutt'altro che elegante ed estremamente lento.

Un altro metodo sarebbe convertire la rappresentazione del limite in un numero di solidi tetraedri imballati. Forma che potrei calcolare il centro di massa di ciascun tetraedro, il suo volume e il momento risultante e quindi calcolare il centro di massa complessivo dalla somma di tutti i tetraedri. Il problema con questo è che non so come convertire una rappresentazione di superficie di triangoli in una rappresentazione di volume di tetraedri (sto assumendo che sia un compito abbastanza banale).

Dose qualcuno conosce qualche metodo o può pensare a metodi che potrei provare? O forse anche qualche materiale di riferimento che parla di questo?

Per ulteriori informazioni sui file STL (solo le prime 2 sezioni sono importanti, tutto il resto è inutile): http://en.wikipedia.org/wiki/STL_%28file_format%29

Answer 1

Dopo un sacco di riflessione e sperimentazione ho la risposta!

Per prima cosa aggiungiamo un quarto punto a ciascun triangolo per trasformarli in tetraedri con un centroide del volume. Calcoliamo i volumi e i centri di massa e li moltiplichiamo l'uno per l'altro per ottenere i nostri momenti. Sommiamo i momenti e dividiamo per il volume totale per ottenere il nostro centroide globale.

Calcoliamo volumi utilizzando il metodo determinato qui illustrato (equazione 32): http://mathworld.wolfram.com/Tetrahedron.html

I centroidi di ciascuno dei tetraedri è semplicemente la media dei 4 punti.

Il trucco qui è che a causa del modo in cui il file STL viene creato, i triangoli hanno un normale quel punto verso l'esterno dalla superficie della parte, seguendo la regola della mano destra dei 3 vertici usati per creare il triangolo. possiamo usare questo a nostro vantaggio, permettendoci di avere una convenzione coerente in cui determinare se un volume del tetraedro dovrebbe essere aggiunto o sottratto dalla nostra parte di rete (questo perché il punto di riferimento che abbiamo scelto potrebbe non essere necessariamente all'interno della parte e la parte generale non è necessariamente convessa, ma è un oggetto chiuso).

Utilizzando il metodo di determinazione per calcolare il volume, i primi tre punti di coordinate rappresentano i tre punti del nostro triangolo. Il quarto punto sarebbe la nostra origine comune. Se il normale creato dal triangolo (seguendo la regola della mano destra che va dal punto 1, 2, 3) punta verso il nostro punto di riferimento comune, quel volume sarà calcolato come non parte del nostro volume complessivo solido o negativo (puntando verso, Intendo dire che il vettore creato dalla normale del triangolo punta liberamente verso lo stesso lato di un piano normale creato dal vettore dal nostro punto di riferimento al centroide del tetraedro). Se il vettore punta verso il lontano dal punto di riferimento, allora è il volume positivo o all'interno della parte. Se è normale, il volume si azzera quando il triangolo si trova sullo stesso piano del punto di riferimento.

Non dobbiamo preoccuparci di tenere traccia di tutto ciò come se fossimo coerenti con i nostri input (come nei triangoli seguono la regola della mano destra con il normale rivolto verso l'esterno dalla parte) il determinante ci darà il segno corretto.

Ad ogni modo, ecco il codice (è ancora più semplice della spiegazione).

class data // 3 vertices of each triangle 
{ 
public: 
    float x1,y1,z1; 
    float x2,y2,z2; 
    float x3,y3,z3; 
}; 

int main() 
{ 
    int numTriangles; // pull in the STL file and determine number of triangles 
    data * triangles = new triangles [numTriangles]; 
    // fill the triangles array with the data in the STL file 

    double totalVolume = 0, currentVolume; 
    double xCenter = 0, yCenter = 0, zCenter = 0; 

    for (int i = 0; i < numTriangles; i++) 
    { 
     totalVolume += currentVolume = (triangles[i].x1*triangles[i].y2*triangles[i].z3 - triangles[i].x1*triangles[i].y3*triangles[i].z2 - triangles[i].x2*triangles[i].y1*triangles[i].z3 + triangles[i].x2*triangles[i].y3*triangles[i].z1 + triangles[i].x3*triangles[i].y1*triangles[i].z2 - triangles[i].x3*triangles[i].y2*triangles[i].z1)/6; 
     xCenter += ((triangles[i].x1 + triangles[i].x2 + triangles[i].x3)/4) * currentVolume; 
     yCenter += ((triangles[i].y1 + triangles[i].y2 + triangles[i].y3)/4) * currentVolume; 
     zCenter += ((triangles[i].z1 + triangles[i].z2 + triangles[i].z3)/4) * currentVolume; 
    } 

    cout << endl << "Total Volume = " << totalVolume << endl; 
    cout << endl << "X center = " << xCenter/totalVolume << endl; 
    cout << endl << "Y center = " << yCenter/totalVolume << endl; 
    cout << endl << "Z center = " << zCenter/totalVolume << endl; 
} 

Estremamente veloce per il calcolo dei centri di massa per i file STL.

Answer 2

EDIT: Look up "avvolgimento algoritmo numero" o "attraversare algoritmo numero" - quello che ho provare a descrivere di seguito è un algoritmo di numero di attraversamento 3-d.

Ho la sensazione che qualcosa di simile a questo lavoro, ma non hanno la possibilità di verificare il lavoro svolto, in questo momento:

costruire l'compilato struttura 3-D da triangoli in il file STL in modo iterativo. Inizia selezionando un singolo punto da utilizzare come base per la struttura 3-d. Quindi, inizia la tua struttura creando una piramide triangolare, con base definita dal primo triangolo nel file STL e vertice del punto scelto. Ogni componente del volume costruito in modo iterativo contiene anche una "parità di intersezione" - inizializza a 0.

Per ogni triangolo successivo nel file STL, creare una piramide simile e vedere se si interseca con la 3-d struttura che hai costruito finora. In tal caso, calcolare l'intersezione e segmentare la struttura esistente e la nuova piramide in modo che non si sovrappongano due componenti. Mantieni la "parità di intersezione" della parte più esterna del nuovo poliedro 0, ma attivala su tutte le parti interne dell'intersezione: se fosse 0, rendi 1, se fosse 1, rendi 0.

Alla fine, avrai il poliedro chiuso definito da tutte le parti della tua struttura che hanno la parità di intersezione 0. Calcola i momenti di tutti questi poliedri e calcoli insieme per ottenere il tuo centro di massa. Penso che la complessità sarebbe qualcosa come O (n^2).