Generating a procedural mesh from a 3D graph

Question

Imagine a cave system that is represented as a graph of vertices and edges, with each vertex having a position in 3D space, and each edge representing a tunnel. Or perhaps the edges represent roads and the vertices represent corners and intersections. The point is that we have a graph of geometric data and we want be able to extrapolate arbitrary structures around that data. What algorithm could generate a mesh to render these things in 3D?

Here is an excellent Youtube video on a similar topic: Unite 2015 - A coder's guide to spline-based procedural geometry. It deals with a simpler case where we only have to go from one point to another with no branching, but surely similar concepts would be of use in rendering a graph-based 3D structures.

Answer 1

1. Start with creating circular caves

   you can use Smoothly connecting circle centers as a start point. Then add some randomness and more cave like profile to it by changing the circle to some different shapes. You can also modulate the radius (or width) based on distance to graph intersection point. Do not forget to store also UV mapping for proper texturing later on. That should be simple you can use the cylinder axis as U and the angle parameter of the "circle" as V. This can be also used as TBN matrix for bump/normal mapping.

   The main problem with this will be the graph intersection points. You will need to create a mesh that smoothly connects the intersecting tubes for example by some cave "room". It should be doable as the vertexes should be ordered by parameter angle of the circle so you know which vertexes are on which side of each tube and can connect them programaticaly without any horrible effort (even with proper polygon winding).

   This way you should be able to generate the geometry.

2. add objects and features

   for that you can be either fully random or use some physical approach like I did here Random Island generator for creating biomes. So you can add/exploit some rules like how far are you from enterance or water or how deep are you to generate vegetation and stuff.

3. generalize

   When put #1,#2 together try to code it so as input is some specific seed per cave area and your graph. This way you can generate each part of cave separately and repetitive. Just add this seed to your graph.

   To make smooth transitions you should generate also the neighbor cave areas and interpolate the connection between them.

   Another option is to have uniform cave environment without biomes and add stuff to the cave area interior much more then to the edge areas so at the joint points there will be not too much change at once.

[Notes]

Now you obviously got the graph as an input but just in case you do not you can generate that randomly too see:

• Polar Coordinate Map Generation

To make the cave walls more realistic you can use Diamond&Square (from the Island generator link) to modulate the radiuses just make sure the averaging is done circularly in angular parameter direction so the resulting map is seamless when added to the cylinder surface.