13 Nov 2002 pabos   » (Journeyer)

Quixotic : Repainting, Paths & Fonts

My foray into 2d graphics and typography is provining to be very stimulating. I've been exploring how to implement the rendering pipeline for my Quixotic project recently.

I have a vague notion in my head that when redrawing an image, an efficient and complete redraw will do better overall than using logic and data structures to minimize redraw areas. Undoubtedly this is a simplification but I persist in thinking it while trying to avoid it at the same time. Mostly this is a combination of prior experience and inexperience. Some years ago I made some assembly language demos in DOS which often involved blitting some image to the screen as fast as possible to draw some sprite, animatated fire or the like. The concept which has stuck with me is "wait for the refresh signal and blit like mad". Still, anything beyond basic 2d vector shapes will require bitmap intermediaries so blitting will undoubtedly be a very import component of the whole solution. The inexperience factor is my unfamiliarity with how data structures behave when random lookups, caching, and computations all play variable parts in a time constrained redraw. 'Behave' sounds like an odd word to use to my ears but I think it describes it well enough since I can think of what the data structures should do but I don't have a feeling for what I they should do.

Since I'm trying to get some experience with data structures suitable for editable, easily renderable objects, I've been playing with paths and trying to decide on a good way to do partial path renderings. Redrawing the entire path if the path's bounding box is dirtied seems inelegant at best and, more importantly, the inevitable chained redraws that result would be a killer. For example, redrawing a path may cause a redraw of another path which partially overlaps it, which may cause the redrawing of text touching it, etc. This becomes enormously expensive very quickly, especially if the paths are filled with some form of bitmap paint (ie. gradient, image, pattern), masked, filtered and then composited. For that matter, since I'd like to support very large images redrawing even a single path can be expensive.

The problem I'm having is that I can't find a good way to represent partial paths. I've recently read that libart has a bounding box for each segment of its Sorted Vector Paths (SVPs) which could help at the expense of much higher memory use and the need to continually regenerate the SVP of paths being edited. However, my target canvas is in physical coordinates, not pixels, and I think SVP coordinates are already rasterized to pixel coordinates. I'll have to check into this further.

After trying to form all kinds of data structures for this purpose, I suddenly realized that clipping the paths within the regions of the canvas to be redrawn to that region would effectively bound the redraw to a limited area and draw only the portions of the path that I need. SVPs may prove useful here.

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!