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://webptt.com/cn.aspx?n=bbs/GameDesign/M.1580887919.A.083.html ※ 编辑: oopFoo (36.231.142.245 台湾), 02/05/2020 15:35:35