mspage

A Library for Spherical Geometry with an Application to Visibility Computations

Plan B Master's Project

This work was completed in partial fulfillment of the requirements for an MS degree from the
Department of Computer Science and Engineering, University of Minnesota.

Overview

Computational geometry, as a discipline, is concerned with providing efficient algorithmic solutions to problems involving geometric entities such as points, lines, polygons, polyhedra, and freeform curves and surfaces. Historically, the focus within the field has been on theoretical investigation. Today however, computational geometry is in transition. There is a conscious shift toward the applied. As a result, there is a need for working libraries of geometric code. This project is step toward meeting that need. It provides implementations of three basic algorithms for solving geometric problems on the unit sphere. The efficacy of these implementations is demonstrated via an application which computes directions of visibility for the surfaces of non-convex polyhedra.

A PDF copy of the full report on the project and associated library is available here.

The Algorithms

Click on any image for a larger view.

Hemisphericity

The "hemisphericity" operation takes a set of points on the surface of the unit sphere and determines if that point set can be contained within a hemisphere. If the answer is in the affirmative, the algorithm constructs a bounding hemisphere. This is shown in the image to the right, the hemisphere is represented by blue "circle with a handle."

Spherical Convex Hull

Given a set points on the unit sphere, spherical convex hull constructs a convex spherical polygon of minimal area that bounds the set.

Hemisphere Intersection

Given a set of hemispheres, this algorithm finds the convex spherical polygon formed by their intersection. In the image to the right, the hemispheres are shown as the circles with handles, and the intersection is shown as a green edged polygon (somewhat difficult to see, as it runs along the boundaries of the hemispheres).

Application to Visibility Computations

The algorithms in the library can be used to compute directions of visibility for the surfaces of polyhedra. If you take a single facet, you can imagine collecting all the lines of sight that hit the surface. In accord with intuition, these lines will all fall within 90 degrees of the normal vector of the facet. If we map these vectors to points on the unit sphere, we get a hemisphere.

When the polyhedron has an identation, or "pocket", the visibility for a facet within the pocket is limited; the other facets within the pocket block some lines of sight. In this case, we can compute a visibility map, or "V-Map", that is formed by intersecting the visibility hemisphere for each

V-Maps have numerous applications, particularly in Numerically-Controlled Machining (NC-Machining). Here, a machine head needs to have access to all surfaces on an object. Within a single setup, or orientation of the object, the head will generally not be able to access all surfaces. Since changing setups is time-consuming, it is desirable to find setups that maximize the number of surfaces that are hit. This optimization problem can be solved using the notion of visibility maps.

Non-Convex Polyhedron
A pocket can be seen in the polyhedron
pictured to the right, shown as a shaded
region.

Pocket Finding
A modified 3D convex hull algorithm
can be used to find what facets are in
pockets and group them accordingly.
To the right, the algorithm has
determined three facets reside in a
single pocket, shown in blue.

Compute Visibility Maps
Here we see the "visibility map"
for the blue pocket drawn on the
surface of a sphere. It is formed
by intersecting the hemispheres
of visibility corresponding to each
of the facets in the pocket.

Project to Plane
As a final step, the visibility map is
projected to the plane. Conventional
planar geometric algorithms can
then be used to solve optimization
problems such as the NC-machining
example mentioned above.

A 3-Pocket Example

Shown below is a somewhat more complicated, three pocket polyhedron and the resulting visibility maps.

Non-Convex Polyhedron A pocket can be seen in the polyhedron pictured to the right, shown as a shaded region.
Pocket Finding A modified 3D convex hull algorithm can be used to find what facets are in pockets and group them accordingly. To the right, the algorithm has determined three facets reside in a single pocket, shown in blue.
Compute Visibility Maps Here we see the "visibility map" for the blue pocket drawn on the surface of a sphere. It is formed by intersecting the hemispheres of visibility corresponding to each of the facets in the pocket.
Project to Plane As a final step, the visibility map is projected to the plane. Conventional planar geometric algorithms can then be used to solve optimization problems such as the NC-machining example mentioned above.