using Subdiv2D to find quad problem

asked 2018-11-05 04:34:52 -0500

gino0717 gravatar image

updated 2018-11-05 04:37:48 -0500

berak gravatar image

I'm trying to make some free form deformation and some algorithms says they need quad instead of triangle. So I try to modify the triangle finding code copyied from somewhere into the quad one. I make a subclass

class MyDelauny : public Subdiv2D

and do something like:

    void fourVertex(vector<int> &triangleList) const
    {
        {
            vector<int> clean;
            triangleList.swap(clean);
        }
        int i, total = (int)(qedges.size() * 4);
        std::vector<bool> edgemask(total, false);

        const bool filterPoints = true;
        Rect2f rect(topLeft.x, topLeft.y, bottomRight.x - topLeft.x, bottomRight.y - topLeft.y);

        for (i = 4; i < total; i += 2)
        {
            if (edgemask[i])
                continue;
            Point2f a, b, c,d;
            int edge_a = i;
                int indexA = edgeOrg(edge_a, &a) - 4;

            if (filterPoints && !rect.contains(a))
                continue;
            int edge_b = getEdge(edge_a, NEXT_AROUND_LEFT);
            int indexB = edgeOrg(edge_b, &b) - 4;

            if (filterPoints && !rect.contains(b))
                continue;
            int edge_c = getEdge(edge_b, NEXT_AROUND_LEFT);
            int indexC = edgeOrg(edge_c, &c) - 4;

            if (filterPoints && !rect.contains(c))
                continue;

            int edge_d = getEdge(edge_a, NEXT_AROUND_RIGHT);
            int indexD = edgeOrg(edge_d, &d) - 4;;

            if (filterPoints && !rect.contains(d))
                continue;


            edgemask[edge_a] = true;
            edgemask[edge_b] = true;
            edgemask[edge_c] = true;
            edgemask[edge_d] = true;

            triangleList.push_back(indexA);
            triangleList.push_back(indexB);
            triangleList.push_back(indexC);
            triangleList.push_back(indexD);

        }
    }

Since I already can get the triangle form 2 NEXT_AROUND_LEFT (blue) , If I add another NEXT_AROUND_RIGHT (red) then I can get a quad.

image description

After outputting the vectors, I draw the points and link they together

image description

looks not bad but actually the quad drew twice becasue I just add an edge to a triangle.

I tried to record which vertex I have alread used and not to use it to find quad but it results in too few quad .

needs help for better ways to find quads.thanks a lot!

edit retag flag offensive close merge delete