Constructive Solid Geometry on procedural pipes

[CHPedersen]

Dear all,

First off, sorry about this huge text, but it was important for me to explain the problem properly. :)

I have a pretty hairy geometry question I've been pondering for a while. I'm developing an application that involves the generation of some pipes. The pipes consist of meshes created at runtime, two meshes per pipe (one with triangles facing out, the other with triangles facing in, so that it doesn't become invisible from neither the inside or outside). The meshes are drawn around a line in space defined by a series of points that are read into the program from an XML file. Think of them as subway tunnels, basically.

Occasionally, the tunnel might have sidetracks that split apart from the main pipe. Sticking to the subway analogy, this is just a connecting tunnel. The sidetrack is defined by a series of points just like the mainpipe, and then a certain position that indicates where it connects to the main pipe.

At the moment, I'm simply drawing the sidetrack with the exact same algorithm as the mainpipe, with no regard to intersecting geometry. From the outside, this looks fine:

The sidetrack seems to just blend into the mainpipe seamlessly.

But when you move the camera closer so that the near clipping plane cuts open the geometry, the fact that they are simply drawn on top of one another without any kind of attention to intersection becomes painfully obvious:

This is a problem, since I need the user to be able to traverse the inside of the pipes and see where they split apart properly from the inside as well. This is a Constructive Solid Geometry problem, i.e. it involves the merging of two parametric surfaces. These problems aren't usually trivial, and I've sweated over how to solve it for a while, and I have a few ideas, but I'd like your input on how to best do it, which is why I'm posting the problem here. :)

My idea is to try and generate a voxel grid surrounding each pipe, and then perform set operations on them to remove the voxels that overlap in space, that is, the voxels from a sidetrack that end up inside the mainpipe's geometry. After that, I would reconstruct the triangle mesh using some implementation of the Marching Cubes algorithm.

So I guess the question is two-fold. First, can you think of a better way to accomplish the merger of this geometry where the pipes intersect? Second, if not, do you know of a library for Unity that specializes in constructive solid geometry, or am I on my own? Thanks in advance!

• Christian

[sneftel]

This actually sounds like a pretty straightforward CSG problem. It's all about cutting planes.

Your pipe network is made up of edges (in the graph-theoretical sense of the word). The presence of an edge in your pipe network leads to the creation of a single pipe mesh. This pipe mesh can be thought of as an infinite cylinder, collinear in its center line with the pipe edge, which is cut by a series of planes (aka boolean intersection with half-spaces). For instance, a single pipe edge would lead to a single cylinder, with two half-planes cutting it (one for each end).

If a pipe just ends, the cutting plane on that side is perpendicular to the pipe. (I assume -- that would be the natural way to do it.)

If two pipe edges meet at a vertex (again, in the graph-theoretical sense), they are each cut by a cutting plane is (a) parallel to the cross product of the two pipes' edge vectors, and (b) also parallel to the bisector of the two pipe vectors. So if AB and AC are the normalized vectors along two pipes which meet at A, they will be cut by a plane which contains A and has the normal `(AB + AC) x (AB x AC)`.

If you've got a bunch of pipe edges meeting at a vertex, there will be a cutting plane for each pair of edges. That cutting plane will affect only those edges. So for AB, AC, and AD meeting at A, B will be cut by the AB-AC and AB-AD cutting planes, but not by the AC-AD cutting plane.

Once you have all the cutting planes for a pipe, consider the pipe in terms of the edges (in the mesh sense) which run from one end of the pipe to the other, parallel to the center of the pipe. Each one has its own extents, determined by intersecting the potentially infinite line with all the cutting planes for that pipe.

Once you have the extents for all those edges, just connect them up in the normal cylinder way, and you have your pipes.

A degenerate case to consider: some of those lines may have zero extents (corresponding to a pipe which, due to its short length and oblique cutting planes, no longer goes all the way around), which may require some clever stitching.

Note that this won't entirely eliminate gaps if the pipes are not all coplanar, since you need to choose where to start going around the rim of the pipe. Having more radial subdivisions will minimize this problem.

Let me know if you have questions about any of this.