# US 2016/0124425 A1 · System and Method For Locating Clamping Points For A Part To Be Manufactured Through Computer Numerical Control (CNC) Machining Operations With The Aid Of A Digital Computer

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2016/0124425 A1
- Document ID: US20160124425A1
- Status: Published application
- Kind: A1
- Application number: 14/993,004
- Filed: 2016-01-11
- Published: 2016-05-05
- Earliest claimed: 2013-03-15
- Assignees: Palo Alto Research Center Incorporated
- Applicants: Palo Alto Research Center Incorporated
- Inventors: Saigopal Nelaturi; Arvind Rangarajan; Tolga Kurtoglu; Christian Fritz
- Web page: https://patentgrep.com/patent/US20160124425A1

## CPC

- G05B 19/4097: characterised by using design data to control NC machines, e.g. CAD/CAM (G05B19/4093 takes precedence)
- G06F 30/00: Computer-aided design [CAD]
- G05B 2219/35025: Design and manufacture jig
- G05B 2219/35043: Tool, fixture design
- G05B 2219/35134: 3-D cad-cam
- G05B 2219/35218: From cad data derive fixture configuration and assembly program
- G05B 2219/36315: Library for shapes of tool holders, fixtures, chucks
- G05B 2219/49123: Simulation of clamping workpiece, modeling fixture and workpiece
- G05B 2219/50125: Configurable fixture, jig
- G05B: CONTROL OR REGULATING SYSTEMS IN GENERAL; FUNCTIONAL ELEMENTS OF SUCH SYSTEMS; MONITORING OR TESTING ARRANGEMENTS FOR SUCH SYSTEMS OR ELEMENTS (systems for controlling or regulating non-electric variables G05D; systems for regulating electric or magnetic variables G05F; control devices or systems insofar as characterised by mechanical features only G05G)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Automated fixture layout is approached in two distinct stages. First, the spatial locations of clamping points on the work piece are determined to ensure immobility of the fixtured part under any infinitesimal perturbation. Second, spatial locations are matched against a user-specified library of reconfigurable clamps to synthesize a valid fixture layout or configuration that includes clamps that are accessible and collision free. The spatial locations matching during the second stage can be the same spatial locations chosen in the first stage to ensure immobility, or a different set of spatial locations.

## Claims

### Claim 1

A system for locating clamping points for a part to be manufactured through computer numerical control (CNC) machining operations with the aid of a digital computer, comprising:
a storage of digital information comprising:
a model of a part to be machined, the model defining the part's surfaces and a constraint volume; and
parameters for a CNC machining tool, the parameters comprising a plurality of orientations at which the tool is able to longitudinally traverse a rotating cutting edge; and
a computer comprising a processor and memory operatively coupled to the storage, comprising:
an identification module configured to identify fixturable regions comprising locations on the part's surfaces that cannot be approached by either the CNC tool in motion or a clamp;
an evaluation module configured to evaluate reachable locations comprising collisions with the CNC tool through ray intersections from locations in the fixturable regions and sweeps of the CNC tool in each approach from the locations;
a generator module configured to generate fixturable locations by finding form closure based on those reachable locations on the part's surface that do not result in a ray intersection; and
a programming module configured to program the CNC tool with process plans downloaded by the computer and comprising machining operations by the CNC tool with the part fixtured using the fixturable locations,
wherein the CNC tool operates per the machining operations in the downloaded process plans by machining off the removal volumes through longitudinal traversals of the rotating cutting edge over the surfaces of the part.

### Claim 2 (depends on 1)

A system according to claim 1, further comprising:
the storage further comprising binary space partitioning trees formed of the part's surfaces and the part's constraint volume; and the computer further comprising:
a candidate module configured to obtain a candidate set of the fixturable locations by sampling the boundary along the part's surfaces; and
a query module configured to query whether a ray shot from a location on the part's boundary along a triangle normal will intersect the model, and to discard the triangle if the ray indicates an intersection between the ray and the constraint volume.

### Claim 3 (depends on 2)

A system according to claim 2, further comprising:
the storage representing the part boundary as centroids of triangles formed in a mesh.

### Claim 4 (depends on 1)

A system according to claim 1, further comprising:
the storage denoting a position and unit inward surface normal at the reachable locations; and
the computer further comprising:
a clamp module configured to assume that a clamp located at each of the reachable locations exerts a known force along a vector from the unit inward surface normal at the reachable location; and
a mapping module configured to determine a maximum possible non-slipping applied force at each of the reachable locations, and to map the applied force to a wrench at a triangle normal for each of the reachable locations.

### Claim 5 (depends on 4)

A system according to claim 4, wherein the clamp at reachable location i exerts a force fi along ni, where pi and ni comprise vectors that denote the position and unit inward surface normal at the reachable locations indexed by I, such that, in the presence of friction, assuming a Coulomb model and a coefficient of friction μ, a non-slipping tangential force fij along a tangent direction j at location i satisfies the expression:
∥fij∥≦∥μfi∥
and the net non-slipping force acting at any point contact location is:
∑
j

(
f
ij
+
f
i
)
wherein the limit points of the set of non-slipping tangent forces lie on a circle of radius ∥μfi∥ and the set fij+fi of resultant vectors form a cone that is called the Coulomb friction cone.

### Claim 6 (depends on 5)

A system according to claim 5, further comprising:
the computer further comprising a sampling module configured to sample the tangent forces at discrete orientations on a circle that represents the friction cone as a polyhedron, such that the maximum possible non-slipping force at any contact location is {circumflex over (f)}i=Σjfi.

### Claim 7 (depends on 6)

A system according to claim 6, further comprising:
the computer further comprising a mapping module configured to map each applied force {circumflex over (f)}i to a wrench by the triangle defined by the Plucker coordinates wi={circumflex over (f)}i,pi×{circumflex over (f)}i).

### Claim 8 (depends on 7)

A system according to claim 7, further comprising:
the mapping module further configured to map wrenches to indices for the reachable location using a hash function comprising at least one of:
a wrench module configured to apply a wrench step function v: 6→6 obtained by applying the Heaviside step function to each component wk of a wrench, such that:
v(wi)={Heaviside(w1),Heaviside(w2), . . . ,Heaviside(w6)};
a concatenation module configured to concatenate the components of v(wi) into a six-bit binary string; and
a conversion module configured to convert the six-bit binary string to identify the index for a bin for the reachable location into which the wrench was hashed.

### Claim 9 (depends on 8)

A system according to claim 8, further comprising:
the computer further comprising a randomized algorithm module configured to choose six extreme points at random and testing for linear independence of the corresponding vectors by constructing a wrench matrix whose columns are the vectors corresponding to the extreme points, to iteratively search the bins exclusive of those bins from which the extreme points were randomly selected to check whether a form closure configuration exists, and if form closure exists, to return the reachable locations and the normals.

### Claim 10 (depends on 8)

A system according to claim 8, further comprising the steps of:
the computer further comprising a separating halfspaces algorithm configured to generate the indices corresponding to bins on H+ and H− when H is one of the six principal hyperplanes, where a convex hull Hulle of extreme points can be asserted to have elements on either side of any hyperplane passing through the origin if the convex hull Hullw of wrench points has the property of form closure and every hyperplane H passing through the origin separates 6 can be separated into disjoint halfspaces H+ and H− defined by the hyperplane, and, if the wrench matrix can be generated using bins on one half of a separating hyperplane, to find a final form closure location among the other bins on the other half of the hyperplane.

### Claim 11

A method for locating clamping points for a part to be manufactured through computer numerical control (CNC) machining operations with the aid of a digital computer, comprising the steps of:
providing a computer comprising a processor, memory and storage with a model of a part to be machined, the model defining the part's surfaces and a constraint volume;
providing the computer with parameters for a CNC machining tool, the parameters comprising a plurality of orientations at which the tool is able to longitudinally traverse a rotating cutting edge;
identifying with the computer fixturable regions comprising locations on the part's surfaces that cannot be approached by either the CNC tool in motion or a clamp;
evaluating reachable locations with the computer comprising collisions with the CNC tool through ray intersections from locations in the fixturable regions and sweeps of the CNC tool in each approach from the locations;
generating fixturable locations by finding form closure with the computer based on those reachable locations on the part's surface that do not result in a ray intersection;
programming the CNC tool with process plans downloaded by the computer and comprising machining operations by the CNC tool with the part fixtured using the fixturable locations; and
operating the CNC tool per the machining operations in the downloaded process plans by machining off the removal volumes through longitudinal traversals of the rotating cutting edge over the surfaces of the part.

### Claim 12 (depends on 11)

A method according to claim 11, further comprising the steps of:
forming with the computer binary space partitioning trees of the part's surfaces and the part's constraint volume;
obtaining a candidate set of the fixturable locations with the computer by sampling the boundary along the part's surfaces;
querying with the computer whether a ray shot from a location on the part's boundary along a triangle normal will intersect the model; and
discarding the triangle with the computer if the ray indicates an intersection between the ray and the constraint volume.

### Claim 13 (depends on 12)

A method according to claim 12, further comprising the step of:
representing the part boundary with the computer as centroids of triangles formed in a mesh.

### Claim 14 (depends on 11)

A method according to claim 11, further comprising the steps of:
denoting with the computer a position and unit inward surface normal at the reachable locations;
assuming with the computer that a clamp located at each of the reachable locations exerts a known force along a vector from the unit inward surface normal at the reachable location;
determining with the computer a maximum possible non-slipping applied force at each of the reachable locations; and
mapping with the computer the applied force to a wrench at a triangle normal for each of the reachable locations.

### Claim 15 (depends on 14)

A method according to claim 14, wherein the clamp at reachable location i exerts a force fi along ni, where pi and ni comprise vectors that denote the position and unit inward surface normal at the reachable locations indexed by I, such that, in the presence of friction, assuming a Coulomb model and a coefficient of friction μ, a non-slipping tangential force fij along a tangent direction j at location i satisfies the expression:
∥fij∥≦∥μfi∥
and the net non-slipping force acting at any point contact location is:
∑
j

(
f
ij
+
f
i
)
wherein the limit points of the set of non-slipping tangent forces lie on a circle of radius ∥μfi∥ and the set fij+fi of resultant vectors form a cone that is called the Coulomb friction cone.

### Claim 16 (depends on 15)

A method according to claim 15, further comprising the steps of:
sampling with the computer the tangent forces at discrete orientations on a circle that represents the friction cone as a polyhedron, such that the maximum possible non-slipping force at any contact location is {circumflex over (f)}i=Σjfi.

### Claim 17 (depends on 16)

A method according to claim 16, further comprising the step of:
mapping with the computer each applied force {circumflex over (f)}i to a wrench by the triangle defined by the Plücker coordinates wi=({circumflex over (f)}i,pi×{circumflex over (f)}i).

### Claim 18 (depends on 17)

A method according to claim 17, further comprising the step of:
mapping with the computer wrenches to indices for the reachable location using a hash function comprising at least one of the steps of:
applying a wrench step function v: 6→6 obtained by applying the Heaviside step function to each component wk of a wrench, such that:
v(wi)={Heaviside(w1),Heaviside(w2), . . . ,Heaviside(w6)};
concatenating the components of v(wi) into a six-bit binary string; and
converting the six-bit binary string to identify the index for a bin for the reachable location into which the wrench was hashed.

### Claim 19 (depends on 18)

A method according to claim 18, further comprising the steps of:
choosing with the computer six extreme points at random and testing for linear independence of the corresponding vectors by constructing a wrench matrix whose columns are the vectors corresponding to the extreme points;
iteratively searching with the computer the bins exclusive of those bins from which the extreme points were randomly selected to check whether a form closure configuration exists;
if form closure exists, returning with the computer the reachable locations and the normals.

### Claim 20 (depends on 18)

A method according to claim 18, further comprising the steps of:
generating with the computer the indices corresponding to bins on H+ and H− when H is one of the six principal hyperplanes, where a convex hull Hulle of extreme points can be asserted to have elements on either side of any hyperplane passing through the origin if the convex hull Hullw of wrench points has the property of form closure and every hyperplane H passing through the origin separates 6 can be separated into disjoint halfspaces H+ and H− defined by the hyperplane; and
if the wrench matrix can be generated with the computer using bins on one half of a separating hyperplane, finding a final form closure location among the other bins on the other half of the hyperplane.