3
\$\begingroup\$

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. Inflated shapes and skeleton

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.

enter image description here

Improve this question
\$\endgroup\$
6
  • \$\begingroup\$ Can we have some screenshots please? \$\endgroup\$
    – ashes999
    Mar 14, 2014 at 22:03
  • \$\begingroup\$ 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. \$\endgroup\$
    – AturSams
    Mar 14, 2014 at 22:12
  • \$\begingroup\$ So why not just making tybes around all connecting lines and spheres on intersections? \$\endgroup\$
    – Kromster
    Mar 15, 2014 at 5:24
  • \$\begingroup\$ Do you know an algorithm that does that and creates a mesh without any intersections? The result has to look good on the inside. \$\endgroup\$
    – AturSams
    Mar 15, 2014 at 6:43
  • \$\begingroup\$ 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? \$\endgroup\$
    – GuyRT
    Mar 15, 2014 at 9:47

2 Answers 2

Reset to default
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ I do have some (c++) code I could post which you could easily adapt to do step 1. \$\endgroup\$
    – GuyRT
    Mar 16, 2014 at 10:50
  • \$\begingroup\$ 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. \$\endgroup\$
    – AturSams
    Mar 16, 2014 at 11:44
  • \$\begingroup\$ 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? \$\endgroup\$
    – GuyRT
    Mar 16, 2014 at 12:30
  • \$\begingroup\$ I need the inside.I want to procedurally generate game levels. \$\endgroup\$
    – AturSams
    Mar 16, 2014 at 12:40
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – GuyRT
    Mar 16, 2014 at 17:28
1
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – AturSams
    Mar 17, 2014 at 8:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .