Forums > MaxMSP

partitioned fft convolution

December 24, 2007 | 4:54 pm

i’ve been working on a patch to do this for a couple of weeks now, and it’s turning out to be more complicated than i expected – i’ve implemented it in C before, but with a signal processing structure rather than procedural code it’s kind of awkward. the thing is, i’m very surprised no such patch or external already exists for this.. maybe it does, but i haven’t been able to find one anywhere. i would have thought it would be a very common and useful effect.

can anyone point me to something that already exists, or anything else that might be useful?


December 24, 2007 | 7:48 pm

gizmo~


December 24, 2007 | 8:19 pm

hmm, not sure how gizmo~ is relevant


December 24, 2007 | 9:35 pm

oops! wrong fft

try this

save this as aConvolve~:
#P window setfont Times 10.;
#P window linecount 1;
#P comment 9 217 170 1310730 convolution of input 1 with input 2.;
#P window setfont "Fixedwidth Serif" 10.;
#P newex 64 116 27 1441802 *~;
#P newex 12 116 27 1441802 *~;
#P newex 12 183 62 1441802 fftout~ 1;
#P newex 127 65 59 1441802 cartopol~;
#P newex 127 29 108 1441802 fftin~ 2;
#P newex 12 29 114 1441802 fftin~ 1;
#P connect 1 1 2 1;
#P connect 1 0 2 0;
#P fasten 2 0 4 1 132 95 34 95;
#P fasten 2 0 5 1 132 95 86 95;
#P connect 5 0 3 1;
#P connect 0 1 5 0;
#P connect 4 0 3 0;
#P connect 0 0 4 0;
#P window clipboard copycount 7;

then use it like this:
#P window setfont "Sans Serif" 9.;
#P window linecount 1;
#P newex 7 144 34 196617 pass~;
#N comlet inR;
#P inlet 140 28 15 0;
#P window setfont "Fixedwidth Serif" 10.;
#P newex 7 57 143 1441802 pfft~ aConvolve~ 1024 2;
#B color 5;
#N comlet OutLeft;
#P outlet 7 184 15 0;
#N comlet inL;
#P inlet 7 26 15 0;
#P connect 2 0 4 0;
#P connect 3 0 2 1;
#P connect 4 0 1 0;
#P connect 0 0 2 0;
#P window clipboard copycount 5;


December 25, 2007 | 11:20 am

On 24 Dec 2007, at 17:54, pete wrote:

> . the thing is, i’m very surprised no such patch or external
> already exists for this.. maybe it does, but i haven’t been able to
> find one anywhere. i would have thought it would be a very common
> and useful effect.
>
> can anyone point me to something that already exists, or anything
> else that might be useful?

thomas resch, one of our students here at ESB in basel has done a
partitioned convolution external for maxmsp
as part of his diploma. first version was still a little buggy, but i
think meanwhile he managed to improved the overall stability
and has done a UB version (no windows i believe).
you can find it at http://www.zippernoise.net/

volker.


December 25, 2007 | 11:51 am

On 24 Dec 2007, at 22:36, don malone wrote:

> oops! wrong fft
>
> try this
>
> save this as aConvolve~:
> #P window setfont Times 10.;
> #P window linecount 1;
> #P comment 9 217 170 1310730 convolution of input 1 with input 2.;
> #P window setfont "Fixedwidth Serif" 10.;
> #P newex 64 116 27 1441802 *~;
> #P newex 12 116 27 1441802 *~;

this won’t give you linear convolution, which i think pete is
interested in.
since you are ignoring the phases of the second signal i would rather
call it ‘cross synthesis’.
this might even work better if some sort of spectral flattening would
be imposed on one of the input spectrums.
just my 2 ‘rappen’
vb


December 25, 2007 | 4:44 pm


December 25, 2007 | 4:50 pm


December 27, 2007 | 8:48 pm

I think that although partitioned fft convolution is possible with max objects only, it is impractical in terms of CPU usage.

I’ve been considering writing a C external for this for a month or so (I know there are one or two others already, but for various reasons I’d prefer to write my own). Anyway, this thread convinced me to try a max only version. However, the cost of simply doing the complex multiplication is higher with msp objects than vanilla c code – far higher again than the purpose written apple routines in the accelerate framework (sorry pc guys). However, I found the main problem is with simply moving the data around in buffers etc…. The cost of index~ objects is prohibitively expensive making it non-viable. I reckon most of your CPU would go on a medium length stereo impulse (10 secs or so), which on a 2.4 GHz machine is not what you want,,,,,

So I didn’t reach a final product – it wasn’t worth it – plus although the processing itself is quite straightforward partitioning the impulse and doing the ffts on it is a bit of a pain (by no means impossible – but slightly unwieldy.

So – I’d advise an external-based approach. If you can hack the limitation of machines with SSE instructions only then I’d advise vectorising the code – I think you could be looking at a speed increase of 2-4 times although I haven’t tested that yet. For stereo you might like to offset your FFTs (left and right) to give more even cpu usage – the delay will remain the same – you’ll just have more efficient use of resources. At some point I’ll have an external for zero-latency partitioned convolution on mac that I’d be happy for someone to port / recompile for windows, although they’d have to deal with the fft stuff as I’ll be using the apple routines. There is unfortunately no time-frame on this though as it’s not a priority, so if you have code you’re happy with I’d advise using that…

If you need any help with the max/msp C API I’m pretty familiar with it – if the code you have is realtime then the port to an external could probably be done very quickly ..

Regards,

Alex


December 27, 2007 | 10:49 pm

Quote: AlexHarker wrote on Thu, 27 December 2007 13:48
—————————————————-
>
> I think that although partitioned fft convolution is possible with max objects only, it is impractical in terms of CPU usage.
>
> I’ve been considering writing a C external for this for a month or so (I know there are one or two others already, but for various reasons I’d prefer to write my own). Anyway, this thread convinced me to try a max only version. However, the cost of simply doing the complex multiplication is higher with msp objects than vanilla c code – far higher again than the purpose written apple routines in the accelerate framework (sorry pc guys). However, I found the main problem is with simply moving the data around in buffers etc…. The cost of index~ objects is prohibitively expensive making it non-viable. I reckon most of your CPU would go on a medium length stereo impulse (10 secs or so), which on a 2.4 GHz machine is not what you want,,,,,
>
> So I didn’t reach a final product – it wasn’t worth it – plus although the processing itself is quite straightforward partitioning the impulse and doing the ffts on it is a bit of a pain (by no means impossible – but slightly unwieldy.
>
> So – I’d advise an external-based approach. If you can hack the limitation of machines with SSE instructions only then I’d advise vectorising the code – I think you could be looking at a speed increase of 2-4 times although I haven’t tested that yet. For stereo you might like to offset your FFTs (left and right) to give more even cpu usage – the delay will remain the same – you’ll just have more efficient use of resources. At some point I’ll have an external for zero-latency partitioned convolution on mac that I’d be happy for someone to port / recompile for windows, although they’d have to deal with the fft stuff as I’ll be using the apple routines. There is unfortunately no time-frame on this though as it’s not a priority, so if you have code you’re happy with I’d advise using that…
>
> If you need any help with the max/msp C API I’m pretty familiar with it – if the code you have is realtime then the port to an external could probably be done very quickly ..
>
> Regards,
>
> Alex
—————————————————-

really useful reply, thanks. i’ve started down the external route now – have decided i’m going to base it on the Pd external partconv~ by Ben Saylors (i hope he doesn’t mind..) which uses the fftw library (http://www.fftw.org/). sounds like between us we’ll sort out mac and windows versions. is it worth standardising the interface? i was thinking of just keeping it simple as possible, like:

[conv~ buffername partitionsize]

with a set message to change the buffer~ being used.

i don’t know anything about vectorization though, what does it involve?


December 28, 2007 | 9:08 am

On 27 Dec 2007, at 21:48, Alex Harker wrote:

> At some point I’ll have an external for zero-latency partitioned
> convolution…

hm, Lake dsp has a patent on this one, no?
or are you thinking about something new/different?


December 28, 2007 | 11:48 am


December 28, 2007 | 12:02 pm

I’ve managed to confirm from a uk government website that the European patent has been revoked – so as far as I’m aware – in my part of the world I’m free to write and distribute my external…..

Alex


December 28, 2007 | 1:07 pm

On 28 Dec 2007, at 13:02, Alex Harker wrote:

> I’ve managed to confirm from a uk government website that the
> European patent has been revoked – so as far as I’m aware – in my
> part of the world I’m free to write my external…..

sounds like good news – thanks for letting us know!

volker.


December 28, 2007 | 3:26 pm

Hi,

do you have an URL for this?

Best,
Trond

Alex Harker wrote:
>
> I’ve managed to confirm from a uk government website that the European patent has been revoked – so as far as I’m aware – in my part of the world I’m free to write my external…..
>
> Alex


December 29, 2007 | 12:45 am

Quote: Trond Lossius wrote on Fri, 28 December 2007 08:26
—————————————————-
> Hi,
>
> do you have an URL for this?

http://www.ipo.gov.uk/2006-6091.pdf

The patent number is listed under revoked patents- it’s the first in the list I think. You can google it to confirm that it’s the patent in question.

i believe the US equivalent is still valid however….

Alex


Viewing 16 posts - 1 through 16 (of 16 total)