Intersezione di una mesh con una superficie parametrica

Question

Mi chiedo come sia possibile scrivere un algoritmo preciso per calcolare la frontiera della superficie di intersezione tra una superficie parametrica f : R^2 --> R^3 e una maglia triangolata.

ho pensato ad un primo approccio:

nStepsU = 100 
nStepsV = 100 
tolerance=0.01 // pick some sensical value 
intersectionVertices={} 
for u from minU to maxU in nStepsU: 
    for v from minV to maxV in nStepsV: 
     for v in verticesInMesh: 
      if euclidean distance(f(u,v), v) < tolerance: 
       add vertex v in a set 

connect the vertices in intersectionVertices with a line strip 
draw the vertices in intersectionVertices 

Questo algoritmo, è molto semplice ma lento (n^3) e non tiene conto del fatto che la topografia della rete è basata su triangoli così i punti di output sono punti della mesh e non punti calcolati che sfruttano l'intersezione della superficie con i triangoli ed è fortemente dipendente dalla tolleranza che si deve impostare.

Qualcuno ha un'idea migliore o può portarmi a una libreria adatta per questo scopo?

Answer 1

Vorrei scorrere su ciascun triangolo e calcolare l'intersezione del triangolo con la superficie. Vorrei usare uno shader di geometria che prende i triangoli come input e emette strisce di linea. Per ogni vertice nel triangolo, calcola la distanza segnata verso la superficie. Quindi scorrere i bordi: se ci sono due vertici in cui h ha segni diversi, il bordo tra questi vertici si interseca con la superficie. Mentre sono sicuro che l'incrocio esatto può essere calcolata, la soluzione più semplice sarebbe quella di interpolare linearmente, cioè

vec3 intersection = (h0 * v1 + h1 * v0)/(h0 + h1); 

uscita Poi ogni incrocio come un vertice del segmento di linea.

Il codice che ho inviato here può iniziare. Se vuoi semplicemente disegnare il risultato, probabilmente incontrerai lo stesso problema che ho descritto in quella domanda. Se hai bisogno dei vertici sul client, puoi usare transform feedback.

Modifica: ho appena fatto un piccolo test. Come la funzione di distanza ho usato

float distToHelicoid(in vec3 p) 
{ 
    float theta = p.y/5 + offset.x/50; 
    float a = mod(theta - atan(p.z, p.x), 2*PI) - PI; // [-PI, PI[ 
    if (abs(a) > PI/2) 
    a = mod(theta - atan(-p.z, -p.x), 2*PI) - PI; 
    return a; 
} 

Poiché non v'è dentro/fuori, e questa funzione la distanza va da -90 ° a 90 °, si può emettere solo i vertici se il segno va dal piccolo negativo a positivo o piccole viceversa, non quando si inverte da 90 ° a -90 °. Qui semplicemente filtrato distanze dove abs (dist)> 45 °:

pulita modo sarebbe per determinare l'indice della rivoluzione vicina. Per esempio. [-pi, pi] sarebbe rivoluzione 0, [pi, 3pi] = rivoluzione 1, ecc. Quindi emetteresti solo se due distanze si riferiscono alla stessa rivoluzione.

Answer 2

Se la superficie è sempre elicoidale, si può provare a proiettare tutto su un cilindro intorno all'asse Y.

La superficie elicoidale è costituito da linee ortogonali alla superficie di quel cilindro e dopo la proiezione si otterrà una spirale . Dopo aver proiettato la mesh triangolare 3D su quel cilindro, otterrai una mesh triangolare 2D (nota che alcune aree potrebbero essere coperte da diversi strati di triangoli).

Così il compito diventa trovare triangoli in mesh triangolare 2D che intersecano la spirale che è più semplice. Se stai bene con le approssimazioni, puoi segmentare quella spirale e usare un qualche tipo di albero per trovare i triangoli che intersecano la spirale.

Quando si ha un triangolo che interseca parte della spirale, la sua intersezione sarà un segmento, è possibile ricalcolare solo le coordinate 3D del segmento e l'insieme di questi segmenti è la linea di intersezione.