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 borde y registros de caras. Dada una referencia a un registro de borde, se pueden responder varios tipos de consultas de adyacencia (consultas sobre bordes, vértices y caras vecinos) en tiempo constante. Este tipo de información de adyacencia es útil para algoritmos como la superficie de subdivisión .
Características
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 unen y se encuentran en un borde común. El orden es tal que las superficies se ordenan 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. [ aclaración necesaria ]
La estructura de datos del borde alado permite un recorrido rápido entre caras, bordes y vértices debido a la estructura explícitamente vinculada de la red. Sirve consultas de adyacencia en tiempo constante con poca sobrecarga de almacenamiento. Esta forma rica de especificar una cuadrícula no estructurada contrasta con las 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 .
Estructura y pseudocódigo
Los registros de cara y vértice son relativamente simples, mientras que el registro de borde es más complejo. Para cada vértice, su registro almacena solo la posición del vértice (por ejemplo, coordenadas) y una referencia a un borde incidente (los otros bordes se pueden encontrar siguiendo más referencias en el borde). De manera similar, cada registro de cara solo almacena una referencia a uno de los bordes que rodean la cara. Finalmente, la estructura del registro de borde es la siguiente. Se supone que un borde está dirigido. El registro de borde contiene dos referencias a los vértices que forman los puntos finales del borde, dos referencias a las caras a cada lado del borde y cuatro referencias a los bordes anterior y siguiente que rodean la cara izquierda y derecha. En resumen, el registro de borde tiene referencias a todos sus registros adyacentes, tanto al atravesar un vértice adyacente como alrededor de una cara adyacente.
class Edge { Vértice * vert_origin, * vert_destination; Cara * cara_izquierda, * cara_derecha; Edge * edge_left_cw, * edge_left_ccw, * edge_right_cw, * edge_right_ccw;}class Vertex { flotar x, y, z; Borde * borde;}class Face { Borde * borde;}
Ver también
enlaces externos
- Bruce G. Baumgart. 1972. Representación del poliedro de borde alado. Informe técnico. Universidad de Stanford, Stanford, CA, EE. UU.
- Bruce G. Baumgart. 1975. Una representación de poliedro para visión por computadora. En Actas del 19 al 22 de mayo de 1975, conferencia y exposición nacional de computadoras (AFIPS '75). ACM, Nueva York, NY, EE. UU., 589-596. DOI = 10.1145 / 1499949.1500071 http://doi.acm.org/10.1145/1499949.1500071 ( Representación de poliedro de borde alado para visión artificial )
- La estructura de datos de borde alado , en la Universidad Tecnológica de Michigan
- Winged Edge , en la Universidad de Pisa