四边形网格剖分算法代码

由于四边形网格剖分算法有很多种不同的实现方式，以下代码只是其中一种可能的实现，仅供参考。

输入：一个四边形网格的顶点坐标数组 vertices，每个四边形的顶点编号数组 indices，以及期望的网格尺寸 gridSize。

输出：一个新的顶点坐标数组 newVertices 和索引数组 newIndices，分别对应剖分后的三角形网格。

import numpy as np

def quad_mesh_split(vertices, indices, gridSize):
    # 将四边形网格转换为三角形网格
    triangles = []
    for i in range(len(indices)):
        if i % 2 == 0:
            # 第偶数个四边形
            triangles.append((indices[i], indices[i+1], indices[i+2]))
            triangles.append((indices[i], indices[i+2], indices[i+3]))
        else:
            # 第奇数个四边形
            triangles.append((indices[i], indices[i+1], indices[i+3]))
            triangles.append((indices[i+1], indices[i+2], indices[i+3]))
    
    newVertices = vertices.copy()
    newIndices = []
    
    # 按照行列顺序遍历网格
    rows = int(np.ceil((vertices[:,1].max() - vertices[:,1].min()) / gridSize))
    cols = int(np.ceil((vertices[:,0].max() - vertices[:,0].min()) / gridSize))
    for i in range(rows):
        for j in range(cols):
            # 计算当前格子的四个顶点编号
            v1 = len(newVertices)
            v2 = v1 + 1
            v3 = v1 + 2
            v4 = v1 + 3
            
            # 计算当前格子的四个顶点坐标
            x1 = vertices[:,0].min() + j * gridSize
            y1 = vertices[:,1].min() + i * gridSize
            newVertices = np.vstack((newVertices, [x1, y1]))
            
            x2 = x1 + gridSize
            y2 = y1
            newVertices = np.vstack((newVertices, [x2, y2]))
            
            x3 = x2
            y3 = y2 + gridSize
            newVertices = np.vstack((newVertices, [x3, y3]))
            
            x4 = x1
            y4 = y3
            newVertices = np.vstack((newVertices, [x4, y4]))
            
            # 将当前格子的四边形分割成两个三角形
            newIndices.append((v1, v2, v3))
            newIndices.append((v1, v3, v4))
            
    return newVertices, newIndices

注意，上述代码中的四边形网格顶点顺序是按照顺时针方向排列的。如果输入的顶点顺序是逆时针方向的，则需要先将其转换为顺时针方向，否则会导致剖分结果不正确。