Tracciare una linea iso di un campo scalare implicito 2D

Question

Ho un campo scalare implicito definito in 2D, per ogni punto in 2D posso farlo calcolare un valore scalare esatto ma è un calcolo alquanto complesso.
Vorrei disegnare una linea iso-line di quella superficie, diciamo la linea del valore '0'. La stessa funzione è continua ma la linea iso '0' può avere più istanze continue e non è garantito che tutte siano collegate.
Il calcolo del valore per ciascun pixel non è un'opzione perché richiederebbe troppo tempo, nell'ordine di pochi secondi e questo deve essere il più possibile in tempo reale.

Quello che sto attualmente usando è una divisione ricorsiva dello spazio che può essere pensata come una specie di quad-albero. Prendo un campionamento iniziale, molto approssimativo dello spazio e se trovo un quadrato che contiene una transizione da valori positivi a negativi, lo divido ricorsivamente in 4 quadrati più piccoli e li ricontrollo, fermandomi a livello di pixel. La transizione positivo-negativo viene rilevata campionando un sqaure nei suoi 4 angoli. Funziona abbastanza bene, tranne quando non lo è. Le iso-linee che vengono disegnate a volte vengono tagliate perché il rilevamento delle transizioni fallisce per le transizioni che si verificano in una piccola area di un bordo e che non attraversano un angolo di un quadrato.

Esiste un modo migliore per eseguire il disegno iso-line in queste impostazioni?

Answer 1

Ho avuto molto successo con gli algoritmi descritti qui http://web.archive.org/web/20140718130446/http://members.bellatlantic.net/~vze2vrva/thesis.html che trattano la modellazione adattiva (simile a quella che descrivi) e anche alcuni altri problemi con la stampa del contorno in generale.

Non esiste un modo generale per garantire di trovare tutti i contorni di una funzione, senza guardare ogni pixel. Potrebbe esserci un contorno chiuso molto piccolo, in cui una regione ha solo la dimensione di un pixel in cui la funzione è positiva, in una regione in cui la funzione è generalmente negativa. A meno che non si esegua il campionamento abbastanza finemente da posizionare un campione all'interno della regione positiva, non esiste un modo generale per sapere che è presente.

Se la tua funzione è abbastanza fluida, potresti essere in grado di indovinare dove si trovano contorni così piccoli chiusi, perché il modulo della funzione si riduce in una regione che li circonda. Il campionamento potrebbe quindi essere perfezionato solo in queste regioni.