From: steve <sjbaker1_at_airmail.net>

Date: Tue Nov 07 2006 - 10:34:01 EET

Date: Tue Nov 07 2006 - 10:34:01 EET

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

*
This archive was generated by hypermail 2.1.8
: Tue Jul 21 2009 - 10:27:52 EEST
*