6
$\begingroup$

(I've largely revamped this entire question, though the motivation remains the same.)

revised question

I want to convert a raster of cartesian pixels into polar pixels. Is there a sensible algorithm for doing this? For example, how do I compute the value of the shaded (polar) pixel in the image below, given the value of the three (cartesian) pixels that it overlaps?

enter image description here

original question

Is there a reasonable way to compute the area of the intersection of a square and an annular section, as shown in the orange section below?

enter image description here

The motivation: I have a raster of square pixels, and I'm converting it to "polar pixels" -- I want to find out the contribution of each cartesian pixel to each polar pixel.

$\endgroup$
  • $\begingroup$ the alignment of your left border of the toroidal slice with the rectangle axis is purely coincidental ? $\endgroup$ – v.oddou Jun 22 '16 at 1:42
  • 1
    $\begingroup$ Is this a coverage calculation? Why would you choose to implement a very ineficient box filter? $\endgroup$ – joojaa Jun 22 '16 at 5:44
  • $\begingroup$ @joojaa Agree but if it makes it easier, an approx, say, Gaussian could be built from a few of these coverage calculations. $\endgroup$ – Simon F Jun 22 '16 at 8:33
  • 1
    $\begingroup$ @trichoplax: points well taken! I'll take down the question on Maths.SE - thank you for that guidance. $\endgroup$ – fearless_fool Jun 22 '16 at 14:52
  • 2
    $\begingroup$ Something like that. Box filtering in general is the worst filter you could choose. Pixels are not really squares but point samples (read a pixel is not a square x 3) By using a standard function reconstruction you can do the same with a finite sampling which results in a better image than a box filter would with less work since your box filtering algorithm is so incredibly convoluted and expensive. $\endgroup$ – joojaa Jun 22 '16 at 15:08
6
$\begingroup$

I have implemented the cartesian-to-polar-conversion and have used different interpolation methods:

1) nearest neighbor

2) a subsampling approach, which averages 81 subpixel locations

3) bilinear interpolation

The 2nd row in the image below shows detail magnifications of the output for the three approaches:

enter image description here

Here is the GLSL shader code for approach 1 and 3:

precision mediump float;
varying vec2 tc; // texture coordinate of current output pixel
uniform sampler2D inputImg; // input image
const float PI = 3.141592653589793238462643383;
void main() {
  float phi = tc.x; // phi is x-direction in output
  float r = tc.y;   // radius is y-direction in output
  float xx = r * cos(2.0 * PI * phi);  // unit circle in range [-1.0, 1.0]
  float yy = r * sin(2.0 * PI * phi);
  float x = xx * 0.5 + 0.5; // input texture coordinate in range [0.0, 1.0];
  float y = yy * 0.5 + 0.5;
  gl_FragColor = texture2D(inputImg, vec2(x,y));
}

This is the GLSL shader code for approach 2:

precision mediump float;
varying vec2 tc; // texture coordinate of current output pixel
uniform sampler2D inputImg; // input image
uniform int outputWidth; // width of output image
uniform int outputHeight; // height of output image
const float PI = 3.141592653589793238462643383;
const int samplesPerSide = 4;
void main() {
  int samplesPerDirection = samplesPerSide * 2 + 1;
  // compute size of subsample step in texture coordinates
  float sampleStepX = 1.0 / float(outputWidth * samplesPerDirection); 
  float sampleStepY = 1.0 / float(outputHeight * samplesPerDirection);
  vec4 sampleSum = vec4(0); // init sum to zero
  for(int i = -samplesPerSide; i <= samplesPerSide; i++) {
    for(int j = -samplesPerSide; j <= samplesPerSide; j++) {
      float phi = tc.x + float(i) * sampleStepX; // phi is x-direction in output
      float r = tc.y + float(j) * sampleStepY;   // radius is y-direction in output
      float xx = r * cos(2.0 * PI * phi);  // unit circle in range [-1.0, 1.0]
      float yy = r * sin(2.0 * PI * phi);
      float x = xx * 0.5 + 0.5; // input texture coordinate in range [0.0, 1.0];
      float y = yy * 0.5 + 0.5;
      sampleSum += texture2D(inputImg, vec2(x,y));
    }
  }
  gl_FragColor += sampleSum / float(samplesPerDirection * samplesPerDirection);
}

Approach 2, which is approx. factor 81 slower than 1 and 3, is probably the one you are looking for but I also like the bilinear interpolation result.

With a WebGL capable browser you can try out these implementations here:

https://www.gsn-lib.org/index.html#projectName=CartesianToPolar&graphName=CartesianToPolar

$\endgroup$
  • $\begingroup$ Beautifully answered. And rendered. Thanks. $\endgroup$ – fearless_fool Jul 1 '16 at 23:24
  • $\begingroup$ Use a indented block for code in future please. Nice answer $\endgroup$ – joojaa Jul 2 '16 at 7:14
0
$\begingroup$

I called up an old officemate and CG expert, and after asking me a few questions he offered a simple solution. I may have mangled a few details, but the basic idea follows:

Subsample the polar coordinates to whatever degree of accuracy needed, treating each subsample as a point. It's then trivial to find the cartesian pixel that contains each point. Sum up the sub-sampled points for each polar pixel to get its final value.

There's some subtlety in getting the weights right -- the guiding insight is that if the entire cartesian raster is flat gray, then each polar pixel should each have the same grayscale value. And you could add on lots of other nuances, but the basic technique is intuitively and computationally straightforward.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.