https://github.com/dgreenheck/OpenFracture

概要

提供了比较完善的mesh切分算法，不过切分方式比较单一
好处是可以渐进式切分，异步不断一刀一刀切
不用一次性生成一大堆碎片导致卡顿

大致算法:

1
2
3
4
5
6
7
8
mesh入队
while(碎片数量<指定数量)
{
    取出队头mesh
    Slice(mesh)=> A,B
    A,B入队
}
Slice

一些算法细节

Slice

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public static void Slice(FragmentData meshData,
                         Vector3 sliceNormal,
                         Vector3 sliceOrigin,
                         Vector2 textureScale,
                         Vector2 textureOffset,
                         out FragmentData topSlice,
                         out FragmentData bottomSlice)
{   
    topSlice = new FragmentData(meshData.vertexCount, meshData.triangleCount);
    bottomSlice = new FragmentData(meshData.vertexCount, meshData.triangleCount);

    //记录各个顶点位于哪个半面上，后续用于判断哪些三角形需要被切割
    bool[] side = new bool[meshData.vertexCount];

    //遍历非cut顶点，判断半面，加入到对应数据结构中(top/bottom)
    for (int i = 0; i < meshData.Vertices.Count; i++)
    {
        var vertex = meshData.Vertices[i];
        side[i] = vertex.position.IsAbovePlane(sliceNormal, sliceOrigin);
        var slice = side[i] ? topSlice : bottomSlice;
        slice.AddMappedVertex(vertex, i);
    }

    //遍历cut顶点，判断半面，加入到对应数据结构中(top/bottom)
    int offset = meshData.Vertices.Count;
    for (int i = 0; i < meshData.CutVertices.Count; i++)
    {
        var vertex = meshData.CutVertices[i];
        side[i + offset] = vertex.position.IsAbovePlane(sliceNormal, sliceOrigin);
        var slice = side[i + offset] ? topSlice : bottomSlice;
        slice.AddMappedVertex(vertex, i + offset);
    }

    //切分三角(mesh)
    SplitTriangles(meshData, topSlice, bottomSlice, sliceNormal, sliceOrigin, side, SlicedMeshSubmesh.Default);
    //切分三角(subMesh)
    SplitTriangles(meshData, topSlice, bottomSlice, sliceNormal, sliceOrigin, side, SlicedMeshSubmesh.CutFace);

    //填充切面
    FillCutFaces(topSlice, bottomSlice, -sliceNormal, textureScale, textureOffset);
}

meshData:

  • sliceNormal : 切割方向
  • sliceOrigin : 切割原点
  • textureScale : 纹理缩放比例
  • textureOffset : 纹理偏移
  • topSlice : 切分后的上半部分数据
  • bottomSlice : 切分后的下半部分数据
  • FragmentData 切割过程中的辅助数据结构，用于存放Mesh数据

new FragmentData(meshData.vertexCount, meshData.triangleCount);

初始化的时候直接传入顶点数和三角数，避免resize 和GC

切分三角

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
private static void SplitTriangles(FragmentData meshData,
                                   FragmentData topSlice,
                                   FragmentData bottomSlice,
                                   Vector3 sliceNormal,
                                   Vector3 sliceOrigin,
                                   bool[] side,
                                   SlicedMeshSubmesh subMesh)
{
    int[] triangles = meshData.GetTriangles((int)subMesh);
    int a, b, c;
    for (int i = 0; i < triangles.Length; i += 3)
    {
        // Get vertex indexes for this triangle
        a = triangles[i];
        b = triangles[i + 1];
        c = triangles[i + 2];

        //之前判断了所有顶点位于的面位置
        //所有可以直接根据这个判断在上半面
        if (side[a] && side[b] && side[c])
        {
            topSlice.AddMappedTriangle(a, b, c, subMesh);
        }
        else if (!side[a] && !side[b] && !side[c])
        {
            bottomSlice.AddMappedTriangle(a, b, c, subMesh);
        }
        else
        {
            //三角形的顶点位于不同半平面上，故切分之
            //这三种是两个在上，一个在下
            if (side[b] && side[c] && !side[a])
            {
                SplitTriangle(b, c, a, sliceNormal, sliceOrigin, meshData, topSlice, bottomSlice, subMesh, true);
            }
            else if (side[c] && side[a] && !side[b])
            {
                SplitTriangle(c, a, b, sliceNormal, sliceOrigin, meshData, topSlice, bottomSlice, subMesh, true);
            }
            else if (side[a] && side[b] && !side[c])
            {
                SplitTriangle(a, b, c, sliceNormal, sliceOrigin, meshData, topSlice, bottomSlice, subMesh, true);
            }
            //这三种是两个在下，一个在上
            else if (!side[b] && !side[c] && side[a])
            {
                SplitTriangle(b, c, a, sliceNormal, sliceOrigin, meshData, topSlice, bottomSlice, subMesh, false);
            }
            else if (!side[c] && !side[a] && side[b])
            {
                SplitTriangle(c, a, b, sliceNormal, sliceOrigin, meshData, topSlice, bottomSlice, subMesh, false);
            }
            else if (!side[a] && !side[b] && side[c])
            {
                SplitTriangle(a, b, c, sliceNormal, sliceOrigin, meshData, topSlice, bottomSlice, subMesh, false);
            }
        }
    }
}

v3BelowCutPlane从来标记两种情况
即单独顶点v3处于法线方向还是背向法线方向

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
private static void SplitTriangle(int v1_idx,
                                  int v2_idx,
                                  int v3_idx,
                                  Vector3 sliceNormal,
                                  Vector3 sliceOrigin,
                                  FragmentData meshData,
                                  FragmentData topSlice,
                                  FragmentData bottomSlice,
                                  SlicedMeshSubmesh subMesh,
                                  bool v3BelowCutPlane)       
    // v3BelowCutPlane = true
    // ======================
    //                                
    //     v1 *_____________* v2   .
    //         \           /      /|\  cutNormal
    //          \         /        |
    //       ----*-------*---------*--
    //        v13 \     /  v23       cutOrigin
    //             \   /
    //              \ /
    //               *  v3         triangle normal out of screen                                                                                  
    //    
    // v3BelowCutPlane = false
    // =======================
    //
    //               *  v3         .                                             
    //              / \           /|\  cutNormal  
    //         v23 /   \ v13       |                    
    //       -----*-----*----------*--
    //           /       \         cut origin                                
    //          /         \                                                                  
    //      v2 *___________* v1    triangle normal out of screen

这里对于法线和UV的处理(等比例划分 s13/s23是切分线段的比例)

1
2
3
4
var norm13 = (v1.normal + s13 * (v3.normal - v1.normal)).normalized;
var norm23 = (v2.normal + s23 * (v3.normal - v2.normal)).normalized;
var uv13 = v1.uv + s13 * (v3.uv - v1.uv);
var uv23 = v2.uv + s23 * (v3.uv - v2.uv);

Q:为何要分上下平面?
A 因为要分内外表面(法线方向)，并根据这个生成正确的三角形序列(环绕方向，逆时针为正)

填充切面

此处针对上下半平面，顶点和三角数据只需要计算一次，法线相反即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
private static void FillCutFaces(FragmentData topSlice,
                                 FragmentData bottomSlice,
                                 Vector3 sliceNormal,
                                 Vector2 textureScale,
                                 Vector2 textureOffset)
{
    //遍历所有切分顶点(切分过程中生成的新顶点) 位置相同的就合并之
    topSlice.WeldCutFaceVertices();

    if (topSlice.CutVertices.Count < 3) return;

    //三角化
    var triangulator = new ConstrainedTriangulator(topSlice.CutVertices, topSlice.Constraints, sliceNormal);
    int[] triangles = triangulator.Triangulate();

    //处理UV和法线
    //对于上下半平面，UV一致，法线相反
    for (int i = 0; i < topSlice.CutVertices.Count; i++)
    {
        var vertex = topSlice.CutVertices[i];
        var point = triangulator.points[i];

        Vector2 uv = new Vector2(
            (triangulator.normalizationScaleFactor * point.coords.x) * textureScale.x + textureOffset.x,
            (triangulator.normalizationScaleFactor * point.coords.y) * textureScale.y + textureOffset.y);

        var topVertex = vertex;
        topVertex.normal = sliceNormal;
        topVertex.uv = uv;

        var bottomVertex = vertex;
        bottomVertex.normal = -sliceNormal;
        bottomVertex.uv = uv;

        topSlice.CutVertices[i] = topVertex;
        bottomSlice.CutVertices[i] = bottomVertex;
    }

    //为上下半平面填充三角形
    int offsetTop = topSlice.Vertices.Count;
    int offsetBottom = bottomSlice.Vertices.Count;
    for (int i = 0; i < triangles.Length; i += 3)
    {
        topSlice.AddTriangle(
            offsetTop + triangles[i],
            offsetTop + triangles[i + 1],
            offsetTop + triangles[i + 2],
            SlicedMeshSubmesh.CutFace);

        bottomSlice.AddTriangle(
            offsetBottom + triangles[i],
            offsetBottom + triangles[i + 2], // Swap two vertices so triangles are wound CW
            offsetBottom + triangles[i + 1],
            SlicedMeshSubmesh.CutFace);
    }
}

三角化

1
2
3
4
5
//1. 
var triangulator = new ConstrainedTriangulator(topSlice.CutVertices, topSlice.Constraints, sliceNormal);

//2.
int[] triangles = triangulator.Triangulate();

1中，会根据切分平面建立2维坐标系(因为是一刀切的，所以所有点都在一个平面上)

1
2
3
4
5
6
7
8
9
10
11
12
//叉乘找到基向量
Vector3 e1 = (inputPoints[0].position - inputPoints[1].position).normalized;
Vector3 e2 = normal.normalized;
Vector3 e3 = Vector3.Cross(e1, e2).normalized;

for (int i = 0; i < N; i++)
{
    //投影到二维平面上，找到对应的coords
    var position = inputPoints[i].position;
    var coords = new Vector2(Vector3.Dot(position, e1), Vector3.Dot(position, e3));
    this.points[i] = new TriangulationPoint(i, coords);
}

2中是真正的三角化步骤，这里是用这篇论文提供的CDT算法，这里略过:

[1] Sloan, Scott W. “A fast algorithm for generating constrained Delaunay triangulations.” Computers & Structures 47.3 (1993): 441-450.

其他一些数学相关操作

  1. 判断线面相交:
  • a,b: 线段
  • n : 平面法线
  • p0 : 平面原点
    输出:
  • bool : 是否发生穿插
  • x : 交点
  • s : 切分线段比例 (即:x = a+ (b-a) * s )

此处根据(p0->a)和(b-a)投影比例判断是否穿插
(如果穿插，则s位于[0,1]之间)
(这里平面为无限平面)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static bool LinePlaneIntersection(Vector3 a,
                                         Vector3 b,
                                         Vector3 n,
                                         Vector3 p0,
                                         out Vector3 x,
                                         out float s)
{
    // Initialize out params
    s = 0;
    x = Vector3.zero;

    // Handle degenerate cases
    if (a == b)
    {
        return false;
    }
    else if (n == Vector3.zero)
    {
        return false;
    }

    s = Vector3.Dot(p0 - a, n) / Vector3.Dot(b - a, n);

    if (s >= 0 && s <= 1)
    {
        x = a + (b - a) * s;
        return true;
    }

    return false;
}
  1. 判断是否在某个面上方(法线方向):
  • p : 要判断的顶点
  • n : 法线方向
  • o : 平面原点位置

这里实际上就是用向量方向和法线方向做了一次内积

1
2
3
4
public static bool IsAbovePlane(this Vector3 p, Vector3 n, Vector3 o)
{
    return (n.x * (p.x - o.x) + n.y * (p.y - o.y) + n.z * (p.z - o.z)) >= 0;
}