En gráficos por computadora , la estructura de datos de borde alado es una forma de representar mallas poligonales en la memoria de la computadora . Es un tipo de representación de límites y describe tanto la geometría como la topología de un modelo. Se utilizan tres tipos de registros: registros de vértice, registros de arista y registros de cara. Dada una referencia a un registro de aristas, se pueden responder varios tipos de consultas de adyacencia (consultas sobre aristas, vértices y caras vecinas) en tiempo constante . Este tipo de información de adyacencia es útil para algoritmos como la superficie de subdivisión . [1]
La estructura de datos de borde alado describe explícitamente la geometría y topología de caras, bordes y vértices cuando tres o más superficies se juntan y se encuentran en un borde común. El orden es tal que las superficies están ordenadas en sentido antihorario con respecto a la orientación innata del borde de intersección. Además, la representación permite situaciones numéricamente inestables como la que se muestra a continuación. [ se necesita aclaración ]
La estructura de datos de borde alado permite un recorrido rápido entre caras, bordes y vértices debido a la estructura explícitamente vinculada de la red. Atiende consultas de adyacencia en tiempo constante con poca sobrecarga de almacenamiento. Esta rica forma de especificar una cuadrícula no estructurada contrasta con especificaciones más simples de mallas poligonales , como una lista de nodos y elementos, o la conectividad implícita de una cuadrícula regular . Una alternativa a la estructura de datos de borde alado es la estructura de datos de medio borde .
Los registros de caras y vértices son relativamente simples, mientras que los registros de aristas son más complejos.
En resumen, el registro de arista tiene referencias a todos sus registros adyacentes, tanto cuando se atraviesa alrededor de un vértice adyacente como alrededor de una cara adyacente.
borde de clase{ Vértice *vert_origin, *vert_destination; Cara *cara_izquierda, *cara_derecha; Borde *edge_left_cw, *edge_left_ccw, *edge_right_cw, *edge_right_ccw;}clase vértice{ flotar x, y, z; Borde *borde;}cara de clase{ Borde *borde;}