OpenSCAD: Quantized Vertices

Back when I started fiddling with 3D printed chain mail, the whole process from model to plastic worked wonderfully well. That continued with the larger sheets, but now, occasionally, the OpenSCAD model would produce weirdly sliced links. Depending on nothing repeatable, some links wouldn’t bridge correctly: the thread paths in the bottom layer across the gap would mysteriously stop just short of one pillar, return to the start, and leave an unsupported shelf that would, of course, fall into the gap.

Shortly before Christmas, I managed to get a consistent failure that manifested differently: upon loading the STL file, Slic3r would quietly perform dozens of automatic corrections that (sometimes!) produced bizarrely distorted results. Feeding a failing model into Meshlab showed an irregular assortment of “self intersecting faces”, highlighted in red:

Chain Mail Square Armor - open - 2x2 - Meshlab self-intersecting faces

Chain Mail Square Armor – open – 2×2 – Meshlab self-intersecting faces

Although all four outer links in that image come from the same OpenSCAD module with identical sizes, they don’t all exhibit the same problem in the (nominally identical) faces on each of their four corners. In fact, those faces come from the intersection of two square slabs, carefully sized and positioned to avoid creating coincident planes:

Chain Mail Link - Outer shape

Chain Mail Link – Outer shape

The central opening comes from a similar, slightly smaller, intersected-squares shape, but all four interior corner faces in each link show that they’re self-intersecting.

The STL looked fine in Meshlab, except for the highlit self-intersecting faces, so the geometry seemed OK.

When Slic3r autocorrected the “problems”, it apparently removed one vertex on the bottom surface of each bar, deleted the triangles connected to that vertex, then repaired the mesh to produce a delightfully symmetric pattern:

Chain Mail Square Armor - open - 2x2 - Slic3r corrections

Chain Mail Square Armor – open – 2×2 – Slic3r corrections

Although the links are resolutely symmetric, Slic3r seemed happy with the identical vertices at the other end of the bar.

Unfortunately, the resulting G-Code won’t produce good links:

Chain Mail Square Armor - open - 2x2 - first layer G-code visualization

Chain Mail Square Armor – open – 2×2 – first layer G-code visualization

So, shortly before Christmas, I filed an issue on OpenSCAD’s Github repository.

The ensuing discussion showed that Meshlab flags faces as “self intersecting” when they have different vertices, even if their values are numerically equal, as well as vertices that differ by teeny amounts. Slic3r applies slightly different criteria to vertices & faces when it automagically corrects “problems” in the STL file, so that Meshlab may:

  • Highlight faces that don’t bother Slic3r
  • Apply the same highlight to faces that cause horrible problems

I don’t profess to understand much of that and may have the details wrong, but, apparently, OpenSCAD formerly used quantized coordinates that ensured all vertices within a tiny volume would have the same numeric value. In particular, all three faces that meet at a common point would, in fact, have numerically equal coordinate values for that point. The STL file format consists of a list of separate triangles, each with three coordinates for each of the three axes, and (without quantization) it was entirely possible for each of the three triangles with a common point to have three very slightly different positions for that point.

In theoretic terms, quantized coordinates cause horrible problems during geometric manipulation, because numeric values that aren’t exact can make repeated transformations come out wrong; running an object through a transformation and it’s inverse might not yield an object identical to the original one.

In practical terms, it seems that slicers and STL repair algorithms can reach incorrect conclusions based on minute differences produced by floating-point operations and numeric-to-text conversions. Those differences depend on slight changes in position, rotation, and size, so doing anything to the model produces completely different results.

That notwithstanding, the day after Christmas brought a new OpenSCAD version that uses quantized coordinates. A bit of rummaging in the source shows that the 3D grid (defined in src/grid.h) isn’t all that coarse:

const double GRID_FINE   = 0.00000095367431640625;

STL files don’t carry units, so that could be in either millimeters (the Slic3r / RepRap convention) or inches (Sketchup, but we won’t go there). It’s exactly 1/10242, in case you were wondering, which produces a 5% speedup in the geometry engine compared to the more human-readable 1/10002.

With that commit in hand, all the chain mail links slice perfectly again.

A very nice Christmas present, indeed!

Thanks, Marius…


, ,

  1. #1 by Jason Doege on 2015-01-02 - 14:13

    They use floating point for this??? This seems like an opportunity to implement software that relies on integer multiples of minimum units.

    • #2 by Ed on 2015-01-02 - 14:25

      The mailing list has had some, let us say, spirited discussions about integer arithmetic, rational fractions, and exact-math stuff like that. As nearly as I can tell, the key problems revolve around what the supporting libraries can handle, what happens when you apply non-rational transformations (which everybody does), and whether any changes would produce meaningful results.

      So far, double floats seem to produce Good Enough Results for most purposes.

      I watch the compiler output scroll by on the portrait monitor in awe…

  2. #3 by Jason Doege on 2015-01-08 - 01:17

    I finally fired up my deltamaker last night. It printed the flexy braclet and the calibration cube with no fuss. Nice finish and reasonable accuracy (25.25mm x 25.25mm X and Y and 20mm Z). I was very surprised and how smoothly things went. My expectations were low. Tonight I tried my first custom part. I used OpenSCAD. I wanted to thank you for all the information you’ve shared, here. I modeled my part in 20 minutes and had the part printed and fit as of a couple of minutes ago. The first print fit perfectly. Now I just need to print with more infill for strength. So, question. What do you recommend for infill on a part that needs some strength? You can tell by my pictures here ( ) and here ( ) that I’ve over-engineered it a bit.

    • #4 by Ed on 2015-01-08 - 09:36

      Looks good to me! Welcome to the Bracket Makers Club…

      None of the stuff I build must withstand much force, so 20% infill suffices. I think we used more on the indestructible longboard electronics case, but that’s an outlier.

      I’d print that part on its side to route complete threads around the arch and prevent it from cracking off. You don’t care about the shape of the screw holes, because you’ll be running a drill through them anyway, and a washer under each screw head will keep the bracket from splitting from hole to hole. Bonus: no support material!