Name
SGI_fft
Name Strings
GL_SGI_fft
Status
XXX - Not complete yet!!!
Version
Last Modified Date: April 24, 2000
Author Revision: $Header: //depot/main/doc/registry/extensions/SGI/fft.spec#11 $
Number
99
Dependencies
SGI_complex is required
SGI_complex_type is required
SGI_color_table affects the definition of this extension
EXT_convolution affects the definition of this extension
Overview
The Fast Fourier Transform (FFT) is a set of efficient algorithms for
computing the discrete Fourier transform (DFT) that are based on the
fundamental principle of decomposing the computation of the Fourier
transform of a sequence into successively smaller discrete Fourier
transforms.
This extension defines complex to complex pixel formats 1-dimensional
fast Fourier transforms in the pixel transfer process. Pixel drawing,
reading and copying are all candidates for FFTs. Note that it is possible
to compute the forward DFT, inverse DFT, multi-dimensional DFT, real to
complex DFT, and any combination of the above efficiently, using the complex
to complex 1-dimensional forward FFT only.
The number of input elements must be a power of two. If the original
series size is not a power of two, the data can be padded with zeros or
resampled to meet this prerequisite. It is the user's responsibility to
satisfy this constraint.
FFT precision is implementation dependent.
This extension replaces the convolution block of the pixel pipeline
with a new pixel transform block. The pixel transform block
can be configured to be the convolution operation defined by the
EXT_convolution extension or the fft operation defined in this extension.
It also can be enabled or disabled all together.
Issues
* some platforms (i.e Moosehead and MG) may initially only implement 1D and
2D FFT's, if this is the case, should we break up the 3D extension as a
separate one? Will these machines be forced to say that this extension
is not 'fully' supported if they do not implement 3D?
resolved: we will only support 1D ffts and allow later
expandibility to 2D and 3D. still need to resolve whether we
support 1D in row, column, and depth order on 2D and 3D images
to make it easier to build 2D and 3D ffts.
* We also have to take in account a possible broadening of the restricted
list of input sizes of powers of 2, to sizes whos prime factors are 2, 3,
and maybe even 5. The motivation is induced by standard video image sizes
that are not always powers of 2. The FFT of the zero padded series and
the FFT of the original series are not always equivalent
resolved: we will only support power of 2 input sizes
* 1D FFTs are defined on images of all dimensions. This is different from
the way CONVOLUTIONS are defined. We might need a parameter or name that
specifies in what dimension does a 1D FFT applied to an incoming n-D
image.
* we refer to the new pixel processing block which can be configured
as either convolution or fft as the pixel transform. Is there a better
name for this.
* it seems the way the spec is defined, that only way to disable the
scale and bias is to select convolve as the transform and use disable
the convolve using Disable. Is there a better way?
* Even though the algorithm is not described in the spec, this
knowledge might have some importance to the user, because
precision becomes a more important issue, and the size of the
FFT directly supported will typically be limited. In order to
provide operators that can be used as basic blocks for computing
larger size of FFTs, some extra parameters might be appropriate.
This is a low priority issue, as the suggested parameters can be added
later, if the need arises.
FFT_TYPE_UNKNOWN_SGI
FFT_TYPE_RADIX4_DIF_NIO_SGI
FFT_TYPE_RADIX4_DIT_NOO_SGI
DIF - Decimation in Frequency
DIT - Decimation in Time
NIO - Normal Input Order
NOO - Normal Output Order
The FFT_SORT_SGI parameter can be used to suppress sorting into digit
reverse order.
* The TRANSPOSE_SGI parameter can be used to transpose a 2-D image after
performing 1-D fft on the image rows before it is placed at the
destination color buffer, in order to expedite the 2-D fft.
HP has already an extension in effect, I'm told, that does those kind of
operations on images. It make sense to place it immediately before the
zoom operation.
New Procedures and Functions
void PixelTransformSGI(enum target);
void PixelTransformParameterfSGI(enum target,
enum pname,
float param);
void PixelTransformParameterfvSGI(enum target,
enum pname,
const float* params);
void PixelTransformParameteriSGI(enum target,
enum pname,
int param);
void PixelTransformParameterivSGI(enum target,
enum pname,
const int* params);
void GetPixelTransformParameterfvSGI(enum target,
enum pname,
float* params);
void GetPixelTransformParameterivSGI(enum target,
enum pname,
int* params);
New Tokens
Accepted by the parameter of PixelTransformSGI:
CONVOLUTION_SGI 0x81C5
FFT_1D_SGI 0x81C6
Accepted by the parameter of GetBooleanv, GetIntegerv, GetFloatv,
and GetDoublev:
PIXEL_TRANSFORM_OPERATOR_SGI 0x81C4
Accepted by the parameter of Enable, Disable, and IsEnabled,
and by the parameter of GetBooleanv, GetIntegerv, GetFloatv,
and GetDoublev:
PIXEL_TRANSFORM_SGI 0x81C7
Accepted by the parameter of GetPixelTransformParameterfvSGI
and GetPixelTransformParameterivSGI:
MAX_FFT_WIDTH_SGI 0x81C8
Accepted by the parameter of PixelTransferi, PixelTransferf,
and by the parameter of GetBooleanv, GetIntegerv, GetFloatv,
and GetDoublev:
POST_TRANSFORM_RED_SCALE_SGI ????
POST_TRANSFORM_GREEN_SCALE_SGI ????
POST_TRANSFORM_BLUE_SCALE_SGI ????
POST_TRANSFORM_ALPHA_SCALE_SGI ????
POST_TRANSFORM_RED_BIAS_SGI ????
POST_TRANSFORM_GREEN_BIAS_SGI ????
POST_TRANSFORM_BLUE_BIAS_SGI ????
POST_TRANSFORM_ALPHA_BIAS_SGI ????
*Note* - values defined in the spec, but not documented below
SORT_SGI = 0x81C9
TRANSPOSE_SGI = 0x81CA
Additions to Chapter 2 of the OpenGL Specification (OpenGL Operation)
None
Additions to Chapter 3 of the OpenGL Specification (Rasterization)
The specification of pixel operators is added to the GL Specification in
section 3.6.2, "Pixel Transfer Modes."
The operations of the pixel transforms are added to the GL Specification in
section 3.6.3, "Rasterization of Pixel Rectangles, immediately following the
subsection "Index Lookup", and immediately prior to the operations described
by EXT_histogram. Transforms are enabled, disabled, and queried by calling
Enable, Disable and IsEnabled respectively. The pixel transform is enabled
by default. A particular transform is selected by calling PixelTransformSGI
with the parameter set to one of: CONVOLUTION_SGI, or FFT_1D_SGI.
The pixel transform is performed only for RGBA groups, though these groups
may have been specified as color indexes and converted to RGBA by index
table lookup.
The convolution transform is described in the EXT_convolution
specification.
If pixel transform is enabled and FFT_1D_SGI is selected, the 1-dimensional
fft is applied to the image passed to TexImage1D, and to 1-dimensional
textures queried by GetTexImage. It is applied on a per-row basis to
the 2-dimensional images passed to DrawPixels, CopyPixels, ReadPixels,
TexImage2D, TexSubImage2DEXT, CopyTexImage2DEXT, CopyTexSubImage2DEXT,
and to 2-dimensional images queried by GetTexImage. It is also applied
on a per-row basis to the 3-dimensional images passed to CopyTexSubImage3DEXT,
TexImage3DEXT, and TexSubImage3DEXT, and to 3-dimensional images queried by
GetTexImage.
The discrete fourier transform is a complex valued sum of products of
source image pixels and the discretely sampled function exp(2PIikn/N).
[exp(2PIix) == sin(x)+icos(x)]
Source image pixels always have four components: red, green, blue,
and alpha. Individual color components of each source image pixel
are always independently processed as part of the transform.
The discrete fourier transform is defined differently for each of
the three transform types. In the following equations the
SUM{}{}equation
notation indicates the sum of the equation evaluated for all
combinations of conditions indicated within the curly brackets. The
variables Ws, Hs, and Ds refer to the dimensions of the source
pixel image.
The discrete fourier transform equation is:
1-dimensional transform:
C[n] = SUM{k = 0 through Ws-1}
Cs[k]*exp(2PIikn/Ws)
The inverse transform equation is:
1-dimensional transform:
C[n] = SUM{k = 0 through Ws-1}
Cs[k]*exp(-2PIikn/Ws)
-----
Ws
The particular fft algorithm is left unspecified to allow greater
flexibility for implementations.
If a pixel transform operation is performed, the resulting image is scaled
and biased by parameters specified using the PixelTransfer command.
These operations are:
red = red * POST_TRANSFORM_RED_SCALE_SGI
+ POST_TRANSFORM_RED_BIAS_SGI
green = green * POST_TRANSFORM_GREEN_SCALE_SGI
+ POST_TRANSFORM_GREEN_BIAS_SGI
blue = blue * POST_TRANSFORM_BLUE_SCALE_SGI
+ POST_TRANSFORM_BLUE_BIAS_SGI
alpha = alpha * POST_TRANSFORM_ALPHA_SCALE_SGI
+ POST_TRANSFORM_ALPHA_BIAS_SGI
If no fft operation is performed, the scale and bias are not
performed either.
Additions to Chapter 4 of the GL Specification (Per-Fragment Operations
and the Framebuffer)
The operation of fft during pixel copy and query operations is
identical to the operation during pixel drawing and texture image
definition.
Additions to Chapter 5 of the GL Specification (Special Functions)
Commands GetPixelTransformParameterfvSGI and
GetPixelTransformParameterivSGI are not include in display lists.
They are always executed immediately.
Additions to Chapter 6 of the GL Specification (State and State Requests)
Integer and floating point query functions
GetPixelTransformParameterivSGI and
GetPixelTransformParameterfvSGI are provided. must be
FFT_1D_SGI. must be MAX_FFT_WIDTH_SGI. The value of the
specified parameter is returned in .
Additions to the GLX Specification
None
GLX Protocol
None
Dependencies on EXT_convolution
If EXT_convolution is defined, then the post convolution scale and
bias enumerants POST_CONVOLUTION_RED_SCALE_EXT,
POST_CONVOLUTION_GREEN_SCALE_EXT, POST_CONVOLUTION_BLUE_SCALE_EXT,
POST_CONVOLUTION_ALPHA_SCALE_EXT, POST_CONVOLUTION_RED_BIAS_EXT,
POST_CONVOLUTION_GREEN_BIAS_EXT, POST_CONVOLUTION_BLUE_BIAS_EXT,
and POST_CONVOLUTION_ALPHA_BIAS_EXT are aliased with the
corresponding POST_TRANSFORM scale and biases in the obvious way.
The commands ConvolutionParameterfEXT, ConvolutionParameterfvEXT,
ConvolutionParameteriEXT, ConvolutionParameterivEXT,
GetConvolutionParameterfvEXT, and GetConvolutionParameterivEXT are
equivalent to the corresponding PixelTransformParameterfSGI,
PixelTransformParameterfvSGI, PixelTransformParameteriSGI,
PixelTransformParameterivSGI, GetPixelTransformParameterfvSGI, and
GetPixelTransformParameterivSGI commands and should be superseded
by the PixelTransform versions of the commands.
If EXT_convolution is not defined, then specifying CONVOLUTION_SGI for the
parameter to the command PixelTransformSGI will result in an
INVALID_OPERATION error.
Errors
INVALID_ENUM is generated if PixelTransformParameteriSGI,
PixelTransformParameterfSGI, PixelTransformParameterivSGI,
PixelTransformParameterfvSGI, GetPixelTransformParameterivSGI, or
GetPixelTransformParameterfvSGI parameter is not
FFT_1D_SGI.
INVALID_ENUM is generated if PixelTransformParameteriSGI,
PixelTransformParameterfSGI, PixelTransformParameterivSGI, or
PixelTransformParameterfvSGI, parameter is GL_FFT_1D_SGI, and
parameter is not TRANSPOSE_SGI.
INVALID_ENUM is generated if GetPixelTransformParameterivSGI,
or GetPixelTransformParameterfvSGI, parameter is GL_FFT_1D_SGI, and
parameter is not MAX_FFT_WIDTH_SGI or TRANSPOSE_SGI.
INVALID_VALUE is generated if the width, specified in DrawPixels,
TexImage1D or TexImage2D is less than zero, or greater than
MAX_FFT_WIDTH_SGI or not a power or two.
INVALID_OPERATION is generated if PixelTransformParameterfSGI,
PixelTransformParameterfvSGI, PixelTransformParameteriSGI,
PixelTransformParameterivSGI, GetPixelTransformParameterfvSGI, or
GetPixelTransformParameterivSGI is executed between execution of
Begin and the corresponding execution of End.
New State
Get Value Get Command Type Initial Value Attribute
--------- ----------- ---- ------------- ---------
POST_TRANSFORM_RED_SCALE_SGI GetFloatv R 1 pixel
POST_TRANSFORM_GREEN_SCALE_SGI GetFloatv R 1 pixel
POST_TRANSFORM_BLUE_SCALE_SGI GetFloatv R 1 pixel
POST_TRANSFORM_ALPHA_SCALE_SGI GetFloatv R 1 pixel
POST_TRANSFORM_RED_BIAS_SGI GetFloatv R 0 pixel
POST_TRANSFORM_GREEN_BIAS_SGI GetFloatv R 0 pixel
POST_TRANSFORM_BLUE_BIAS_SGI GetFloatv R 0 pixel
POST_TRANSFORM_ALPHA_BIAS_SGI GetFloatv R 0 pixel
PIXEL_TRANSFORM_OPERATOR_SGI GetIntegerv Z2 CONVOLUTION pixel
PIXEL_TRANSFORM_SGI IsEnabled B TRUE pixel/enable
New Implementation Dependent State
Get Value Get Command Type Minimum Value
--------- ----------- ---- -------------
MAX_FFT_WIDTH_SGI GetPixelTransformParameterivSGI 1 x Z+ 256