背景

在用trimesh处理模型时，遇到这样一个问题：

给定一个mesh和一张贴图，如何在mesh的每一个face（即每一个三角面片）上贴上此图？

问题

设置贴图关键是设置顶点的uv坐标，最开始的思路是，先设置贴图的4个角落：

uv = np.array([
    [0.0, 0.0],
    [1.0, 0.0],
    [1.0, 1.0],
    [0.0, 1.0],
])

再建立一个(len(vertices), 2)的numpy数组，遍历时依次填入各角落对应的uv坐标。

这样尝试后，发现mesh的贴图会出现很多奇怪的纹路——这是uv坐标有问题的表现。那问题出现在哪里？

问题在于，mesh的face间会相邻，顶点可能在多个face中存在。因此遍历时，顶点的uv坐标可能覆盖，且同一个face的顶点可能用了相同的uv坐标。这样渲染时就可能是从texture中提取了点或线，而不是提取一个三角面，这些点/线在mesh的face上展开时，就会有异样的纹路。

思路

之前的实现显然少了约束，思考一番后，重新定义问题如下：

给出n个三角形，以及0、1、2、3共四个数，要求每个三角形的顶点都分配一个值，且三角形各个顶点的值不一致。在这些三角形有可能相邻的情况下，如何实现一个分配算法？

拿纸演算了下，发现问题并不太简单。问题的描述又有些冗长，搜索后也没找到思路的火花。抱着试一试的想法，问了下chatGPT，其回答是：

这是一个图着色问题，可以使用图论中的染色算法来解决。

首先，将每个三角形看作一个节点，如果两个三角形有共同的边，则它们之间连一条边。这样得到的图称为三角形图。

对于这个三角形图，可以使用贪心算法来进行染色。具体步骤如下：

  1. 将三角形图中的所有节点按照度数从大到小排序。

  2. 依次遍历每个节点，将其周围已经染色的节点的颜色从可选颜色列表中删除。

  3. 如果所有可选颜色都已经被用过，为当前节点分配一个新的颜色。

  4. 继续处理下一个节点，直到所有节点都被染色。

对于本题中的0、1、2、3四个数，可以将它们看作四个颜色，每个三角形的顶点对应一个节点，然后按照上述方法进行染色即可。

需要注意的是，这种染色算法并不能保证一定能够找到一种可行的染色方案。当图中存在奇环（即环的长度为奇数）时，无论使用何种染色算法都无法找到可行的染色方案。因此，在实际应用中，需要对算法进行改进或者针对特定的问题进行分析，以保证能够得到正确的结果。

本来已经做好了chatGPT又会胡诌一番，煞有其事地编出些“算法”。但看到“图着色”的一刻，记忆又涌了上来——我知道它是对的。我怎么会没想到图着色呢？（好吧，图论在工作里遇到的实在太少了）

再复习下图着色：

实现

现在首要问题变成了如何生成vertex的图。查看了下trimesh，颇为惊喜地发现trimesh就带了graph模块，并提供了trimesh.graph.vertex_adjacency_graph 函数，其返回一个networkx.Graph结构。

再看networkx， 和其名称一样，是一个专门做图分析的包。那么应当有对经典着色问题的实现？果真有，Coloring — NetworkX 3.0 documentation

剩下的实现变得颇为简单：

mesh = trimesh.load('test.obj')
texture = cv2.imread('test.png')
# 省略其它处理
graph = trimesh.graph.vertex_adjacency_graph(mesh)
coloring = nx.coloring.greedy_color(graph, interchange=True)
num_colors = max(coloring.values()) + 1

uv = np.array([
    [0.0, 0.0],
    [1.0, 0.0],
    [1.0, 1.0],
    [0.0, 1.0],
    [0.0, 0.5],
    [0.5, 0.0],
    [0.5, 0.5]
])
# 如所需color的数量大于当前`uv`元素数量，则插入随机坐标以补足
if uv.shape[0] < num_colors:
    diff = num_colors - uv.shape[0]
    u = np.random.uniform(low=0.0, high=1.0, size=diff)
    v = np.random.uniform(low=0.0, high=1.0, size=diff)
    extra = np.column_stack((u, v))
    uv = np.concatenate((uv, extra), axis=0)

# 设置顶点的uv坐标（color视为索引，再从`uv`中提取元素作为坐标）
num_vertices = mesh.vertices.shape[0]
uv_coords = np.zeros((num_vertices, 2))
for i in range(num_vertices):
    assert i in coloring
    color = coloring[i]
    uv_coords[i] = uv[color]

# 设置mesh的uv坐标和贴图
mesh.visual = trimesh.visual.texture.TextureVisuals(uv=uv_coords, image=texture)