Triangle.NET

Question

我已经查看了似乎每个问题和资源，Triangle.NET 试图找到如何将顶点插入现有三角剖分的答案。我得到的最接近的是 Traingle.Net 的讨论档案，有人问了类似的问题（讨论 ID 632458），但不幸的是，答案不是我要找的.

我的目标是在 Unity 中制作一堵可破坏的墙，当玩家射击墙时，它会在墙上创建一个洞（就像在彩虹六号围攻中一样）。

这是我为最初的实现所做的：

使用墙的四个角创建初始三角测量。
当玩家射击时，执行光线投射，如果光线投射与墙壁相交，则将交点添加到多边形变量并使用该变量重新三角化整个网格。
在墙上绘制新的三角剖分作为纹理以可视化正在发生的事情。
重复。

如您所见，第 2 步是问题所在。

因为每次玩家撞墙时我都会重新对整个网格进行三角剖分，所以玩家撞墙的次数越多，随着顶点数量的增加，三角剖分的速度就越慢。我想这可能没问题，但我希望可破坏的墙壁在我的游戏中扮演重要角色，所以这是不可接受的。

因此，通过挖掘 Triangle.Net 源代码，我找到了一个名为 InsertVertex 的内部方法。此方法的摘要指出：

Insert a vertex into a Delaunay triangulation, performing flips as necessary to maintain the Delaunay property.

这意味着我不必在玩家每次射击时都重新进行三角测量！

所以我开始实施这个方法，但是...它不起作用。我收到如下错误：

NullReferenceException: Object reference not set to an instance of an object TriangleNet.TriangleLocator.PreciseLocate (TriangleNet.Geometry.Point searchpoint, TriangleNet.Topology.Otri& searchtri, System.Boolean stopatsubsegment) (at Assets/Triangle.NET/TriangleLocator.cs:146)

我已经被这个问题卡住了天，我一辈子都解决不了！如果任何对 Triangle.NET 库有足够了解的人愿意帮助我，我将不胜感激！除此之外，如果我正在使用的实现或库有更好的替代方案（出于我上面概述的目的），那也很棒！

目前，我设置场景的方式非常简单，我只有一个四边形，我将其放大并将下面的脚本作为组件添加到其中。然后我将该组件链接到附加到主相机的拍摄光线投射脚本：

How the scene is setup.

What it looks like in Play Mode.

我克隆的确切 Triangle.Net 回购是 this one。

我的代码贴在下面：

using UnityEngine;
using TriangleNet.Geometry;
using TriangleNet.Topology;
using TriangleNet.Meshing;

public class Delaunay : MonoBehaviour
{
    [SerializeField]
    private int randomPoints = 150;
    [SerializeField]
    private int width = 512;
    [SerializeField]
    private int height = 512;

    private TriangleNet.Mesh mesh;
    Polygon polygon = new Polygon();

    Otri otri = default(Otri);
    Osub osub = default(Osub);

    ConstraintOptions constraintOptions = new ConstraintOptions() { ConformingDelaunay = true };
    QualityOptions qualityOptions = new QualityOptions() { MinimumAngle = 25 };

    void Start()
    {
        osub.seg = null;

        Mesh objMesh = GetComponent<MeshFilter>().mesh;

        // Add four corners of wall (quad in this case) to polygon.
        //foreach (Vector3 vert in objMesh.vertices)
        //{
        //    Vector2 temp = new Vector2();
        //    temp.x = map(vert.x, -0.5f, 0.5f, 0, 512);
        //    temp.y = map(vert.y, -0.5f, 0.5f, 0, 512);
        //    polygon.Add(new Vertex(temp.x, temp.y));
        //}

        // Generate random points and add to polygon.
        for (int i = 0; i < randomPoints; i++)
        {
            polygon.Add(new Vertex(Random.Range(0.0f, width), Random.Range(0.0f, height)));
        }

        // Triangulate polygon.
        delaunayTriangulation();
    }

    // When left click is pressed, a raycast is sent out. If that raycast hits the wall, updatePoints() is called and is passed in the location of the hit (hit.point).
    public void updatePoints(Vector3 pos)
    {
        // Convert pos to local coords of wall.
        pos = transform.InverseTransformPoint(pos);
        Vertex newVert = new Vertex(pos.x, pos.y);

        //// Give new vertex a unique id.
        //if (mesh != null)
        //{
        //    newVert.id = mesh.NumberOfInputPoints;
        //}

        // Insert new vertex into existing triangulation.
        otri.tri = mesh.dummytri;
        mesh.InsertVertex(newVert, ref otri, ref osub, false, false);

        // Draw result as a texture onto the wall so to visualise what is happening.
        draw();
    }

    private void delaunayTriangulation()
    {
        mesh = (TriangleNet.Mesh)polygon.Triangulate(constraintOptions, qualityOptions);
        draw();
    }

    void draw()
    {
        Texture2D tx = new Texture2D(width, height);

        // Draw triangulation.
        if (mesh.Edges != null)
        {
            foreach (Edge edge in mesh.Edges)
            {
                Vertex v0 = mesh.vertices[edge.P0];
                Vertex v1 = mesh.vertices[edge.P1];

                DrawLine(new Vector2((float)v0.x, (float)v0.y), new Vector2((float)v1.x, (float)v1.y), tx, Color.black);
            }
        }

        tx.Apply();
        this.GetComponent<Renderer>().sharedMaterial.mainTexture = tx;
    }

    // Bresenham line algorithm
    private void DrawLine(Vector2 p0, Vector2 p1, Texture2D tx, Color c, int offset = 0)
    {
        int x0 = (int)p0.x;
        int y0 = (int)p0.y;
        int x1 = (int)p1.x;
        int y1 = (int)p1.y;

        int dx = Mathf.Abs(x1 - x0);
        int dy = Mathf.Abs(y1 - y0);
        int sx = x0 < x1 ? 1 : -1;
        int sy = y0 < y1 ? 1 : -1;
        int err = dx - dy;

        while (true)
        {
            tx.SetPixel(x0 + offset, y0 + offset, c);

            if (x0 == x1 && y0 == y1) break;
            int e2 = 2 * err;
            if (e2 > -dy)
            {
                err -= dy;
                x0 += sx;
            }
            if (e2 < dx)
            {
                err += dx;
                y0 += sy;
            }
        }
    }

    private float map(float from, float fromMin, float fromMax, float toMin, float toMax)
    {
        float fromAbs = from - fromMin;
        float fromMaxAbs = fromMax - fromMin;

        float normal = fromAbs / fromMaxAbs;

        float toMaxAbs = toMax - toMin;
        float toAbs = toMaxAbs * normal;

        float to = toAbs + toMin;

        return to;
    }
}

Answer 1

好消息！我已经设法解决了这个问题。 InsertVertex() 实际上并没有将新顶点添加到顶点列表中！所以这意味着当它尝试三角测量时，它试图指向新的顶点但它不能（因为该顶点不在列表中）。因此，为了解决这个问题，我只是手动将我的新顶点添加到网格中的顶点列表中，在调用InsertVertex() 之前。注意：执行此操作时，还需要手动设置顶点的 id。我将 id 设置为顶点列表的大小，因为我将所有新顶点添加到列表的末尾。

// When left click is pressed, a raycast is sent out. If that raycast hits the wall, updatePoints() is called and is passed in the location of the hit (hit.point).
public void updatePoints(Vector3 pos)
{
    // Convert pos to local coords of wall. You don't need to do this, i do it because of my draw() method where i map everything out onto a texture and display it.
    pos = transform.InverseTransformPoint(pos);
    pos.x = map(pos.x, -0.5f, 0.5f, 0, 512);
    pos.y = map(pos.y, -0.5f, 0.5f, 0, 512);
    Vertex newVert = new Vertex(pos.x, pos.y);

    // Manually add new vertex to list of vertices.
    newVert.id = mesh.vertices.Count;
    mesh.vertices.Add(newVert.id, newVert);

    //Doing just the first line gave me a null pointer exception. Adding the two extra lines below it fixed it for me.
    otri.tri = mesh.dummytri;
    otri.orient = 0;
    otri.Sym();

    // Insert new vertex into existing triangulation.
    mesh.InsertVertex(newVert, ref otri, ref osub, false, false);

    // Draw result as a texture onto the wall so to visualise what is happening.
    draw();
}

希望这对完成道路的人有所帮助！

Triangle.NET - 如何将顶点添加到现有三角剖分？

Triangle.NET - How to add vertex to existing triangulation?

c#

unity3d

triangulation

delaunay