http://www.geom.umn.edu/software/geomview/

Term Project

by: George North

439-68-5643

Computational Geometry

CSCI 6640

Fall 1995

Dr. N. Adla A. DePano

TABLE OF CONTENTS

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

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

NAME

rbox - generate point distributions for qhull

SYNOPSIS

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

DESCRIPTION

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.

OPTIONS

n number of points

Dn dimension n-d (default 3-d)

many other options (refer to WWW home page)

AUTHOR

C. Bradford Barber

c/o The Geometry Center

1300 South Second Street, Suite 500

Minneapolis, MN 55454

NAME

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

SYNOPSIS

Command "Qhull" (.) lists the options

(-) help message for all options

DESCRIPTION

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

MAIN OPTIONS

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

PERCISION OPTIONS

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

OUTPUT OPTIONS

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

ALGORITHM AUTHORS

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

Software.

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:

**http://www.geom.umn.edu/software/geomview/docs/geomview_toc.html **

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)