Winged edge

Nella computer grafica, la struttura dati del winged edge è un metodo per rappresentare mesh poligonali nella memoria del computer. È un tipo di rappresentazione dei confini e descrive sia la geometria che la topologia di un modello. Vengono utilizzati tre tipi di record: record di vertice, record di bordo e record di faccia. Dato un riferimento a un record di bordo, è possibile rispondere a diversi tipi di query di adiacenza (su bordi, vertici e facce vicini) in tempo costante. Questo tipo di informazioni di adiacenza è utile per algoritmi come la superficie di suddivisione.

Rappresentazione grafica di un record di bordo (si noti che i riferimenti del bordo sembrano delle ali)

Funzionalità

La struttura dati del winged edge descrive in modo esplicito la geometria e la topologia di facce, bordi e vertici quando tre o più superfici si uniscono e si incontrano su un bordo comune. L'ordinamento è tale che le superfici sono ordinate in senso antiorario rispetto all'orientamento innato del bordo di intersezione. Inoltre la rappresentazione consente situazioni numericamente instabili.

Struttura e pseudocodice

I record di faccia e vertice sono relativamente semplici, mentre il record di bordo è più complesso.

• Per ogni vertice, il suo record memorizza solo la posizione del vertice (ad es. coordinate) e un riferimento a un bordo incidente. Gli altri bordi possono essere trovati seguendo ulteriori riferimenti.

• Allo stesso modo, ogni record di faccia memorizza solo un riferimento a uno dei bordi che circondano la faccia.
• Infine, la struttura del record di bordo è la seguente: si presume che un bordo sia diretto. Il record di bordo contiene due riferimenti ai vertici che costituiscono i punti finali del bordo, due riferimenti alle facce su entrambi i lati del bordo e quattro riferimenti ai bordi precedente e successivo che circondano la faccia sinistra e destra.

In breve, il record di bordo ha riferimenti a tutti i record adiacenti, sia quando si sposta attorno a un vertice adiacente che attorno a una faccia adiacente.

class Edge {
  Vertex *vert_origin, *vert_destination;
  Face *face_left, *face_right;
  Edge *edge_left_cw,
       *edge_left_ccw,
       *edge_right_cw,
       *edge_right_ccw;
}
class Vertex {
  float x, y, z;
  Edge *edge;
}
class Face {
  Edge *edge;
}