page for Qhull (http://www.geom.umn.edu/locate/qhull)
Dn: FAQ about Qhull
News about Qhull
Brad Barber, Cambridge MA, March 7, 2002
Qhull 3.1 from October 4, 2001 is the most recent version.
To download the latest version use
The Spanish mirror site (ftp) is www6.uniovi.es.
the documentation use Qhull manual.
See README.txt for installation
instructions and Changes.txt for change notes.
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
and a principal author of
The Geometry Center continues to be a good home for Qhull.
Bug reports, notes, and work in progress
Most recent first.
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]
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
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
MathWorks added qhull to MATLAB.
See functions convhulln,
MathWorks uses joggled input ('QJ') to guarantee simplicial output.
Triangulated output ('Qt') would produce more accurate results.
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
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
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 firstname.lastname@example.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 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 email@example.com.
Please report problems to firstname.lastname@example.org.
How is Qhull used?
If you find Qhull helpful, please let me know about your
application. Send e-mail to email@example.com
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
- 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
- Belsis classified molecules by their biological activity.
- Boardman determined the principal components of spectral
- 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.
improved the secondary recovery from fractured oil
- Didwania computed the Delaunay triangulation for random
- Donolato modelled multicrystalline solar cells.
- Eberwein determined the operating characteristics of
- Ehmann implemented SWIFT++ for collision detection.
- Faken studied the structure of high-dimensional clusters.
- Gibson studied the simultaneous stabilization of two
- Goddyn studied circuits of matroids that form a Hilbert
- 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
- 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
- Harmon calculated the
morphological disparity among groups of species in the context of their
- 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
- Hirota reconstructed the surface of a patient's body from
- 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
- 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
- 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
- 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
- Porter built micromagnetic models with irregular grain
- Powers studied the creep rupture behavior of ceramic
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.
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
- Schkolne investigated interactive 3-d shape modeling.
- Schmidt determined point neighborhoods for cluster
- Schreier et al. found invariant sets for delta-sigma
- 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
- 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
- Thibout produced virtual reality systems.
- Thompson produced supports for mechanical parts from a
gas deposition rapid prototyping system.
- Urner built Waterman
- 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.
determined the shape of the left ventricle for electrical
analysis of hearts.
- Walker showed the movement of an object while recording
- 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
- 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
- Zwick computed the smallest enclosing annuli by
intersecting the Voronoi diagram with the furthest-site
Up: Home page for Qhull
Dn: FAQ about Qhull
The Geometry Center Home Page
Comments to: firstname.lastname@example.org
Created: Sept. 25, 1995 --- Last modified: see top