-
Notifications
You must be signed in to change notification settings - Fork 188
Home
Qhull 2019.1 2019/06/21 (7.3.2) is available on github and www.qhull.org
-
git clone git@github.com:qhull/qhull.git
-
git checkout 2019.1 # git checkout v7.3.2
Qhull 2019.1 contains bug fixes and improvements to logging, error reporting, and merging.
-
Fixed fifty bugs, including initialization bugs and memory corruption bugs in qh_readpoints and qh_option.
-
For programmers using qh_findbestfacet to locate a Delaunay triangulation, qh_findbestfacet may return an adjacent triangle [F. Drielsma].
-
Qhull compiles as 32-bit or 64-bit code. As 64-bit code, Qhull's 4-D data structures increase by 50% and reduce the effectiveness of cache memory. This will slow down Qhull for large data sets.
-
New option 'TAn' stops Qhull after adding n points.
-
New option 'Tf' flushes qh_fprintf for debugging segfaults.
-
New options '--help', '-?', or '--' display a short help message. Under Git for Windows or MSYS2, 'qhull' waits for stdin.
-
Option 'TP-1' turns on tracing after qh_buildhull and qh_postmerge. It traces qh_check_maxout, qh_prepare_output, qh_triangulate, and qh_voronoi_center
-
Options 'TI' and 'TO' do not require a space before the filename. traces qh_check_maxout, qh_prepare_output, qh_triangulate, and qh_voronoi_center
-
An unknown Qhull option is an error. It was a warning. Override with option 'Qw'.
-
Short or long input to Qhull is an error. It was a warning. Override with option 'Qa'.
-
Documentation encourages the use of joggled input. Joggled input is less precise than facet merging, but it cannot incur merge errors for highly degenerate input.
-
Documentation refers to 'dupridge' instead of 'duplicate ridge'. A dupridge is an erroneous ridge between four or more facets.
-
CMake exports QhullTargets for config.cmake.in and find_package [tamasmeszaros]
-
The C++ interface, QhullFacet and QhullVertex, includes new methods hasNext() and hasPrevious().
-
Test scripts qtest.sh and q_benchmark help with logging and optimizing Qhull, particularly for intermittent errors and bad cases for Qhull.
Please convert to reentrant Qhull (libqhull_r) if you use libqhull_p or qh_QHpointer. A new shell script, eg/make-qhull_qh.sh, recreates libqhull code from libqhull_r code. A directory-diff is a test that the conversion was correct.
An experimental option, 'Q14', merges pinched vertices. Pinched vertices are nearly adjacent vertices (ca. 1.0E-13 apart on the unit cube). They are far enough apart to avoid geometric errors, but not far enough apart to avoid topological errors. An example of a topological error is four facets that share the same ridge; a ridge should only have two neighboring facets. Qhull 2015.2 merges facets to repair these errors, but it may fail, especially for multiple pinched vertices.
The N_PINCHED section of q_benchmark
tests pinched vertices with option 'Q14'.
Qhull continues to report errors for difficult cases. Some of these inputs always fail with Qhull 2015.2.
However, other inputs almost always succeed with Qhull 2015.2. It addition, normal inputs for
Qhull 2019.1 with 'Q14' are somewhat slower than for Qhull 2015.2.
The q_benchmark tests of N_PINCHED reveal the interaction between geometric precision errors and topological errors. In Euclidean space with precise arithmetic, the mathematics of convex hulls prevent topological errors. With imprecision, topological errors become possible. Qhull handles precision and topological errors with facet and vertex merging. With repeated merges, precision errors and topological errors eventually become too severe and prevent further processing. For a further discussion of known issues see Limitations of merged facets.
These problems are unlikely to occur in practise. Most of the troublesome inputs consist of many points approximately 1.0e-13 (scaled to the unit cube) from either nearby points or hyperplanes. Such inputs lead to many merges that eventually fail. Points substantially closer or further apart are OK. A future version of Qhull will include per-vertex joggle. Per-vertex joggle can prevent precision errors, just like Qhull's joggle option 'QJ'.
Qhull 2015.2 fixes memory leaks reported by Marcos Sandim, the Cmake build reported by Niclas Rosenvik, and the DevStudio 2012 build. It fixes the return type of QhullLinkedList::last() and back(), and includes as requested by Ben Boeckel.
Qhull 2015.1 is the first release of Qhull's reentrant library, libqhull_r. If you call Qhull from a program, you should use libqhull_r instead of libqhull or libqhullp. The C++ interface uses libqhull_r.
libqhull_r does not use global variables. Instead, a qhT pointer is the first argument to each procedure. This approach was pioneered by Pete Klosterman in 2010.
Qhull 2015.1 fixes error QH6228 "all neighbors ... are flipped or upper Delaunay". This error occurred rarely with nine reports. J. Metz provided input that triggered this error.
Qhull 2015.1 includes rbox option 'Cn,r,m' to generate nearly coincident points. This is a newly understood, bad case for Qhull. It will be fixed in a later version of Qhull by merging facets before adding a new point. A bounding box for Delaunay triangulations and Voronoi diagrams may alleviate the problem. For more information, see "Nearly coincident points on an edge" in Nearly coincident points on an edge.
Version 2015.0.7 cleans up Qhull's collection classes and iterators, with thanks to Filip Jares for reporting these problems.
Version 2015.0.6 makes it easier to remove references to exit(), stderr, and stdout from libqhull, libqhull_r, and libqhullcpp. By redefining usermem_r.c, all references are removed except for two instances of stderr (to initialize a null FILE* parameter) [D. Sterratt].
Version 2015.0.1 increased the maximum vertex ID and ridge ID from 16M to 4G [H. Strandenes, C. Cantwell]
Comments, errors, suggestions are welcome.
--Brad