# Archive for January 2nd, 2015

### OpenSCAD: Quantized Vertices

Posted by Ed in Machine Shop, Software on 2015-01-02

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:

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:

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:

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:

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/1024^{2}, in case you were wondering, which produces a 5% speedup in the geometry engine compared to the more human-readable 1/1000^{2}.

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

A very nice Christmas present, indeed!

Thanks, Marius…

## Blowback