from Hacker News

Half-Edge Data Structures (2019)

by msvan on 8/11/23, 8:08 PM with 8 comments

• by Mageek on 8/11/23, 8:50 PM

  Another very good blog overview here (not mine): https://ianthehenry.com/posts/delaunay/

  I love DCELs and have been tinkering with them in my own side projects lately. Very cool data structure!

• by speps on 8/11/23, 9:18 PM

  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/fc52516467dfa124b...

  [2] http://www.glprogramming.com/red/chapter11.html#name1

• by kaveh808 on 8/11/23, 11:10 PM

  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

• by amelius on 8/11/23, 11:16 PM

  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

• by slavapestov on 8/12/23, 1:29 AM

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

• by bionhoward on 8/12/23, 1:30 AM

  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.

• by blobfish01 on 8/11/23, 10:07 PM

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

• by denvaar on 8/12/23, 1:07 AM

  A little margin/padding would go a long way