Allora, vi sottopongo un quesito sul quale mi sto baloccando da qualche giorno, ma non riesco a venirne a capo nel modo corretto.
Ho implementato tempo fa su un motore di rendering (una cosa triviale dell'università, molto didattico e poco "reale") le isosuperfici (o Blob).
Chiariamo una cosa: normalmente i motori di rendering creano approssimazioni delle figure tramite mesh di poligoni, ma dato che si tratta di un lavoro didattico a noi interessa renderizzare le figure così come sono.
Nello specifico, io dovevo implementare il rendering di Blob. Riporto degli stralci della mia relazione per chiarire cosa sono i Blob:
regione di spazio descritta da un insieme di funzioni n-dimensionali \( \displaystyle f(d(x_1,...,x_n)) \)
ed un valore di threshold che definiscono un volume:
\( \displaystyle \sum_{i=0}^k a_i \cdot f_i(d(x_1,...,x_n)) \leq threshold \)
dove \( \displaystyle a_i \) è uno scalare e \( \displaystyle d(x_1,...,x_n) \) è una funzione che restituisce la distanza del punto \( \displaystyle p=(x_1,...x_n) \) dallo scheletro
della metasuperficie, così definita:
\( \displaystyle d \colon \mathds{R}^n \mapsto \mathds{R}^+ \)
NB:
Lo scheletro determina la forma e possiamo usare: un punto (per creare una sfera), un segmento (cilindro), etc..
(NB2: la definizione è generale, ovviamente poi si tratta di 3 dimensioni!!!)
Ora, il problema principale è determinare quando un raggio (la luce) interseca la nostra funzione, e trovare il primo punto di intersezione del raggio con il Blob.
Nella mia implementazione quello che facevo non era altro che una banale bisezione sul raggio, aiutandomi con l'analisi degli intervalli.
Ovvero, essendo \( \displaystyle f(d) \) una funzione decrescente (più il punto p da cui calcolo la distanza è vicino alla metasuperficie, più \( \displaystyle f(d) \) è grande), ne so calcolare il massimo ed il minimo.
Ovviamente se \( \displaystyle f(distanzaMin) \geq threshold\; \& \; f(distanzaMax) \leq threshold \) allora c'è intersezione, dato che sto dicendo che il punto più vicino (sul raggio) è interno alla figura, il punto più lontano è esterno. Ho gli estremi per una bisezione, la applico.
(NB3: ovviamente essendo la mia funzione totale una somma di funzioni, la cosa è leggermente più complessa, perché non calcolo il vero max e il vero min ma una sovrastima del massimo e una sottostima del minimo, ma comunque la cosa non cambia molto).
Ora mi chiedevo, è possible invece di fare bisezione applicare il metodo di Newton ad una funzione così?
In fondo è una funzione monotona decrescente (rispetto alla distanza), e io devo calcolare \( \displaystyle \sum_{i=0}^k a_i \cdot f_i(d(x,y,z)) - threshold = 0 \) , dato che quando il valore della funzione è uguale al threshold allora sono sul bordo.
Allora, facciamo alcune considerazioni. Il raggio parte da un certo punto P che si assume essere sempre esterno alla figura. Se rilevo la possibilità che ci sia l'intersezione, (come ho detto prima), so che "scorrendo" lungo il raggio il valore di \( \displaystyle f(d) \) deve diminuire, fino a raggiungere il valore del treshold, e quindi sono sul bordo (o anche, \( \displaystyle f(d) - treshold \) deve diminuire fino ad arrivare a 0 e quindi sono sul bordo).
Sotto queste ipotesi, correggetemi se sbaglio, potrei iniziare un metodo di newton, e tra l'altro partendo da un qualsiasi punto esterno alla figura (per esempio quel punto iniziale P), dato che so che per funzioni monotone decrescenti newton converge allo zero in modo globale.
Il punto è che questa distanza d non è unica per tutte le f.
Mi spiego meglio:
immaginate un Blob come una figura costituita da più figure semplici, ad esempio n sfere. Ogni funzione \( \displaystyle f_i \) definisce una di queste sfere, e per valutare quando vale \( \displaystyle \sum_{i=0}^k a_i \cdot f_i(d(x,y,z)) - threshold = 0 \) devo quindi valutare le varie f sulla distanza d.
Solo che io non posso calcolare la distanza dal blob, ma posso calcolare n distanze diverse, ognuna dal punto P al centro della sfera.
In questo senso devo considerare il blob come una funzione in n variabili, ovvero devo risolvere il problema
\( \displaystyle f_1(d_1) + f_2(d_2) + \ldots + f_n(d_n) - treshold = 0 \) , dove le varie \( \displaystyle d_i \) posso tranquillamente pensarle come numeri, senza complicarmi la vita considerandole funzioni (e questo mi aiuta molto nella definizione della derivata del blob, che mi serve per newton).
In questo caso, come posso risolvere il tutto?
Ho qualche dubbio in testa, perché non riesco a capire se devo trattare il problema come la ricerca di una radice di una funzione n-dimensionale o se comunque devo considerala una funzione a 1 variabile, dato che anche se le distanze sono tutte diverse, di fatto rappresentano la distanza dello stesso punto P da ogni isosuperfice.
In pratica ogni \( \displaystyle f_i \) da il suo contributo al calcolo totale, in base ad una distanza che è diversa per ogni \( \displaystyle f_i \) , ma che comunque rappresenta sempre la distanza da un punto comune.
Se qualcuno ha capito qualcosa di quello che ho detto mi può dare una mano?
Per ogni chiarimento ovviamente chiedete, non so se sono stato chiarissimo. In testa ho tutto chiaro, a parlarne non so mai se riesco a spiegarmi. Grazie.


