Browse Prior Art Database

Determining the Three Dimensional Convex Hull of a Polyhedron

IP.com Disclosure Number: IPCOM000085345D
Original Publication Date: 1976-Mar-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 3 page(s) / 47K

Publishing Venue

IBM

Related People

Appel, A: AUTHOR [+2]

Abstract

In three-dimensional computer graphics, there are several uses for the convex hull of an object. The representation can be used for determining strategies for the recognition of three-dimensional objects, for determining how to pickup objects, and to test in model form for rest positions of an object.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Determining the Three Dimensional Convex Hull of a Polyhedron

In three-dimensional computer graphics, there are several uses for the convex hull of an object. The representation can be used for determining strategies for the recognition of three-dimensional objects, for determining how to pickup objects, and to test in model form for rest positions of an object.

The algorithm to be described aims to find the edges of the convex hull. Identifying the edges of the three-dimensional convex hull seems to be most appealing for two reasons: (1) should the edges be known, vertex points on the convex hull can be identified and with small effort the topological map can be constructed; and (2) the probability of wasteful testing for convex edges is less than the probability of wasteful testing for convex planes.

The basic algorithm is as follows: (1) Test all possible pair combinations of the vertex points on the object to identify convex edges. The test for a convex edge is based on the property that if all points are projected parallel to this edge, the edge projects as a convex point on the polygon image. Fig. 1 shows a determination of convex edges from a projection plane perpendicular to the edges. The point projection of lines (1,2), (5,6), (7,8), and (9,10) are convex points hence these lines are convex edges. The point projection of line (3,4) is not a convex point and this line is not a convex edge.

No convex edges are colinear.

(2) Form loops in three-dimensional space of convex edges. Each edge must be used twice and all the edges used in any particular loop must lie on the same convex plane. A convex plane has the property that all points of the object in three-dimensional space lie in the plane or are only on one side of this plane.

A typical convex hull and its convex edge list is...