17 Sep 2001 compiler   » (Journeyer)

Back to work

Spatial index anyone? I'm testing the limits of fine- grained'ness for web services. Most CAD and interactive graphics programs will have a spatial index to speed selection hit testing. Usually it's integrated into the scene graph as an implementation detail. Not so here...

Under what conditions will this be useful? I really don't know. Why you'd want to implement fast hit testing over the wire is not obvious. Still, I have a feeling it's a good idea so I'm doing it.

It works like this:

  • Add a set of nodes (bounds & user data)
  • Query for the nodes that intersect (or are contained in) a given rect

    Ah, simplicity. The assumption is that adding nodes is done rarely, and that queries are much more common. Consequently, adding a node is slow (as are editing and removing) but a query is quite fast.

    To improve the performance of adding, etc. I've implemented a simple graph in which each node is internally indexed. This is a gimmic, since the result is just a set of indexes that are searched as one. The performance of queries is somewhat degraded when using structure, but not much.

    I'll try to get it up on XMethods soon.

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