What strikes me as unclear on first sight is, in CMake WITH_GMP is an option, yet most of the code files seem to include gmpxx.h assuming it's going to be there, is GMP going to be optional?

I'll have to see if i can make GMP work with msvc, thanks for including unit tests from the start, should make the process much faster!

The code uses gmpxx.h but it includes gmp.h, Most of the real code is in C and gmpxx.h is close to a headers-only wrapper around the C types. But there is a small corresponding c++ source file that defines mainly the stream I/O functions.

When I configured gmp from its download, I used the flags --prefix=my-preload-lib-dir/gmp and --enable-cxx and --disable-shared. I also added some other debugging flags but those won't be necessary for distributition.

Is it OK to add gmp to the dependencies for Blender? Is the way I did it OK? (What I have done to get the library found doesn't work yet, and I haven't yet done the code that could retrieve and build the library in the precompiled library area, but that is my intention.)

I think it's ok.

I have been experimenting with a style that makes heavy use of references rather than pointers, for function arguments, and heavy use of returning big structures from routines. My intention is to write move-constructors, move-copiers, and move-assignment operators such that in almost all cases these returns of big structures just copy pointers from the about-to-be-destroyed source). This seems to me to be the recommendation of the latest C++ coding guidelines. Do you all agree with this idea?

No problem with this.

What do you think of the general idea of having C++ templatized versions of (some of) the BLI_math and BLI_vector routines?

Personally I wouldn't try to match naming of the C BLI_math functions and use operator and function overloading. The only reason we have such verbose function names is because that's missing in C. I'd try to be consistent with BLI_float2/3.hh as much as possible instead.

I would keep these classes as specifically intended for exact arithmetic, maybe in files named BLI_exact_math_*.hh, and types in their own namespace like BLI::exact_math::vec3.

If these can share a base class with BLI_float2/3.hh that could help, but I don't think it's important or necessarily helpful to tie these things together through sharing a base class rather than just manually keeping them consistent.

The reason I didn't just go for something like BLI::exact_math::vec3 is that I want not to repeat code in the delaunay, intersect, and boolean code for both double and gmpq_class. I could solve this by using an abstract base class for vec and vec3, but then wouldn't all the actual functions operating on those require using virtual functions, costing an extra indirection (and probably not getting the benefit of inline, though I may be wrong there). Those problems go away, at the expense of (nearly) duplicated machine code, by using the templated solution. Brecht, do you have a preference for the derived-class method of doing this, or am I missing something/making a mistake?

If I keep going with my templated Vec2<T> and Vec3<T> method, would you prefer that I drop the parts of the names that are disambiguated by argument type? E.g., using dot(Vec2<T>,Vec2<T>) and dot(Vec3<T>,Vec3<T>) instead of dot_v2v2(Vec2<T>, Vec2<T>) and dot_v3v3(Vec3<T>, Vec3<T>) ?

Another possibility would be to just abandon the idea of making these library routines (CDT, intersect, boolean) work with double, and make them only work for exact arithmetic. There is some attraction to doing that -- it is easier to develop without templates, and it is not clear I can easily make the double versions of intersect and boolean work, even approximately, without a lot of extra code that isn't needed when we are using exact arithmetic. The only (perhaps big) downside is that if some internal or external users want (much) faster versions of these routines. There's something like a 20x slowdown using exact arithmetic. I will try to alleviate that by using floating point filters for predicates, but there is no fast thing to do when I actually have to calculate new points.

So would also like an opinion on that: should i just do exact-arithmetic-only versions of these routines?

I have been experimenting with a style that makes heavy use of references rather than pointers, for function arguments,

This is good imo.

and heavy use of returning big structures from routines.

This fine, especially with guaranteed copy elision in C++14.

I definitely agree with Brecht that operator overloading should be used whenever appropriate. Functions like add_v2v2 really should not need to exist in C++.

I do not think that types like float3 should be generalized more in Blender. If we would generalize it, it is unclear to me at which level to stop with the generalization. You suggest to use a template for the type. Later we might want to generalize the size (combine float2 and float3). Even later we might want to generalize the number of dimensions, as in combining float3 and float4x4. Those generalizations are useful sometimes, but for the majority of Blender we really just need float3. I'm not entirely sure, but templating this type more could result in quite bad error messages, longer compile times and a worse debugging experience. Furthermore adding convenience functions that only make sense for a specific type like float3 becomes harder. An abstract base class could work of course, but virtual function calls for these simple operations are really a no-go imo.

Nevertheless, I see the need for being able to write code that can be templated to use e.g. either float3 or mpq3 (I'll just call it like that for now). I think we can have completely separate types and still write templated code that can use different types.
First, as Brecht already said, we should make sure that float3 and mpq3 have the same interface. However, just doing that is not enough, because we'd probably need many auto keywords in the procedures.

I just did a small test with a potential solution: P1433. The only issue is that in this solution T cannot be deduced from float3 automatically. That does add a little bit of overhead, but it seems to be ok. What do you think?

If there are some functions that will likely only work with exact arithmetic, they should only be implemented for exact arithmetic. I don't see any benefit of having templated functions when only one instantiation is going to work anyway.

Thanks for looking, Jacques and Brecht. Did you happen to notice any other strangeness in a quick glance at my C++ code? I am not an expert in C++ , and especially that enhancements to C++ that have happened since I last seriously coded in it (more than 10 years ago),, so am happy to have things pointed out to me.

It looks like I first have to make the choice: should I only try doing Intersect and Boolean for mpq3? I had some rather different code working, using doubles, and tuned it so that it was about on par with the current BMesh boolean in performance. The problem was, it was very hard to make it so that consistent choices are made when intersecting an edge with a face (when the intersection is near the edge or vertex of the face). I was trying various caching and canonicalization strategies but it just wasn't coming together with reliable results when the features started to get very small. So I decided to try this exact-arithmetic implementation.

An important basic subroutine needed for general mesh intersection is the Constrained Delaunay Triangulation. I got this to work in both double arithmetic and mpq arithmetic, and would kind of like to put both versions in Blenlib. Initial timing showed that the mpq version was about 20 times slower than the double version, but I have yet to experiment with using double filters to make it faster so don't know if I could get the mpq version to be good enough, performance-wise, that that need be the only one in Blenlib. For small problems it would be fine. But one external addon developer wanted to use it to handle million vertex problems.

The intersection routine (needed before doing Boolean) is another question. I suspect it will kind of work in double arithmetic with a couple epsilon tests, some canonicalization, and some caching; but how good is "kind of"? Does that mean "as good as current BMesh" or worse than that? This is unknown. Hence I was trying to use templated code for now, so that I could decide later. But now we are at the point of: is it worth it even to try? Maybe I should just write mpq3 code for intersection and boolean and work as hard as I can to make it performant?

Anyway, whether or not I make such a choice, it appears that both of you do not like the math_tpl.hh approach I took, so I will change that. I can make mpq3.hh and double3.hh interfaces. The double3.hh one wouldn't be necessary if I make the choice to doing only mpq3 versions of both CDT and intersect/boolean. If I do decide to try to make double versions some of them, then the approach in Jacque's paste looks OK to me. (I think, if I understand it correctly, I would still be writing templated code -- just that the T type would now be one of mpq3 or double3. Right?)

I think, if I understand it correctly, I would still be writing templated code -- just that the T type would now be one of mpq3 or double3. Right?

T would be mpq_class or double in my example. vec3<T> will become mpg3 when T is mpq_class and it will become double3 when T is double.

Is the full boolean implementation working already or do you currently just test the performance of individual subroutines? It might be best to simply write the entire implementation for exact arithmetic first, to see if the quality turns out to be as good as expected. I guess that templating some of that code afterwards should be relatively straight forward.

I have a couple of small notes on the code style. Nothing super important though. It seems to be generally fine.

• When a class has only public members, it could also be a struct.
• Instead of typedef enum ... { ... } ...; just use enum ... { ... } or enum class ... { ... }.
• Looks like you are missing a couple of inline keywords. For example for interp_v2v2.
• Reduce scope of variables by declaring them when they are first used when possible. For example, in id_range_in_list there is no need to declare the two variables in the first two lines and leave them uninitialized.

Thanks, Jacques.
Right now:

• delaunay works in double and mpq
• intersect is very close to done for mpq; I have't tried testing the double version of it yet.
• boolean is not yet started with this redo, though there is stuff I can copy from my previous non-exact implementation.

So I think I will take your advice and do intersect and boolean as mpq-only for now, and perhaps template them afterwards, I have found that IDEs give more help when writing non-templated code, so this will probably speed implementation. Then when it all works and i've tuned it as much as I can, if it just seems too slow to me, then I can consider templating it later, as you say.

LazyDodo: if you are reading this: would it make your life much easier if I didn't use the C++ bindings for gmp? I could spend the time to use the C gmpq_t type directly if so. There may be some advantages to that anyway, as the C++ stuff may be hiding some inefficiencies that would be more obvious if I were implementing the primitive operations on mpq3 and the occasional mpq_class myself.

I think this is fine overall.

I wish we could have a less obscure name than mpq, but I can't come up with a compact and clear alternative so it seems ok. But some code comments explain what this is are needed in the header files.

Thanks for the reviews, Brecht and Jacques. I have now moved this work-in-progress into my newboolean branch. I will incorporate your suggestions there. I will therefore close this revision now.