Qual è l'approccio giusto per tagliare una maglia 3D? Le mesh sono tutte superfici chiuse e le sezioni devono essere immagini binarie di cosa c'è dentro la mesh. Ad esempio, una mesh che rappresenta una sfera e le immagini di una sezione sono quelle dei cerchi pieni.Algoritmo o software per affettare una rete
Sto cercando una libreria software o un algoritmo che possa essere integrato nel mio attuale progetto C++.
La mia libreria di giochi open source contiene un'implementazione di mesh slicing. Funziona con l'API di Irrlicht, ma potrebbe essere riscritto per utilizzare un'API diversa con uno sforzo modesto. Puoi usare il codice sotto i termini della licenza BSD, o imparare da esso un tuo proprio.
Vedere MeshTools :: splitMeshZ in this file for an implementation of mesh slicing.
Se si desidera solo conoscere l'algoritmo, ecco una descrizione di alto livello di quello che ho fatto:
ho inizialmente pensato di usare un rettangolo di selezione asse allineato per specificare dove tagliare la rete. Questo è stato problematico perché ha introdotto molti casi speciali. Ad esempio, un bordo che attraversa l'angolo della scatola può essere diviso in tre pezzi anziché solo due.
Utilizzare un piano per tagliare la mesh in una mesh sinistra e una mesh destra per ridurre il numero di casi speciali, perché un bordo si trova su un lato del piano o dell'altro oppure attraversa il piano e lo è anche tagliato in due pezzi esattamente.
Qualsiasi configurazione dei tagli desiderata può essere eseguita semplicemente tagliando una volta, prendendo una delle mesh risultanti e tagliandola nuovamente in un'altra posizione, e così via. Specificamente nel caso che descrivi nella sezione, un cerchio potrebbe essere tagliato da una sfera tagliando una metà della sfera, spostando l'aereo di una piccola quantità e tagliando l'altra metà lasciando solo una banda sottile. (Non puoi tagliare una mesh con letteralmente senza profondità con il codice che ho scritto, ma potresti tagliare una mesh fino a qualsiasi cosa tu abbia impostato la soglia dell'uguaglianza in virgola mobile. Penso di aver arbitrariamente scelto 0.001 nel mio codice.)
Utilizzando una logica simile, qualsiasi angolo desiderato del piano di taglio può essere ottenuto utilizzando un piano fisso; hai solo bisogno di trasformare la mesh per ruotarla rispetto al piano di taglio fisso, e quindi trasformare il risultato indietro. (Per il mio gioco avevo solo bisogno di tagli perpendicolari al piano XY, quindi per semplicità permetto solo di impostare il valore Z del taglio, e presumo che il taglio sia in quella posizione Z.)
OK, ora che abbiamo semplificato il problema, l'algoritmo non è poi così male:
condizione di partenza: Si dispone di un piano di taglio. Hai una serie di triangoli sorgente. Hai due serie di destinazioni di poligoni (non triangoli: i quad possono essere generati tagliando il triangolo). I due set di destinazione sono chiamati Left e Right.
Processo: Iterare su tre punti di un triangolo. Contare il numero di punti che sono inferiori al piano di taglio. Chiamerò quelli meno del piano di taglio sinistro e quelli più grandi del piano di taglio. Ci sono solo una manciata di casi:
Due punti sono a sinistra, un punto è a destra. Se si tiene un bordo di un triangolo e lo si taglia attraverso gli altri due bordi, si rimane in mano un trapezio. Metti un quad nel set di sinistra composto dai due punti in mano, più i due punti che attraversano il taglio. Metti un triangolo nel set giusto (immagine speculare del caso sopra).
Al termine, trasformare i quad in triangoli aggiungendo un collegamento nella parte più breve.
Questo è tutto. Questo è l'algoritmo di base. Il codice attuale gestisce altri casi, ad esempio se un bordo è esattamente uguale al taglio, e se un triangolo è esattamente sul bordo, non aggiungere poligoni degenerati (ad esempio un punto senza corpo), ecc.
Misc. problemi (tutti trattati nel codice legato):
Non complicare la matematica per LERP'ing il punto in cui il bordo attraversa il piano di taglio. Non ha bisogno di un'interpolazione lineare completa, è in realtà solo Highschool Algebra II: aumento over run, tempi di un rapporto
È vantaggioso memorizzare nella cache i punti (LERP) generati in modo che i triangoli che condividevano i vertici in la mesh non tagliata condividerà i corrispondenti nuovi vertici nella rete di taglio.
Se si intende preservare la condivisione dei vertici e si utilizzano i buffer dell'indice triangolare, sfortunatamente non si conosce ancora l'indice quando si generano le forme da inserire negli insiemi sinistro e destro. Io uso una classe chiamata "PossibleVertex" per rappresentare un futuro numero indice del triangolo.
Se si desidera visualizzare la trama, l'ordine di avvolgimento è importante. Un attento pensiero su come lo si codifica può garantire che i poligoni risultanti utilizzino lo stesso ordine di avvolgimento dei triangoli da cui provengono. Questo diventa particolarmente difficile quando si triangola i quadricipiti. Non riesco a ricordare i dettagli ma è tutto gestito nel codice collegato.
Per il mio gioco, ho voluto creare un nastro piatto che collega due reti tagliate. Ecco perché splitMeshZ genera 3 mesh, anziché solo due.Puoi usare la mesh centrale o semplicemente ignorarla.
Hai scritto un codice simile per ottenere solo l'intersezione del piano con la mesh e non le sezioni risultanti? – user1365836
Suppongo tu stia parlando di mesh triangolari?
Qual è l'approccio "giusto" che dipende fortemente dalle specifiche del caso d'uso.
L'approccio OpenGL suggerito da Jerry potrebbe funzionare per voi.
Un altro approccio sarebbe quello di calcolare esplicitamente i tagli. Puoi farlo con CGAL. Più specificamente con il suo kernel 3D. È dotato di un function in grado di calcolare le intersezioni tra tutti i tipi di primitive, tra cui un piano e un triangolo. Usando questa funzione puoi calcolare con precisione il tuo schema di intersezione e renderlo in un'immagine. - In questo modo non dipenderai da OpenGL ma da CGAL.
La funzione CGAL è interessante, quindi l'intersezione di un piano x-y e una mesh poliedrica restituirebbero ciò che specificamente? –
Dovresti intersecare il tuo piano con ciascun triangolo individualmente. Nei casi comuni, 'intersezione' restituire '0' se non ci sono intersezioni o segmenti di linea. Ci sono anche i casi in cui un triangolo giace interamente sul piano o lo tocca solo in un angolo, nel qual caso l'intersezione restituisce il triangolo o un singolo punto, rispettivamente. –
Ho delineato l'algoritmo per calcolare le intersezioni tra piano e volume in this answer. Viene fornita un'implementazione in Java.
Sarebbe più veloce (per se stessi, non è in esecuzione in tempo), se si sceglie di implementare da soli: Questi sono i semplici passi che devi fare:
1-Estraete tutti i triangoli della mesh
2-per ogni triangolo,
2-1- controllo se uno qualsiasi dei punti triangolo sono sulla fetta piano,
2-2- se no, per ciascuno dei suoi tre lati, per l'intersezione ion con il tuo slice-plane (se ce n'è uno). Devi avere 2 di loro intersecati con l'aereo o nessuno.
2-2-1 Se 2 bordi intersecano con il piano, si aggiunge una linea tra questi 2 punti sul piano.
Un progetto in affettare mesh 3D (con un codice sorgente in C++):
http://www.dainf.ct.utfpr.edu.br/~rminetto/projects/slicing/
Una possibilità potrebbe essere quella di rendere la rete con OpenGL, e utilizzare un piano di ritaglio per fare il "affettare". –