3 ms·

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

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.

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.