For the "smooth rounded rectangle" example at the end of the article, what's to stop it from getting closer-and-closer to an answer, but never actually getting there?
I'm talking about idealized mathematical objects, of course. I realize that in real-world computing there's no point continuing beyond some practical precision threshold.
Termination conditions for GJK are hard, and caused a lot of trouble. Search for "GJK algorithm" and "termination". There are several academic papers, and discussions in the game dev community.
GJK works on convex polyhedra. The "convex" requirement is strict. For example, a cube with tesselated faces is not convex. The two triangles that make up the face of a cube are co-planar, and the edge between them has a zero break angle. This messes up GJK. It's necessary to be able to handle flat polygon faces, not just triangles. That creates a new problem. Polygons are not perfectly flat due to round-off error in floating point. What works is computing a convex hull with a minimum break angle of about 1 degree. That creates geometry GJK can process.
GJK is an example of an algorithm for which there is considerable distance between the naive algorithm that mostly works and the production-quality version that works reliably. Some other algorithms like that include:
- JPEG 2000 decoding. The open source reference implementation is slow and somewhat buggy. There is proprietary code that is faster and works reliably, but it is rather expensive. This is partly why JPEG 2000 never really caught on, outside of medical imagery.
- Mesh simplification. There are two common open source approaches - local triangle merging and quadric mesh simplification. Both can create a big mess if pushed too hard. The metric you really want is that the reduced mesh should look roughly the same as the original when seen from a distance at any angle. Neither of those approaches achieve that. The open source code in Blender works, but the results are disappointing for many cases. Simplygon and Unreal Engine have better approaches, but are proprietary.
- Convex hull decomposition. Given a non-convex mesh, produce a set of disjoint convex meshes which add up to the original. This is a preprocessing step before you can use GJK. Most algorithms for this produce terrible-looking decompositions, with long, skinny triangles. There's something called approximate convex hull decomposition, which relaxes the "disjoint" requirement, allowing some overlap. This results in much simpler sets of convex meshes. There's
open source code for this, but it crashes if the input geometry is not absolutely correct, and sometimes when it is.
- Constructive solid geometry. Create a cylinder. Create a thread form. Extrude the thread form along a spiral. Subtract that from the cylinder to get a screw. Chamfer the end. Autodesk Inventor has been able to do that since about 2014, which is what you get for the big bucks. There's some open source code, but historically it hasn't handled the hard cases well. This matters when the next step is cutting the part out of metal.
- Layered clothing for game characters. Create a game character. Set them into an A-pose (arms out, legs apart).
Put a rigged mesh shirt on them as a rigged mesh. Resize so that the shirt fits and the body doesn't poke through. Add a coat created by someone else than the one who created the shirt. Resize so the coat fits and the shirt doesn't poke through. Now observe that if the character moves out of A-pose, you probably get some peek-through at shoulders and elbows. Automatically adjust the mesh rigging to fix that. Clo and Marvelous Designer have non-real-time solutions to this, and Roblox has a real-time solution. There's no known open source solution.
Each of these problems is good for years of thesis-level hard work.
> - Constructive solid geometry. Create a cylinder. Create a thread form. Extrude the thread form along a spiral. Subtract that from the cylinder to get a screw. Chamfer the end. Autodesk Inventor has been able to do that since about 2014, which is what you get for the big bucks. There's some open source code, but historically it hasn't handled the hard cases well. This matters when the next step is cutting the part out of metal.
In freecad I didn't encounter any issue doing just that. Of course we are 10y later, so maybe things have improved.
I made quite elaborate custom threads for 3D printing this way.
Computational Geometry has a technique for avoiding all of the complex cases where point are colinear, coplanar, cocircular, etc.. I’ve forgotten the techniques’ name, but coordinates are integers plus an epsilon term. As the epsilon goes to zero, you get the original statement of the problem.
The epsilon terms are used for breaking ties. If you are deciding if a point is to the right or left of a line, you can use the factors on epsilon terms to decide. If the limit of the point for epsilon close to but greater than 0 is right or left, you use that answer.
You can use multiple epsilon terms, one for each dimension and claim that the x-dimension approaches zero faster than the y or z-dimension, etc. It makes it all work as integer linear algebra with simple greater than or less than on scalar result.
For mesh simplification, what about https://github.com/wjakob/instant-meshes ?
I know it does the thing you required, but it doesn't really do variable density (you could tell it what areas need what density and it would do that; the paper has a demonstration of this).
For the "smooth rounded rectangle" example at the end of the article, what's to stop it from getting closer-and-closer to an answer, but never actually getting there?
I'm talking about idealized mathematical objects, of course. I realize that in real-world computing there's no point continuing beyond some practical precision threshold.