|
Nesting of 2D Polygonal
Parts using a Shape Reasoning Heuristic
Project done in CAED (ME451)
under Dr. Amitabha Mukerjee
Indian Institute of Technology Kanpur
|
Introduction
The general algorithm of fitting 2D objects into a given
empty resource is NP-Complete. NP - this means that to generate
the best solution we may need time which varies exponentially in proportion
to the number of parts being fitted. Complete means, given a solution
of the problem, we can verify it in polynomial time. So NP-Complete problem
are difficult to solve, but it is easy to verify if the solution
is correct. Therefore we use heuristics to solve such problems to give
us good solutions which of course might not be optimal.
A technique is outlined here for the allocation or nesting
of irregular parts into arbitrarily shaped containers. Placements are
generated by matching complementary shapes between the unplaced parts and
the remaining areas of the stock material. The part and resource profiles
are characterized by varying levels of detail using geometric features
at each stage of processing to intelligently select parts of the resource.
Numerous criteria are available for selecting the best part, orienting
it, and placing it on the resource. One technique used is to search for
complementary shapes existing between the profiles of the unplaced parts,
and the remaining usable stock. Fine detail is ignored and more generic
characteristic shapes or features are used to judge the quality of the
actual match between two profiles.
This technique has many uses. A few of them are
Finding cut patterns in garment manufacture so that minimum
cloth is wasted
Cutting blanks out of metal sheets
Fitting electronic component on chips: the closer they
are packed, faster they can communicate with each other.
Technicalities
Features can be described by the two adjacent edges
and the included angle. A third side can also be added to have concept
of protrusions and pockets. It has been found, it is necessary only to
extract convex features from parts to match with concave features from
remaining stock material (or void). By simplifying the object profile,
a hierarchical group of features describing both miniscule and large scale
characteristics of a profile can be constructed. Void and Object profile
is simplified by
- SCR (Small scale Complexity Reduction)
- which eliminates inconsequential shallows, ridges, and
fillets by examining each profile vertex and its two adjacent sides.
- LSRD (Large Scale Resource Division)
- which eliminates complexity at more global level, splitting
the void at locations of necking and evaluating the usefulness of the regions
based on their shape and size. The objective here is to maintain larger
useful areas, while eliminating smaller unusable ones where the likelihood
of successful placement of parts is minimal.
Differing levels of details can be achieved by varying
the maximum allowable height of the irregularities. Once the primary side
of a match is selected, the way in which the two features mesh or fit together
is ascertained - known as the align type. Because features are only
an approximate representation of the actual profiles, the initial part
placement indicated by the align type is only an estimate. For those placements
residing completely within the void, further refinement is achieved by
translating the part as far as possible in a predefined direction, calculated
from the angles of the void feature.
To summarize
Determine the align type for the associated features.
Position the part using the align type and insure it
falls totally within the remaining resource.
Shift the part as far as possible within the void and
in the direction specified by the align type. To determine the quality
of match, a matching index is generated for each possible alignment of
a pair of features (one feature of a void and the other from the object).
This index is a combination of three basic difference measures between
the part and the void feature.
Implementation
- Preprocess the parts to extract features at varying levels
of details.
- Simplify the remaining resource in varying levels of
detail, extract features.
- Generate matching indices for all possible feature combinations
from part and voids.
- Go from most favourable to least favourable index, and
see if placement is possible.
- Among all the parts satisfying 4 choose that object
which wastes the minimum space.
- If parts remain, goto 2 else generate solution
and end.
Our Approach
We implemented the above algorithm which did
generation of features of both the stock and the parts.
The feature consist of two adjacent sides with the angle included.
built a match index which for each stock feature, for
each part feature, found out the index value if the part could potentially
be placed ( if the feature angle of the part is less than that of the stock,
and also if the part is placed, it doesnot intersect with the filled stock
, we say the part can be placed). Here extensive feature matching was required.
Feature matching requires translating of the part feature to the stock
feature being considered and then rotating the part so as to align one
of the edges with the stock feature. The index value of the match reflects
the fitness of the match. We used the sum of following two parameters
to find out the index value
- the normalized angular difference*0.7
- the normalized length difference of the aligned edges*0.3
After the index was built (which incidentally is the
most computive intensive operation of the algorithm), the best match (which
had the maximum index value) was chosen as the next part to be fitted.
The part was then placed (effectively it is the union of the part and the
stock under consideration) Now the stock features were again generated,
match index built ... till all parts were placed or more parts could not
be placed.
We didnot implement the resource (remaining stock) simplification.
The input to our program is through a file describing the objects to be placed as well the empty stock. A few examples follow.
|
Figure 1 showing placement of 3 parts
|
The big "U" in white lines is the void. All the three parts were defined at the lower left corner. The boundary lines of parts in white show the intermediate steps where they were unsuccesfully tried to be placed. The final positions are shown in colour.
|
Figure 2 showing placement of 5 parts.
|
Note how the square fits into the cavity of the arrow. Also see how the inverted "W" tilts to avoid overlap.
|
Figure 3
|
In Figure 4 below, the left limb of the stock overhangs.
|
Figure 4
|
References
Lamousin, H. Waggenspack, W.N.,Nesting of two-dimensional irregular parts using a shape reasoning heuristic.,Computer-Aided Design, Vol. 29, No. 3, pp 221-238, 1997.