barycentric coordinates using quads

Question

Hi everyone, some of you know how fill a quads in 2D using barycentric coordinates?At the present, I'm splitting the quads into 2 triangles, but that way is inefficient because I have to iterate over the second bounding box which repeats pixel that were filled previously (by example, to fill the 2nd triangle I traversed the 1st triangle that belongs at bounding box formed by 2nd triangle) Thanks

esmitt

Answer 1

Here is a python example that should be what you're looking for. As you probably know there are no uniquely defined barycentric coordinates for quads in two dimension (there are barycentric coordinates for tetrahedra in three dimensions, but that's another thing).

import sys

def fill(xa, ya, xb, yb, xc, yc, xd, yd):
    abx = yb - ya
    aby = xa - xb
    kab = - (xa*abx + ya*aby)

    bcx = yc - yb
    bcy = xb - xc
    kbc = - (xb*bcx + yb*bcy)

    cdx = yd - yc
    cdy = xc - xd
    kcd = - (xc*cdx + yc*cdy)

    dax = ya - yd
    day = xd - xa
    kda = - (xd*dax + yd*day)

    for y in xrange(25):
        for x in xrange(79):
            if (x*abx + y*aby + kab >= 0 and
                x*bcx + y*bcy + kbc >= 0 and
                x*cdx + y*cdy + kcd >= 0 and
                x*dax + y*day + kda >= 0):
                sys.stdout.write('+')
            else:
                sys.stdout.write('-')
        sys.stdout.write('\n')

fill( 10, 5,
      6, 22,
      60, 17,
      70, 9 )

Basically I'm computing the line coefficients for every edge and then check if the point is on the correct side of each of them. The line coefficients are not normalized because if you only want an hit/miss test that is not needed (you will only check the sign and not the magnitude of x*nx + y*ny + nk).

Note that this approach requires convex oriented quads ...