Re: [rp-ml] STL files

Adrian Bowyer wrote:

> Well, there are a few completely CSG systems out there. But I suspect
> that it's actually impossible to write a guaranteed bug-free solid
> modeller (B-rep or CSG) in any machine that's Turing equivalent.

Yep - I agree. Finite precision is a major problem for CSG.

But in any case, the CPU demands for true CSG modellers are quite
outrageous for models of any kind of complexity. They almost always
end up converting the model to triangles or spline patches internally.

> If the file is always going to be triangles, then you store the genus of
> the object, a list of vertex coordinates, then a list of triangles, each
> one of which has six entries (in a cyclic order to define the
> outward-pointing surface normal); the first three are the vertices of
> the triangle, and the second three are the three other triangles across
> each edge opposite the corresponding vertex.

This is a variation on 'Winged edge topology' in which the edges
are what really defines the model and the triangles (or polygons in
general) are defined only by the edges they are made up of with the
vertex data being indexed by the edges. You can store models like
that using the PLY model format.

You need another constraint (to avoid Klein bottles) and that is
that the order of the vertices on one edge of a particular triangle
must run in the opposite order from the other triangle sharing that
edge.

> You can move about that structure without doing any global searching,
> and check it for topological solidity just from the triangle list and
> genus (all integers), completely ignoring the vertex coordinates. The
> only thing that can be wrong with it is if it self-intersects, which
> does require the coordinates to be interrogated to check, and reduces to
> the simple question, "Do any two triangles cut each other?"

Sadly, no - it doesn't.

How about when the triangles exactly line up such that four or
more triangles share the same edge. This could either mean
that two continuous surfaces intersected each other - or it
could be that you have (say) two cubes that happen to be
exactly touching down one edge. There is no easy way to tell
the difference - yet one is clearly illegal and the other is
not only legal - but also quite useful.

The 'winged edge' approach can help here by telling us which
pairs of triangles deliberately shared the edge - and which
ones fortuitously happened to line up along the same coordinates.
But there are still pathalogical cases where it'll kill you.

It is these kinds of nightmares that keep us 3D software folk
lying awake at night sketching lines in the air with our
fingertips!
Received on Thu Dec 07 09:33:34 2006