STL format MISINFORMATION (long)

From: Stephen Rock (Rensselaer  Polytechnic Institute)
To: RP-ML
Date: Monday, October 3, 1994
Subject: STL format MISINFORMATION (long)
           *** STL FORMAT DISCUSSION MISINFORMATION ***

A colleague recently made me aware of a discussion taking place 
on this mailing list regarding STL format inadequacies which contained
some misinformation about an alternative format (RPI format) concept 
advanced in a paper titled "A Flexible File Format for Solid Freeform
Fabrication", by Stephen J. Rock and Michael J. Wozny, which appeared
in the 1991 Solid Freeform Fabrication Symposium Proceedings.
 
Mike Brindley writes:
> I haven't seen those other file formats.  Do you have any 
> references?  The only one I've seen discussed is Rock and Wozny's
> RPI format which is exceeding complex.  

It's clear that I need to correct some misinformation circulating
about this work.

(1) The RPI representation presented IS NOT EXCEEDINGLY COMPLEX, 
    and a provision is made for writing data as 
    informationally primitive as found in the STL format.
    Section 2.2 of the paper states, "In the simplest case,
    only a vertex list and face list are provided.  The vertex list 
    is referenced directly by index values in the face list."
    
Brindley states:
>...I got upset enough with STL files one day that I sketched 
>out a basic format which used the list of vertices followed 
>by the faces referencing the vertex list. ...
    
    This sounds like the same thing to me.?

(2) The RPI format paper advanced the idea of imbedding a 
    defining schema within the data itself.  This provides 
    entity tags, which Brindley appears to advocate:

Mike Brindley writes:
>My format hasn't been used (yet).  ...
>                         ... It is also a tagged data format, taking
>care of the issue of adding multiple objects in a file.  The tagging
>also makes it easily extendible, so in the future it could include
>more complicated things like NURBS and CSG.  Adding support for
>polygonal (planar) faces instead of just triangles is easy and
>I have some notes on it.

    However, along with entity tags, the RPI format specifies the 
    data type associated with the tag.  This allows a post-processor
    completely unaware of a particular tag id to skip select information
    but continue to process the remainder of the file.  This is useful
    (nearly essential) for forward compatibility as new capabilities 
    and processes evolve.  Others have recognized the benefit of
    combining data type information within data files (IBM's 
    DataExplorer).

    An abbreviated example of the RPI format follows for clarification:
     PROCESSDATA 2 PROCESS STR * SLS SLA
     PROCESSDATA 1 PART_NAME STR * example.rpi
     FACETSOLID 1 INDEX INT * 1
     VERTS 3582 INDEX INT X DBL Y DBL Z DBL *
     1 83.6787 121.7 27.7256
     2 84.3622 121.356 28.2707
     3 84.2698 122.023 27.5492
     ...
     3580 125.606 100.531 81.6959
     3581 122.387 95.68 83.1261
     3582 122.708 106.524 82.3616
     FACES 7160 INDEX INT V1 INT V2 INT V3 INT F12 INT F23
     INT F31 INT *
     1 3483 3482 3480 1792 1793 1791 
     2 3350 3348 3347 1794 1795 1796 
     3 2387 2594 2592 1797 1798 1799 
     ...
     7158 6 4 2 7125 1790 7149 
     7159 5 1 4 7139 1790 7127
     7160 3 2 1 7150 1790 7138 
     FACETSOLID 0
    Please see the SFF91 paper for more detail.

(3) The RPI format does allow more complex representations to be 
    stored (limitless, based on the preceding discussion).  The choice
    to store a more complex representation which includes model
    topology is basically an economic decision--trading processing time
    necessary to reconstruct model topology against increased storage
    costs which accompany a more informationally rich model.  When
    actively working with a model, I prefer to operate on the richer
    file.  (My time is worth more than disk space -- I haven't
    found a way to buy a 25th hour in a day...)  

(4) The size reductions reported in this paper are based only on
    facet models (all in ASCII format).

Mike Brindley writes (replying to a comment by Chuck Krischman):
>I thought that the RPI format was doing just the opposite; by using
>primary representations of the object (CSG, NURBS, etc.) they condensed
>they file while increasing the calculation burden on the RP machine
>software (slicing, etc.) by a few orders of magnitude.  The paper
>makes a big point of how much smaller thier files are.

    Reductions are achieved by eliminating the repetition of keywords
    found in the ASCII STL file and replacing the redundant vertices 
    with a list of unique vertices.  Very little discussion, and no
    storage requirement results, were presented in the paper
    for CSG based models. Even files with complete face, edge, 
    and vertex topology (including the unnecessary normals) are
    only 50% of the original file size.  ASCII RPI format files with 
    only the necessary information are approx 10%-20% the size of the 
    corresponding STL files.  Of course, a smaller size reduction will
    be experienced for the binary counterparts because the keywords
    found in the ASCII STL file are not present in the binary form.

    Storing the topology actually lessens the burden on the RP machine
    by making slicing very efficient since a topological marching 
    algorithm can be used (see SFF91 proceedings, p.28-36). 
    Additionally, it makes model validity checking trivial.

(5) The paper did describe a method for storing more complex (3D)
    entities (with examples given for CSG-based solids).  This could
    just as well be used for NURBS patches and any other objects one
    cares to define in the future.

(6) The format provides for multiple solids in a single file.

(7) The format provides for storing process data and other
    comment information -- both human and machine interpretable.
    For example, build information could be appended to a file 
    for development of a manufacturing history.
    
The purpose for publishing the RPI format paper cited above was 
to share work done which overcomes many of the problems faced
when operating with the de facto standard STL format.  Although we 
have used this format internally for several years, I did not
expect the masses to ink the "new standard" stamp in 1991, nor do
I now.  I do, however, hope this work advanced some concepts which 
could benefit a new standard. Is anyone aware of any effort between 
RP vendors, CAD companies, end-users, and universities to develop a 
better representation or format standard for RP (other than the more 
general STEP work)?

Mike Brindley writes:
>                                    ... I could waste many electrons
> typing about what is wrong with the STL file format!  I have my own
> ideas about what would make a good format.

I bet most who have ever been blessed with the opportunity to work
with STL files can too!  Are your ideas published somewhere?

Chuck Kirschman writes (replying to Mike Brindley's initial comment
                        regarding RPI format complexity):
> I'd love to see your format.  I have seen Rock's, and I agree, it is 
> unnecessarily complex.  They want to greatly reduce processing time
> at the expense of storage.  But calculating all of the information
> is not that difficult with good algorithms.  

The previous responses regarding RPI format complexity applies.

Additionally, Kirschman says that with "good algorithms", calculating 
all of the information is not that difficult.  If you're talking about
reconstructing topological information from a disconnected facet 
representation as provided by the STL format, you are best-case 
talking about a searching operation.  While perhaps not that 
"difficult" in the intellectual sense, searching operations 
(particularly in higher dimensional spaces) can consume significant 
compute time even if spatial partitioning techniques are employed. 
Processing STL data generated by a variety of industrial CAD systems
typically brings with it some additional challenges. Redundantly 
specified vertices that should have been "the same" may be 
numerically non-equal due to different ordering of operations used
during tessellation.  Additionally, problems with missing facets,
non-manifold topology, and zero-volume shells must be addressed.
Even with good algorithms, all of this has overhead associated with it.

Regarding a trade between processing time and file size: Yes we
do "greatly reduce processing time at the expense of storage", but
I disagree with the implication that this is a bad trade-off. 
For archival storage, we do reduce the information retained, but the
RPI format concept allows this to be done rather transparently.  Our
slicing approach is based on topology, so while actively working with
a model, we do chose to keep a larger, more informationally rich 
file around.

Chuck Kirschman writes:
> Don't discount Rock's ideas for slicing, though - very fast.  
> But they do depend on a _good_ STL file, and need some repair
> functions for todays files.  I'll bring this up in another
> message so it doesn't dissapear in this thread.

Well, a _good_ STL file is not a necessity.  The paper presented
at SFF91 only talked about slicing "valid" (a.k.a. _good_)
models; however, it doesn't require much imagination to envision 
extending this approach for models missing some facets--providing 
the topology exists for the remaining facets. (March around the 
holes and interpolate.)

Mike Brindley replies:
>I don't discount Rock's slicing ideas - they are nearly identical
>to mine!  I developed the same ideas (independently) as the only
>reasonable approach to slicing.  I was amazed and horrified by
>the descriptions I saw of what 3D Systems was doing to slice files.

Good to hear :-)
Are the descriptions of 3D Systems approach public?  If so, can someone
please point me to a reference?
Also, Mike, did you publish your slicing ideas somewhere?  I'd be
interested in comparing thoughts.


Critical review is beneficial and this mailing list is an excellent 
medium for rapidly sharing ideas and opinions; however, perhaps before
critiquing the methods presented in a published paper, a thorough
read-through is in order.

Thanks for your consideration,
Steve Rock