Constraint Solving Strategies With Graphics Hardware

Graphics hardware is cheap but incredibly powerful. This has been recognized and it has been argued that the use of graphics hardware for geometric computations and equation solving constitutes a convergence of the GPU and the CPU. 

Intel's Larrabee platform is an example of the convergence where the evolutionary path begins with the CPU and makes its way to a capable graphics coprocessor.  That avoids specific idiosyncracies the are found in today's GP-GPU and are related to the memory structure of graphics cards.  The examples below have been computed on the GPU as the Larrabee platform is not yet available.  However, the types of computation involved here will be compared with a like Larrabee implementation.  We expect that to be a close race, especially when problem scale and accuracy of solutions is taken into account.

The following examples show a progression from simpler to more advanced GPU techniques and demonstrate that complex geometric and algebraic computations can be done by the GPU in a fraction of a second, a speedup of several orders of magnitude over previously known algorithms.


Distance Functions

The construction of circles with unknown center and radius is a fundamental problem in geometric constraint solving. Owing to the many geometric configurations possible with such constructions, the underlying algebraic problem is complex and difficult to solve. This difficulty increases when allowing general shape elements that anchor the construction constraints on the circles. Such shape elements include conic arcs and Bezier curves.

The algebraic problem can be reduced to distance function computations for which good GPU techniques are available. The following image illustrates this. Here, we are given three curves, a circle and two ezier curves, colored red, green and blue. The colored regions indicate areas of the plane closer to one than the other two curves. The white curves separating the regions are the so-called voronoi edges and are equidistance curves. Accordingly, their intersection is a point equidistant from all three shapes, thus is teh center of a circle that is tangent to the given shapes.

Conventional algorithms computing the equidistance curves are rather complicated and comparatively ineficient. However, graphics hardware can easily render the regions and determine the equidistance curves when considering the distance map as three-dimensional graph. The resulting speedup is several orders of magnitude.


Medial Axis

Complicated shapes have complicated distance functions and there it is possible that certain points are equidistant from two different parts of the shape. Such points comprise the Medial Axis of the shape, and it is of interest to compute it.  The medial axis has applications in injection molding including mold design, in mesh generation, computer vision, and in other areas.  Again, it is simple to understand the medial axis and complicated to compute it on uniprocessors.  Graphics hardware changes that, and the example below demonstrates that the medial axis of a complex curve is easy to compute as the ridge lines of the distance function.  The extracted medial axis is shown below, with red the shape input, and green the medial axis output.


Configuration Space Constructs

Sometimes the constraints from which to determine an unknown circle involve four geometric entities whose relative position is not known completely. Typically, the four elements are two pairs where one pair may move as rigid structure in relation to the other pair. The relative motion may be a translation or a rotation. To solve this problem, where the solution determines both the circle and the relative position of the two pairs, we need to generalize the distance function to a function that captures the relevant distances for every possible position of the pair. Such generalizations are analogous to configuration space structures familiar from motion planning.

The figure below shows and example of solving this problem when there is a translational degree of freedom. The algebraic problem is practically intractable, but using the graphics hardware, the problem can be solved at interactive speeds. Two solutions are shown.

The first image shows the problem formulation and where the two solutions are to be expected.  The circles are to be tangent to the red line, the light blue circle and the red circle.  Their centers are to lie on the dark blue circle.  Neither the exact center location nor the circle radii are known beforehand.  The red line and circle are allowed to move rigidly along the direction indicated by the arrow.  This situation may arise when a partially solved sub problem in the constraint structure has to be accounted for. 

The following two images demonstrate the two solutions.

Problem Formulation: Circles are to be found that are centered on the dark blue circle and tangent to the other two circles and the line.  The relative position of the red objects may change by a translation along the direction shown by the arrow.

First Solution

Second Solution