How to obtain barycentric coordinates? (Wireframe Shader)

novaleaf

I'm a shader noob trying to write a wireframe shader.

it seems that the way to do this is to use barycentric coordinates, meaning location inside of the vertex. This is a webgl example of using barycentric coords to do a wireframe shader: http://codeflow.org/entries/2012/aug/02/easy-wireframe-display-with-barycentric-coordinates/

However in the shader docs I don't see any way of obtaining the barycentric coordinates. Is there another option? I can't see any Godot examples of doing either wireframe or edge enhancements in shader. does anyone know some resources?

I know I can do edge enhancement by inverse hull or by a postprocess screen shader, but I'm interested in learning how to write model shaders.

cybereality

Yes, it can be done in Godot.

I actually ported that shader myself a few weeks ago and it works. The best part is that it is done in a shader, so it can run fast on mobile (unlike post-process effects). You have to create the barycentric coordinates yourself, and then update them using a vertex attribute (you can use the vertex color or some other property that is not being used to store the coordinates). I used MeshDataTool to process the vertices. I believe I based it on these two articles.

https://tchayen.github.io/wireframes-with-barycentric-coordinates/ https://www.pressreader.com/australia/net-magazine/20171005/282853666142801

Let me know if that is enough for you to figure it out. I can also share my code but it sounds like you may want to learn on your own, so let me know how that goes. Cheers.

novaleaf

Thanks @cybereality I am going through that right now. How did you encode the vertex into the color? I'm not sure how I'll be able to translate that into the barycentric coords later (when I get that far), but here's what I'm doing now:

		float vertexCount = mdt.GetVertexCount();
		for (var i = 0; i < vertexCount; i++)
		{
			var channel = i % 3;
			var color = new Color(0, 0, 0, 1);
			switch (channel)
			{
				case 0:
					//color.r = i / vertexCount * 3;
					color.r = 1;
					break;
				case 1:
					//color.g = i / vertexCount * 3;
					color.g = 1;
					break;
				case 2:
					//color.b = i / vertexCount * 3;
					color.b = 1;
					break;
			}

			mdt.SetVertexColor(i, color);
		}

as color is 4 byte I should be able to shove an int in there, but don't know how to do that yet.

novaleaf

It seems like the approach I outlined above isn't really going to work, as two corners of the triangle can be the same color.

cybereality

So the basic idea is to set each of the 3 vertices to be 1.0 in a single color channel.

The way I am doing this is like this for each face:

var coords = [Vector3(1, 0, 0), Vector3(0, 1, 0), Vector3(0, 0, 1)]

Then for each vertex in the loop:

var next = coords.pop_front()

Then set the vertex color to the value next. MeshDataTool has a member called set_vertex_color. https://docs.godotengine.org/en/3.2/classes/class_meshdatatool.html#class-meshdatatool-method-set-vertex-color

If you don't need inner edge removal, then this is all you have to do. For the edge removal it gets a little more complicated. To be honest, I'm looking at my code and it doesn't really make sense to me. I mean, it works but I'm not sure exactly how it works entirely. I think I found some Unity code on StackOverflow or something, I can see if I can find the link for you if you need it.

novaleaf

actually the code I posted above works under certain conditions. it seems that some models (like those I exported from magicavoxel) have different (messed up?) vertex winding orders, so there are some faces with R,G,G, which messes up this process.

@cyberreality if you could post or email me your version I would appreciate it. (jasons aat novaleaf doot coom)

heres my code to process the mesh (C#)

	public override void _Ready()
	{
        var testNode = FindNode("Test") as MeshInstance;
		//var mesh = GD.Load<ArrayMesh>("res://asset/fish/Fish1.obj");
		mesh = testNode.Mesh as ArrayMesh;

		var mdt = new MeshDataTool();
		mdt.CreateFromSurface(mesh, 0);



		float vertexCount = mdt.GetVertexCount();
		for (var i = 0; i < vertexCount; i++)
		{
			var channel = i % 3;
			var color = new Color(0, 0, 0, 1);
			switch (channel)
			{
				case 0:
					color.r = 1;
					break;
				case 1:
					color.g = 1;
					break;
				case 2:
					color.b = 1;
					break;
			}

			mdt.SetVertexColor(i, color);
		}
		//replace our mesh with modified version
		mesh.SurfaceRemove(0);
		mdt.CommitToSurface(mesh);

		testNode.Mesh = mesh;
	}

and here is the shader

shader_type spatial;
void fragment() {	
	if(COLOR.x < 0.01 || COLOR.y < 0.01 || COLOR.z < 0.01) {
		ALBEDO = vec3(0.0, 0.0, 0.0);
	} else {
		ALBEDO = vec3(0.5, 0.5, 0.5);
	}
}

novaleaf

here's an example of the same workflow on my magicavoxel mesh.

it seems like I need to rebuild the mesh, any ideas?

cybereality

Yeah, I can share my code, maybe that will help.

func init_mesh():
	var mdt = MeshDataTool.new()
	var cube = get_node("Mesh")
	var mesh = cube.get_mesh()
	var mat = cube.get_surface_material(0)
	mdt.create_from_surface(mesh, 0)
	var done = {}
	var bary = {}
	randomize()
	var rand_color = Color(randf(), randf(), randf())
	var nors = {}
	for j in range(mdt.get_face_count()):
		var fid = mdt.get_face_vertex(j, 0)
		var nor = mdt.get_vertex_normal(fid)
		var coords = [Vector3(1, 0, 0), Vector3(0, 1, 0), Vector3(0, 0, 1)]
		for n in nors:
			var dot = nor.dot(nors[n]["normal"])
			if dot == 1:
				rand_color = nors[n]["color"]
			else:
				rand_color = Color(randf(), randf(), randf())
		nors[fid] = {"normal": nor, "color": rand_color}
		for k in range(3):
			var vid = mdt.get_face_vertex(j, k)
			if bary.get(vid):
				coords.erase(bary.get(vid))
		for i in range(3):
			var vid = mdt.get_face_vertex(j, i)
			if !done.get(vid):
				done[vid] = true
				var removal = Vector3(0.0, 0.0, 0.0)
				
				var vert_0 = mdt.get_face_vertex(j, 0)
				var vert_1 = mdt.get_face_vertex(j, 1)
				var vert_2 = mdt.get_face_vertex(j, 2)
				
				var edge_a = mdt.get_vertex(vert_2).distance_to(mdt.get_vertex(vert_0))
				var edge_b = mdt.get_vertex(vert_0).distance_to(mdt.get_vertex(vert_1))
				var edge_c = mdt.get_vertex(vert_1).distance_to(mdt.get_vertex(vert_2))
				
				if (edge_a > edge_b) && (edge_a > edge_c):
					removal.y = 1.0
				elif (edge_b > edge_c) && (edge_b > edge_a):
					removal.x = 1.0
				else:
					removal.z = 1.0
				
				var next = coords.pop_front()
				if next:
					bary[vid] = next + removal
				else:
					var coords2 = [Vector3(1, 0, 0), Vector3(0, 1, 0), Vector3(0, 0, 1)]
					for m in range(3):
						if m == i:
							continue
						var vid2 = mdt.get_face_vertex(j, m)
						if bary.get(vid2):
							coords2.erase(bary.get(vid2))
						bary[vid] = coords.pop_front() + removal
				mdt.set_vertex_color(vid, Color(bary[vid].x, bary[vid].y, bary[vid].z))
	mesh.surface_remove(0)
	mdt.set_material(mat)
	mdt.commit_to_surface(mesh)

novaleaf

Your code is a bit complex, so I spent a good number of hours implementing my own version, but I kept running into a pathological case. I then realized that this is basically "Graph coloring" and found an algorithm called "Welsh-Powell" that seems to work at reasonable speed: https://iq.opengenus.org/welsh-powell-algorithm/

I'm going to implement that, and if I still get problems I think the vertex may have too many edges. I have an idea to color alpha in that case and have the shader ignore where alpha ==0;

i'll post when done!

cybereality

I see, okay. Let me know how that goes. It's also possible the model is not made of triangles and barycentric only works for triangles I believe. You could probably triangulate and re-export in Blender.

novaleaf

@cybereality do you mind sharing your shader code? I ported your algorithm to c# and ran it, so now have a really good idea as to the logic flow. However I'm currious as to why you are adding extra color based on edge length. I'm guessing it's to do with how you are shading the wireframe in the shader (I still haven't gotten to wireframe optimizations in those articles you sent)

btw, here's a code review of your code, hope it's helpful:

line 16: for n in nors: this logic is not actually used in computing the end results. you can remove this and the nors list entirely and you'll improve your performance a lot. Delete lines 16 to 22. (with the lines removed I can load sibnek (100k+ verts) but with it there it stalls out)
line 49: if next: this will always be true. you can just call bary[vid] = next + removal and remove the entire if / else block (delete lines 49 to 59)

I implemented a few versions of vertex coloring algos and for large meshes I always need 4 colors, so I adjusted my shader algo to use R,G,B,A for barycentric coords instead of just R,G,B. Still, with huge meshes like sibnek cathedral I have aprox 0.1% occuranaces that need 5 colors. in those I just color the vertex white, so no wireframe for that face. Here's a screenshot of my RGBA method with Sibnek. I'll post code after I try another few algos trying to reduce pathological "5 color" cases.

cybereality

Most of that code is for the inner edge removal (so quads will result in a square wireframe). I can't remember what I was doing with the normals, but it looks like I never finished that part. You're also probably right that it isn't optimized, I was only testing on small models. Here is the shader code:

shader_type spatial;
render_mode unshaded;

float get_edge(vec3 color) {
	vec3 deriv = fwidth(color);
	float width = 1.0;
	vec3 threshold = step(deriv * width, color);
	return 1.0 - min(min(threshold.x, threshold.y), threshold.z);
}

void fragment() {
	vec3 color = vec3(0.0);
	ALBEDO = max(vec3(get_edge(COLOR.rgb)), color);
}

novaleaf

Thanks for the help @cybereality , I finished, at least good enough for now. The above is an example output and configurable shader.

My MeshDataTool code is written in C# so not sure how usable it will be, but you can find it and a test scene here: https://github.com/jasonswearingen/godot-csharp-tech/tree/dev/demo-projects/scratch/demos/WireframeMeshDemo

The MeshDataTool processing is done in WireframeMeshDemo.cs and I did my best to comment the code. I ended up using 5 color channels for vertex ID's, and 1 channel to hint what side is longest (for interrior edge removal). I was able to have these 6 channels by encoding 5 choices into red (20% each) and 1 into green. The shader reads this encoded data and generates the barycentric coords for the rest of the shader to use. The shader is in WireframeMeshDemo.shader

While this took a lot longer than I expected (everything does) I sure learned a lot about shaders! hope I don't forget it for next time it's needed.

cybereality

That's awesome! So glad I was able to be of help.