Implementing a Convert BoT to Pipe framework for BRL-CAD

[foposseleger]

hello Guys,

In the design phase of an aircraft, component positions and locations are continually in flux leading to a lag in models of line routing. Typically when lines are received from an aircraft manufacturer to the vulnerability analyst, they may not terminate at the component(s) they were meant to connect to. Therefore, when importing these lines from high-end CAD packages such as Catia or Pro-E into BRL-CAD, they need to be re-routed so that they reflect the aircraft systems accurately and eliminate any overlapping issues. Currently these lines are imported using an intermediate format such as STL, which is a facetted geometry. In BRL-CAD this becomes a "Bag-of-triangles" (BoT) solid which cannot be edited with any efficiency. It is very desirable to be able to import these lines using BRL-CAD native geometry via the pipe solid. I would someone familiar with CAD to assist me in explaning how the converter works and how it could be done. I can do the coding its just understanding the problem generally here.

Thanks,
Leger

[stahta01]

I suggest posting to this sub-forum; it requires paying for help.
Projects and Job Recruitment

Tim S.

[foposseleger]

I just want to know the mathematics behind converting a stl file to a primitive like a pipe. I just wish someone like @Nominal Animal could help me here.

[laserlight]

I'm moving this to Tech Board first in case someone really is able to give a suitable explanation with the given info, though it does sound like you may need to hire someone.

[Nominal Animal]

Tim S. and Laserlight are quite right. You'll probably have to hire someone.

The problem can be stated quite simply:

We currently cannot import pipe-like structures from commercial programs, except as triangular meshes. Triangular meshes work, but cannot be sanely edited (as pipe-like structures) in BRL-CAD.

The optimal solution is to have the commercial programs and pipe rerouting applications export the data as pipe-like structures, instead of triangular meshes.

Obviously, the companies behind these software packages are not going to help with that, because it would increase competition, and they are all about software lock-in, not competition or user needs. (After all, if they were, there would be no demand for projects like BRL-CAD or OpenSCAD..)

I'd say you're completely screwed there. Even if you find a solution, these companies are ready to do quite extensive changes to their output formats to avoid widespread use.

---

A completely separate problem, but which just happens to also solve the above problem, is the computational geometry problem of approximating triangular meshes describing pipes and pipe T- and Y-joints, using solid geometry pipe structures instead. This has been in the BRL-CAD wish list since 2012 (here), and is currently listed in the BRL-CAD GSOC/Project Ideas page.

(However, I'd like to point out how silly this is. The original programs obviously model the lines and flows using data structures similar to pipes, not as triangular meshes. [Fluid analysis often requires some sort of finite element cell meshing, but I bet they are formed as needed, from the original pipe structures, instead of always describing the pipes as meshes.] Doing two lossy conversions makes just no sense to me, especially since the intermediate representation requires orders of magnitude more data, than the original or desired final representation. Just fix the actual programs instead! Oh, you can't? Well, switch to programs that let you do what you need to do, instead of working around them. Just because they are commercial and well respected, does not mean they are really worth the workarounds. If there are no alternatives, then spend the money to get proper tools done.)

BRL-CAD has a pipe primitive, which takes a list of vertices the pipe axis passes through, with inner radius, outer radius, and bend radius for each vertex also specified. Note that there have been reports (crashes) when the primitive is used, so I'm not certain how reliable or well-tested the primitive is.

This problem shares certain interesting properties with another of my favourites, angular momentum cancellation for nanocluster simulations. (In molecular dynamics simulations, increasing temperature in a simulation containing nanoclusters, often results in additional rotation, instead of atomic Brownian motion. Instead of heating up, the nanoclusters start rotating. In theory, you can just find out the axis of rotation and angular velocity (or acceleration), and substract it out. In practice, it's much more difficult, since the nanoclusters are not rigid. In fact, even the nanoclusters themselves may be in flux, adding or losing atoms continuously; you may not even be able to tell which atoms belong to the nanocluster, and which are part of the surrounding vapor. Most physicists just punt, and use a different model (extra degree of freedom, usually) for temperature control, to avoid the angular momentum issue completely.)

Both of these problems have a symmetry "axis", with a point cloud surrounding that axis -- except that the "axis" itself is a vague concept, and may even branch (T and Y joints) in this case. In many ways, the pipe case is easier, since the mesh provides the vertex connectivity graph.

(The nanocluster case is similar to if the pipe mesh data was modeled from old, rusted pipes; with varying thicknesses, and sometimes even patches, included in the data. With no metadata to indicate them, of course.)

My intuition (based on very limited experience!) says that this is very solvable problem, although it would require a lot of effort.

I'd start by unraveling the meshes.

Look at the triangular mesh connectivity graph. Given a specific vertex, the circuit with the shortest 3D circumference (sum of Cartesian edge lengths) containing that vertex, such that you cannot short-circuit/bypass any of the vertices in the circuit, is a cross section of the cylinder the mesh approximates at that point. (The circuit obviously has to have more vertices than the maximum number of sides in the vertex mesh polygons; otherwise you're just looking at a single polygon.)

Such polygons are the shortest ones containing that vertex, that circle the cylinder/pipe axis (the vertex mesh approximates) at that point. (I think. I'd certainly verify, and probably also ask someone better versed in graph theory and cycles in particular, before relying on that. Even if my description here is incorrect, I'm completely sure there exists a relatively straightforward way to analyse the mesh to obtain the roughly-cross-sectional polygons. Those are the key here.)

Obviously, you can also determine the order of those polygons from the connectivity graph.

The above will give you a stack of not-exactly-flat-but-close, almost-circular polygons, forming the approximate cross sections of the pipe. (The inner mesh will correspond to the pipe inner surface, and outer mesh to outer surface. Because the 'pipe' primitive can only describe pipes with symmetric walls, you can/have to assume the cross sections are coaxial/concentric.)

(If the mesh is very coarse, it will not model a pipe, but a twisted polygonal rod. If such data is prevalent in practice, I'd also consider a completely different approach: sweeping the meshes with spheres [or cylinders, in practice]. It will be a lot slower approach, although there are lots of mathematical tricks you can do to make it faster. I've done something similar to estimate molecular volumes, by "scanning" the molecule from the outside using a monomolecular gas -- by not trying to estimate the molecule volume, but by estimating the volume it would displace/exclude, if surrounded by a monomolecular ideal gas. There, graphing the volume as a function of the displaced gas atoms, yields useful information about the geometric properties of the molecule. Here, the sphere centers and radiuses form a set of intermediate data, to which the pipe parameters are fitted to.)

At joints, the mesh gets silly. I'd personally model everywhere else first, and then extrapolate the joint properties last, using the mesh vertices as helpful point cloud data only. (For example, for a T or Y joint, all three legs of the joint tend to be straight. The point closest to all three axis vectors is most likely the joint point. Another option is to use the leg information to construct a prototype joint, and compare the joint prototype to the mesh data, adjusting the parameters to obtain the best fit.)

Any small-scale features at joints -- say something like the nooks used in old sewers near tight bends, causing turbulence in the flow, keeping the bend clean from debris -- are always lost, but that should not matter here anyway: the 'pipe' primitive cannot model them anyway.

Overall, I think it should be quite achievable to implement this -- triangular mesh to pipe conversion -- either as a BRL-CAD command, or as an external utility. A lot of work, but good results are certainly achievable.

Unfortunately, every use for this I can think of, is in commercial industry (aviation, process engineering, et cetera) with zero benefits to hobbyists.

Personally, I love to teach and help others learn.
(And obviously I'm very easily manipulated by flattery, too. Well done.)

However, I'm not at all keen on doing massive amounts of free work, just to help a commercial entity increase their profits. (Specifically: I am personally not at all interested in doing this, neither for free, nor as a paid work regardless of the pay. The theory is interesting to me, but working with BRL-CAD and having no use for this, makes the actual implementation work really dull.)

(Also, compared to any serious developer in the BRL-CAD community, I'm a newbie. I think I have some experience in computational geometry to describe a couple of ways how one might approach the solution, and I've got such a huge ego I believe I could do this myself if I was interested in it.. which makes me believe there are lots of developers out there with the necessary skills. I'm hoping this wall of text will help you determine if a developer candidate has those skills, really.)

You guys have the money to hire a developer to implement something like this.
Better yet, you could easily pool some funds and hire a developer to add the functionality to BRL-CAD -- you know, leverage the free software paradigm. You'd not only get at least some kind of a say at how the functionality should work (making it compatible with your work flow), but also having other users to voice their opinions would mean it would be likely the functionality would stay useful to you, even if your use cases were to change.

Making it a Google Summer of Code Project idea reeks of exploitation to me.

I think my stance is pretty typical of FLOSS developers, so I'd say it is unlikely you'll find anyone doing this for free. Any student capable of implementing this (as a GSOC project) is easily capable enough to be hired as-is, and since there are no hobbyist use cases I can see, there just aren't capable developers that would implement this just because they have a use for it or a keen interest in it themselves. After all, that's why many advanced projects and utilities get made; just look at Graphviz for example. It is arguably better than any commercial alternatives, and even the scientific background it is based on is well listed there.

Anyway, good luck with your efforts, whatever path you choose.

[MutantJohn]

Wait Nominal, isn't shifting from a bag of triangles to a pipe structure literally the same thing as just using an edge structure for triangular mesh in the first place? Normally, you'd just use the simplex as the mesh primitive. Ooh, look all the fancy lingo I learned.

But basically, you use the shape itself as the primitive data structure in the mesh. So isn't converting from a BoT the same thing as shifting from the simplex to an edge? That sounds super duper easy, actually.

I mean, I don't know how to navigate a pure edge mesh but that's not the point, a triangular mesh is nothing but edges so it's possible.

[Nominal Animal]

Wait Nominal, isn't shifting from a bag of triangles to a pipe structure literally the same thing as just using an edge structure for triangular mesh in the first place?

No. Consider a pipe with inner radius 0.9, outer radius 1.1, extending from origin to x=0,y=0,z=10. The pipe structure describing this is

pipe 2   0 0 0  0.9 1.1 0   0 0 10  0.9 1.1 0

i.e. two nodes, first at (0,0,0) with inner radius 0.9 and outer radius 1.1 with zero bending radius; second at (0,0,10) with inner radius 0.9 and outer radius 1.1 with again zero bending radius. (I may have botched the exact syntax, as I haven't actually used the pipe primitive in BRL-CAD.)

A more complicated pipe or tube path requires only more points sampled along the pipe axis, each sample containing one vector and three lengths (radiuses). The important point about using such a structure should be obvious: if you wish to move (reroute!) the pipe, you only need to relocate or resample the points along the pipe axis.

(Constructive geometry for pipes is simple. To join, you first add together all the joined pipes' outer volumes, then substract all the inner volumes. This also corresponds to milling out the join from a solid chunk of material, especially if the pipe axes are straight in the joint region.)

If you have a bag-of-triangles or triangle mesh, you have one mesh describing the inner surface of the pipe, and one mesh describing the outer surface of the pipe. You don't know where the pipe axis is, what the pipe radius is, only the two surfaces approximated by the triangle mesh. You basically have two sets of vertices,

inner_x(u,v) = 0.9*cos(u*Pi*2/umax)
inner_y(u,v) = 0.9*sin(u*Pi*2/umax)
inner_z(u,v) = 10*v/vmax

outer_x(u,v) = 1.1*cos(u*Pi*2/umax)
outer_y(u,v) = 1.1*sin(u*Pi*2/umax)
outer_z(u,v) = 10*v/vmax

and you don't know the exact (u,v) values for each vertex, and not even that something like the above formulas were used to define the vertices. The problem is that for editing, the original pipe properties must be gleaned from the vertex data.

Nothing trivial here. (Assuming I understood OP correctly, of course.)

You can obviously do things like fluid dynamics based on the triangle meshes -- using the inner mesh to construct quad cells should be nearly trivial --, but you cannot move or edit the pipe.

You can edit the pipe described by the bag of triangles via deformations, but it will not retain the pipe properties -- in particular, the inner and outer radiuses. You do that with e.g. hydraulic fluid lines, and your model is no longer valid: constrictions or expansions along the pipe affect the flow speed and pressure a lot.

I fail to see any reason why you'd think any of this is super duper easy, but then again, maybe I completely misunderstood the original question. I don't think so, though.

[foposseleger]

Thanks very much, for the response. Will get into it.

Cheers!
Nyah

[foposseleger]

Hi Nominal Animal,

I'll like to implement this project for this year's GSoC for BRL-CAD; I really found it hard to understand in the first place, but with your explanation I can an idea on what it's all about and would be willing to do what it takes to implement this converter for this year's GSoC. I'll try to finish my project proposal and give you the link to review and then submit on google-melange. I'll contact you if I run into any trouble.

Thanks very much @Nominal Animal @Mutant John.

Cheers!
Leger

[foposseleger]

Hi Nominal Animal,

Here is the link to my proposal on BRL-CAD wiki; User:Foposseleger/GSoC 2014 proposal - BRL-CAD
I'll love to have some further explanations and links on how to better understand this problem for my GSoC project. I really like this project and will be able to do what it takes to execute it.

Thanks very much @Nominal Animal for the assistance

Cheers!
Leger

[MutantJohn]

Ew, why would I ever want to build something out of pipes?

Like, I get meshing. If tetrahedra aren't good enough, use a polyhedral mesh. I mean, is there anything actually better at fluid simulations than a Voronoi tessellation? And if you know, please tell me. If it's not as geometry focused I guess that's okay but I'm really hoping it is.

I'm just curious, why a pipe over a tetrahedron?

[Epy]

Ew, why would I ever want to build something out of pipes?

Like, I get meshing. If tetrahedra aren't good enough, use a polyhedral mesh. I mean, is there anything actually better at fluid simulations than a Voronoi tessellation? And if you know, please tell me. If it's not as geometry focused I guess that's okay but I'm really hoping it is.

I'm just curious, why a pipe over a tetrahedron?

they're talking about converting a triangle representation to a CSG representation, basically rebuilding a CAD model from triangles so the model can be edited

[MutantJohn]

But triangulations can be deformed as well, assuming 'edit' implies a deformation or reformation.

Eh, I don't know what I'm talking about but I'll definitely check out the wiki page on CSG so pardon me if I speak with my foot in my mouth.

[Epy]

I think you're over thinking things. They're wanting to take an STL file and basically turn it into BRL-CAD format which is represented in whole objects instead of triangular faces.