[心得]Half Edge的應用

看板GameDesign (遊戲設計)作者oopFoo (3d)時間4年前 (2020/02/05 15:31)推噓2(2推 0噓 4→)

留言6則, 3人參與討論串1/1

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