isosuperficie inseguimento in alte dimensioni

Question

come rintracciare isosurface su uno spazio dimensionale superiore efficientemente

Answer 1

Hai una funzione di costo scalare N dimensioni,

f ( y , y , .., y _N) ε ℝ,   y ε ℝ

ma campionata solo in un normale griglia rettangolare,

y _k = Ψ _k + ψ _k x _k,   costanti Ψ _k ε ℝ e ψ _k ε ℝ, e coordinate reticolo x _k ε ℕ

e il problema è quello di individuare l'isosurface (s) i,

f ( y , y , .., y _N) = C _i

L'approccio diretta sarebbe poco ciclare su ogni cella griglia e controllare se l'isosuperficie corrente interseca la cella corrente e, in tal caso, descrivere la parte dell'isosurface all'interno della cella corrente. (Marcia cubi è un approccio a descrivere come l'isosurface interseca ciascuna cella della griglia.)

La restrizione è quello di utilizzare una ricerca basata zona invece di esaminare ogni singola cellula.

OP ha avuto un previous question specificamente per il caso 3D, a cui ho posted un link ad esempio di codice, grid.h e grid.c (a Pastebin.com, perché erano troppo lunghi per includere in linea).

Questa implementazione è completamente diversa dal metodo di affettamento dell'OP. Il mio è una passeggiata diretta e semplice sulle celle della griglia che interseca l'isosuperficie corrente.Memorizza nella cache i campioni della griglia e utilizza una mappa separata (uno char per cella della griglia) per tenere traccia di quali celle della griglia sono state memorizzate nella cache, camminate e/o spinte in una pila da percorrere in seguito. Questo approccio è facilmente estendibile a più di tre dimensioni. Sebbene il codice sia scritto esattamente per tre dimensioni, l'approccio stesso non è specifico per tre dimensioni; tutto quello che devi fare è regolare le strutture dei dati per adattarle a qualsiasi numero (ragionevole) di dimensioni.

La passeggiata isosuperficiale è di per sé banale. Si inizia da una qualsiasi cella della griglia che interseca l'isosuperficie, quindi si esaminano tutte le 2 celle più vicine vicine allo N per verificare se l'isosuperficie interseca anche quelle. In pratica, si utilizza una pila di posizioni delle celle della griglia da esaminare e una mappa delle bandiere delle celle della griglia per evitare di riesaminare le celle della griglia già esaminate.

Poiché il numero di campioni di punti di griglia per cella della griglia è 2 N, il mio codice di esempio non è ottimale: un sacco di punti della griglia vicine finiscono per essere valutata per vedere se le celle della griglia vicina si intersecano l'isosurface. (Invece di esaminare solo i punti della griglia che delimitano l'isosuperficie, vengono esaminati i punti della griglia che appartengono a qualsiasi cella della griglia che circonda l'isosuperficie.) Questo lavoro extra cresce in modo esponenziale al crescere di N.

Un approccio migliore sarebbe quella di considerare ciascuno dei 2 N possibile ( N -1) -faces separatamente, per evitare esaminare cellule isosurface non interseca affatto.

In un N dimensionale regolare griglia rettangolare, ciascuna cella è un parallelepipedo dimensionale N, definito dai punti della griglia 2 ^N ai vertici (angoli). I N cellule -cuboid hanno N ( N -1) facce bidimensionali e 2 N ( N -1) facce -dimensionale.

esaminare singolarmente ( N -1) -face, è necessario esaminare la funzione di costo ai 2 ^{N -1} punti della griglia definiscono che ( N -1) -face. Se la funzione di costo in quei punti si estende sul valore di isosuperficie, l'isosuperficie interseca la ( N -1) -face e l'isosurface interseca anche la cella della griglia successiva in quella direzione.

Sono disponibili due ( N -1) perpendicolarmente a ciascun asse. Se l'isosuperficie interseca la ( N -1) -fase più vicina all'infinito negativo, allora l'isosuperficie interseca anche la cella della griglia successiva lungo quell'asse verso l'infinito negativo. Allo stesso modo, se l'isosuperficie interseca la ( N -1) -fase più vicina all'infinito positivo, quindi interseca anche la cella della griglia successiva lungo quell'asse verso l'infinito positivo. Pertanto, i ( N -1) -facce sono perfetti per decidere quali celle vicine devono essere esaminate o meno. Questo è vero perché la ( N -1) -face è esattamente l'insieme di punti della griglia condivisa dalle due celle.

Sono molto riluttante a fornire codice C di esempio, perché il codice di esempio dello stesso approccio per il caso 3D non sembra aver aiutato nessuno finora.Temo che una spiegazione più lunga con immagini di esempio a 2 e 3 dimensioni per l'illustrazione sarebbe necessaria per descrivere l'approccio in termini facilmente comprensibili; e senza una solida comprensione della logica, qualsiasi codice di esempio apparirebbe come un gobbledygook.

Answer 2

Si sta utilizzando una libreria per 2 dimensioni è possibile provare l'algoritmo di Conrec dal Prof. Paul Bourke. È simile a un cubo in marcia.