Followers 0

# Barycentric puzzle

## 10 posts in this topic

I'm having trouble abstracting in my mind the following problem. It seems like the solution should be simple, but it's not coming to me. I have a field of hexagons described by triangle tessellation patches. I need my shaders to be able to determine which part of the triangle patch belongs to which hexagon. See the following picture:

[attachment=17651:BarycentricPuzzle.png]

Is there a straightforward mathematical way to determine if a point (in barycentric coords) on the triangle is within the blue shaded area?

Edited by cephalo
0

##### Share on other sites

unbird, that is FREAKY that you solved the puzzle that fast, and with pictures! It obviously wasn't difficult enough, so I have a new one for you. Another thing I will have to do across these hexes at some point later on is texture blending. So, imagine that in the example picture you gave, that the edges between the hexes would be slightly blended together to some degree, or 'fuzzy' if you will. How would you handle that?

cwchambers, thanks for the reply. It seems useful, but I am struggling to understand it with my high school level math education. That high school was 20+ years ago for me is not helpful. When you say x and y, do you mean u and v from the trio of uvw? Inside my shader I'm dealing with barycentric triangle positions rather than Cartesian coords.

0

##### Share on other sites

cwchambers, thanks for the reply. It seems useful, but I am struggling to understand it with my high school level math education. That high school was 20+ years ago for me is not helpful. When you say x and y, do you mean u and v from the trio of uvw? Inside my shader I'm dealing with barycentric triangle positions rather than Cartesian coords.

Yeah, I may have jumped the fun in my reply. The solution I presented is for transforming points of a Cartesian plane to points of a grid-graph that indexes hexes. Sorry about that.

:(
0

##### Share on other sites

cwchambers, thanks for the reply. It seems useful, but I am struggling to understand it with my high school level math education. That high school was 20+ years ago for me is not helpful. When you say x and y, do you mean u and v from the trio of uvw? Inside my shader I'm dealing with barycentric triangle positions rather than Cartesian coords.

Yeah, I may have jumped the fun in my reply. The solution I presented is for transforming points of a Cartesian plane to points of a grid-graph that indexes hexes. Sorry about that.

Still, this could be very useful later on. I'll have it bookmarked. I'm actually doing something similar in other ways, and your way might be a lot faster, (as soon as I can understand it anyway).

0

##### Share on other sites
I took the challenge (and the chance to learn something about barycentric coordinates). Though I have already been beaten - thanks Lorenzo - I'll still post my discoveries. Cause I got pictures... ("in farbe ... und bunt")

For transitions my if/else cascade is not good, are more mathematical approach is due.

So, can we get e.g. a central line ? How does one express a line in barycentric coordinates ?

Ahah!

Let's try this in HLSL
float3 uvw = pin.DomainLocation.xyz;

float3 r1 = float3(0.5, 0.5, 0  );  // first point
float3 s1 = float3(0  , 0  , 1  );  // second point
float  t1 = determinant(float3x3(uvw,r1,s1)); // line equation (line is at t1 = 0)

// use this value for transition
float transition = 10;
float x = smoothstep(0, 1, transition * t1 + 0.5);

return float4(x,x,x,1);

That looks useful:

The other lines...
float3 uvw = pin.DomainLocation.xyz;

float3 r1 = float3(0.5, 0.5, 0  );
float3 s1 = float3(0  , 0  , 1  );
float  t1 = determinant(float3x3(uvw,r1,s1));

float3 r2 = float3(0.5, 0, 0.5  );
float3 s2 = float3(0  , 1, 0    );
float  t2 = determinant(float3x3(uvw,r2,s2));

float3 r3 = float3(0  , 0.5, 0.5);
float3 s3 = float3(1  , 0  , 0  );
float  t3 = determinant(float3x3(uvw,r3,s3));

float transition = 10;
float r = smoothstep(0, 1, transition * t1 + 0.5);
float g = smoothstep(0, 1, transition * t2 + 0.5);
float b = smoothstep(0, 1, transition * t3 + 0.5);

return float4(r,g,b,1);

Yep, we can work with that:

Now, we combine the parts to get those hex sections. This is done using intersection. For blending weights one can use e.g. min(a,b):
//... r,g,b like before
float rr = min(r,g);
float gg = min(g,b);
float bb = min(b,r);
return float4(rr,gg,bb,1);

Ooops:

Naah, intersect with the complement of the next line...
//... r,g,b like before
float rr = min(r,1-g);
float gg = min(g,1-b);
float bb = min(b,1-r);
return float4(rr,gg,bb,1);

... looks better:

Not quite happy with the centre. An alternative is to use multiplication:
float rr = r*(1-g);
float gg = g*(1-b);
float bb = b*(1-r);


Too dark at the transitions. Well, blending weights should sum to 1, so lets normalize them
	float3 rgb = float3(rr,gg,bb);
float s = dot(float3(1,1,1), rgb);
return float4(rgb / s, 1);

Yep:

One can now simplify the math stuff, e.g. a determinant with (1,0,0) in it, will just evaluate to a sub-determinant.

Now this is of course fun (well, it was for me), but I wonder if a different approach is actually better. I think starting with an alternative geometry, e.g. 6 triangles for one hex patch could simplify this greatly. I expect you could generate the appropriate texcoords earlier instead of going this - now rather convoluted - approach through the barycentrics.
2

##### Share on other sites

Thanks unbird! One of the reasons I'm using triangle patches at the corners, is that it's the simplest way to describe the full interaction between the three neighboring hexes, and they are seamlessly tile-able as well. I originally tried to describe full hexes, and the fact that you are dealing with 6 neighbors rather than three was really complicating things at the time. Coming up with tangent frames and blend weights with that amount of interaction was a big mouthful in a shader.

I'll try to post a screen shot later.

0

##### Share on other sites

Ok, here is a screenshot of some of the new developments. The most difficult part of this by FAR was drawing text. I did everything I could think of to avoid dx 11.1, but everything else had some reason why I couldn't use it. Anyway its working now. A cool thing I added was the ability to pick a hex with the mouse hover! (see the little green hex cursor) That made debugging the river system a lot easier, because if I saw a problem I could know which hex it was within a sea of hexes, and also print hex specific debug info on the selected hex. It works very well too, in an oblique view I can select a hex that is miles and miles (or whatever distance units you prefer) away.

The river system supports 3 sizes of river and currently just runs from the watersheds to the tiles that have no outlet. Right now, I'm just painting the rivers blue to make sure it's working, but later I will use these textures to make displacement and normal maps, and also possibly flow maps so that I can make the water surface flow down the river.

So the reason I needed to figure out this varonoi scheme is because now that I have rivers mostly working, I need to throw in the ocean and lakes. For now, I just need to paint them blue like the rivers to make sure it all works in a system, then I will start making it fancy.

[attachment=17660:HexMap2.png]

2

##### Share on other sites

Thanks unbird! One of the reasons I'm using triangle patches at the corners, is that it's the simplest way to describe the full interaction between the three neighboring hexes, and they are seamlessly tile-able as well. I originally tried to describe full hexes, and the fact that you are dealing with 6 neighbors rather than three was really complicating things at the time. Coming up with tangent frames and blend weights with that amount of interaction was a big mouthful in a shader.

Yeah, I saw that. My idea was to start with a hex made of six equilateral triangles, but then look at the triangles individually. Well, excuse if I underestimated your research effort, I was just thinking out loud providing alternatives. I'm not sure anyway if it will provide any advantage.

Anyway: The approach I demonstrated uses a pixel shader. For performance try pulling (at least) the line evaluation up the shader pipeline. It's linear, so interpolation should pose no problem. It's similar to a plane equation for e.g. custom clipping with SV_ClipDistance.

I also recommend reading more about linear algebra. E.g. what c.w.chambers showed is (apart from the rounding) more or less a shear transformation. Barycentrics, determinants, etc., yeah, all linear algebra.
0

## 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