Direct Fourier or DCT texture mapping?

[Tim Sweeney]

I was thinking about the logistics of writing a texture mapper which maps
textures from 2D Fourier or DCT space, directly onto the screen. This
approach would seem to have many advantages, such as the ability to perform
anisotropic texture filtering, by convolving the texture with an
anisotropic filter kernel (a simple operation since convolution in the
texture doman corresponds to multiplication in the Fourier doman).

It's trivial to write a texture mapper which renders an nxn texture
directly from Fourier space using n^2 multiplies per pixel. With an FFT
operation a faster execution time should be possible, i.e. n * log(n) for a
FFT. However, that operation works for arbitrary pixels, and it seems that
a much faster operation might be possible, by exploiting the fact that
texture mapping involves tracing a spatially linear (though not necessary
temporally linear, due to perspective correction) path through a texture.

Has anyone tried this?
Is anyone aware of past work on this topic?
Does this seem like a good idea, or can someone with more experience in
Fourier transforms find fault with this approach?

-Tim Sweeney, Epic MegaGames, Inc.

[Stephen Westin]

In article <01bc09bd$35809760$eabfa1ce@unreal> "Tim Sweeney" <t...@epicgames.com> writes:

> I was thinking about the logistics of writing a texture mapper which maps
> textures from 2D Fourier or DCT space, directly onto the screen. This
> approach would seem to have many advantages, such as the ability to perform
> anisotropic texture filtering, by convolving the texture with an
> anisotropic filter kernel (a simple operation since convolution in the
> texture doman corresponds to multiplication in the Fourier doman).
>
> It's trivial to write a texture mapper which renders an nxn texture
> directly from Fourier space using n^2 multiplies per pixel. With an FFT
> operation a faster execution time should be possible, i.e. n * log(n) for a
> FFT. However, that operation works for arbitrary pixels, and it seems that
> a much faster operation might be possible, by exploiting the fact that
> texture mapping involves tracing a spatially linear (though not necessary
> temporally linear, due to perspective correction) path through a texture.
>
> Has anyone tried this?

2D Texture filtering and reconstruction from the frequency domain?
Evans & Sutherland. Don't know if it ever made it into their flight
simulators.

If I understand your second paragraph, you want to take a linear 1D
slice or projection from the 2D Fourier transform of the texture map
to simplify computation of a 1D scan line in screen space. This
reminds me of the work done on Fourier volume rendering, where a 2D
projection from a 3D volume is needed.

> Is anyone aware of past work on this topic?

From the SIGGRAPH on-line bibliography:

@InProceedings{Norton:1982:CMA,
author = "Alan Norton and Alyn P. Rockwood and Philip T.
Skolmoski",
title = "Clamping: a Method of Antialiasing Textured Surfaces
by Bandwidth Limiting in Object Space",
year = "1982",
month = jul,
volume = "16",
number = "3",
booktitle = "Computer Graphics (SIGGRAPH '82 Proceedings)",
pages = "1--8",
keywords = "texture mapping",
}

I don't recall if they
included anisotropic kernels.

On volume rendering from the Fourier domain:

@InProceedings{Levoy:1992:VRU,
author = "Marc Levoy",
title = "Volume rendering using the Fourier projection-slice
theorem",
pages = "61--69",
booktitle = "Proceedings of Graphics Interface '92",
year = "1992",
month = may,
conference = "held in Vancouver, B.C.; 11-15 May 1992",
keywords = "shading models, scientific visualization, medical
imaging",
annote = "",
}

@Article{Malzbender:1993:FVR,
author = "Tom Malzbender",
title = "Fourier Volume Rendering",
journal = "ACM Transactions on Graphics",
year = "1993",
volume = "12",
number = "3",
pages = "233--250",
month = jul,
}

There was also a paper at SIGGRAPH '93 by Takashi Totsuka and Marc
Levoy; it's at page 271 in the Proceedings, called "Frequency Domain
Volume Rendering".

<snip>
--
-Stephen H. Westin
swe...@ford.com
The information and opinions in this message are mine, not Ford's.

[Max Elliott]

Tim Sweeney wrote:
>
> I was thinking about the logistics of writing a texture mapper which maps
> textures from 2D Fourier or DCT space, directly onto the screen. This
> approach would seem to have many advantages, such as the ability to perform
> anisotropic texture filtering, by convolving the texture with an
> anisotropic filter kernel (a simple operation since convolution in the
> texture doman corresponds to multiplication in the Fourier doman).
>
> It's trivial to write a texture mapper which renders an nxn texture
> directly from Fourier space using n^2 multiplies per pixel. With an FFT
> operation a faster execution time should be possible, i.e. n * log(n) for a
> FFT. However, that operation works for arbitrary pixels, and it seems that
> a much faster operation might be possible, by exploiting the fact that
> texture mapping involves tracing a spatially linear (though not necessary
> temporally linear, due to perspective correction) path through a texture.
>
> Has anyone tried this?

> Is anyone aware of past work on this topic?

> Does this seem like a good idea, or can someone with more experience in
> Fourier transforms find fault with this approach?
>
> -Tim Sweeney, Epic MegaGames, Inc.

Sounds like quadratic approximation to me... :) Ever think about using
MMX to do the multiple coeff adds silmultaneously? I know this means
that the FPU is tied up meanwhile but maybe one can dispense with it for
the duration? Just some recent thoughts.

Max Elliott
Sibling Interactive

[Richard Cant]

In article <01bc09bd$35809760$eabfa1ce@unreal>, Tim Sweeney
<t...@epicgames.com> writes

>I was thinking about the logistics of writing a texture mapper which maps
>textures from 2D Fourier or DCT space, directly onto the screen. This
>approach would seem to have many advantages, such as the ability to perform
>anisotropic texture filtering, by convolving the texture with an
>anisotropic filter kernel (a simple operation since convolution in the
>texture doman corresponds to multiplication in the Fourier doman).
>
>It's trivial to write a texture mapper which renders an nxn texture
>directly from Fourier space using n^2 multiplies per pixel. With an FFT
>operation a faster execution time should be possible, i.e. n * log(n) for a
>FFT. However, that operation works for arbitrary pixels, and it seems that
>a much faster operation might be possible, by exploiting the fact that
>texture mapping involves tracing a spatially linear (though not necessary
>temporally linear, due to perspective correction) path through a texture.
>
>Has anyone tried this?
>Is anyone aware of past work on this topic?
>Does this seem like a good idea, or can someone with more experience in
>Fourier transforms find fault with this approach?
>

For a completely general implementation it seems too time consuming.

Early high quality real time texture mapping systems used such a
technique but were restricted to textures which had few Fourier
components.

Oddly enough the MIP Mapping technique is really a Fourier space
algorithm - if you think hard enough about it....

--
Richard Cant

[Barthold Lichtenbelt]

Tim Sweeney wrote:
>
> I was thinking about the logistics of writing a texture mapper which maps
> textures from 2D Fourier or DCT space, directly onto the screen. This
> approach would seem to have many advantages, such as the ability to perform
> anisotropic texture filtering, by convolving the texture with an
> anisotropic filter kernel (a simple operation since convolution in the
> texture doman corresponds to multiplication in the Fourier doman).
>
> It's trivial to write a texture mapper which renders an nxn texture
> directly from Fourier space using n^2 multiplies per pixel. With an FFT
> operation a faster execution time should be possible, i.e. n * log(n) for a
> FFT. However, that operation works for arbitrary pixels, and it seems that
> a much faster operation might be possible, by exploiting the fact that
> texture mapping involves tracing a spatially linear (though not necessary
> temporally linear, due to perspective correction) path through a texture.

A 1-D fourier transform will take NlogN operations, a 2-D FFT 6N^2logN
operations. As far as I know it's not possible to reduce that number.
Anisotropic filtering in the frequency domain could be faster than
filtering in the spatial domain, but it depends on the width and
complexity of the anisotropic filter.

filtering in freq. domain takes the following:

1) Compute 2D FFT of filter
2) Compute 2D FFT of texture
3) Compute filter times texture
4) Compute 2D Inverse FFT of result

1) and possible 2) only have to be computed once. 3) and 4) have to be
done everytime you want to texturemap a surface. 3) and 4) are N^2 +
6N^2logN operations (multiplies basically). It depends if that is
cheaper than simply doing the filtering (convolution) in the spatial
domain.

Note that the implementation is tricky. The result of 1) should be the
same
size as the result of 2), else you can't really do the multiplication in
the frequency domain.

Hope this helps.

Barthold

--
Barthold Lichtenbelt | Hewlett Packard Company
Graphics Software Lab | 3404 East Harmony Road
http://www.hp.com/info/voxelator | MS-74
(970) 229 6974 fax: (970) 229 4319 | Fort Collins, CO 80525