Subdividing and triangulating a polygon

Question

I get a random contour as an input. I need to transform it into a polygon and display it in 3d space. (A)

Normally, I would do it through a standard ear-clipping algorithm, and the result will be something like (B)

However due to a bug in the graphics drivers for the video card I'm working on (VIVANTE GC 2000), I can only triangulate small shapes like that. The reason is that when rendering, if a vertex of a mesh lies too far outside of frustum to the left or right - the position is calculated incorrectly. This results in wild flickering and deformation of large meshes on the screen. It is a confirmed driver issue, and it doesn't happen on other platforms or even with the older version of drivers for the same videocard. Unfortunately, I can't use the old drivers, and the card manufacturer isn't likely to fix the bug, seeing it's been known for almost a decade.

Here's a relates SO thread going a bit more in-depth of the problem OpenGL Perspective Projection Clipping Polygon with Vertex Outside Frustum = Wrong texture mapping?

So I have to use crutches. In other words - I have to split my mesh into several smaller triangles, something like (C) So that at any point in time, the vertexes of the triangles rendered are not outside of frustum too far.

Unfortunately, there's really no way to do it otherwise that I see. I know this is a very inelegant solution, but there really no other way to get around the driver bug.

But I'm stuck at actually doing it. Somehow, I can't wrap my head around how I should generate the triangulated data (A -> C). Can someone help me with an algorithm of splitting/triangulating mesh in such a way or give ideas? Assume that all "squares" are N-by-N squares with N being specified by me.

Or maybe someone has some other suggestions how I could deal with the problem.

Jordi Cruzado · Answer 1 · 2020-06-23T07:02:09.223

2

I guess you could consider to continue subdividing each one of the triangles once you have B, like this:

as many subdivisions as needed:

edited Jun 23 '20 at 07:02

answered Jun 23 '20 at 06:09

Jordi Cruzado

875
6
13

I did consider that, actually. But this results in more triangles than the C example that I provided, and I would rather have less than more, considering it's an ARM device. Thanks for the tip, though! Any such idea is valuable because I may not have thought of that. =) – Vlad Vyatkin Jun 23 '20 at 06:43
This other kind of subdivision (I have edited my response) allows you to subdivide only those triangles that are out of the frustum and let without subdivision those that are correct. You will have less triangles at the end – Jordi Cruzado Jun 23 '20 at 07:03
I don't think it would be effective to constantly changing the mesh composition based on what parts of it fall outside of frustum as the user rotates the camera... – Vlad Vyatkin Jun 23 '20 at 07:51
I was not thinking about to do it dynamically, but considering a kind of threshold for triangle edge length and subdivide accordingly. Anyway I am not aware of the details. It was just an idea. I guess that the C solution is not as easy as it could seem. – Jordi Cruzado Jun 23 '20 at 08:02
It's not, that's why I created that topic =D. Thanks for your ideas anyway, I appreciate it. – Vlad Vyatkin Jun 23 '20 at 08:08

score 2 · Accepted Answer · answered Jun 26 '20 at 11:07

So, I made it work.

Idea outline:

take a contour
calculate bissecting lines across X and Y for it (could be many lines
subdivide initial contour into "slices", bissecting it on certain Y coordinates
go through each slice and split its edges on certain X coordinates.
triangulate each of the resulting submeshes.

I also ensure to keep track of unique vectors (because I end up with doubles for vertexes on the dividing lines). This also helps me to later easier create vertex array.

Here's a few links:

Subdividing a non-convex contour: https://geidav.wordpress.com/2015/03/21/splitting-an-arbitrary-polygon-by-a-line/
Ear-clipping triangulation: https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

My code (It's a bit messy, I'm planning to refactor it, but on the other hand it's all-in-one)

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

2 Answers2