Ordering shapes within a layer

govenius

Hi,

I have a GDS file with a number of layers and a number shapes (boxes & polygons) within each layer. I would like to control the order of the shapes, either by manually ordering them or, preferably, by sorting them based on the x-coordinate. Is there already a feature in KLayout that would allow this or would it require writing my own script/macro?

If a custom script/macro is required, is something like this reasonable?

1. Get a reference to the currently selected cell and find out the currently selected layer number.
2. Get a reference to the shapes with cell.shapes(layerno).
3. shapes_copy = shapes.dup()
4. shapes.clear()
5. call shapes.insert(shape) in the desired order for each shape in shapes_copy.

The reason I care about the order is that the GDS file is used to control an electron beam writer which seems to occasionally make a mistake in the first/last polygon it writes.

Thanks!
Joonas

P.S. I saw this older post but the issue there seems to be slightly different since for me the output format is also GDS: http://klayout.de/forum/comments.php?DiscussionID=231

Matthias

Hi Joonas,

basically your idea is correct, but unfortunately there is no warranty the the shape container stores the shapes in the order they are inserted. The shape container's order is optimized by KLayout to reflect the quad tree for quick lookup for example.

I have not checked that yet, but there are at least two requirements that you need to fulfil: first you have to use Editor mode and second you have to confine yourself to one kind of shape. Specifically you have to convert all shapes to polygons and strip text objects.

If you want to put some uncritical shape to the front or back, maybe binary manipulation of the GDS stream is the best option. The GDS format has a very nice property: you can easily insert or remove objects in the stream without having to adjust the other portions. The GDS format is very simple, so such a tool is not rocket science.

Regards,

Matthias

govenius

Thanks for the info Matthias! I'm sure manipulating the binary directly would be the fastest way to take care of this issue.

As an alternative, I'm think that one could overload db::Shapes::begin so that it accepts a comparison function and iterates over the shapes in a sorted order (as determined by the comparison function). Then dbGDSWriterBase.cc:278 could be modified to something like:

db::ShapeIterator shape (cref.shapes (l->first).begin (db::ShapeIterator::Boxes | db::ShapeIterator::Polygons | db::ShapeIterator::Edges | db::ShapeIterator::Paths | db::ShapeIterator::Texts, ptr_to_a_function_that_compares_some_property));

"some_property" here could be the x-coordinate or a user property called something like "export_weight".

Unfortunately my C++ skills are a bit rusty so I'm not sure what the best way to implement the function_that_compares_some_property is. It might be nice if the user could specify it dynamically as a Ruby function, but perhaps that's an overkill. Maybe it's enough to hard-code it as a regular C++ function that compares a user property called "export_weight", if it exists, or uses the x-coordinate otherwise.

Thoughts?

Matthias

Hi Joonas,

it's definitely not easy to modify the shape iterator - this is a high-level iterator scheme that provides all the abstraction atop of the binary data structures (which is a lot). Serialization into a specific order is simply not designed in, so you should better forget about that approach.

The best place to apply code modifications is probably the GDS writer. You could sort the shapes before they are output. But frankly, although I understand your wish to find a workaround for you failing writer hardware, your requirement is very specific since GDS by itself does not make any assumption about the order of elements. Any reader of GDS which does so is simply buggy or at least short-sighted and should be fixed. And providing some kind of order raises more questions like how to proceed in the general case of hierarchical layouts (and most layouts are in fact hierarchical). Plus given the two-dimensional nature of a layout, a simple sequential order is of little use in the general case.

I'd dump that issue to your writer vendor. They should fix their tool.

Matthias

govenius

Hi Matthias,

I would agree with you that for most applications the order should not matter. However, a sequential "vector style" writer (e.g. typical e-beam writer which skips empty regions) has to in the end choose the order of the shapes within the same level of hierarchy (cell and layer) somehow, so it doesn't seem unreasonable to use the order in which they appear in the data file (GDS2). Regardless of whether this is the best strategy or not, this is what the hardware I'm currently using does so I find the possibility of defining an order useful.

I made a patch that can be applied to 0.22.7. It allows sorting shapes in the GDS writer based on the x or y coordinate or a user-defined property (so that you can define an arbitrary order using a Ruby script/macro):
http://physics.aalto.fi/~govenij1/klayout-0.22.7-sort_within_layer_in_gds_writer.patch

One thing is that the patch moves static Variant get_property(...) from gsiDeclDbShape.cc to db::Layout (dbLayout.h). For consistency, it might make sense to move set_property(...) and delete_property(...) there as well, but I didn't do it since I wanted to keep the changes minimal.

You are welcome to incorporate the patch into the main branch if you wish. That would of course make upgrades to new versions easier for me.

Joonas

Matthias

Hi Joonas,

thank you for the patch. I had a look at it and basically it's complete with all the necessary extensions.

Let me allow some remarks:

Basically the static get_properties method could go into the db::Shape class. But it is part of Ruby interface intentionally. For Ruby methods, performance is not of much concern, but the method should be convenient. For C++ you can speed up the sorting significantly if you take the property name to id lookup out of the sorting loop, specifically work with the property name ID rather than the property key and do the name to ID conversion before the sorting. If you take that out from the get_properties method the remaining three lines can be put into the comparison function itself, so there is no real need for a new method. You can optimize that even more by providing a shortcut in the case of equal property ID's - in that case, the result of the compare function is false always.

I am a little reluctant to incorporate the sorting feature as provided also because the new writing code always collects the shapes into a shape vector even if no sorting is requested. A shape object may represent a single object inside a shape array and storing the expanded shape instances can easily exceed the memory requirements for the whole layout itself. That is a particular issue when converting OASIS to GDS files. Performance and memory awareness is crucial in that core functionality.

I'd like to call for a vote: if more users find such a feature useful I'd spend to time to test, document and optimize it. I personally still think that the feature is somewhat too specialized for a general purpose tool. For OASIS there is no solution because inside OASIS, reordering is a explicit degree of freedom required for compression. The feature also rises questions like how to deal with hierarchical layouts, what other properties to sort by (right side, area, what else?), provide sorting of instances as well etc.

Matthias