Title: Kaleidoscopis IFS - using Hart's method ? Post by: 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 ;) Title: Re: Kaleidoscopis IFS - using Hart's method ? Post by: David Makin 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. Title: Re: Kaleidoscopis IFS - using Hart's method ? Post by: Jesse 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 :dink: ...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... Title: Re: Kaleidoscopis IFS - using Hart's method ? Post by: David Makin 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 :dink: ...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. Title: Re: Kaleidoscopis IFS - using Hart's method ? Post by: knighty on July 29, 2010, 12:39:49 PM Hi,
Here is the link to papers page (http://graphics.cs.uiuc.edu/~jch/papers/) of Pr. Hart. ^-^ @David: I think that kaleidoscopic IFS are not RIFS. I'm not sure because I can't prove it ;D. 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. Title: Re: Kaleidoscopis IFS - using Hart's method ? Post by: knighty 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: Title: Re: Kaleidoscopis IFS - using Hart's method ? Post by: Jesse 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 :dink: Title: Re: Kaleidoscopis IFS - using Hart's method ? Post by: David Makin 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 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. Title: Re: Kaleidoscopis IFS - using Hart's method ? Post by: David Makin 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). Title: Re: Kaleidoscopis IFS - using Hart's method ? Post by: Jesse 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 :'( Title: Re: Kaleidoscopis IFS - using Hart's method ? Post by: David Makin 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 ;) Title: Re: Kaleidoscopis IFS - using Hart's method ? Post by: knighty 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 :))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. |