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: Visit us on facebook
 
*
Welcome, Guest. Please login or register. September 23, 2020, 05:49:51 PM


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] 2 3   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: Tglad's Mandelbox and using the delta DE methods for RIFS  (Read 11881 times)
0 Members and 1 Guest are viewing this topic.
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« on: February 14, 2010, 12:15:00 AM »

Hi all,

When implimenting Tom Lowe's Mandelbox in my formula for Ultra Fractal I realised that it's essentially a different way of doing escape-time RIFS (that's Restricted IFS not Random IFS).
In fact it's revealed the answer I was looking for in terms of how to efficiently render RIFS using the standard escape time method rather than employing Hart's method as I did in my older 3D IFS formula (which can only be used for purely affine IFS/RIFS).
However to do true "correct" IFS using the method (e.g. for the Sierpinski tetrahedron) is not applicable to all IFS.

When using the contractive methods for rendering IFS (chaos game or deterministic) then each transform normally consists of a contraction (scale/skew/rotate etc) followed by an attraction (translation to the transform's location) but using the escape-time methods this is reversed to being a repulsion (away from the attractors location) followed by an expansion (scale/skew/rotate etc.).

When using the contractive methods the key transform that dictates if the point concerned belongs to a particular transform's area/volume is the *last* transform performed, when using the escape-time method the key transform that dictates which transform's area/volume a point belongs to is the *first* transform performed.
This fact about the escape-time method can be exploited because if we determine which area a given point is in (i.e. which transform's area/volume it belongs to) then we know the next transform to perform for that point.
Using the Sierpinski tetrahdron for example it's easy to find which of the 4 transforms concerned should be applied next to a given point simply by finding which of the vertices of the tetrahedron the given point is closest too and applying the associated transform to the point and iteratively repeat that procedure as normal until bailout or max iterations is reached.
The drawback with this method is that if the volumes relating to each transform are not easy to separate (as is usually the case when using rotations for instance) then the method causes parts of the "correct" attractor to be missed due to choosing the wrong transform at some point during the iteration, though this of course can be used to control the results too.
Also the delta DE methods give us a way of mixing affine and non-affine transforms for RIFS using the escape-time method.

Am just working out a new formula addition to the options in my wip 3D formula along these lines.

I realise the method is a little "chicken and egg" since you need to know the fractal shape in terms of the transform areas/volumes before you can use it to render a particular fractal, but then again yoiu could just play with the parameters until you find something you like completely ignoring whether parts of the "correct" result are missing or not wink

« Last Edit: February 14, 2010, 12:18:52 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
Timeroot
Fractal Fertilizer
*****
Posts: 362


The pwnge.


WWW
« Reply #1 on: February 14, 2010, 01:19:00 AM »

Hey, that's pretty interesting. I have a question though: you said that for the Sierpinski tetrahedron, you can determine which transform to apply simply based on the nearest vertex. Wouldn't this just give four points, in the end? Don't you need to vary the transform randomly in order to get all the details? Me is confused...  huh?
Logged

Someday, man will understand primary theory; how every aspect of our universe has come about. Then we will describe all of physics, build a complete understanding of genetic engineering, catalog all planets, and find intelligent life. And then we'll just puzzle over fractals for eternity.
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #2 on: February 14, 2010, 01:44:21 AM »

Hey, that's pretty interesting. I have a question though: you said that for the Sierpinski tetrahedron, you can determine which transform to apply simply based on the nearest vertex. Wouldn't this just give four points, in the end? Don't you need to vary the transform randomly in order to get all the details? Me is confused...  huh?

No, you don't have to do anything random, nor compute an entire IFS tree for each point.

Remember this is using the escape-time method, so we're starting with a point and saying "is this point on the fractal ?" by finding the first transform to use for the start point, which gives us a new poiint for which we again find the transform to use and so on - so every start point will have a very different iterated sequence.
Each point on the attractor has a "genetic code" of the transforms used to get there using the contractive methods, what we're doing here is attempting to decode that genetic code by going in the reverse (expanding) direction, if the point is truly part of the attractor then the correct genetic sequence will repeatedly take us to other points on the attractor, if the point is not on the attractor than no matter what sequence we use eventually we'll bailout - also the further from the attractor the point is then the sooner we'll bailout.
The important (and potentially problematic) part is the identification of the correct transform area/volume occupied by the point at each stage which gives us the next transform in the sequence.
Two general methods are to identify the fundamental point attractors of the transforms concerned and either just use the nearest of these as a guide to the next transform, or to create cutting planes based on these to separate the areas/volumes (a bit like a BSP tree) but neither of these will work perfectly for all transforms - in particular not for those with rotations.
Any ideas of how to better (and efficiently) find the correct transform volume for a given point would be appreciated (note that simply applying all transforms on each iteration and picking the result with the smallest magnitude is *not* generally much good).


« Last Edit: February 14, 2010, 01:46:12 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
Timeroot
Fractal Fertilizer
*****
Posts: 362


The pwnge.


WWW
« Reply #3 on: February 14, 2010, 02:16:06 AM »

I think I get it better now. It's basically identical to iterating a general Julia Set, and seeing if it is attracted to anything, or if it stays on the Julia Set. The only thing is that you have different functions which created the Julia Set, and so it's harder to "work backwards". You have to figure out what sequence of transforms created that specific part of the Julia Set. Correct?
Logged

Someday, man will understand primary theory; how every aspect of our universe has come about. Then we will describe all of physics, build a complete understanding of genetic engineering, catalog all planets, and find intelligent life. And then we'll just puzzle over fractals for eternity.
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #4 on: February 14, 2010, 03:34:19 AM »

I think I get it better now. It's basically identical to iterating a general Julia Set, and seeing if it is attracted to anything, or if it stays on the Julia Set. The only thing is that you have different functions which created the Julia Set, and so it's harder to "work backwards". You have to figure out what sequence of transforms created that specific part of the Julia Set. Correct?

Correct - normally the "correct" Julia for a standard given IFS would be with a seed/constant of zero, changing the constant/seed would effectively be simply modifying all the translations by a set value, but you can actually apply it in the Mandelbrot form as well - in fact in the case of Tom's Mandelbox it's that form that's interesting.
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 #5 on: February 14, 2010, 10:54:12 PM »

Finally got around to comparing the delta DE method with Hart's method and was pleasantly surprised (I was expecting Hart's method to be both considerably faster and higher quality).

Here are two renders of part of a Sierpinski Tetrahedron:

Hart's Method:



Delta DE (Buddhi's method but using just 2 points per step)



You can see that the edges are about the same roundness/shininess but the smallest holes are much clearer on the delta DE version.
Hart's method took 1min. 3secs.
Delta DE took 1min. 45secs.
However I tried to adjust the bailout size and closeness on the Hart's method version to match the clarity of the delta DE version but to do this required considerable increase in the bailout size and decrease in the closeness factor and changing this in this way produces pretty much exponential increases in render times - I got a better render but it took well over 3 minutes and still wasn't as clear as the delta DE version.

I should also point out the obvious - there's definitely an issue with respect to the shadowcasting, there's not enough shadow on the Hart's method version and possibly too much on the delta DE version - I will be looking into this smiley

I should add that this sort of holey low dimension fractal is optimum for Hart's method but worst-case for the delta DE method so for fractals that are more solid/of higher dimension the delta DE method will be relatively much better provided it can be applied to them successfully.

« Last Edit: February 14, 2010, 10:59:06 PM 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 #6 on: February 21, 2010, 10:23:35 PM »

I decided to see if application of Tglad's location restricted based rendering (which I suppose originally should be credited to Barnsley for example with the Barnsley types in Fractint) could be used to optimise the rendering of more general IFS.

So I decided to start with the classic Heighway Dragon.

Here is a render showing the Heighway Dragon coloured to separate the areas belonging to each of the primary transforms (the last if using convergent rendering, the first if using divergent rendering):



Clearly we can't really use a simple location method to separate the areas for each of the transforms since the boundary between them is itself fractal in nature, however we could split the plane into 3 sections, an area to the left (transform 2 only), a central area (both transforms possible) and an area to the right (transform 1 only).

In this case we could say that transform 1 is needed if x>-0.34 and transform 2 is needed if x<0.167.
Rendering on a depth by depth basis rather than traversing the IFS tree we can use this to control which transforms are performed on each iteration and using the above figures we get this result for a bailout radius of 16:



Clearly we are getting hard breaks in the distance estimates, this is because we have only decided which transforms to use on locations inside the fractal but our colouring is actually outside.

Here is a view of the fractal with both inside and outside coloured based on areas belonging to the primary transforms:



Clearly splitting the plane in the same way means the central area that requires both transforms to be performed is much larger.
Re-rendering using the new locations corrects the DE:



In case you're wondering why use such a large bailout value, here's the problem if you use the smallest possible bailout:



As you can see the distance estimation is split at the iteration boundaries, this is because that although our bailout radius (here 1.36) is large enough to contain the whole fractal so inside/outside is rendered correctly the magnitude is insufficient for correct distance estimation because the second level bailout spheres overlap the primary bailout sphere and a larger bailout is required to reduce/prevent this problem.

I then thought that maybe doing a limited resolution pre-render to a square of side 2*bailout radius storing the information about which point belongs to which transform may be useful (such that if pixel 1 belongs to transform 1 first then all pixels in the associated 3*3 pixels are flagged as belonging to transform 1 and the same for transform 2 i.e. so boundary pixels could use both transforms).
This worked very well and is in fact by far the fastest rendering method.

Here is a test UPR which includes my test formula (copy the whole lot and paste into an open fractal window in UF:

Code:
IFStransforms {
::HYFDOjn2tX5WrtNMUA43Dk/DC/02DNRXskt3QPMIrwgVGsu3LK2KJaV+CSydN7X/kvlIoZQX
  pdbsFwGkOSnrSf6sxIydC9bmPDAcKnWyj+wlX7MiK7maTpNC8NVhbHnFDB7kqt7c84UIQL2L
  NWecna5GZhyZ5RrE3pKAXJuVV9W8SMaJGigRzn1v5ePkLacq6KeUpqCYEFqWLY17jA1Niclb
  PHBhg7UW1afcUVDKlud1F8yWtT1Is25zKFNNqqtDGTW5kGOcJEUK2WxRLozn1F0taR/GKF3r
  62BBCakm8dy8b51b2A2o0yKRpPV/kZtPyX0upMC4tmZPP6z+0PqT7mbyr11tG+Kl1twPt1K3
  qrXL0dhWzNF1C94wv2qVC+ep1PWYMi9W13lcEFOYn1Cl3QOfAmS9TtSZRfU7Hi4wF0l+/O3N
  OpTOmfx4Cjhykg5zUVWVhsPBLk+x+yGcBCMck5z2q6KZQKWWuZRbu+Q+d1VXKuwXlIr8ZpPq
  Ohxw0jWTrqkCzj1eb7OT9L0bQbZdt/mTXZRVVIvnDBdVUDHxIw04ksRxpjipJsMYc6oUEr/M
  eQBSMigQTKgjHlzSRoEayoYC+w2RQMh0X6GWK+orToQWKbS+kvRIMjmlgGlTDcONl5VaaF2k
  vpsMM2PbQcC+oDYJxpJH9dagvhQc2U4mO57EYSSKGOKOLw1JJMSMlOVRgxHSQCBRwkpFQHzc
  cmXhAvjwHcPBC9fHqWZZjLQ8hbKm4vNMQhhHe+r3TndTMKmSPJS/OtG8qCZjbHY9eQ/gXDC4
  8w3UC49Ob8XHy/lpY9xh9D6ek8Z/6Q/gJC4+HB0TeqYaI2/ke34Mn//Ln/x6cR3IgRadGVuT
  W8Quf8GWI03Zknl+8+ud4/QY/QL+fK3jihBkPmyehA/neD6T3wncuf/53BeReHYk/PRP//Ja
  0jS/9A8knXeP89jzt9Pj7PA3/Bg4w2+H
}

Orbits.ufm:RIFS {
::azlnfhn2trV3vttNQ83LQ/fgNeoQKO2RUtJroxKwoobD719xTd5BFHZNaLZ7JLvZbk/43RSR
  xvtdczSX3SAih1x7Oe3Pe3xTHcex8bTLe/LfxVI0o5lLKyWjSxoE0wR4zDw9j6NcJOUf5Y2y
  xilj5L/N3lNmMLD9xv7D/6PwosoiMrOItR8mnocTGjGuaZWObvf5LkqOfL+TDTrqS3sksN7G
  9li9v0WwiCiOLKUj8IgKsGl24i5p1o8SL1LWI23CgOi6HpShSCnFHxIC+EKv2StcyxOJv4Tx
  Xc5Zw/SSjoIOW+IFhlqno90EtnmKe625zLQ5Z/Z2MgSd1qMJxxkql1KUbcklU8B3Xqr1aaej
  4JO7LWbiEL2IpUltILtm+NkieQceW+HV1BDvNlUMfVd4pswm8NnjjfXf+Jmu8I+eZKV+auEo
  eUjOUwLNWayqCSqgAiFFFdDoCQPdBjlsIYxmQl1LbW/eNGuXhDK0McZW2dCaZFLzcsDtBdGa
  uBWU0mTbJb2dkxiHMP8Y0MP7YEVP54bQb8D7xpyDAToFZGArqS4zTZweU/LU8KAiZ2mki0YH
  nqBMI1gXxf/1vTKyQBgVmA/3DHedi26sdIIvM5+AIdNJgiuAj30DqBFeOU/pb+ow7DHICG0l
  lbfjiHIz1MZAxqeA8cjsigx6ly1LtXmuDsTC7lQs88GZx2rnZgPOkiW/g6vOEWN+wEjpf21e
  LdvhsiISEqnDL1MQR39LHwwIyNuYoBgJex3WMm4Di3LM3CaEPI9uQbdh9D47A0bRxeO3bPSt
  aWNpACuJJ5EIyfQk1xltcOIJOBsAOe2sNguDokdDyhG2MZHw1Bb6uztjp52xf1kbH/cu9TUu
  d8z52fW52xPR52AB2V7aX/LaYxoxATTwVzOyWZc3+QM0+Q8h0+AP77B1+AePlY4ok/SMy1dE
  /LAZGezNOXJ+YWiP+JOxHvrEf8+T8x7Jxn58kd77fdl/1k44yZOg7/aDOP87/eO485gz/JCO
  tLgrxiwFmmkPtLtsbny01k6sK093T3/rTMjaZwU+G4V0j996nUHiAVwRv+1wXGEfxlal/pv6
  a+aVF4LQhqopCFN1URCOW8p8pnBnwvKBAGKnCCDejjQWxiUjo97dBM9YO8Mhv81dj3DSTDWY
  suRwqYl1Jg40zgG/UQfTCwbL9GlSmRqfv6ow8PWN/TVjNUtObVJVaTiO2gOLIrzYzxzYYMaT
  Rp1h5TPy3o48NJOrBxZPHO3jhz9U40n4m+A30m32EtBs5a+amjoxAEEjKSiSIU7Ao4EZTeSW
  F1xwlMmrkBWKnHUx85LYn86oDjBzh7A2pcqO2jzRdOONtgNCnInfzVyr3elcau0csgh3NPto
  gWloKLtIA8H4+lwr7F1/NvNUdydHsk4+xxhhofTJ/C4JQXaIlFwj5VBBqC3VfQihnymi45GU
  PTT3IGyCaCyq6G0jUmmLUXvDSdQ9mYNHl2AA9+fuWktm65yfQEvv1Lkyyf3S9r9KFk1uSAUk
  jXVoWwr2tS23j3yXNzsNu7QvcHLex81WNV5u6JwTR+yBgnZ3EwWKRLQoBIIW4gfsoxPJWwh/
  WbEsbjKebIwV/D+uxgkY2xgGnaPwBIFXll4r+8WDQyFKMR33N96JO8V/mUzDP46DDi6jv8bP
  m6DDi7fx7+qq8w14dXdo5dD+CXdA/c1B10d8/jrOgfkrOY/6HOGcEtTqRzhY/qkk2Wn7QN5m
  GypmCLZ46ItlLb9ImDHJ52Jbt2kkDrxTpOXKR7QxJy5R9AK3xSbOq2hESeUtDxF+RreHXdfu
  tDx0yB1OkvhgwrZaXwTQWLRvWQlX7SrCF9A2cAHPOVowuqQh9WhC7pCVdzC22+/uqhMxyG/M
  7PgHqdM9H0I5R1fwXy8Ff9HISX2f/BPnu8fr0F7LMP4bHxPW3OK+i6O3INTCWUcZZ4pLHpw/
  Vd2mYkbxH7xDJ36KPpVNa6ATrA9cFzSbtnOrPF025X+2owzaosplClfzfWb8fGbNbb7zHvzd
  C6kHPHEMomv3MEIliDgfkuqgvQNpGagJBdSdG0z1P9jf/PfCboeZzoT3VZyTLSrSLR8zaR0w
  KaQzJfkssuPY8d2Cf8LVpzWOeeV5Jcma2LRwFEIwUkUja/6/U5vt7PbZYl2fA8rMDOJ/iG6s
  Z3oapUkmJuaLhWdXJ/4+v7C3CI/BlJ5uFqdwO2m5+XcmY+d2CMyjA+0fsF792zG4TCD+/bg9
  efMN
}

Here is a UPR to compare the different rendering methods (needs the formula from the UPR above so paste that lot into UF first):

Code:
IFSde {
::TPxSxhn2tv5WPyNuZa47Ng/PUovKZD626jn5GoLyiJZxCkZTQOcbaI3lKblp6qKUlaPtyv+l
  UHI/eJdyafxOIBrH4BtIFP+p3HRx+l9hrdPN2d8f/tvZ3uxhxj9t39f9b+j77vb3POsf8jtG
  VzuP2P8hPOOf5xup+r3aVxi/01+9Dj3av776+0w+dff3PMc6XKengenohau7tvZuwzt8TdXG
  HOfq9uf/1+7v2faffou7eu7yur93GvO80YI5Pbf/lxPu79T7mv4nf3uzX6eaYcqlaaitynGu
  N8+wI805dP3P+xz7bf+ljjDX6ud7tvJ0YXGO9hlur/0Y/12mHMkrhU2Gtzpe39NPQahXRk1E
  zL0/f4Ur6Bh+tv5w5rh2qbu2P396Qs6ymdX6v+0H7f6HaPf4wuDDH7P19cIC97u++wE/hXO8
  8d7Cd11p27+Dho2dxaf5xnOf88LXb/uhbjPES+yt+Pc8877O2O1fLke/5ujHjzhLP+Xf54Q3
  a2dXv2Ndb4v13KsLtz77GCN0YrQbCpu13vvt5dNxLpwUT/uw/H7t1Ex8Ft3vej1RyWGv9NDn
  uNsvfe+tvPcdIq2Em57Gv2d62hws905T9sp4zPf4hXe6Ya+99f/vp7+QUS+dhZZYUlatUDcc
  4Uf31v0m4DX72PEuxcbc75znDatYgYIoNettZXMIetlMyGny6Xz2tmt2a8NK3aukZ+Z+SFkK
  SS0WFEq18NuwTdtdNbpIVcqRIlzhrlbpydtV3Ycmt836biEGt3Sr5rZdu2ZCVa7Omt+Wb8CR
  I1S2WRuDMWlzm7bHrvbaE+thrbrvtNWrT0smtn11WrRq06tISjKNBlSSKkb3gyz8AJo1senE
  puX20E+XKa59r3QGGuOhMIAWAT+Dvgge7Z3G2K06P7LB+tnfqLe1/vC+nB+/XZ/wQ+nK4X+N
  2/bs/P5s/v64x/xsOD0n5x/Fn1XA8EsvUxMvr9Nf1w+Sbw49vB7fD2/nXY/81hPMcq74uA4E
  ER99Rl0nC7io7Y9q8/Ug7i/e0+3/8B1MrHLdWLr+Pu/XfLMn6/TDP3Hp/Av9jdXPtg53+45f
  c/wz5Ezcy6bvu8YciGjFUABv84lnPvP0RX77O+z+b/lL/8YTN/Ow53B9YoXCv4Le1hhXDziU
  rESO/6i5OJkI+CjlEbv64Pfr/693u0/0whhwnTtcjQvu+2iDxQ31+1Xr8+IT+ytg8bp5Sj/4
  FiHiFpb/f9lbjpBQQWMP0/vDxzwjyt39dOs5vwb/6O9U/uf9txhn7GPfNOpOfc/Thyfudt/P
  9yzx03O3Kmnedz37BXcSf58SnvWH68cEYrGUsKLNyl5Q1aTsW6LYpvw6gL5eYuLWakxnO3Ej
  LLXSrT3wliW52lyg6Z9SVre7SdrZLcGSZatb3w262u0163u0H00pupJmfquEFgw09EBOMlQ2
  Sp+mUtUq3Jd4x1Wbsuyz/Z/p+xhnyRDIW0SrBiUYIFE2C1YkeJ0tElxgMGjTPQmjy5g8yjxx
  nyx3c4NHdnDubhic4dO6OfVOymDs546SYdr+LB2lLZBVeMlHSXjopavETjX/pm2lfSzhtxPJ
  ivnI8TZrc+nqW18P1t65faaNrNznst25f6adz/036XaqQgYtRDt6SzGHZLNcccJ3ai4Abp9j
  jpYP8c3wpLXHmHFvebMeZcgMtcpaO3PGvcd2MtkK2Lfofum6lvJZ/yjlrnHDfVxDpXzsf9hU
  owhL3+qiwLEv1Pu95HHOOuW7Xh6MBpCjjw3DM34phyWGxp01wLIj9w8LeiX38OaZoNmGaj5a
  P32j5R34adXGaj5h2IfoNmfX3E0CLjux1BzEkKO0GZDtYjTLNSY0d7HGucbpP6GXVDtxl0mv
  bz6n2FLF9c3tfg2eSkyRMLpSJlYSFmUXVdDWA7cyQsqpVphgVQ6+Q4LGoGjN81POjWZ1ClqJ
  8FVKpRE+IBneJW2U+kuJt/xQAthHQbgn1NQ0sp8ZdDLg2wCoNrPrDrd0EW7I8hnhrHelV/Dn
  Cvu4uu/tDnmXQ8X8+4qHdp2oZ9x9lfM0Hi5Lf6GbWcIMlCfg6px41XWnAdvuNcf/rbjsQDky
  9wpwl3GOt+x4TpSPxK9Uu0TzlOGtnbuYs8yhm0LTDihrr981hD3ayLSOn8xNlySKCSJybKYJ
  DJcbFkSDpMlV1C32Bp84YopsuEOsIBmEHVkqq6bDtQsgYghYFM4JFchuABDBCGiVwgn0UV9E
  YEeJrEJD6LmMoSygW3Q1CaQc0gA0gA0gKRDihGEDNoMaQM0gA0gqRjUbQZ0gSoBxRDihG0Ga
  QJ0gYoBlRDijGpSPxK9Uu0TUCNoEaQAaQZ0gQ0gA0gA0gKRDCQDCQDCQDqENIANIANIANoK0
  gQ0gQ0gQ0gqQDCQDx6uECKXJSGyKyQikhEJDJSGyKyQCkhocJDxXMYIglfFM91xRBnKEAVIA
  qQAL/Kya8IVIYUhITFCGVsV/ASIQkYVomaDRmKEJqY7uHCzmMSISy0uXFJqQwoCRmKEr68up
  URnYzjIVkL9kIRFiEVsGsiIhIjEiVkILZEAVIAqQ8oASJR1mAoCBQFiFqIlyWWVHcbPOGKGS
  UZlJccBUhYlKyJ15qHCHyMVoQqQhfFlaFJyqcFSFKkKU4XRpWRi1x95R5MVshEyvYkQWuWhs
  9eablCJnJkATIBmQWuShktShkxEyMTIZMhEWpQWvSRqNkZmQmYCJflCJDLkbrUITMhkxEyMT
  I5rUkK9Er0T5SPJTMhMxESYlCZGLk4KFSgJkATILXpQCrUIBmQCMhsclCJsShEYCJwEyqVKk
  4KFSkJkITIrWpQCrUoyMhGZCd1KFaclCNyEakJ0VrUohVKUtStNDFq4u7Xl9qSZf8mNBO5dR
  nktW/CAo4AgCAAVeTaLMgCWXQxAAFDAUZAQNDALNRgBU51FU1AQqNUZAQFBg1fJK3Up1FUMA
  QtBAqEAoYAAbSEYAVadhUpnYlOlbAAUJAIWgVX6ucQlXXQlBAFCAKAAUPW8CYFsugCAAFAAq
  H1lV1A32CpcQKfZVpiRFhJxBFJrqOOy4AgODAmqdXbw1FMIAYQAwUt7aDuugBAAdrh9bJRP7
  dys8XXK/1xdIIdk/d3TPQCveR/r56fNo/1l6fNo/1M9vmp/1Z9vG1/6s+XXr/TthOr/1c9vO
  p/1M9veT/rT6fNT/rB9vOp/TleiV6UuB9vOp/1c9vOr/1Z9vG1/aQ/rL1/aQ/rB9vG0/6S9v
  G0/aQ/rB9vuU/rR9vG1/aU/rr0/aU/rB9vJr/tV6fLq/to+3i6fbl+3i6fLo/NtyGGAYy/i4
  MlAQoJeQpXcgx3oVL6/tw5rr1PwIyEBMn0wRADgAm4JgIBBGGEYyQgBhATGCM1QQqNMZIwwh
  ATCCMMIwsBBmEEYYQgBgATCCSleiV6UuBIwkgADHCMZIwkhADCBGACMlQgBgADABGACMlQgB
  gADABGACMlQgBhADCBGECMVQgBhADAB2ME4qgAHCBOECcIE4qgAHCBOACs8fT52MCYLRgQBn
  f7vfV8bBx/czQJxfMpgr9tg23ye9vlp8tZlvFV+2sy3Wr8TthNr8tclvNp8tMlvdT5bTKfLT
  5bBlvNp8TleiV6UuBlvNp8tclvNr8tZlvFV+WQ5bLV+WQ5bBlvFU+2SlvFU+WQ5bBlvtU5bR
  lvFV+WU5brU+WU5bBlvLr89VKfPq89oy3jKffly3jKfPo8dFGx4mf/9X2/twIuSGxF3d890C
  g44fdkD+6IHs9YX52jdM8wxwDXGPcstH7gtH7qxjUb4y4hLt9YHf7xOGe42wDXCPcM8wl3es
  jv94UpnYleKX6JXCPcptH7gtH7y4hDxDHgHOY7xuytH7A8wB4hD2esrc7xOAPcAe4gtH7q2e
  sDxDHiHOc7xuqtH7A8wnxDqB3f8SaYDyLZJLKiqItuItpuJSUivgS8f1UivkS8zrksAJeOk4
  BIxDQivES8MIxzgEfGS8MIxDQivGSSthPDJ+Ek45QinBJ+NIxngEPDS8ZIxzhkUpnYleKX6J
  fCS8JIxDQiPDJeES8Ak4BIxXCJeAS8Ak4BIxXCJeAS8Ak4BIxXBJeES8Ik4RIxXBJe0IuGGl
  QFUCVTJlmUX6SNVQJUNlgGVTNFYycGfdcCVZZ9cObkCBeWTop1LJ5fwF1AfxFx9tm4GXTMnr
  pG8ruS1KaQ3nx86cDRM7rpG+nelKzh4MkZTXyCbK7hNxNxmPpiu11k+CscNm41Inf0uOmx33
  Wa4VP7ayfHGxczmKszmW9zmZxF6pN1AfMGhWaTreaDVXjFwgJtYSXV19YBgPKjKs2m282GH/
  FDR4DzoC7tzubOL5Ls4mEFn8jCHupNLuLbCdRRMFpzUFVSV0XPVVb3Nx8wgQ7uL87mqoKCpK
  wybwzbup3UBVRMq6z57d24buz3EQVUmqAzvzufzs/G8/mQqiyUFzCcwDcuJ4EQVMnwJGVxNC
  v0JcqiqKsDnQqqwNcqiqKsEnQqqwRcqiqKsFnKoqSXxpaqq0acqgqQnxJBSVF2jTyCqqwdcS
  WTVFWkTyCqCdInElUl4rnqEVUVy55jjE4WOh2lvkEgK0z8UyZoibZOx8MnEFQFz4cS8ZgqUD
  RMjzJBAVZ3zJu95bznuXps75E3+c+kKCVZP0z1YiXjc+RoSAQV2Idi5kOxsSnEFQloCqQ30J
  0OdSgQloCqQH1J0SdSgQloCqQX1pCb1JRBUJqhqCn1pCr1JBCVSEqKcXnKsXnUFQlqGqKcYn
  KsYnUIUJLhK5XPUV52ONb3+2HAC+tToh7LJBqSiUF3zdib6OxcdnkFUlkRVfGj3zNExsenkA
  VJzUF39dKZ/Ol9fn4GwznURqSmpqsH88akzPSVSgqyWxv1xzUFzJeqwKeSWRVof8kEpK0OeS
  WRVon8kEpK0SeSWRVov8ksgqKslnk1UVh38ksgqQr5JFSVF+zT6CqqweeSXTVFe0T6CqCton
  UlUl6rnqqMzn2cZPCVgH+EaiPV5iPh24Tcf8JuR+EzJfqwKfi5lP9ZMzP3QEzOfC8znyG6Tc
  H9pkl+U2TfibqPhu6TZb9z1YiXjc+RoSBQlKDVMz9Jm7+Uh9+kqCqUIUhO8ToF/kqCqUIUhu
  8ToN/kqCqUIUV40PVY1PpqhKVBUV42Ph29TaEqMFQVhj/Uhl/kpGqMFQVhr/Ea7PpLhK9XPU
  VdEBmzZDqgDGAhnMAq6oBQ4ZDg4HOAif6AI2xDgKOfAE7ACQfmTIQuhI2ZEggDJAlPlAE/YC
  QpzJAlPoAE/kCQ4RFgynVgcNm41InfEq0AUpzQF7EDQsjMAVcmBIdFUpRoCP2AEeuBIdFUpR
  oCP6AEe2BIdFUpRoq44DQFnfASXDV6Coq4IEQ60Zrk9XB83+L/9b/l/+/p/l/+/A6rbSvC==
}

Timings on my machine for the individual test layers in the above:

Original traversal of the entire tree: 6 mins 36 secs
Depth by depth complete: 4 mins 59 secs
Depth by depth Location restricted: 1 min 40 secs
Depth by depth Pre-render restricted: 25 secs

The key thing is obviously to reduce the area that requires more than one transform/path on each iteration - this manifests itself in my test formula as the array size required to avoid errors rendering the "inside" - e.g. try reducing the array sizes on the depth by depth layers and you'll see the problem.

Obviously the low-resolution pre-rendered map method is best but it does suffer from problems e.g. extremely thin/small transform areas may get missed and there would definitely be memory issues for applying it in 3D - here a 256*256 pixel pre-render is no problem but 256*256*256 is starting to get a little large smiley

Edit: I should add that the depth-by-depth methods are by no means fully optimised - for instance changing the array storage to a linked list method sorted by magnitude would probably help a lot smiley
« Last Edit: February 21, 2010, 10:47:39 PM 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
Timeroot
Fractal Fertilizer
*****
Posts: 362


The pwnge.


WWW
« Reply #7 on: February 22, 2010, 02:50:03 AM »

Wow, this is sounds really interesting... I hope you help a noob like me understand it:

1) - What do you mean, "depth-by-depth"?
2) - I don't understand what the third image, with the irregular split, is supposed to represent. Is it some other way of splitting of the transforms?
3) - What's the difference between "Depth-by-depth complete" and "Depth-by-depth Location restricted"?

For the pre-render, you mentioned that memory usage could become an issue, especially in 3D. Would it be possible to just store certain "boundary points", and then if a point in question lies on one side of the area between some boundary points, and with a small margin away, a certain transform would be used, otherwise it uses both? That is, just storing the surface instead of the entire area?
 huh? huh? huh? huh? Please help baffled...
Logged

Someday, man will understand primary theory; how every aspect of our universe has come about. Then we will describe all of physics, build a complete understanding of genetic engineering, catalog all planets, and find intelligent life. And then we'll just puzzle over fractals for eternity.
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #8 on: February 22, 2010, 04:09:57 AM »

Wow, this is sounds really interesting... I hope you help a noob like me understand it:

1) - What do you mean, "depth-by-depth"?
2) - I don't understand what the third image, with the irregular split, is supposed to represent. Is it some other way of splitting of the transforms?
3) - What's the difference between "Depth-by-depth complete" and "Depth-by-depth Location restricted"?

For the pre-render, you mentioned that memory usage could become an issue, especially in 3D. Would it be possible to just store certain "boundary points", and then if a point in question lies on one side of the area between some boundary points, and with a small margin away, a certain transform would be used, otherwise it uses both? That is, just storing the surface instead of the entire area?
 huh? huh? huh? huh? Please help baffled...


1. The "usual" method of doing escape-time IFS involves traversing the entire IFS tree for each point by stepping down the tree until either bailout is reached or we get to a certain depth (or overall scale factor). If we hit bailout first then we step back up the tree by one depth and try the next transform and so on, stepping back up the tree to higher branchings each time we hit bailout and have done all transforms for that branch at that depth - obviously in this case if we hit max depth/greatest overall scale then the point is "on" the fractal.
That method works quite well but doesn't lend itself to applying the location restrictions - for that we need to start with the point to test and apply all applicable transforms on the first iteration giving us up to n new poiints where n is the number of transforms, then on the second iteration we repeat the process for all the points generated from the first iteration. Obviously as soon as one of these points bails out we do not pass it on to the next iteration. The problem with this method is that if not enough points bailout and many transforms need to be applied on each iteration then our number of points can grow exponentially though of course location restriction reduces the number of required transforms for a given point on a given iteration.

2. The third image is a zoomed out map of which pioints belong to which primary transform's area including those points that are "outside" in this case the area belonging to transform 1 (on the right) is all one colour but I've coloured the area for transform 2 so that the "inside" and "outside" are different colours - the rather small area shows you the "inside" area for transform 2 (compare with the first image to get an idea of scale). When I say the "outside" area belonging to a given primary transform I mean the area where the highest iteration bailout (with the lowest bailout magnitude) had that transform as it's primary.

3. "Depth by Depth complete" applies all transforms to the current array of points for a given iteration passing all the ones that don't bailout on to the next iteration. "Depth by depth location restricted" (and pre-render resricted) restrict the number of transforms for each of the points in the current array depending on each point's location thus reducing the number of points passed on to the next iteration.
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 #9 on: February 22, 2010, 04:42:39 AM »

For the pre-render, you mentioned that memory usage could become an issue, especially in 3D. Would it be possible to just store certain "boundary points", and then if a point in question lies on one side of the area between some boundary points, and with a small margin away, a certain transform would be used, otherwise it uses both? That is, just storing the surface instead of the entire area?
 huh? huh? huh? huh? Please help baffled...


You could limit the storage required in some way but the only way to do a really quick look-up test to decide the transforms to use for a given point is a complete set of flags indicating required transforms for the whole area within bailout - I can't really see a method using just boundary points that would work in a general case - consider Barnsley's ferns for instance, they usually have many areas of overlap so I think a complete area map is the only efficient generic method to use.
Obviously specific cases are simpler, in fact for a Sierpinski carpet or Menger Sponge then simple coordinate testing would obviously be the optiimum method.
I'm trying to develop a generic method that I can both make as "black-box" as possible and that will even work when some transforms are non-affine, though I'm considering abandoning the black-box idea in favour of making the location tests part of the actual user-parameters for the fractal i.e. a type where the user specifies location control as well as the transforms - that would be far easier from the formula author's point of view 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 #10 on: February 24, 2010, 02:49:01 AM »

First results based on Tglad's method used for location-restricted-IFS (both a distorted Sierpinski Octahedron):

"Sierpinski Sponge"



If no image above then look here:

http://makinmagic.deviantart.com/art/Sierpinski-Sponge-155198251

"Sierpinski Stone"



If no image above then look here:

http://makinmagic.deviantart.com/art/Sierpinski-Stone-155198492

They were produced with a very basic addition to my wip3D formula that only allows up to 6 transforms with just translation and scaling and decides which transform to use based on the nearest translation location, I'm hoping to expand the method and release an update at the weekend though I doubt I'll be adding rotations for now.

Logged

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

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
kram1032
Fractal Senior
******
Posts: 1863


« Reply #11 on: February 24, 2010, 03:27:26 PM »

that first image looks a lot like a 2D-Version of some of the 1D-cellular automata smiley
Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #12 on: February 24, 2010, 09:57:53 PM »

Another one, still just a distorted Sierpinski Octahedron:



If no image above then look here:

http://makinmagic.deviantart.com/art/The-Complex-155249983?loggedin=1
Logged

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

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
Timeroot
Fractal Fertilizer
*****
Posts: 362


The pwnge.


WWW
« Reply #13 on: February 25, 2010, 01:17:07 AM »

that first image looks a lot like a 2D-Version of some of the 1D-cellular automata smiley
Considering that the Sierpinski triangle can be generated using 1-D cellular automata, I actually bet you could make something like that. I wonder if anyone has a program for generating the 2D-cellular automata. It would certainly look cool....  afro
Logged

Someday, man will understand primary theory; how every aspect of our universe has come about. Then we will describe all of physics, build a complete understanding of genetic engineering, catalog all planets, and find intelligent life. And then we'll just puzzle over fractals for eternity.
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #14 on: February 25, 2010, 04:06:03 AM »

Here's another test - I added analytical DE for these IFS fractals:

http://www.fractalforums.com/index.php?action=gallery;sa=view;id=1742
Logged

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

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
Pages: [1] 2 3   Go Down
  Print  
 
Jump to:  

Related Topics
Subject Started by Replies Views Last post
Tglad's Formula crash error v1.21 Bug Reporting geomagnet 6 900 Last post February 18, 2014, 07:02:53 PM
by geomagnet
Hybri-Station on Delta 4 Images Showcase (Rate My Fractal) JoeFRAQ 1 561 Last post October 31, 2014, 02:09:53 AM
by JohnVV
tglad's trick Mandelbulber Gallery taurus 1 405 Last post July 31, 2016, 07:00:59 PM
by paigan0
IFS, KIFS, DIFS, RIFS, LRIFS. How does DEcombinate fit in? General Discussion valera_rozuvan 4 633 Last post August 03, 2016, 08:58:49 PM
by valera_rozuvan
Tweak for tglad fold Amazing Box, Amazing Surf and variations mclarekin 3 630 Last post January 20, 2017, 05:53:56 PM
by knighty

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.187 seconds with 29 queries. (Pretty URLs adds 0.014s, 2q)