**Next message:**Mike Brindley: "Re: STL validator ..."**Previous message:**Marshall Burns: "Re: Solar in RP's future?"**In reply to:**Gill Barequet: "Re: Stl slice algorithm"**Next in thread:**Gill Barequet: "Re: Stl slice algorithm"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

Gill, as usual, I found you comments quite interesting!

Gill Barequet wrote:

*> Mike Brindley wrote:
*

*>
*

*> > (... slicing - snipped ...)
*

*> >
*

*> > The time consuming part of the topological slicing just described is
*

*> > reconstructing the topology of the surface, normally an O(n^2) algorithm.
*

*> > Using various well known techniques to speed up searches (trees, hashing,
*

*> > etc.) this algorithm becomes O(nlog(n)). The topology reconstrucion
*

*> > can be done ahead of time (before building starts), enabling 'slice-on-
*

*> > the-fly'.
*

*>
*

*> Here are my two cents. Many years ago I compared many methods for
*

*> reconstructing the topological info (adjacencies of polygons) of a soup
*

*> of triangles (aka stl file). In principle (asymptotically, in the expected
*

*> case) the hashing approach should be the best, because under the assumption
*

*> of good hashing you expect to waste constant time per operation (insert,
*

*> find [delete is not needed here]), summing up to an O(n) expected-time
*

*> algorithm. However, the involved constant of proportionality is too high:
*

*> the hashing approach will eventually win for high-enough values of n, which
*

*> are larger than any file processed in practice. My experiments (again, about
*

*> 10 years ago), led to the conclusion that the simple sort-and-scan approach
*

*> is the best for up to even millions of triangles. Let me explain in short
*

*> this approach. Assume we have n triangles. Then we have 3n edges, and
*

*> Theta(n) vertices (according to Euler's formula). First you need to identify
*

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Just a clarification. The STL file directly specifies n triangular facets,

so we have 3n edges and 3n vertices. The Euler formula (V-E+F=2, where V

is the number of vertices, E is the number of edges, and F is the number

of faces -> 'n' in this discussion) only applies after the topology has

been reconstructed (and the resulting object is error free -> water-

tight and 2-manifold). Analysis for a valid, error-free STL object

reveals that, after topology reconstruction, the resulting object will

have exactly 1.5 times as many edges as faces (E/F = 3/2). And for

objects with a large number of faces (and a couple of other assumptions),

each vertex will be shared by about 6 faces (and edges) on average. This

leads to the number of unique vertices being aproximately 1/2 the number

of faces (V ~= F/2). I did this analysis some years ago when I was

writing software to deal with STL files (I wanted an estimate of how

large an STL file the software could handle with the memory on the

computer).

*> repeating vertices. Sort the vertices according to lexicographic order (say,
*

*> according to keys X, Y, Z, in this order). This is an O(n log n)-time step.
*

*> Now scan the sorted list in O(n) time and identify all duplicates. The same
*

*> approach works for finding adjacencies. Pile up all the 3n edges, keeping the
*

m

*> as pairs of 2 point indices (smaller index first; keep also a flag indicating
*

*> edge direction). Again, sort all edges in lexicographic order in O(n log n)
*

*> time, scan the sorted list in O(n) time and find all adjacencies. Nothing
*

*> of the above is new. I just claim that according to my experiments the
*

*> described approach is the fastest. Trees and friends give the same
*

*> functionality (and comparable running times) but require more overhead.
*

I'll keep this algorithm in mind for possible future use. Was your study

published? I tried your website, but the CS Department web server was

not responsing; I'll try again later.

--> Mike Brindley brindley@ece.orst.edu Corvallis, Oregon, USA

"I take unanimity on any difficult topic as a danger sign."

- P. J. Plaugher

For more information about the rp-ml, see http://ltk.hut.fi/rp-ml/

**Next message:**Mike Brindley: "Re: STL validator ..."**Previous message:**Marshall Burns: "Re: Solar in RP's future?"**In reply to:**Gill Barequet: "Re: Stl slice algorithm"**Next in thread:**Gill Barequet: "Re: Stl slice algorithm"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

*
This archive was generated by hypermail 2.1.2
: Tue Jun 05 2001 - 23:02:42 EEST
*