Algoritmo di riempimento poligono

Question

Sto lavorando all'utilità di affettatura mesh per scopi di stampa 3D. In generale, dovrebbe tagliare un modello di mesh 3D in forme 2D (un numero di poligoni, probabilmente con fori) e riempirle con percorsi di spessore determinato utilizzando un modello specifico. Questi percorsi verranno utilizzati per generare comandi gcode per un firmware di stampante 3D.

Esistono vari strumenti open source con gli stessi scopi, scritti su python e perl. Ma il mio obiettivo è capire il flusso di lavoro di slicer e scrivere il mio strumento in C o C++.

Finora sono in grado di ottenere il contorno della fetta e ora li riempirò di percorsi. Il problema è che non ho trovato un algoritmo efficiente per farlo. Un processo schematico di esempio di riempimento:

Qualcuno può consigliare come generare questi percorsi di riempimento? Grazie.

---

Attualmente sto usando il seguente algoritmo:

1. Trova un riquadro della forma
2. Split bb verticalmente con le linee (numero di righe = bb.width/path.thickness)
3. punti di intersezione Ricerca per forma e ogni linea (dovrebbero essere due punti per linea)
4. costruire un segmenti da questi punti con offset dal contorno
.210
5. Aggiungere a segmenti che si collega un segmenti originali insieme formando una striscia linea
6. Siamo pronti a generare gcode o disegnare un percorso

Questo è semplice e algoritmo veloce, ma fa non funziona per poligoni concavi e poligoni con fori. Inoltre usa solo un modello specificato.

Answer 1

Dopo un po 'di tempo di ricerca, ho terminato con il seguente algoritmo: Tuttavia, ci sono diverse opportunità di ottimizzazione.

Answer 2

Si consiglia di esaminare this webpage sugli algoritmi per l'applicazione di tratteggio alle regioni.

Answer 3

L'approccio seguente produrrà un modello di riempimento costituito da un singolo percorso (ovvero, l'ugello di riempimento non verrà mai spento, spostato e riattivato) ogni volta che ciò è possibile.

Dopo il passaggio 4 ("Costruisci segmenti da questi punti con offset dal limite"), trasforma ciascun segmento di linea verticale in 2 o più punti: il punto superiore e inferiore, più (immagina che il diagramma sia disegnato su un diapositiva trasparente, posizionare un pezzo di carta con linee orizzontali al di sotto e contrassegnare dove i segmenti della linea verticale nel diagramma intersecano le linee orizzontali sulla carta).

Ora forma un grafico ponderato sul bordo contenente un vertice per ogni punto, con un bordo che collega due vertici ogni volta che i punti corrispondenti sono inferiori o uguali a un'unità di griglia. Aggiungete anche i bordi tra i punti più alti adiacenti dei segmenti di linea e tra i punti più in basso adiacenti. Usa la distanza euclidea tra i punti per il peso del bordo.Infine, la parte magica: trova un peso minimo Hamiltonian path su questo grafico. Questo è un percorso che visita ogni vertice esattamente una volta e ha una lunghezza minima. Il vincolo di lunghezza minima garantisce che il percorso non si incrocerà mai, poiché se due linee si incrociano, ad esempio la linea da a a b e la linea da c a d, allora sarebbe sempre possibile creare un percorso complessivo più breve eliminandole due linee e creando due nuove linee usando una diversa combinazione di endpoint (a --- c eb --- d oppure a --- d eb --- c). Questo è il percorso che riempirai.

Trovare un percorso hamiltoniano (per non parlare di un percorso hamiltoniano a peso minimo) è un problema NP-hard che è strettamente correlato al più famoso problema del venditore ambulante. Poiché esistono già molti solutori TSP precisi (ad es. Concorde), sarebbe opportuno utilizzare uno di questi per trovare un tour di un commesso viaggiatore e quindi semplicemente eliminare uno dei bordi per produrre un breve percorso hamiltoniano. (Anche se elimini il bordo più pesante, questo non produrrà necessariamente un percorso hamiltoniano di lunghezza minima, poiché potrebbe esserci che esistono percorsi più brevi che non iniziano e finiscono ai vertici adiacenti, ma non ci interessa davvero lunghezza totale qui, vogliamo solo un percorso che visita tutti i vertici e non attraversa se stesso.)

Sfortunatamente, non è garantito che un grafico contenga un percorso hamiltoniano o un tour di un commesso viaggiatore. (Ovviamente non possono esistere se il grafico è disconnesso, ad esempio, ma anche i grafici collegati possono non avere uno o entrambi: ad esempio un grafico con qualsiasi vertice di grado 1 non può avere un tour TSP.) In questo caso, se il Il solutore TSP che stai utilizzando può trovare tour che non visitano tutti i vertici, puoi semplicemente ripetere questo fino a coprire tutti i vertici. In caso contrario, ricorreremo al tuo algoritmo originale.