algorithm - Inicializando la estructura de datos de medio borde desde vértices

data-structures computational-geometry

Question

Estoy trabajando en la implementación de varios algoritmos de subdivisión (como catmull-clark); hacer esto de manera eficiente requiere una buena manera de almacenar información sobre una cuadrícula de polígonos tesselated. Implementé la estructura de datos de medio borde como se indica en el código de flujo , pero ahora no estoy seguro de cómo poblar la estructura de datos de los vértices.

Mi primer intento fue

• crear vértices
• agrupar vértices en caras
• ordena los vértices dentro de las caras (usando su ángulo relativo al centroide)
• para cada cara, tome el primer vértice y luego recorra la lista de vértices ordenados para crear una lista de medio borde.

¡Sin embargo, esto crea una lista de caras (con semidesfiles) que no tienen ninguna información sobre caras adyacentes! Esto también se siente un poco mal, porque parece que las caras son realmente el objeto de primera clase y los bordes proporcionan información auxiliar; Realmente siento que debería crear bordes a partir de los vértices y luego ordenar las caras desde allí. Pero, una vez más, no estoy realmente seguro de cómo hacerlo, no puedo pensar en una forma de crear una lista de medias aristas sin crear las caras primero.

¿Alguna sugerencia sobre cuál es la mejor manera de convertir los datos sobre vértices (y caras) en bordes medios?

Answer 1

Primero, me gustaría señalarle una excelente implementación en C ++ de la estructura de datos de mitad de borde: OpenMesh . Si desea usarlo, asegúrese de trabajar en el tutorial. Si (y solo si) haces eso, trabajar con OpenMesh es bastante sencillo. También contiene algunos métodos interesantes sobre los cuales puede implementar algoritmos de subdivisión o reducción.

Ahora a tu pregunta:

¡Sin embargo, esto crea una lista de caras (con semidesfiles) que no tienen ninguna información sobre caras adyacentes! Esto también se siente un poco mal, porque parece que las caras son realmente el objeto de primera clase y los bordes proporcionan información auxiliar

Creo que esto pierde un poco el punto de la estructura de datos de medio borde. En una estructura de medio borde, ¡son los medios bordes los que llevan la mayor cantidad de información!

Citando descaradamente de la documentación de OpenMesh (ver también la figura allí):

• Cada vértice hace referencia a un semicírculo saliente, es decir, un semiciso que comienza en este vértice.
• Cada cara hace referencia a uno de los semicedios que lo delimitan.
• Cada halfedge proporciona un mango para
  • el vértice al que apunta,
  • la cara a la que pertenece
  • la siguiente media cuña dentro de la cara (ordenada en sentido contrario a las agujas del reloj),
  • el semisero opuesto,
  • (opcionalmente: el semiseguro anterior en la cara).

Como puede ver, la mayoría de la información se almacena en los medios bordes , estos son los objetos primarios. Iterar sobre mallas en esta estructura de datos se trata de seguir inteligentemente los punteros.

¡Sin embargo, esto crea una lista de caras (con semidesfiles) que no tienen ninguna información sobre caras adyacentes!

¡Esto está perfectamente bien! Como se ve arriba, una cara solo hace referencia a un borde medio delimitador. Suponiendo una malla de triángulos, la cadena de punteros que sigues para obtener los 3 triángulos adyacentes a una cara dada F es la siguiente:

F -> halfEdge -> oppositeHalfEdge -> face

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

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

Opcionalmente, puede usar nextHalfEdge -> nextHalfEdge si no usa los punteros ''anteriores''. Esto, por supuesto, se generaliza fácilmente a cuadrantes o polígonos de orden superior.

Si establece correctamente los punteros enumerados anteriormente al construir su malla, entonces puede iterar sobre todo tipo de adyacencias en su malla de esta manera. Si usa OpenMesh, puede usar un grupo de iteradores especiales que apuntan hacia el puntero.

Por supuesto, configurar los punteros de "medio borde opuesto" es la parte difícil cuando se construye una estructura de medio borde a partir de una "sopa de triángulo". Sugiero utilizar una estructura de datos de mapas de algún tipo para realizar un seguimiento de los medios bordes ya creados.

Para ser más específicos, aquí hay un pseudocódigo muy conceptual para crear una malla de medio borde a partir de caras. Omití la parte del vértice, que es más simple y se puede implementar con el mismo espíritu. Supongo que la iteración sobre los bordes de una cara está ordenada (por ejemplo, en el sentido de las agujas del reloj).

Supongo que las medias aristas se implementan como estructuras de tipo HalfEdge , que contienen los punteros enumerados anteriormente como miembros.

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

Deje que Edges sea ​​un mapa de pares de identificadores de vértice a punteros a las instancias reales de medio borde, por ejemplo

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

en C ++. Aquí está el pseudocódigo de construcción (sin la parte de vértice y cara):

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) ];
       }
    }
 }

EDITAR: hizo el código un poco menos pseudo, para ser más claro sobre el mapa de Edges y los punteros.