Up: http://www.qhull.org
To:: Bug and Notes and Qhull Users
Dn: FAQ about Qhull


[RANDOM] Qhull News, Bugs, and Users

Highlights   ::   Known Problems   ::   Bugs and Notes   ::   Qhull Users
Change History   ::   Readme   ::   Functions

Qhull 2020.2 is available for download (2020/08/31, 8.0.2, README, Changes).

Qhull 2020.2 2020/08/31 (8.0.2) updates Qhull's builds and Qhull's C++ interface.

Qhull's builds produce a shared library, libqhull_r.so (qhull_r.dll), several static libraries, and several applications using these libraries. They do not produce deprecated libraries: libqhull.so, qhull.dll, libqhull_p.so, and qhull_p.dll. Users of these libraries should convert their code to reentrant Qhull (libqhull_r.so) or link to libqhullstatic.a.

Qhull's Java-style iterators use a copy constructor to avoid subtle errors due to memory management. Its C++ interface is compatible with C++98.

Other changes for Qhull 2020.2:

You may call Qhull from your program (Qhull Code). Qhull includes a C interface, a C++ interface, demonstration programs, and test programs. Start with small examples that you work out by hand. Compare your program with the results from Qhull. Understand the data structures and precision issues.

Programs and libraries that use Qhull should upgrade to Qhull 2020.2. The reentrant library, libqhull_r, was introduced in Qhull 2015.1. It replaces the qh_QHpointer library, libqhull_p, and the non-reentrant library, libqhull. The qh_QHpointer library, libqhull_p, should not be used. The static, non-reentrant library, libqhullstatic.a, remains useful for Qhull applications that do not include user code.

Multiple threads may use the reentrant library, libqhull_r, at the same time. Each instance of Qhull is a separate run. The first argument for most Qhull procedures is a pointer to the qhT data structure. This approach was pioneered by Peter Klosterman in 2010. To verify the changes required, a shell script, eg/make-qhull_qh.sh, recreates libqhull code from libqhull_r code. A directory-diff checks that the conversion was correct.

The C++ interface is based on the reentrant library. It includes QhullUser and RboxPoints classes. Output produced by 'qhull' can be transferred to QhullUser. Most of the output produced by 'rbox' is transferred to RboxPoints.

Comments, errors, suggestions are welcome (bradb@qhull.org).

This site also hosts pages on C++ and Perl Guidelines for advice on writing programs, Road bash for a portable bash shell for Unix, Mac, Windows XP or Windows 8, Road Intranet for (out-of-date) advice on Windows, Perforce, etc, and ttcnf for truth table CNF. Visit thid.io for a thesaurus of research literature and namec for programming with arbitrary names.

Copyright © 1995-2020 C.B. Barber

» Known problems

All users

Qhull uses pointer-intensive data structures. As a result, 64-bit builds of Qhull use more memory than 32-bit builds. If the data structures do not fit into cache memory, processing speed is reduced. If practical, use 32-bit builds of Qhull. If 64-bit builds are required, monitor the processing time per point with option TFn. If processing time increases dramatically, you may be running out of high-speed memory. A future version of Qhull will improve 64-bit memory and performamce.

In 3-d and higher Delaunay Triangulations or 4-d and higher convex hulls, multiple, nearly coincident points may lead to very wide facets. For points in the unit cube, it occurs when many points are approximately 1e-13 apart. Closer points or further apart points are OK. The problem has existed since the beginning of Qhull. Qhull 2019.1 introduces an experimental option Q14 to address this issue. It merges vertices that create topological errors. While it repairs some problems, it demonstrates the limitations of facet merging. For more information, see "Nearly coincident points within 1e-13" in Limitations of merged facets. A future version of Qhull will add per-vertex joggle to avoid topological errors.

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 prevents 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. An error is reported.

In 3-d and higher, option 'Qt' does not produce conforming triangulations for adjacent, non-simplicial facets. For example, if you have a regular, 3-d array of input sites, their Delaunay triangulation consists of cubes. Option 'Qt' will triangulate each cube into tetrahedra. Within each cube, the triangulation is consistent, but it is not necessarily consistent between adjacent cubes [C. Bertoglio; C. de Visser]. How to fix this problem is unknown.

Users of 'qhull d' and 'qhull v' should use 'qhull d Qbb' and 'qhull v Qbb' respectively. Option 'Qbb' is automatically set for 'qdelaunay', 'qvoronoi', and 'QJ'. It improves precision by scaling the paraboloid.

All programmers

qh_findbestfacet [poly2_r.c] returns the facet with the largest signed distance to a given point. For Delaunay triangulations, this facet is usually, but not always, the facet containing the point. See this test of qh_findbestfacet by F. Drielsma. For green points, the "best" facet is the lower-left "green" triangle. However, along the upper-right edge, the green points are in the upper-right "yellow" triangle. Qhull computes a Delaunay triangulation via the convex hull of a paraboloid one dimension higher. Vertices of the convex hull correspond tp input sites of the Delaunay triangulation.

For triangulated non-simplicial facets, qh_findbestfacet returns one of several tricoplanar facets. These facets share the same hyperplane as the original non-simplical facet. For Delaunay triangulations, the facet containing the point may be any of the tricoplanar facets or their neighbors.

Both problems may be resolved by testing the returned facet and its neighbors for containment (see, Mucke, et.al. 1996).

qh_detvnorm [io_r.c] implements Voronoi options 'Fi' and 'Fo' for separating hyperplanes. An error is not reported if a hyperplane is degenerate (e.g., 'rbox c P0 D2 | qhull v Fo'). Option 'Tv' collects statistics to verify 'Fi'.

  • See Bug and Notes for problems in previous Qhull versions.

    » Highlights

    [Apr 2018] G. Heinzel designed a "frequency plan", a part of the operational schedule, for the planned gravitational detector space mission LISA. He ran millions of tests whether or not a 4D point lies within the Minkowski sum of a 4D cuboid and another 5D cuboid linearly distorted into 4D space. See Wikipedia on Convex hulls of Minkowski sums.

    [Jan 2016] R. Gonzalez released PARAVT: Parallel Voronoi Tessellation code (code) for large, astrophysics data sets. This is the first package built on reentrant Qhull.

    [Nov 2014] Peterka, Morozov and Phillips used their DIY data-parallel programming library for high-performance computation of large-scale, 3D Voronoi and Delaunay tesselations. Their code uses either CGAL or Qhull. CGAL was substantially more compact and faster. CGAL generates 3D-specific code, while Qhull is general dimensional. For 64-bit code, Qhull's data structures nearly double in size and reduce the effectiveness of cache memory. A future version of Qhull will provide bulk addition of input sites and optimizations for 64-bit code.

    [Sep 2014] 3scan uses Qhull for volumetric reconstruction and segmentation of microscopy images. They commercialized the "Knife-Edge Scanning Microscope" first developed at Texas A&M�s Brain Networks Laboratory.

    [July 2014] Toronto and McCarthy published Practically accurate floating-point math in Computing in Science & Engineering. They show how to rewrite a computation to avoid the "badlands". It would improve Qhull's computations, particularly qh_setfacetplane. From the abstract "With the right tools, floating-point code can be debugged like any other code, drastically improving its accuracy and reliability."

    [Mar 2014] D. Gregorius gave a tutorial on QhullHull at the 2014 Game Developers Conference. It describes the QuickHull algorithm used in Qhull and facet merging to handle precision errors.

    [Jan 2014] I. Thomas added Qhull to matplotlib, an open-source python plotting library. It will appear in 1.4.0 onwards.

    [Jun 2013] Miller, Sheehy, and Velingker published a paper on well-space points and approximate delaunay graphs. It builds on work of Shewchuk, Hang, and Alliez et al. and may suitable for implementation in Qhull [Miller et al, Symp. on Computational Geometry, 2013].

    [Mar 2013] D. Gregorius gave a talk on the separating access test (SAT) at the Game Developers Conference. SAT in combination with Qhull build a powerful tool for collision detection in computer games.

    [Feb 2013] M. Lysenko created a JavaScript port of Qhull using Emscripten (https://github.com/mikolalysenko/qhull-js.

    [Nov 2012] S.P. Ong wrote pyhull, a Python wrapper for Qhull.

    [Nov 2012] J. Milutinovich translated the Qhull home page into Serbo-Croatian.

    [Nov 2011] Grasman, Gramacy, and Sterratt added Qhull in R via their geometry package.

    [April 2010] V. Le Guilloux, Schmidtke, and Tuffery based fpocket on Qhull's qvornoi. It is a very fast, open source, protein pocket (cavity) detection algorithm ["Fpocket: An open source platform for ligand pocket detection", www.biomedcentral.com, 2009].

    [May 2009] R. Cervellione added Qhull to GC. GC generates minimal surfaces.

    [Jan 2009] F. Lee uses Voronoi diagrams to cluster data. He figured out a problem with missing hyperplanes generated by 'qvoronoi Fi Fo'. His data was nearly cospherical leading to merged facets. See option 'Fv' for further discussion.

    [Feb 2008] Finnigan wrote Python programs for constructing 3-d models of Voronoi diagrams computed by Qhull (zoetrope/voronoi3d)

    [Nov 2007] Zolotykh wrote Skeleton. It generates all extreme rays of a polyhedral cone using the Double Description Method. It supports float, integer, and arbitrary precision arithmetic.

    [Dec 2006] Geomview may be used on Windows. It provides a good visualization of Qhull's results. Geomview does not handle CRLF line endings, so pipe qhull's output through Cygwin's dos2unix. You will need to compile Geomview under Cygwin. For detailed instructions, see Building Savi and Geomview under Windows. To run Geomview, launch X11 with startx and /usr/X11R6/bin in your PATH. Then run ./geomview [L. Wood]

    [Nov 2006] xCellerator is an extensible Mathematica package for signal transduction modeling. Their mPower package includes Mathematica interfaces to qconvex, qdelaunay, and qvoronoi.

    [Nov 2006] See Blender for open source 3D modeling, animation, rendering, post-production, interactive creation and playback. Qhull is part of their game engine.

    [August 2006] Ruebenko wrote QHullInterface, for using Qhull with Mathematica. It is part of his IMTEK Mathematica Supplement.

    [March 2006] Engwirda wrote mesh2d for unstructured mesh generation in MATLAB. It is based on the iterative method of Persson and generally results in better quality meshes than delaunay refinement.

    [September 2005] Hang Si wrote TetGen, a quality tetrahedral mesh generator and Delaunay triangulator, and TetView, a tetrahedral mesh and piecewise linear complex viewer. TetGen produces constrained 3-d Delaunay triangulations using Shewchuk's precise geometric predicates.

    [March 2005] Ratcliff released QullLib 1.0 in Sept 2004. It is a Qhull library with a clean C++ interface for computing convex hulls. It was the basis for Qhull's RboxPoints.cpp.

    [Feb 2005] A useful addition to Qhull would be computing the volumes of Voronoi regions. For an algorithm, see Max, N., "Computer assisted sphere packing in higher dimensions," Proc. 2nd Conf. Visualization '91, p. 102-108, IEEE, 1991. For an implementation, see Clarkson's hull program. [A. Wouterse].

    [2005] Li and Snoeyink compared five implementations of 3D Delaunay tessellations on data with six digits of precision. Qhull used four times as much memory as CGAL and three times as much memory as Shewchuk's pyramid code. It ran substantially slower than these codes. Qhull's data structures are general dimension, while CGAL and pyramid data structures are 3D. As 64-bit code, Qhull's data structures nearly double in size and reduce the effectiveness of cache memory.

    [Nov 2004] Bruynooghe integrated Qhull with Python and is using Qhull for mesh generation. See his Delny Python package [home page].

    [Fall 2004] J.E. Lloyd implemented the QuickHull3D in Java. As done in Qhull, he used facet merging to handle precision problems. D. Gregorius gave a tutorial on QhullHull at the 2014 Game Developers Conference. K. Johnston used QhullHull3D.java for VariableStarAnalysis (April 2019).

    [July 2004] Mathworks released MATLAB R14 with Qhull 2002.1 and triangulated output. Triangulated output is significantly more accurate than MATLAB's prior use of joggled input. MATLAB uses Qhull for Delaunay triangulations, Voronoi diagrams, and convex hulls. [P. Anderson]

    [Feb 2004] GNU Octave [Geometry] upgraded to Qhull 2003.1 with triangulated input. Octave uses Qhull for Delaunay triangulations, Voronoi diagrams, and convex hulls. [R. Laboissiere].

    [Feb 2003] MATLAB implements tsearch by building the Delaunay triangulation and searching for the best facet of each test point. It should be faster to add the test sites at Qhull initialization and process them like coplanar points, but without searching nearly coplanar facets until the end. As with findDelaunay(), tricoplanar regions will need special processing. A later version of Qhull may implement tsearch.

    [May 2001] Sugihara's "Robust geometric computation based on topological consistency" [ICCS 2001, LNCS 2072:12-26] is a good review of his topological approach to computational geometry. Qhull likewise produces topologically consistent structures. Qhull adds a geometric test of convexity that applies to imprecise data. Under certain assumptions, Qhull bounds the maximum geometric error. In practice, Qhull's maximum error is a small multiple of the minimum, maximum error.

    [April 2001] For Qhull library users. The BGL Boost Graph Library [aka GGCL] provides C++ classes for graph data structures and algorithms [Dr. Dobb's 9/00 p. 29-38; OOPSLA '99 p. 399-414]. It is modelled after the Standard Template Library. It would provide a good interface to Qhull. If you are interested in adapting BGL to Qhull, please contact bradb@qhull.org.

    [2001] The Crust, Cocone, PowerCrust, and natural neighbor algorithms of Amenta, Bern, Boissonant, Cazals, Choi, Dey, Kolluri, and Leekha, use Voronoi diagrams to reconstruct surfaces from sampled points. They can guarantee that the output surface is geometrically close to the sampled surface. For a recent paper, see [Dey & Giesen, Symp. on Computational Geometry, 2001, p. 257-263]. For an implementation using Qhull, see Kumar's Reviver: A Practical Provable Surface Reconstructor and his Reviver home page. Reviver uses joggled input with follow-on processing in exact arithmetic. Triangulated output may avoid the need for exact arithmetic.

    [April 2000] Several Qhull users use the Visualization Toolkit (VTK) to visualize their results. It should be straightforward to rewrite the Geomview visualizations for VTK. If you use VTK with Qhull, please send how-to instructions and code to bradb@qhull.org.

    [July 1999] Comes and Ziegelmann published "An easy to use implementation of linear perturbations within CGAL", [WAE'99, LNCS 1668:169-182, 1999]. They eliminate degerneracy with a random perturbation of the input. This is similar to Qhull's joggled input. While Qhull's perturbation is random coordinates within a cube, their perturbation is random directions of fixed amplitude.

    [1999] Devillers published an algorithm for deletion in Delaunay Triangulations [ACM Symposium on Computational Geometry, Minneapolis 1999]. He has implemented it in 3-d. It should be straightforward to implement in Qhull.

    [1999] Mucke, et al, published an algorithm for fast randomized point location in Delaunay triangulations [Computational Geometry: Theory and Applications, 12:63-83, 1999]. Qhull users frequently ask about point location in Delaunay triangulations. For other methods, see the FAQ

    [1998] Shewchuk published an algorithm for constrained Delaunay triangulations [ACM Symposium on Computational Geometry, Minneapolis 1998]. An implementation of Shewchuk's algorithm would be a valuable addition to Qhull.

    If your group would like to maintain and enhance Qhull, please send e-mail to bradb@qhull.org. Project ideas include specialized versions, volumes of Voronoi regions, constrained Delaunay triangulations, and rewriting Qhull in C++ (see Enhancements to Qhull). Constrained Delaunay triangulations have many applications.

    To view graphical output under Windows, use Mathematica ('m'), Maple ('FM'), or Meyer's 3d Java applet. and OFF file format [use 'o' and delete the first line of output]. If you write VRML output for Qhull, please send e-mail to bradb@qhull.org.

    » Bug reports, notes, and work in progress

    Please report problems to qhull_bug@qhull.org.

    Here are the problems in previous versions of Qhull by version and by date. Problems are listed in the most recent version, Except for the current version, they are fixed in more recent versions. See Known Problems for problems in the current release of Qhull. See Change History for fixed bugs and new features in each release.

    Qhull 2020.1

    Qhull 2019.1

    Qhull 2015.2

    Qhull 2015.1

    Qhull 2012.1

    Qhull 2011.2

    Qhull 2011.1

    Qhull 2010.1

    Qhull 2009.1

    Qhull 2003.1

    Problems by date

    [Sept 2011] For Qhull library users. qh_new_qhull should call qh_prepare_output if outfile is not defined [A. Aldoma]. qh_prepare_output handles options that are computed after the convex hull (e.g., area and volume).

    [Apr 2011] In 3-d and higher, option 'Qt' does not produce conforming triangulations for adjacent, non-simplicial facets. This remains an open problem. See Known Problems. Related entries are [May 2007], and [Dec 2006] below.

    [Apr 2011] qh_newhashtable, qh_setnew, and qh_memalloc should report an error if the size argument is negative [X. Cheng]. Negative arguments may occur on 64-bit hosts due to integer overflow. Qhull uses 32-bit ints for identifiers, counts, and sizes.

    [Jan 2009] Qhull's qh_gethash [poly.c] allows a negative return value, leading to an overwrite or segfault. Upgrade to 2011.2 or 2009.1.2 or apply poly.c-qh_gethash.patch. .

    [Apr 2008] Qhull's qset.c does not compile correctly under gcc 4.1 and later with option -O2 (4.0.1 works OK [B. Shapiro]). These versions of gcc work correctly when compiled with -fno-strict-aliasing [R. Laboissiere]. gcc 4.4 appears to work OK. A workaround is to replace FOREACHsetelement_ with FOREACHsetelement_i_ in qh_setlast and qh_setappend of qset.c [A. Rossiter]. D. Szczerba also reported the problem. The following patch works on both 32-bit (ix86) and 64-bit (amd64) Linux PCs [S.D. Lee].

    --- Makefile    2003-12-31 11:20:50.000000000 +0800
    +++ Makefile    2008-04-09 15:20:13.192023303 +0800
    @@ -95,7 +95,8 @@
     merge.o:  $(HFILES)
     poly.o:   $(HFILES)
     poly2.o:  $(HFILES)
    -qset.o:   qset.h mem.h
    +qset.o:   qset.c qset.h mem.h
    +       $(CC) -c $(CCOPTS1) -fno-strict-aliasing $<
     stat.o:   $(HFILES)
     user.o:   $(HFILES)
    

    [May 2007] de Visser produced an example of the Dec 2006 'Qt' bug (see following) using Matlab. Notice that the triangulation is nonconforming between the non-simplicial regions (i.e., the cubes). Option 'QJ1e-8' may be useful as a workaround. It forces a triagulation by perturbing the input sites.

    [Dec 2006] In 3-d and higher with adjacent, non-simplicial regions, the output triangulation generated by option 'Qt' does not conform to the triangulation of the region's ridges, nor to the triangulation of its neighboring facets. For example, if you have a regular array of input sites, their Delaunay triangulation consists of cubes. Option 'Qt' will triangulate each cube into tetrahedra. Within each cube, the triangulation is consistent, but it is not necessarily consistent between adjacent cubes [C. Bertoglio; C. de Visser]. To visualize the qhull bug in geomview, load Qhull-Qt-bug.oogl as generated by

    rbox 32 M1,0,1 | qhull d Qbb Qt Gt | dos2unix > Qhull-Qt-bug.oogl

    [August 2004] Qhull may incorrectly report a coplanar input set if the max or min points along the coordinate axes are nearly coplanar and they include nearly coincident subsets. If so, the point set and inital simplex may be full dimensional, while at the same time, the initial simplex is not clearly convex. Other point sets can cause the same problem. These cases appear to be unlikely for most users. A workaround is to use option 'Qs'. [E. Voth]

    [Jan 2004] For qhalf users. The identity pipe for Qhull reveals some precision questions for halfspace intersections. The identity pipe creates the convex hull of a set of points and intersects the facets' hyperplanes. It should return the input points, but narrow distributions may drop points while offset distributions may add points. It may be better to normalize the input set about the origin. For example, compare the first results with the later two results: [T. Abraham]

    rbox 100 s t | tee r | qconvex FV n | qhalf Fp | cat - r | /bin/sort -n | tail
    rbox 100 L1e5 t | tee r | qconvex FV n | qhalf Fp | cat - r | /bin/sort -n | tail
    rbox 100 s O10 t | tee r | qconvex FV n | qhalf Fp | cat - r | /bin/sort -n | tail

    [Dec 2003] For Qhull library users. If you are writing code for Delaunay triangulations using the Qhull library, findDelaunay() in user_eg.c does not work for triangulated ouput ('Qt'). If the input sites are cospherical, findDelaunay will return one of several "tricoplanar" regions. Additional code will be needed to identify the correct region. See locate a facet with qh_findbestfacet().

    » How is Qhull used?

    If you find Qhull helpful, please let me know about your application. Send e-mail to bradb@qhull.org and I'll add you to the list below. If you publish a paper that mentions Qhull, please send a reference and abstract. Please use the following citation. See Highlights and Google Scholar for other Qhull references.

    Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T., "The Quickhull algorithm for convex hulls," ACM Transactions on Mathematical Software, 22(4):469-483, Dec 1996, http://www.qhull.org

    Qhull Users


    Up: http://www.qhull.org
    To:: Bug and Notes and Qhull Users
    Dn: FAQ about Qhull


    [HOME] The Geometry Center Home Page

    Comments to: qhull@qhull.org
    Created: Sept. 25, 1995 --- Last modified: see top