3D Membrane System

[Nunz]

I wanted to make this thread for an issue I have decided to personally tackle and that is the generation of a 3D Membrane. So far I have come up with these solutions:

First solution involves using an Edge Detection Function (which i’ll likely have to write) to generate vertices (dots which connect to form triangles) that form half the outline of your cell’s membrane. Then those vertices would be duplicated several times and rotated around the thinnest axis of the shape and connected in such a way to form triangles. I will demonstrate this method manually later today.

• Biggest issue I forsee is that this will result in perfect symmetry every single time and tendrils/protrusions will have to be marked and handled seperate somehow or else they will just form cones and protruding rings on the cell. However this method I feel will result in things which can be UV unwrapped and auto textured very well. I’ll have to try and find out.

The other solutions is to use spheres which automatically fuse/meld together and form smooth shapes like Z-Spheres from Z-Sculpt. Meshes made this way usually have to be remade in other programs for games so i am unsure if that’s the right way to go but, it’s worth looking into as well.

The biggest reason I wish to do this is so that shaders may be applied to the cells, which will make the game look much nicer. Also animating 3D shapes is easier in my opinion than 2D.

Please give me any opinions or ideas.

[hhyyrylainen]

As this is about programming (the membrane mesh generation), I changed the category there.

I think this recent idea for how to do it seemed very nice to me:

Convolution Surfaces: A better alternative to metaballs

I saw the metaballs concept on my Facebook feed, and figured I should probably makes this post (about 4 years overdue). One of the things I was working on back in 2016 was figuring out a good solution for 2d and 3d organism editing. There are quite a few constraints that a good editor should meet, but the 3 main ones is that it should be easy to use (you don’t need a 2 hour long course to design a creature), it should be sufficiently powerful (any creature you can come up with should be possible…

and also the reply in that thread.

How does your idea differ from that, what are the pros and cons with your system? I got the picture that the convolution surfaces idea would fulfill all of the things the players seem to want the membrane to do.

[Nunz]

My first method is completely different and generates a usable mesh straight away from the outline of all the hexagons using vertices.

My second method is the convolution ball method essentially. Meshes made that way are usually very poorly optimized models and must have their detail baked to a lower polygon mesh.

[Nunz]

Pros of my first method:
*Should generate an optimized model
*uses the hexagon system already in place
*Proper texture files can be generated easier

Cons
*perfect symmetry
*tendrils and protrusions made from hexagons not along the long axis will have to be handled seperate

[Nunz]

So to show my method I went into my 3D program and took pictures of the various steps my function will have to go through in order to create 3D shapes from hexagons like the following:

Currently, such a configuration of hexagons produces this:

Obviously not even close to the shape we wanted. So what we will do to remedy this is we will trace the outline of the hexagons and identify the outer most vertices just like this:

This will give us a loop of vertices shaped like this:

Not terribly impressive but with just a bit of subdivision and math:

Not bad. Not bad at all. But it’s not 3D. This is where things get a bit tricky. Currently, the one solution I have found is to simply chop the loop in half, and place a duplicate of that half every 45 degrees around the long axis of the shape giving us:

and if we connect the vertices to form faces along with some subdivision:

We have achieved 3D. The primary advantage of this method is geometry. The geometry of this mesh is essentially perfect for manipulating/deforming which makes things like UV Unwrapping for textures (or even adding animation) very easy:

However this method is not perfect. The cons include not really being able to do asymmetry and things like tendrils or bumps become shapes like this concave section at the rear:

Overall however it’s a workable solution that I think can be improved, and if nothing else the Edge Detection may come in handy.

[Nunz]

So I wasn’t going to say anything until I was actually done but, I figured this is important to mention and things are moving along where I feel confident sharing this.

I have more or less decided on a new method and it (so far) seems to be the way to go. The method essentially involves generating 3D shapes according to patterns in the hex grid and then uses the Marching Cubes Algorithm to create a single mesh from those shapes. I am currently developing a Prototype in Godot for it and will release it and explain it deeply at a later date when I feel comfortable.

Once the Prototype is complete, I will go about putting it in the main game, and we should have 3D cells with little change to the mechanics of the current editor.

[Nunz]

Updating this because, I just kinda forgot about this thread lol:

So as many of you know I changed up the algorithm quite a bit. First big difference is instead of using simple Primitives, I will be using Signed Distance Functions, essentially simple equations that define the points of space that are below or above a certain surface. You can find a more detailed article here:http://jamie-wong.com/2016/07/15/ray-marching-signed-distance-functions/

Next big difference is I decided to use Convolution Surfaces after all. Initially, I was very against using them for a very simple reason; they are usually very slow. This is because you have to do so many calculations, you have to do equations like the SDFs mentioned before, then you have to do a sort of smoothing equation/algorithm, then on top of all of this you have to use a very heavy/slow algorithm to actually generate your data like Marching Cubes or Dual Contouring. Originally, I tried optimizing everything to where almost all of the work load would be on the Marching Cubes step of generating the mesh (hence using premade primitives with a simple smoothing algorithm of some sort, and making the 3D grid for Marching Cubes low enough resolution to do some smoothing of it’s own) however, my findings were basically that despite working ok, most of the speed loss was coming from the Marching Cubes algorithm to the point where the SDFs or smoothing honestly wouldn’t slow things down at all in comparison if you do it right. Marching Cubes, although very simple to implement and decently effective has many inherent inefficiencies and the meshes made by it are from far ideal in geometry. This lead me to scour the internet and Computer Science articles looking for a solution I may not have seen before. That’s how I found Del-Iso.

Del-Iso is a very sophisticated isosurface meshing algorithm which descends from Delaunay Refinement. It builds from a process that has actually existed for a while and is pretty well known and that is the combination of 3D Voronoi Cells and Delaunay Triangulation to generate surfaces. However those algorithms are notoriously slow and are bottle-necked by the data generation portion of the algorithm (this is basically why before Del-Iso, even the worst Marching Cubes style algorithm was faster) Del-Iso solves this by optimizing the data generation portion in a fairly clever way that is best explained in the original article:

deliso.pdf

So, I know what you’re thinking “Ok, but how much faster can this really be? Wouldn’t the SDFs still slow things down?” . Del-Iso is 3 - 4 x faster than the prior algorithms, at worst it’s 1.5 x faster. This is blisteringly fast and is the difference between seconds and milliseconds in some cases. What’s more is, there are many obscure improved models of this algorithm if you look hard enough or simply write the code better and make good use of modern hardware (Del-Iso is over a decade old) you can get even more speed. In essence, the SDFs wouldn’t add much time in comparison to other algorithms simply because this one is so much faster.

Below I have basically the main comments I wrote down in my current code to help guide my development and I think it sums up the algorithm for the entire script well enough (though I’m sure there’s stuff missing or vague since I wrote these before starting to code):

//find center mass hex, this is (0,0)
//create SDF (Signed Distance Function) at (0,0), radius initialized at 1
//sort the list for organelle positions so they can be checked
//loop checks if the SDF radius can be increased, preventing the need for many to form mesh
//check outside the SDF for extra organelles
//create SDFs at groups of extra organelles
//use SDF qualities to make bones for animation
//run SCALIS algorithm on SDFs to make the isoSurface
//create points along isoSurface for use in Del-Iso
//run Del-Iso algorithm

If you have any questions please ask

[Nunz]

Current state of affairs is that we need a UV unwrapping solution, and the tessellation of the mesh plays a huge role. My heart is already with Del-Iso for triangle making but, I’ve been reading a lot of theory and science around UV unwrapping trying to figure out what kind of things we have to do, in order to make sure we’re not just creating a jumbled mess of algorithms, since this would be the third piece now. Del-Iso has many inherent benefits geometrically speaking, the grander concept of Delaunay Triangulation is actually how lots of LOD systems work under the hood. Going to try something soon to incorporate it’s qualities in an unwrapping solution.

The actual math in C# of the Convolution Surfaces themselves is done but, is not fast and not compatible with our past visions of using it in realtime, it’s just not feasible without compute shaders. We need to overhaul the reproduction system so the membrane doesn’t need constant regeneration.

Here are some notes of mine, may be incomplete:

/// RESTRICT

// figure out way to pick voxels on surface
pick random points in voxel grid
make sure we have a dense sample
foreach point selected // sites
{
	// group together sites near each other
	find nearest neighbors
	separate neighbors as group	
	foreach group
	{
		// find voronoi cell bounds
		find distance between each point // line is dual
		place plane separating each pair halfway
		build edges along any intersections // voronoi edge
		foreach edge
		{
			// collect any restrictions of dual edges
			if isosurface crosses edge: restrict dual
		}
	}
}

/// REFINE

foreach triangle of dual restriction
{
	make circle around triangle
	insert new site at center of circle
	add site to collection of restricted sites
}

// sample density can go by the size of voronoi cells
restrict and refine sites until we have a dense enough sample

!! NOTES !!

• We have a geometric skeleton so, we know the general shape

• The skeleton has points of it’s own, we should try restricting some to see what happens

• Del-Iso is unique from Marching Cubes in that we can have different cuts of creature refine independently that are smooth rather than being made up of voxels

• Del-Iso has inherently useful properties for a generalized LOD system (Dynamic Tesselation) if we wish to make one

• Convolution Surfaces are not lumpy, so there will be spots that match defined weights for skeletal elements, like metaball radius

• If we can cut up the surface before triangulation (into 2D shapes), we can use this mapping for both greatly accelerated 2D voronoi restriction, and UV mappings

• Could the surface be cut up using general formulas based on the mathematics of Convolution Surfaces?

• This general algorithm should be done in C++ at a final iteration, it can be ‘slow’ depending on implementation, especially combined with Convolution Surfaces

• Without compute shaders, we can’t use this constantly in realtime

• Convolution Surfaces gives us integrals that we can use to find lines along the surface

• This is potentially the final piece of the Convolution Surface puzzle, barring any Godot quirks

[Buckly]

Membrane generation seems to have always been a pretty resource-intensive process. But doing away with features such as organelle splitting would be pretty sad after having it around for so long, given that it gives some nice flavor to the microbe stages.

Thinking on this, one potential solution I’ve devised is the following:

Instead of regenerating the membrane each and every time the organism duplicates an organelle, it could simply grow in size as reproductive progress is made. This would gradually increase more room for the internal organelles to themselves grow and divide. Obviously this then presents a very prominent danger of the organelles clipping through the membrane after splitting and growing, so there’s another method of handling that:

Organelles first grow in size at an approximately similar rate to the membrane itself until they are ready to split. When the organelles finally split, the two resulting sister organelles will be at the initial size, and the membrane will not be altered to accommodate. The sister organelles will be tightly packed against each other, and instead of growing larger will grow further apart as the cell continues to grow from this point.

I’ll simplify the process into steps:

1. Membrane and organelles grow in size as the player collects compounds
2. Passing the halfway point of reproduction, the organelles will begin splitting, but remain tightly packed against each other.
3. The membrane continues to grow as progress is made, the sister organelles begin to shift further apart from each other, but do not grow.
4. Once the reproductive bar is filled, all growth will cease and each pair of organelles should no longer be in physical contact with one another. The cell is ready to begin division.

This method ensures that the process of organelle duplication remains, and growth continues to have an impactful and visual presence in the game. Some fine tuning may be needed to ensure that organelles don’t often or never escape the confines of the membrane when splitting, but I think this method may work. Of course, this is a drastic change, and there’s probably alot of code that will need to be entirely reworked for this to happen…

[hhyyrylainen]

I think it’s worth it to first try to just remove organelle duplication that happens before a dividing animation would start. That was already kind of accepted as the solution to the slow membrane generation problem. As a bonus that is also scientifically more accurate as cells don’t really gradually duplicate their stuff, instead they just do it all at once when they are going to split (if I remember right what was said about this). So I suggest that we just do that at first and only consider solutions if that is even an actual problem.

[Deus]

I wanted to post this here to make it or available to the public as opposed to just on Discord, regarding intercellular matrixes.

A common question we get is related to progress on intercellular matrixes, with little to report back. However, it is important to note that at a very microscopic scale, membranes of multicellular organisms don’t typically blend into one another, or mesh together as they do in advanced tissues and macroscopic structures. Oftentimes, it looks like cells are taped together as awkward as it may seem.

Here are some photos of multicellular organisms:

So this is to say that there likely won’t be this immense transformation of binding graphics in the future. This is not to say there is no area of improvement, especially related to cell positioning and membranes themselves.

[hhyyrylainen]

It might just be a coincidence but I recently answered a question on reddit about the multicellular graphics. I want to add intercellular matrix as basically an hourglass shaped graphics piece used to visually attach colony members in multicellular. That is in the first place needed because the body plan cells can end up really far away from each other. Why I am suggesting that instead of a proper position fix? Well that’s because I basically have no doable idea right now how to fix the positions, instead with the “intercellular matrix” graphics that would mostly mitigate worst of the problem which seems to be the players noticing the massive gaps and posting about it.

[dligr]

I’d like to revive this discussion, since I’ve made some significant progress with 3D membranes. I devised two different algorithms for them and made proof-of-concept realizations of them, to decide what would be better for Thrive.

Without further ado,

Prism-based membranes

This algorithm is best if we want to preserve the current style, while also getting all benefits of 3D. I’ve made a scheme on how it works:

In fact, this algorithm was discussed back in 2015, when the current membranes were made in the first place, but it seemingly never made it into the game.

Anyway, this is how the resulting meshes look:

I want to stress that those meshes are pretty much what we have in the game now, just extended into 3rd dimension. No other changes.

Pros of this algorithm:

• Performance (at least compared to algorithms based on 3D grids, like convolution surfaces or metaballs)
• Very simple UV mapping
• Preservation of the current memrane visuals (though it is subjective whether this is a pro).

Cons:

• Player still has no control over membrane shape.

Meatball-based membranes

This algorithm is based on Dual Contouring mesh-generation, with the defining mathematical function being a modified version of metaballs.

But before I detail this algorithm, I would like to explain the reason for not using Convolution surfaces, which was already proposed in this thread.
That reason is performance. Even if we swap SCALIS for a basic convolution formula (which are way more performant), calculating each bone would still be more resource-intensive than calculating each metaball, just because of how the corresponding formulas work. Moreso, with our hex-based microbes, there would be more bones (aka adjacencies between hexes) than metaballs (aka hexes themselves). Thus, convolution surfaces would be significantly worse for performance.

So, back to meatballs. One important thing to consider is that in our hex-based editor, there is always the exact same distance between adjacent hexes. In other words, the same exact distance between each pair of metaballs that needs to be connected. This gives us the possibility to make some changes to the formula to counteract metaballs’ flaws.

And in our case, their biggest flaw is infinite range at which each metaball can influence mesh shape. Simply put, it makes shapes with a big amount of meatballs fuse into one big blob. I fixed it by adding a distance cap, after which metaball doesn’t have any kind of influence. I also added some other function modifications for shape fine-tuning, but I think that they aren’t as important in our context.

Anyway, here is what I got (after some struggle with UVs):

(Those white dots are metaballs’ centers)

And here are some other meshes that I generated:

Feel free to ask for more mesh pictures.

Pros:

• Player actually has control over membrane shape
• Membranes are just less boring than the convex shapes we have now

Cons:

• Performance. Even though the meshes above took a little under 0.1 s each to generate, I imagine performance will be significantly worse for big microbes. I see some possible optimisations, though.
• Harder UV mapping. If you look closely at the images above, textures on membranes’ tops are weirdly arranged, which is the direct result of that. Maybe it would be possible to solve this by projecting a second texture from the top, however.
• Unrealism? I’m not sure about that, but it seems to me that shapes that are possible to make with meatballs wouldn’t always resemble real microbes. But I’m not a biologist.

Well, that’s about it. I would like to ask what everyone else thinks about this, and which of those algorithms would be better to implement into the game.

[Deus]

Very exciting work!

I can’t speak much as to technical requirements and performance concerns, but atleast visually, I do think it is a good idea for us to give the player some more control over the shape of their cell. Like you illustrated, there are some shapes that are pretty bizarre which would then be possible. Protists can have very bizarre shapes, and bacteria even more -

Though there are some limits - we definitely don’t want holes in our cells for example, and that one question mark shape is a bit odd. The hole-in-species problem definitely would need some special handling.

If there are ways to - I don’t know if this is the proper term - “round out” the way metaballs connect to eliminate these more bizarre shapes, that could be ideal; though at that point, the question is if the result would essentially be largely the same as prism-based membranes. Perhaps the underlying math behind membrane generation itself could be more optimized, and that would result in prism-based membranes having more finely controlled appearances?

So yeah, those are some thoughts. Apologies if there aren’t too many answers there. One thing I remember though, Hh mentioned a while ago that they’d be very willing to help change certain things if there are issues (for example, organelle splitting since Nunz mentioned that really slowed things down) to get 3D membranes implemented, due to how much the community wants them. Though of course, less dramatic reworks are much preferred.

[hhyyrylainen]

This is some excellent prototyping.

It’s probably partially due to being so familiar with the current visuals that the new ones make things look a bit strange. Though I think we’ll need at least some texture updates to go along with the new shape to make the texture fit better.

@Deus

Hh mentioned a while ago that they’d be very willing to help change certain things if there are issues (for example, organelle splitting since Nunz mentioned that really slowed things down)

When an organelle splits, the shape of the microbe changes as it has a new organelle in it. I said before that we could move to an approach where organelles don’t split (or if they do it would be like part of a cell division animation).

The performance is pretty major concern because with the current approach the generation has to be fast enough to not cause too major lag spike. If we do need much more generation time we can find a workaround for the organelles dividing, and add a new loading screen step during which all membranes for species in the current patch are generated to avoid lag spikes during gameplay.

Also I’ll bring up the physics shape, engulf and mucocyst effects as things that depend on the current membrane shape and need to be updated in the second approach (I assume the prism is the same overall shape as before so it can be done with much less effort).

[dligr]

@Deus

Though there are some limits - we definitely don’t want holes in our cells for example, and that one question mark shape is a bit odd. The hole-in-species problem definitely would need some special handling.

I think that the best way to solve this would probably be to make those “donut” cell layouts illegal, which was already proposed recently.
Now, I tried making some changes to the formula, removing that hole, but that unfortunately doesn’t work for bigger “donut” membranes.

@Deus

Perhaps the underlying math behind membrane generation itself could be more optimized, and that would result in prism-based membranes having more finely controlled appearances?

Unfortunately, I don’t think it’s possible, since prism-based generation doesn’t work well with non-convex shapes that could be made with more player control.

So, there is indeed a lot of things that would need to be done to implement the meatball-based membranes.

To sum up what we need to do to implement them:

• Better UV mapping, probably along with a new texture for membranes. The new one would probably be projected from the top, as I mentioned in the previous post.
• Engulf and mucocyst effects. Would need an entirely new visual concept for each of those, because I don’t think we can just keep the current 2D effects
• And most likely something to handle organelle splits. Theoretically, we could try not updating the mesh each time an organelle splits, instead just making each of organelles occupy the same spot. However, this would definitely take away some of the game’s flavor.

There is also performance to worry about. The current generator and the prism-based one are O(n), where n is the number of hexes. Basically, linear time growth. Metaball-based generator, however, is O(n * m^2), where n is the number of hexes, m is dots calculated per side. This is exponential time growth.
I tested it with 228 metaballs, and the time was 7 s, which is, in my opinion, unacceptable even if this metaball count is outside of what could be reasonably encountered in game. For reference, a shape with 7 metaballs generates in ~0.06 s

So, I’d like to hear your thoughts about that. Metaball-based generator seems like a really uphill task (and it isn’t flawless even then), so maybe we should make the prism-based one?

[Gamedungeon]

I personally like the prism based one more. We actually have code for the current membrane generation to generate concave shapes, but explicitly decided not to use it as it would make physics more difficult (If we ever reverse that choice I could get the code ported in a few minutes.)

I also agree that we should ban the donut cell layouts. They are unrealistic and provide a plethora of problems.

I believe some shenanigans with the mesh normals of the prism could go a long way to making it look more round and less blocky. That would really help cell the illusion.