# Re: Stl slice algorithm

From: Mike Brindley (brindley@ece.orst.edu)
Date: Mon Jan 24 2000 - 20:44:34 EET

Scott Nelson wrote:
>I'm curious about the mathematical algorithm used to generate slices through
>an stl file.
>I would love to see some psuedo-code showing the processes necessary to
>accomplish this. If you have any ideas, please let me know.

Since no one else has answered, I'll jump in.

3D Systems used to use a brute force technique, which is why objects
needed to be sliced before starting the build - a process which took
considerable time (hours). The STL file is a collection of triangles
with no information on the relationships between these patches of
the surface. So, the algorithm would create a list of all the line
segments making up the intersection between the facets and the
slicing plane. Then, it would search the line segments, matching up
the endpoints to form the boundaries of the layer. Note: this is
speculation based on some clues I read. I do not know if they
are still using this same algorithm.

Rock and Wozny published the other basic algorithm in the proceedings
of the Solid Freeform Frabrication Symposium (Austin, Texas, USA) in
the 1990 to 1992 time frame (I believe that Steven Rock subscribes to
this list). I also made up (independently) the basics of the algorithm
in a job interview in 1992 (I felt that this basic algorithm is so
obviously the right way to do it that I was puzzled by the hints I read
about 3D Systems brute force approach). Essentially, you reconstruct
the topology of the surface (the relationships between the facets) by
matching up the vertices. During this reconstruction process, you
keep track of which facets share an edge. Then, to slice, you find
a facet/edge which intersects the slicing plane and walk around the
surface hopping from facet to facet (keeping track of the slicing
plane intersections with the edges of the facets). When you are back
at the starting facet, you have one complete path (or outline). Then,
you continue searching for facets which intersect the slice plane and
which you haven't already used to make the previous paths/outlines.
Continue in this manner until you have used all the facets which intersect
the slice plane. You now have one or more paths/outlines which form
the boundaries of the slice.

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'.

--> Mike Brindley brindley@ece.orst.edu Corvallis, Oregon, USA
"I take unanimity on any difficult topic as a danger sign."
- P. J. Plaugher