Hey guys, so I'm trying to create a quad renderer that renderers quads using 4 half space functions instead of rendering 2 triangles. I was previously following ryg's (https://fgiesen.wordpress.com/2013/02/10/optimizing-the-basic-rasterizer/) tutorial on triangle rasterization and he uses barycentric coordinates to interpolate values as well as see if the point is inside all of the edges. This works great for triangles but I know some people previously made quad rasterizers and I found this paper (http://geometry.caltech.edu/pubs/MHBD02.pdf) about generalized barycentric coordinates for n-sided polygons. Now this is my first ever attempt at understanding a mathematical paper so I'm probably not understanding a lot of basic principles here.

They use a couple variables, q1->qn are the vertices, Q is the polygon, p is a point inside the polygon and alpha1->alphan are the coefficients for each vertice (a percent saying how much percent of each vertex weight applies to that point), and w1->wn which is the actual weight. They have 3 properties that they are trying to gain in their generalized barycentric coords: affine combination, smoothness and convex combination.

For affine combination, the first summation is a bit confusing. They're saying if you sum all coefficients multiplied by the vertices then you get the point p but I'm not entirely sure what that is achieving. They're also saying all the coefficients add up to 1 which makes sense since the coefficients are percents so they have to reach a total of 100% or 1. After they state the properties, they then say you can rewrite the affine summations as the summation of each wj(qj - p) which equals to 0. Now I thought I'd do a example with a triangle and see if this works.

My vertices would be (0,0), (0.5, 1), (1, 0) with p being (0.5, 0.5) and my weights being 5, 4 and 3. Applying the formula I would get:

5(0.5 - 0.5, 1 - 0.5) + 4(0 - 0.5, 0 - 0.5) + 3(1 - 0.5, 0 - 0.5)

= (-0.5, -1)

First off, I don't get how the vector value is supposed to equal to 0 unless its the vector 0. Second, I don't get why this example doesn't work. Is there something wrong with the vertices I chose or am I missing some step in between? Thanks in advance.

The affine combination part means each vertex has a coefficient, you multiply all vertices with all the coefficients and sum the result. The coefficients themselves sum to 1. It's just a standard affine combination of points. The goal of this is to generate a point from a combination of the polygon vertices, as a way of mapping coefficients of a polygon to the space around the polygon.

I skimmed the paper and I'm pretty skeptical; if you have more edges than 3 for a 2D shape, I don't think you can guarantee a 1 to 1 mapping of coefficients to points in the polygon. This property is pretty much the entire reason barycentric coordinates are interesting, and you lose that once you have too many degrees of freedom. Maybe someone else will come along that actually reads it thoroughly, but to me it seems to be pretty lame. Additionally, modern hardware has built in functionality for dealing with triangles making the entire paper really useless for modern purposes. I hate to give you such a lame suggestion but: you are probably better off studying a better paper.

I hope this helps!

Hmm, im going to read up on affine math, I've never actually learned it, the most I know about it is from ryg's tutorials on barycentric coordinates but thats really rough. Thanks for the affine combination term, will help me figure all of this out.

The paper has over 200 references so doesn't that make it more useful? :P Just to clarify, this is for a software renderer and in my case I'm only rendering cube's (or 6 quads) so I wanted to see if a quad renderer would be faster than rendering 2 triangles for each quad. I was hoping SIMD would work out better with 4 half space functions vs 3. I came across this paper because I didn't know how to interpolate with 4 points vs 3 (its not as well documented or used probably).

I'll read up more on affine math but I know that interpolating with 4 points has to be possible because I've seen mentions of people who created software renderers that only render quads (not as 2 triangles but as 4 halfspace functions).

You can think of an affine combination as a weighted average of points. I recommend Essential Math by Van Verth, 2nd Ed.

Your example doesn't work because of 2 things:

1. You're using the normal Cartesian coordinates of the triangle points instead of converting them to barycentric coordinates.
2. You're basically pre-selecting the barycentric coordinates. You need to use the formulas to compute all the \( w_j \) values and then you'll see \( \sum_{j=0}^n w_j(\mathbf{q}_j-\mathbf{p}) = 0 \), where \( \mathbf{q}_j, \mathbf{p} \) are in Cartesian coordinates.

In order to get the proper interpolation you're looking for, You have to use the formulas in that paper to convert the point to the barycentric coordinates (the \(\alpha_j\) vector) and then dot that with the values you want those points to have in order to get the interpolated value of the given point.

I will agree with Randy Gaul that you do lose coordinate uniqueness if the polytope isn't a simplex. However, I disagree with him that this paper is not interesting. True, barycentric coordinates with a simplex will guarantee a unique coordinate value for any point, but there are a lot of uses beyond just finding points in a simplex, although you have to be sufficiently interested in computational geometry to appreciate them. In a game programming setting, there might be only a couple of relevant uses beyond this one.

Oh okay, that makes a lot more sense. I read up on affine spaces and I think i can properly visualize them now. I read a bit of essential math but the matrix example confused me so I might go back with a better understanding now and see how else it is applied in graphics. From my pdf, it explained affine spaces as 2 sets and a operator overload. We have a set E of points, a set E' of vectors which is a vector space, and we overload + in order to satisfy certain addition axioms. The set E' is basically all the possible vectors that you can apply to displace any point E and still be left with a point in E (this way of looking at it made it a lot easier to visualize for me).

I also now understand why the weights sum to 1 and that's so that affine combinations behave similarly to linear combinations (this was actually quite interesting figuring out why this is the case and I wouldn't imagine that the weights would have to be constrained like that just because we shift the origin and remove its significance).

I'm going to back now and look over the paper so I might still update this post with questions, but I feel like if we just define an affine space with 4 points instead of 3 in 2D, we would basically have a quad in affine space the same way we have a triangle in affine space so we could interpolate from the barycenters and what not the same way we can interpolate a triangle. Are there any properties that get lost if we do just this? You guys are saying that you lose coordinate uniqueness once you go further than a triangle but if you did that, you would have 4 weights instead of 3. Wouldn't that guarantee that each coordinate is unique especially since its also a valid affine space and every coordinate is unique in a affine space?

Not quite.

Say we have 2 points A and B to define a line AB. We can create a combination of those two points:

c0 * A + c1 * B = P

Where P is a point on the line, and c0 + c1 == 1. c0 and c1 map to the point P given A and B.

Similarly, if we take any point P, we can directly compute c0 and c1:

n = norm( B - A )

divisor = 1.0 / length( B - A )

c0 = dot( P - A, n ) * divisor

c1 = dot( B - P, n ) * divisor

Since we have only two points A and B that define this line AB, there is a one to one mapping of coefficients to any point P on the line. Note that AB defines a one dimensional space where c0 and c1 are barycentric coordinates of the segment AB. Now say we have three points to define this line: A B and C. Imagine an affine combination of these three points that maps to P.

c0 * A + c1 * B + c2 * C = P

c0, c1 and c2 still need to sum to 1. This means we can choose any of these three coefficients and set it equal to zero. When we do this we result in the original equation above. This shows that only two points are necessary to construct a one to one mapping in this one dimensional space.

In 2D we can define a one to one mapping of three coefficients in an affine combination to a point P, and these coefficients would be called barycentric coordinates. Similar to the one dimensional example space above, we can write down equations to compute barycentric coordinates given P and 3 points, or vice versa.

If we added another point (4 instead of 3) then four (four choose three, binomial theorem) different combinations of all four points can map to a single point P. Pick any three from the set of four, and you can calculate an affine combination of those three points that maps to P.

The property you lose by adding too many degrees of freedom is one to one mapping.

That can't be right for points inside the quad. Lets say I define a triangle from a,b,c. If I make another triangle from a,b,d the points inside both triangles don't have to overlap. So theres no way to define for triangle abc the coordinates in abd without using negative weights which at that point are outside the triangle. If I define a quad from a,b,c,d the points inside the quad should be unique but the points outside might not since like you said, your adding to many degrees of freedom. So I guess wouldn't the points inside the quad be defined uniquely? ie: the weights must all be positive, you cannot have negative weights.

EDIT: I guess this assumes both triangles are also on the same plane in order to be apart of the same affine space and that abc and abd don't overlap. I'll try to do a bit of math to figure this out but it seems correct.

Yeah, 3 unique points would represent a 2-space (plane).

If you have 4 unique points you can represent 3-space, though the same rule applies: more than 4 points for a 3-space mapping and you will not have a one to one mapping.

Randy Gaul is right. You lose the one-to-one mapping because you can find other sets of weights that satisfy all the equations.

However, if I understand the application right (which maybe I don't), I don't think you need to care about that for a rasterizer. Losing the one-to-one mapping in this case means that you could have two points be rendered as the same color, but does that matter? I wouldn't think so, but then I might be missing the point of the application.