domanda comune algoritmo

Question

Supponiamo di avere un po 'di maglia (vedi l'immagine che illustra da CorelDraw, che utilizza la stessa tecnica in "Mesh riempire" strumento).

alt text http://www.sonic.net/mnitepub/pccafe/reviews/coreldraw9/meshfill.jpg

Ovviamente questo tipo di rete è rappresentato da un insieme di punti e linee tra di loro sono in realtà determinato impiegando tale insieme di punti (probabilmente qualche modo interpolato). Questo strumento ha anche pulsanti per aumentare la risoluzione della mesh.

La mia domanda è la seguente: come vengono calcolati tali tipi di cose? Supponiamo di avere qualche serie di punti che rappresentano effettivamente una mesh (per un caso facile assumiamo anche che i punti sul "bordo" siano statici e non possano muoversi). E voglio aumentare la risoluzione della mesh, ad esempio, in 4 volte (in modo che il numero di punti di mesh diventi effettivamente 4 * initial_points_count).

Come devo calcolare le posizioni dei nuovi punti se l'unico dato che ho è quella matrice punti iniziale?

Il metodo più veloce (anche se approssimato) sarebbe adatto a me, ma non so dove cercare o come sviluppare questo tipo di algoritmo.

Grazie.

Answer 1

Vorrei iniziare con l'aggiunta di punti a metà strada su tutte le linee interpolando (le curve della illustrazione sono molto probabilmente Bézier curves di qualche tipo, quindi li interpolerei come tale, o usare l'interpolazione bilineare come suggerito da Mau) e ponendo nuovi punti a metà strada tra i vecchi, dandomi 3 volte la risoluzione. Quindi interpolerei tra questi nuovi punti (in entrambi i casi se la precisione è la chiave) e posiziono un nuovo punto all'incrocio (o a metà strada). Vedi "illustrazione" qui sotto.

Initial state => Interpolate => Place points => Interpolate => Final state 
    x  x   x-------x  x x x   x x x  x x x 
        |  |        |  
        |  |  x  x   x---+---x  x x x 
        |  |        | 
    x  x   x-------x  x x x   x x x  x x x 

Answer 2

Suona come un lavoro per Bilinear Interpolation (in cui il sistema di coordinate si trova sulla superficie della sfera).

Answer 3

Hai guardato subdivision? Dovrebbe lavorare per rifinire maglie del genere.

Answer 4

Quello che stai cercando è un algoritmo mesh smooth. Purtroppo non ho risorse a portata di mano, quindi posso solo suggerire a google di "mesh smoothing". Questo è un campo enorme.

EDIT

Ecco una bella, breve, carrellata di una coppia di metodi/algoritmi per raggiungere maglia lisciatura: http://www.mpi-inf.mpg.de/~ag4-gm/handouts/06gm_surf3.pdf

Answer 5

Commenti risposte esistenti:

mi sembra che la risposta di martient di Mau e descrivere una soluzione al problema di approssimare una forma nota con polygon mesh (e non hanno una forma nota) .

Algoritmo che Dave menziona potrebbe smussare qualsiasi forma, ma non necessariamente nel modo previsto.

Se osservate la risposta di You vedrete che i nuovi punti derivano dall'interpolazione lineare tra i punti, e se questo è abbastanza buono per voi tutte le soluzioni sono comparabili (eccetto quelle di Dave).

Tale aumento della densità di rete non corrisponde a e rende la mesh risultante più "carina", più simile alla forma originale. Se ciò non è abbastanza buono, devi prima decidere quale sia la forma/forma effettiva che stai cercando di rappresentare con la mesh (se potresti espandere il tuo esempio potrebbe essere un po 'più ovvio, è questo strumento che crea solo mesh circolari o può prendere qualsiasi forma e riempirla?).

Inoltre, si dovrebbe notare che non si lavora con una mesh poligonale, ma con una mesh di curve (probabilmente bezier), che è un'altra ragione per cui alcune delle risposte non si applicano direttamente al problema.

EDIT: Dopo aver guardato più da vicino il modo in cui Corel fa questo e supponendo che in realtà conosce le curve non solo i punti (!):

• Si comincia con la serie di curve, e sembra per me che hai curve orizzontali e verticali per iniziare con
• Se vuoi aumentare la risoluzione (ad esempio la risoluzione orizzontale), puoi prendere due curve verticali consecutive e dividere ogni segmento delle curve orizzontali che attraversano a metà punto creando così a insieme di punti che definiscono la nuova curva; si potrebbe anche interpolare l'angolo al quale la curva passa attraverso il punto

alt text http://img706.imageshack.us/img706/5693/path5818.png

L'immagine precedente (disegnati manualmente) mostra tenta di illustrare a) l'aggiunta della nuova curva (rosso) che si farebbe generare in questo modo. b) aggiungere la poligonale interpolati linearmente (blu), che va più verso approccio mesh poligonale (in modo da poter giudicare se questo è accettabile per voi)

Nota: A seconda dell'algoritmo per cui si prepara la maglia potresti o meno avere dei vantaggi nel considerare le linee di maglia come curve (la differenza tra soluzioni rosse e blu potrebbe essere trascurabile per alcuni algoritmi e importante per altri). Se l'algoritmo si aspetta semplicemente dei punti, dovresti anche considerare come approssimare le curve di Bezier con i punti (la lettura attraverso lo this potrebbe aiutarti, anche se non hai bisogno della precisione dei pixel).

Per la massima precisione/i migliori risultati, è necessario innanzitutto aumentare la densità delle curve e approssimarle con le linee.