APPROACH

Field of the Invention

The present invention relates to a computer implemented method for segmenting a ship hull into small plates and packing them into bins.

Background of the Invention

A ship hull is a large structure and cannot be produced at once. Therefore, it has to be decomposed into producible hull plates and manufactured individually, and then assembled and welded to produce the hull. These producible hull plates are flattened to 2D, called flattened hull plates, and produced using flat steel plates with specific widths and heights. Shapes of the producible hull plates are obtained using designer's experience. Flattened hull plates are produced from flat steel plates while minimizing the waste of these steel plates. 2D bin packing algorithm is the mainly utilized in the literature for this.

In 2D bin packing algorithm, size or shape of the flattened hull plates are fixed. Starting with a fixed size of these hull plates, waste of flat steel plates is minimized. Here is the problem definition for the 2D bin packing problem (see Fig. 11):

- Packing n rectangular items (flattened hull plates) into identical bins (flat steel plates) with height H and width W.

- Each rectangle j is defined by a width w_ j and height h_ j where w_ j < W and h_ j < H forj = 1, ...,n. - No overlapping is allowed. All rectangles must be entirely contained within the bin.

- Goal: Minimize the number of bins (i.e., waste of bins). Summary of the Invention

The objective of the present invention is to provide a computer implemented method for minimizing the number of used bins much more than the existing techniques using the 2D bin packing approach.

In the present invention, the formulation of 2D bin packing (2Dbp) problem is modified which can minimize the number of bins more than the original formulation of the 2Dbp technique. Here is the proposed 2D bin packing problem (see Fig. 12):

- Non-rectangular quad (or triangular) items can be both packed.

- Items can have greater size than those of bins.

- No overlapping is allowed. All rectangles must be entirely contained within the bin.

- Goal: Packing items into bins by minimizing the bin waste.

Detailed Description of the Invention

A computer implemented method developed to fulfill the objectives of the present invention is illustrated in the accompanying figures, in which:

Figure 1 shows the segmentation process of a ship hull into mega blocks and sub- meshes.

Figure 2 shows the formation process of bin templates.

Figure 3 shows the covering process of a flattened block with bin templates. Figure 4 shows the formation process of combined item.

Figure 5 shows the combined items for a mega block. Figure 6 shows the generation of candidate points and regions.

Figure 7 shows the generation of combined items orientations.

Figure 8 shows the placement of combined items on bins.

Figure 9 shows generation of candidate items from exceeding items.

Figure 10 shows the results using conventional 2D bin packing techniques (a) and the proposed approach (b).

Figure 11 shows the conventional 2D bin packing problem.

Figure 12 shows the proposed 2D bin packing formulation. The components shown in the figures are each given reference numbers as follows:

1. Ship Hull

2. Mega block

3. Sub-mesh

4. Flattened block

5. Flattened block boundary

6. User constraint

7. Bin

8. Bin template

9. Row

10. Column

11. Combined bin template

12. Combined item

13. Boundary bin template

14. Trimmed item

15. Inner bin template

16. Inner item

17. Candidate region

18. Candidate point

19. Main point 20. Packed portion

21. Remaining portion

22. Exceeding item

23. Concave vertices

24. First point

25. Second point

Vp. First vector

Vn. Second vector

VH. Horizontal (X) direction

vv. Vertical (Y) direction

Pp. Previous vertex

Pc. Closest concave vertex

Pn. Next vertex

Pi. First polygon

P ₂ . Second polygon

C1-C8. Candidate items

A computer implemented method for segmenting a ship hull (1) into the small plates and packing them into bins (7) within a computer system comprising a processor, a database, a user interface and a monitor, the method comprising the steps of;

accessing in the database a three dimensional ship hull (1) consisting of mega blocks (2);

receiving from the user interface user constraints (6) corresponding to boundaries of the mega blocks (2) and sub-meshes (3) of the ship hull (1); segmenting the ship hull (1) into three dimensional mega blocks (2) and sub- meshes (3) respectively;

obtaining flattened blocks (4) by flattening the three dimensional sub-meshes (3) to two dimensional;

- obtaining a plurality of bin templates (8) from a bin (7); covering the flattened blocks (4) with the bin templates (8) without overlapping each other until when there is no intersection between the placed bin templates (8) and the flattened blocks (4);

generating a plurality of combined bin templates (11) for covering the overlapping regions between the flattened blocks (4) and boundary bin templates (13) having partially intersection with the flattened blocks (4), wherein the combined bin templates (11) are generated by the sub-steps of; o for each boundary bin template (13), computing an overlapping region between the boundary bin template (13) and the flattened block (4);

o finding an enclosing region of each overlapping region;

o generating combined bin templates (11) by merging the each enclosing region with its a neighboring enclosing region or an inner item (16) covered by a bin template (8) having no intersection with any overlapping region,

- replacing the boundary bin templates (13) with the combined bin templates

(I D;

packing plates of flattened blocks (4) covered with the bin templates (8) and combined bin templates (11), into bins (7);

displaying the used bins (7) with their waste on the monitor.

The computer implemented method is conducted within a personal computer and a laptop or a tablet PC which comprises; a processor, a microprocessor, microcontroller or FPGA, etc. for processing the steps of the method; a database or a memory, such as a hard disk, a CD, a flash disk or a remote database connected to the computer via a communication network, etc. for storing data such as a ship hull (1) represented using triangular mesh model and mega blocks (2) whose union is the given ship hull (1); a user interface, such as a mouse, a keyboard, a touchscreen keyboard... for receiving user inputs such as boundaries of both the mega blocks (2) and the sub-meshes (3); and a monitor (such as an LCD monitor, touchscreen display, etc.) for displaying packing processes and/or results. The proposed method is proper to be utilized for the ship hull (1) production problem. The geometrical characteristics of the items (the hull plates) to be packed into bins (7) should be listed as follows:

- Maximum length constraint: Since items with larger edge lengths are difficult to bend and transport, maximum edge length of an item should be smaller than

Imax.

- Minimum length constraint: Each edge length of an item should be greater than Imin since items with smaller edge lengths are difficult to weld and bend.

- Minimum angle constraint: The angle between consecutive edges of an item should be greater than alphamin since items with smaller angles of alphamin are difficult to weld.

The steps of the computer implemented method can be grouped into three main steps;

Preprocessing Step.

Combined Item Formation Step.

Split and Pack Approach Step. In the "Preprocessing step "; the processor accessing the ship hull (1) consisting of mega blocks (2) in the database/memory and segment them into mega blocks (2) and several sub-meshes (3) whose boundaries are defined by a design or manufacturing engineer by means of the user interface (Fig. 1). After segmenting the ship hull (1) into sub-meshes (3), the each sub-mesh (3) is flattened to two dimensional (2D) and will be packed using a modified 2D bin packing approach in the next steps.

In the "Combined Item Formation step", firstly, bin templates (8) are obtained which will be utilized in order to initially cover the flattened blocks (4) and then these bin templates (8) will be utilized to form combined bin templates (11). The strategy to obtain bin templates (8) is summarized here. Bin templates (8) with length "/" and width "w " are generated from bins (7) with length "L" and width "W", where the length and width of bin templates (8) are less than length and width of the bin (7) (I < = L and w < = W). Starting from a bin (7) (Fig. 2a), horizontal and vertical cuts are generated (Fig. 2b). These cuts divide the bin (7) into equally- spaced regions each of which will be a bin template (8) as seen in Fig. 2c. To compute the length and the width "w ", the number of required cuts in horizontal and vertical directions (nh and nv) are first determined and are calculated as follows: nh=f(W/lmax) (Equation 1) nv = floor(L/lmax) (Equation 2) where floor(x) maps a real number x to the largest previous integer. Finally, the length "/" and the width "w " are computed using the nh and nv:

/ = L/(nv + 1) (Equation 3) w = W/(nh + 1) (Equation 4)

After obtaining the bin templates (8), initial covering of the flattened blocks (4) with the bin templates (8) is realized. Fig. 3 shows a flattened block (4), the same flattened block (4) covered with the generated bin templates (8) and combined bin templates (11) respectively. Bin templates (8) are placed on the flattened block (4) without overlapping each other and a 2D regular grid consisting of these bin templates (8) with uniform grid spacing in X or Y directions is obtained. Starting from a first vertex (initial vertex) of the flattened block (4), for each row (9) or columns (10), the bin templates (8) are placed to the first vertex to a second vertex which is in the opposite side of the first vertex, until one edge of the placed bin template (8) passes an edge of flattened block' s (4) bounding box. In one embodiment of the invention, starting from the left most vertex (initial vertex) of the flattened block (4), bin templates (8) are placed from left to right (i.e., in positive X direction). By doing so, a single row (9) of the flattened block (4) is covered with the bin templates (8). Upper/lower rows (9) of the flattened block (4) are similarly covered by moving the initial vertex by the width (w) of the bin template (8) in positive/negative Y directions. Covering the flattened block (4) with the bin templates (8) (in positive/negative Y directions) stops when there is no intersection between the placed bin templates (8) and the Flattened block (4). Finally, bin templates (8) having partially intersection with the flattened block (4) are removed; those that intersect with the flattened block boundary (5) are marked as boundary bin templates (13), and those without intersection with the boundary are marked as inner bin templates (15). Also, the boundary bin templates (13), the inner bin templates (15) and other templates disclosed below can be colored with different colors (red, yellow, blue, green...) to be distinguished from each other.

Boundary bin templates (13) possess bin (7) waste since they are located on the flattened block boundary (5). Therefore combined bin templates (11) having triangular or quad convex regions will be replaced with boundary bin templates (13) in order to reduce waste on the flattened block boundaries (5). For each boundary bin template (13), an overlapping region between the boundary bin template (13) and the flattened block (4) is first computed. An enclosing region of the overlapping region is then found which is a minimum enclosing triangular or quad convex region of the overlapping region, and called a trimmed item (14). Plates of flattened blocks (4) covered by the inner bin templates (15) are called inner items (16). Combined items (12) will be generated by merging trimmed items (14) with their at least one neighboring items (another trimmed item (14) or inner item (16)). Fig. 4 (b) depicts two trimmed items (14) with their neighboring items and two combined items (12) in Fig. 4 (b) and Fig. 4 (c). The method is elaborated here. Let TB and TI denote the set of trimmed items (14) and inner items (16) respectively. And a first list, LI, stores all these items to be merged in the database. TBu is the infeasible trimmed item set where items do not satisfy the minimum edge length and angle criteria. And other items are stored in a feasible trimmed item set denoted by TBf. Items in TBf only merge with items in TB and do not merge with items in TI. However, items in TBu are allowed to merge with both items in 77 and TB to eliminate the infeasible trimmed items (14). A merging operation merges an item with its neighbor item and a combined item (12) is obtained which encloses both of these items. Waste (W) can occur after merging an item A with its neighboring item(s) B which is computed as follows:

W=Area(CAB )-Area(PAB ) where Area(.) is a function computing area of a polygon. CAB is the combined item (12), and PAB is the polygon enclosing both item A and item(s) B. A second list, L2, stores all possible merging item pairs, and if the computed waste is greater than a user defined parameter, E, the merging item pair is not added to the second list. Merging operations in the second list are grouped into two list: third list, L3, and fourth list, LA. The third list stores the merging item pairs where a feasible combined item (12) is obtained after merging items, one of which is an infeasible item. The fourth list contains the rest of the merging item pairs in the second list. The third list and the fourth list are sorted by waste occurring after the merge operation in an increasing order. Merging item pairs in the third list are appended to the second list first and then those of the fourth list are appended. By doing this, items in TBu can be merged faster and become a set of TBf. The first item pair in the second list is merged first. And then the second list is rearranged similarly as described in above. In other words, third and fourth list is obtained with existing items and appended to the second list in a sorted manner. Items are merged until no mergeable item pair left in the second list and combined items (12) are obtained. Fig. 5 shows combined items (12) in bold color boundaries for a mega block (2) consisting of three Flattened blocks (4).

In the "Split and Pack Approach step", how to pack items on bins (7) and then packing of combined items (12) will be described under the titles of;

- Combined Item (12) Packing Strategy,

- Generation of Candidate Points (18) and Regions (17),

- Generation of Combined Item (12) Orientations Before Packing, and - Packing Process.

Combined item packing strategy: Initially we have a set of combined items (12) and a finite number of bins (7) in this step. A combined item (12) is a quad or a triangle represented by its corner vertices. A bin (7) is a polygon initially having four corner vertices in 2D with length L and width W, and the number of corner vertices changes while packing combined items (12) into the bin (7). Combined items (12) are placed on bins (7) separately and the cost for each placement is computed using a cost function minimizing the waste of bins (7). The item with a minimum cost value is placed first. Bin (7) geometry is updated after each combined item (12) placement (i.e., shape of bin (7) is modified by subtracting the bin (7) from the placed combined item (12)). Candidate points (18) where combined items (12) are placed and their corresponding Candidate regions (17), convex triangle or quad regions, are found using the bin (7) geometry. As combined items (12) can be larger than Candidate regions (17), some portions of these items can exceed the Candidate regions (17). In that case, whether a combined item (12) is larger than a candidate region (17) is determined. If so, the intersection between the combined item (12) and the Candidate region (17) is found, and the intersected portion is packed into the bin (7). The exceeded portion is then split into quad or triangular items, each of which will be separately packed into the bin (7) in the next steps. After that, if the bin (7) has enough space for insert another combined item (12) is determined. If the bin (7) does not have enough space to insert combined items (12), a new (unused) bin (7) is utilized for the further combined item (12) placements, otherwise another combined item (12) is inserted into the same bin (7). Packing of combined items (12) is done until all combined items (12) are placed.

Generation of candidate points (18) and regions (17): To generate candidate regions (17) from a concave bin (7), the bin (7) is split into convex polygons by extending edges connecting an inner (concave) vertex and an outer (convex) vertex, and the convex polygons with the greatest areas are selected as candidate regions (17). Fig. 8 shows the methodology of candidate points (18) and regions' (17) generation. Fig. 6a shows a bin, whose geometry is updated as concave after placement of combined item/items (12), with Candidate points (18) in black. Firstly, a closest concave vertex (P _c ) to a Candidate point (18) is selected (Fig. 6b). A first vector (v _p ) and a second vector (v _n ) are computed in the direction of previous vertex (P _p ) of closest concave vertex (P _c ) to closest concave vertex (P _c ) and next vertex (P _n ) of closest concave vertex (P _c ) to closest concave vertex (P _c ) respectively (Fig. 6c). An edge connecting the closest concave vertex (P _c ) and the previous vertex (P _p ) is extended in the first vector (v _p ) direction until reaching another edge in the bin (7) and the bin (7) is split into two polygons (Fig. 6d). The first polygon (Pi) containing the Candidate point (18) is selected. The second polygon (P ₂ ) is found similarly using the closest concave vertex (P _c ), the next vertex (P _n ) and the second vector (v _n ) by extending an edge connecting the closest concave vertex (P _c ) and the next vertex (P _n ) in the second vector (v _n ) direction until reaching another edge in the bin (7) and the bin (7) is split into two polygons (Fig. 6d). The second polygon (P ₂ ) containing the Candidate point (18) is selected. The polygon out of the first polygon (Pi) and the second polygon (P ₂ ) with the greatest area is chosen. Another concave vertex of the second polygon (P ₂ ) is eliminated in a similar way by extending an edge connecting another concave vertex and another vertex until reaching another edge in the bin (7) and the bin (7) is split into two polygons (Fig. 6e). Two quad polygons are found, and the bottom one is selected as the Candidate region (17) (Fig. 6f). Three Candidate points (18) with their corresponding Candidate regions (17) are generated at the end (Fig. 6g). Generation of Combined Item (12) Orientations before Packing them into the Candidate Regions (17): Fig. 7 depicts the generation of combined item (12) orientations. Given a combined item (12) with its one of corner (such as left most corner), three more orientations of the combined item (12) are generated by rotating it around its main point (19) by 90 degrees. Orientation of four combined items (12) (Fig. 7a) are modified by mirroring them in the X-axis and four more orientations are obtained. Each of these orientations of combined items (12) will be used during packing them into the candidate regions (17).

Packing process: A combined item (12) can have a size that is greater than that of a bin (7) and may exceed the bin (7). The intersected portion between the combined item (12) and the bin (7) has to be packed into the bin (7) and the exceeding item (22) should be further packed in the next steps. The left image of Fig. 8a shows a bin (7) and a combined item (12). Four separate regions are formed after packing the combined item (12) into the bin (7): the packed portion (20) of the combined item (12), the remaining portion (21) of the bin (7), and two combined item (12) portions exceeding the bin (7) called exceeding items (22). An exceeding item (22) can have a shape other than a quad or triangle. Fig. 8b, 8c and 8d list the possible exceeding item (22) shapes. If the bin (7) is quad, the Exceeding item (22) can be six types of different polygons: triangle, quad, pentagon, hexagon, heptagon, octagon (see cases 1 to 6 in Fig. 8b). If the bin (7) is triangular, the Exceeding item (22) can have triangular, pentagonal, hexagonal and heptagonal shapes (see cases 7 to 10 in Fig. 8c). If an Exceeding item (22) has a shape other than a triangle or quad, it has to be decomposed into convex quad or triangular items, which are called Candidate items (Ci - C ₈ ) (Fig. 9). Candidate items (Ci - C ₈ ) will be packed into the bin (7) separately in the next steps. An exceeding item (22) can be convex or concave as shown in Fig. 9a and Fig. 9b respectively. To decompose a non-triangular or non-quad Exceeding item (22) with concave geometry into triangular or quad Candidate items (C1-C4), vertices of the Exceeding item (22) are ordered in counter-clockwise direction and concave vertices (23) in the exceeding item (22) are detected (Fig. 9a). Edges having at least one concave vertex (23) are then found, each of which consists of a start and end vertex in the counter-clockwise order. By extending the edge along the direction from its start vertex to the end vertex until the edge reaches the Exceeding item (22) boundary, a first point (24) is obtained. Another point (a second point (25)) is obtained by extending the edge in the opposite direction. The Candidate item (C1-C4) is the region containing first point (24) and second point (25) and all vertices (23) from the first point (24) to the second point (25) ordered in the counter-clockwise direction. To decompose a convex and non-triangular or non-quad Exceeding item (22) into Candidate items (C5-C8), an edge is formed from each vertex of the Exceeding item (22) in the positive and negative horizontal (X) direction (VH) and vertical (Y) direction (w) (Fig. 9 b). These edges divide the Exceeding item (22) into two regions (C5 - C8). If two regions do not exist after this division process, or if one of the generated regions does not satisfy the minimum length and angle constraints, they are not respected as Candidate items. Generated regions determined if they are triangular or quad. Generated regions are set as Candidate items (C5-C8) if they are triangular or quad. Otherwise, they have to be decomposed further until obtaining triangular or quad regions. It is also possible to utilize different directions rather than using positive and negative X and Y directions, which will result in the generation of Candidate items with different geometry.

Fig. 12 shows results using conventional 2D bin packing techniques and our approach. Applying our approach can minimize the bin (7) waste more.

Post Processing of Combined Items: Since packed combined items (12) can have edge lengths greater than the maximum length constraint (i.e., Imax), they have to be further decomposed into hull items satisfying the minimum and maximum length constraints disclosed before. Horizontal and vertical cuts, introduced in bin template (8) formation process, can split these combined items (12) into items that can be producible.