allow double precision

[pca006132]

While it is not our main usecase, it might be desirable to be able to handle large meshes which requires using 64 bit indices. Note that the mesh itself may not be that large, but there can be many collisions that makes intermediate operation exceed the 32 bit integer range.

Apart from refactoring, we may hit NVIDIA/cccl#744. Doing NVIDIA/thrust#541 first may help.

Also, using larger integer indices will probably come with a performance cost due to the additional memory transfers. I wonder if we should dynamically dispatch the operations to select the best size, int16/32/64 depending on the data size. This will make the code a bit more complicated (additional logic for dispatch, maybe we can make it something like the existing par.h API), but may be worth it.

[elalish]

Considering the additional code complexity involved, I'd prefer to wait on this until it becomes a problem for at least one of our users. I would say switching to double precision is probably a higher priority (float was mostly due to CUDA originally), since we know this is necessary for large-scale engineering design, e.g. ships.

[ramcdona]

I would +1 for double precision as floats really fall on their face so much sooner.

You can always use a #define or a template to make these options compile-time decisions. That would be a lot more simple than some dynamic system that changes types on the fly.

[pca006132]

Indeed, we can use some macro for compile-time decisions. However, I think it would be nice in the long run if we can make it dynamic to avoid performance regression for regular users. We are limited by memory bandwidth for some operations, so changing to larger size will make things slower.

[t-paul]

When looking at compile time decisions, please consider shipping the library as binary. If it's application / library-user compile time, that's cool. If it's library compilation time that can make things difficult. Of course if a dynamic solution is possible, that's awesome.

[ramcdona]

@pca006132 I guess I'm curious how you're defining 'regular users'.

I'm thinking of Manifold as a library -- where the 'user' is actually the developer of an end-user application. In this situation, the developer of the application is probably in a very good position to know the kinds of problems typically encountered by their end users (in size and required precision) and also what kind of performance tradeoff they are willing to make. Here a compile time decision (by the developer) will usually suffice.

For example, in any engineering application, I will avoid floats at all cost. They are basically a subtle bug waiting to happen. Doubles may seem like sweeping the same thing under the rug, but they suffice for most engineering purposes. When they don't, we go to exotic lengths like robust arithmetic and compensated summation to avoid floating point problems. When we do that, we are acutely aware of exactly where our precision is running out and we likely want to delay it as much as possible.

Perhaps you're thinking of Manifold as an end-user application (say ManifoldCAD.org). In that case, you could possibly argue that you have no idea the size and scope of problem that an end user will bring -- and that you will need to trade precision for speed dynamically.

However as an end user, that kind of behavior scares me. Imagine I start with a simple problem and add complexity as my project moves forward. When the problem is simple, your heuristic uses double precision because computation is cheap. At some point, your heuristic is going to decide that it needs to switch to floats to improve performance. As a user, I might not immediately notice the loss of precision (though I may appreciate the performance), but when that loss in precision comes to bite me, it will hurt. Making this kind of change invisible to a user is scary to me.

I feel that much of the argument for Manifold extends to this conversation -- non-manifold results may be good enough for graphics and animation (the eye forgives what it does not see) -- and likewise floats are good enough to send to a graphics card to generate pixels. However, for serious work, I would only use floats if I had done a very detailed study of my particular application to know if I could get away with them. Using floats is a clear example of premature optimization to me.

The counter example is when you are trying to develop algorithms that are robust to truncation error -- in this situation, using floats (that cause the TE to occur earlier and more obviously) can make it easier (by introducing the bug you're trying to fix). However, when these algorithms are put to real use, one would switch back to doubles to provide a belt and suspenders approach to truncation error.

All this is to say that being able to switch the fundamental data type is handy. Whether float, double, double-double, quad-double, or whatever.... Or to use complex numbers, or automatic differentiation via operator overloading, or something I haven't thought of, flexibility in type is good for the developer.

If I were developing an end-user application where I had determined that I needed the ability to change precision dynamically, I would develop my code with either a #define or templated data type. I would then compile it multiple times -- each wrapped up in a different namespace.

That way, I could then have my application access the library using the namespaced versions of the code. The goal would be to keep all the complexity of dynamic precision out of the library and in the application that needs it.

[pca006132]

I would consider regular users as users building small stuff (e.g. most users using OpenSCAD, or Nomad Sculpt) where the precision of float is sufficient for their use cases.

The way I think about dynamically switching precision is actually the opposite of what you think: we should switch to double when the magnitude of the coordinates are large, and never switch from double to float. In practice this is probably making already slow operations (using float) even slower (due to switching to double), though this is not very accurate because our slowness mainly come from the complexity of the mesh instead of the magnitude of the coordinates.

In fact, after thinking for a while, I think we should probably go with template and let the users choose which precision they want. The wasm and python bindings (end-user facing part) can decide whether to use float or double based on the magnitude of the coordinates, and users can override the decision using some kind of flags. Applications using manifold as a library can do their own decision and we will respect that.

[elalish]

@t-paul We've been struggling through getting binary Python wheels building on our CI for deployment, thanks to @pca006132. I'm less clear on a good approach for C++ binary distribution and I'm also not sure how it fits with NVIDIA/thrust#554. If anyone does know how to make a good automation process for binary distribution, I would welcome a PR.

My only concern about making precision a template is that it might make compilation crazy, but I bet the rest of you know more about that than I do, so please chime in. @ramcdona you hit the nail on the head with "Doubles may seem like sweeping the same thing under the rug" - we're taking a different approach to rounding error in this library than traditional computational geometry libraries, so the point is to guarantee robustness without robust arithmetic or extended precision. So for me, double precision is not at all about robustness, but just coordinate accuracy. Agreed that the precision should never surprise the user.

[pca006132]

I think template should not cause much issue, we can do specialization which should make the compile time manageable. If there is interest on this, I can work on it.

[elalish]

When I talked to the Rhino CAD guys years ago I remember they said float precision was a hard blocker for them because of the physical scale of the engineering projects they're used for, so yes, I think double precision is important, especially now that CUDA is gone. This will make the library useful far beyond e.g. 3D printing.

[t-paul]

If anyone does know how to make a good automation process for binary distribution, I would welcome a PR.

I'm not sure you need to release binary libs directly. What I wanted to point out is the different times a feature set can be decided.

Example where we hit that issue is GLEW which for Linux supports both GLX (like the classic OpenGL window on X11) interface and EGL (works even headless on Linux commandline) for GL context creation.

GLEW has the decision as compile time switch at library compilation time. So Debian ships the GLX library version and there's no trivial chance to use EGL. Just replacing the package with one that supports EGL would potentially break other apps that expect GLX.

I'd be ok if we could select GLX/EGL at application compile time if there would be a binary libglew-dev package that supports both and gives the decision to the application.

Now that's not a point for header-only libraries or when assuming to always rebuild libraries along with the application. But at least the current state on Linux it's mostly prefered to ship shared libs which can be security fixed once for everyone depending on the library code.

[ramcdona]

In my experience, the difficulty in distributing binaries is one of combinatorics.

For a long time, we built binaries for Mac and Windows -- and we assumed that Linux users were smart enough to compile for themselves. This turned out to be less true than we had hoped.

Taking on a Linux binary build means you have to choose one or more distribution -- Debian, Ubuntu, RedHat, whatever -- and also which version (Ubuntu 20.04, 22.04, etc.) While I'm sure it is possible, cross-building Linux packages is more complex -- i.e. GitHub's CI is based on Ubuntu, so that is easy, but using GitHub's CI to build RedHat packages is surely more complex. So now the more flavors of Unix you want to support (FreeBSD, NetBSD, Slackware, SUSE, RedHat, etc.) you need a large number of CI servers. Our CI is on GitHub, so we build Ubuntu packages and that is it. Our CMake is set up to build RedHat / Centos packages, so users on those platforms can make their own *.rpm's.

My program uses SWIG to generate Python bindings for our C++ API. Now you have to deliver a binary package that matches a targeted version of Python (3.6, 3.9, 3.10, 3.11, etc). At a minimum, the binding needs to match the architecture (x86, x86-64, Aarch64), and I've sometimes had issues requiring that I match the same Python as built and packaged with Anaconda vs. an independent download of Python.

From what I can tell, matplotlib provides about 40 pre-built binary packages. That is just the major desktop platforms -- it gets substantially worse if you want to include RasberryPy, Game Consoles, Phones, Tablets, etc.

[t-paul]

This gets a bit off-topic, so I'll only add that OpenSUSE provides some nice means for building packages for a good range of distributions via their OpenSUSE Build Service (OBS, but not the streaming thing).
https://build.opensuse.org/package/show/home:t-paul/OpenSCAD

[elalish]

I'm changing the title to match the discussion. I don't think we want to distribute pre-built C++ packages - that sounds like a lot of work.

[fire]

In other places it's possible to use a custom type that users can redefine to be either float32_t or float64_t. Like by macros.

[pca006132]

Figured this may be easier to deal with than the 64 bit integer thing, and more important for our users. I will probably do this first.

@elalish I think MeshGL should remain using 32 bit float, but everything else should change, right?

[elalish]

I think MeshGL should remain using 32 bit float, but everything else should change, right?

Yes, and we should also make a MeshGL64, though that can be a separate PR.