# Reconstructing mesh from topological skeleton?

I have a topological skeleton of a 3d maze-like level (think Descent[I]/II). It looks like a tree where each node is a vertex in 3d-space.

If it were on a 2d plain, I would "simply" use this to offset it and reconstruct the polygon. However, it's not a 2d skeleton and I am interested in 3d mesh outward offsetting it in 3d space.

What I tried so far is offsetting outward as if it were in 2d space and then extruding the flat shape into a 3d-object. This however does not work where two edges in the skeleton are close to one another as they intersect after this process.

Is there an algorithm or tool that accomplishes this?

I am trying to do the opposite of this I believe:

skeletonization

Please notice that this is a graph with simple cycles, in my specific case it's a tree.

Starting from a skeleton and getting a rough mesh without buggy intersections.

This is an example of what it would look like after being offset outwards (inflated). Minus the intersections of course.

• Can we have some screenshots please? Mar 14, 2014 at 22:03
• Click the link that says topological skeleton. I will get some 3d screens tomorrow. For now I added an image very similar to what I am attempting to accomplish. Mar 14, 2014 at 22:12
• So why not just making tybes around all connecting lines and spheres on intersections? Mar 15, 2014 at 5:24
• Do you know an algorithm that does that and creates a mesh without any intersections? The result has to look good on the inside. Mar 15, 2014 at 6:43
• No idea whether this would suit your problem: You could render the skeleton into a volume, expand the skeleton in the volume by iteratively filling empty voxels which have filled neighbours, then extract the resulting surface (using e.g. marching cubes). Will this process be offline? Mar 15, 2014 at 9:47

One approach would be to use voxels as an intermediate representation.

1. Render the skeleton line segments into a volume
2. Expand the volume belonging to the skeleton by iteratively filling voxels whose neighbours belong to the skeleton
3. Extract the resulting surface using the marching cubes (or marching tetrahedra) algorithm
• I do have some (c++) code I could post which you could easily adapt to do step 1. Mar 16, 2014 at 10:50
• I think I'll try running a computation shader on a 128 x 128 x 128 volume to check each cube for the distance from the nearest line segment. if the distance is < radius I'll place a voxel there. Then I'll probably remove the insides by removing voxels whose neighbours are are not empty cells. That way I'll get the outside of the tubing. Then I need to figure out some good implementation of dual marching cubes. I hope I can figure this part out but for starters I guess voxels will be sufficient. Mar 16, 2014 at 11:44
• Ok - so you don't need to "grow" the skeleton. I guess you'll end up with a better surface your way. Do you need both inside and outside surfaces? Mar 16, 2014 at 12:30
• I need the inside.I want to procedurally generate game levels. Mar 16, 2014 at 12:40
• I think you can do away with the second step (removing voxels), and end up with a better surface if you store signed distance at each voxel. Set each voxel to min( distance_from_line[i] - line_radius[i] ) and you'll end up with an approximate signed distance field with -ve values inside the tunnels. Mar 16, 2014 at 17:28

Build shell mesh around every segment, feed them to some CSG processor, smooth resulting mesh.

• I thought about using carve I think it's also a reasonable solution. I need to start a blog about it and report my findings. Mar 17, 2014 at 8:08