Up: Home page for Qhull (http://www.geom.umn.edu/locate/qhull)
Dn: Changes
Dn: FAQ about Qhull

News about Qhull

Brad Barber, Cambridge MA, March 7, 2002

Latest version

Qhull 3.1 from October 4, 2001 is the most recent version.

• Added triangulated output ('Qt'). Triangulated output replaces joggled input ('QJ') for Delaunay triangulations and other applications. Triangulated output is more accurate than joggled input.

• Identified a new class of difficult inputs. The following distributions have a few large facets and many small facets meeting at a sharp angle. See Limitations of merged facets.

       rbox 1000 s W1e-13 t | qhull d Tv
       rbox s 1000 W1e-13 P0 D2 t | qhull d Tv
       rbox 1000 s Z1 G1e-13 t | qhull Tv
  

• Rewrote qh_findbest() and qh_findbestnew() to better handle the previous inputs. The new code is easier to understand and may be faster.

To download the latest version use Download Qhull. The Spanish mirror site (ftp) is www6.uniovi.es. To view the documentation use Qhull manual. See README.txt for installation instructions and Changes.txt for change notes. See log00.htm and log01.htm for Qhull's web server statistics.

A special thanks to Mark Phillips for running the Geometry Center web site long after the Geometry Center closed. Mark is a founder of Geometry Technologies and a principal author of Geomview. The Geometry Center continues to be a good home for Qhull.

Bug reports, notes, and work in progress

If you are compiling Qhull with gcc-2.95.1, you need to set flag -fno-strict-aliasing. This flag is set by default for other versions of gcc [B. Karas and N. Krishnaswami].

The executable files for Makefile.txt are 'chmod +x ../eg/qhull' instead of '../eq/qhull' [B. Karas].

The hyperplane coefficients for cdd format (options 'FD' and 'Fd') have the incorrect sign. The offsets and point coefficients are correct. [T. Abraham]

Search Google for recent references to Qhull (updated in last 3 months). Search Google Groups for references to Qhull in newsgroups.

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.

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@geom.umn.edu.

MathWorks added qhull to MATLAB. See functions convhulln, delaunayn, griddata3, griddatan, tsearch, tsearchn, and voronoin. MathWorks uses joggled input ('QJ') to guarantee simplicial output. Triangulated output ('Qt') would produce more accurate results.

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@geom.umn.edu.

K. Erleben of Copenhagen University wrote a simple Visual C++ 6.0 interface to Qhull. He could not include qhull_a.h directly because of C++ conflicts with math.h.

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.

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

Veron and Leon published an algorithm for shape preserving polyhedral simplification with bounded error [Computers and Graphics, 22.5:565-585, 1998]. It remove nodes using front propagation and multiple remeshing.

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@geom.umn.edu. 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 Win95, use Mathematica ('m') or Meyer's 3d Java applet for 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@geom.umn.edu.

Please report problems to qhull_bug@geom.umn.edu.

How is Qhull used?

If you find Qhull helpful, please let me know about your application. Send e-mail to bradb@geom.umn.edu and I'll add you to the list below. If you publish a paper that mentions Qhull, please send a reference and abstract.

• 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.
• 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.
• 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.
• Boardman determined the principal components of spectral data.
• Bolson et al. analyzed 3-d models of heart chambers.
• 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.
• Eberwein determined the operating characteristics of process equipment.
• Ehmann implemented SWIFT++ for collision detection.
• 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).
• Grundman designed non-linear controllers for controlling vibration.
• 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.
• 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.
• 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.
• Kumar released Reviver [paper]for provable surface reconstruction from sample points.
• Kuss converted MS Flightsimulator planes to Flight Gear Flight Simulator format.
• Lovejoy studied nonlinear forecasting with fractal dynamics.
• Majhi, Janardan, Smid, and Gupta improved the surface finish of parts in layered manufacturing.
• Masubuchi simulated a spatial database system to evaluate spatial tessellations for indexing.
• Mirtich developed V-clip (Voronoi-clip) for collision detection of polyhedral objects.
• 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.
• 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.
• 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.
• 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.
• 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 colloidal glasses with a confocal microscope.
• Wloka wrote a cloth simulation demo for NVidia.
• 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: Home page for Qhull
Dn: Changes
Dn: FAQ about Qhull

The Geometry Center Home Page

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