Basic design of layout drawing and data storage in Klayout

edited January 2010 in General
I'm interested in Klayout's basic design of layout drawing on Qt. The reason of my interest is..
I have several software development experience in GDS processing but these are just data and no drawing so I don't have no experience/idea of drawing layout except small and flat layout using simple QPainter widget.
I have a dream of developing LAYOUT VIEWER BY MYSELF so I seek enlightenment on large layout drawing and data treatment.
It is sure that watching the code is better than hear. However I'm beginner of Qt programming 3 month long and does not catch up large data drawing technique.

Again please tell me about basic design of layout drawing and
data storage on Qt.

Regards,
-Kenji Morohashi-

Comments

  • edited 11:19AM

    Hi Kenji,

    well, generally spoken there are probably more than one way to implement a layout database and the associated drawing engine.

    Doing it by the textbook would be like that: Analyze the requirements for your database, define a class hierarchy (probably involving some
    Shape base class and some specializations like Rectangle), define some persistency layer, add a view and a controller and you'll end up
    with a basic viewer application.

    I really think that it's possible to get quite far with that approach. It would be pretty simple to
    use a QPainter and map the geometrical objects to drawing primitives (preferably though some view object).
    You would instantly benefit from hardware acceleration available through Qt's abstraction layer and profit from QPainter's
    advanced drawing capabilities such as edge smoothing. Qt offers a great abstraction layer which greatly simplifies the
    implementation of such a scheme.

    However, I did not quite follow that approach. Maybe I was somewhat too suspicious but I had some concerns, mainly originating
    from the fact that I wanted to support very large layout databases and provide good memory efficiency. I did not do a in-depth analysis and
    research, so some of the design decisions may be questionable.
    I would like them to be seen as one way of implementing the functionality.

    That's basically my database design:

    • First, there are no virtual classes in the shape containers. Instead I use template classes for the shape containers and combine
      multiple specialized containers to represent a layer with multiple shape types. That is basically similar to the STL approach.
      The advantage of this approach is that shape containers can be very efficiently organized as linear memory blocks which beside a low memory
      overhead has considerable advantages algorithm-wise (i.e. fast random access) and an unbeatable memory bandwidth efficiency.
    • To maintain a high efficiency for objects with a variable length (in particular polygons), I use a cache to hold the actual
      point lists. Ideally, this further reduces the memory footprint of the layout database.
    • The linear containers can be efficiently organized into quad trees which are the basic data structures used in KLayout for
      geometrical lookup. A quad is actually a consecutive block of shapes which is located in a contiguous memory block. This way,
      all that is required for the quad is a pointer and a length value. That greatly reduces the overhead required for the
      geometrical indexing which is a key component of every layout database.
    • For holding OASIS data I keep the OASIS shape arrays at least in viewer mode. That is actually an efficient way to reduce
      memory but has some side effects performance wise.
    • To simplify the code, I implemented some access layer which is basically some generalized iterator providing a unified
      view on all shape types. This layer adds some considerable amount of algorithmic complexity but it looks like modern C++
      compiler do a great job of optimizing away all the unnecessary overhead.

    For the drawing engine, I also use a custom approach:

    • The drawing canvas is organized into bit planes which keep a monochrome image for the shapes of one layer. More precisely,
      multiple bitmaps exist per layer which each hold certain subsets of the geometrical information, such as vertices, the
      frames or the interior of the shapes.
    • The actual image is generated on-the-fly by combining these monochrome bitmaps with given properties such as color, width,
      visibility and similar. That actually is the basis of the layer colorization: by using a different color for the frame bitmapt,
      the frame of a shape is shown in a different color. The charm of this approach is that no redrawing is required when the
      display characteristics of a layer changes. It's just the combination of the bitmaps which changes. In addition, the convolution
      capabilities of the bitmap combination algorithm is the basis of the "marked" feature which otherwise I think is hard to implement
      efficiently.
    • Since however I did not trust in Qt's capabilities to paint into monochrome off-screen bitmaps, I decided to write my own
      rendering code. This basically is not very difficult (it's described in many textbooks) and it gave way to numerous low-level
      optimizations which helped to speed up the painting considerably.

    That are basically the main design principles behind KLayout. I see that many other projects use a different approach, in particular
    for painting. Most modern implementations employ OpenGL for speeding up the painting and there are good reasons to do that. We will see
    more and more powerful hardware support for OpenGL in the future and it's probably a good idea to jump onto that train. I personally
    see some issues when it comes to off-screen or background multithreaded rendering and there are still a lot of users with
    limited graphics hardware support, i.e. on remote servers behind some VPN or with fancy netbook hardware. Therefore I feel that the
    custom rendering approach still has some benefits but please considered that a biased opinion ... :-)

    Hopefully this explanation is helpful although it might be too elaborate. I can give you some hints where to look in the code if
    you have specific questions.

    Best regards,

    Matthias

  • Hello, Matthias,

    I am also reading Klayout source code for some self-developments. I also want to figure out the layout paint pricinples. Can you gvie me some hints about the sequency of code reading for layout painting part ?

Sign In or Register to comment.