Monday, January 18, 2010

OpenSCAD Tip: Manifold Space and Time

While not quite as bad as some non-euclidean projective geometry, the geometry of 3D printed parts must be manifold and the spice must flow.

A 3D model is considered manifold if it is water tight and there are no holes in the geometry.While there are no obvious holes in the mesh below, at the point indicated it looks like the surface is not differentiable and is causing a problem.

Avoiding intersections like this will help ensure that your parts can be produced. Usually just moving the feature slightly will fix the problem.

Selecting Thrown Together from the View menu in OpenSCAD can also help trouble shoot problems. The patterned areas in the image above are indeterminate and will cause problems.

So, when performing composite solid geometry operations, it is important to remember that the piece you are subtracting must extend past the original part.


Robotbling said...

If you apply a smoothing operation to the mesh to increase its polygon count, would that help?

I Heart Robotics said...

Sometimes that will help, but usually its caused by the geometry being mathematically indeterminate. Floating point errors often causes geometry problems.

In python for example
>>> print repr(32.0/100.0)
>>> print repr((132.0/100.0)-(100.00/100.00))

So if you have two surfaces that are supposed to meet exactly, they may not.

I did try smoothing the mesh but OpenSCAD doesn't seem to do it consistently.

scale([1/100, 1/100, 1/100]) cylinder(h = (H)*100, r=(ID/2)*100, center = true);

Dominic Muren said...

While "watertightness" is a nice by-product of a manifold mesh, the real test of whether a mesh is manifold or not is that all edges must be shared by exactly two polygons (usually triangles). If we think about a hole (or a leak, in terms of watertightness) that would be a triangle with an edge used by only one polygon. But another way to make a non-manifold, but still technically watertight mesh is to take a manifold mesh and connect two arbitrary edges with a triangle -- that would create at least one edge shared by three polygons.

The computer has issues with this, because it can't decide what the inside and outside are, if there are multiple volumes enclosed by meshes.

In this case, it looks like you might have had an errant triangle, or an edge that didn't terminate correctly, because of how many edges shared that upper vertex. Making the step freed the vertex up.

Nice work on the part. I'll give it a test with my makerbot when she's up and running.

Don Bright said...

I think it may be possible that these are simply bugs in both CGAL and in OpenCSG... there doesn't seem to be a 'physical' reason that we shouldn't be able to print any of the stuff you have rendered above. . .

I Heart Robotics said...

It is not a physical problem, it is a mathematical problem.

Here is a better example in python
>>> print repr(1.0/3.0)
>>> print repr(1.0-(2.0/3.0))

Both of these numbers should be the exact same, but they are not due to the issues with floating point math. This is because most computers do math in base 2,

Which works out to something like 1/3 = 2^−2 + 2^−5 + 2^−6 + 2^−9
And dis-intuitively 1 - 2/3 does not produce the same series.

A longer explanation of floating point problems can be found here.

The other problem is having a singularity. I'm not sure this is clearer than the wikipedia example but this can perhaps be explained by considering a venn diagram. Consider two overlapping circles whose intersection is considered the solution. If the circles are tangent there is one solution at the point where they meet, however there is no area. So if you then try to subtract one circle from the other you need to remove the point without removing any area, which is undefined.

Unknown said...

It's not like floating-point roundoff errors can't be handled sanely. Even problems like solids touching at a corner can be handled in some reasonable manner, especially if the solids are both created from linear_extrude. And then, it is very easy to create examples that are clearly correct that OpenSCAD still insists are not. There are a lot of bugs and a lot of fixing to be done.