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，不過那不是我要討論的範圍。