Communications - January 2013

symmetries and infer part types and parameters based on the symmetry properties. If a part is rotationally symmetric, we mark it as either a rotational gear or axle, use the symmetry axis as the rotation axis, and use the order of symmetry to estimate teeth count and width. If a part is helically symmetric, we mark it as a helical gear, use the symmetry axis as the screw axis, and record the helix pitch. Finally, if a part has discrete translational symmetry, we mark it as a translational gear (i.e., rack), use its symmetry direction as the translation axis, and use the symmetry period to estimate the teeth count and width. Note that the symmetry detection method also handles partial symmetries that are present in parts like variable-speed gears (see Figure 3). If a part exhibits no symmetries and has not been classified by the user as a cam, rod, crank, piston, lever or belt, we assume it to be a fixed support structure.

Cylinders versus cones. Next, we analyze the side profiles of rotational and helical gears to determine whether they are cylindrical or conical, respectively. Specifically, we partition such gears into cap and side regions as follows. Let ai denote the rotation/screw axis of part Pi.

We mark its j-th face as a cap face if its normal nj is parallel to the part’s rotational/screw axis, such that |nj · ai| ≈ 1, otherwise we mark it as a side face. We then build connected components of faces with the same labels, and discard components with only few faces as members (see Figure 4). Subsequently, we fit least squares cylinders and cones to the side regions and classify parts with low residual error as cylindrical or conical, respectively.

sharp edge loops. Finally, we use sharp edge loops, which are 1D curves defined by sharp creases on a part, to determine additional part parameters for rotationally or helically symmetric parts, as well as cams, cranks, levers, and fixed support structures. We start by marking all mesh edges whose adjacent faces are close to orthogonal (i.e., dihedral angle in 90° ± 30° in our implementation) as sharp (see also Gal et al. 7 and Mehra et al. 21). We then partition the mesh into segments separated by sharp edges, discard very small segments (less than 10 triangles in our tests), and label the boundary loops of the remaining segments as sharp edge loops. Next, we identify all the sharp edge loops that are (roughly) circular by fitting (in a least squares sense) circles to all the loops and selecting the ones with low residual errors. For rotationally and

figure 4. for rotationally and helically symmetric parts, we use their symmetry axes to partition the parts into cap- and side-regions. We fit cylinders or cones to the side regions to determine their profile types and extract sharp edge loops to estimate part attributes like radii.

helically symmetric parts, we use the minimum and maximum radii of the circular loops as estimates for the inner and outer radii of the parts (e.g., Figure 4-left shows the outer radius of a cylindrical gear).

For fixed support structures, a group of circular loops with a consistent orientation often indicates a potential axis of rotation for a part that docks with the fixed structure. Such clusters of loops also indicate potential rotation axes for cams, cranks, and levers. We cluster circular loops in two stages (see Figure 5): For each loop we compute the normal of the plane that contains the fitted circle, which we call the circle axis, and cluster loops with similar circle axes. Then, we partition each cluster based on the projection of the circle centers along a representative circle axis for that cluster. The resulting clusters represent groups of circular loops with roughly parallel circle axes that are close to one another. We record the representative circle axis for each cluster as a potential rotation axis.

4. 2. interaction analysis

To build the edges of the interaction graph and estimate their parameters, we: (i) compute the topology of the interaction graph based on the contact relationships between part pairs; (ii) classify the type of mechanical interaction at each contact (i.e., how motion is transferred from one part to another); and (iii) compute the motion of the assembly. (i) Contact detection. We use the contact relationships between parts to determine the topology of the interaction graph. Following the approach of Agrawala et al. 1, we consider each pair of parts (Pi, Pj) in the assembly and compute the closest distance between them. If this distance is less than a threshold a, we consider the parts to be in contact, and we add an edge eij between the nodes ni and nj in the interaction graph. We set a to 0.1% of the diagonal of the assembly bounding box in our experiments.

As an assembly moves, its contact relationships evolve, that is, edges eij in the interaction graph may appear or disappear over time (see Figure 10c). We detect such contact changes using a space–time analysis. Suppose at time t, two parts Pi and Pj are in contact and we have identified their interaction type (see below). On the basis of this information, we estimate their relative motion parameters, compute their positions at subsequent times t + D, t + 2D, etc., and

figure 5. We detect circular sharp edge feature loops on a part (left) and cluster the loops based on the orientations of their circle axes (middle) and the projections of the circle centers onto these axes (middle-inset). such clusters represent groups of nearby loops with parallel axes, shown here in different colors (right).