**Next message:**Rod Gentry: "Looking to buy a Sanders ModelMaker"**Previous message:**Guy.Bourdeau@coulter.com: "Re: 3D Systems product suggestion address"**In reply to:**Scott Nelson: "Stl slice algorithm"**Next in thread:**Anshuman Razdan: "RE: Stl slice algorithm"**Reply:**Anshuman Razdan: "RE: Stl slice algorithm"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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

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

**Next message:**Rod Gentry: "Looking to buy a Sanders ModelMaker"**Previous message:**Guy.Bourdeau@coulter.com: "Re: 3D Systems product suggestion address"**In reply to:**Scott Nelson: "Stl slice algorithm"**Next in thread:**Anshuman Razdan: "RE: Stl slice algorithm"**Reply:**Anshuman Razdan: "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:41 EEST
*