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\$
  • \$\begingroup\$ Can we have some screenshots please? \$\endgroup\$ – ashes999 Mar 14 '14 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 '14 at 22:12
  • \$\begingroup\$ So why not just making tybes around all connecting lines and spheres on intersections? \$\endgroup\$ – Kromster Mar 15 '14 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 '14 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 '14 at 9:47
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\$
  • \$\begingroup\$ I do have some (c++) code I could post which you could easily adapt to do step 1. \$\endgroup\$ – GuyRT Mar 16 '14 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 '14 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 '14 at 12:30
  • \$\begingroup\$ I need the inside.I want to procedurally generate game levels. \$\endgroup\$ – AturSams Mar 16 '14 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 '14 at 17:28
1
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\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 '14 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.