Sign in to follow this  
D.V.D

Understanding Generalized Barycentric Coordinates

Recommended Posts

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. 

Share this post


Link to post
Share on other sites

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!

Edited by Randy Gaul

Share this post


Link to post
Share on other sites

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).

Share this post


Link to post
Share on other sites

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. 

Edited by cadjunkie

Share this post


Link to post
Share on other sites

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?

Share this post


Link to post
Share on other sites

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.

Edited by Randy Gaul

Share this post


Link to post
Share on other sites

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.

Edited by D.V.D

Share this post


Link to post
Share on other sites

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. 

Share this post


Link to post
Share on other sites

Sorry, I've been stuck with exams, just finished my first one and Im not done till end of april.

 

Yeah I'm not too sure if it matters either. The triangle rasterizer that I had before would look at what changed in the half plane equations as you stepped through x and y independantly and only update the small parts of the math that actually change. I was hoping to do the same for this. As for whether the one to one will even matter, I'm not entirely sure. I feel like it could screw up the weights and how they are distributed if you got 4 of them. I guess I'll just test it afterwards or maybe Ill grab a bit of time to make the quad rasterizer quickly. 

 

Basically, my concern is that because of no one to one mapping, you will have a point where you could represent it as maybe 50%w0, 20%w1, 20%w2 and 10%w3 but might also be represented as 10%w0, 20%w1, 20%w2, and 50%w3 (i just pulled these numbers out of no where but I think it illustrates the point). If this is the case, then when i interpolate the z at each point, I might be getting completely wrong answers depending on which of the above cases happens to be the result we get for that pixel.

Share this post


Link to post
Share on other sites

Yeah I'm not sure if computing the same pixel multiple times matters for your application. So long as your algorithm of choice generates a consistent color for a single pixel you'll be fine.

 

Ryg's triangle rasterizer is fast because you can use SIMD to compute 4 pixels at once. Barycentric coordinates are just used for point in triangle testing, in which you can reject pixels outside of your triangle (if I'm not mistaken). Additionally, the problem of rasterization triangles is embarrassingly parallel to the point where each thread can be running SIMD code simultaneously -- the only difficult threading consideration would be false sharing.

 

For a quad you can do the exact same thing, except instead of barycentric coordinates you can do four plane tests, one for each edge of the quad. Normals don't need to be normalized since you're only sign testing, and you should be able to come up with a robust and fast rasterizer. It may even be faster in some specific cases where the quads fill up their own bounding AABB better than triangles do.

Share this post


Link to post
Share on other sites

Yeah I'm not sure if computing the same pixel multiple times matters for your application. So long as your algorithm of choice generates a consistent color for a single pixel you'll be fine.

 

Ryg's triangle rasterizer is fast because you can use SIMD to compute 4 pixels at once. Barycentric coordinates are just used for point in triangle testing, in which you can reject pixels outside of your triangle (if I'm not mistaken). Additionally, the problem of rasterization triangles is embarrassingly parallel to the point where each thread can be running SIMD code simultaneously -- the only difficult threading consideration would be false sharing.

 

For a quad you can do the exact same thing, except instead of barycentric coordinates you can do four plane tests, one for each edge of the quad. Normals don't need to be normalized since you're only sign testing, and you should be able to come up with a robust and fast rasterizer. It may even be faster in some specific cases where the quads fill up their own bounding AABB better than triangles do.

 

Okay I found the time and made a quick one. I didn't really go for implementing what was in the paper yet, I wanted to see if just extending ryg's code would work. Here's what I got:

void RenderQuad(ScreenBuffer* Screen, Vector2i P[4], float32 z[4], uint32 Color)
{
	//SortPoints4(P);
	// Get bounding box
	int32 MinX = Min4(P[0].x, P[1].x, P[2].x, P[3].x);
	int32 MaxX = Max4(P[0].x, P[1].x, P[2].x, P[3].x);
	int32 MinY = Min4(P[0].y, P[1].y, P[2].y, P[3].y);
	int32 MaxY = Max4(P[0].y, P[1].y, P[2].y, P[3].y);
	MinX = Max2(0, MinX);
	MinY = Max2(0, MinY);
	MaxX = Min2(Screen->Width, MaxX-1);
	MaxY = Min2(Screen->Height, MaxY-1);
	Vector2i Pos = { MinX, MinY };
	// Increment values
	int32 A01 = P[0].y - P[1].y; int32 B01 = P[1].x - P[0].x;
	int32 A12 = P[1].y - P[2].y; int32 B12 = P[2].x - P[1].x;
	int32 A23 = P[2].y - P[3].y; int32 B23 = P[3].x - P[2].x;
	int32 A30 = P[3].y - P[0].y; int32 B30 = P[0].x - P[3].x;
	// Calculate row starting positions
	int32 w0_row = (P[2].x - P[1].x)*(Pos.y - P[1].y) - (P[2].y - P[1].y)*(Pos.x - P[1].x);
	int32 w1_row = (P[3].x - P[2].x)*(Pos.y - P[2].y) - (P[3].y - P[2].y)*(Pos.x - P[2].x);
	int32 w2_row = (P[0].x - P[3].x)*(Pos.y - P[3].y) - (P[0].y - P[3].y)*(Pos.x - P[3].x);
	int32 w3_row = (P[1].x - P[0].x)*(Pos.y - P[0].y) - (P[1].y - P[0].y)*(Pos.x - P[0].x);
	// Rasterize
	for (Pos.y = MinY; Pos.y < MaxY; ++Pos.y)
	{
		int32 w0 = w0_row;
		int32 w1 = w1_row;
		int32 w2 = w2_row;
		int32 w3 = w3_row;
		
		for (Pos.x = MinX; Pos.x < MaxX; ++Pos.x)
		{
			if ((w0 | w1 | w2 | w3) >= 0)
			{
				float32 DepthValue = (w0 + w1 + w2 + w3) / (w0*z[0] + w1*z[1] + w2*z[2] + w3*z[3]);
				Screen->BackBuffer[Pos.y*Screen->Width + Pos.x] = Color;
				Screen->DepthBuffer[Pos.y*Screen->Width + Pos.x] = DepthValue;
			}
			// One step to the right
			w0 += A12;
			w1 += A23;
			w2 += A30;
			w3 += A01;
		}
		// One row step
		w0_row += B12;
		w1_row += B23;
		w2_row += B30;
		w3_row += B01;
	}
}

So far, this works properly at rendering one of the faces of a quad while keeping proper depth interpolation (ie: the triangles don't get drawn overlapping when they shouldn't). I didn't do extensive testing to see if the depth is exactly the same as drawing the quad with 2 triangles (exams maybe later). I'm wondering if the paper is any different now, it looked more complicated to be honest but I still wanna figure it out, maybe after exams. I do have a question on sorting the triangles points, ryg's blog says the vertices have to be sorted counter clockwise so I made this function to do so:

void SortPoints4(Vector2i* P)
{
	float32 angles[4] = { atan2(P[0].y, P[0].x), atan2(P[1].y, P[1].x), atan2(P[2].y, P[2].x), atan2(P[3].y, P[3].x) };
	for (int32 i = 1; i < 4; i++)
	{
		float32 tmp = angles[i];
		Vector2i tmp2 = P[i];
		int j = i;
		for (; j && tmp < angles[j - 1]; --j)
		{
			angles[j] = angles[j - 1];
			P[j] = P[j - 1];
		}
		angles[j] = tmp;
		P[j] = tmp2;
	}
}

This doesn't work properly even though it should sort the points counter clock wise. It works by finding the angles from the origin which is bottom left of the screen, and then it makes it go from lowest to highest. Unfortunately, this makes the quad disappear sometimes depending on its orientation to the camera. Is there a easy way of doing this? Or is there a way of making it invisible all the time or only when the normal of the quad is facing the camera?

 

Not sure if this helps, but here is a really nice tutorial on point arithmetic (it starts about chapter 7):

http://www.flipcode.com/archives/3D_Geometry_Primer_Chapter_1-Introduction.shtml

 

Thanks for the link, will look over it!!

Share this post


Link to post
Share on other sites

There's a lot of ways to sort 3 verts. You can use a series of if-statements to enumerate all the possibilities (once in screen space), or you can cross two edges and see if the resulting vector points towards or away from the camera.

 

I found some really old code of mine for doing backface culling (read with caution):

bool Camera::IsBackFace( const Point4& a, const Point4& b, const Point4& c )
{
  Vec4 A, B, C;
  A.Set( a.x, a.y, a.z, a.w );
  B.Set( b.x, b.y, b.z, b.w );
  C.Set( c.x, c.y, c.z, c.w );
  Vec4 v1( B - A );
  Vec4 v2( C - A );
  Vec4 N( Vec4::CrossProduct( v1, v2 ) );
  Point4 pos( position.x, position.y, position.z, position.w );
  Vec4 view( pos - a );
  return Vec4::DotProduct( N, view ) < 0.0f;
}

Share this post


Link to post
Share on other sites

It looks like your code is looking at which way your object is facing (towards camera or away). I know that is one of the ways to check clockwise vs counter clockwise ordering but my method which sorts points based on their angle from the origin or bottom left part of the screen should also work yet it doesn't. For most of the random rotations my quad goes through, it goes invisible even though the vertices are ordered properly. Is there anything wrong with my code? Its just a sort that I found somewhere online.

 

I've seen other people do similar software rasterizing as I am but they don't order their vertices, they just transform them to camera space, figure out which ones are together via index buffer and render. For some reason when I define my quad as 


	Vector3f Cube[8] = { { 1.0f, 1.0f, 1.0f }, { 1.0f, 0.0f, 1.0f }, { 0.0f, 1.0f, 1.0f }, { 0.0f, 0.0f, 1.0f },
	{ 1.0f, 1.0f, 0.0f }, { 1.0f, 0.0f, 0.0f }, { 0.0f, 1.0f, 0.0f }, { 0.0f, 0.0f, 0.0f } };

and render each face, some of my faces appear correctly under arbitrary rotations but others disappear sometimes. Is there a way to somehow arrange the vertices before hand so I don't need to sort each face after? If it helps, I will only ever be rendering cubes. If some of my faces work properly under arbitrary rotations, then I think there has to be some way to get this to work.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this