4 ms·

Half-Edge Data Structures (2019)

69 points by msvan 3y ago

Mageek 3y ago
Another very good blog overview here (not mine): https://ianthehenry.com/posts/delaunay/ https://ianthehenry.com/posts/delaunay/ I love DCELs and have been tinkering with them in my own side projects lately. Very cool data structure!
speps 3y ago
The original GLU Tessellator[1][2] used that structure for most of its internal representation of meshes, it's a very powerful data structure for meshes. [1] https://github.com/memononen/libtess2/blob/fc52516467dfa124bdd967c15c7cf9faf02a34ca/Source/mesh.h#L40 https://github.com/memononen/libtess2/blob/fc52516467dfa124b... [2] http://www.glprogramming.com/red/chapter11.html#name1 http://www.glprogramming.com/red/chapter11.html#name1
blobfish01 3y ago
In action: https://doc.cgal.org/latest/Surface_mesh/index.html https://doc.cgal.org/latest/Surface_mesh/index.html Built on top of boost graph.
amelius 3y ago
The difficulty, in a geometric setting, is still how to maintain a robust correspondence between geometry and topology. https://en.wikipedia.org/wiki/Robust_geometric_computation https://en.wikipedia.org/wiki/Robust_geometric_computation
kaveh808 3y ago
The Symbolics Lisp Machine S-Geometry 3D modeler from the mid 1980's was based on the winged-edge structure. It was the best polygonal modeler of its time, and the package lives on in philosophy as the Wings3D open source modeler. https://www.youtube.com/watch?v=UNXEemZ_Ysk https://www.youtube.com/watch?v=UNXEemZ_Ysk
denvaar 3y ago
A little margin/padding would go a long way
slavapestov 3y ago
I enjoyed reading this book a few years ago: https://www.amazon.com/Introduction-Solid-Modeling-Martti-Mantyla/dp/0716780151 https://www.amazon.com/Introduction-Solid-Modeling-Martti-Ma...
bionhoward 3y ago
This article would be more clear if the & symbol were clarified. Right now it looks like Rust borrowing in Python. Maybe I’m too dumb and didn’t read it right and missed the definition. Anyway the big picture idea is cool and resonates with the idea of a bidirectional HashMap.

69 points by msvan 3y ago

Another very good blog overview here (not mine): https://ianthehenry.com/posts/delaunay/ https://ianthehenry.com/posts/delaunay/ I love DCELs and have been tinkering with them in my own side projects lately. Very cool data structure!

speps 3y ago

The original GLU Tessellator[1][2] used that structure for most of its internal representation of meshes, it's a very powerful data structure for meshes. [1] https://github.com/memononen/libtess2/blob/fc52516467dfa124bdd967c15c7cf9faf02a34ca/Source/mesh.h#L40 https://github.com/memononen/libtess2/blob/fc52516467dfa124b... [2] http://www.glprogramming.com/red/chapter11.html#name1 http://www.glprogramming.com/red/chapter11.html#name1

blobfish01 3y ago

In action: https://doc.cgal.org/latest/Surface_mesh/index.html https://doc.cgal.org/latest/Surface_mesh/index.html Built on top of boost graph.

amelius 3y ago

The difficulty, in a geometric setting, is still how to maintain a robust correspondence between geometry and topology. https://en.wikipedia.org/wiki/Robust_geometric_computation https://en.wikipedia.org/wiki/Robust_geometric_computation

kaveh808 3y ago

The Symbolics Lisp Machine S-Geometry 3D modeler from the mid 1980's was based on the winged-edge structure. It was the best polygonal modeler of its time, and the package lives on in philosophy as the Wings3D open source modeler. https://www.youtube.com/watch?v=UNXEemZ_Ysk https://www.youtube.com/watch?v=UNXEemZ_Ysk

denvaar 3y ago

A little margin/padding would go a long way

slavapestov 3y ago

I enjoyed reading this book a few years ago: https://www.amazon.com/Introduction-Solid-Modeling-Martti-Mantyla/dp/0716780151 https://www.amazon.com/Introduction-Solid-Modeling-Martti-Ma...

bionhoward 3y ago

This article would be more clear if the & symbol were clarified. Right now it looks like Rust borrowing in Python. Maybe I’m too dumb and didn’t read it right and missed the definition. Anyway the big picture idea is cool and resonates with the idea of a bidirectional HashMap.