3D Membrane System

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.

2 Likes

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:

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.

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.

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

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.

1 Like

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.

4 Likes

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:

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

3 Likes

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

2 Likes

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…

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.

3 Likes