细分和三角化多边形

Question

我得到一个随机轮廓作为输入。我需要将其转换为多边形并以 3d space 显示。 (A)

一般情况下，我会通过标准的剪耳算法来实现，结果会是这样的 (B)

但是由于我正在使用的视频卡 (VIVANTE GC 2000) 的图形驱动程序中存在错误，我只能对这样的小形状进行三角剖分。原因是在渲染时，如果网格的顶点位于平截头体的左侧或右侧太远 - 位置计算不正确。这会导致屏幕上大网格的剧烈闪烁和变形。这是一个已确认的驱动程序问题，它不会发生在其他平台上，甚至不会发生在同一显卡的旧版本驱动程序上。不幸的是，我不能使用旧的驱动程序，而且卡制造商不太可能修复这个错误，因为它已经为人所知将近十年了。

这里有一个相关的 SO 线程更深入地讨论了这个问题

所以我不得不用拐杖。换句话说 - 我必须将我的网格分成几个较小的三角形，比如 (C) 这样在任何时间点，渲染的三角形的顶点都不会在截锥之外太远。

不幸的是，除此之外我真的没有办法做到这一点。我知道这是一个非常不优雅的解决方案，但确实没有其他方法可以解决驱动程序错误。

但我坚持不懈地去做。不知何故，我不知道应该如何生成三角数据 (A -> C)。有人可以用这种方式帮助我 splitting/triangulating 网格算法或提供想法吗？假设所有的“方块”都是N×N的方块，N是我指定的。

或者有人对我如何处理这个问题有其他建议。

Answer 1

我想你可以考虑在有了 B 之后继续细分每个三角形，如下所示：

根据需要细分：

Answer 2

所以，我成功了。

想法大纲：

画轮廓
为其计算横跨 X 和 Y 的二等分线（可以是多条线
将初始轮廓细分为“切片”，在某些 Y 坐标上将其一分为二
遍历每个切片并在特定 X 坐标上拆分其边缘。
对每个生成的子网格进行三角剖分。

我还确保跟踪独特的矢量（因为我最终在分界线上得到了双倍的顶点）。这也有助于我以后更轻松地创建顶点数组。

这里有几个链接：

细分非凸轮廓：https://geidav.wordpress.com/2015/03/21/splitting-an-arbitrary-polygon-by-a-line/
剪耳三角：https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

我的代码（有点乱，打算重构一下，但另一方面是一体机）

public TriangulationOutput triangulateSubdivide(List<Vector2f> contour)
    {
        // clear lists and reset variables
        input.clear();
        polygonVerts.clear();;
        convexVerts.clear();
        reflexVerts.clear();
        straightVerts.clear();
        earVerts.clear();
        canBeEars.clear();
        corner = null;
        uniqueVectors.clear();

        List<Triangle>  result = new ArrayList<>();

        // Reverse the order of verts if the list is clockwise
        if (isClockwise(contour))
        {
            Collections.reverse(contour);
        }

        // find leftmost and topmost points in the
        Vector2f top = contour.get(0);
        Vector2f left = contour.get(0);
        Vector2f bottom = contour.get(0);
        Vector2f right = contour.get(0);
        for (int i = 1; i < contour.size(); i++)
        {
            Vector2f current = contour.get(i);
            if (current.y > top.y)
                top = current;
            if (current.y < bottom.y)
                bottom = current;
            if (current.x < left.x)
                left = current;
            if (current.x > right.x)
                right = current;
        }

        // check if the entire mesh fits within the space
        if ((Math.abs(top.y - bottom.y) <= GlobalSettings.OPT_MAX_DISTANCE)&&(Math.abs(right.x - left.x) <= GlobalSettings.OPT_MAX_DISTANCE))
        {
            // I haven't tested this edge case yet, but it's not really relevant to the algorythm
            System.err.println("TriangulateSubdivide -> shortcut used");
            return new TriangulationOutput(triangulateSimple(contour), contour);
            //TODO: Could be trouble
        }

        //Find X and Y split coordinates
        List<Float> linesY = new ArrayList<>();
        float lineCoord = ((float)((int)(top.y / GlobalSettings.OPT_MAX_DISTANCE))) * GlobalSettings.OPT_MAX_DISTANCE;
        while (lineCoord > bottom.y)
        {
            linesY.add(lineCoord);
            lineCoord -= GlobalSettings.OPT_MAX_DISTANCE;
        }

        List<Float> linesX = new ArrayList<>();
        lineCoord = ((float)((int)(right.x / GlobalSettings.OPT_MAX_DISTANCE))) * GlobalSettings.OPT_MAX_DISTANCE;
        while (lineCoord > left.x)
        {
            linesX.add(lineCoord);
            lineCoord -= GlobalSettings.OPT_MAX_DISTANCE;
        }

        List<List<Vector2f>> submeshes = new ArrayList<>();
        List<Vector2f> contourCpy = new ArrayList<>();
        contourCpy.addAll(contour);
        
        for (int i = 0; i < linesY.size(); i++)
        {
            List<Vector2f> submesh;
            List<Vector2f> intersections = new ArrayList<>();

            float yCoord = linesY.get(i);

            // split polygon edges on dividing horizontal lines
            // store found intersections to find them easier later
            for (int j = 0; j < contourCpy.size(); j++)
            {
                Vector2f current = contourCpy.get(j);
                int index = (j - 1) < 0 ? contourCpy.size()-1 : (j - 1);
                Vector2f previous = contourCpy.get(index);
                index = (j + 1) >= contourCpy.size() ? 0 : (j + 1);
                Vector2f next = contourCpy.get(index);

                // determines on which side of the line vertexes lie, or if they lie directly on it
                VertexStatus vsCurrent = new VertexStatus(current, yCoord, true);
                VertexStatus vsNext = new VertexStatus(next, yCoord, true);
                VertexStatus vsPrevious = new VertexStatus(previous, yCoord, true);

                if (vsPrevious.isOn() && vsCurrent.isOn() && vsNext.isOn())
                {
                    // adjacient edges lie completely on the line
                    continue;
                }

                if (vsCurrent.isOn())
                {
                    // add point if it lies on the line
                    intersections.add(current);
                }
                else if ((vsCurrent.status() != vsNext.status()) && (!vsNext.isOn()))
                {
                    // line intersects current edge in a point other than vertexes
                    float x = current.x + ((yCoord - current.y)*(next.x - current.x)) / (next.y - current.y);
                    Vector2f ip = new Vector2f(x, yCoord);
                    intersections.add(ip);
                    contourCpy.add(index, ip);       //TODO: possible trouble at last node
                    j++;    //increment to skip the point we just added
                }
            }

            //sort intersections
            intersections.sort(new Comparator<Vector2f>()
            {
                @Override
                public int compare(Vector2f v1, Vector2f v2)
                {
                    return (v1.x < v2.x) ? -1 : 1;
                }
            });

            // find submeshes that lie above the line. Every two intersections 
            for (int j = 0; j < intersections.size(); j+=2)
            {
                // for every two points we find a linked submesh
                submesh = new ArrayList<>();

                int indexEnd = contourCpy.indexOf(intersections.get(j));
                int indexStart = contourCpy.indexOf(intersections.get(j+1));

                int index = indexStart;
                boolean cont = true;
                while (contourCpy.size() > 0)
                {

                    submesh.add(contourCpy.get(index));

                    if (index == indexEnd)
                    {
                        break;
                    }

                    if ((index != indexStart))
                    {
                        // remove points between intersections from future countour
                        contourCpy.remove(index);

                        if (index < indexEnd)
                        {
                            indexEnd--;
                        }
                    }
                    else
                    {
                        index++;
                    }

                    if (index >= contourCpy.size())
                    {
                        index = 0;
                    }
                }
                //while (index != indexEnd);

                submeshes.add(submesh);
            }
        }

        // add the remaining contour as final bottom-most mesh
        submeshes.add(contourCpy);
        
        for (List<Vector2f> submesh : submeshes)
        {
            // Add more vertexes for X coord divisions
            for (int i = 0; i < submesh.size(); i++)
            {
                Vector2f current = submesh.get(i);

                // add current vector to unique
                boolean add = true;
                for (int v = 0; v < uniqueVectors.size(); v++)
                {
                    if (uniqueVectors.get(v).equals(current))
                    {
                        add = false;
                        break;
                    }
                }
                if (add)
                {
                    uniqueVectors.add(current);
                }

                int index = (i + 1) >= submesh.size() ? 0 : (i + 1);
                Vector2f next = submesh.get(index);

                for (int j = 0; j < linesX.size(); j++)
                {
                    float xCoord = linesX.get(j);
                    VertexStatus vsCurrent = new VertexStatus(current, xCoord, false);
                    VertexStatus vsNext = new VertexStatus(next, xCoord, false);

                    if (vsCurrent.isOn() || vsNext.isOn())
                    {
                        continue;
                    }

                    if (vsCurrent.status() != vsNext.status())
                    {
                        // vectors lie on different sides of xCoord
                        float y = current.y + ((next.y - current.y)*(xCoord - current.x)) / (next.x - current.x);
                        Vector2f ip = new Vector2f(xCoord, y);
                        // add current vector to unique
                        add = true;
                        for (int v = 0; v < uniqueVectors.size(); v++)
                        {
                            if (uniqueVectors.get(v).equals(ip))
                            {
                                ip = uniqueVectors.get(v);
                                add = false;
                                break;
                            }
                        }
                        if (add)
                        {
                            uniqueVectors.add(ip);
                        }
                        submesh.add(index,ip);

                        //TODO: possible trouble here
                        if (current.x > next.x)
                        {
                            index++;
                        }
                        i++;
                    }
                }
            }

            result.addAll(triangulateSimple(submesh));
        }

        // this basically just stores triangles and a list of vertexes and doesn't do anything else.
        return new TriangulationOutput(result, uniqueVectors);
    }

细分和三角化多边形

Subdividing and triangulating a polygon

opengl-es

mesh

triangulation