• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
cephalo

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

sad.png

 

 

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 this post


Link to post
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 laugh.png - 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:
6e5cfc272604874.jpg

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:
b25159272604868.jpg

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:
016f78272604896.jpg

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:
791684272604880.jpg

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);
462a9a272604884.jpg

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:
38ad83272604893.jpg

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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

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  
Followers 0