List of Parts and Connections

[Cole]

I am trying to figure out how to take Lego model files and get a list of all parts and how they connect.  Ideally, I would get something akin to an edge list (https://en.wikipedia.org/wiki/Edge_list) so I can make a design structure matrix (https://en.wikipedia.org/wiki/Design_structure_matrix) showing how each part connects the others. 

I have been looking at stuff, and the files appear to just store each part at a location and the programs state whether they collide or connect. I see that a lot of that information is kept in binary form, or lists the relative location of each connection part (such as stud2). 

I am lost as to where to start. Worst case, I would have to do a giant for loop thing to check each part, the location of each other, and if it connects and how. That sounds computationally impossible for larger sets.

If you have any recommendations, please let me know.

If you're curious, this is one that I did manually. It is set 8045: the mini telehandler. You can see parts of the lift part and the fork.

[Basil Bader]

I have developed something similar recently. The code has three main parts:
1. Parsing the LDCad snap metas and converting them to a slightly different structure. This isn't difficult, it just took some time to fully understand the snap meta format.
2. Finding out which parts can interact (Broadphase collision). Each part has a bounding box. An AABB tree is built to efficiently find all the pairs where the bounding boxes intersect.
3. For each pair that intersects: Iterate through all combinations of connectors of both parts to determine which connectors are connected. This sounds computationally expensive, but most combinations can be ruled out pretty fast (cylindrical connectors must be colinear for example).

This method is pretty fast. I can compute a full connection graph for datsville in a few seconds on my i7-6700k. But the graph is too large to visualize with GraphViz.

Here's a visualization of a submodel of the Porsche 911 OMR model:
   

[Cole]

I have developed something similar recently. The code has three main parts:
1. Parsing the LDCad snap metas and converting them to a slightly different structure. This isn't difficult, it just took some time to fully understand the snap meta format.
2. Finding out which parts can interact (Broadphase collision). Each part has a bounding box. An AABB tree is built to efficiently find all the pairs where the bounding boxes intersect.
3. For each pair that intersects: Iterate through all combinations of connectors of both parts to determine which connectors are connected. This sounds computationally expensive, but most combinations can be ruled out pretty fast (cylindrical connectors must be colinear for example).

This method is pretty fast. I can compute a full connection graph for datsville in a few seconds on my i7-6700k. But the graph is too large to visualize with GraphViz.

Here's a visualization of a submodel of the Porsche 911 OMR model:

That's very cool! I'm surprised that Graphviz won't handle it. I manually made the 42052 helicopter from the instructions and networkx was able to process and present it just fine—about 1100 pieces.

Any advice on the snap meta part? I'm unsure what that is, other than seeing a few references to connectivity files. I've started looking at just the file tree with the idea being to examine intersections via alphashape collisions. Convex full would be faster, but that only works with some parts. In the end, even if it's time-consuming, it'll be quicker than making it myself lol

[Basil Bader]

Graphviz has a image width/height limit of 32768px for PNG images. SVG images do not have that limit, but I can't remember if I ever tried to export datsville as an SVG.

The snap metas work similar to the LDraw type 1 lines (subfile references). You will need the full subfile reference logic in your parser if you want to use the snap metas. I don't think that using the 3D mesh of the parts to determine which parts are connected to each other is easier than using the snap metas. There will be precision issues and if a connection isn't recognized you would either have to alter the 3D shape of the part or store additional connectivity information (which the snap metas already do)