Inizializzazione della struttura dati a mezza costa dai vertici

Question

Sto lavorando all'implementazione di vari algoritmi di suddivisione (come catmull-clark); per farlo in modo efficiente è necessario un buon modo per memorizzare informazioni su una griglia di poligoni tessellati. Ho implementato la struttura dati a mezza costa come outlined by flipcode, ma ora non sono sicuro di come popolare la struttura dei dati dai vertici!

mio tentativo iniziale era di

• creare vertici
• vertici gruppo in facce
• vertici sort raggio facce (utilizzando il loro angolo rispetto al centroide)
• per ogni faccia, afferrare il primo vertice e quindi percorrere l'elenco dei vertici ordinati per creare un elenco a metà bordo.

Tuttavia, questo crea un elenco di facce (con mezzi bordi) che non hanno alcuna informazione sulle facce adiacenti! Anche questo sembra un po 'sbagliato, perché sembra che le facce siano davvero l'oggetto di prima classe e che i bordi forniscano informazioni ausiliarie; Mi sento davvero come se dovessi creare bordi dai vertici e quindi selezionare i volti da lì. Ma ancora una volta, non sono davvero sicuro di come procedere in questo modo - Non riesco a pensare a un modo per creare un elenco di mezzi bordi senza creare prima i volti.

Qualche suggerimento su quale sia il modo migliore per trasformare i dati dei vertici (e delle facce) in mezzitoni?

Answer 1

Innanzitutto, vorrei indicarvi un'eccellente implementazione C++ della struttura dati a mezza costa: OpenMesh. Se vuoi usarlo, assicurati di lavorare nel tutorial. Se (e solo se) lo fai, lavorare con OpenMesh è abbastanza semplice. Contiene anche alcuni buoni metodi in cima ai quali è possibile implementare algoritmi di suddivisione o suddivisione.

Ora alla tua domanda:

Tuttavia, questo crea un elenco di facce (con mezze bordi) che non hanno alcuna informazione su facce adiacenti! Anche questo sembra un po 'sbagliato, perché sembra che le facce siano davvero l'oggetto di prima classe e gli spigoli forniscano informazioni ausiliarie

Penso che in qualche modo manchi il punto della struttura dati a mezza costa. In una struttura a mezza costa, sono i mezzi bordi che portano la maggior parte delle informazioni!

Citando spudoratamente dal OpenMesh documentation (si veda anche la figura lì):

• Ogni vertice riferimento per una HalfEdge uscente, cioè un HalfEdge che inizia a questo vertice.
• Ogni faccia fa riferimento a una delle mezzene che lo delimita.
• Ogni HalfEdge fornisce una maniglia per
  • vertice cui punta,
  • faccia appartiene
  • successivo HalfEdge all'interno della faccia (ordinata in senso antiorario),
  • il HalfEdge opposto ,
  • (opzionalmente: il precedente halfedge in faccia).

Come si vede, maggior parte delle informazioni sono memorizzate nelle mezze bordi - questi sono gli oggetti primari. L'iterazione di mesh su questa struttura di dati si basa in modo intelligente sui seguenti indicatori.

Tuttavia, questo crea un elenco di facce (con mezzi bordi) che non hanno alcuna informazione sulle facce adiacenti!

Questo è perfettamente ok! Come si vede sopra, una faccia fa riferimento a solo a con un mezzo bordo di delimitazione. Assumendo una mesh triangolare, la catena di puntatori seguite per ottenere i 3 triangoli adiacenti per una data faccia F è la seguente:

F -> halfEdge -> oppositeHalfEdge -> face

F -> halfEdge -> nextHalfEdge -> oppositeHalfEdge -> face

F -> halfEdge -> previousHalfEdge -> oppositeHalfEdge -> face

Facoltativamente, è possibile utilizzare nextHalfEdge -> nextHalfEdge se non si utilizzano i puntatori "precedenti". Questo, ovviamente, si generalizza facilmente ai quadricipiti o ai poligoni di ordine superiore.

Se si impostano correttamente i puntatori sopra elencati quando si costruisce la mesh, è possibile scorrere su tutti i tipi di adiacenze della mesh in questo modo. Se usi OpenMesh, puoi usare una serie di iteratori speciali che il puntatore insegue per te.

L'impostazione dei puntatori "bordo intermedio opposto" è ovviamente la parte difficile quando si costruisce una struttura a mezza costa da una "zuppa triangolare". Suggerisco di usare una struttura di dati di una mappa per tenere traccia dei mezzi bordi già creati.

Per essere più specifici, ecco alcuni pseudo-codice molto concettuale per creare una mesh a metà bordo dalle facce. Ho omesso la parte vertice, che è più semplice, e può essere implementata nello stesso spirito. Suppongo che l'iterazione su bordi di una faccia sia ordinata (ad esempio in senso orario).

Suppongo che i mezzi bordi siano implementati come strutture di tipo HalfEdge, che contengono i puntatori elencati sopra come membri.

struct HalfEdge 
    { 
     HalfEdge * oppositeHalfEdge; 
     HalfEdge * nextHalfEdge; 
     Vertex * vertex; 
     Face * face; 
    } 

Sia Edges essere una mappa da coppie di identificatori di vertici a puntatori alle istanze mezza bordo reale, ad esempio

map< pair<unsigned int, unsigned int>, HalfEdge* > Edges; 

in C++.Ecco il pseudo-codice di costruzione (senza la parte di vertice e la faccia):

map< pair<unsigned int, unsigned int>, HalfEdge* > Edges; 

for each face F 
{ 
    for each edge (u,v) of F 
    { 
     Edges[ pair(u,v) ] = new HalfEdge(); 
     Edges[ pair(u,v) ]->face = F; 
    } 
    for each edge (u,v) of F 
    { 
     set Edges[ pair(u,v) ]->nextHalfEdge to next half-edge in F 
     if (Edges.find(pair(v,u)) != Edges.end()) 
     { 
     Edges[ pair(u,v) ]->oppositeHalfEdge = Edges[ pair(v,u) ]; 
     Edges[ pair(v,u) ]->oppositeHalfEdge = Edges[ pair(u,v) ]; 
     } 
    } 
} 

EDIT: Realizzato il codice un po 'meno pseudo, per essere più chiaro circa la cartina Edges ei puntatori.