Re: [LAD] update: OT-ish: realtime 2d placement algorithms :-/

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
> Linux-audio-dev@email-addr-hidden
> http://lists.linuxaudio.org/listinfo/linux-audio-dev
>

_______________________________________________
Linux-audio-dev mailing list
Linux-audio-dev@email-addr-hidden
http://lists.linuxaudio.org/listinfo/linux-audio-dev
Received on Fri May 21 16:15:03 2010