... this page is part of the Web Site of George North ...


Term Project

due Monday, November 27, 1995

by: George North

Computational Geometry
CSCI 6640
Fall 1995

Dr. N. Adla A. DePano


Graphic (borrowed from Geomview Home Page) Cover
The Assignment 3
Introduction 4
Methods 4
Recommendation 5
rbox 6
Qhull 7
Geomview 9
Printed Copy of Geomview Manual 10 to 110

Term Project
... view 3-D Convex Hull algorithm "at work"


I used two resources that turned out to be invaluable in my work on this project: the World Wide Web, and my classmate Karen Heath. Within a day of being assigned this project, Karen had downloaded the Geomview software and began to install it in her ho me account on the Computer Science Unix systems. There were some initial problems, and with some help it was determined that Geomview was not compatible with the new version of Unix installed during this past summer. After another day, Karen had Geomview up and running in "~kheath/Pub/Geomview" directory. We obtained a printed copy of the Geomview manual. With "Tutorial" in hand, our entire class met one morning in the CS lab to text drive Geomview.

I found Geomview's user interface pleasant, but at times confusing. It uses too many windows to display its control structures. I found it difficult to remember how these windows interacted ... and at times I could not predict the results of my actions. It was never determined if this was my inexperience, or a defect in Geomview. This system is certainly not short on options. These can be applied interactively and through its own command language. Geomview is a multipurpose tool, developed over sever al years, by several different teams. I think that this has contributed to its confusing using interface.

With Geomview at a tool, and working closely with Karen Heath, I set about the task to "view 3-D convex hull algorithm at work" ... to construct a video history of the solution process. Much of the credit for the work we did must go the Karen.


We had learned that Geomview would allow us to view a 3-D convex hull (in color, in 3-D space). And Geomview included features that would allow for objects to be animated . From our experience with the Tutorial, we had example of Geomview input. Two other requirements were identified: (i) random points in a unit sphere, and (ii) an implementation of a convex hull algorithm.
The first experiments were with the program chull.c . It produced the needed solution to convex hull algorithm, but a satisfactory solution of transforming its output to Geomview input not found. Two programs found at the Geomview home page seem to offer a solution. Qhull.c is an implementation of the Quick Hull algorithm. Its output can be formatted in several ways, at least one of which is compatible with Geomview. Included with Qhull.c was rbox.c . This utility can generate random points in 3-D space (n-D space). Its output can be piped directly to Qhull.c. What remained was to coerce Geomview into animating Qhull.c's output. This was not a trivial task.
Many weeks past as we experimented with various ways to combine Qhull.c with Geomview's animate features. Karen Heath's term project paper describes the procedures used in getting these three programs to work together. I expect that several other methods exist to automate Geomview's output. In part, the problems we encountered result from the ins tallation of a new version of Unix on the Computer Science systems. A patch to upgrade Geomview to Unix System V is available, but has not been installed. Rbox used a version of a random function that was removed from the standard libraries.


Geomview should be reinstalled and its System V patches applied. A Unix system administrator should be responsible for this. Students should be referred to the Geomview home page ( http://www.geom.umn.edu/software/geomview/). Much valuable information exists there, including a complete Geomview manual. The Qhull home page is also helpful ( http://www.geom.umn.edu/software/qhull/). Much of the utility software referenced at these sites should also be installed for general use.



rbox - generate point distributions for qhull

Command "rbox" (w/o arguments) lists the options.

rbox generates random or regular points according to the options given, and outputs the points to stdout. The points are generated in a cube, unless 's' or given. The format of the output is the following: first line contains the dimension and a c omment, second line contains the number of points, and the following lines contain the points, one point per line. Points are represented by their coordinate values.

n number of points
Dn dimension n-d (default 3-d)
many other options (refer to WWW home page)

C. Bradford Barber
c/o The Geometry Center
1300 South Second Street, Suite 500
Minneapolis, MN 55454



Qhull compute convex hulls, Delaunay triangulations, Voronoi vertices, and halfspace intersection.

Command "Qhull" (.) lists the options
(-) help message for all options

Qhull is a general dimension code for computing convex hulls, Delaunay triangulations, Voronoi vertices, and halfspace intersection. It implements the Quickhull algorithm for computing the convex hull. Qhull handles round-off errors from floating point ari thmetic. It can approximate a convex hull. Synopsis of Qhull

By default, Qhull computes the convex hull of the input points (description of qhull). The same code can also compute the following structures:
d Delaunay triangulation by lifting points to a paraboloid
v Voronoi vertices via the Delaunay triangulation
Hn,n halfspace intersection about point [n,n,0,...]

C-0 Qc handle precision problems by merging non-convex facets
A-0.9 merge facets if cosine of angle > 0.9
Qx handle precision problems in 5-d and higher
Tv verify result: structure, convexity, and point inclusion

s summary of results to stderr (default)
i vertices incident to each facet or Voronoi cell
o OFF file format for facets or Voronoi cells
n normals with offsets
p vertex or Voronoi vertex point coordinates
FA compute total area and volume for summary
G Geomview output (2-d, 3-d and 4-d)
m Mathematica output (2-d and 3-d)
f print all fields of all facets

Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T., "The Quickhull algorithm for
convex hulls," May 25, 1995, submitted to the ACM Trans. on Mathematical



What is Geomview?

Geomview is an interactive program, written by staff members of the Center for the Computation and Visualization of Geometric Structures, a National Science Foundation
Science and Technology Center at the University of Minnesota. Geomview is for viewing and manipulating geometric objects. It can be used as a standalone viewer for static objects or as a display engine for other programs which produce dynamically changing geometry.

It runs on Silicon Graphics (SGI) IRIS workstations and NeXT workstations. Also, an X11 version of Geomview currently exists and has been compiled on Linux, Sun sparc, HP Risc, IBM RS/6000 and Dec Alpha workstations.

A complete manual for Geomview is available online at the Geometry Center. A postscript version is available for download. Geomview binaries and source can be downloaded from the software library. Visit the Geometry Center on WWW at:

Tamara Munzner, Stuart Levy, and Mark Phillips are the original authors of Geomview. Celeste Fowler, Charlie Gunn, and Nathaniel Thurston also made significant contributions. Daniel Krech and Scott Wisdom did the NeXTStep and RenderMan port, and Daeron Mey er and Tim Rowley have worked on the port to X windows.

Version 1.5 of Geomview for X
Geomview (Sun4 binary, X11 version) (5.9 Meg)
Geomview (HP binary, X11 version) (3.8 Meg)
Geomview (Linux binary, X11 version) (4.4 Meg)
Geomview (DEC Alpha binary, X11 version) (4.4 Meg)
Geomview (IBM RS/6000 binary, X11 version) (4.3 Meg)
Geomview (source code) (4.5 Meg)