Subject:
|
Re: Make Small BOMs
|
Newsgroups:
|
lugnet.cad
|
Date:
|
Sun, 22 May 2005 19:14:21 GMT
|
Viewed:
|
843 times
|
| |
|
|
In lugnet.cad, Timothy Gould wrote:
> Dear all,
>
> I've decided to contribute my own small (no pun intended) contribution to
> Lego(R) CAD tools. For those who like to play, not read, here is the link.
>
> <http://www.lancs.ac.uk/staff/gouldt/makesmlbom/makesmlbom.html>
Very cool! Welcome to the fold.
>
> Basically it is a little perl program called (imaginatively) makesmlbom.pl
> which generates a smaller bill-of-materials from the LPub 2.3.07's output.
> Since a picture tells a thousand words, hear is what I mean.
>
> [LPub output]
>
> <<http://www.lancs.ac.uk/staff/gouldt/makesmlbom/citycat_bom_lpub_th.png>>
>
> [makesmlbom.pl output]
>
> <<http://www.lancs.ac.uk/staff/gouldt/makesmlbom/citycat_bom_msb_th.png>>
>
> Please let me know what you think, whether you think it is useful, what would
> make it useful, when it crashes etc. I've also released the code (small as it
> is - a theme here?) under the GPL although it is quite a mess, please feel
> free to play around.
>
> Tim
>
> PS. This project started with me trying to work out an algorithm for how to
> efficiently fit rectangles into a larger rectangle (a sort of tiling problem)
> and gre into the application from there.
When LPub is doing PLI's it sorts all the parts by width, and drops the widest
part in the first column (bottom of the PLI). The width of this part defines
the column width.
From there it tries to add part(s) to the next row within the column, starting
with the widest unplaced part. If a part is narrower than (or equal to) the
column width then the part is placed into the column. If there are no parts
that fit unto the column, we start on a new column with the widest unplaced
part.
So LPub allocates rows and columns.
Now, lets say the widest part is twice as wide as the second widest part. In
PLIs, before LPub tries to allocate a new row, it tries to see if any pieces
will fit to the right of the parts currently in the row, and yet does not spill
past the width of the column. If so, it allocates this part to a subcolumn.
LPub will then try to allocate any other parts into the subrows within the
subcolumn, as long as they are narrower than the subcolumn and the tot aheight
for the subrow is shorter than the row.
+-----------+-------------+-------+
| | second part | |
| first part| in subcolumn| |
| in row +-------------+ |
| defines | first part | |
| row height| in subcol +-------+
| | defines sub | new |
| | column width|subcol |
+-----------+-------------+-------+
| |
| first part in column defines |
| column width |
| |
+---------------------------------+
So PLIs can be packed pretty densly, but still maintain some sort of column/row
motif.
I used to allow BOMs to be placed just like PLIs, and they became *very* dense,
but they lacked any sense of order. If I tried to use the BOM to walk over to
my sorted collection and pick out all the parts, the picking was very
haphazzard.
Mindstorms' Bill Of Materials were sorted by part type, then width.
LPub sorts the BOM parts list by part type and then part width. It also
restricts placement to rows and columns, not allowing subcolumns or subrows.
This makes the BOM easy to work with, but leaves it not packed as densly as if
it were treated as a PLI.
I'm adding a new meta-command to control the sort type, and allow/disallow
subcols/subrows.
*** But *****
This still leaves LPub packing rectangles. In fact, a greater packing density
would be possible if LPub packed parallelograms (Don has some even better ideas
for the densest packing ability, but they are much more compute intensive.
If you render something like a long axle as a part, you end up with a thick
diagonal line (lines) going from the bottom left to the upper right of the
image. This leaves a large empty triangle in the upper left of the image, and a
large empty triangle in the lower right triangle of the image.
The large triangles guarantee less than optimum packing when packing rectangles.
When I render a part it is cropped (either by ldglite, or LPub after initial
render completes) to give me the smallest possible enclosing rectangle.
What I want to do is then determine the smallest enclosing parallelogram, where
the sides of the parallelogram are vertical, and the top and bottom are
diagonal. The slope of the top and bottom edges of the parallelogram is based
on the viewing angle provided when the part renders.
From there, we can pack parallelogram...... SO the above example looks like
this.
/|
/ |
/ |
/| /|
/ | / |
/ |/ |
/ | |
/ /| /|
/ / | / |
/| / |/ |
/ | / / |
/ | / / |
/ |/ / /
/ | / /
./ | / /
| |/ /
| / /
| / /
| / /
| / /
| / /
|/ /
| /
| /
| /
| /
|/
Notice that this leaves two triangles unallocated at the bottom and top of the
column. We can further allocate subrows and subcolumns in these triangles.
I want to enhance LPub to pack parallelograms rather than rectangles, but I'm
very open to other ideas too.
Kevin
|
|
Message has 3 Replies:
 | | Re: Make Small BOMs
|
| (...) <snip> Here is the BOM for pendmatic sorted by type and then allocated with rows and columns: (URL) is the BOM for pedmatic sordted only by width, and allowing subcolumns and rows. (URL) the second one has higher part density. Kevin (19 years ago, 22-May-05, to lugnet.cad)
| | | Re: Make Small BOMs
|
| (...) <snip> Here is pedmatic's BOM sorted by type with no subcolumns or subrows. (URL) is pedmatic's BOM sorted by width and allowing subcolumns and subrows. (URL) second one clearly has a higher part density. Kevin (19 years ago, 22-May-05, to lugnet.cad)
| | | Re: Make Small BOMs
|
| (...) <snip> (...) That's essentially what my algorithm does but I give the bias to whichever side will make the biggest new area rather than basing it on a specific preference. (...) Although there's no particular reason for it to happen, my (...) (19 years ago, 23-May-05, to lugnet.cad)
|
Message is in Reply To:
| | Make Small BOMs
|
| Dear all, I've decided to contribute my own small (no pun intended) contribution to Lego(R) CAD tools. For those who like to play, not read, here is the link. (URL) Basically it is a little perl program called (imaginatively) makesmlbom.pl which (...) (19 years ago, 22-May-05, to lugnet.cad, FTX)
|
8 Messages in This Thread:
  
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
This Message and its Replies on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
