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，不过那不是我要讨论的范围。