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?

Hmmm, "voronoi" in barycentric coordinates with the corners as points:

    float ulen = length(pin.DomainLocation.xyz - float3(1,0,0));
    float vlen = length(pin.DomainLocation.xyz - float3(0,1,0));
    float wlen = length(pin.DomainLocation.xyz - float3(0,0,1));
    float3 color = float3(1,0,0);
    if(vlen < ulen)
    {
        if(wlen < vlen)
            color = float3(0,0,1);
        else
            color = float3(0,1,0);
    }
    else
        if(wlen < ulen)
            color = float3(0,0,1);
        
    return float4(color, 1);

Edit: There should have been a question mark, but it looks fine to me



Code could probably be compacted with some tricks I guess.

PS: I like your puzzles.

If your hexagons are uniform*, and if you don't mind indexing your vertices as elements of an oblique grid-graph, then there is an algebraic solution picking which hex a given point is in.

To determine which hex a point lies within one can use the following function for each index-coordinate:

floor((floor(f(x,y))+floor(g(x,y)))/3),

where ‘f’ and ‘g’ and linear transformations such that neither ‘f+g=0’ nor ‘f-g=0’ are not true. Alternatively you could combine the functions into a matrix and supply the function the resulting points ‘x’ and ‘y’ coordinates in place of the functions ‘f’ and ‘g’, respectively.

For each index-coordinate there is a different set of transformations. One can determine these transformations by observing that by picking two adjacent edges of your zero-hex, ‘(0,0)’ and determining the implicit forms of the lines on which these edges lies, that one determines both the lower zig-zag edge of the of a row of hexes in which the zero-hex lies, and the implicit-forms of the lines are implicit-functions that determine the transformations.

A quick example. Suppose we align the grid-vertices such that the zero-vertex coincides with the origin and the vertex indexed (1,0) coincides with the same point of the plane. This centers the zero-hex at (0,0) and the hex indexed as (1,0) centered at the same point. If one wants rows that run parallel to the x-axis and with indexes rising in the positive y-direction, then pick the vertex of the zero-hexagon which lies on the y-axis below the x-axis as a point lying on the lower edge of the hex row, the two edges of the hex which share that vertex are the edges which determine the transformation. In this case those functions are:

f(x) = x+sqrt(3)*y+1, and
g(x) = -x+sqrt(3)*y+1.

You can see the result of this here on Wolfram Alpha:

http://m.wolframalpha.com/input/?i=plot%E2%8C%8A%28%E2%8C%8Ax%2B%E2%88%9A%283%29y%2B1%E2%8C%8B%2B%E2%8C%8A-x%2B%E2%88%9A%283%29y%2B1%E2%8C%8B%29%2F3%E2%8C%8B+x%3D-1.5..1.5+y%3D-1.5..1.5&x=0&y=0

This might be overkill for what you need as it is a general hex-picking solution, but you might be able to adapt it to your needs. Hope that helps.

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.

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.

:(

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

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.

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.

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]