OK, so for anybody who knows about such things... Would it be feasible 
to render an Iterated Function System image using a GPU? And would it be 
any faster than using the CPU?

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> OK, so for anybody who knows about such things... Would it be feasible 
> to render an Iterated Function System image using a GPU? And would it be 
> any faster than using the CPU?

  From the little I know, Pixel Shader Model 3 supports branching and
looping, so I assume it might be possible to create a pixel shader which
colors pixels according to an iterated function system.

  However, if I'm not completely mistaken, pixel shaders are calculated
on a specific pixel and cannot re-use previous calculations from other
pixels which have been calculated with a pixel shader (because else it
would make parallelizing pixel shaders extremely difficult, if not
impossible). Thus you are limited to making a pixel shader routine
which is calculated on a per-pixel basis, without input from other
pixels.
  I assume that this means that you cannot create a pixel shader which
jumps around the screen and draws pixels here and there, as most IFS
fractals do. You are limited to calculate on single pixels, like for
example how the basic Mandelbrot set is calculated.

  Assuming it is indeed possible to implement some IFS fractals with
pixel shaders, then it may indeed be much faster than with the CPU.
That's because modern display cards can run a fair amount of shaders
in parallel.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

>   From the little I know, Pixel Shader Model 3 supports branching and
> looping, so I assume it might be possible to create a pixel shader which
> colors pixels according to an iterated function system.
> 
>   However, if I'm not completely mistaken, pixel shaders are calculated
> on a specific pixel and cannot re-use previous calculations from other
> pixels which have been calculated with a pixel shader (because else it
> would make parallelizing pixel shaders extremely difficult, if not
> impossible). Thus you are limited to making a pixel shader routine
> which is calculated on a per-pixel basis, without input from other
> pixels.
>   I assume that this means that you cannot create a pixel shader which
> jumps around the screen and draws pixels here and there, as most IFS
> fractals do. You are limited to calculate on single pixels, like for
> example how the basic Mandelbrot set is calculated.

That seems like a reasonable assessment to me.

I wonder if you could attempt this using the Copy Game rather than the 
Chaos Game? That is, start with a white screen, apply each 
transformation to it seperately, merge the frame buffers back together, 
and then repeat. Do this enough times and the shape on the screen is 
guaranteed to converge to the attractor of the system. If you implement 
the "merging" state correctly, you can even get density information.

The fatal problem with this method is that it utterly fails if the 
entire attractor does not fit on the screen. For attractors involving, 
say, infinitely long lines, this method can never work properly.

Also, how about random number generation? Is this "easy" to do on a GPU?

Could you do something like rendering millions of tiny semi-transparent 
polygons of roughly 1-pixel size?

Does a GPU provide any way to procedurally render texture bitmaps that 
might allow a histogram to be built?

Asside from all that, presumably you'd have to go with some kind of 
GPGPU solution such as CUDA. Again, I'm not sure how well the GPU memory 
architecture is going to play with that; I haven't looked at the numbers.

>   Assuming it is indeed possible to implement some IFS fractals with
> pixel shaders, then it may indeed be much faster than with the CPU.
> That's because modern display cards can run a fair amount of shaders
> in parallel.

This was my feeling...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> Also, how about random number generation? Is this "easy" to do on a GPU?

  Even if pixel shaders didn't have some RNG available (I don't know if
they have), a simple linear congruential generator should be rather
trivial to implement.

  (OTOH that means that the LCG would have to store the seed somewhere
so that the next time the shader is called it can use it. Again, I don't
know if that's possible. There could well be parallelism problems with
that.)

> Could you do something like rendering millions of tiny semi-transparent 
> polygons of roughly 1-pixel size?

  Why would you want to do that? There's no need. A pixel shader determines
the color of a screen pixel, so what else do you need? AFAIK, you don't even
need any polygons in order to fill the screen with the products of a pixel
shader (or you need at most one).

  (The idea of pixel shaders is that if they are attached to a polygon,
when that polygon is projected on screen, each of the pixels of this
projection is colored according to the shader. The shader has tons of
information available from that polygon and other data in order to
determine the color of the pixel.)

  If what you want to do is to fill the screen with data in progressive
steps, graphics cards support that. They have stencil buffers and other
similar techniques for additive drawing.

-- 
                                                          - Warp

Post a reply to this message

Orchid XP v8 wrote:
> OK, so for anybody who knows about such things... Would it be feasible 
> to render an Iterated Function System image using a GPU? And would it be 
> any faster than using the CPU?
> 

As long as you can break down your function so that a single step is 
performed on the entire screen at once, then you can.

Ie, you can do function f() on all pixels, store the output in a buffer, 
and use that buffer as the input in the next step.

If you have to perform varying steps on individual pixels, you get 
problems.  As in, if you go f() then g() then h() on one pixel, then 
only g() and h() on its neighbor, then only f() and h() on a third, this 
won't work.

The same instructions have to be run on the whole screen (well, the 
whole polygon - for what you're asking about, I would just draw a quad 
to the whole screen).

...Chambers

Post a reply to this message

I haven't done any GPU programming myself, but from what I've gathered 
from friends who have modern GPUs are essentially fully programmable 
architectures these days, so you can use them to boost the speed of 
computations which have seemingly little to do with actually displaying 
things on the screen (for instance, I believe that folding@home can use 
the GPU).

It probably depends on what graphics card you have as to weather or not 
you can do this on it, but you might take a look at CUDA, a C compiler 
revently released by nvidia that allows you to write things for the GPU:

http://www.nvidia.com/object/cuda_learn.html

You'll, of course, need to design your IFS algorithm so that it can be 
run in a highly parallel manner, but unless I'm missing something that 
should be pretty straightforward in this case (just run multiple 
iterators simultaneously).  Of course, not having ever done this sort of 
thing increases the chances that I'll have missed something :-)


Orchid XP v8 wrote:
> OK, so for anybody who knows about such things... Would it be feasible 
> to render an Iterated Function System image using a GPU? And would it be 
> any faster than using the CPU?
>

Post a reply to this message

> OK, so for anybody who knows about such things... Would it be feasible to 
> render an Iterated Function System image using a GPU? And would it be any 
> faster than using the CPU?

Yes, and yes it would be much faster.  Sometimes you need to think a bit 
before implementing such a thing though...

I would run several points through the IFS in parallel.  Say, 2^16 points. 
Create two 256x256 textures of floats, one to hold the X coordinates and one 
to hold the Y coordinates of all your points.

Then write two pixel shaders, one to calculate the new X coordinate, and one 
to create the new Y coordinate.

Then, for each pass, set the current X and Y textures and inputs, and render 
to the newX texture.  Render again to the newY texture with the other pixel 
shader.

Now, here comes the clever bit.  After you've generated the new XY textures, 
you now run a *vertex* shader with 2^16 quads.  THe vertex shader looks up 
the XY values from the texture for each quad and translates the quad to that 
position.  You can then just use a fairly normal pixel shader to increment 
the pixel value on the screen, or some off-screen texture.

It should run pretty fast, and don't forget you're doing 64k points in 
parallel so it should outrun the CPU by a huge factor.

Post a reply to this message

Kevin Wampler wrote:

> It probably depends on what graphics card you have as to weather or not 
> you can do this on it, but you might take a look at CUDA, a C compiler 
> revently released by nvidia that allows you to write things for the GPU:

Yeah, CUDA seems the obvious way to do this.

Unfortunately, only GeForce 8 and newer support this technology. I have 
a GeForce 7900GT. :-(

(Also... I get the impression you need Vista for the GeForce 8 to work.)

> You'll, of course, need to design your IFS algorithm so that it can be 
> run in a highly parallel manner, but unless I'm missing something that 
> should be pretty straightforward in this case (just run multiple 
> iterators simultaneously).  Of course, not having ever done this sort of 
> thing increases the chances that I'll have missed something :-)

There are 3 processes that need to happen.

1. A stream of coordinates needs to be generated.
2. A histogram of the coordinates needs to be constructed.
3. A non-linear mapping from histogram frequencies to colours is performed.

Step 2 looks to be the tricky one - but it shouldn't be *vastly* 
difficult I think. The question is whether the histograms will fit into 
the limited RAM on the card...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Chambers wrote:

> As long as you can break down your function so that a single step is 
> performed on the entire screen at once, then you can.

This is the program. An IFS image is essentially a histogram plot. You 
can't just compute each pixel's colour independently.

OOC, is it possible to use a GPU to copy and transform chunks of video 
data? (E.g., rotate, scale, that kind of thing.)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

scott wrote:

> Yes, and yes it would be much faster.  Sometimes you need to think a bit 
> before implementing such a thing though...
> 
> I would run several points through the IFS in parallel.  Say, 2^16 
> points. Create two 256x256 textures of floats, one to hold the X 
> coordinates and one to hold the Y coordinates of all your points.
> 
> Then write two pixel shaders, one to calculate the new X coordinate, and 
> one to create the new Y coordinate.
> 
> Then, for each pass, set the current X and Y textures and inputs, and 
> render to the newX texture.  Render again to the newY texture with the 
> other pixel shader.
> 
> Now, here comes the clever bit.  After you've generated the new XY 
> textures, you now run a *vertex* shader with 2^16 quads.  THe vertex 
> shader looks up the XY values from the texture for each quad and 
> translates the quad to that position.  You can then just use a fairly 
> normal pixel shader to increment the pixel value on the screen, or some 
> off-screen texture.
> 
> It should run pretty fast, and don't forget you're doing 64k points in 
> parallel so it should outrun the CPU by a huge factor.

Uuhhh... any chance of some code? :-}

(Also... what's a vertex shader?)

Would it be possible to do all this using just, say, OpenGL? So far the 
approaches I've considered would all require CUDA, which obviously works 
*only* for certain GPUs.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message