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

[RANDOM] Qhull News, Bugs, and Users

Bugs and Notes   ::   Qhull Users   ::   Change History   ::   Readme   ::   http://home.scarlet.be/zoetrope/voronoi3d/index.htm

[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 instructions, see Building Savi and Geomview under Windows. [L. Wood]

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

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

See Bugs and Notes for additional items.

[Dec 2003] Released Qhull 2003.1 2003/12/30

All users of joggled input ('QJ') should consider converting to triangulated output ('Qt'). Triangulated output was introduced in Qhull 3.1 2001/10/04. It is approximately 1000 times more accurate than joggled input.

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

You can call Qhull from your program. The Qhull library is difficult to use. 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. In poly2.c, qh_findbestfacet() is not implemented for triangulated output.

To download the latest version use Download Qhull. The Spanish mirror site (ftp) is www6.uniovi.es.

? Bug reports, notes, and work in progress

See Change History for a complete list of fixed bugs and new features. Visit ttcnf for truth table CNF. Visit www.thesa.com for a thesaurus of research literature.

[Apr 2008] Qhull's qset.c does not compile correctly under gcc 4.x with option -O2 (4.0.1 works OK [B. Shapiro]). Gcc 4.x works correctly when compiled with -fno-strict-aliasing [R. Laboissiere]. 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

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

[Feb 2005] The 'TO' option should close qh.fout. [F. Dorfbauer]

[Feb 2005] For qconvex, qdelaunay, qhalf, and qvoronoi users. The 'TI' option does not work if the file name contains a 'd', 'm', 'n', or 'v'. Either rename your input file or use the equivalent qhull command. [F. Dorfbauer]

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

[Jan 2005] For 'Q4' users. qh_findbest_test() in merge.c may return a garbage value for the minimum distance. For almost all users, this error only effects trace output and the Wminvertex statistic. It does not effect the minimum inner hull reported by 's' and 'Fs' (qh.min_vertex is recomputed as the minimum vertex). For 'Q4' users, it may change the selection of the merged facet. To fix the bug, replace "else maxdist= dist;" with "else {mindist= 0; maxdist= dist;}" [A. Tonchev]

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

[June 2004] For Qhull library users of convex hull and halfspace intersection. Contrary to spec, qh_findfacet_all() in poly2.c never returns a facet that is above a point. As a result, qh_findbestfacet() on inside points may report a facet on the opposite side of a convex hull. Neither routine is used in Qhull. The error does not effect Delaunay triangulations and Voronoi diagrams; these structures do not have inside points or lens distributions. In qh_findfacet_all(), "REALmin" should be "-REALmax" [L.A. Taylor]. 

	facetT *qh_findfacet_all (pointT *point, realT *bestdist, boolT *isoutside, int *numpart) {
	<clip>
	*bestdist= -REALmax;

[Feb 2004] Added Unix distribution of Qhull 2003.1 to the download page. It includes a 'configure' program for most Unix platforms [R. Laboissiere].

[Feb 2004] For Qhull library users. qh_produce_output() includes several housekeeping calls before calling the print functions. In the next version of qhull, those calls will move to a new function called qh_prepare_output(). Qhull library users should call qh_prepare_output() if qh_new_qhull() succeeds. The variables (qh VORONOI, etc.) are set from the option string. [P. Tarrafeta] 

	void qh_prepare_output(void) {
	  if (qh VORONOI) {
		qh_clearcenters (qh_ASvoronoi);
		qh_vertexneighbors();
	  }
	  if (qh TRIangulate) {
		qh_triangulate();
		if (qh VERIFYoutput && !qh CHECKfrequently)
		  qh_checkpolygon (qh facet_list);
	  }
	  qh_findgood_all (qh facet_list);
	  if (qh GETarea)
		qh_getarea(qh facet_list);
	  if (qh KEEParea || qh KEEPmerge || qh KEEPminArea < REALmax/2)
		qh_markkeep (qh facet_list);
	}

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

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

Please report problems to qhull_bug@qhull.org.

? 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 CiteSeer 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