fft in spherical coordinates

Sorry if this question has been asked before, I just can't find any 
answer in the archive. And sorry for not completely knowing what I am 
asking.
I have a set of data in spherical coordinates (phi, theta, r) and I need 
to subject these to a fft operation. When I search the literature, I am 
being warned of regular FFT since the spherical data are not defined on 
a regular grid having well-defined equidistant grid cells (uniformely 
sampled), but an irregular grid where (to simplify take a 2-dim. polar 
grid) those with smaller 'r' are clustered together more densely than 
those with higher 'r'.
Now, this sounds to me as a visualization effect of a polar grid not the 
actual grid which in my case is a well defined linear cartesian grid 
where 'phi' spans [-pi pi] and theta [0 pi/2] with equidistant, equally 
sized bins (cells). For those of you familiar with matlab, after 
converting my data from cartesian to spherical using matlab's "cart2sph" 
and grouping my 'phi's and 'theta's and 'r's to bins (10 bins in 'phi' 
and 36 bins in 'theta', and averaging my 'r's in those bins, I construct 
a grid by matlab's meshgrid command where the grid is 10x36 cells (bins) 
and map my averaged 'r's into the grid. . This looks to me as a linear 
grid and not a spherical non-uniform one.
My question is, what is then wrong with taking FFT and not bothering 
about the actual spherical grid ?

Thanks in advance,
Henrietta

On 24 Aug, 10:51, Henrietta Denoue <henrie...@netcalcul.fr> wrote:
> Sorry if this question has been asked before, I just can't find any
> answer in the archive. And sorry for not completely knowing what I am
> asking.
> I have a set of data in spherical coordinates (phi, theta, r) and I need
> to subject these to a fft operation. When I search the literature, I am
> being warned of regular FFT since the spherical data are not defined on
> a regular grid having well-defined equidistant grid cells (uniformely
> sampled), but an irregular grid where (to simplify take a 2-dim. polar
> grid) those with smaller 'r' are clustered together more densely than
> those with higher 'r'.
> Now, this sounds to me as a visualization effect of a polar grid not the
> actual grid which in my case is a well defined linear cartesian grid
> where 'phi' spans [-pi pi] and theta [0 pi/2] with equidistant, equally
> sized bins (cells). For those of you familiar with matlab, after
> converting my data from cartesian to spherical using matlab's "cart2sph"
> and grouping my 'phi's and 'theta's and 'r's to bins (10 bins in 'phi'
> and 36 bins in 'theta', and averaging my 'r's in those bins, I construct
> a grid by matlab's meshgrid command where the grid is 10x36 cells (bins)
> and map my averaged 'r's into the grid. . This looks to me as a linear
> grid and not a spherical non-uniform one.
> My question is, what is then wrong with taking FFT and not bothering
> about the actual spherical grid ?

It depends entirely on what you try to achieve.
The FFT works if the problem is stated in terms
of rectangular coordinates, and the corresponding
spectrum is what you want.

It does not work if the problem is stated in some
other coordinate system, and you want a result
stated in the corresponding spectrum coordinates.

The Radon transform and Fourier-Bessel transform
are examples of 'Fourier-like' transforms that play
much the same role as the 2D DFT, but map the signal
to other coordinates.

Rune

Henrietta Denoue <henrietta@netcalcul.fr> wrote:
 
< I have a set of data in spherical coordinates (phi, theta, r) and I need 
< to subject these to a fft operation. 

Why do you want to subject them to an fft?  (It matters)

< When I search the literature, I am 
< being warned of regular FFT since the spherical data are not defined on 
< a regular grid having well-defined equidistant grid cells (uniformely 
< sampled), but an irregular grid where (to simplify take a 2-dim. polar 
< grid) those with smaller 'r' are clustered together more densely than 
< those with higher 'r'.

(snip)

What are the boundary conditions on the data?

My first thought would be to expand in spherical harmonics for
the theta and phi part.

I know for cylindrical coordinates there is a Fourier-Bessel
transform, with sine/cos on the Z axis and theta axis, and
bessel functions on the R axis.  

As with a recent discussion here, it depends on the problem
you are trying to solve.  If you want to find the vibrational
modes for a solid or hollow sphere, you have to have the right
boundary conditions.  

-- glen

Henrietta Denoue <henrietta@netcalcul.fr> wrote:
 
< I have a set of data in spherical coordinates (phi, theta, r) and I need 
< to subject these to a fft operation. When I search the literature, I am 
< being warned of regular FFT since the spherical data are not defined on 
< a regular grid having well-defined equidistant grid cells (uniformely 
< sampled), but an irregular grid where (to simplify take a 2-dim. polar 
< grid) those with smaller 'r' are clustered together more densely than 
< those with higher 'r'.

(snip)

continuing, the Fourier transform is separable in rectangular
coordinates, such that you can do separate x, y, and z transforms.
It isn't separable in cylindrical or spherical coordinates.

If you want to do it in those cases, you can do a coordinate
transform to map into rectangular coordinates.  That is, put
your sphere inside a cube and then do the transform.
That works well if the results can be in rectangular coordinates,
otherwise it probably doesn't.

-- glen

Henrietta Denoue wrote:
> 
> Sorry if this question has been asked before, I just can't find any 
> answer in the archive. And sorry for not completely knowing what I am 
> asking.
> I have a set of data in spherical coordinates (phi, theta, r) and I need 
> to subject these to a fft operation. When I search the literature, I am 
> being warned of regular FFT since the spherical data are not defined on 
> a regular grid having well-defined equidistant grid cells (uniformely 
> sampled), but an irregular grid where (to simplify take a 2-dim. polar 
> grid) those with smaller 'r' are clustered together more densely than 
> those with higher 'r'.
> Now, this sounds to me as a visualization effect of a polar grid not the 
> actual grid which in my case is a well defined linear cartesian grid 
> where 'phi' spans [-pi pi] and theta [0 pi/2] with equidistant, equally 
> sized bins (cells). For those of you familiar with matlab, after 
> converting my data from cartesian to spherical using matlab's "cart2sph" 
> and grouping my 'phi's and 'theta's and 'r's to bins (10 bins in 'phi' 
> and 36 bins in 'theta', and averaging my 'r's in those bins, I construct 
> a grid by matlab's meshgrid command where the grid is 10x36 cells (bins) 
> and map my averaged 'r's into the grid. . This looks to me as a linear 
> grid and not a spherical non-uniform one.
> My question is, what is then wrong with taking FFT and not bothering 
> about the actual spherical grid ?
> 
> Thanks in advance,
> Henrietta

Thanks Rune and Glenn for the answers.
Just to add some info and the actual case and what the data are 
consisting of:
The original data are illumination vectors on a target point in seismic 
(I guess very much like the lighting vectors in 3D graphics). These 
vectors are defined in a 3D cartesian coordiante system with their 
normal components (x, y, z). These will later be used in a 
spatio-temporal filtering (in frequency domain, forward and inverse), to 
get an idea how an underwater area is illuminated (observed) by a 
source, given the geometry of the source, the target and the medium in 
which the waves travel.
The end user need these data in spherical coordinates to do the actual 
filtering and hence source estimation (pulse).
Perhaps, I should first find out what the user want in frequency domain, 
spectrum in rectangular grid or spherical grid ?

regards,
Henrietta

On 24 Aug, 11:26, Henrietta Denoue <henrie...@netcalcul.fr> wrote:
> Henrietta Denoue wrote:
>
> > Sorry if this question has been asked before, I just can't find any
> > answer in the archive. And sorry for not completely knowing what I am
> > asking.
> > I have a set of data in spherical coordinates (phi, theta, r) and I need
> > to subject these to a fft operation. When I search the literature, I am
> > being warned of regular FFT since the spherical data are not defined on
> > a regular grid having well-defined equidistant grid cells (uniformely
> > sampled), but an irregular grid where (to simplify take a 2-dim. polar
> > grid) those with smaller 'r' are clustered together more densely than
> > those with higher 'r'.
> > Now, this sounds to me as a visualization effect of a polar grid not the
> > actual grid which in my case is a well defined linear cartesian grid
> > where 'phi' spans [-pi pi] and theta [0 pi/2] with equidistant, equally
> > sized bins (cells). For those of you familiar with matlab, after
> > converting my data from cartesian to spherical using matlab's "cart2sph"
> > and grouping my 'phi's and 'theta's and 'r's to bins (10 bins in 'phi'
> > and 36 bins in 'theta', and averaging my 'r's in those bins, I construct
> > a grid by matlab's meshgrid command where the grid is 10x36 cells (bins)
> > and map my averaged 'r's into the grid. . This looks to me as a linear
> > grid and not a spherical non-uniform one.
> > My question is, what is then wrong with taking FFT and not bothering
> > about the actual spherical grid ?
>
> > Thanks in advance,
> > Henrietta
>
> Thanks Rune and Glenn for the answers.
> Just to add some info and the actual case and what the data are
> consisting of:
> The original data are illumination vectors on a target point in seismic
> (I guess very much like the lighting vectors in 3D graphics). These
> vectors are defined in a 3D cartesian coordiante system with their
> normal components (x, y, z). These will later be used in a
> spatio-temporal filtering (in frequency domain, forward and inverse), to
> get an idea how an underwater area is illuminated (observed) by a
> source, given the geometry of the source, the target and the medium in
> which the waves travel.
> The end user need these data in spherical coordinates to do the actual
> filtering and hence source estimation (pulse).
> Perhaps, I should first find out what the user want in frequency domain,
> spectrum in rectangular grid or spherical grid ?

Yes, you should.

The seismic problem is a bit difficult since the answer
depends on the distance between the source and the target:

- At small distances tone needs to use the spherical
  coordinate system.
- At larger distances one can get away with using the
  cylindrical coordinate system.
- At even larger distances the rectangular coordinate
  system is OK.

Rune

On Aug 24, 5:04&#4294967295;am, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
> I know for cylindrical coordinates there is a Fourier-Bessel
> transform, with sine/cos on the Z axis and theta axis, and
> bessel functions on the R axis. &#4294967295;

For spherical coordinates, there is an analogous transformation with
spherical bessel functions along the R axis and spherical harmonics in
the angular dimensions

There are fast algorithms for these kinds of things based on FFTs; see
http://www-user.tu-chemnitz.de/~potts/nfft/ and http://crd.lbl.gov/~cmc/ccSHTlib/doc/
for code for spherical-harmonic transforms, and a recent paper by Mark
Tygert proposing a theoretical improvement (http://cs-www.cs.yale.edu/
homes/tygert/spharmonic.pdf).  There have also been algorithms
proposed for the radial transform (google fast Hankel transform), but
I'm aware of less free code for that case.

Regards,
Steven G. Johnson

On Aug 24, 10:51 am, Henrietta Denoue
<henrie...@netcalcul.fr> wrote:

> I have a set of data in spherical coordinates (phi, theta,
> r) and I need to subject these to a fft operation. When I
> search the literature, I am being warned of regular FFT
> since the spherical data are not defined on a regular grid
> having well-defined equidistant grid cells (uniformely
> sampled), but an irregular grid where (to simplify take a
> 2-dim. polar grid) those with smaller 'r' are clustered
> together more densely than those with higher 'r'. Now, this
> sounds to me as a visualization effect of a polar grid not
> the actual grid which in my case is a well defined linear
> cartesian grid where 'phi' spans [-pi pi] and theta [0
> pi/2] with equidistant, equally sized bins (cells). For
> those of you familiar with matlab, after converting my data
> from cartesian to spherical using matlab's "cart2sph" and
> grouping my 'phi's and 'theta's and 'r's to bins (10 bins
> in 'phi' and 36 bins in 'theta', and averaging my 'r's in
> those bins, I construct a grid by matlab's meshgrid command
> where the grid is 10x36 cells (bins) and map my averaged
> 'r's into the grid. . This looks to me as a linear grid and
> not a spherical non-uniform one. My question is, what is
> then wrong with taking FFT and not bothering about the
> actual spherical grid ?

Your grid is a spherical nonuniform one; you are just
distorting it to look uniform. Distances in your grid
between different angular coordinates do not represent the
same physical distance at different radii. Of course you
*can* apply an FFT to data on such a grid, but the
corresponding physical interpretation will be more
complicated. This is because frequency in the angular
coordinates does not represent "cycles per metre" but only
"cycles per radian". Oscillations of the same number of
cycles per radian represent quite different physical
frequencies/wavelengths, depending on the radius at which
they are taking place.

But why are your angular coordinates so truncated? Remember
the FFT assumes periodicity.

Actually I am not sure what you are doing at all. Why are
you "averaging your r's"? What is the data precisely? Is it
a real-valued function of theta and phi whose value you are
representing by the r coordinate? This is misleading: the r
coordinate then has a very different physical significance
from the theta and phi coordinates. Or are the data 3d
vectors that themselves are somehow organised spatially,
i.e. a vector field?

illywhacker;

illywhacker wrote:
> On Aug 24, 10:51 am, Henrietta Denoue
> <henrie...@netcalcul.fr> wrote:
> 
>> I have a set of data in spherical coordinates (phi, theta,
>> r) and I need to subject these to a fft operation. When I
>> search the literature, I am being warned of regular FFT
>> since the spherical data are not defined on a regular grid
>> having well-defined equidistant grid cells (uniformely
>> sampled), but an irregular grid where (to simplify take a
>> 2-dim. polar grid) those with smaller 'r' are clustered
>> together more densely than those with higher 'r'. Now, this
>> sounds to me as a visualization effect of a polar grid not
>> the actual grid which in my case is a well defined linear
>> cartesian grid where 'phi' spans [-pi pi] and theta [0
>> pi/2] with equidistant, equally sized bins (cells). For
>> those of you familiar with matlab, after converting my data
>> from cartesian to spherical using matlab's "cart2sph" and
>> grouping my 'phi's and 'theta's and 'r's to bins (10 bins
>> in 'phi' and 36 bins in 'theta', and averaging my 'r's in
>> those bins, I construct a grid by matlab's meshgrid command
>> where the grid is 10x36 cells (bins) and map my averaged
>> 'r's into the grid. . This looks to me as a linear grid and
>> not a spherical non-uniform one. My question is, what is
>> then wrong with taking FFT and not bothering about the
>> actual spherical grid ?
> 
> Your grid is a spherical nonuniform one; you are just
> distorting it to look uniform. Distances in your grid
> between different angular coordinates do not represent the
> same physical distance at different radii. Of course you
> *can* apply an FFT to data on such a grid, but the
> corresponding physical interpretation will be more
> complicated. This is because frequency in the angular
> coordinates does not represent "cycles per metre" but only
> "cycles per radian". Oscillations of the same number of
> cycles per radian represent quite different physical
> frequencies/wavelengths, depending on the radius at which
> they are taking place.
> 
> But why are your angular coordinates so truncated? Remember
> the FFT assumes periodicity.
> 
> Actually I am not sure what you are doing at all. Why are
> you "averaging your r's"? What is the data precisely? Is it
> a real-valued function of theta and phi whose value you are
> representing by the r coordinate? This is misleading: the r
> coordinate then has a very different physical significance
> from the theta and phi coordinates. Or are the data 3d
> vectors that themselves are somehow organised spatially,
> i.e. a vector field?
> 
> illywhacker;

Thanks illy for the answer,
the reason I have constructed such a grid is, I needed some fast 
algorithm to do the frequency analysis, something like FFT. And not 
knowing the equivalent method in a spherical domain(and not 
understanding what it really means) I just thought I use FFT on my 
rectangular grid. And, obviously having encountered the warnings about 
doing FFT on a non-uniform grid, I asked what is it I actually should 
do. As I explained in another post, my data is a vector "field" (vectors 
emanating from a single point in different directions). The vectors are 
described in spherical coordinates and construct a 3D spatial volume in 
which the target point is visible in the space. Sort of a spanish fan 
shaped filter in space (cross-sectioned if looked in 2D). Now if one 
wants to describe this filter in frequency domain, given that these are 
in spherical coordinates, how would one do that without going to 
cartesian and how is this so called frequency spectrum is interpreted ?
Reason for my 2D grid is, since the vectors are all normalized then the 
"r" in spherical coordinartes is equal to 1 for all the vectors. Then, 
what I have is only variations in theta and phi. As to the truncation of 
my angular domain, it was just an example for the gridding of my theta 
(0-pi) and phi (0-pi/2), that is the only region I am interested in 
(application related).

On 28 Aug, 15:20, Henrietta Denoue <henrie...@netcalcul.fr> wrote:

> the reason I have constructed such a grid is, I needed some fast
> algorithm to do the frequency analysis, something like FFT. And not
> knowing the equivalent method in a spherical domain(and not
> understanding what it really means) I just thought I use FFT on my
> rectangular grid.

That ought to be the first point on your to-do list:
Find out what the assignment is all about. Pick up a
textbook on differential equations, particularly
vibrations in shells and spheres.

> And, obviously having encountered the warnings about
> doing FFT on a non-uniform grid, I asked what is it I actually should
> do. As I explained in another post, my data is a vector "field" (vectors
> emanating from a single point in different directions). The vectors are
> described in spherical coordinates and construct a 3D spatial volume in
> which the target point is visible in the space. Sort of a spanish fan
> shaped filter in space (cross-sectioned if looked in 2D). Now if one
> wants to describe this filter in frequency domain, given that these are
> in spherical coordinates, how would one do that without going to
> cartesian and how is this so called frequency spectrum is interpreted ?

The details depend on the basis functions in the spherical
coordinate system. In range, the basis functions are of
Bessel type, and in azimuth they are sinusoidals. They might
be sinusoidals in elevation as well, but do check that with
a textbook.

As for the interpretations, the spectra are frequency-wavenumber
spectra (possibly with more than one wavenumber dimenstion)
that are found all over spatial signal processing.

> Reason for my 2D grid is, since the vectors are all normalized then the
> "r" in spherical coordinartes is equal to 1 for all the vectors. Then,
> what I have is only variations in theta and phi. As to the truncation of
> my angular domain, it was just an example for the gridding of my theta
> (0-pi) and phi (0-pi/2), that is the only region I am interested in
> (application related).

Again, check the basis functions on the spherical shell with a
textbook on maths. Then make absolutely certain that r really is
fixed. IFF there are sinusoidal basis functions in BOTH azimuth
AND elevation, AND r really is fixed, then you MIGHT be able
to get away with a regular 2D FFT.

But there are lots of caveats here. If you want useful results
you need *all* the details to add up.

Rune