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.

The ConstrainedDelaunay2 class had two bugs that needed to be fixed. The first bug was incorrect handling of adjacent triangles during retriangulation of the triangle strips containing the constrained edges. This problem shows up when the triangle strip snakes around and has a shared edge with another triangle that is not its immediate predecessor in the strip. The second bug was an incorrect computation of the pseudosquared distance function. This problem shows up when locating the closest vertex of a boundary polygon to the base polygon edge. In particular, the bug was exercised when the projections of the candidate vertices to the base edge of the polygon contained at least one projection on the segment and one projection outside the segment.

This code is approximately 13 years old and was complicated to read and debug. It discarded the mGraph member from the Delaunay triangulation and instead used the compact arrays mIndices and mAdjacencies. I rewrote ConstrainedDelaunay2 to continue using the mGraph member, in the process simplifying the implementation to be readable. Many comments were added, but I plan on adding a PDF to the website describing the pitfalls of the retriangulation and how to avoid them. The original code was based on an online research paper that discussed the simplest retriangulation configuration, but had no discussion about the pitfall cases. The various file changes are described next.

GTE/GTMathematics/ConstrainedDelaunay2.h: Reimplemented ConstrainedDelaunay2 according to the aforementioned comments.

GTE/GTMathematics/Delaunay2.h: Factored out some code into a new function UpdateIndicesAdjacencies. This code occurred after the Delaunay triangulation to synchronize the information in mGraph with the compact arrays mIndices and mAdjacencies. To support ConstrainedDelaunay2, the factored function can be called after a user-determined set of edges have been inserted one at a time.

GTE/GTMathematics/ETManifoldMesh.h: Added two helper functions to ETManifoldMesh::Triangle, namely, GetAdjacentOfEdge and GetOppositeVertexOfEdge. I will continue to encapsulate commmon operations and add them to ETManifoldMesh. These operations tend to occur as in-application code, but that code should be shared.

GTE/GTMathematics/TriangulateCDT.h: The modifications to ConstrainedDelaunay2 required a small modification to the polygon triangulation that uses constrained Delaunay triangulation. The code copies the Delaunay mGraph object to the local graph object.

GTE/Samples/Geometrics/ConstrainedDelaunay2D/ConstrainedDelaunay2DWindow2.cpp: The insertions are not batched; rather, they are executed one at a time based on key strokes. The application now needs to call UpdateIndicesAdjacencies after each edge insertion.

I redesigned and rewrote TriangulateCDT to support shared vertices, coincident vertex-edge configurations and coincident edge-edge configurations. These configurations are not supported by TriangulateEC. To avoid repackaging polygon trees in an application using both classes, I factored out the nested Tree classes into a new class PolygonTree. Objects of this class are inputs to the triangulators, and they are not modified internally. I also created a new class PolygonTreeEx that currently represents the output of TriangulateCDT. Eventually, this class will become an input-output parameter for both triangulators. Note that TriangulateCDT does not support polygon trees where two edges intersect at an edge-interior point of both edges and that intersection point is not in the input points to the triangulator. The problem is that the constrained Delaunay triangulation works correctly when the constrained edges do not intersect other than at shared-vertex endpoints. If one were to insert two edges into the Delaunay triangulation that have an edge-interior intersection, each edge interferes with the local re-triangulation of the other edge. I plan on adding support for such edges, but the task is of significant size and will take some time.

Added to the nested class Triangle a function that tests whether a directed edge in mesh is in the same direction as an undirected triangle edge or in the opposite direction (or not a triangle edge at all). This is a common query that is now encapsulated.

Swap chain creation in DX11 now has flip flags that are recommended. The DX11Engine still uses the old flags. Apparently, the internal changes to DX11 for the flip flags sometimes causes creation of a second ID3D11Context during a swap-chain Present call in order to create an ID3D11RenderTargetView and related objects. The DXGI debug layer indicates that the back buffer is unbound from the pipeline, which is not what I thought was happening with the old swap-chain creation flags. The second context appears to be created to patch the problem. However, the time of its destruction is nondeterministic. In some cases, the destruction occurs before the GTE application mDevice is destroyed, and the FinalRelease(mDevice) is successful. In other cases, the destruction occurs after the final release of mDevice, but an exception is thrown (by the GTE code) indicating the reference count for mDevice is positive. Finally, in many cases, the second context is never created. Until I understand why this behavior occurs, I have replaced the DX11::FinalRelease calls in DX11Engine::DestroyDevice with DX11::SafeRelease calls, the latter not tracking the reference counts and not throwing exceptions.

I also updated the Gte5UpdateHistory.pdf and GteFullUpdateHistory.pdf that ship with the zip file I post to my website.

Allow user to set the normalized z coordinate used by TextEffect.

The modifications allow versions of CMake before 3.12 to compile the code.

Added comments that Sylvester's criterion is used to test for positive definiteness. The loop on halving the root was limited to 8 iterations, but the number has been increased to allow rational arithmetic for which an unlimited loop could be infinite. The new limit is 2048, which will not be reached for floating-point types float and double. The ApprEllipse2 code had a redundant test for the determinant of the entire matrix, but it has now been removed.

The old code ApprEllipse2 and ApprEllipsoid3 for fitting points with ellipses and ellipsoids were based on a nonlinear least-squares error function that was a sum of distances from points to the objects. The comments in those files described eigendecompositions of the M matrices but were in error, and the code did not correctly implement the mathematics. Moreover, ApprEllipsoid3 failed to initialize angle[2] before running the minimizer. The rewritten code uses a minimizer involving a 2-step gradient descent algorithm. Unit tests and end-to-end tests were added to the internal test suite to verify the algorithm and results.

I upgraded my Ubuntu machine to use 20.04.1 LTS. Visual Studio Code and CMake are now used on Ubuntu/Fedora for code maintenance.

Added support to the Linux distribution for CMake executed from a command line and for Visual Studio Code. Please read the installation and release notes on how to build the libraries and samples on Linux.

The shared-library executables in the Linux distribution were crashing on exit from  the main program. Using gdb and the core dump, the problem appeared to be in the destruction of global objects in the gtapplications shared library. The singleton TheWindowSystem was actually created 3 times because of the way shared libraries are linked and loaded. I had added -rdynamic to the makesample.gte link line (suggested by a poster at stackoverflow). This eliminated the multiple creations of TheWindowSystem. Unfortunately, on-exit crashes still occurred, this time in the destruction of global objects in the gtgraphics shared library. The only global objects are several class-static members. To diagnose with a visual debugger, I decided to add Visual Studio Code support. With this environment, the on-exit crashes no longer
occur. The CMake output files are cryptic, and I am not skilled enough to figure out what differences occur between CMake and my makefiles regarding linking and loading of shared libraries. Visual Studio Code and CMake work fine, so I am abandoning my simple Unix makefile approach.

I moved the GTE/Mathematics/GPU folder to GTE/MathematicsGPU to support the new CMake and Visual Studio Code project organization on Linux. All the associated project source files had to be modified so the header includes access the new location. Some application files had to be modified.

When building all configurations of the libraries and samples, g++ complained about potentially uninitialized variables in several files. None of these were a problem, but I initialized them anyway to avoid the warnings.

The find-intersection query for moving spheres and oriented boxes calls the base-class protected query for moving spheres and aligned boxes. That call requires the center point to be in the first octant and makes adjustments accordingly. The find-intersection for the oriented boxes did not make this adjustment. I moved the transforming of the center point into the base-class query to fix the problem. The visual test harness for this code is the sample application MovingSpheresBoxes, where I apparently never moved the sphere into a position that exercised the bug.

Deprecated the class UniqueVerticesTriangles. Added a replacement, UniqueVerticesSimplices that works in any dimension 2 or larger. The class has been used for removing duplicated and unused vertices from triangle meshes and for generating meshes from a vertex-only based representation to one using an indexed representation. The generalized code applies to dimension 2 and will be used for computational geometry algorithms involving polygons (Boolean operations on polygons, for example). The deprecation is in the C++ 14 sense: the class is tagged with [[deprecated]]. It will be removed sometime in the near future.

Removed the compiler define for GTE_THROW_ON_UINTEGERFP32_OUT_OF_RANGE and exposed the one line of code controlled by it in \Code{SetNumBits}. An exception needs to be thrown if the bit request exceeds the number of bits provided by the class so that a caller can trap this with a try-catch block.

The BSPPolygon2::Finalize function passed *this as a non-const parameter and this->mEArray as a const parameter to the BSPTree2 constructor, which should have been a clue that the BSP implementation is badly done. A test data set was included in a bug report, and it led to an infinite loop in the BSPTree2 code because mEArray was modified via the *this object. A copy of mEArray is now passed as the second parameter of the BSPTree2 constructor.

The constructor also has a switch statement that classifies the intersection type of two edges. In the cases TRANSVERSE_POSITIVE and TRANSVERSE_NEGATIVE, it is possible that floating-point rounding error can cause the intersection point to be one of the segment endpoints. This must be trapped and handled separately. Before the change, the test data set triggered an assertion in SplitEdge for the user reporting the problem. I was unable to reproduces this, but compiled expressions using floating-point arithmetic can lead to different low-level code depending on the compiler, and the rounding behavior can vary. This is not just a matter of the low-level expression tree of operations, it can also be a matter of what precision registers are used and whether downcasts occur from a high-precision register (say, 80-bit) to a low-precision register

This is the initial repository for Geometric Tools Engine 5.0.