Simple anti aliasing / supersampling help!

[richardrosenman]

Hey gang;

I've been trying to understand anti aliasing a bit more lately, especially in my fractals, and I am a bit stuck. I've been putting together a simple Fern Fractal program for which I am trying to implement aa to no avail. I understand the principle of supersampling (generate a larger image and then downsample to the current resolution) and I have managed to implement it into my Mandelbrot using the following theory:


for (y = 0; y < yres; ++y)
for (x = 0; x < xres; ++x)
{
   float r = 0.0f, g = 0.0f, b = 0.0f;

   for (v = 0; v < supersample_factor; ++v)
   for (u = 0; u < supersample_factor; ++u)
   {
      float fx = float(x) + float(u) / float(supersample_factor);
      float fy = float(y) + float(v) / float(supersample_factor);

      colour eval = pixel_function(fx,fy);

      r += eval.r;
      g += eval.g;
      b += eval.b;
   }

   r /= float(supersample_factor * supersample_factor);
   g /= float(supersample_factor * supersample_factor);
   b /= float(supersample_factor * supersample_factor);

   imagedata[y * xres + x].set(r,g,b);
}


This was easy because the Mandelbrot is drawn pixel by pixel such as in the example above.

However, with the Fern Fractal, only a number of iterations are processed instead and those pixels are the only ones output so I don't understand how to supersample a fractal in this type of circumstance. This applies to a large number of other fractals such as Lorenz attractors, etc, so I would like to figure it out. Here is my source code below without any supersampling attempts. I am hoping someone can help me understand how to implement supersampling into such a fractal by modifying my  pseudo code below (this is how I learn best):


for(itr = 0; itr < maxitr; itr++)
{
random=rnd(0,100);

  if (random<=1)
   {
   x1 = 0;
       y1 = 0.16 * y0;
   }
  else
   {
      if (random <= 7)
      {
            x1 = 0.2 * x0 - 0.26 * y0;
            y1 = 0.23 * x0 + 0.22 * y0;
            }
     else
       {
         if (random <= 14)
         {
              x1 = -0.15 * x0 + 0.28 * y0;
              y1 = 0.26 * x0 + 0.24 * y0 + 0.44;
              }
        else
              {
              x1 = 0.85 * x0 + 0.04 * y0;
              y1 = -0.004 * x0 + 0.85 * y0 + 1.6;
              }
      }
   }

i = Y - (int)(y1 * (35.0/scaleFactor));
j = X / 2  + (int)(x1 * (35.0/scaleFactor));


if (i>=0 && i<=Y && j>=0 && j<=X)
psetp(j,i,color);

x0 = x1;
y0 = y1;

} //itr


Any help would be highly appreciated!

-Rich

[lycium]

hmmm that first block of code sure does look familiar 

i don't see the problem here - render the image bigger, then size it down as you say. it's true that you lose the convenience of not having to actually store the intermediate data with IFS, but them's the breaks with such an algorithm. fortunately it's 2011 and we all have 8gb+ in our computers, right? (i've had 12gb since 2008, it's nothing exotic)

[lycium]

ps. using random numbers in range 0 to 100 is just plain weird  what do computers know about the decimal number system?

[richardrosenman]

Darn. So there's no way to supersample and render it all in one pass? There must be... It's unfortunate because in creating an app, you want one that can produce the best output as opposed to making the user perform multiple operations such as rendering oversize and then downsampling.

If there is no way to supersample such an algorithm, is it possible to render this fractal using another algorithm that would be more subjective to antialiasing?

Yes, that pseudo code was from your other thread and it helped me tremendously in understanding how supersampling works. Hopefully, we can figure out how to make it adaptable to this type of algorithm!

Once again, any suggestions would be highly appreciated!

Rich

[lycium]

for certain restricted classes of IFS (eg. purely linear, like the fern and sierpinski) you can invert the transformations and switch to an escape time algorithm, thereby turning the problem into pixel sampling again.

however, for the most interesting IFS (nonlinear, more general) this doesn't work, and it's brute force supersampling all the way. you could devise a special image storage format that recursively subdivides the image into stored vs not-stored regions to try to economise on storage, but i would say this is a bad idea.

seriously: have you looked at memory prices recently?

[richardrosenman]

Ok Lycium;

Thank you for that thorough reply. Let me ponder over what you wrote and think about alternatives.

-Rich

[Softology]

The way I do it for IFS types etc is to use an internal array large enough to store the oversampled pixels.

eg if your image is width by height, then make your array width*samplepixels by height*samplepixels

Then once you have iterated a million points or so each on screen pixel is colored by averaging the oversampled grid locations.  For supersample_factor of 3, you would average 9 colors from the array for each on screen pixel.

This saves you having to render to a larger bitmap file on the hard drive and then downsample with photoshop etc.  You get too see the supersampled version directly on screen as it is being generated.

Jason.