问题描述
我继承了一些旧代码，这些代码可以在三角形之间旋转边缘以改善拓扑分布，
该算法效果很好，但计算量很大。
I've inherited some legacy code that rotates edges between triangles for improved topology distribution,this algorithm works well but is quite computationally intensive.
给出由四个共享边的三角形组成的四边形的伪代码为：
The psudo-code given the quad made up of two triangles that share an edge is:
/* split 0-2 */
score_02 = (area(v0, v1, v2) / perimeter(v0, v1, v2)) +
(area(v0, v2, v3) / perimeter(v0, v2, v3));
/* split 1-3 */
score_13 = (area(v1, v2, v3) / perimeter(v1, v2, v3)) +
(area(v0, v1, v3) / perimeter(v0, v1, v3));
/* negative number when (0-2) is an improved state */
result = score_13 - score_02;
此方法效果很好，并且可以在2D三角剖分区域上进行细分（参见示例）。
This works very well and can give nice tessellation on 2D triangulated regions (see example).
我主要担心的是效率不是很高（周长计算涉及6个平方根调用）。
My main concern is this is not very efficient (perimeter calculations involve 6 square-root calls).
还有其他吗/更好的方法来计算在（上方）之前，在（下方）之后的松弛状态，例如：
Are there other/better methods to calculate a relaxed state before (above), after relaxation (below), eg:
无法使用好的方法可能是：
Failing to use a good method may:
- 使其中一个三角形的面积为零
（取决于输出的用途，这可能会产生级联效果-面法线为零的面 - 划分不当可能会导致映射纹理变形或严重变形。
已经指出（现在已删除答案）可以使用简单的最短边方法，但是分布不佳（注意边界处的细三角形），例如：
It's been pointed out (in an answer that is now deleted) that a simple shortest-edge method can be used, however this doesn't give a good distribution (notice the skinny triangles at the boundaries) eg:
注1）这可能是一个众所周知的问题，因为它没有记录在
代码中，因此搜索起来并非易事：）
注2）到目前为止，我没有认真研究其他方法，我可能会这样做，并将发现结果发布在这里。
推荐答案
您可以尝试生成约束的delaunay三角剖分。这是给定点集可能具有的最精确的（可证明的）三角测量。
You can try producing a constrained delaunay triangulation. This is the "nicest" (provable) triangulation you may have for a given point set.
如果您可以在内部添加更多点（而不改变形状），或者边缘（称为steiner点），可以保证有更好的三角形（就最小的内角和面积而言）。
If you can add more points (without changing the shape) to the interior or the edges (called steiner points), you can guarantee better triangles (in terms of minimum interior angles and area).
请参阅： http://www.cs.cmu.edu/~quake/triangle.defs.html#conform 。
CGAL具有这些实现。
CGAL has implementations for these.
这篇关于用于计算细分三角形的边缘的最“均匀”方向的算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！