**Next message:**Jim Mallos: "Re: Solar in RP's future?"**Previous message:**Mike Brindley: "Re: STL validator ..."**Maybe in reply to:**Scott Nelson: "Stl slice algorithm"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

*> > 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/

**Next message:**Jim Mallos: "Re: Solar in RP's future?"**Previous message:**Mike Brindley: "Re: STL validator ..."**Maybe in reply to:**Scott Nelson: "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
*