Logo by AGUS - Contribute your own Logo!

END OF AN ERA, FRACTALFORUMS.COM IS CONTINUED ON FRACTALFORUMS.ORG

it was a great time but no longer maintainable by c.Kleinhuis contact him for any data retrieval,
thanks and see you perhaps in 10 years again

this forum will stay online for reference
News: Check out the originating "3d Mandelbulb" thread here
 
*
Welcome, Guest. Please login or register. November 30, 2025, 11:40:40 AM


Login with username, password and session length


The All New FractalForums is now in Public Beta Testing! Visit FractalForums.org and check it out!


Pages: [1]   Go Down
  Print  
Share this topic on DiggShare this topic on FacebookShare this topic on GoogleShare this topic on RedditShare this topic on StumbleUponShare this topic on Twitter
Author Topic: Kaleidoscopis IFS - using Hart's method ?  (Read 2997 times)
0 Members and 1 Guest are viewing this topic.
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« on: July 28, 2010, 01:35:58 AM »

Hi all,

Have just been considering if it's possible to convert the kaleidoscopic IFS method to using a version of LRIFS (language restricted IFS) because if a method can be derived then kaleido IFS fractals can be rendered much faster using Hart's method than they can using distance estimation.

The stumbling block is the conditional use of "abs" but I was wondering if this could be accounted for using LRIFS by using two alternative transforms for each case where "abs" may be applied - i.e. 8 different transforms for each original where abs is applied in 3 dimensions independantly. However just doing that would just produce a horrible mess with a fractal of much higher dimension than the original so some way would be required to restrict which of the transforms should actually be applied at each depth and I can't see how to do that so it correctly mirrors the distance estimation method.

Anyone any ideas ?

I should add it's definitely worth investigating as for the types of kaleido IFS currently being rendered (without mixing with Mandelbulbs or whatever) I'd guess Hart's method would be at least 10 times faster on a CPU - not sure about a GPGPU.

Really just an idle thought at the moment - will probably give it some more thought at the weekend wink
Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #1 on: July 28, 2010, 01:54:48 AM »

OK, should have thought a bit more before posting smiley

I forgot that Hart's method involves transforming *both* a base point and a direction vector, I was thinking in terms of just the direction vector smiley

Unfortunately that doesn't help an awful lot because although it does mean that we could restrict the transforms used based on the value of the point at each depth, the point concerned is not the same as the point tested using the distance estimation method so although modifying the transforms allowed based on the signs of the point coords will produce something, it probably won't match the DE method fractal.
Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
Jesse
Download Section
Fractal Schemer
*
Posts: 1013


« Reply #2 on: July 28, 2010, 11:49:22 PM »

Hi David,

can you point me to a reference of Hart's method?
Have not found anything helpful yet.

Although i dont think that a speedup of  factor 10 is possible  wink
...because the 'analytic' function, or whatever it is called, with just scaling a 4th var for the DE is pretty fast,
speaking in terms of DE methods. But who knows...
Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #3 on: July 29, 2010, 04:37:45 AM »

Hi David,

can you point me to a reference of Hart's method?
Have not found anything helpful yet.

Although i dont think that a speedup of  factor 10 is possible  wink
...because the 'analytic' function, or whatever it is called, with just scaling a 4th var for the DE is pretty fast,
speaking in terms of DE methods. But who knows...

Hi Jesse, unfortunately I'm very disorganised so I can't find the original link or even the document I downloaded - I think lycium gave me one of the relevant links if I remember correctly.

However Hart's method is very simple:

For each pixel we start with a base point for the viewing ray, a direction vector for the viewing ray and a start and end offset (distance along the ray) that defines a line segment for collision testing with the fractal.
We test the initial ray against our bounding volume for the fractal (e.g. defined by centre coordinate and radius) and if tthe line segment meets the bounding volume (sphere) then we enter the IFS tree and transform the base point and direction vector by the (divergent) transforms (using a full tree) at each stage testing to see if the newly transformed line segment still interstects the bounding volume, if not then we proceed no further down that branch of the IFS tree, otherwise we continue until we reach either a given depth in the tree and/or the overall scale factor applied reaches a given threshold - obviously at each stage of intersection with the bounding volume we can limit the line segment further to the line segment within the bounding volume i.e. modify the line segment start and end offsets.

That's essentially it - hopefully you can figure out the detail smiley

As to the 10* speed-up, maybe that's a little over-optimistic but I'd definitely expect 5* - for example my implimentation of Hart's method in UF renders the Menger Sponge in 13.2 secs on my system compared to over a minute using distance estimation in UF on the same system.
Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
knighty
Fractal Iambus
***
Posts: 819


« Reply #4 on: July 29, 2010, 12:39:49 PM »

Hi,

Here is the link to papers page of Pr. Hart. Azn

@David: I think that kaleidoscopic IFS are not RIFS. I'm not sure because I can't prove it  grin. In KIFS, the symmetry planes are visible wich give it a kaleidocope look. RIFS don't show this "feature" as far as I know. Obviously, some RIFS (like Sierpinski polyhedrons and Menger sponge) are also KIFS.

These last days, I was thinking about a raytracing method similar to Hart's algorithm. Haven't yet implemented it so still not sure if it works. Here is it's outline (fingers crossed  hurt):
let Ray(origin, direction) the ray we are tracing.
let d the current distance on the current ray.
let cscale=1;(cscale is the current scale factor)
 Let IRay=Ray; i=0;
 While (i<maxiter){
   Let O=intersection point of IRay and the bounding volume (usually a sphere) of the fractal;
   Let deltaD= distance(O,origin(IRay))/cscale;
   Let d=d+deltaD;
   if(deltaD<epsilon) break;
   Let O be the new origin of IRay.
   Apply KIFS's transforms (rotations, reflections and scaling) to IRay's origin and direction. (of course, IRay's direction should not be translated or scale, only rotated and reflected)
   cscale=cscale*KIFS_scale_factor;
   i=i+1;
 }
intersection point of Ray and the fractal should be = origin(Ray)+direction(Ray)*d.

Unlike Hart's algorithm, you don't need any kind of stack here.
Logged
knighty
Fractal Iambus
***
Posts: 819


« Reply #5 on: July 29, 2010, 04:30:49 PM »

 hurt hurt hurt
Sorry! it doesn't work. My fault!
In fact, recursion is needed. I'll check twice te next time before posting.  embarrass
Logged
Jesse
Download Section
Fractal Schemer
*
Posts: 1013


« Reply #6 on: July 29, 2010, 08:41:56 PM »

Thank you David and Knighty, that is a great link  smiley

So in Hart's method we only use one iteration loop for each ray, and have to use a different kind of formula...

Is it possible that incendia uses also Hart's method?
I have no experience with incendia, but some results i have seen looks like they uses a method that differs from escape time fractals and have some nice possibilities ETF's dont have.

However, i have to read for the next month  wink
« Last Edit: July 29, 2010, 09:02:01 PM by Jesse » Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #7 on: July 30, 2010, 12:07:23 AM »

For an implimentation of Hart's method for UF you could look at my formula "mmf4.ufm:3D IFS" - so you can find it the interesting section (main loop calculations per pixel) starts with this code:

Code:
    x1 = gtestx - tx
    y1 = gtesty - ty
    z1 = gtestz - tz
    found = 1e200
    nomore = true
    if x1*x1 + y1*y1 + z1*z1  - (x1*dx + y1*dy + z1*dz)^2<=gdist
      if @useiterations1
        k = gntm1
        repeat
          count1[k] = gcount1[k]
        until (k=k-1)<0
      endif
      xv[0] = t5 = tx
      yv[0] = t6 = ty
      zv[0] = t7 = tz
      dxv[0] = dx
      dyv[0] = dy
      dzv[0] = dz
      k = gft
      s[0] = 1.0
      j = 0
      repeat
        ss = s[j]*gt[(i[j]=k),12]
        if @useiterations
          cnt = count[j,k] - 1
        endif
        if @useiterations1
          cnt1 = count1[k] - 1
        endif
        xv[(j=j+1)] = t5 = (x1=t5-gt[k,9])*gt[k,0] + (y1=t6-gt[k,10])*gt[k,3] \
                           + (z1=t7-gt[k,11])*gt[k,6]
        yv[j] = t6 = x1*gt[k,1] + y1*gt[k,4] + z1*gt[k,7]
        zv[j] = t7 = x1*gt[k,2] + y1*gt[k,5] + z1*gt[k,8]
        dxv[j] = dx = (x1=dx)*gt[k,0] + (y1=dy)*gt[k,3] + dz*gt[k,6]
        dyv[j] = dy = x1*gt[k,1] + y1*gt[k,4] + dz*gt[k,7]
        dzv[j] = dz = x1*gt[k,2] + y1*gt[k,5] + dz*gt[k,8]
        x1 = gtestx - t5
        y1 = gtesty - t6
        z1 = gtestz - t7
        f = false
        s[j] = ss
        if @useiterations
          count[j,k] = cnt
        endif
        if @useiterations1
          count1[k] = cnt1
        endif

coords are t5,t6 and t7
direction vector is dx, dy and dz
gntm1 is number of transforms - 1
gft is the first transform to use when dropping to a new depth
s[] is the scale at a given depth in the IFS tree
j is the depth in the IFS tree
i[] is the current transforms used at each depth
xv[], yv[], zv[], dxv[], dyv[], dzv[] are the coords and direction vectors currently at each depth
ss is the new scale for after the new transform for this depth is done
cnt and cnt1 are counts that allow restriction of the use of some transforms

Note that the massive amount of code prior to the above is essentially because UF currently doesn't allow parameters to be arrays so each transform allowed has to have its own specific set up code.
Also important in the set up code is a routine to sort the order to apply the transforms in the IFS tree traversal in an optimum manner.
There is also code in the set up to calculate the fractal dimension of the object but this doesn't work correctly for all user settings.
Also when using the formula the user defines the transforms as the normal convergent ones, they are inverted by the formula for using Hart's method.

« Last Edit: July 30, 2010, 12:23:06 AM by David Makin » Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #8 on: July 30, 2010, 12:18:19 AM »

Is it possible that incendia uses also Hart's method?
So in Hart's method we only use one iteration loop for each ray, and have to use a different kind of formula...

I don't think Incendia uses that method - I'd love to know how it does work though wink (Incendia seems to allow the mixing of affine and non-affine transforms which is not possible using Hart's method since Hart's method requires that a straight line remains a straight line under transformation)

One loop, but it's not a simple loop, rather it's iterating through a whole IFS tree, discarding branches that are "outside".
Hart's method was basically for standard IFS so the "formulas" are simply colllections of expanding affine transforms - they produce the same fractal as the convergent methods do using the inverses of the same set of transforms.

Note that an important factor in efficient performance of Hart's method is to pre-sort the order of the transforms so that those with associated volumes nearest the viewpoint are used in the tree traversal first.

I think I've worked out a possible way of doing the Kaleidoscopic fractals correctly using the method but it requires an extra transform per iteration and may have a flaw, but I hope to try it sometime in the next week or so (I get next week off work).
Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
Jesse
Download Section
Fractal Schemer
*
Posts: 1013


« Reply #9 on: July 30, 2010, 12:55:46 AM »

Thank you David, that gives me a very good starting point for experiments.

I will first make some attempts in a seperate program until i get more familiar with it, dunno if i will implement it somdays.

Hmm, spherical folding is not a linear transform, am i correct? That would spoil the fun a bit  cry
Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #10 on: July 31, 2010, 01:08:03 AM »

Hmm, spherical folding is not a linear transform, am i correct? That would spoil the fun a bit  cry

Correct (unfortunately).

Ideally one would use the unchanged viewing ray and test it for intersection with transformed bounding volumes (using contractive transforms) - the problem here would be getting the appropriate bounding volumes as even using affine transforms then a bounding sphere could change shape under transformation, however one could for instance stick to bounding spheres and always transform to the "worst case" new bounding sphere.
I think that might possibly allow rendering of fractals with non-affine transforms using the ray intersection method.

Edit: I should add that this method requires that the IFS tree is upside-down and you traverse the tree bottom-up but apply the transforms top-down smiley

Edit2: Or the tree is the usual way up and you traverse the tree top-down but apply the transforms bottom-up wink

« Last Edit: August 01, 2010, 12:23:03 AM by David Makin » Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
knighty
Fractal Iambus
***
Posts: 819


« Reply #11 on: September 07, 2010, 01:31:55 AM »

Got some time to finish and test the algorithm to raytrace KIFS. The basic idea is to fold the ray at each recursion level and recurse only for the segments of the ray that are inside the bounding volume:
Code:
// evaldraw syntax ("C" like :))
//////////////////////////////////////////////////////////////////////////////////////////////////
//"transmat" is the transformation (affine) matrix. It's a composition of translations, scale and rotations
//"tabplanes" is the array storing the folding planes parametres
//"nbr_planes" is the number of folding planes
#define INFINITY 2^30
#define IINFINITY 2^-30
#define BOUNDINGRAD 1
DivSeg(ox,oy,oz,vx,vy,vz,tmin,tmax,i,j,&k){
   if(i==nbr_planes){//Test intersection with bounding volume
      //Here the bounding volume is simply the sphere centered at the origin and with radius BOUNDINGRAD
     
      //Apply transformation to ray's origin
      xx=transmat[0][0]*ox+transmat[0][1]*oy+transmat[0][2]*oz+transmat[0][3];
      yy=transmat[1][0]*ox+transmat[1][1]*oy+transmat[1][2]*oz+transmat[1][3];
      zz=transmat[2][0]*ox+transmat[2][1]*oy+transmat[2][2]*oz+transmat[2][3];
      ox=xx;oy=yy;oz=zz;
     
      //Apply transformation to ray's direction
      xx=transmat[0][0]*vx+transmat[0][1]*vy+transmat[0][2]*vz;
      yy=transmat[1][0]*vx+transmat[1][1]*vy+transmat[1][2]*vz;
      zz=transmat[2][0]*vx+transmat[2][1]*vy+transmat[2][2]*vz;
      vx=xx;vy=yy;vz=zz;
     
      {//Intersection with the sphere
         c=ox*ox+oy*oy+oz*oz-BOUNDINGRAD^2;
         b=ox*vx+oy*vy+oz*vz;
         a=vx*vx+vy*vy+vz*vz;
         delta=b*b-a*c;
         if(delta>2^-53){
            a=1/a;
            delta=sqrt(delta);
            t0=(-b-delta)*a; t1=(-b+delta)*a;
            if (tmax<t0 || tmin>t1) return INFINITY;//intersection outside [tmin,tmax] => no intersection
            if (j==MI) return t0;//max recursion reached
            return DivSeg(ox,oy,oz,vx,vy,vz,max(tmin,t0),min(tmax,t1),0,j+1);//next level of recursion
         } else return INFINITY;//No intersection at all
      }
   } else {//Fold the ray by the folding plane #i
      //we fold only the part of the ray between tmin and tmax
      r=INFINITY;
      a=vx*tabplanes[i][0]+vy*tabplanes[i][1]+vz*tabplanes[i][2];
      b=ox*tabplanes[i][0]+oy*tabplanes[i][1]+oz*tabplanes[i][2]+tabplanes[i][3];
      vd0=a*tmin+b; //In which side of the folding plane is the tmin extremity of the ray is
      vd1=a*tmax+b; //In which side of the folding plane is the tmax extremity of the ray is
      //account for different cases
      if(a>0){// angle between ray direction and folding plane normal <pi/2
         if(vd0>0) r=DivSeg(ox,oy,oz,vx,vy,vz,tmin,tmax,i+1,j);//on positive side of the folding plane => ray origin and direction are not folded
         else {
            if(vd1<0) r=DivSeg(ox-2*b*tabplanes[i][0],oy-2*b*tabplanes[i][1],oz-2*b*tabplanes[i][2],
                               vx-2*a*tabplanes[i][0],vy-2*a*tabplanes[i][1],vz-2*a*tabplanes[i][2],
                               tmin,tmax,i+1,j);//on positive side of the folding plane => ray origin and direction are folded
            else {//ray segment crosses the folding plane => cut it
               t=-b/a;//No need to test for a==0 because this case never occures.
               //we don't process segments that are too small
               if (t-tmin>IINFINITY) r=DivSeg(ox-2*b*tabplanes[i][0],oy-2*b*tabplanes[i][1],oz-2*b*tabplanes[i][2],
                        vx-2*a*tabplanes[i][0],vy-2*a*tabplanes[i][1],vz-2*a*tabplanes[i][2],
                        tmin,t,i+1,j);
               if(r>t) if (tmax-t>IINFINITY) r=DivSeg(ox,oy,oz,vx,vy,vz,t,tmax,i+1,j);
            }
         }
      } else {//symmetric case
         if(vd0<0) r=DivSeg(ox-2*b*tabplanes[i][0],oy-2*b*tabplanes[i][1],oz-2*b*tabplanes[i][2],
                            vx-2*a*tabplanes[i][0],vy-2*a*tabplanes[i][1],vz-2*a*tabplanes[i][2],
                            tmin,tmax,i+1,j);
         else {
            if(vd1>0) r=DivSeg(ox,oy,oz,vx,vy,vz,tmin,tmax,i+1,j);
            else {
               t=-b/a;
               if (t-tmin>IINFINITY) r=DivSeg(ox,oy,oz,vx,vy,vz,tmin,t,i+1,j);
               if(r>t) if (tmax-t>IINFINITY) r=DivSeg(ox-2*b*tabplanes[i][0],oy-2*b*tabplanes[i][1],oz-2*b*tabplanes[i][2],
                                vx-2*a*tabplanes[i][0],vy-2*a*tabplanes[i][1],vz-2*a*tabplanes[i][2],
                                t,tmax,i+1,j);
            }
         }
      }
      return r;
   }
}
//This function will return the position of the first intersection along the ray {origin : [ox,oy,oz]; direction : [vx,vy,vz];} that is between tmin and tmax
//It calls the recursive function defined above
nextd0(ox,oy,oz,vx,vy,vz,tmin,tmax){
   r=INFINITY;j=0;
   {//Test intersection with bounding volume
      //Here the bounding volume is simply the sphere centered at the origin and with radius BOUNDINGRAD
      {//Intersection with the sphere
         c=ox*ox+oy*oy+oz*oz-BOUNDINGRAD^2;
         b=ox*vx+oy*vy+oz*vz;
         a=vx*vx+vy*vy+vz*vz;
         delta=b*b-a*c;
         if(delta>IINFINITY){
            a=1/a;
            delta=sqrt(delta);
            t0=(-b-delta)*a; t1=(-b+delta)*a;
            if (tmax<t0 || tmin>t1) r=INFINITY;//intersection outside [tmin,tmax] => no intersection
            if (j==MI) r=t0;//max recursion reached
            r=DivSeg(ox,oy,oz,vx,vy,vz,max(tmin,t0),min(tmax,t1),0,j+1);//next level of recursion
         } else r=INFINITY;//No intersection at all
      }
   }
   return r;
}

It can also render KIFS with non uniform scaling.

Room for improvements:
-Take into account the size of the pixels.
-Non recursive version (but still needs a stack).
-A way to compute such bounding volume. The bounding volume should be as small as possible in order to speed up things.
Logged
Pages: [1]   Go Down
  Print  
 
Jump to:  

Related Topics
Subject Started by Replies Views Last post
Is there a preferred install method? Mandelbulber meegja 4 2555 Last post August 29, 2011, 09:57:03 AM
by taurus
3D IFS and Hart's method Programming David Makin 1 2738 Last post August 26, 2011, 05:20:33 AM
by David Makin
Hart-tree Images Showcase (Rate My Fractal) phtolo 0 633 Last post April 11, 2014, 10:56:25 PM
by phtolo
Pixelation reduction method Mandelbulb 3d 1Bryan1 0 2087 Last post December 06, 2015, 05:24:22 AM
by 1Bryan1
Have you used the Interpolate method? Mandelbulb 3d 0Encrypted0 0 1942 Last post July 31, 2016, 06:05:21 AM
by 0Encrypted0

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines

Valid XHTML 1.0! Valid CSS! Dilber MC Theme by HarzeM
Page created in 0.507 seconds with 26 queries. (Pretty URLs adds 0.012s, 2q)