On Fri, May 21, 2010 11:30, James Morris wrote: > Just a quick update. I eventually settled on a 64bit 2D array, with each > 64bit element in the array representing 64 spaces in the grid merely for > tracking the state of space being used or unused. Turns out much faster > this way. There will still be a list of blocks (or windows if it was a > window manager) placed but this is an entirely separate issue. For example > in the test code I keep track of the coordinates (returned by the > algorithm) and dimensions of placed blocks in an array. > > code/demo here: http://jwm-art.net/boxyseq/freespace_grid.tar.bz2
not very portable: uses GCC builtins ctzl, and clzl, and probably other stuff not so portable. > > video/demo here: http://jwm-art.net/art/freespace_grid.ogv > > > > running 'make' in the src, builds a demo/test program which produces > similar output to the video - this is where the good old xterm wins - set > font to 'tiny' and maximize vertically and widen it to atleast 128 chars > and xterm displays fast enough it looks like an animation. > > > I'm hoping this will work well enough for real-time placement, though the > worst case scenario has changed from just being 255 windows placed, to > something like.... placing a 1x1 block in a non-empty grid full of (any > dimensioned window... it's difficult to work out the worst case here. > > james. > > > On Fri, April 30, 2010 23:10, James Morris wrote: >> Hello, >> >> I'm still trying to develop my boxy-sequencer idea. Basically, I've >> tried >> out a couple of algorithms for window-manager-like box placement within >> a >> grid and run into big problems. >> >> Because I need help/advice/ideas, I'm posting here as it has some >> relevance, and I've also posted to >> >> http://stackoverflow.com/questions/2746590/fast-block-placement-algorithm-advice-needed >> >> A quick run down of what's happened so far, the two algorithms: >> >> The first I directly based on Fluxbox's Row Smart placement algorithm. >> Testing only the data structures, (and with gcc -O0) jack kicked out my >> client after around 200 boxes were placed in a 128x128 grid. I then >> counted how many times the algorithm looped through the entire list of >> boxes and discovered (not in RT for this) that the 256th box placement >> required around 14000 scans through the list of 255 previously placed >> boxes (i've decided 256 boxes will be the worst-case-scenario). >> >> The second algorithm consists of a freebox data structure which >> represents >> a rectangular area of free unused space. It also forms a node in a >> doubly >> linked list, as well as four directional links to other freeboxes >> touching >> it (with a maximum of one freebox touching each side of a freebox)... >> turns out rather complex to implement fully: 700+ loc for a partial >> implementation of row-smart left-to-right top-to-bottom placement - >> theres >> also col-smart, r-to-l, b-to-t and all combinations. >> >> Through stackoverflow, I've come across spatial hashing. >> >> I wondered if anyone here uses this technique for the display of data >> (would scrollable window views use such a thing?). worth it for a >> 128x128 >> grid etc? >> >> I'm just after any general thoughts/insights you might have as to what >> might or might not work. Anything worth pursuing. >> >> I'm afraid there's all sorts of little things to be considered so if you >> do have something to suggest, please read the stackoverflow post first. >> >> Cheers for any help, if possible, >> James. >> >> >> > > > _______________________________________________ > Linux-audio-dev mailing list > [email protected] > http://lists.linuxaudio.org/listinfo/linux-audio-dev > _______________________________________________ Linux-audio-dev mailing list [email protected] http://lists.linuxaudio.org/listinfo/linux-audio-dev
