me | department | university | teaching | research | disclaimer | personal stuff

Graphics Tools and Utilities

Graphics programming is fun (at least, as long as one is not to track a memory leak or some other nasty bug ;-), and it is even more fun when the right tools are at hand. Here comes a short list of some of the tools which I have recently implemented. A very extensive list of graphics and math goodies is provided by Dave Eberly's Geometric Tools.

Intersection Tests
Checking for intersections among triangles, line segments, cylinders and spheres is a basic prerequisite for quite a few of the projects I have been involved in. (See, for instance, Collision detection for VR, and NC verification.)

M. Held (1997):
``ERIT: A Collection of Efficient and Reliable Intersection Tests''.
Journal of Graphics Tools 2(4):25-44, February 1999.

Please note: This code is not in the public domain, and no parts of it may be sold or re-distributed in its original version or in a modified version, in any format, without obtaining the prior written consent of the copyright holder. Please note that this excludes the use of ERIT within any open-source, shareware or commercial code.

Computing Adjacencies
The WWW offers tons of geometric models. Unfortunately, most of those models tend to come as so-called "polygon soups", i.e., as unstructured lists of triangles that lack any topological information on adjacencies. Clearly, an all-pairs check is too costly for anything but small models. Thus, I implemented a sorting scheme which recovers adjacencies among N triangles in time O(N logN). In addition, this module also does a little bit of data clean-up.

Polyhedral Approximations
For various applications I needed polyhedral approximations of surfaces of revolution. My software currently is able to compute triangulated approximations of spheres, sphere caps, cylinders, and of general solids generated by rotating a polygon around an axis.

Discrete-Orientation Polytopes
Jointly implemented with Jim Klosowski; see also the WWW page on bounding-volume trees.

PSLG Editor
Jointly designed with Gerhard Mitterlechner.

G. Mitterlechner, M. Held F. Gusenbauer (2005):
"Algorithmenbibliothek für PSLG-Grafikeditoren mit effizienter Online-Validierung zum Einsatz in Tunneldokumentationssystemen"

The following images show objects computed by means of my graphics tools. Click on an image icon in order to see the full-size image. The full-size images have 800x800 pixels.)

[Image of Triangulated Machine Tool] This image shows a polyhedral approximation of a tool used for NC machining.

[Image of Triangulated Machine Tool] This image shows a polyhedral approximation of another tool used for NC machining.

[Image of Triangulated Machine Tool] A 26-dop of a WW-II aircraft.

[Image of CS Logo]
file last modified: Thursday, 27-Feb-2020 07:29:07 CET
email address
Copyright © 2022 Martin Held. All rights reserved.
[Rock climbing]