4 ms·

I'm surprised that OpenSCAD uses GMP. I would think that 64-bit doubles would be good enough.

R0b0t1 5y ago
It's wise to pick a library that can act as a portable layer over implementation details.
amelius 5y ago
Perhaps they need it to ensure robustness of geometric predicates, in edge cases. E.g. if the determinant of some matrix becomes too close to zero, switch to exact arithmetic.
ur-whale 5y ago
> I would think that 64-bit doubles would be good enough. Implementing robust boolean operations on polyhedral geometry is and has been known for quite a while to be very hard if you do not have arbitrary precision math, or at the very least some sort of interval arithmetic that kind winds back a calculation and increases the precision up to the point where an unambiguous decision can be made about the sign of an expression. Here's an example: create a sphere, tesselate it to - say - a million triangle (not much these days), make a rotated copy of the original by 0.01 degrees and intersect with the original. I guarantee you the resulting calculation will either crash your floating point based implementation or it'll produce a model that will be non manifold.
- Animats 5y ago
  I used to watch that get better in each release of Autodesk Inventor. A useful test is to model a bolt. Make a cylinder. Make a 2D cutting tool that has one thread profile. Extrude the thread profile along a spiral. Subtract that from the cylinder. Now you have a threaded rod. Now make a 2D hexagon for the bolt head. Extrude. Union with cylinder. Now chamfer all edges of the bolt head. Also chamfer the end of the bolt. Now take a close look at where the threads meet the bolt head, and where the threads meet the chamfer. If those are all correct, then you have a usable CSG CAD system for machined parts. Inventor started getting that right around 2012. Admittedly, you don't usually model threads at that level of detail. Inventor has "cosmetic threads", which are just textures, which is what you use for ordinary bolts. This is mostly an exercise for CAD operators. It's like whiteboarding for programmers. You sit the applicant down at a workstation, hand them a bolt and calipers, and say "model this". Sometimes you do need that kind of detail, because you're going to have a machine tool machine the thing.
  - dekhn 5y ago
    Fusion 360 handles this perfectly. In fact it has thread creation directly built in (both textured and modelled explicitly). I recently needed to make a nut for a specific thread, and did it by subtracting the thread from a volume. If you're careful you can inspect the results and see how to offset the thread slightly to move from a too-tight fit to a simple press fit.
    - Animats 5y ago
      Fusion 360 is the same CSG engine as Inventor. It just has fewer features and is tied to "the cloud". Inventor has pro features such as "would you like a finite element analysis of the weak points in that", and "Warning - gear tooth counts are not relatively prime and may result in uneven wear".
      - deleted 5y ago
        [deleted]
      - Tossrock 5y ago
        Fusion360 has FEA in the Simulation workspace.
ChrisLomont 5y ago
64-bit doubles are not good enough for a production cad system. Many operations, including CSG, may require much more precise numbers to resolve the question of if and how things intersect, if surfaces remain manifold or fail to be orientable, and on and on. Those things needing (to be careful) arbitrary precision can sometimes be truncated back to 64 bit doubles, as long as necessary invariants are maintained. A simple example: suppose you have a shape at the origin, that is designed for careful CNC, so maybe 1/10,000th of an inch or maybe even 1/100,000th of an inch accuracy. Suppose 1/10,000th accuracy is, say, ~14 bits of mantissa, then making the part 16 inches long is another 4 bits. We're up to 28 bits. Now suppose you do an operation, like intersection with another such part, or a fillet or rounding, whose computation merely needs to square numbers. Now you need 28*28 bits, anf you overflow the mantissa. Or move the part out to coordinate 64, uses another 6 bits. And god forbid you hit an algorithm that needs to cube numbers, which triples the number of bits you need in order to retain accuracy needed for the final part to meet tolerances. It gets troublesome quite quickly.
- sokoloff 5y ago
  Wouldn’t ~14 bits down to 10^-4 plus 4 bits to get to 2^4 be ~18 bits rather than ~28?
  - ChrisLomont 5y ago
    Yep, made error as I was editing it xamples. The underlying idea stands- bits get used up very quickly in many CAD algorithms.
- adgjlsfhk1 5y ago
  If 64 bit doubles aren't enough, why not use libquadmath? It gives you 113 bits of mantissa, and should be around 10x faster than arbitrary precision.
  - ChrisLomont 5y ago
    113 bits will still fail on iterative processes. If you dig into probably any of the robust kernels of things like parametric modelers, they all need these methods. The above example I gave is terribly naive: things get vastly worse. Above was only position. Now build in Bezier surfaces, or better yet, NURBs so you can do true conics as well as crazy freeform surfaces. Now compute the intersection of such objects. These intersections require very high degree polynomial representations. Now repeat. If you quantize points on the intersection curves too much, you'll get all sorts of pathologies, things doubling back, near singularities .. The way to deal with this flawlessly is to allow whatever precision is needed to prove necessary constraints are met. A good lib would use each representation as needed: double, libdouble, liquid, liboct, etc. as needed, and eventually arbitrary precision. I've written several systems that do such over my career. It's a cool space A nice simple place to try this is to make an arbitrary precision Mandelbrot zoomer that switches underlying types as needed for precision. It's much more fun to make these work on various AVX flavors, or on GPUs. All are doable.

It's wise to pick a library that can act as a portable layer over implementation details.

Perhaps they need it to ensure robustness of geometric predicates, in edge cases. E.g. if the determinant of some matrix becomes too close to zero, switch to exact arithmetic.

ur-whale 5y ago

> I would think that 64-bit doubles would be good enough. Implementing robust boolean operations on polyhedral geometry is and has been known for quite a while to be very hard if you do not have arbitrary precision math, or at the very least some sort of interval arithmetic that kind winds back a calculation and increases the precision up to the point where an unambiguous decision can be made about the sign of an expression. Here's an example: create a sphere, tesselate it to - say - a million triangle (not much these days), make a rotated copy of the original by 0.01 degrees and intersect with the original. I guarantee you the resulting calculation will either crash your floating point based implementation or it'll produce a model that will be non manifold.

Animats 5y ago
I used to watch that get better in each release of Autodesk Inventor. A useful test is to model a bolt. Make a cylinder. Make a 2D cutting tool that has one thread profile. Extrude the thread profile along a spiral. Subtract that from the cylinder. Now you have a threaded rod. Now make a 2D hexagon for the bolt head. Extrude. Union with cylinder. Now chamfer all edges of the bolt head. Also chamfer the end of the bolt. Now take a close look at where the threads meet the bolt head, and where the threads meet the chamfer. If those are all correct, then you have a usable CSG CAD system for machined parts. Inventor started getting that right around 2012. Admittedly, you don't usually model threads at that level of detail. Inventor has "cosmetic threads", which are just textures, which is what you use for ordinary bolts. This is mostly an exercise for CAD operators. It's like whiteboarding for programmers. You sit the applicant down at a workstation, hand them a bolt and calipers, and say "model this". Sometimes you do need that kind of detail, because you're going to have a machine tool machine the thing.
- dekhn 5y ago
  Fusion 360 handles this perfectly. In fact it has thread creation directly built in (both textured and modelled explicitly). I recently needed to make a nut for a specific thread, and did it by subtracting the thread from a volume. If you're careful you can inspect the results and see how to offset the thread slightly to move from a too-tight fit to a simple press fit.
  - Animats 5y ago
    Fusion 360 is the same CSG engine as Inventor. It just has fewer features and is tied to "the cloud". Inventor has pro features such as "would you like a finite element analysis of the weak points in that", and "Warning - gear tooth counts are not relatively prime and may result in uneven wear".
    - deleted 5y ago
      [deleted]
    - Tossrock 5y ago
      Fusion360 has FEA in the Simulation workspace.

ChrisLomont 5y ago

64-bit doubles are not good enough for a production cad system. Many operations, including CSG, may require much more precise numbers to resolve the question of if and how things intersect, if surfaces remain manifold or fail to be orientable, and on and on. Those things needing (to be careful) arbitrary precision can sometimes be truncated back to 64 bit doubles, as long as necessary invariants are maintained. A simple example: suppose you have a shape at the origin, that is designed for careful CNC, so maybe 1/10,000th of an inch or maybe even 1/100,000th of an inch accuracy. Suppose 1/10,000th accuracy is, say, ~14 bits of mantissa, then making the part 16 inches long is another 4 bits. We're up to 28 bits. Now suppose you do an operation, like intersection with another such part, or a fillet or rounding, whose computation merely needs to square numbers. Now you need 28*28 bits, anf you overflow the mantissa. Or move the part out to coordinate 64, uses another 6 bits. And god forbid you hit an algorithm that needs to cube numbers, which triples the number of bits you need in order to retain accuracy needed for the final part to meet tolerances. It gets troublesome quite quickly.

sokoloff 5y ago
Wouldn’t ~14 bits down to 10^-4 plus 4 bits to get to 2^4 be ~18 bits rather than ~28?
- ChrisLomont 5y ago
  Yep, made error as I was editing it xamples. The underlying idea stands- bits get used up very quickly in many CAD algorithms.
adgjlsfhk1 5y ago
If 64 bit doubles aren't enough, why not use libquadmath? It gives you 113 bits of mantissa, and should be around 10x faster than arbitrary precision.
- ChrisLomont 5y ago
  113 bits will still fail on iterative processes. If you dig into probably any of the robust kernels of things like parametric modelers, they all need these methods. The above example I gave is terribly naive: things get vastly worse. Above was only position. Now build in Bezier surfaces, or better yet, NURBs so you can do true conics as well as crazy freeform surfaces. Now compute the intersection of such objects. These intersections require very high degree polynomial representations. Now repeat. If you quantize points on the intersection curves too much, you'll get all sorts of pathologies, things doubling back, near singularities .. The way to deal with this flawlessly is to allow whatever precision is needed to prove necessary constraints are met. A good lib would use each representation as needed: double, libdouble, liquid, liboct, etc. as needed, and eventually arbitrary precision. I've written several systems that do such over my career. It's a cool space A nice simple place to try this is to make an arbitrary precision Mandelbrot zoomer that switches underlying types as needed for precision. It's much more fun to make these work on various AVX flavors, or on GPUs. All are doable.