关于多边形三角化，ue4 c++

旧城等待， 2023-10-17 11:47 9阅读 0赞

问题：将一个多边形的所有点按顺序输入（顺逆皆可），输出所有三角形的点的index；

问题描述：如何将一个多边形三角化是三维模型中一个比较常见的问题。最初的想法很简单，认为就是以一个点起点连接和它不相邻的点所有三角形就区分完了。这样写完后放到ue4里面测试，开始比较顺利，当但遇到凹多边形时，就发现问题了。着实一想确实有问题，这样只能判断凸多边形，对于凹多边形时不行的。于是乎查询资料，找到这篇文档(找不到原文了。。)，按照上面的思路一想确实可行。便开始垒代码，写完后DEBUG发现一个问题在遇到“+”这种多边形时，移除两个点后发现出现了四点共线的情况。

想到的便是先把这些共线点移除，在进行凹凸性的判断，然后从第一个凸点开始查看左右相邻点是否可以构成想要的三角形。如果可以就添加进入三角形数组，然后移除该点，依次往后。跳出循环时判断原始数组是否被移除完毕了，如果没有重复以上步骤直到原始数组剩余点数小于3再跳出即可。

三角形提取程序思路：

1.  移除重合点（连续三点i-1,i,i+1,不共线，共线移除中间点）；
2.  找出多边形边缘点i点，用i点到i-1点向量叉乘i点到i+1点向量，得到多边形时序，默认小于零为顺时针（边缘点就是x或者y最大或者最小的点，该点必定为凸点）；
3.  判断每一点的凹凸性（利用②中叉乘的值和自身点的两个向量差乘值比较，相同符号为凸，即可获得所有点的凹凸）
4.  以第一个凸点一个点开始计算构成改点的三角形（i-1，i，i+1）中是否包含其余点。若是，则找到下一个凸点计算直到找到为止，添加该三角形的三个点的index，并从多边形数组中移除该点（注意：①三个点添加到你的三角形面数组的顺序要和你的面朝向有关，在ue4里面三角形法向可以由左手定则表示，四手指按照i-1，i，i+1的顺序，大拇指的朝向就是面的法向量方向。②应该在移除一个点后从新计算点的凹凸性,以及注意循环起始index\[如果弄不清就由从index=0开始循环\]。）

如图是[简单的html网页测试][html]：

![5d387ae97c494abfb4b9ac04ea9057e2.png][]

虽然说看着只有四个步骤，但是初次尝试还是遇到各种想不通的问题，比如程序可以很好地编译，但是一到ue4里面运行就崩溃，将程序放在ue4的新项目里面就可以很好地运行输出。这个问题困扰了很久，最后终于找到问题所在，由于之前在项目里面添加了第三方库，可能导致重复命名了，最后通过封装一个新的类，终于解决了这个问题。

[html]: http://1.14.71.218/%E5%A4%9A%E8%BE%B9%E5%BD%A2%E4%B8%89%E8%A7%92%E5%8C%96.html
[5d387ae97c494abfb4b9ac04ea9057e2.png]: https://img-blog.csdnimg.cn/5d387ae97c494abfb4b9ac04ea9057e2.png