Basic design of layout drawing and data storage in Klayout

Comments

• Matthias

  February 2010 edited November -1

  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
• csanbo

  December 2021

  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 ?