A Complete Algorithm for Designing Planar Fixtures
Using Modular Components

Contents

• Abstract
• Introduction
  • Example of Fixtures Using Modular Components
• Previous Work
  • The Existence of Fixtures and Grasps
  • Fixture/Grasp Analysis
  • Fixture/Grasp Synthesis
• The Algorithm
  • Problem Statement
  • Overview of the Algorithm
  • Transformating the Input
  • Generating Candidate Fixtures
    • Enumerating Locator Triplets
    • Identifying Consistent Part Configurations
    • Enumerating Clamp Configurations
  • Flitering the Candidates
  • Ranking the Survivors
  • Algorithm Complexity

Abstract

In this paper we present an implemented algorithm that accepts a polygonal description of the part silhouette, and efficiently constructs the set of all feasible fixture designs that kinematically constrain the part in the plane. Each fixture is comprised of three locators rigidly attached to the lattice and one sliding clamp, and constrains the part without relying on friction.

The algorithm is based on an efficient enumeration of admissible designs that exploits part geometry and a graphical force analysis. The algorithm run time is linear in the number of designs found, which is bounded by a polynomial in the number of part edges and the part's maximal diameter in lattice units. Our review of the literature suggests that this is the first fixturing algorithm that is complete in the sense that it is guaranteed to find all admissible fixture designs for an arbitrary polygonal part silhouette and to identify the optimal fixture relative to an arbitrary quality metric. The algorithm does not consider out-of-plane forces or motions; however, we view this planar result as an essential component of a larger algorithm that solves the 3-d fixture design problem by treating the planar and out-of-plane constraint problems separately. This approach is analogous to the widely used 3-2-1 fixture design heuristic, and appears to be applicable to a broad class of man-made parts.

Introduction

This is partly due to the uncountable set of alternative fixture designs that must be considered in the general case. One way to reduce the number of alternatives is to limit consideration to a small set of components that must be located on a regular lattice structure. Such modular fixturing systems also have the advantage of allowing rapid set-up and changeover for new parts, precision locating on a tightly-toleranced lattice, and a reduced fixture inventory comprised of re-usable components [Mason 1992].

The concept of modular fixturing using a family of interchangeable components was originally developed in England during World War II, and has resulted in a variety of commercially-available modular fixturing systems [Hoffman 1987]. These systems typically include a square lattice of tapped and doweled holes with spacing toleranced to more or less 0.0002 inch and an assortment of precision locating and clamping elements that can be rigidly attached to the lattice using dowel pins or expanding mandrels. Although the lattice and set of modules greatly reduce the number of alternatives, designing a suitable fixture currently requires human intuition and trial-and-error. Designing a new fixture can be time consuming. Furthermore, if the set of alternatives is not systematically explored, the designer may settle upon a suboptimal design or fail to find any acceptable design.

In this paper we present an algorithm for automatically designing a class of modular fixtures. These fixtures constrain all motion of a part in the support plane. Constraint is provided by four point contacts and does not rely on friction. Each fixture in this class uses three round locators, each centered on a lattice point, and one translating clamp that must be attached to the lattice via a pair of unit-spaced holes, thus allowing contact at a variable distance along the principle axes of the lattice. We use the term fixel (fixture element) to refer to either a locator or a clamp and the term fixture to refer to a geometric arrangement of three locators and one clamp on the lattice.

An acceptable fixture design must satisfy several requirements. First, it must fully constrain the part to prevent its motion. We require fixtures to provide form closure, which is a kinematic constraint condition that prevents all motion [Reuleaux 1876]. In addition to constraining the part, the fixture must not interfere with certain geometric regions of the part, perhaps due to cosmetic surfaces or the need to retain clearance for grasping, machining, assembly, or other operations. Thus we define geometric access constraints, which define regions of points that must remain free of fixture components. With these requirements in mind, we say that a fixture is admissible if it provides form closure and obeys the geometric access constraints. In this paper, we further restrict our attention to fixtures where each fixel makes point contact with only one linear edge of the part. Given a part as input, the algorithm efficiently enumerates all admissible fixtures and ranks them according to a user-definable scalar quality measure.

The algorithm begins with a geometric transformation that expands the part edges by the radius of the locators; this allows us to treat the locators as points on the transformed edges. These edges are then trimmed to respect geometric access constraints. We define a locator setup as the combination of three locator positions and a part configuration such that the part contacts all three locators. The algorithm enumerates all locator setups; for each, it identifies the set of all points along the perimeter of the object where an additional contact would provide form closure constraint. This in turn allows us to identify all of the possible form-closure clamp locations for each locator setup; each clamp location defines a unique fixture design. After pruning this set of fixtures by checking for geometric violations such as the clamp body intersecting the part or other fixels, we rank the surviving admissible fixtures based on some scalar metric such as ability to resist an applied force without exerting large contact reaction forces. The resulting fixtures are then returned to the user.

We believe this is the first modular fixture design algorithm that is complete in the sense that it is guaranteed to find an admissible fixture if one exists. It is essential to acknowledge that such a fixture does not always exist; for example, parts that are much smaller than the lattice spacing will have no available fixture design. Other parts for which no fixture exists are considered in [Zhuang 1994].

This algorithm is guaranteed to find the optimal fixture. Since the algorithm constructs the set of all fixture designs possible for a given modular fixturing kit, the algorithm can score the constructed designs according to a user-supplied quality metric, sort the results, and return the fixture with the highest score. The contact-force analysis included in our implementation is one example of such a metric.

There are a number of issues that are not considered by the algorithm. For example, out-of-plane motions and part deformations are both important considerations in some fixturing problems, and these are not addressed by our planar fixture design algorithm. However, the strong analysis and enumerative aspects of our algorithm make it well-suited for use as part of a larger procedure that synthesizes 3-d fixture designs for prismatic parts, which occur in a variety of man-made products. Limitations and possible extensions of this algorithm are discussed further.

Example

A commercial modular fixturing kit is illustrated in (c), comprised of a precisely machined plate with alternating dowel/threaded holes, a set of three round locators, and a manually-actuated clamp. In (d) this kit is represented by a model of the plate, the locators, and the clamp. The clamp is modeled by a polygon delineating the space occupied by the clamp during normal operation; this includes the region swept as the handle is moved from the open to closed position. The clamp model also includes a polygon describing the shape of the clamp plunger, and the plunger travel limits.

For this example, the algorithm returned 97 fixture designs in just over two minutes on a desktop workstation, sorting them according to a quality metric which examines the maximum contact force required to resist an arbitrary unit applied force. Figure 2 shows three of the returned fixture designs. Note that all three fixture designs provide form closure and obey the geometric access constraints.

If we consider a clockwise unit torque applied to the part, we see that the fixture in (a) is superior to the one in (c), where contacts A and B must exert very large contact reaction forces to resist the torque. Our implementation includes these considerations in the metric it uses to rank fixtures; see Quality Metric..

Previous Work

The Existence of Fixtures and Grasps

Reauleaux showed that at least four wrenches are necessary for form closure in the plane [Reuleaux 1876]. Recently, Markenscoff et al. showed that four wrenches are sufficient for any piecewise-smooth compact connected planar body, excluding surfaces of revolution [Markenscoff 1990]. For objects in 3-d space, it is known that seven wrenches are necessary for form closure [Somoff 1900, Lakshminarayana 1978]; Markenscoff et al. showed that seven wrenches are sufficient for polyhedra [Markenscoff 1990].

The above proofs demonstrate the existence of form-closure fixtures where contacts may occur at arbitrary positions in space. In the case of modular fixtures, the locations of contacts are constrained by the modular fixturing kit. Mishra studied the problem under these constraints, and showed that a fixture can always be found for a rectilinear part as long as all edges have length of four or more lattice units [Mishra 1991]. Zhuang, et al. showed that for the modular fixture kit employed in this paper, there exist polygons of arbitrary size for which no fixture design exists [Zhuang 1994].

Fixture/Grasp Analysis

Asada and By showed how to determine whether a given fixture design provides total constraint of a rigid body, as well as loading accessibility before clamping [Asada 1985b]. Our glue gun example is inspired by their example of a power-drill housing, and highlights the similarities and differences between the results. Our paper extends Asada and By's analysis methods by providing an automatic design procedure that considers geometric access constraints and modular assembly constraints in addition to kinematic closure. However, our algorithm considers only three degrees of freedom.

Several grasp quality measures have been proposed based on the smallest contact force necessary to resist applied forces [Cutkosky 1985,li88]. Such a metric can be defined as the solution to an optimization problem [Markenscoff 1989,Trinkle 1992] or geometrically as the radius of the largest sphere that can be embedded inside the wrench convex [Ferrari 1992, Kirkpatrick 1992]. One subtlety is that the wrench space is not homogeneous, and one must take care when comparing forces with torques. In a similar vein, Bausch and Youcef-Toumi developed a method of evaluating the degree of motion constraint imposed by seven fixels contacting a three-dimensional rigid body [Bausch 1990]. The quality metric we describe in Section Quality Metric is similar to Bausch and Youcef-Toumi's metric, except that our metric analyzes planar problems and explicitly considers expected task forces. Unlike some previous geometric quality metrics, our quality metric is not sensitive to the selection of a force/torque scaling factor, which can be a somewhat arbitrary parameter.

Other authors addressed task-specific requirements that must be satisfied by a fixture. Englert reported methods for assessing a fixture design's susceptibility to part deformation, locator wear, and dynamic chatter during machining operations [Englert 1987]. Sakurai later explored the relationship between fixture design, part tolerances, and part deformation in greater detail [Sakurai 1990]. Sakurai also studied the relationship between cutting forces and clamping forces in fixtures that rely on friction for part restraint --- particularly when top-clamps are employed. Lee and Cutkosky extended Sakurai's results by clarifying the relationship between a fixture with top clamps and the friction limit surfaces that were previously developed to study the motion of sliding planar bodies [Lee 1991]. Kim further extended these results by considering whether or not expected force magnitudes would exceed clamp stress limits [Kim 1993]. Other authors reviewed additional practical requirements of fixture designs [Gandhi 1986, Cohen 1991, Chang 1992]. The algorithm we report in this paper is complementary to these results; while we do not present an analysis of part deformation, tolerances, or maximum allowable clamp forces, it is reasonable to expect that these and other considerations could be folded into the quality metric that rates fixture designs. Ultimately, we envision that the synthesis methods of this paper could be combined with enhanced quality metrics to produce a larger system that will select the fixture that best satisfies this myriad of considerations.

Schimmels and Peshkin examined the problem of loading a given fixture using generalized damper compliant motions, and showed that in the absence of friction, a robust loading strategy exists for all deterministic fixture designs [Schimmels 1992]. (The fixture designs returned by our algorithm are always deterministic in their sense.) Later work characterized the conditions where a fixture may be robustly loaded if friction is present [Schimmels 1994]. Schimmels and Peshkin considered only infinitesimal motions, and did not analyze the effect of finite motions such as large rotations. Whether or not a fixture may be reliably loaded is an important aspect of fixture design that we do not treat in this paper; this consideration may be used either to discard fixtures that cannot be loaded robustly, or as a metric to compare fixtures based on their ease of loading.

Fixture/Grasp Synthesis

Mishra, Schwartz, and Sharir described an algorithm for synthesizing form-closure grasps on an arbitrary 2-d or 3-d object; the grasps returned by the algorithm may require up to six contacts for 2-d objects [Mishra 1987]. Nguyen gave an algorithm for finding a set of four (seven) independent regions on the boundary of a polygon (polyhedron) such that a frictionless contact applied to each region is guaranteed to provide form closure [Nguyen 1988]. Such regions are useful because they allow for uncertainty in the part's pose. For three frictional contacts in the plane, Ponce and Faverjon showed that comparable regions on a polygon could be found using linear optimization [Ponce 1993]. These results both allow contacts at arbitrary points in space, and do not consider the constraints imposed by a modular fixture kit.

In the context of planning grasping strategies for lifting an object off a supporting surface, Trinkle and Paul identified jamming regions on an object's boundary, given three point contacts [Trinkle 1990]. These jamming regions are analogous to the form-closure clamping regions produced by our force-sphere analysis, in that they identify portions of the object boundary where an additional contact would lead to a force-closure condition. The form-closure analysis presented in this paper differs from Trinkle and Paul's construction in that it applies to all possible arrangements of contact normals, while Trinkle and Paul's construction addresses the special case where two of the contact normals are parallel.

In the specific context of fixturing, Mani developed a method for designing planar fixtures based on Reuleaux's rotation center analysis techniques [Mani 1988]. Given a polygonal part shape, Mani's procedure identifies all topologically equivalent fixture designs. However, his procedure does not accurately consider the fixel shape or the mapping of the fixture design onto a modular fixture plate. Chou et al. developed a procedure that designs fixtures for prismatic parts using screw algebra, geometric heuristics to place locators at positions that allow easy loading of the part, and a rotation center analysis to place clamps [Chou 1989].As with Mani, they did not consider the constraints imposed by a modular fixture kit. Kim developed a procedure that designs fixtures using top clamps [Kim 1993]. The procedure focuses primarily on placing the top clamps and estimating the required clamping force; lateral locators are only allowed on user-specified orthogonal datum surfaces, which are assumed to be aligned with the hole grid. Our work complements Kim's result, since we generate all possible locator placements for an arbitrary part shape but do not address top clamping. Kim also developed a procedure for designing fixture setups using a vise. In related work, Hayes and Wright developed an expert system for planning machining operations ,[Hayes 1989, Hayes 1990]. This system analyzed the interaction between machined features and constructed a sequence of setup plans that would allow a part to be machined from raw stock while avoiding feature interaction problems (such as drilling into a slanted surface). This system employed a simplified feature-based geometric analysis to design fixtures; it may be possible to extend the scope of this high-level planning system by including the more detailed geometric analysis presented in this paper. Finally, Englert and Sakurai also reported fixture design methods based on geometric heuristics [Englert 1987, Sakurai 1990]; these methods do not have the generality of the algorithm presented here.

Recently, Wallack and Canny reported an algorithm for designing a class of modular fixtures with four round locators on a split lattice that can be closed like a vise [Wallack 1994]. Their algorithm, like ours, takes the part shape as input and enumerates all combinations of fixture elements that achieve form closure. Also, like ours, their algorithm sweeps edges to compute contact conditions and runs in polynomial time. However, the algorithms differ in the construction of the fourth fixel location. In the case of Wallack and Canny's split vise, the third fixel's (x,y) position may not be known until the location of the fourth fixel is chosen, at which time the part pose may be determined. Consequently their algorithm includes another nested loop instead of the direct force-sphere construction we employ. Further, their algorithm does not require a check for interference between the part and the clamp body. The net result of these differences is that their algorithm entails one less factor of n and one more factor of d in its asymptotic complexity (see Section Complexity), while providing the additional capability of designing fixtures with two translating fixels instead of just one.

The Algorithm

Problem Statement

• Parts and locators are rigid solids. A part can be represented with a simple polygon and locators can be represented as circles with identical radii less than half the grid spacing l$(SQRT\; 2)l/2$ on an alternating grid). Thus we do not have to check collisions between locators.
• All contacts are ideal unilateral point constraints. Our analysis treats these contacts as frictionless: the fixtures do not depend on any minimum level of friction.

Input:

• Polygonal part boundary, provided as a list of vertices.
• A set of geometric access constraints, provided as a list of polygons defined in the part coordinate frame.
• Height and width of the fixture plate lattice.
• Locator radius.
• Description of the clamp. This includes a polygon describing the shape of the clamp body, locations of the clamp mounting holes, a polygon describing the shape of the clamp plunger, and its min/max travel limits. The tip of the plunger is assumed to be a circle of the same radius as the locators.
• A quality metric. This is a function that accepts a fixture design and returns a scalar quality measure.

Overview of the Algorithm

1. The input is transformed by growing the part such that the fixels can be treated as ideal points, and the fixture plate lattice is assumed to be infinite.
2. All possible candidate fixture designs are constructed. This is accomplished by enumerating the set of possible locator setups, and then passing the result to a form-closure analysis routine that constructs all of the possible abstract clamp locations for each setup. Each locator setup and clamp location specifies a unique fixture.
3. The set of candidate fixtures are then filtered to remove those that do not obey clamp travel limits, cause collisions with the clamp body or plunger, or do not fit on the finite fixture plate.
4. The resulting fixtures are scored according to the user-specified quality metric, and then sorted in order of decreasing score. The algorithm returns the sorted list of fixtures.

Transforming the Input

Although the expanded boundary has rounded edges corresponding to contacts between a locator and an object vertex, we consider only the linear components of the expanded boundary. We similarly grow the constraint regions by the fixel radius, and then restrict our attention to the subset of the expanded part edges which do not intersect the grown constraints. This will assure that the fixels of all generated fixtures will avoid the access constraint regions. This results in a list of rigidly attached but possibly unconnected linear edges. See Figure 4. We are now free to translate and rotate this group of edges to bring edges into contact with lattice centers.

Generating Candidate Fixtures

Enumerating Locator Triplets

To enumerate all locator triplets, the following steps are repeated for all combinations of three edges, where either all three edges differ, or two of the three edges are identical. For example, (e₁ , e₅ , e₂) and (e₄ , e₇ , e₄) are both valid edge combinations. Order is not significant, so there are {n!/[(3!)(n-3)!]}+n(n-1) such combinations for n edge segments. The second combinatorial is multiplied by two because there are two valid triples for every choice of two distinct edges. Note that we need not consider combinations with three identical edges, since a part with three locators on one edge cannot be held in form closure.

Given a combination of three edges, (e_a , e_b , e_c), we can assume without loss of generality that e_a makes contact with a locator at the origin of the lattice. By translating and rotating e_a about the origin, e_b sweeps out an annulus centered on the origin, with inner diameter equal to the minimum distance between e_a and e_b and outer diameter equal to the maximum distance between e_a and e_b. That is, for any orientation of e_a, as we translate along the extent of e_a, e_b sweeps out a parallelogram. The union of these parallelograms as we rotate e_a forms an annulus. To eliminate equivalent fixtures, we only need to consider the first quadrant of this annulus. See Figure 5.

We now consider each of these second locator positions in turn, and identify all possible positions for the third locator. If the first locator contacts e_a and the second locator contacts e_b, then a third locator in contact with e_c must be pairwise consistent with both e_a and e_b. The exact region swept out by e_c as we maintain contact with the first two locators is difficult to characterize. However, we can easily find an envelope that contains this region by independently considering each pair. That is, the possible locations for e_c with respect to e_a form an annulus around the origin, and the possible locations for e_c with respect to e_b form an annulus around the second locator. Intersecting these annuli provides a conservative bound on the set of grid locations that simultaneously satisfy both constraints.

We can further refine this bound by considering the angular limits for each annulus. This is accomplished by first identifying the angular limits of the part configurations that simultaneously contact the first and second locators, producing a [O_min , O_max] interval of reachable part angles. Then we transform this interval by adding the[B_min , B_max] interval that delineates the minimum and maximum angle attainable by a ray connecting e_a and e_c. The resulting[(O_min+B_min) , (O_max+B_max)] interval describes the set of all possible angles between points on edge e_a and e_c , while e_a and e_b maintain contact with locators 1 and 2. This interval defines a sector of the e_a e_c annulus; points outside this sector are unreachable by e_c. A similar construction produces a sector of the e_b e_c annulus based on the B-interval corresponding to edges e_b and e_c . Intersecting these annular sectors provides a set of candidate locations for the third locator. See Figure 6.

Identifying Consistent Part Configurations

There may be up to two solutions to these equations, corresponding to different poses of the part that permit simultaneous contact with the three chosen locators (see Figure 7). In these cases, we generate two candidate locator setups, one for each pose. In certain geometric situations there are an infinite number of solutions (such as when all three edges are parallel); these cases are discarded because they do not constrain the part to a unique location.

Enumerating Clamp Configurations

To generate the set of form-closure clamp positions for a locator setup, we perform a constraint analysis on the force sphere, a unit sphere centered at the origin of the (F_x , F_y , T/P ) space of planar forces.

This representation was previously described in Brost 1990; see Brost 1991 for implementation details. This space represents both the direction and moment components of a line of force exerted in the plane. For example, Figure 8 shows an example planar force and its corresponding point on the force sphere. Note that if we were performing dynamic analysis, we would choose the part origin and P to correspond to the the part center of mass and radius of gyration; however, in our purely static analysis these may be chosen arbitrarily.

We treat each fixel/edge contact as an ideal unilateral point constraint. Thus each fixel may resist motion by exerting a reaction force in the direction of the inward-pointing contact normal. Figure 9 shows the set of points on the force sphere corresponding to the three contact normals of a typical locator setup. The convex-combination of these points is also shown; this triangle on the force sphere delineates the set of all total contact reaction forces that may be produced by combining forces from all three contacts.

A fixture design provides form closure exactly when the corresponding set of contact normals positively spans the entire force sphere. When this condition is satisfied, combinations of contact reaction forces may produce an arbitrary total reaction force, thus opposing an arbitrary motion. Put another way, if the set of contact normals for a given fixture design span the force sphere, then all possible motions will violate at least one kinematic constraint.

Given a set of three contact normals corresponding to a locator setup, we can directly construct the set of forces that would produce form closure if provided as a fourth contact normal. This is accomplished by forming the convex-combination of the three contact normals on the force sphere, and then centrally projecting this triangle onto the opposite side of the sphere. The resulting negated triangle delineates the set of all forces that will produce form closure. If we can find a clamp position with a contact normal that corresponds to a point strictly in the negated triangle, then this clamp position and the three locators will define a form-closure fixture.

We can directly construct the set of clamp positions that satisfy this condition. We accomplish this by characterizing the set of all contact reaction forces that can be applied by a contact along the perimeter of the grown part. This set of forces is illustrated in Figure 10. Note that the set of all possible contact forces corresponds to a ``zig-zag'' locus of points that encircle the force sphere. Fixel contacts along the edges of the polygon correspond to the vertical edges of the locus; note that as a force moves along an edge, only the torque component of its wrench will vary. Fixel contacts with the vertices of the polygon correspond to the diagonal locus edges. By intersecting the vertical locus edges with the set of possible form-closure forces constructed previously, we can identify the set of all available edge-contact normals that produce form closure for a given locator setup. We then map this set of contact normals back onto the grown part perimeter to identify the regions where a fourth contact point will produce form closure. Finally, we identify the set of possible clamp positions by intersecting the identified regions with the horizontal and vertical edges of the fixture lattice. This construction is illustrated in Figure 11.

Filtering the Candidates

Ranking the Survivors

The final step of the algorithm is to rank the surviving fixtures according to the user-supplied quality metric. A user may then view the top fixtures and apply additional criteria to select a winner.

Our implementation includes a default quality metric that favors fixtures that can resist expected applied forces without generating excessive contact reaction forces. Large contact forces are undesirable because they may deform the part. The effect of fixture geometry on contact reaction force is illustrated in Figure 12. In this figure, a part is held in two different fixtures, both of which provide form closure. Which fixture is better? The answer depends on the forces that will be exerted on the part. For example, if downward forces will be applied to the part, then fixture A is better than fixture B, since fixture B will develop large ``wedging'' forces between the fixels. On the other hand, if clockwise torques will be applied, then fixture B is superior, since fixture A must develop large contact reaction forces to oppose rotation of the part.

As an example, we implemented a quality metric that allows the user to specify a list of expected forces on the part. These forces are represented by a list of force-sphere regions with associated magnitudes that could arise from operations such as machining, assembly, or pallet transfer operations. The quality metric scores each fixture by estimating the maximum contact reaction force required to resist the list of expected applied forces.

The estimated maximum contact reaction force for a given fixture is calculated by visiting each force-sphere region in the applied force list, generating a discrete sampling of points in the region, computing the maximum contact reaction force required to resist each point, scaling the result by the associated magnitude, and taking the maximum of all the resulting contact reaction forces.

Given a particular point p' within a force-sphere region, the maximum contact reaction force may be constructed directly. First the negation of the point -p' is constructed. Since the four force-sphere points corresponding to fixel contact normals positively span the force sphere, the point -p' must lie in a triangle formed by three of the normals, along an edge formed by two normals, or exactly coincide with one normal. In each of these cases, -p' may be expressed as a positive linear combination of the corresponding normals, and the associated scaling factors may be computed directly. These scaling factors determine the magnitude of each contact reaction force in the force space; projecting the resulting scaled vector onto the [F_x ,F_y] plane produces the contact reaction force in the real space. The maximum contact reaction force then corresponds to the force with the largest magnitude sqrt(F²_x+F²_y).

Algorithm Complexity