Структура «крылатое ребро» (winged-edge)
Классическая структура данных полигональной сетки, где каждое ребро помнит две свои вершины, две смежные грани и четыре соседних ребра.
Если хранить сетку просто списком треугольников, вопрос «какие грани делят это ребро?» обходится дорого — приходится перебирать всё. В winged-edge, которую Брюс Баумгарт (Bruce Baumgart) предложил в диссертации в Стэнфорде в 1972 году, вся топология подвешена на ребро: две его конечные вершины, две разделяемые им грани и четыре ребра, «крыльями» отходящие от его концов. Запросы о смежности выполняются за константное время.
Расплата — память и учёт: любая правка должна согласованно обновить множество перекрёстных ссылок. Более поздние структуры вроде half-edge (направленные полурёбра) и quad-edge упростили обход и сегодня преобладают в средствах моделирования и обработки сеток, но winged-edge первой сделала посильной произвольную топологию.