Algoritmo per "de-rasterizzare" un'immagine voxel di un poliedro

Question

Algoritmo per "de-rasterizzare" un'immagine voxel di un poliedro

#1 da (1 voti)

1

Rasterizzare un poligono in questa domanda consiste nel creare una serie di pixel binari che "rappresentano" il poligono. Il contrario di questo processo è facile da approssimare in tempo lineare al perimetro in pixel. Usa una "soglia di dettaglio" D per definire quanto sarà complesso il poligono. Quando D diminuisce, il poligono diventa più dettagliato.

Ricorda che questo è solo per poligoni e immagini 2D, non in 3D,

Rimuovi l'interno dell'immagine se ce n'è una, quindi abbiamo un perimetro di 1 pixel di spessore
Assegna un pixel "primo" arbitrario come pixel attivo e il primo punto sul nostro poligono
Iterate in una direzione attorno all'immagine, utilizzando ciascun pixel come "pixel di prova"
Per ciascun pixel di prova, tieni traccia dell'angolo minimo e massimo tra il pixel attivo e i nostri pixel di test
Se la differenza tra questi due angoli diventa maggiore di D * 2, crea punti sul poligono per questi due punti minimo e massimo
Imposta il pixel attivo su qualsiasi valore di min / max al secondo (ovvero il più estremo in senso orario)
D'ora in poi, scorrere l'immagine e aggiungere un altro vertice quando | (angolo del segmento di linea precedente) - (angolo tra pixel attivo / test) | > D. Il pixel attivo diventa il vertice aggiunto più recentemente.

Questo non produce un poligono ottimale, ma funziona. È il meglio che potessi pensare, comunque. Se rasterizzi il risultato, produrrebbe qualcosa di simile all'immagine originale. Potrebbe essere potenzialmente migliorato impostando una distanza minima tra i vertici.

Tuttavia, in che modo un algoritmo come questo può essere esteso a 3D , dove l'"immagine" rasterizzata è 3D / ha un volume e stiamo producendo un poliedro? Sono in perdita su come capire questo.

Grazie in anticipo per l'aiuto.

algorithms geometry

posta TND 26.10.2014 - 02:51

fonte

1 risposta

Leggi altre domande sui tag algorithms geometry

Aggiungi argomenti a mysql in "dbshell" di Django Riferimenti alla documentazione ufficiale nella documentazione del codice sorgente

score 1 · Accepted Answer

Nota: presumo che ci sia un solo oggetto (tutti i voxel sono collegati). Se questo non è il caso, allora devi iniziare separando "tutti i voxel" in "un set di voxel per oggetto".

Inizia assumendo che ogni voxel sia un cubo con 6 facce. Per ciascuna faccia il voxel adiacente può essere vuoto (il volto deve essere nella mesh) o presente / solido (la faccia è omessa dalla mesh). Questa è la rimozione della superficie nascosta di base.

Avanti; unire le facce adiacenti Ad esempio, per un cubo di voxel 3 * 3 * 3, la parte superiore sarebbe costituita da 9 facce piccole e queste facce piccole possono essere unite per formare 1 faccia grande. Puoi (se lo desideri) generare trame per ogni "faccia grande" mentre fai questo o dopo averlo fatto (dove color textel = corrispondente colore voxel).

Avanti; trova "bolle interne". Scegli qualsiasi faccia e il segno è come appartenente a "mesh 1". Quindi trova le facce che condividono un lato con quella faccia e contrassegnali come appartenenti alla "mesh 1". Continua a farlo in modo ricorsivo per trovare tutte le facce che appartengono a "mesh 1". Se sono rimasti dei volti, scegline uno e contrassegnalo come appartenente a "mesh 2" e trova tutte le altre facce che appartengono a "mesh 2". Fallo finché non rimangono più facce (tutte le facce appartengono a una mesh). Trasmetti un raggio da qualsiasi punto lontano (ad esempio lungo l'asse Z da "Z = infinito") e vedi quale faccia colpisce per primo. Qualsiasi maglia a cui appartiene questa faccia è la "mesh esterna". Tutte le altre maglie sono "bolle interne".

Nota 1: se la videocamera non può trovarsi all'interno di alcuna bolla interna, è possibile eliminare le mesh delle bolle interne. Se la telecamera può trovarsi all'interno di una bolla interna, quindi per ciascuna mesh interna della bolla puoi trovare il suo punto centrale e il raggio (il vertice più lontano dal punto centrale), e quindi rendere solo la bolla interna se la distanza dalla telecamera al centro della bolla il punto è inferiore alla distanza dal centro della bolla al suo estremo più estremo.

Nota 2: l'ho descritto in questo modo per renderlo più facile da capire. In pratica vorrai lanciare il raggio per primo e usare la faccia che colpisce per prima come prima faccia di "mesh 1". Ciò significa che "mesh 1" è sempre la mesh esterna; e (se la telecamera non può essere all'interno di una bolla interna) ti consente di scartare tutti i volti che non fanno parte di "mesh 1" senza creare mesh di bolle interne.

Nota 3: avresti anche lanciato quel raggio nella direzione opposta a ciò che ho descritto; partendo da una faccia e trovando l'ultima faccia che attraversa il raggio. Questo evita la possibilità che "Ray manchi tutte le facce".

Infine, (se lo si desidera), liscia le mesh cercando i bordi tra le facce e generando nuove facce in modo che la normale della superficie della nuova faccia sia il prodotto puntuale delle normali della superficie delle vecchie facce. Puoi farlo più volte (ad esempio, angoli di 90 gradi diventano angoli smussati di 45 gradi, che diventano 22,5 gradi "angoli smussati tripli", e così via) fino a che non stai approssimando le curve con un raggio pari alla metà della larghezza di un voxel .