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

[Feb 2012] Released Qhull 2012.1 2012/02/18

To download the latest version use Download Qhull or Gitorious (git://gitorious.org/qhull/qhull.git).

To install, see README.txt.

The changes in Qhull 2012.1 are for users who call Qhull from their programs. Users of qhull shared libraries may need to change their build. No change is needed if you compile Qhull into your program.

Upgrading to Qhull 2012.1

You may call Qhull from your program (Qhull Code). Qhull includes a C interface, a preliminary 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.

This site also hosts pages on C++ and Perl Guidelines for advice on writing programs, Road bash for a portable bash shell, Road Intranet for advice on Windows, Perforce, etc, and ttcnf for truth table CNF. Visit www.thesa.com for a thesaurus of research literature.

» Known problems

All users

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 versions for programmers

In poly2.c, qh_findbestfacet() is not implemented for triangulated output.

If Qhull appears to work but user_eg.c or your program reports no results, your code and the Qhull shared library use different settings for qh_QHpointer. Either compile your code with -Dqh_QHpointer, or change your shared library to libqhull.so.

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

    » Highlights

    [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.

    [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].

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

    [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 practise, 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. See Known Problems for problems in the current release of Qhull. See Change History for fixed bugs and new features.

    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 [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 December's 'Qt' bug 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. Visit 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