Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

using Subdiv2D to find quad problem

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!

click to hide/show revision 2
None

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

berak gravatar image

using Subdiv2D to find quad problem

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:

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!