[心得]Half Edge的應用

[oopFoo (3d)]

3D繪圖的資料基本上只有點和面，但處理3D mesh的時候常常需要Adjacency（相鄰）的資訊。這時就需要其它資料結構。最常見的就是Winged Edge, Quad Edge與Half Edge.
Quad Edge其實就是Winged Edge的另一種變化，兩種相通，Half Edge顧名思義的就是Winged Edge的Half。
這幾個用起來其實差不多，但Half Edge稍微有效率一點。Half Edge有時也稱 doubly connected edge list (DCEL)。

Half Edge只能處理2-manifold的3d 物件，所以像3dmax ，Maya會輸出non-manifold的物件，我們要注意，要另外處理。如果不想另外處理non-manifold的問題就要用其它方法
http://vcg.isti.cnr.it/vcglib/  這是好用的MeshLab的底層Library.可處理non-2manifold
http://www.openvolumemesh.org/ 也可以用來處理non-2manifold的3d物件


但其實manifold Mesh有很多的好處和必須，像3d print, 模擬軟體常常需要closed Manifold的Mesh。

Half Edge請盡量不要自己寫，請用別人寫好的Library。常見的有
http://www.openmesh.org/
https://www.cgal.org/
https://www.pmp-library.org/

Half Edge最常見的形式是ptr based的，但其實indexed也可。如貓大https://t.co/gr6pNLZhwS

如果我們能限制polygon都是triangle的話（遊戲幾乎都是），有特別優化的方法可用
http://dtecta.com/files/GDC17_VanDenBergen_Gino_Brep_Triangle_Meshes.pdf
https://www.graphics.rwth-aachen.de/media/papers/directed.pdf
openmesh的trimesh就是特別優化的directed edge.

如果你想自己寫Half Edge的話，請一定要看
https://kaba.hilvi.org/homepage/blog/halfedge/halfedge.htm
如果看懂如何加Edge加Face的話，那後面就簡單很多。

Half Edge在遊戲裡有用嗎？
貓大就用在碰撞。
Navigation Mesh也可以使用，雖然Recast & Detour使用的是另外的Adjacency List
Procedural Generation 。
https://martindevans.me/game-development/2016/03/30/Procedural-Generation-For-Dummies-Half-Edge-Geometry/

那有遊戲真的在使用嗎？有的
https://fgiesen.wordpress.com/2012/02/21/half-edge-based-mesh-representations-theory/#comment-396
你也可以看到Graphic大神Tom Forsyth描述他的用法。

你也可以發現，discontinuities是最大的問題，而貼圖就會製造mesh的discontinuities，不過那不是我要討論的範圍。

------------------------
因為最近需要考慮要不要把Half Edge移植到Web Assembly上，所以就順便寫一篇分享與討論。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.142.245 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/GameDesign/M.1580887919.A.083.html
※ 編輯: oopFoo (36.231.142.245 臺灣), 02/05/2020 15:35:35
推 dreamnook:
推 zxc9764315: 好像對手上的工項有幫助，推個
→ oopFoo: http://www.pmp-book.org/
→ oopFoo: 我現在正要寫一個貼圖工具。本來是想寫LSCM的，但後來看到
→ oopFoo: https://bit.ly/2GZ7f7h ,Boundary First Flattening
→ oopFoo: 真的超讚。很容易讓美術調整貼圖。