• January 21, 2021, 09:14:01 AM

Login with username, password and session length

Author Topic:  Algorithm for Full Exploration of 3D Fractal in Realtime  (Read 814 times)

0 Members and 1 Guest are viewing this topic.

Offline AranLeer

  • Fractal Phenom
  • ****
  • Posts: 45
Algorithm for Full Exploration of 3D Fractal in Realtime
« on: April 24, 2019, 06:46:22 PM »
Hello Everyone.

For a long time I have been developing algorithms for realtime viewing and exploration of 3D fractals, and have finally come up with a solution that lets me fully explore various 3D fractals all the way from the outside down to double-precision decimal quality (from a distance of 5 units, down to 5x10-15 units, which would be the equivalent of seeing the nuclei of atoms if the whole fractal was the size of a beach-ball).

Essentially, the heart of the algorithm is splitting the rendering process into two separate parts: raymarching (like normal), and point-cloud rendering.

Instead of trying to raymarch the whole image at once for each frame, it is possible to instead raymarch a random spread of screen pixels, then cache the resulting color data into 3D points, which are then rendered to the screen in the place of a static image. The result is that over a small amount of time, enough points are calculated to result in a fully-detailed image of the area of the fractal that is in front of the camera. But unlike a dynamic resolution algorithm, when you start moving the camera you don't loose any of the calculated detail. The previously calculated points are just rotated and translated as the camera moves, so they are still valid and don't need to be recalculated using the slower raymarching process. For the purposes of maintaining a more solid infill, points are rendered larger than a single pixel, but only update the depth-buffer at the center, which allows for quick blocky infill, but still allows the image to resolve to pixel-quality given enough points.

The overall result then is that you will see initial artifacting that will look like the image is out of focus, but it will quickly resolve to a reasonable quality. Then when moving the camera, parts of the fractal that you have been viewing will continually gain more and more detail, while parts of the fractal that were outside the viewing frustum or occluded by other parts of the fractal will again show momentary artifacting as those parts are resolved.

The whole process is fast enough, though, that it can be run CPU-only and maintain reasonable framerates with several hundred-thousand points. However, I was able to get a significant improvement to framerate (or maintain a similar framerate with around a million points) and infill speed (the speed that the image fills up with points) by offloading the point-cloud rendering to the GPU, which opened up more of the CPU for more raymarching.

I don't know for sure if this is a technique that has not been done before, but I haven't been able to find references to similar algorithms.
But please let me know if this has already been done, as I don't want to just repeat something that has been seen before :) .

Also - the algorithm was not specifically designed to generate high-quality images. Rather it was designed to allow full freedom of exploring 3D fractals in realtime. I will still attach some screenshots and videos (if I can) of the program in action, but please note they will not be the most beautiful things on this forum.

This is more for people interested in the idea of being pioneers, diving into the nearly infinite unknown depths of the fractal universe.


Anyway, for anyone who has read this far down, thank you so much for your time. I really appreciate any comments or advice for continued improvements that can be made to the algorithm.

Sincerely
- Luke

Linkback: https://fractalforums.org/fractal-mathematics-and-new-theories/28/algorithm-for-full-exploration-of-3d-fractal-in-realtime/2771/

Offline AranLeer

  • Fractal Phenom
  • ****
  • Posts: 45
Re: Algorithm for Full Exploration of 3D Fractal in Realtime
« Reply #1 on: April 24, 2019, 06:48:01 PM »
If possible, I would like to also share some videos I have of exploring the fractal, but I'm not sure how to show them here. They are currently mp4 (or just a bunch of images I used to create the mp4), but that is not one of the supported video formats on this forum. Is there a format that supports a 30+ second video post?

Offline hobold

  • Fractal Fluff
  • *****
  • Posts: 391
Re: Algorithm for Full Exploration of 3D Fractal in Realtime
« Reply #2 on: April 24, 2019, 10:54:44 PM »
The method you outlined sounds like a really good approach for re-using previously computed surface points. I think your algorithm is very similar in spirit to a method called reprojection. But that one was originally used only to speed up stereoscopic rendering specifically, so your method seems to be a generalization.

Thanks for sharing! This could be one of the more powerful tools for realtime exploration.

Offline 3DickUlus

  • Administrator
  • *******
  • Posts: 1979
    • Digilantism
Re: Algorithm for Full Exploration of 3D Fractal in Realtime
« Reply #3 on: April 25, 2019, 06:59:04 AM »
Hi, this sounds great!

We don't host videos here on FF but I would like to see some video of your program in action, maybe post on youtube or vimeo and we can embed them here in posts using the vimeo or youtube buttons, just blockmark the link text in the "Post" editor and select the vimeo or youtube button...
[youtube]https://link to your youtube vid[/youtube]  or [vimeo]https://link to your vimeo vid[/vimeo] and voila! the thumbnail is displayed and the video is played when clicked on :D

Offline AranLeer

  • Fractal Phenom
  • ****
  • Posts: 45
Re: Algorithm for Full Exploration of 3D Fractal in Realtime
« Reply #4 on: April 25, 2019, 01:59:40 PM »
Thank you!
That sounds perfect.
I'll give it a go, and see if I can upload the videos to a Youtube channel and link them here soon.

Offline AranLeer

  • Fractal Phenom
  • ****
  • Posts: 45
Re: Algorithm for Full Exploration of 3D Fractal in Realtime
« Reply #5 on: April 25, 2019, 03:10:10 PM »

Here is my first try with a video.
Hopefully it works! :)

Offline AranLeer

  • Fractal Phenom
  • ****
  • Posts: 45
Re: Algorithm for Full Exploration of 3D Fractal in Realtime
« Reply #6 on: April 25, 2019, 04:04:26 PM »

Here's a brand new one exploring one of the side-bulbs of the fractal, which looks a lot like a forest.

Offline AranLeer

  • Fractal Phenom
  • ****
  • Posts: 45
Re: Algorithm for Full Exploration of 3D Fractal in Realtime
« Reply #7 on: April 25, 2019, 05:31:36 PM »

This time, an alternate fractal equation, which is much more spiky.

Offline xenodreambuie

  • Fractal Friar
  • *
  • Posts: 106
Re: Algorithm for Full Exploration of 3D Fractal in Realtime
« Reply #8 on: April 26, 2019, 12:37:44 AM »
This method is known as point splatting, and is used for fast visualization of point clouds. There are papers on the method that use circles or ellipses, oriented by a local normal. Just because the general method isn't new doesn't mean you shouldn't develop it specifically for 3D fractals; I don't recall anyone else implementing it for fractal raymarching.

Offline AranLeer

  • Fractal Phenom
  • ****
  • Posts: 45
Re: Algorithm for Full Exploration of 3D Fractal in Realtime
« Reply #9 on: April 26, 2019, 01:23:18 AM »
Ok, cool! Thank you for the information. :)

I figured there had to be something like it. I originally came up with this idea after hearing about Oculus' "Space Warp" technique for speeding up VR rendering. It's a similar concept that prioritizes camera framerate over object update framerate.

Offline 3DickUlus

  • Administrator
  • *******
  • Posts: 1979
    • Digilantism
Re: Algorithm for Full Exploration of 3D Fractal in Realtime
« Reply #10 on: April 26, 2019, 02:50:28 AM »
 O0 :clapping: :thumbs_up_by_craig_m:

Offline TGlad

  • Fractal Friar
  • *
  • Posts: 113
    • Scale symmetry page
Re: Algorithm for Full Exploration of 3D Fractal in Realtime
« Reply #11 on: April 26, 2019, 03:54:01 AM »
Very awesome AranLeer,

 you are exploiting frame coherence. It assumes that your viewpoint will not change a great deal from one frame to the next. I think it is a nice idea.

Another idea would be to 'warm start' the ray tracing iterations each frame by using the 3D points or the depth buffer as a starting guess for the ray location. There are a few interesting ideas in this area, and I think you might even be able to build on yours, for example, what extra data could these 3D points cache? a radius? a normal? an 'age' to decide when to update?

 How does it compare with GPU raytracers like Boxplorer? does it allow more detail in realtime?

Offline AranLeer

  • Fractal Phenom
  • ****
  • Posts: 45
Re: Algorithm for Full Exploration of 3D Fractal in Realtime
« Reply #12 on: April 26, 2019, 05:05:02 AM »
It's funny you should mention the "warm start" idea. One of the first successful realtime 3D fractal algorithms I designed focused on that idea, and worked quite well. Essentially each screen pixel held a depth value and would simply move forward or backward each frame. It was actually very efficient, but the only issue is that it was very inaccurate when dealing with thin or layered parts of the fractal, causing very very heavy artifacting around any detailed parts of the fractal. I had several additional parts to the algorithm that helped, but not enough for detailed exploration.

I could share some visuals from that program if yoy'd like, just to compare.

I do definitely think more can be done to improve the algorithm. I like the idea of caching more useful data, but will have to think more about what.

As far as comparisons to other programs, I have tried looking up other ones, but haven't really found many that offer free first-person movement to compare against. Does Boxplorer do that? That would just offer the best 1-to-1 comparison.

Offline TGlad

  • Fractal Friar
  • *
  • Posts: 113
    • Scale symmetry page
Re: Algorithm for Full Exploration of 3D Fractal in Realtime
« Reply #13 on: April 26, 2019, 07:34:08 AM »
Yes I think Boxplorer is the closest one I know for realtime GPU rendering: https://sourceforge.net/projects/boxplorer/

Yes, edges are a problem for the basic warm starting. I think you'd do something like take the minimum depth of the last pixel with the 8 surrounding pixels, or something like that, to allow you to 'notice' when a new closer surface occludes the pixel. Anyway, yeah, nice work.


xx
Fractal exploration: Sightlines

Started by Deliberate Dendrite on Fractal movie gallery

4 Replies
329 Views
Last post January 03, 2021, 08:55:44 AM
by hgjf2
xx
Tripping Eye - Psychedelic Deep Dream Fractal Journey - Full HD

Started by schizo on Fractal movie gallery

0 Replies
577 Views
Last post September 09, 2017, 11:43:06 PM
by schizo
xx
Algorithm for Rendering Slope in a Fractal

Started by LionHeart on Programming

131 Replies
3456 Views
Last post April 14, 2020, 09:07:51 PM
by mrrudewords
clip
"varanasi", fractal realtime music visualisation with "matrjoschka mirror balls"

Started by udo2013 on Fractal movie gallery

0 Replies
256 Views
Last post July 08, 2019, 12:17:58 AM
by udo2013
xx
room full of mirrors

Started by mclarekin on Fractal Image Gallery

0 Replies
151 Views
Last post July 17, 2018, 08:59:48 AM
by mclarekin