0
\$\begingroup\$

So I am trying to draw and fill a triangle on the screen using the barycentric method, but my barycentric implementation seems to be outputting outside triangle coordinates, why?

#include <iostream>
#include <cmath>
using namespace std;
double triarea(double a, double b, double c)
{
    double s = (a + b + c)/2.0;
    double area=sqrt(fabs(s*(s-a)*(s-b)*(s-c)));
    return area;
}

// compute the distance between two 2d points
double dist(double x0, double y0, double x1, double y1)
{
    double a = x1 - x0;
    double b = y1 - y0;
 
    return sqrt(a*a + b*b);
}
double returnMax(double A, double B, double C)
{
    return (A > B ? A : B) > C ? (A > B ? A : B) : C;
}
double returnMin(double A, double B, double C)
{
    return (A > B ? B : A) > C ? C : (A > B ? B : A);
}
double barycentric(double x0, double y0, double x1, double y1, double x2, double y2, double px, double py)
{
    double a = dist(x0, y0, x1, y1);
    double b = dist(x1, y1, x2, y2);
    double c = dist(x2, y2, x0, y0);
    
    double ABC= triarea(a, b, c);
    
    double pa = dist(x0, y0, px, py);
    double pb = dist(px, py, x2, y2);
    double pc = dist(x2, y2, x0, y0);
    double PAB= triarea(pa, pb, pc);
     
    double paa = dist(x1, y1, px, py);
    double pbb = dist(px, py, x2, y2);
    double pcc = dist(x2, y2, x1, y1);
    double PBA= triarea(paa, pbb, pcc);
     
    double inorout = 1 - (PAB/(double)ABC) - (PBA/(double)ABC);
    
    return inorout;
}
void drawtriangle(double x0, double y0, double x1, double y1, double x2, double y2)
{
    double maxx = returnMax(x0, x1, x2);
    double minx = returnMin(x0, x1, x2);
    
    double maxy = returnMax(y0, y1, y2);
    double miny = returnMin(y0, y1, y2);
    
    for(double x = minx; x < maxx; x++)
    {
        for(double y = miny; y < maxy; y++)
        {
            if(barycentric(x0,y0, x1,y1, x2,y2, x,y) >= 0)
            {
                //draw pixel
                cout <<  "(" << x << "," << y << ")" << endl;
            }
        }
    }
    
}
int main()
{
   drawtriangle(-5,-5,10,30,20,5);
    return 0;
}
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

It looks to me like you've taken a Barycentric coordinate function designed for determining the coordinates of a point known to be inside the triangle.

It does not account for the way the sign of the area flips when the point exits the triangle, inverting the winding, and it does not check whether areas PAB or PBA (really CAP and BCP) are negative, only the third triangle ABP. So it's not suitable for determining the barycentric coordinates of a point that could be outside the triangle.

It's also a very wasteful method, repeatedly computing distances and areas that are constant for the whole triangle, with all the expensive square rooting and divisions that entails.

If you just want a binary yes/no answer as to whether a point is inside a triangle, you can do that by checking its winding instead.

bool isInsideTriangle(double ax, double ay, double bx, double by, double cx, double cy, double px, double py)
{
    if ((bx - ax) * (px - by) - (by - ay) * (px - bx) < 0) return false;
    if ((cx - bx) * (px - cy) - (cy - by) * (px - cx) < 0) return false;
    if ((ax - cx) * (px - ay) - (ay - cy) * (px - ax) < 0) return false;

    return true;
}

Reverse the sign checks if your front-facing triangles are wound the opposite way.

What this does is compute the z component of the cross product of two edges of each triangle ABP, BCP, CAP. That component will be positive if the triangle winds in one direction, and negative if the triangle winds in the opposite direction. If the point P is inside the triangle ABC, all three sub-triangles wind the same way. As soon as P crosses an edge, one of the sub-triangles flips its winding.

No more square roots or divisions, and with a little elbow grease you could probably vectorize this calculation so you check all three failure cases in parallel.

\$\endgroup\$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .