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:
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):
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
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