Monday, July 28, 2003

Quick Genetic Algorithm. Every once in a while you realize that you've hit the sweet spot with a language.  Tonight it wasn't really in terms of speed...it was how fast I got a genetic algorithm implemented.  I haven't written on in a long time, but for a project I'm working on I wanted a layout engine.  As I started working with the generated layouts, I realized that I just didn't really have any idea what the best layout would look like.  When you don't really know anything about the best solution, it's time to pull out an evolutionary algorithm.  Two hours later I have a pretty nicely encapsulated GA, and it seems to be functioning well in the tests I've run.  I wrote a couple of encodings (bit and float) for it, and the encoding mechanism is extensible. Time to write a cost function for my layout (minimize overlaps and overall size), and see what happens...note that this isn't a general graph layout.  It's for a more specific structure.  I am pretty sure that GAs don't do a good job on general graph layout. And did I mention I love Eclipse?  9:37:04 PM

Piccolo and Size. As my prototype starts to come together, I have been putting more and more detail into my Piccolo views.  Right now I am playing with a few hundred PTexts within a larger structure.  Each PText can have anywhere from a few dozen words to a few hundred words.  Now that I'm pushing this amount of information around, I've finally gotten Piccolo to slow down.  When I zoom in closely, the frame rate is great.  When I pull back, the frame rate drops to unacceptable levels.  Of course, it's doing a lot of work, and there isn't any optimization of the view, as yet. We know that Piccolo can easily handle the display of a few hundred simple shapes.  Reading the pattern document, I am instructed to use the semantic zooming capability.  Specifically, I can create a paint method that chooses what to paint by checking the scale of the paint context.  With something like this I could modify PText to begin check to see if the text I would write onto the screen would be legible (check against pixel size, like 6 or 8 pixels).  If the text is below that threshold, I can choose not to draw it.  This will result in some speedup.  We could also modify PText to check each line to see if it should be drawn (intersection versus the paint context's dirty area). This is all fairly primitive, though.  I am struck by the similarities between a flight simulator's terrain display (see the ROAM algorithm) and what we do in general with 2.5d interfaces.  What we want to do is provide as much visually accurate detail as possible where the viewer needs it, and remove or reduce detail where we don't need it.  A flight simulator usually has a huge database of terrain information.  It calculates an error factor that represents the difference between what is on the screen and what truest representation of the data would be (usually using a pixel metric).  Additional detail from the database is then displayed where necessary.  The best algorithms evaluate this information frame by frame, doing as much work as possible in each frame without violation frame rate display limits, to increase detail level where it is visually appropriate and reduce it where it is not needed.  Viewpoints are also taken into account -- the eye is good at detecting what's going on along the horizon, so more detail is added there, and less to open spaces. Simply creating a very large scene graph and displaying it isn't really possible in the large.  We need some kind of mechanism for managing level of detail with Piccolo, or within its extensions.  If you have thousands of objects and those objects can be expensive to compute, in one form or another, you cannot create them all in advance. PCamera understands what it is looking at in terms of rectangle, scale, and so forth, but doesn't help us with the level of detail problem.  We really want to be able to find out what PNodes are _in_ the view.  We want to know the zoom factor for those PNodes.  We want to be able to dynamically create more structure in the scene graph for visible nodes, or for those nodes that could soon become visible.  We want to be able to discard structure when detail is no longer necessary. The event bus within Piccolo does a great job of giving us keyboard and mouse events, but doesn't provide this level-of-detail information.  For example, I would like to get "close to visible", "is visible", "not visible", and so forth, as events.  As I receive these on PNodes, I can then elect, based on zoom factors and workload, to load in more information and generate more PNode detail in the scene graph, or remove that detail.  PCamera can maintain a list of nodes that are visible and essentially report on additions to or removals from that list.  A "penumbra" list could maintain that set of nodes that are "near visible".  PNodes will also need to have some state management: low detail state, high detail state, generating detail state, etc...and be able to emit some events in this area.  It can be useful for an application to have a standardized mechanism that can be notified when additional detail is ready. I'd like to open a discussion in this area.  The point of libraries like Piccolo is to be able to seamlessly navigate large expanses of detail.  To do this effectively we must have LOD mechanisms at our disposal.  We also need to have well-demonstrated patterns that show the best techniques for doing so.  I recognize that the goal of Piccolo is to have a small, concise library...but I am starting to feel that without the LOD support, Piccolo's full potential will be difficult to realize. 11:12:51 AM

Freaky Cool Illusions. Snagged the link from Critical Section...this comes from somewhere in Japan. Freaky Illusions. 12:05:49 AM