1Name 2 3 SGI_fft 4 5Name Strings 6 7 GL_SGI_fft 8 9Status 10 11 XXX - Not complete yet!!! 12 13Version 14 15 Last Modified Date: April 24, 2000 16 Author Revision: $Header: //depot/main/doc/registry/extensions/SGI/fft.spec#11 $ 17 18Number 19 20 99 21 22Dependencies 23 24 SGI_complex is required 25 SGI_complex_type is required 26 SGI_color_table affects the definition of this extension 27 EXT_convolution affects the definition of this extension 28 29Overview 30 31 The Fast Fourier Transform (FFT) is a set of efficient algorithms for 32 computing the discrete Fourier transform (DFT) that are based on the 33 fundamental principle of decomposing the computation of the Fourier 34 transform of a sequence into successively smaller discrete Fourier 35 transforms. 36 37 This extension defines complex to complex pixel formats 1-dimensional 38 fast Fourier transforms in the pixel transfer process. Pixel drawing, 39 reading and copying are all candidates for FFTs. Note that it is possible 40 to compute the forward DFT, inverse DFT, multi-dimensional DFT, real to 41 complex DFT, and any combination of the above efficiently, using the complex 42 to complex 1-dimensional forward FFT only. 43 44 The number of input elements must be a power of two. If the original 45 series size is not a power of two, the data can be padded with zeros or 46 resampled to meet this prerequisite. It is the user's responsibility to 47 satisfy this constraint. 48 49 FFT precision is implementation dependent. 50 51 This extension replaces the convolution block of the pixel pipeline 52 with a new pixel transform block. The pixel transform block 53 can be configured to be the convolution operation defined by the 54 EXT_convolution extension or the fft operation defined in this extension. 55 It also can be enabled or disabled all together. 56 57Issues 58 59 * some platforms (i.e Moosehead and MG) may initially only implement 1D and 60 2D FFT's, if this is the case, should we break up the 3D extension as a 61 separate one? Will these machines be forced to say that this extension 62 is not 'fully' supported if they do not implement 3D? 63 64 resolved: we will only support 1D ffts and allow later 65 expandibility to 2D and 3D. still need to resolve whether we 66 support 1D in row, column, and depth order on 2D and 3D images 67 to make it easier to build 2D and 3D ffts. 68 69 * We also have to take in account a possible broadening of the restricted 70 list of input sizes of powers of 2, to sizes whos prime factors are 2, 3, 71 and maybe even 5. The motivation is induced by standard video image sizes 72 that are not always powers of 2. The FFT of the zero padded series and 73 the FFT of the original series are not always equivalent 74 75 resolved: we will only support power of 2 input sizes 76 77 * 1D FFTs are defined on images of all dimensions. This is different from 78 the way CONVOLUTIONS are defined. We might need a parameter or name that 79 specifies in what dimension does a 1D FFT applied to an incoming n-D 80 image. 81 82 * we refer to the new pixel processing block which can be configured 83 as either convolution or fft as the pixel transform. Is there a better 84 name for this. 85 86 * it seems the way the spec is defined, that only way to disable the 87 scale and bias is to select convolve as the transform and use disable 88 the convolve using Disable. Is there a better way? 89 90 * Even though the algorithm is not described in the spec, this 91 knowledge might have some importance to the user, because 92 precision becomes a more important issue, and the size of the 93 FFT directly supported will typically be limited. In order to 94 provide operators that can be used as basic blocks for computing 95 larger size of FFTs, some extra parameters might be appropriate. 96 97 This is a low priority issue, as the suggested parameters can be added 98 later, if the need arises. 99 100 FFT_TYPE_UNKNOWN_SGI 101 FFT_TYPE_RADIX4_DIF_NIO_SGI 102 FFT_TYPE_RADIX4_DIT_NOO_SGI 103 104 DIF - Decimation in Frequency 105 DIT - Decimation in Time 106 NIO - Normal Input Order 107 NOO - Normal Output Order 108 109 The FFT_SORT_SGI parameter can be used to suppress sorting into digit 110 reverse order. 111 112 * The TRANSPOSE_SGI parameter can be used to transpose a 2-D image after 113 performing 1-D fft on the image rows before it is placed at the 114 destination color buffer, in order to expedite the 2-D fft. 115 116 HP has already an extension in effect, I'm told, that does those kind of 117 operations on images. It make sense to place it immediately before the 118 zoom operation. 119 120New Procedures and Functions 121 122 void PixelTransformSGI(enum target); 123 124 void PixelTransformParameterfSGI(enum target, 125 enum pname, 126 float param); 127 128 void PixelTransformParameterfvSGI(enum target, 129 enum pname, 130 const float* params); 131 132 void PixelTransformParameteriSGI(enum target, 133 enum pname, 134 int param); 135 136 void PixelTransformParameterivSGI(enum target, 137 enum pname, 138 const int* params); 139 140 void GetPixelTransformParameterfvSGI(enum target, 141 enum pname, 142 float* params); 143 144 void GetPixelTransformParameterivSGI(enum target, 145 enum pname, 146 int* params); 147 148New Tokens 149 150 Accepted by the <target> parameter of PixelTransformSGI: 151 152 CONVOLUTION_SGI 0x81C5 153 FFT_1D_SGI 0x81C6 154 155 Accepted by the <pname> parameter of GetBooleanv, GetIntegerv, GetFloatv, 156 and GetDoublev: 157 158 PIXEL_TRANSFORM_OPERATOR_SGI 0x81C4 159 160 Accepted by the <cap> parameter of Enable, Disable, and IsEnabled, 161 and by the <pname> parameter of GetBooleanv, GetIntegerv, GetFloatv, 162 and GetDoublev: 163 164 PIXEL_TRANSFORM_SGI 0x81C7 165 166 Accepted by the <pname> parameter of GetPixelTransformParameterfvSGI 167 and GetPixelTransformParameterivSGI: 168 169 MAX_FFT_WIDTH_SGI 0x81C8 170 171 Accepted by the <pname> parameter of PixelTransferi, PixelTransferf, 172 and by the <pname> parameter of GetBooleanv, GetIntegerv, GetFloatv, 173 and GetDoublev: 174 175 POST_TRANSFORM_RED_SCALE_SGI ???? 176 POST_TRANSFORM_GREEN_SCALE_SGI ???? 177 POST_TRANSFORM_BLUE_SCALE_SGI ???? 178 POST_TRANSFORM_ALPHA_SCALE_SGI ???? 179 POST_TRANSFORM_RED_BIAS_SGI ???? 180 POST_TRANSFORM_GREEN_BIAS_SGI ???? 181 POST_TRANSFORM_BLUE_BIAS_SGI ???? 182 POST_TRANSFORM_ALPHA_BIAS_SGI ???? 183 184 *Note* - values defined in the spec, but not documented below 185 186 SORT_SGI = 0x81C9 187 TRANSPOSE_SGI = 0x81CA 188 189Additions to Chapter 2 of the OpenGL Specification (OpenGL Operation) 190 191 None 192 193Additions to Chapter 3 of the OpenGL Specification (Rasterization) 194 195 The specification of pixel operators is added to the GL Specification in 196 section 3.6.2, "Pixel Transfer Modes." 197 198 The operations of the pixel transforms are added to the GL Specification in 199 section 3.6.3, "Rasterization of Pixel Rectangles, immediately following the 200 subsection "Index Lookup", and immediately prior to the operations described 201 by EXT_histogram. Transforms are enabled, disabled, and queried by calling 202 Enable, Disable and IsEnabled respectively. The pixel transform is enabled 203 by default. A particular transform is selected by calling PixelTransformSGI 204 with the <target> parameter set to one of: CONVOLUTION_SGI, or FFT_1D_SGI. 205 The pixel transform is performed only for RGBA groups, though these groups 206 may have been specified as color indexes and converted to RGBA by index 207 table lookup. 208 209 The convolution transform is described in the EXT_convolution 210 specification. 211 212 If pixel transform is enabled and FFT_1D_SGI is selected, the 1-dimensional 213 fft is applied to the image passed to TexImage1D, and to 1-dimensional 214 textures queried by GetTexImage. It is applied on a per-row basis to 215 the 2-dimensional images passed to DrawPixels, CopyPixels, ReadPixels, 216 TexImage2D, TexSubImage2DEXT, CopyTexImage2DEXT, CopyTexSubImage2DEXT, 217 and to 2-dimensional images queried by GetTexImage. It is also applied 218 on a per-row basis to the 3-dimensional images passed to CopyTexSubImage3DEXT, 219 TexImage3DEXT, and TexSubImage3DEXT, and to 3-dimensional images queried by 220 GetTexImage. 221 222 The discrete fourier transform is a complex valued sum of products of 223 source image pixels and the discretely sampled function exp(2PIikn/N). 224 [exp(2PIix) == sin(x)+icos(x)] 225 226 Source image pixels always have four components: red, green, blue, 227 and alpha. Individual color components of each source image pixel 228 are always independently processed as part of the transform. 229 The discrete fourier transform is defined differently for each of 230 the three transform types. In the following equations the 231 232 SUM{}{}equation 233 234 notation indicates the sum of the equation evaluated for all 235 combinations of conditions indicated within the curly brackets. The 236 variables Ws, Hs, and Ds refer to the dimensions of the source 237 pixel image. 238 239 The discrete fourier transform equation is: 240 241 1-dimensional transform: 242 243 C[n] = SUM{k = 0 through Ws-1} 244 245 Cs[k]*exp(2PIikn/Ws) 246 247 The inverse transform equation is: 248 249 1-dimensional transform: 250 251 C[n] = SUM{k = 0 through Ws-1} 252 253 Cs[k]*exp(-2PIikn/Ws) 254 ----- 255 Ws 256 257 The particular fft algorithm is left unspecified to allow greater 258 flexibility for implementations. 259 260 If a pixel transform operation is performed, the resulting image is scaled 261 and biased by parameters specified using the PixelTransfer command. 262 These operations are: 263 264 red = red * POST_TRANSFORM_RED_SCALE_SGI 265 + POST_TRANSFORM_RED_BIAS_SGI 266 267 green = green * POST_TRANSFORM_GREEN_SCALE_SGI 268 + POST_TRANSFORM_GREEN_BIAS_SGI 269 270 blue = blue * POST_TRANSFORM_BLUE_SCALE_SGI 271 + POST_TRANSFORM_BLUE_BIAS_SGI 272 273 alpha = alpha * POST_TRANSFORM_ALPHA_SCALE_SGI 274 + POST_TRANSFORM_ALPHA_BIAS_SGI 275 276 If no fft operation is performed, the scale and bias are not 277 performed either. 278 279 280Additions to Chapter 4 of the GL Specification (Per-Fragment Operations 281and the Framebuffer) 282 283 The operation of fft during pixel copy and query operations is 284 identical to the operation during pixel drawing and texture image 285 definition. 286 287Additions to Chapter 5 of the GL Specification (Special Functions) 288 289 Commands GetPixelTransformParameterfvSGI and 290 GetPixelTransformParameterivSGI are not include in display lists. 291 They are always executed immediately. 292 293Additions to Chapter 6 of the GL Specification (State and State Requests) 294 295 Integer and floating point query functions 296 GetPixelTransformParameterivSGI and 297 GetPixelTransformParameterfvSGI are provided. <target> must be 298 FFT_1D_SGI. <pname> must be MAX_FFT_WIDTH_SGI. The value of the 299 specified parameter is returned in <params>. 300 301Additions to the GLX Specification 302 303 None 304 305GLX Protocol 306 307 None 308 309Dependencies on EXT_convolution 310 311 If EXT_convolution is defined, then the post convolution scale and 312 bias enumerants POST_CONVOLUTION_RED_SCALE_EXT, 313 POST_CONVOLUTION_GREEN_SCALE_EXT, POST_CONVOLUTION_BLUE_SCALE_EXT, 314 POST_CONVOLUTION_ALPHA_SCALE_EXT, POST_CONVOLUTION_RED_BIAS_EXT, 315 POST_CONVOLUTION_GREEN_BIAS_EXT, POST_CONVOLUTION_BLUE_BIAS_EXT, 316 and POST_CONVOLUTION_ALPHA_BIAS_EXT are aliased with the 317 corresponding POST_TRANSFORM scale and biases in the obvious way. 318 The commands ConvolutionParameterfEXT, ConvolutionParameterfvEXT, 319 ConvolutionParameteriEXT, ConvolutionParameterivEXT, 320 GetConvolutionParameterfvEXT, and GetConvolutionParameterivEXT are 321 equivalent to the corresponding PixelTransformParameterfSGI, 322 PixelTransformParameterfvSGI, PixelTransformParameteriSGI, 323 PixelTransformParameterivSGI, GetPixelTransformParameterfvSGI, and 324 GetPixelTransformParameterivSGI commands and should be superseded 325 by the PixelTransform versions of the commands. 326 327 If EXT_convolution is not defined, then specifying CONVOLUTION_SGI for the 328 <target> parameter to the command PixelTransformSGI will result in an 329 INVALID_OPERATION error. 330 331Errors 332 333 INVALID_ENUM is generated if PixelTransformParameteriSGI, 334 PixelTransformParameterfSGI, PixelTransformParameterivSGI, 335 PixelTransformParameterfvSGI, GetPixelTransformParameterivSGI, or 336 GetPixelTransformParameterfvSGI parameter <target> is not 337 FFT_1D_SGI. 338 339 INVALID_ENUM is generated if PixelTransformParameteriSGI, 340 PixelTransformParameterfSGI, PixelTransformParameterivSGI, or 341 PixelTransformParameterfvSGI, parameter <target> is GL_FFT_1D_SGI, and 342 parameter <pname> is not TRANSPOSE_SGI. 343 344 INVALID_ENUM is generated if GetPixelTransformParameterivSGI, 345 or GetPixelTransformParameterfvSGI, parameter <target> is GL_FFT_1D_SGI, and 346 parameter <pname> is not MAX_FFT_WIDTH_SGI or TRANSPOSE_SGI. 347 348 INVALID_VALUE is generated if the width, <x> specified in DrawPixels, 349 TexImage1D or TexImage2D is less than zero, or greater than 350 MAX_FFT_WIDTH_SGI or not a power or two. 351 352 INVALID_OPERATION is generated if PixelTransformParameterfSGI, 353 PixelTransformParameterfvSGI, PixelTransformParameteriSGI, 354 PixelTransformParameterivSGI, GetPixelTransformParameterfvSGI, or 355 GetPixelTransformParameterivSGI is executed between execution of 356 Begin and the corresponding execution of End. 357 358 359New State 360 361 Get Value Get Command Type Initial Value Attribute 362 --------- ----------- ---- ------------- --------- 363 POST_TRANSFORM_RED_SCALE_SGI GetFloatv R 1 pixel 364 POST_TRANSFORM_GREEN_SCALE_SGI GetFloatv R 1 pixel 365 POST_TRANSFORM_BLUE_SCALE_SGI GetFloatv R 1 pixel 366 POST_TRANSFORM_ALPHA_SCALE_SGI GetFloatv R 1 pixel 367 POST_TRANSFORM_RED_BIAS_SGI GetFloatv R 0 pixel 368 POST_TRANSFORM_GREEN_BIAS_SGI GetFloatv R 0 pixel 369 POST_TRANSFORM_BLUE_BIAS_SGI GetFloatv R 0 pixel 370 POST_TRANSFORM_ALPHA_BIAS_SGI GetFloatv R 0 pixel 371 PIXEL_TRANSFORM_OPERATOR_SGI GetIntegerv Z2 CONVOLUTION pixel 372 PIXEL_TRANSFORM_SGI IsEnabled B TRUE pixel/enable 373 374New Implementation Dependent State 375 376 Get Value Get Command Type Minimum Value 377 --------- ----------- ---- ------------- 378 MAX_FFT_WIDTH_SGI GetPixelTransformParameterivSGI 1 x Z+ 256 379