Re: Stl slice algorithm

From: Gill Barequet (barequet@cs.Technion.AC.IL)
Date: Sun Jan 30 2000 - 11:50:00 EET


> > Mike Brindley wrote:
>
> 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).

Mike is right: the analysis applies after the topology info is reconstructed
(however when we use the big-Oh notation it also applies for the raw data).

But the implication is the other way around: V~=F/2 -> degree-6 vertices on
the average. The proof goes this way. Euler's formula indeed states that
V-E+F=2. (Where V is #-of-vertices, E - edges, F - faces [triangles].)
Assume F=n. In a valid stl file we always have E=3F/2, since each triangle
contributes 3 edges, and each edge is contributed twice. That is, E=3n/2.
Substitute in Euler's formula to get V=E-F+2=3n/2-n+2=n/2+2. (I.e., V~=F/2.)
[[Consider, for example, a cube. Here V=8, E=12, F=6, and indeed 8-12+6=2.]]
Since we have E edges, we have 2E edge endpoints. These endpoints are spread
over the V vertices. So on the average the degree of a vertex is
(2E)/V=(3n)/(n/2)=6, as claimed.

> > ("my algorithm" snipped)
>
> 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.

As a study of a comparison between methods for topological-info reconstruction
methods, it was never published. The sort-and-scan method is so well-known
as a folklore method, so I regard it as publically known and don't claim
for originality. It is described in one sentence in the first paragraph of the
4th section of my paper
   G. Barequet and M. Sharir, Filling gaps in the boundary of a polyhedron,
   Computer-Aided Geometric Design, vol. 12 (2), pp. 207-229, March 1995.
The web server was indeed down during the weekend. Now it's up and running.

Gill.

---------------------------------------------------------------------------
Gill Barequet, Ph.D. Phone: +972-4-829-3219
Faculty of Computer Science Fax: +972-4-822-1128
The Technion---IIT E-mail: barequet@cs.technion.ac.il
Haifa 32000 WWW: http://www.cs.technion.ac.il/~barequet
Israel
                                "Life is NP-Hard." (-)

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



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