Binary .stl files & point 'equality'

classic Classic list List threaded Threaded
48 messages Options
123
Reply | Threaded
Open this post in threaded view
|

Binary .stl files & point 'equality'

Henry Baker
Hi:

I'm a computer scientist who just started using OpenSCAD a few months ago & am very impressed.

However, I'm curious about a few things:

1.  How come OpenSCAD outputs _ascii_ .stl files instead of _binary_ .stl files ?  I have written code for writing .stl files of both types, and I find it is actually easier to write a _binary_ .stl file, and more importantly, the _interpretation_ of the resulting .stl file is more consistent.

Binary .stl files depend upon the IEEE binary 32-bit floating point standard, which is much more tightly specified than is ascii floating point.  As a result, when you write out a triple to a binary .stl file & read it back it, it will be always recognized as being exactly the same number, whereas with ascii representations, the reader program may assign a slightly different floating point binary number to that ascii floating point number, so that the triples no longer match exactly.

Thus, an ascii .stl reader may need some sort of 'fuzz'/'tolerance' to recognize the 'same' point, whereas this won't be necessary with binary .stl files.

(It should also be pointed out that the standard interpretation of 'normals' in .stl files is _outwards_, whereas the OpenSCAD interpretation of the polyhedron command is _inwards_; i.e., in 'thrown together' mode, the .stl interpretation will yield 100% pink!)

I've noticed that 'netfabb Studio' complains about some of the known 'watertight' output from OpenSCAD; it is possible that some of these complaints may stem from the use of _ascii_ rather than _binary_ .stl files.  (Or perhaps netfabb Studio simply has bugs in its watertightness code.)

2.  Running OpenSCAD on a faster/bigger machine doesn't seem to speed up CGAL rendering.  I assume that faster CGAL rendering requires paying $$$ ??

3.  I've noticed that putting two identical cubical blocks (produced with the 'polyhedron' command) side-by-side _exactly_, doesn't seem to work very well; the faces don't cancel one another correctly.  (I hope this isn't due to the 'fuzz' issue mentioned in #1, above.)  I find I have to laboriously remove the faces myself before stitching the blocks together into a single object.  This can't be right, as it eliminates the whole advantage of CSG operations.

4.  Is there any way to have the effect of a 'mapping' operation ?  More importantly, is there any way to construct a new sequence/vector of length determined at run time?  I'd even be willing to write the computed vector to a file & read it back in !!

I'm sure you've been asked this last question before!

Henry Baker
Santa Barbara, CA

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Binary .stl files & point 'equality'

David Powell
i have a question 

given  the fuzz  issue you covered in point 1 and the issues in point 3  are problems that are both related to maths precision and need to be fudged  at some point 
by the same token   a cube of  ( 9Exp-11 )  should it have flat sides or should it be represented as a cubic array of spheres (cubic array of 24 electrons )? 

for the maths accuracy  operations where a line never quite intersects with another even extending the maths to 128 bit  or more precision would do little to resolve this  and only eat up more cpu time processing and produce results with sub quantum level tolerances , that become  of no relevance other than to prove in math one way or another that a face/ edge intersects or not with another 
(remembering  on the fact that other physical forces not within the scope of the app would come into play before this level of accuracy )

from the science point of view as this is also an engineering application used to create real world 3d printable objects where a tolarance of 0.001 of an inch would be hard to achieve on a machine and although only 1Exp-9 would be needed if you are doing csg on silicone chip gate scale objects the 
fact is that real world surfaces are no longer flat 
   
so can i ask
   what is the reason that accuracy at the current level is an issue  ?
 and given the above what would you suggest would be the physical limit needed  

  


On Tue, Jun 25, 2013 at 12:21 AM, Henry Baker <[hidden email]> wrote:
Hi:

I'm a computer scientist who just started using OpenSCAD a few months ago & am very impressed.

However, I'm curious about a few things:

1.  How come OpenSCAD outputs _ascii_ .stl files instead of _binary_ .stl files ?  I have written code for writing .stl files of both types, and I find it is actually easier to write a _binary_ .stl file, and more importantly, the _interpretation_ of the resulting .stl file is more consistent.

Binary .stl files depend upon the IEEE binary 32-bit floating point standard, which is much more tightly specified than is ascii floating point.  As a result, when you write out a triple to a binary .stl file & read it back it, it will be always recognized as being exactly the same number, whereas with ascii representations, the reader program may assign a slightly different floating point binary number to that ascii floating point number, so that the triples no longer match exactly.

Thus, an ascii .stl reader may need some sort of 'fuzz'/'tolerance' to recognize the 'same' point, whereas this won't be necessary with binary .stl files.

(It should also be pointed out that the standard interpretation of 'normals' in .stl files is _outwards_, whereas the OpenSCAD interpretation of the polyhedron command is _inwards_; i.e., in 'thrown together' mode, the .stl interpretation will yield 100% pink!)

I've noticed that 'netfabb Studio' complains about some of the known 'watertight' output from OpenSCAD; it is possible that some of these complaints may stem from the use of _ascii_ rather than _binary_ .stl files.  (Or perhaps netfabb Studio simply has bugs in its watertightness code.)

2.  Running OpenSCAD on a faster/bigger machine doesn't seem to speed up CGAL rendering.  I assume that faster CGAL rendering requires paying $$$ ??

3.  I've noticed that putting two identical cubical blocks (produced with the 'polyhedron' command) side-by-side _exactly_, doesn't seem to work very well; the faces don't cancel one another correctly.  (I hope this isn't due to the 'fuzz' issue mentioned in #1, above.)  I find I have to laboriously remove the faces myself before stitching the blocks together into a single object.  This can't be right, as it eliminates the whole advantage of CSG operations.

4.  Is there any way to have the effect of a 'mapping' operation ?  More importantly, is there any way to construct a new sequence/vector of length determined at run time?  I'd even be willing to write the computed vector to a file & read it back in !!

I'm sure you've been asked this last question before!

Henry Baker
Santa Barbara, CA

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Binary .stl files & point 'equality'

nophead
I think the issue is that where there are vertices very close the object can be come none manifold when they are collapsed by floating point rounding when converting to text and back again.


On 25 June 2013 12:19, David Powell <[hidden email]> wrote:
i have a question 

given  the fuzz  issue you covered in point 1 and the issues in point 3  are problems that are both related to maths precision and need to be fudged  at some point 
by the same token   a cube of  ( 9Exp-11 )  should it have flat sides or should it be represented as a cubic array of spheres (cubic array of 24 electrons )? 

for the maths accuracy  operations where a line never quite intersects with another even extending the maths to 128 bit  or more precision would do little to resolve this  and only eat up more cpu time processing and produce results with sub quantum level tolerances , that become  of no relevance other than to prove in math one way or another that a face/ edge intersects or not with another 
(remembering  on the fact that other physical forces not within the scope of the app would come into play before this level of accuracy )

from the science point of view as this is also an engineering application used to create real world 3d printable objects where a tolarance of 0.001 of an inch would be hard to achieve on a machine and although only 1Exp-9 would be needed if you are doing csg on silicone chip gate scale objects the 
fact is that real world surfaces are no longer flat 
   
so can i ask
   what is the reason that accuracy at the current level is an issue  ?
 and given the above what would you suggest would be the physical limit needed  

  


On Tue, Jun 25, 2013 at 12:21 AM, Henry Baker <[hidden email]> wrote:
Hi:

I'm a computer scientist who just started using OpenSCAD a few months ago & am very impressed.

However, I'm curious about a few things:

1.  How come OpenSCAD outputs _ascii_ .stl files instead of _binary_ .stl files ?  I have written code for writing .stl files of both types, and I find it is actually easier to write a _binary_ .stl file, and more importantly, the _interpretation_ of the resulting .stl file is more consistent.

Binary .stl files depend upon the IEEE binary 32-bit floating point standard, which is much more tightly specified than is ascii floating point.  As a result, when you write out a triple to a binary .stl file & read it back it, it will be always recognized as being exactly the same number, whereas with ascii representations, the reader program may assign a slightly different floating point binary number to that ascii floating point number, so that the triples no longer match exactly.

Thus, an ascii .stl reader may need some sort of 'fuzz'/'tolerance' to recognize the 'same' point, whereas this won't be necessary with binary .stl files.

(It should also be pointed out that the standard interpretation of 'normals' in .stl files is _outwards_, whereas the OpenSCAD interpretation of the polyhedron command is _inwards_; i.e., in 'thrown together' mode, the .stl interpretation will yield 100% pink!)

I've noticed that 'netfabb Studio' complains about some of the known 'watertight' output from OpenSCAD; it is possible that some of these complaints may stem from the use of _ascii_ rather than _binary_ .stl files.  (Or perhaps netfabb Studio simply has bugs in its watertightness code.)

2.  Running OpenSCAD on a faster/bigger machine doesn't seem to speed up CGAL rendering.  I assume that faster CGAL rendering requires paying $$$ ??

3.  I've noticed that putting two identical cubical blocks (produced with the 'polyhedron' command) side-by-side _exactly_, doesn't seem to work very well; the faces don't cancel one another correctly.  (I hope this isn't due to the 'fuzz' issue mentioned in #1, above.)  I find I have to laboriously remove the faces myself before stitching the blocks together into a single object.  This can't be right, as it eliminates the whole advantage of CSG operations.

4.  Is there any way to have the effect of a 'mapping' operation ?  More importantly, is there any way to construct a new sequence/vector of length determined at run time?  I'd even be willing to write the computed vector to a file & read it back in !!

I'm sure you've been asked this last question before!

Henry Baker
Santa Barbara, CA

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Binary .stl files & point 'equality'

Tom Cook
In reply to this post by Henry Baker
Hi Henry,

As a computer scientist, I'd hope you would understand that comparing floating-point numbers is a bad idea.  Even if you do manage to produce two bit-pattern-identical numbers, as soon as you scale, rotate or translate the output in any way the result will depend on the CPU vendor, the CPU model, the mode the CPU is operating in, the operating system, the compiler, the compiler options, the compiler floating-point model, 32vs64-bit OS, SIMD v x87 operations, runtime v compile-time evaluation...  

So while you can put the same number through exactly the same code path and generally expect the same result, you can't run "the same piece of software" on the same input on different machines or at different times and guarantee (or even expect) the same result.  It is certainly possible to create software that executes the same sequence of instructions in different threads and produce different results.  Trying to guarantee identical results is a bad idea- you're only setting yourself up for a lot of pain when you realise it doesn't work.  See here for a chart that details *some* of the complexities: http://randomascii.files.wordpress.com/2012/03/image6.png

What I'm getting around to is that this sort of fuzzing is always going to be necessary.  Utterly unavoidable.  ASCII-format STL files are the least of your problems.

Regards,
Tom


On Tue, Jun 25, 2013 at 12:21 AM, Henry Baker <[hidden email]> wrote:
Hi:

I'm a computer scientist who just started using OpenSCAD a few months ago & am very impressed.

However, I'm curious about a few things:

1.  How come OpenSCAD outputs _ascii_ .stl files instead of _binary_ .stl files ?  I have written code for writing .stl files of both types, and I find it is actually easier to write a _binary_ .stl file, and more importantly, the _interpretation_ of the resulting .stl file is more consistent.

Binary .stl files depend upon the IEEE binary 32-bit floating point standard, which is much more tightly specified than is ascii floating point.  As a result, when you write out a triple to a binary .stl file & read it back it, it will be always recognized as being exactly the same number, whereas with ascii representations, the reader program may assign a slightly different floating point binary number to that ascii floating point number, so that the triples no longer match exactly.

Thus, an ascii .stl reader may need some sort of 'fuzz'/'tolerance' to recognize the 'same' point, whereas this won't be necessary with binary .stl files.

(It should also be pointed out that the standard interpretation of 'normals' in .stl files is _outwards_, whereas the OpenSCAD interpretation of the polyhedron command is _inwards_; i.e., in 'thrown together' mode, the .stl interpretation will yield 100% pink!)

I've noticed that 'netfabb Studio' complains about some of the known 'watertight' output from OpenSCAD; it is possible that some of these complaints may stem from the use of _ascii_ rather than _binary_ .stl files.  (Or perhaps netfabb Studio simply has bugs in its watertightness code.)

2.  Running OpenSCAD on a faster/bigger machine doesn't seem to speed up CGAL rendering.  I assume that faster CGAL rendering requires paying $$$ ??

3.  I've noticed that putting two identical cubical blocks (produced with the 'polyhedron' command) side-by-side _exactly_, doesn't seem to work very well; the faces don't cancel one another correctly.  (I hope this isn't due to the 'fuzz' issue mentioned in #1, above.)  I find I have to laboriously remove the faces myself before stitching the blocks together into a single object.  This can't be right, as it eliminates the whole advantage of CSG operations.

4.  Is there any way to have the effect of a 'mapping' operation ?  More importantly, is there any way to construct a new sequence/vector of length determined at run time?  I'd even be willing to write the computed vector to a file & read it back in !!

I'm sure you've been asked this last question before!

Henry Baker
Santa Barbara, CA

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Binary .stl files & point 'equality'

Alan Cox
In reply to this post by David Powell
> so can i ask
>    what is the reason that accuracy at the current level is an issue  ?
>  and given the above what would you suggest would be the physical limit
> needed

The precision question is a red herring. The way this is solved in most
other situations is to quantise it onto a fixed grid (or mesh for 3D). A
pixelated representation as it were. At that point you can define the
meaning of things like a union or intersection precisely  within the
resolution specified because you have pixel boundaries and effectively an
integer co-ordinate system.

Precision will never fix it - indeed in the real world we have no reason
to believe the question "is A touching B" can actually meaningfully be
answered in the sense that CSG uses it.

On the other points

2. A faster machine helps but processor speed generally isn't much faster
on a "faster" machine and openscad isn't making any use of parallelism so
extra cores don't help. That is probably fixable to some extent in
OpenSCAD so send patches(*). Optimising CGAL is also possible and again
I'm sure they would be interested in good quality work on that.

Another alternative is to write a new fast geometry engine for the job
rather than a generic mathematically elegant engine. ImplicitCAD for
example is taking this kind of tack.

4. There are a load of things you can't currently do in OpenSCAD such as
bending an object along a curved path. Many of these are possible if you
use blender instead and work with the Blender python interface, treating
blender as a particularly unpleasant python library. Blender is improving
greatly in the bindings so this is getting better as a choice.

Alan
(*) OpenSCAD is functional so you should be able to compute all the
subcomponents of any conmbination of two components in parallel.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Binary .stl files & point 'equality'

Henry Baker
In reply to this post by Tom Cook
The problem is that the proper interpretation of .stl files _requires_ the exact comparison of IEEE floating point numbers.

For example, in order to determine watertightness of a simple tetrahedron consisting of 4 vertices, 4 triangles/faces, and 6 edges, you need to make sure that when the triangle/face vertices are listed, that the 'same' vertices show up again in the next triangles/faces.

OpenSCAD avoids this problem in its 'polyhedron' command by creating a points 'dictionary', and subsequently referring to the points by means of their indices into this dictionary.  These integer indices can be robustly compared for identity without any 'fuzz'.

Unfortunately, an .stl reader must create such a 'points' dictionary when reading the file, so as to ensure correct interpretation in subsequent triangles/faces.

The good news is that so long as 'write-number' (or whatever its name is) is a _function_, always producing exactly the same characters (for ascii output), or exactly the same bits (for binary output), then vertex equality is preserved in the process sequence write;read.

Unfortunately, unless writing & reading are carefully done, vertex _inequality_ may NOT be preserved, and 2 previously different nodes may be incorrectly 'aliased' together by the write;read process.

This is why I suggest using _binary_ rather than _ascii_ .stl files.

BTW, my personal .stl reader simply treats x,y,z coordinates as _uninterpreted_ 32-bit unsigned quantities, which I then use to build my 'points dictionary'.  Only after I've already created my points, triangles/faces, and edges data-structures, do I finally 'interpret' these 32-bit bitstrings in the 'points dictionary' as IEEE floating point numbers.

The only time that 'fuzz' might be required for .stl reading is to 'repair' some poorly constructed .stl file.

At 05:15 AM 6/25/2013, Tom Cook wrote:

>Hi Henry,
>
>As a computer scientist, I'd hope you would understand that comparing floating-point numbers is a bad idea. Â Even if you do manage to produce two bit-pattern-identical numbers, as soon as you scale, rotate or translate the output in any way the result will depend on the CPU vendor, the CPU model, the mode the CPU is operating in, the operating system, the compiler, the compiler options, the compiler floating-point model, 32vs64-bit OS, SIMD v x87 operations, runtime v compile-time evaluation... Â
>
>So while you can put the same number through exactly the same code path and generally expect the same result, you can't run "the same piece of software" on the same input on different machines or at different times and guarantee (or even expect) the same result. Â It is certainly possible to create software that executes the same sequence of instructions in different threads and produce different results. Â Trying to guarantee identical results is a bad idea- you're only setting yourself up for a lot of pain when you realise it doesn't work. Â See here for a chart that details *some* of the complexities:Â http://randomascii.files.wordpress.com/2012/03/image6.png
>
>What I'm getting around to is that this sort of fuzzing is always going to be necessary. Â Utterly unavoidable. Â ASCII-format STL files are the least of your problems.
>
>Regards,
>Tom
>
>On Tue, Jun 25, 2013 at 12:21 AM, Henry Baker <[hidden email]> wrote:
>Hi:
>
>I'm a computer scientist who just started using OpenSCAD a few months ago & am very impressed.
>
>However, I'm curious about a few things:
>
>1. Â How come OpenSCAD outputs _ascii_ .stl files instead of _binary_ .stl files ? Â I have written code for writing .stl files of both types, and I find it is actually easier to write a _binary_ .stl file, and more importantly, the _interpretation_ of the resulting .stl file is more consistent.
>
>Binary .stl files depend upon the IEEE binary 32-bit floating point standard, which is much more tightly specified than is ascii floating point. Â As a result, when you write out a triple to a binary .stl file & read it back it, it will be always recognized as being exactly the same number, whereas with ascii representations, the reader program may assign a slightly different floating point binary number to that ascii floating point number, so that the triples no longer match exactly.
>
>Thus, an ascii .stl reader may need some sort of 'fuzz'/'tolerance' to recognize the 'same' point, whereas this won't be necessary with binary .stl files.
>
>(It should also be pointed out that the standard interpretation of 'normals' in .stl files is _outwards_, whereas the OpenSCAD interpretation of the polyhedron command is _inwards_; i.e., in 'thrown together' mode, the .stl interpretation will yield 100% pink!)
>
>I've noticed that 'netfabb Studio' complains about some of the known 'watertight' output from OpenSCAD; it is possible that some of these complaints may stem from the use of _ascii_ rather than _binary_ .stl files. Â (Or perhaps netfabb Studio simply has bugs in its watertightness code.)
>
>2. Â Running OpenSCAD on a faster/bigger machine doesn't seem to speed up CGAL rendering. Â I assume that faster CGAL rendering requires paying $$$ ??
>
>3. Â I've noticed that putting two identical cubical blocks (produced with the 'polyhedron' command) side-by-side _exactly_, doesn't seem to work very well; the faces don't cancel one another correctly. Â (I hope this isn't due to the 'fuzz' issue mentioned in #1, above.) Â I find I have to laboriously remove the faces myself before stitching the blocks together into a single object. Â This can't be right, as it eliminates the whole advantage of CSG operations.
>
>4. Â Is there any way to have the effect of a 'mapping' operation ? Â More importantly, is there any way to construct a new sequence/vector of length determined at run time? Â I'd even be willing to write the computed vector to a file & read it back in !!
>
>I'm sure you've been asked this last question before!
>
>Henry Baker
>Santa Barbara, CA

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Binary .stl files & point 'equality'

kintel
Administrator
In reply to this post by Henry Baker
On 2013-06-24, at 19:21 , Henry Baker wrote:

> 1.  How come OpenSCAD outputs _ascii_ .stl files instead of _binary_ .stl files ?

More software appear to support ascii STL than binary STL, so we started there. It's easy enough to add a checkbox to the export dialog and implement binary writing though. If you open an issue on it on github, perhaps the idea will get some traction. This could probably be done together with cleaning up the GUI for all export options.

> 2.  Running OpenSCAD on a faster/bigger machine doesn't seem to speed up CGAL rendering.  I assume that faster CGAL rendering requires paying $$$ ??
>
It should, but as someone pointed out, we're currently using only one core. I've seen pretty large differences in running time. To optimize, get a fast CPU with a large cache and very fast RAM. For some examples, see http://forum.openscad.org/OpenSCAD-performance-numbers-td4707.html

> 3.  I've noticed that putting two identical cubical blocks (produced with the 'polyhedron' command) side-by-side _exactly_, doesn't seem to work very well;

Please provide some (minimal) examples. Such corner cases are invaluable when improving the code.

> 4.  Is there any way to have the effect of a 'mapping' operation ?  More importantly, is there any way to construct a new sequence/vector of length determined at run time?

I think this would be covered by this issue: https://github.com/openscad/openscad/issues/201

 -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Binary .stl files & point 'equality'

nophead
On the subject of STL export. I wrote this script to canonicalise the STLs produced by OpenScad because otherwise the order of the faces varies even when the shape is identical.


On 25 June 2013 21:00, Marius Kintel <[hidden email]> wrote:
On 2013-06-24, at 19:21 , Henry Baker wrote:

> 1.  How come OpenSCAD outputs _ascii_ .stl files instead of _binary_ .stl files ?

More software appear to support ascii STL than binary STL, so we started there. It's easy enough to add a checkbox to the export dialog and implement binary writing though. If you open an issue on it on github, perhaps the idea will get some traction. This could probably be done together with cleaning up the GUI for all export options.

> 2.  Running OpenSCAD on a faster/bigger machine doesn't seem to speed up CGAL rendering.  I assume that faster CGAL rendering requires paying $$$ ??
>
It should, but as someone pointed out, we're currently using only one core. I've seen pretty large differences in running time. To optimize, get a fast CPU with a large cache and very fast RAM. For some examples, see http://forum.openscad.org/OpenSCAD-performance-numbers-td4707.html

> 3.  I've noticed that putting two identical cubical blocks (produced with the 'polyhedron' command) side-by-side _exactly_, doesn't seem to work very well;

Please provide some (minimal) examples. Such corner cases are invaluable when improving the code.

> 4.  Is there any way to have the effect of a 'mapping' operation ?  More importantly, is there any way to construct a new sequence/vector of length determined at run time?

I think this would be covered by this issue: https://github.com/openscad/openscad/issues/201

 -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Binary .stl files & point 'equality'

Tom Cook
In reply to this post by Henry Baker

Hi Henry,

As others have pointed out, double precision allows you to model common objects to subatomic level.  So you only need equality comparisons to assess water-tightness if your "water" is pretty strange stuff.  In practice, many structures with vertices that are not exactly equal will be water-tight, depending on local temperature and atmospheric pressure.

And it is trivially easy to produce a program that mis-processes geometry to produce inequality.  Is your program multi-threaded?  Do you use direct3d? Or does a library you use also use direct3d? Oops, now you get different geometry results from different threads.

If you are checking for equality of floating point numbers, you are, 99.99% of the time, doing it wrong.

Tom

On 25 Jun 2013 20:42, "Henry Baker" <[hidden email]> wrote:
The problem is that the proper interpretation of .stl files _requires_ the exact comparison of IEEE floating point numbers.

For example, in order to determine watertightness of a simple tetrahedron consisting of 4 vertices, 4 triangles/faces, and 6 edges, you need to make sure that when the triangle/face vertices are listed, that the 'same' vertices show up again in the next triangles/faces.

OpenSCAD avoids this problem in its 'polyhedron' command by creating a points 'dictionary', and subsequently referring to the points by means of their indices into this dictionary.  These integer indices can be robustly compared for identity without any 'fuzz'.

Unfortunately, an .stl reader must create such a 'points' dictionary when reading the file, so as to ensure correct interpretation in subsequent triangles/faces.

The good news is that so long as 'write-number' (or whatever its name is) is a _function_, always producing exactly the same characters (for ascii output), or exactly the same bits (for binary output), then vertex equality is preserved in the process sequence write;read.

Unfortunately, unless writing & reading are carefully done, vertex _inequality_ may NOT be preserved, and 2 previously different nodes may be incorrectly 'aliased' together by the write;read process.

This is why I suggest using _binary_ rather than _ascii_ .stl files.

BTW, my personal .stl reader simply treats x,y,z coordinates as _uninterpreted_ 32-bit unsigned quantities, which I then use to build my 'points dictionary'.  Only after I've already created my points, triangles/faces, and edges data-structures, do I finally 'interpret' these 32-bit bitstrings in the 'points dictionary' as IEEE floating point numbers.

The only time that 'fuzz' might be required for .stl reading is to 'repair' some poorly constructed .stl file.

At 05:15 AM 6/25/2013, Tom Cook wrote:
>Hi Henry,
>
>As a computer scientist, I'd hope you would understand that comparing floating-point numbers is a bad idea. Â Even if you do manage to produce two bit-pattern-identical numbers, as soon as you scale, rotate or translate the output in any way the result will depend on the CPU vendor, the CPU model, the mode the CPU is operating in, the operating system, the compiler, the compiler options, the compiler floating-point model, 32vs64-bit OS, SIMD v x87 operations, runtime v compile-time evaluation... Â
>
>So while you can put the same number through exactly the same code path and generally expect the same result, you can't run "the same piece of software" on the same input on different machines or at different times and guarantee (or even expect) the same result. Â It is certainly possible to create software that executes the same sequence of instructions in different threads and produce different results. Â Trying to guarantee identical results is a bad idea- you're only setting yourself up for a lot of pain when you realise it doesn't work. Â See here for a chart that details *some* of the complexities:Â http://randomascii.files.wordpress.com/2012/03/image6.png
>
>What I'm getting around to is that this sort of fuzzing is always going to be necessary. Â Utterly unavoidable. Â ASCII-format STL files are the least of your problems.
>
>Regards,
>Tom
>
>On Tue, Jun 25, 2013 at 12:21 AM, Henry Baker <[hidden email]> wrote:
>Hi:
>
>I'm a computer scientist who just started using OpenSCAD a few months ago & am very impressed.
>
>However, I'm curious about a few things:
>
>1. Â How come OpenSCAD outputs _ascii_ .stl files instead of _binary_ .stl files ? Â I have written code for writing .stl files of both types, and I find it is actually easier to write a _binary_ .stl file, and more importantly, the _interpretation_ of the resulting .stl file is more consistent.
>
>Binary .stl files depend upon the IEEE binary 32-bit floating point standard, which is much more tightly specified than is ascii floating point. Â As a result, when you write out a triple to a binary .stl file & read it back it, it will be always recognized as being exactly the same number, whereas with ascii representations, the reader program may assign a slightly different floating point binary number to that ascii floating point number, so that the triples no longer match exactly.
>
>Thus, an ascii .stl reader may need some sort of 'fuzz'/'tolerance' to recognize the 'same' point, whereas this won't be necessary with binary .stl files.
>
>(It should also be pointed out that the standard interpretation of 'normals' in .stl files is _outwards_, whereas the OpenSCAD interpretation of the polyhedron command is _inwards_; i.e., in 'thrown together' mode, the .stl interpretation will yield 100% pink!)
>
>I've noticed that 'netfabb Studio' complains about some of the known 'watertight' output from OpenSCAD; it is possible that some of these complaints may stem from the use of _ascii_ rather than _binary_ .stl files. Â (Or perhaps netfabb Studio simply has bugs in its watertightness code.)
>
>2. Â Running OpenSCAD on a faster/bigger machine doesn't seem to speed up CGAL rendering. Â I assume that faster CGAL rendering requires paying $$$ ??
>
>3. Â I've noticed that putting two identical cubical blocks (produced with the 'polyhedron' command) side-by-side _exactly_, doesn't seem to work very well; the faces don't cancel one another correctly. Â (I hope this isn't due to the 'fuzz' issue mentioned in #1, above.) Â I find I have to laboriously remove the faces myself before stitching the blocks together into a single object. Â This can't be right, as it eliminates the whole advantage of CSG operations.
>
>4. Â Is there any way to have the effect of a 'mapping' operation ? Â More importantly, is there any way to construct a new sequence/vector of length determined at run time? Â I'd even be willing to write the computed vector to a file & read it back in !!
>
>I'm sure you've been asked this last question before!
>
>Henry Baker
>Santa Barbara, CA

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Binary .stl files & point 'equality'

nophead
"water-tightness " in this context is nothing to do with the physics of water. It is a topological concept.


On 25 June 2013 21:45, Tom Cook <[hidden email]> wrote:

Hi Henry,

As others have pointed out, double precision allows you to model common objects to subatomic level.  So you only need equality comparisons to assess water-tightness if your "water" is pretty strange stuff.  In practice, many structures with vertices that are not exactly equal will be water-tight, depending on local temperature and atmospheric pressure.

And it is trivially easy to produce a program that mis-processes geometry to produce inequality.  Is your program multi-threaded?  Do you use direct3d? Or does a library you use also use direct3d? Oops, now you get different geometry results from different threads.

If you are checking for equality of floating point numbers, you are, 99.99% of the time, doing it wrong.

Tom

On 25 Jun 2013 20:42, "Henry Baker" <[hidden email]> wrote:
The problem is that the proper interpretation of .stl files _requires_ the exact comparison of IEEE floating point numbers.

For example, in order to determine watertightness of a simple tetrahedron consisting of 4 vertices, 4 triangles/faces, and 6 edges, you need to make sure that when the triangle/face vertices are listed, that the 'same' vertices show up again in the next triangles/faces.

OpenSCAD avoids this problem in its 'polyhedron' command by creating a points 'dictionary', and subsequently referring to the points by means of their indices into this dictionary.  These integer indices can be robustly compared for identity without any 'fuzz'.

Unfortunately, an .stl reader must create such a 'points' dictionary when reading the file, so as to ensure correct interpretation in subsequent triangles/faces.

The good news is that so long as 'write-number' (or whatever its name is) is a _function_, always producing exactly the same characters (for ascii output), or exactly the same bits (for binary output), then vertex equality is preserved in the process sequence write;read.

Unfortunately, unless writing & reading are carefully done, vertex _inequality_ may NOT be preserved, and 2 previously different nodes may be incorrectly 'aliased' together by the write;read process.

This is why I suggest using _binary_ rather than _ascii_ .stl files.

BTW, my personal .stl reader simply treats x,y,z coordinates as _uninterpreted_ 32-bit unsigned quantities, which I then use to build my 'points dictionary'.  Only after I've already created my points, triangles/faces, and edges data-structures, do I finally 'interpret' these 32-bit bitstrings in the 'points dictionary' as IEEE floating point numbers.

The only time that 'fuzz' might be required for .stl reading is to 'repair' some poorly constructed .stl file.

At 05:15 AM 6/25/2013, Tom Cook wrote:
>Hi Henry,
>
>As a computer scientist, I'd hope you would understand that comparing floating-point numbers is a bad idea. Â Even if you do manage to produce two bit-pattern-identical numbers, as soon as you scale, rotate or translate the output in any way the result will depend on the CPU vendor, the CPU model, the mode the CPU is operating in, the operating system, the compiler, the compiler options, the compiler floating-point model, 32vs64-bit OS, SIMD v x87 operations, runtime v compile-time evaluation... Â
>
>So while you can put the same number through exactly the same code path and generally expect the same result, you can't run "the same piece of software" on the same input on different machines or at different times and guarantee (or even expect) the same result. Â It is certainly possible to create software that executes the same sequence of instructions in different threads and produce different results. Â Trying to guarantee identical results is a bad idea- you're only setting yourself up for a lot of pain when you realise it doesn't work. Â See here for a chart that details *some* of the complexities:Â http://randomascii.files.wordpress.com/2012/03/image6.png
>
>What I'm getting around to is that this sort of fuzzing is always going to be necessary. Â Utterly unavoidable. Â ASCII-format STL files are the least of your problems.
>
>Regards,
>Tom
>
>On Tue, Jun 25, 2013 at 12:21 AM, Henry Baker <[hidden email]> wrote:
>Hi:
>
>I'm a computer scientist who just started using OpenSCAD a few months ago & am very impressed.
>
>However, I'm curious about a few things:
>
>1. Â How come OpenSCAD outputs _ascii_ .stl files instead of _binary_ .stl files ? Â I have written code for writing .stl files of both types, and I find it is actually easier to write a _binary_ .stl file, and more importantly, the _interpretation_ of the resulting .stl file is more consistent.
>
>Binary .stl files depend upon the IEEE binary 32-bit floating point standard, which is much more tightly specified than is ascii floating point. Â As a result, when you write out a triple to a binary .stl file & read it back it, it will be always recognized as being exactly the same number, whereas with ascii representations, the reader program may assign a slightly different floating point binary number to that ascii floating point number, so that the triples no longer match exactly.
>
>Thus, an ascii .stl reader may need some sort of 'fuzz'/'tolerance' to recognize the 'same' point, whereas this won't be necessary with binary .stl files.
>
>(It should also be pointed out that the standard interpretation of 'normals' in .stl files is _outwards_, whereas the OpenSCAD interpretation of the polyhedron command is _inwards_; i.e., in 'thrown together' mode, the .stl interpretation will yield 100% pink!)
>
>I've noticed that 'netfabb Studio' complains about some of the known 'watertight' output from OpenSCAD; it is possible that some of these complaints may stem from the use of _ascii_ rather than _binary_ .stl files. Â (Or perhaps netfabb Studio simply has bugs in its watertightness code.)
>
>2. Â Running OpenSCAD on a faster/bigger machine doesn't seem to speed up CGAL rendering. Â I assume that faster CGAL rendering requires paying $$$ ??
>
>3. Â I've noticed that putting two identical cubical blocks (produced with the 'polyhedron' command) side-by-side _exactly_, doesn't seem to work very well; the faces don't cancel one another correctly. Â (I hope this isn't due to the 'fuzz' issue mentioned in #1, above.) Â I find I have to laboriously remove the faces myself before stitching the blocks together into a single object. Â This can't be right, as it eliminates the whole advantage of CSG operations.
>
>4. Â Is there any way to have the effect of a 'mapping' operation ? Â More importantly, is there any way to construct a new sequence/vector of length determined at run time? Â I'd even be willing to write the computed vector to a file & read it back in !!
>
>I'm sure you've been asked this last question before!
>
>Henry Baker
>Santa Barbara, CA

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Binary .stl files & point 'equality'

Tom Cook

So, as I've been saying, if it's a precise concept, you shouldn't be using floating point numbers to assess it. Really.

On 25 Jun 2013 22:05, "nop head" <[hidden email]> wrote:
"water-tightness " in this context is nothing to do with the physics of water. It is a topological concept.


On 25 June 2013 21:45, Tom Cook <[hidden email]> wrote:

Hi Henry,

As others have pointed out, double precision allows you to model common objects to subatomic level.  So you only need equality comparisons to assess water-tightness if your "water" is pretty strange stuff.  In practice, many structures with vertices that are not exactly equal will be water-tight, depending on local temperature and atmospheric pressure.

And it is trivially easy to produce a program that mis-processes geometry to produce inequality.  Is your program multi-threaded?  Do you use direct3d? Or does a library you use also use direct3d? Oops, now you get different geometry results from different threads.

If you are checking for equality of floating point numbers, you are, 99.99% of the time, doing it wrong.

Tom

On 25 Jun 2013 20:42, "Henry Baker" <[hidden email]> wrote:
The problem is that the proper interpretation of .stl files _requires_ the exact comparison of IEEE floating point numbers.

For example, in order to determine watertightness of a simple tetrahedron consisting of 4 vertices, 4 triangles/faces, and 6 edges, you need to make sure that when the triangle/face vertices are listed, that the 'same' vertices show up again in the next triangles/faces.

OpenSCAD avoids this problem in its 'polyhedron' command by creating a points 'dictionary', and subsequently referring to the points by means of their indices into this dictionary.  These integer indices can be robustly compared for identity without any 'fuzz'.

Unfortunately, an .stl reader must create such a 'points' dictionary when reading the file, so as to ensure correct interpretation in subsequent triangles/faces.

The good news is that so long as 'write-number' (or whatever its name is) is a _function_, always producing exactly the same characters (for ascii output), or exactly the same bits (for binary output), then vertex equality is preserved in the process sequence write;read.

Unfortunately, unless writing & reading are carefully done, vertex _inequality_ may NOT be preserved, and 2 previously different nodes may be incorrectly 'aliased' together by the write;read process.

This is why I suggest using _binary_ rather than _ascii_ .stl files.

BTW, my personal .stl reader simply treats x,y,z coordinates as _uninterpreted_ 32-bit unsigned quantities, which I then use to build my 'points dictionary'.  Only after I've already created my points, triangles/faces, and edges data-structures, do I finally 'interpret' these 32-bit bitstrings in the 'points dictionary' as IEEE floating point numbers.

The only time that 'fuzz' might be required for .stl reading is to 'repair' some poorly constructed .stl file.

At 05:15 AM 6/25/2013, Tom Cook wrote:
>Hi Henry,
>
>As a computer scientist, I'd hope you would understand that comparing floating-point numbers is a bad idea. Â Even if you do manage to produce two bit-pattern-identical numbers, as soon as you scale, rotate or translate the output in any way the result will depend on the CPU vendor, the CPU model, the mode the CPU is operating in, the operating system, the compiler, the compiler options, the compiler floating-point model, 32vs64-bit OS, SIMD v x87 operations, runtime v compile-time evaluation... Â
>
>So while you can put the same number through exactly the same code path and generally expect the same result, you can't run "the same piece of software" on the same input on different machines or at different times and guarantee (or even expect) the same result. Â It is certainly possible to create software that executes the same sequence of instructions in different threads and produce different results. Â Trying to guarantee identical results is a bad idea- you're only setting yourself up for a lot of pain when you realise it doesn't work. Â See here for a chart that details *some* of the complexities:Â http://randomascii.files.wordpress.com/2012/03/image6.png
>
>What I'm getting around to is that this sort of fuzzing is always going to be necessary. Â Utterly unavoidable. Â ASCII-format STL files are the least of your problems.
>
>Regards,
>Tom
>
>On Tue, Jun 25, 2013 at 12:21 AM, Henry Baker <[hidden email]> wrote:
>Hi:
>
>I'm a computer scientist who just started using OpenSCAD a few months ago & am very impressed.
>
>However, I'm curious about a few things:
>
>1. Â How come OpenSCAD outputs _ascii_ .stl files instead of _binary_ .stl files ? Â I have written code for writing .stl files of both types, and I find it is actually easier to write a _binary_ .stl file, and more importantly, the _interpretation_ of the resulting .stl file is more consistent.
>
>Binary .stl files depend upon the IEEE binary 32-bit floating point standard, which is much more tightly specified than is ascii floating point. Â As a result, when you write out a triple to a binary .stl file & read it back it, it will be always recognized as being exactly the same number, whereas with ascii representations, the reader program may assign a slightly different floating point binary number to that ascii floating point number, so that the triples no longer match exactly.
>
>Thus, an ascii .stl reader may need some sort of 'fuzz'/'tolerance' to recognize the 'same' point, whereas this won't be necessary with binary .stl files.
>
>(It should also be pointed out that the standard interpretation of 'normals' in .stl files is _outwards_, whereas the OpenSCAD interpretation of the polyhedron command is _inwards_; i.e., in 'thrown together' mode, the .stl interpretation will yield 100% pink!)
>
>I've noticed that 'netfabb Studio' complains about some of the known 'watertight' output from OpenSCAD; it is possible that some of these complaints may stem from the use of _ascii_ rather than _binary_ .stl files. Â (Or perhaps netfabb Studio simply has bugs in its watertightness code.)
>
>2. Â Running OpenSCAD on a faster/bigger machine doesn't seem to speed up CGAL rendering. Â I assume that faster CGAL rendering requires paying $$$ ??
>
>3. Â I've noticed that putting two identical cubical blocks (produced with the 'polyhedron' command) side-by-side _exactly_, doesn't seem to work very well; the faces don't cancel one another correctly. Â (I hope this isn't due to the 'fuzz' issue mentioned in #1, above.) Â I find I have to laboriously remove the faces myself before stitching the blocks together into a single object. Â This can't be right, as it eliminates the whole advantage of CSG operations.
>
>4. Â Is there any way to have the effect of a 'mapping' operation ? Â More importantly, is there any way to construct a new sequence/vector of length determined at run time? Â I'd even be willing to write the computed vector to a file & read it back in !!
>
>I'm sure you've been asked this last question before!
>
>Henry Baker
>Santa Barbara, CA

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Binary .stl files & point 'equality'

nophead
The problem is STL files use floating point so you can't avoid it. You can however use binary or ascii, which is the subject of this thread. If points that were separate in the model get merged when rounded to floats then the topology is corrupted make objects no longer 2 manifold.


On 25 June 2013 22:20, Tom Cook <[hidden email]> wrote:

So, as I've been saying, if it's a precise concept, you shouldn't be using floating point numbers to assess it. Really.

On 25 Jun 2013 22:05, "nop head" <[hidden email]> wrote:
"water-tightness " in this context is nothing to do with the physics of water. It is a topological concept.


On 25 June 2013 21:45, Tom Cook <[hidden email]> wrote:

Hi Henry,

As others have pointed out, double precision allows you to model common objects to subatomic level.  So you only need equality comparisons to assess water-tightness if your "water" is pretty strange stuff.  In practice, many structures with vertices that are not exactly equal will be water-tight, depending on local temperature and atmospheric pressure.

And it is trivially easy to produce a program that mis-processes geometry to produce inequality.  Is your program multi-threaded?  Do you use direct3d? Or does a library you use also use direct3d? Oops, now you get different geometry results from different threads.

If you are checking for equality of floating point numbers, you are, 99.99% of the time, doing it wrong.

Tom

On 25 Jun 2013 20:42, "Henry Baker" <[hidden email]> wrote:
The problem is that the proper interpretation of .stl files _requires_ the exact comparison of IEEE floating point numbers.

For example, in order to determine watertightness of a simple tetrahedron consisting of 4 vertices, 4 triangles/faces, and 6 edges, you need to make sure that when the triangle/face vertices are listed, that the 'same' vertices show up again in the next triangles/faces.

OpenSCAD avoids this problem in its 'polyhedron' command by creating a points 'dictionary', and subsequently referring to the points by means of their indices into this dictionary.  These integer indices can be robustly compared for identity without any 'fuzz'.

Unfortunately, an .stl reader must create such a 'points' dictionary when reading the file, so as to ensure correct interpretation in subsequent triangles/faces.

The good news is that so long as 'write-number' (or whatever its name is) is a _function_, always producing exactly the same characters (for ascii output), or exactly the same bits (for binary output), then vertex equality is preserved in the process sequence write;read.

Unfortunately, unless writing & reading are carefully done, vertex _inequality_ may NOT be preserved, and 2 previously different nodes may be incorrectly 'aliased' together by the write;read process.

This is why I suggest using _binary_ rather than _ascii_ .stl files.

BTW, my personal .stl reader simply treats x,y,z coordinates as _uninterpreted_ 32-bit unsigned quantities, which I then use to build my 'points dictionary'.  Only after I've already created my points, triangles/faces, and edges data-structures, do I finally 'interpret' these 32-bit bitstrings in the 'points dictionary' as IEEE floating point numbers.

The only time that 'fuzz' might be required for .stl reading is to 'repair' some poorly constructed .stl file.

At 05:15 AM 6/25/2013, Tom Cook wrote:
>Hi Henry,
>
>As a computer scientist, I'd hope you would understand that comparing floating-point numbers is a bad idea. Â Even if you do manage to produce two bit-pattern-identical numbers, as soon as you scale, rotate or translate the output in any way the result will depend on the CPU vendor, the CPU model, the mode the CPU is operating in, the operating system, the compiler, the compiler options, the compiler floating-point model, 32vs64-bit OS, SIMD v x87 operations, runtime v compile-time evaluation... Â
>
>So while you can put the same number through exactly the same code path and generally expect the same result, you can't run "the same piece of software" on the same input on different machines or at different times and guarantee (or even expect) the same result. Â It is certainly possible to create software that executes the same sequence of instructions in different threads and produce different results. Â Trying to guarantee identical results is a bad idea- you're only setting yourself up for a lot of pain when you realise it doesn't work. Â See here for a chart that details *some* of the complexities:Â http://randomascii.files.wordpress.com/2012/03/image6.png
>
>What I'm getting around to is that this sort of fuzzing is always going to be necessary. Â Utterly unavoidable. Â ASCII-format STL files are the least of your problems.
>
>Regards,
>Tom
>
>On Tue, Jun 25, 2013 at 12:21 AM, Henry Baker <[hidden email]> wrote:
>Hi:
>
>I'm a computer scientist who just started using OpenSCAD a few months ago & am very impressed.
>
>However, I'm curious about a few things:
>
>1. Â How come OpenSCAD outputs _ascii_ .stl files instead of _binary_ .stl files ? Â I have written code for writing .stl files of both types, and I find it is actually easier to write a _binary_ .stl file, and more importantly, the _interpretation_ of the resulting .stl file is more consistent.
>
>Binary .stl files depend upon the IEEE binary 32-bit floating point standard, which is much more tightly specified than is ascii floating point. Â As a result, when you write out a triple to a binary .stl file & read it back it, it will be always recognized as being exactly the same number, whereas with ascii representations, the reader program may assign a slightly different floating point binary number to that ascii floating point number, so that the triples no longer match exactly.
>
>Thus, an ascii .stl reader may need some sort of 'fuzz'/'tolerance' to recognize the 'same' point, whereas this won't be necessary with binary .stl files.
>
>(It should also be pointed out that the standard interpretation of 'normals' in .stl files is _outwards_, whereas the OpenSCAD interpretation of the polyhedron command is _inwards_; i.e., in 'thrown together' mode, the .stl interpretation will yield 100% pink!)
>
>I've noticed that 'netfabb Studio' complains about some of the known 'watertight' output from OpenSCAD; it is possible that some of these complaints may stem from the use of _ascii_ rather than _binary_ .stl files. Â (Or perhaps netfabb Studio simply has bugs in its watertightness code.)
>
>2. Â Running OpenSCAD on a faster/bigger machine doesn't seem to speed up CGAL rendering. Â I assume that faster CGAL rendering requires paying $$$ ??
>
>3. Â I've noticed that putting two identical cubical blocks (produced with the 'polyhedron' command) side-by-side _exactly_, doesn't seem to work very well; the faces don't cancel one another correctly. Â (I hope this isn't due to the 'fuzz' issue mentioned in #1, above.) Â I find I have to laboriously remove the faces myself before stitching the blocks together into a single object. Â This can't be right, as it eliminates the whole advantage of CSG operations.
>
>4. Â Is there any way to have the effect of a 'mapping' operation ? Â More importantly, is there any way to construct a new sequence/vector of length determined at run time? Â I'd even be willing to write the computed vector to a file & read it back in !!
>
>I'm sure you've been asked this last question before!
>
>Henry Baker
>Santa Barbara, CA

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Binary .stl files & point 'equality'

Henry Baker
In reply to this post by Tom Cook
At 01:45 PM 6/25/2013, Tom Cook wrote:
>If you are checking for equality of floating point numbers, you are, 99.99% of the time, doing it wrong.

Tom,

Ordinarily, I would agree with you, but in the specific case of reading .stl files, bit-level equality works just fine, because I compare these bit strings _before I realize that they are floating point numbers_.  This is a highly constrained situation, where the bit-level format is completely defined as little-endian 32-bit IEEE binary floats, and I am required to ascertain when one vertex is 'the same' as a previously-read vertex.

"BTW, my personal binary .stl reader simply reads x,y,z coordinates as _uninterpreted_ 32-bit unsigned quantities, which I then use to build my 'points dictionary'.  Only after I've already created my points, triangles/faces, and edges data-structures, do I finally 'interpret' these 32-bit bit strings in the 'points dictionary' as IEEE floating point numbers."

---
IEEE 32-bit binary floats allow for the existence of 'gradual underflow', negatively signed zeros, and Not-a-Numbers (NaN's).

Gradually underflowing numbers require an additional step in conversion from bit-strings, but are otherwise non-problematical.

I haven't encountered negatively signed zeros or NaN's yet in processing .stl files.  NaN's would presumably be out-and-out errors, while a negatively signed zero is considered to be not equal to a positively signed zero.  The reason is that if this number is one of the coordinates of vertex v, then the same 'write-number' routine should be utilized each time this vertex is encountered, in which case the exact same bit string will be written -- either +0.0 or -0.0, but never +0.0 one time and -0.0 another time.
---

BTW, floating point numbers aren't some mysterious quantum numbers whose value is randomly determined every time we look at them.  They are classical entities defined by the IEEE committee.  Yes, some of the subtleties aren't always implemented, like NaN's, gradual underflow, or 100% precise rounding, but these are only affected by _operations_ on floating point numbers, and not by simple transmission (reading/writing).

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Binary .stl files & point 'equality'

Alan Cox
On Tue, 25 Jun 2013 14:49:12 -0700
Henry Baker <[hidden email]> wrote:

> At 01:45 PM 6/25/2013, Tom Cook wrote:
> >If you are checking for equality of floating point numbers, you are, 99.99% of the time, doing it wrong.
>
> Tom,
>
> Ordinarily, I would agree with you, but in the specific case of reading .stl files, bit-level equality works just fine, because I compare these bit strings _before I realize that they are floating point numbers_.  This is a highly constrained situation, where the bit-level format is completely defined as little-endian 32-bit IEEE binary floats, and I am required to ascertain when one vertex is 'the same' as a previously-read vertex.

This makes an assumption about the STL file being read but it certainly
makes a lot of sense.

The problem IMHO is much more mundane than floating equality for a lot of
the issues around being manifold. It's a straight "third normal form"
problem. STL is misdesigned because it stores multiple occurrences of
what should be the same point repeatedly rather than via a dictionary
with a single definition of the point.

In openscad the same problem occurs because there is ambiguity and fuzz
in the co-ordinates because they expressed as co-ordinates rather than
describing a set of points and describing the objects in terms of them.

I'm not sure I'd care to work in an environment that constructed all of
its objects this way. It would be a fairly painful process for any
language version that I can think of right now. Setting up shapes in
blender python ain't exactly fun.

You could allow the definition of a "point" and allow its use in the
language by passing co-ordinates not point,size but you'd have to
propogate that through the whole engine which sounds like a rewrite - and
you might as well just quantize it all and be done with it if so ?

Alan
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Binary .stl files & point 'equality'

kintel
Administrator
On 2013-06-25, at 18:01 , Alan Cox wrote:
> […] and you might as well just quantize it all and be done with it if so ?
>
On the topic of quantization - we do that in OpenSCAD to avoid infinitely sub-floating point details.
However, our "quantizator" isn't topology-aware and will actually destroy manifoldness in some cases.
Lots of fun work to be done here…

 -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Binary .stl files & point 'equality'

Henry Baker
BTW, I put my .stl reader (which initially treats x,y,z values as uint32's, and then hashes them into a vertex table with these xyz 96-bit keys) together with a trivial .scad 'polyhedron' writer (which dumps out a polyhedron 'points' vector and a polyhedron 'triangles' vector with indices back into the 'points' vector).

I can now convert any binary .stl file into an .scad polyhedron.  This is how I noticed that the normals all had to be reversed when going from .stl to .scad.

I've been able to convert some pretty large .stl files into .scad files; some with hundreds of thousands of edges; OpenSCAD can even process them!  (OpenSCAD sees them as a single polyhedron command).

This program isn't written in C -- it's in Common Lisp -- but it would take only a day to convert it into C.

At 03:12 PM 6/25/2013, Marius Kintel wrote:
>On 2013-06-25, at 18:01 , Alan Cox wrote:
>> […] and you might as well just quantize it all and be done with it if so ?
>
>On the topic of quantization - we do that in OpenSCAD to avoid infinitely sub-floating point details.
>However, our "quantizator" isn't topology-aware and will actually destroy manifoldness in some cases.
>Lots of fun work to be done here…
>
> -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Binary .stl files & point 'equality'

kintel
Administrator
On 2013-06-25, at 18:44 , Henry Baker wrote:
> I can now convert any binary .stl file into an .scad polyhedron.  This is how I noticed that the normals all had to be reversed when going from .stl to .scad.
>
Actually, I've been thinking about supporting "inlining" of external files; converting dxf to polygons and stl to polyhedron, to avoid external dependencies in scripts. Not sure how useful it would be, so it hasn't been given priority yet..

 -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Binary .stl files & point 'equality'

Henry Baker
I would imagine that importing .stl into .scad would be useful when incorporating 3D 'scanned' objects with OpenSCAD constructed objects.

MeshLab does a pretty good job cleaning up scanned objects, I have been told.

At 05:18 PM 6/25/2013, Marius Kintel wrote:
>On 2013-06-25, at 18:44 , Henry Baker wrote:
>> I can now convert any binary .stl file into an .scad polyhedron.  This is how I noticed that the normals all had to be reversed when going from .stl to .scad.
>
>Actually, I've been thinking about supporting "inlining" of external files; converting dxf to polygons and stl to polyhedron, to avoid external dependencies in scripts. Not sure how useful it would be, so it hasn't been given priority yet..
>
> -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Binary .stl files & point 'equality'

kintel
Administrator
On 2013-06-25, at 20:25 , Henry Baker wrote:

> I would imagine that importing .stl into .scad would be useful when incorporating 3D 'scanned' objects with OpenSCAD constructed objects.
>
Yes, it's becoming more and more useful as more people use STLs and more people produce STLs..

I should put this on the wiki (from an off-line writeup I have lying around:

OpenSCAD fails on border-case STL models. This is typically caused by things like co-incident vertices caused by floating point inaccuracy. To improve this, this is the suggested path:

o Refactor the internal mesh representation (core developer task)
o Write some simple mesh-repair methods; e.g. co-indicent vertex removal (look at e.g. MeshLab for typical operators, as well as implementation hints)
o Look at opportunities for implementing surface optimization techniques (e.g. null-decimation)
o Extend the mesh representation as needed

Difficulty: Medium, but could be relatively isolated once the refactoring is in place

 -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
Reply | Threaded
Open this post in threaded view
|

Re: Binary .stl files & point 'equality'

kintel
Administrator
On 2013-06-26, at 24:18 , Marius Kintel wrote:

> […] I should put this on the wiki

duh - I beat myself to it: https://github.com/openscad/openscad/wiki/Ideas-for-Development-Tasks

 -Marius

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://rocklinux.net/mailman/listinfo/openscad
http://openscad.org - https://flattr.com/thing/121566
123