The projects now include the just-added incremental insert/remove for Delaunay triangulation.

Ported the incremental insertion and removal of points for a Delaunay 2D triangulation from Wild Magic to GTE. The Wild Magic code did not correctly handle removing points from the convex hull boundary of the triangulation. I fixed this by adding a new subsystem to correctly retriangulate the removal polygon. A sample application has been added to illustrate.

The current notes are for 5.8. Removed the 5.5 and 5.6 notes.

Added constructor to MinHeap::Result with initialized members to avoid MSVS code analysis warnings.

The Delaunay2 code was failing on a platform using a virtual machine and Microsoft Visual Studio 2015. The problem is that the compiler is optimizing away some floating-point expressions that should not be due to rounding mode. I mentioned this problem in Section 3.4 of https://www.geometrictools.com/Books/RobustAndErrorFreeGeometricComputing/RAEFGC_BookCorrections.pdf. I removed the final uses of std::fesetround and std::fegetround, replacing them with SWInterval interval arithmetic support that works with the default FPU rounding mode (round to nearest ties to even). These modifications affect only the new ConstrainedDelaunay2 and Delaunay2 implementations. The older implementations do not use <cfenv> for floating-point environment changes, and they are currently tagged as deprecated but will exist until the full GTL distribution is available.

The deprecated code in ConstrainedDelaunay2 (the first implementation in the header file) had a bug in Retriangulate that was introduced based on my blindly following a suggestion by the Microsoft Visual Studio code analysis tool. The description here is long but intended to let others know to be careful about the code analysis suggestions.

The Retriangulate function originally had a line of code to access the top of
the stack,
  auto i = stack[top--];
The Microsoft Visual Studio code analysis tool complained "'auto' doesn't deduce references. A possibly unintended copy is being made} and suggested modifying to a reference "auto&" (or "auto const&}. Without thinking about the message, I changed the code to
  auto const& i = stack[top--];
which is an error, because now I have a reference to the stack[top+1] element. Later in the function,
  stack[++top] = { i[0], isplit };
  stack[++top] = { isplit, i[1] };
In the first line of this code, the value "top" is incremented first and then the pair is copied to the stack. The problem is that "i" is the pair to which the left-hand side of the assignment refers. The write of "i[0]" to this location overwrites itself (no problem), but the write of "isplit" to this location overwrites "i[1]" (the error). The second line of code reads "i[1]", which was inadventently modified to "isplit". I have been burned several times by the faulty suggestions of the code analyzer and learned now to think about them, replacing the "auto" keyword by the actual type or ignoring them. The same problem had occurred in the new CDT code (the second implementation in the header file), but during unit testing I had found and fixed the problem. I had not thought to go back to the old code to see whether it had the same problem. My solution was to replace
  auto const& i = stack[top--];
by
  std::array<size_t, 2> i = stack[top--];

All but the first mAccumulatedLength elements are uninitialized, which causes GetTotalLength() to fail. The Release-build unit tests did not fail (via NaturalSplineCurve) using Microsoft Visual Studio because the compiler initializes the elements to zero. The compiler then optimizes away the first line of code in GetTotalLength() because it believes mAccumulatedLength.back() will return zero the first time GetTotalLength() is called. This hides the bug when using MSVS. Other compilers will most likely leave mAccumulatedLength uninitialized, in which case the bug shows up.

The BSNumber constructors that take integer inputs need to compute the debug-supporting mValue first. The previous code modifies the inputs before computing mValue, which causes the sign to be positive when the inputs are negative. The
problem showed up only when GTE_BINARY_SCIENTIFIC_SHOW_DOUBLE was enabled for debugging and testing and does not affect the correctness of the actual BSNumber.

Added counting of maximum number of words for testing for sum of two squares and for (not yet published) Delaunay2 that computes the triangulation using a 3D convex hull for points (x,y,x^2+y^2).

The ray-sphere and segment-sphere queries were generating incorrect results when the linear component is tangent to the sphere. This occurred because result.parameter[1] is uninitialized in the line-sphere query for the tangent case, and the ray-sphere and segment-sphere code uses both result.parameter[] values for interval-interval intersection. The Result nested-class constructors now have all members initialized, and result.parameter[1] is set to result.parameter[0] in the tangent case. The same issues arise with ray-ellipsoid and segment-ellipsoid queries; they were fixed in the same manner.

Added counting of maximum number of words for testing for coplanar points. Added a comment with a formula for determining the number of bytes used by BSNumber<UIntegerFP32<N>>. The value is 4*(N+4).

In Hull3, the incoming hull has coplanar points. When inserting the next point, the hull becomes volumetric. The incoming hull triangles are inserted into the VET mesh, but the winding orders are reversed. The triangles generated after that have the correct winding order. Fixed the winding order.

Added counting of maximum number of words for testing for colinear points.

Added debug support for counting the maximum number of blocks of bits used in UIntegerFP32<N> during application execution. The class UIntegerAP32 already has this support.

I figured out why MinimumVolumeBox3D was broken. It turns out that the member function CreateCompactMesh has an implicit assumption that the vertices in the VETManifoldMesh::Vertex are ordered by the integer key. This assumption was satisifed when the vertex map was a std::map, but not when the vertex map was changed to a std::unordered_map. I restored the vertex map to be an unordered map and added code to the minimum-volume box to sort the vertices before creating the compact array of vertex adjacencies.

The sample GTE/Samples/Geometrics/MinimumVolumeBox3D was broken in that the displayed box no longer contained the convex polyhedron. I traced this back to GTE 5.4 where I replaced the std::set and std::map objects by std::unordered_set} and std::unordered_map objects. For a reason that I am unable to understand, the sample runs correctly when using std::map for VETManifoldMesh::VMap, but it does not run correctly when using std::unordered_map for VETManifoldMesh::VMap. The key type in either case is the native type int32_t. For now, I restored VMap to use std::map.

Modified the copyright notices to include 2021.

The ConvexHull3 performance was absolutely awful, requiring over 1 hour to compute the hull of a 120K-vertex dataset. I reimplemented this to use incremental insertion (single-threaded) and a divide-and-conquer algorithm (multithread). On an Intel i9-10900 CPU, the incremental insertion for the 120K-vertex dataset executes in approximately 4 seconds. The divide-and-conquer algorithm using 8 threads executes in approximately 1.7 seconds. Files that depend on ConvexHull3 were modified accordingly.

Added a new file for interval arithmetic. The implementation is software based and uses std::nextafter for determining the intervals. This avoids the floating-point hardware state changes when setting the rounding modes, and it avoids the problem with GCC that appears not to expose the ability to modify the floating-point environment.

Replaced "int V[3]" by "std::array<int, 3> V" in the ETManifoldMesh::Triangle class. A similar change had been made already to ETManifoldMesh::Edge.

The DX11Engine constructors that have a window handle input are designed for rendering to the window. These constructors create default render states that GTE wants, and these states are not all the default DX11 render states. The DX11Engine constructors that do not have a window handle input are designed for windowless applications using compute shaders. These constructors do not create default render states for GTE, so the default states are those of DX11. To support a windowless application that renders to an offscreen render target, and to allow that code to work whether windowed or windowless, I added creation of the default GTE render states to the compute-intended DX11Engine constructors. I also removed calls to DestroyDefaultObjects in the constructors because at the time of call, all the objects do not exist.

Eliminated the annoying MSVS 2019 warning about DFType being an unscoped "enum", suggesting that "enum class" is better. These are used as indices into arrays, so "enum class" does not work. I replaced the enumeration by a list of constexpr values. The type DFType is defined to be uint32_t.

Updated projects, makelists and release notes.

An algorithm to rasterize a collection of tetrahedra into a 3D grid.

Modified to include new queries.

Replaced the one remaining std::set object by a std::unordered_set object.

While porting Delaunay2 from GTE to GTL, the more robust GTL unit tests for the ToCircumcircle function failed for nearly cocircular points (the GTE unit tests did not have a case for nearly cocircular points). Fixed the bugs in the GTE code.

Added interfaces to allow passing a raw pointer to vertices and the number of vertices.

Incremented the GTE_MINOR_VERSION to 4.

Added a function to compute the maximum number of words for computing the pseudosquared distance function in TriangulateCDT using BSNumber<UIntegerFP32<N>>.

Classes affected by the manifold mesh and Delaunay modifications.

Commented out the [[deprecated("...")]] tag to avoid build failures when "Treat warnings as errors" is selected.

Added new classes that do not require the user to specify the computing type. The old classes are now tagged as deprecated and will be removed in a later version of GTE.

Added a new file to create hash functions in order to use std::unordered_set and std::unordered_map in GTE code, replacing std::set and std::map when a performance increase is desired.

Factored IntervalProductUp and IntervalProductDown from ConvexHull3.h to ProductLowerBound and ProductUpperBound in FPInterval.h so that the code can be shared by other computational geometry queries involving interval arithmetic.

Added a new member function CopyFrom that does a direct copy from UIntegerFP32<N> to UIntegerFP32<M> as long as N is no larger than M. This allows converting floating-point inputs to UIntegerFP32<N> for N-value 2 or 4. These can then be copied on-demand into a pool of UIntegerFP32<M> for much larger M that is used to represent an expression tree that must be computed with exact arithmetic. The goal is to reduce heap memory usage when computing with arbitrary-precision arithmetic. The pool can be allocated on the heap to avoid having to greatly increase the program stack size when M is large.

Fixed a bug that was introduced when performance optimizations were added to the file. The original code had allocated vectors for mB, mC and mD. The optimized code packed these into a single chunk of memory, but the aforementioned variables which became pointers were not set to point to the proper locations in that chunk. This was only for the clamped-spline case.

Added/updated comments about how large N must be to use ComputeType of BSNumber<UIntegerFP32<N>>. The performance is much better when you use UIntegerFP32<N> rather than UIntegerAP32 because the latter leads to significant heap management costs.

When using ComputeType that is a floating-point type, rounding errors can cause sign misclassifications in the loop over linkEdges and prevent ProcessTriangleStrip and ProcessCoincidentEdge from being called. The consequence is that partition is an empty std::vector and the call to partition.back() causes a crash. I added a LogAssert call to throw an exception in this case. It is strongly recommended to use an arbitrary-precision type for ComputeType. Alternatively, use a try-catch block to triangulate using a floating-point type and, if an exception is thrown, repeat the call using an arbitrary-precision type. I also replaced the nondescriptive "Unexpected condition" in the LogAssert statements with function calls that return strings with more description.

Added more members and queries to PolygonTreeEx. Previously, the insideTriangles vector stored all triangle in the polygon tree. For TriangulateCDT to be consistent with TriangulateEC, it is convenient to partition these into interiorTriangles, which are those triangles bounded by an outer polygon and its child inner polygons, and exteriorTriangles, which are those triangles bounded by an inner polygon and its child outer polygons. The point-containment query of TriangulateEC searches only the interior triangles. In fact, that class does not construct exterior triangles. I added point-containment queries for each type of vector member of PolygonTreeEx, including comments about typical usage. You can create your own queries, especially if you want to use multithreading. Also, it is sometimes convenient to know which node of the polygon tree stores the containing triangle. The node index information has also been added to PolygonTreeEx for the various triangle vector members, and a couple of the point-containment queries use these.