|
David Makin
|
 |
« 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 
|
|
|
|
|
Logged
|
|
|
|
|
David Makin
|
 |
« Reply #1 on: July 28, 2010, 01:54:48 AM » |
|
OK, should have thought a bit more before posting  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  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
|
|
|
|
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  ...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
|
 |
« 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  ...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  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
|
|
|
|
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.  @David: I think that kaleidoscopic IFS are not RIFS. I'm not sure because I can't prove it  . 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  ): 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
|
|
|
|
|
|
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  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 
|
|
|
|
« Last Edit: July 29, 2010, 09:02:01 PM by Jesse »
|
Logged
|
|
|
|
|
David Makin
|
 |
« 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: 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
|
|
|
|
|
David Makin
|
 |
« 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  (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
|
|
|
|
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 
|
|
|
|
|
Logged
|
|
|
|
|
David Makin
|
 |
« 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  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  Edit2: Or the tree is the usual way up and you traverse the tree top-down but apply the transforms bottom-up 
|
|
|
|
« Last Edit: August 01, 2010, 12:23:03 AM by David Makin »
|
Logged
|
|
|
|
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: // 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
|
|
|
|
|