Qhull News, Bugs, and Users

» 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

• The C++ interface contained unnecessary dependencies on C++11.
• C++ Jave-style iterators used a pointer to container instead of a copy constructor. When used on temporary sets, subtle memory errors may occur.
• /usr/local/lib/pkgconfig for CMake debug builds named the files incorrectly.
• QhullSet::toQList (Qt only) failed to compile due to prototype and type errors.
• QhullFacet_test.cpp contained an incorrect test of hyperplane epsilon.
• Function documentation contained many broken links when installed to /usr/local/include/libqhull*. Use www.qhull.org instead.

Qhull 2019.1

• SOVERSION was not incremented despite substantial ABI breakage.
• operator->() was defined incorrectly for QhullLinkedList::const_iterator.
• merge_r.c/qh_appendmergeset,qh_appendvertexmerge,qh_mergefacet,qh_tracemerge: fix error check of index for mergetypes

Qhull 2015.2

• qh_buildcone_onlygood ('Qg') corrupted memory if it called qh_delfacet.
• qh_check_maxout did not include qh.DISTround when checking f.maxoutside
• qh_distround did not acount for 'Rn' (random roundoff) in option 'QJn'
• qh_findbestfacet should document that it may return an adjacent triangle for Delaunay triangulations [F. Drielsma]
• qh_findfacet_all should not search visible facets or f.upperdelaunay facets [P. Virtanen, S. Dominguez, J.Arkin]
• qh_findgood may report a bad facet for qh.GOODvertex ('QVn'). Restrict the search to good facets.
• qh_freebuild deleted unattached ridges, leading to a double delete
• qh_initial_hull tested 'maybe flipped' instead of 'clearly flipped'. As a result facets could be incorrectly oriented, leading immediately to 'Only 4 facets remain' [S. Caron, P. Virtanen, D. Sterratt, others]
• qh_initstatistics was missing initialization. As a result, the final qh_checkoutput may be skipped.
• qh_initstatistics cannot use qh_fprintf to report errors. Use qh_fprintf_stderr
• qh_maxsimplex did not detect nearly flat simplices except for the last vertex. It assumed the max coordinate was approximately 1. As a result, Qhull reported false narrow hulls or false low dimensional inputs. [J.R. Roussel, D. Sterratt]
• qh_option could overflow the qh.qhull_options buffer
• qh_partitionpoint could leave an outside point before qh.next_facet, leading to a skipped point.
• qh_stddev was incorrect. It should be sqrt of absolute value.
  

• 'Qbb' scaled the last coordinate to qh.MAXwidth causing loss of precision. It should be qh.MAXabs_coord.
• 'rbox' and 'user_eg3' returned non-zero exit status for their help prompt. Should be 0.
• 'rbox Cn,r,m' does not produce points for 'rbox r'
• An error in qh_initqhull_start2 could loop forever. Need to set qh.NOerrexit
• Do not call qh_check_points ('Tv') if reporting an error and qh.FORCEoutput ('Po')
• If 'd' or 'v' was used with 'H', memory corruption occurred. Should be disallowed.
• Improved searching of coplanar facets by qh_findbesthorizon.
• Options 'Pdk' and 'Pdk' always returned the closest facet. This should only occur with option 'Pg'.
• PointCoordinates::appendPoints should not require whitespace after a point
• Setting qh.MINoutside could lead to verification ('Tv') failures. Fixed by setting qh.KEEPnearinside and calling qh_partitionpoint in qh_partitionall

Qhull 2015.1

• The C++ interface has a memory leak (e.g., 'user-eg3 eg-100') [M. Sandim].
• QhullLinkList::last() and back() returned a reference to computed results (T&) instead of the results (T)
• CMakeModules was missing from the distribution [C. Rosenvik]
• The DevStudio 2012 builds did not work.

Qhull 2012.1

• Point partition may lead to a rare "all facets flipped or upper Delaunay" [error QH6228, J. Metz, L. Fiaschi, N. Bowler, A. Liebscher, V. Vieira, N. Rhinehart, N. Vance, P. Shafer].
• If errfile is incorrectly NULL in qh_new_qhull(), qhull goes into an error reporting loop (https://bugs.debian.org/738339) [D. Haley]
• Coverity reported errors for logging after 'delete' and missing checks [K. Schwehr]
• qh_findbestfacet has an incorrect test for isoutside [Coverity, K. Schwehr]
• QHULL_UNUSED is incorrect for C compilers that define __INTEL_COMPILER [R. Stogner]

Qhull 2011.2

• gcc 4 requires -fno-strict-aliasing to compile qset.c. Otherwise qset segfaults on most input.
• qh_setappend_set fails to append an empty set to a full set (does not occur in qhull). An error or segfault occurs when using the resulting set.

Qhull 2011.1

• Qhull-go reports a not-compatible error. The code itself is OK.
• Qhull may silently overflow on 64-bit hosts (e.g., rbox 64 D32 | qhull). [X. Cheng]
• If programmers set outfile=0, qh_prepare_output is not called. Triangulation, area, volume, Voronoi vertices, statistics, good facets are not done. [A. Aldoma]
• gcc 4 requires -fno-strict-aliasing to compile qset.c. Otherwise qset segfaults on most input.
• qh_setappend_set fails to append an empty set to a full set (does not occur in qhull). An error or segfault occurs when using the resulting set.

Qhull 2010.1

• Qhull-go reports a not-compatible error on 64-bit hosts. The code itself is OK.
• If programmers set outfile=0, qh_prepare_output is not called. Triangulation, area, volume, Voronoi vertices, statistics, good facets are not done.
• Output of QhullVertex throws error QH10034 and does not define defineVertexNeighbors(). [renangms]
• QhullFacet::PrintRideges did not check hasNextRidge3d
• Qhull may silently overflow on 64-bit hosts (e.g., rbox 64 D32 | qhull).
• gcc 4 requires -fno-strict-aliasing to compile qset.c. Otherwise qset segfaults on most input.
• qh_setappend_set fails to append an empty set to a full set (does not occur in qhull). An error or segfault occurs when using the resulting set.

Qhull 2009.1

• qh_gethash causes an overwrite or segfault on 32-bit hosts running in high memory (poly.c-qh_gethash.patch).
• 'TO' and 'TI' options did not allow filenames starting with 'd' or 'v'.
• rbox ignored flags that were not separated by spaces
• qh_pointid was incorrect if ptr_intT was unsigned
• qh_build_withrestart did not clear qh.STOPcone for option 'QJn'
• qh_findfacet_all used 'REALmin' instead of '-REALmax' so the search did not always work. [L.A. Taylor]
• Triangulated facets freed facet->centrum twice.
• findbest_test initialized mindist incorrectly if testcentrum=0 [Ratcliff]
• rbox could overflow the 'command' buffer when appending seedbuf.
• qh_initqhull_globals used an incorrect upper bound for the sanity check of qh_RANDOMmax
• qh_eachvoronoi segfaults if fp=0 and printvridge=1. [D. Szczerba]
• qhmem computed totshort incorrectly
• many warnings reported when compiled [kwilliams]
• Qhull may silently overflow on 64-bit hosts (e.g., rbox 64 D32 | qhull).
• gcc 4 requires -fno-strict-aliasing to compile qset.c. Otherwise qset segfaults on most input.
• qh_setappend_set fails to append an empty set to a full set (does not occur in qhull). An error or segfault occurs when using the resulting set.

Qhull 2003.1

• Undefined evaluation order for pre-incremented arguments to strtod in rbox
• qh_produce_output and qh_initstatistics used '%d' instead of '%lu' for size_t arguments
• See Qhull 2009.1 for other problems.

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

• [Apr 2019] K. Johnston incorporated Lloyd's QuickHull3D.java as part of his VariableStarAnalysis. See VariableStarAnalysis/blob/master/common/utilities/math-utilities/.../QuickHull3D.java (github) and QuickHull3D.java under 'Fall 2004' highlights above.

• [Mar 2019] S. V. Rakovic uses Qhull for model predictive control.

• [Jun 2018] F. Drielsma published Measurement of Phase Space Density Evolution in MICE on the Muon Ionization Cooling Experiment (MICE). He used Qhull to compute the volume of the fractional emittance.

• [Feb 2018] J. Mangelson used Qhull for some research on convex robotic trajectory alignment.

• [Feb 2017] Using Qhull, Easwar added 3-d convex hulls to OriginLab DataAnalysis > 3D Convex Hull.

• [Oct 2016] J. de Brumath uses Qhull for the CFDM : French Cup of Distance with Powered Paraglider (all entries, explanation). The whole competition is based on the convex hull of the GPS trace of each submitted flight,

• [Jul 2016] M. Faes computes the volume of 4-d and higher convex hulls for non-probabilistic uncertainty quantification.

• [Feb 2016] C. Carson and J. Levine studied x-ray computed tomographic images of foamed cement and their 2-d cross sections. Other applications include porous media transport and crack-tip propagation [Journal of Microscopy, 2016.

• [Jul 2015] A. Tomilov implemented the Quickhull algorithm for points in general dimension (quickhull.hpp, doc-ru). It checks that the output is clearly convex.

• [Jun 2015] G. Sicherman determined the smalled polyomino whose convex hull is an N-gon.

• [Jun 2015] C. Carson computes 3-d tessellations of closed pore materials. He uses the Scipy implementation of Qhull.

• [Nov 2014] Heylen and Scheunders used Qhull in their algorithm to estimate the pixel purity index for hyperspectral image processing [Tran. Geosci. Remote Sensing, 2003].

• [Aug 2014] J. Pavia analyzed proportion configurations that produce a particular share of seats in a Parliament after using d'hondt rule and other constraints.

• [Jul 2014] Q. Zhang constructed surrogate models for mixed-integer linear programs and data-driven optimizations

• [Jan 2014] NifTools includes Qhull for building the NetImmerse/GameBryo game engine.

• [Oct 2013] M. Peigney studied the quasiconvex hull of energy-minimizing, stress-free strains of martensitic structures (J. Mechanics and Physics of Solids, 61.6 (2013).

• [Apr 2013] Y. Xu found galaxy clusters from the Second Center for Astrophysics Galaxy Catalog (abstract). They match the known clusters very well.

• [Mar 2013] Leica Geosystems uses Qhull to help view and process point clouds from 3d scanners.

• [Mar 2013] M. Freese added Qhull to v-rep, a virtual robot experimentation platform.

• [Feb 2013] M. Treacy finds open space in crystalline zeolite structures.

• [July 2012] B. Bahlberg et. al. measured the technical inefficiency of a firm using the principle of least action. They used Qhull to determine the supporting hyperplanes for the efficiency boundary.

• [May 2012] Khirevich et al. studied advection-diffusion transport in the pore space of random sphere packings, used Qhull to analyze geometry of the pore space, and based on this analysis derived scalar geometrical descriptors demonstrating a strong correlation with the simulated transport coefficients (hydrodynamic dispersion coefficient and effective diffusion coefficient).

• [Dec 2010] Flash Foto, Inc uses qhull for face-hair segmentation, which separates the face and hair of a person from the background - on most people, the top of the head is convex.

• [Nov 2010] Robert's PC-DMIS controls coordinate measuring machines for manufactured parts. It uses qhull to compute some of the geometry from sampled points.

• [Nov 2010] Vasilakis and Fudos computed the convex hull and half-space intersection for their refined skeleton extration method. See "GPU rigid skinning based on a refined skeletonization method" [paper].

• [Aug 2010] Brinch and Hogerheijde developed LIME for solving the molecular and atomic excitation and radiation transfer problem in a molecular gas and predicting emergent spectra [abstract and paper]

• [June 2010] Reuter triangulates point clouds from astrophysical Smoothed-Particle Hydrodynamics simulations. The output is used for visualization. See their project description.

• [Mar 2010] Fallavollita integrated fluoroscopic and electrical data from RF catheters to assist cardiac ablation procedures [paper]

• [Feb 2010] Mac Dermed and Isbell produced an approximation algorithm for stochastic games with multi-agent reinforcement learning [paper];

• [April 2009] Dalbey constructed predictive simulation and model based hazard maps of geophysical mass flows.

• [April 2009] Kruip and Paaredekooper construct Voronoi-Delaunay structures for their radiative transfer method SimpleX.

• [June 2008] Jena computed the surface mesh for point clouds generated from radiotherapy treatment planning data in brain tumours.

• [May 2008] Bhamidipati modeled grain geometry in a polycrystalline material.

• [May 2007] Mughal studied topological defects in the crystalline state of one-component plasmas of non-uniform density [paper; to appear in Phy. Re E.]

• [April 2007] Grossman created metal sculptures with a mathematical twist, Bathsheba Sculpture.

• [April 2007] Antiprism is a collection of programs for generating, manipulating, transforming, and visualizing polyhedra. Includes transforms from OFF format to VRML and other formats.

• [April 2007] Myers' PyXL modeled synthetic microstructrues of polycrystalline materials.

• [Mar 2007] Rodrigues modeled damping controllers for electric power systems

• [Mar 2007] Yoshizawa approximated the 3-D medial axis with a Voronoi-based skeletal mesh.

• [Mar 2007] blitz3d used a Qhull 1.0 library to simplify collision tests.

• [Dec 2006] Boyle located the nuclei of cells in a devaloping embryo (e.g., section thru a C elgans embryo at the 88 cell stage).

• [Nov 2006] Oesterle and Knauss of KOOK Architecture visualized 3-d Voronoi diagrams with Rhino. See the qvoronoi page.

• [Nov 2006] Gardener generated triangular meshes for point cloud data in Daylon's Leveller, a heightfield/bumpmap/terrain modeler. A common source of point cloud data is ocean seafloor scans or radar altimetry.

• [Nov 2006] King wrote MorseExtract to convert functions over a 3-d simplicial complex to a discrete Morse function in the sense of Forman.

• [June 2006] Belov thermodynamically calculated the phase diagram of heterogeneous systems using Gibbs energies [Russian J Physical Chemistry, 77.10:1685-1694, 2003].

• [March 2006] Schmeja measured the area and volume of young star clusters. See S. Schmeja & R.S. Klessen, "Evolving structures of star-forming clusters," Astronomy & Astrophysics, 449 (2006), 151, preprint.

• [Dec 2005] Petrek uses qconvex in CAVER. CAVER provides rapid, accurate and fully automated calculation of pathways leading from buried cavities to outside solvent in static and dynamic protein structures. Study of these pathways is important in drug design and molecular enzymology to understand binding of inhibitors to the receptors, substrate binding and product egress from the enzyme active sites. Calculated pathways can be visualized by graphic program PyMol dissecting anatomy and dynamics of entrance tunnels.

• [Nov 2005] Ritzerveld, Icke, and Rijkhorst computed radiation transport on unstructured grids using their SimpleX method (paper). They performed large scale cosmological simulations on a simple desktop computer. For archived samples, see TrianRad poster and Reionization.

• [May 2005] Ferri et al evaluated classifiers in machine learning by computing the volume under receiver operating characteristic surfaces [Ferri, C., Hern?ndez-Orallo, J.. Salido, M.A., "Volume under the ROC Surface for Multi-class Problems," 14th European Conference on Machine Learning, 108-120, 2003].

• [April 2005] Landman found asymptotic solutions of boundary value problems involving vibrations of rotating thin shells of revolution. The algorithm permits the symbolic integration of the governing equations for any range of values of the parameters appearing in these equations.

• [Feb 2005] Jaramillo analyzed sesmic data using Voronoi diagrams as described in Gardner and Canning, "Reducing 3-D acquisition footprint for 3-D DMO and 3-D prestack migration," Geophysics, VOL 63, No 4 (July-August 1998).

• [Jan 2005] Piche identified thermodynamically valid sets of coexisting minerals (phases) for any given rock composition.

• [Jan 2005] Galvao investigated a conjecture concerning probability polytopes arising from measurements in quantum theory. He used Qhull to compute the convex hull of 30 points in 24 dimensions. See Galvao, E.F., "Discrete Wigner functions and quantum computational speed-up," to be published in a journal of Physics Review A.

• [Sept 2004] Xu found galaxy clusters at Los Alamos National Lab.

• [August 2004] Casale studied bottleneck analysis of queueing networks models. See Casale G., Serazzi G., "Bottlenecks Identification in Multiclass Queueing Networks using Convex Polytopes," Proc. 12th IEEE/ACM Inter. Symp. on Modeling, Analysis, and Simulation of Comp. and Tlc. Systems (MASCOTS 2004) (PDF).

• [July 2004] Moon is using Qhull to determine the atomistic configurations at the grain boundaries of materials. Knowledge on local volume along grain boundary gives insight on the segregation phenomena.

• [June 2004] Taylor found the attainable region of a set of chemical reactions.

• [May 2004] Erleben added Qhull to OpenTIssue: An Open-source Library for Physics-based Animation.

• [Mar 2004] From Dr. Anis Limaiem, Wilcox Associates (PC-DMIS):

  I started using qhull a couple of weeks ago. It is really an excellent tool. Even though it is not written in an API form and is not object oriented, once you understand its data structure and its different features you can do miracles . I used it to implement curve and surface reconstruction using the crust algorithm as well as discrete curvature estimation.

• [Mar 2004] Errami used Qhull to tessellate protein surfaces in Friend. Qhull was much faster than their previous implementation. Friend is aimed to interactively manipulate hundreds of proteins, visualize spatial structures, amino-acid and nucleotide sequences and alignments, active and binding sites, fragments, and domains in protein and gene families.

• [Feb 2004] Laboissiere et. al. used Qhull in the scientific plotting library, PLplot. They used Qhull to obtain grid data from irregularly sampled data [Examples].

• [Feb 2004] Neyrinck found haloes in cosmological N-body simulations [VOBOZ]. These simulations simulate the gravitational clustering of dark-matter particles in the universe, which form clumps where galaxies can form, called haloes. He used Qhull to find the Voronoi diagram of these particles, which finds both a natural set of neighbors and an estimate of the density (1/Volume(Voronoi cell)). He also used Qhull to find the volume of each cell.

• [Jan 2004] Shea released TesselSphere 1.1. It uses Qhull to generate vertexia for rendering pollen, viruses and radiolaria (an example).

• Alcock and Hare studied the excited states of particles on a sphere.
• Alfs simulated the kinematic configuration control of redundant robots.
• Allen et al. computed support structures for objects in layered manufacturing [submitted to Journal of Design & Manufacturing, 1995].
• Archer wrote the game 'VGA Planets'. It uses Voronoi diagrams for the political maps of galaxies.
• Bapat computed the straightness and flatness tolerance for a set of Coordinate Measuring Machine data points.
• Bacik rendered the great outdoors with fast occlusion culling
• Bishop studied phase field simulations of microstructural evolution in ceramics.
• Begnis computed grain boundaries for simulating the precipitation of carbo-nitrides in a nitrided alloyed steel.
• Belsis classified molecules by their biological activity.
• Blekas, Likas, and Stafylopatis built a neural network classifier based on geometrical fuzzy sets [IEEE International Conference on Tools with Artificial Intelligence (ICTAI'97), Nov. 1997}
• Boardman determined the principal components of spectral data.
• Bolson et al. analyzed 3-d models of heart chambers.
• Bordignon, [Journal of Guidance, Control, and Dynamics, 18.5, 1995].
• Braun estimated the emittance of extracted beams from the Tevatron Fixed Target lattice.
• Bromley studied the rotation of a supermassive black hole in active galaxy MCG-6-30-15.
• Buddenhagen visualized the polyhedra that maximized the minimum distance between vertices.
• Butte used Qhull for x-ray crystallography research.
• Cameron wrote code to compute the distance between convex polyhedra.
• Cornell's Multiscale Materials Modeling Collaboration tessellated a cube with 10000 grains.
• Dershowitz improved the secondary recovery from fractured oil reservoirs.
• Didwania computed the Delaunay triangulation for random sphere packings.
• Donolato modelled multicrystalline solar cells. [Semiconductor Science and Technology, 99/00?]
• Eberwein determined the operating characteristics of process equipment.
• Ehmann implemented SWIFT++ for collision detection.
• Ekawati and Bahri assessed the controllability of an industrial five effects evaporator process utilizing the Modified Dynamic Operability Framework. [submitted to Journal of Process Control, April 2002]
• Faken studied the structure of high-dimensional clusters.
• Gibson studied the simultaneous stabilization of two systems.
• Goddyn studied circuits of matroids that form a Hilbert base.
• Goslinga investigated stationary and optimal solutions to the Points on a Sphere problem.
• Grenestedt generated cell structures of closed cell 3D cellular solids (e.g., expanded PVC and foamed metals).
• Grundmann designed non-linear controllers for controlling vibration [Ph.D. thesis, "Robust Control of a Two-Mass-Oscillator by linear State Feedback and Nonlinear, Time-Optimal Control Rules," TU Dresden 1997].
• Guyler used Qhull and MATLAB to visualize the printing gamuts of various wide gamut ink systems in 3D true color. Qhull solved their previous connectivity problems with gamut surface visualization.
• Habel added Qhull to GNU Octave for Delaunay triangulation, Voronoi Diagrams and Convex Hull. Octave is an open source clone of MATLAB.
• Harmon calculated the morphological disparity among groups of species in the context of their evolutionary history.
• Harris reproduced some of Zilles's work on human brain cortical convolution measurement.
• Hase found the largest gaps in between the reference points of of a global reference frame. This was work for the Transportable Integrated Geodetic Observatory.
• Hemkemeier constructed a very dense sphere packing of the E^9 lattice.
• Hirota reconstructed the surface of a patient's body from sampled points.
• Holley studied globular protein folding by computing the convex hull of hydrophobic sidechain atoms.
• Indumathi classified handwritten digits.
• Ierapetritou developed and analyzed efficient models and solution methodologies for product and process design and process operations.
• Irisa extended scaled particle theory and calculated the hydration free energy of protein.
• Jackson analyzed and visualized contaminant plumes based on groundwater samples.
• Jervis and Briant studied stable vortex arrays in rotating superfluid helium.
• Johnson analyzed remote sensor images with 300,000+ pixels, each with 44 channels of spectral data.
• Joshi et. al. studied the spatial organization of a deciduous forest.
• Kelly computed the volume of home ranges for ringed seals under the Arctic icepack.
• Kristiansen estimated urinary bladder volume based on surface points obtained from compound ultrasound scanning.
• Kumar released Reviver [paper] for provable surface reconstruction from sample points.
• Kuss converted MS Flightsimulator planes to Flight Gear Flight Simulator format.
• Levy simulated the collision of galaxies
• Littlewood, Drakopoulos, and Subbarayan minimized ink during CIELAB to CMYK color conversion for printer color management [ACM Transactions on Graphics, 21.2:132-175, 4/02]
• Lovejoy studied nonlinear forecasting with fractal dynamics.
• Majhi, Janardan, Smid, and Gupta improved the surface finish of parts in layered manufacturing [ACM Workshop on Applied Computational Geometry, June 1996].
• Masubuchi simulated a spatial database system to evaluate spatial tessellations for indexing.
• Michel, Giavitto, and Cohen added Delaunay graphs and Voronoi neighborhoods to their language, mgs.
• Mirtich developed V-clip (Voronoi-clip) for collision detection of polyhedral objects.
• Montesinos wrote NormNewPoly, abbreviation for Normals to Newton Polyhedra.
• Mouat solved Radial Basis Function surface fitting problems in 2 and 3 dimensions.
• Nagle detected collisions between a falling robot and its environment.
• Netanyahu et al. let robots learn how to navigate.
• Orlando simulated silicon detectors for a proposed calorimeter.
• Pearlmutter triangulated brain magnetoencephalogrphic data for publication.
• Perez-Minana analyzed the training sets for a multi-layer perceptron model.
• Porter built micromagnetic models with irregular grain structures.
• Powers studied the creep rupture behavior of ceramic materials.
• Rappoport and Spitz interactively construct solid geometry models for conceptual design [SIGGRAPH'97].
• Rasanen built geographical information systems.
• Roosen et al developed Wulffman for interactively examining the Wulff shapes of crystals with specified symmetries.
• Rosenthal mapped global snow cover from satellite data using unsupervised spectral unmixing.
• Sambridge et al. modeled subduction zones of tectonic plates and studied fluid flow and crystal deformation [Nature, 376:655-660, 1995].
• Seynaeve computed serving areas for a GSM cellular operator.
• Schkolne investigated interactive 3-d shape modeling.
• Schmidt determined point neighborhoods for cluster analysis.
• Schreier et al. found invariant sets for delta-sigma modulators.
• Schwarzkopf wrote Ipe, an extendible drawing editor. It includes an extension for drawing Voronoi diagrams, Delaunay triangulations, order-2 and order-3 Voronoi diagrams, furthest point Voronoi diagrams, and the medial axis of a convex polygon.
• Silva found efficient facets in a DEA (data envelopment analysis) context.
• Singh analyzed protein 3D structure.
quick
• Sullivan studied the neighbors of the origin in the R^8 lattice.
• Thibout produced virtual reality systems.
• Thompson produced supports for mechanical parts from a gas deposition rapid prototyping system.
• Urner built Waterman polyhedra.
• van den Bergen developed SOLID for collision detection of 3-d objects undergoing rigid motion and deformation.
• Velez performed discrete simulations of incompressible viscous fluids using vortex methods.
• Viggiano and Hoagland determined the color gamuts for six-color lithographic printing
• Voth determined the shape of the left ventricle for electrical analysis of hearts.
• Walker showed the movement of an object while recording stresses.
• Weeks studied the physics of colloidal glasses (archived) with a confocal microscope [Weeks, et. al., Science, 2000]
• Wloka wrote a cloth simulation demo for NVidia with a demo.
• Wright and independently, Hayashi, created 6-d "wrench spaces" to measure the stability of robot grasps.
• Xavier simulated rigid-body dynamics with intermittent and continuous contact.
• Zheng et al. computed 3-d, unstructured meshes for computational fluid dynamics.
• Zaboj wrote a convex hull plugin for k3studio
• Zwick computed the smallest enclosing annuli by intersecting the Voronoi diagram with the furthest-site Voronoi diagram.

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

The Geometry Center Home Page

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