Logo by Pauldelbrot - 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. March 29, 2024, 10:41:23 AM


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]   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: Ray tracing without marching?  (Read 2230 times)
0 Members and 1 Guest are viewing this topic.
willvarfar
Explorer
****
Posts: 57


« on: August 05, 2012, 11:55:33 AM »

Distance estimators give a general distance in any direction to the fractal, and you 'march' your ray closer.

If I were raytracing a sphere or cube I could instead comput the distance on the ray to intersection as a single step.

Are there similiar single-step functions for the Mandelbulb and other fractals?

that is, not using an iterative marching.
Logged
real_het
Forums Freshman
**
Posts: 13


« Reply #1 on: August 05, 2012, 09:14:05 PM »

No, it would render the fingerprint of God to a completely flat surface  grin
Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #2 on: August 06, 2012, 05:00:51 AM »

Yes there is but it would most definitely not be optimum, be tricky to get correct and be 100% non-generic i.e. require custom code not only for every formula but for each particular iteration level that you decide will be "solid".
One could solve |z(n)|==bailout and z[0] is on the viewing ray for a Julia, or |z[n]|==bailout and c (the constant) is on the viewing ray for a Mandelbrot - where n is the iteration depth that you decide is "solid", but of course solving involves solving a high degree polynomial, e.g. of degree 2^n for standard z^2+c, and finding the closest solution in front of the viewpoint.
Logged

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

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
hobold
Fractal Bachius
*
Posts: 573


« Reply #3 on: August 06, 2012, 11:58:40 AM »

As David described, this is equivalent to finding the zeros of very high degree polynomials. If you want to google around, other common jargon for this kind of thing is "polynomial roots" or "polynomial factorization". I am afraid what you find will be rather disappointing. Beyond polynomials of degree five or so, no explicit formulas exist. It isn't that they are too difficult to work out. Algebra just doesn't carry that far.

That leaves numerical methods. Those are not too promising either, because they become less and less reliable with higher degree polynomials. And they are not exactly quick.

The reason why ray marching has been the method of choice so far is that it is simply the best known method yet. That does not mean it is the be all and end all. But whatever might replace ray marching some day is unlikely to be based on polynomial factorization.
Logged
cKleinhuis
Administrator
Fractal Senior
*******
Posts: 7044


formerly known as 'Trifox'


WWW
« Reply #4 on: August 06, 2012, 01:06:14 PM »

would be interesting how far this could be pushed, e.g. if polynomals of degree 5 are directly solveable, this would mean that fractals of iteration 4 or 5 could be made really fast, although there arent real distinguished details visible at such level, i could think of applying it to a ( non-polynomal, non-continuous) mandelbox formula which looks really interesting at low iterations....
Logged

---

divide and conquer - iterate and rule - chaos is No random!
Syntopia
Fractal Molossus
**
Posts: 681



syntopiadk
WWW
« Reply #5 on: August 06, 2012, 04:37:20 PM »

Actually, the problem is worse than simple root-finding: you'd need to find the intersection of the camera ray and the level curves of the polynomium, which requires finding the norm (thus doubling the degree of the resulting polynomial - see http://en.wikipedia.org/wiki/Polynomial_lemniscate).

Take the Mandelbrot polynomials: to solve the *first* iteration, you'd need to solve ||z^2+z|| = Bailout (with z on a line). This requires solving a fourth order equation - something which is already not trivial.
Logged
hobold
Fractal Bachius
*
Posts: 573


« Reply #6 on: August 06, 2012, 08:42:47 PM »

would be interesting how far this could be pushed, e.g. if polynomals of degree 5 are directly solveable, this would mean that fractals of iteration 4 or 5 could be made really fast,
Beware, the explicit methods for these cases are neither pretty nor quick. They are complicated algorithms rather than straight forward formulas. Some of the special cases may require the solution of other nontrivial subproblems. And all of that would happen in the context of symbolic computation, with "infinite" precision arithmetic to boot.

Ray marching ain't so bad, really. Especially in the context of GPU computation, ray marching has an unbeatable advantage in that it is very regular with respect to conditional branching. GPUs can easily leverage their full power here.
Logged
willvarfar
Explorer
****
Posts: 57


« Reply #7 on: August 06, 2012, 09:50:46 PM »

Ray marching ain't so bad, really. Especially in the context of GPU computation, ray marching has an unbeatable advantage in that it is very regular with respect to conditional branching. GPUs can easily leverage their full power here.

Well true its unbeatable but I'm not sure that its very regular with respect conditional branching especially in the looping.  Its maximum pessimism within each warp with the whole warp - 32 threads in NVIDIA and 64 in ATI - waiting for the deepest ray march in their warp to complete?
Logged
Syntopia
Fractal Molossus
**
Posts: 681



syntopiadk
WWW
« Reply #8 on: August 06, 2012, 10:23:02 PM »

Quote
Well true its unbeatable but I'm not sure that its very regular with respect conditional branching especially in the looping.  Its maximum pessimism within each warp with the whole warp - 32 threads in NVIDIA and 64 in ATI - waiting for the deepest ray march in their warp to complete?

A warp should process neighboring pixels, so there should be a good deal of coherence: close rays (in screen space) probably use nearly the same amount of ray marching steps and formula iterations.
Logged
willvarfar
Explorer
****
Posts: 57


« Reply #9 on: August 06, 2012, 11:02:08 PM »

I'm not going to argue as your expert weighing-in has weight with me but the mental model I've implicitly built up from trial and error and adjusting things and seeing how the shaders perform has me thinking there's usually at least one noisy fragment in each warp unfortunately =(
Logged
hobold
Fractal Bachius
*
Posts: 573


« Reply #10 on: August 07, 2012, 10:52:30 AM »

I'm not going to argue as your expert weighing-in has weight with me but the mental model I've implicitly built up from trial and error and adjusting things and seeing how the shaders perform has me thinking there's usually at least one noisy fragment in each warp unfortunately =(
Oh, you are very right. Ray marching is far from perfect in that regard. It's just that a more "typical" or "average" algorithm (however you would want to measure that) is much worse, and wastes many more execution resources on irrelevant computation that ultimately has to be discarded.

It has come to the point where people do explicit sorting passes to separate the wheat from the chaff, so to speak. They call that "stream compaction". I believe that SIMD hardware can and will eventually evolve to alleviate these problems. For example, the later models of the original Cray vector computers had a "split" instruction. It was based on an earlier minicomputer instruction named "bit gravity", which would change the order of bits in a word according to a boolean mask.

Cray's "split" would effectively sort all vector elements within one vector, corresponding to a boolean mask with one bit per vector element. After the split, all elements with a "true" condition would be piled up on the left side of the vector, and all "false" elements were on the right.

Now imagine you extended this idea to work across a pair of vector registers (with a pair of conditional masks as well). All the "true" elements would be at the left side of the vector pair, and all the "false" elements would be on the right side. Consequently, at least one vector of the pair would be uniform, and contain only elements that all share the condition. That half of the result can then be taken through a processing path without wasting effort on vector lanes that have gone dead.

I call that a "conditional vector pair split".
Logged
Syntopia
Fractal Molossus
**
Posts: 681



syntopiadk
WWW
« Reply #11 on: August 07, 2012, 11:10:12 AM »

Willvarfar, you are probably right - I haven't really checked performance - I've just heard the coherence thing repeated many times, and started to believe it :-).

Another thing I'd like to know, is how the GPU organises fragment shader pixels into blocks, i.e. is a warp processing 8x4 pixel blocks, when you draw a fullscreen quad? I couldn't find the information, but it should be possible to detect, by drawing checkerboard patterns, where only one color is the result of a long calculation. I think I'll give it a try tonight.

Stream compaction would be difficult for ray marching I think - finding out which pixels needs the most work probably requires doing the whole calculation in advance. And it would certainly require something stronger than GLSL (though the new Computer Shaders in OpenGL 4.3 might help).

It would be nice if there was a way to stencil out a subset of pixel that a fragment shader should execute - so that the GPU could spend more passes on difficult pixels.
Logged
willvarfar
Explorer
****
Posts: 57


« Reply #12 on: August 07, 2012, 11:35:35 AM »

yes, all my threads here have been concerned with improving fps but I am a novice smiley

the rod marching approach worked only a little bit; most of you have monster GPUs and my test scene was too simple, whereas at the budget end where I live it didn't make more than 25% improvement.  on the CPU without warps it made a fantastic order of magnitude difference.  of course, it seemed buggy; is it fundamently flawed, or is my epsilon all wrong?

CUDA can do sorting.... GLSL ought to be able to approximate it too if we only think it through.  can't see an obvious way though without diectx11 geometry shader reading a bimap.

I'd really like to see the checkerboard test!
« Last Edit: August 07, 2012, 12:09:40 PM by willvarfar » Logged
Pages: [1]   Go Down
  Print  
 
Jump to:  

Related Topics
Subject Started by Replies Views Last post
What is ray marching General Discussion ricbennet 12 10281 Last post April 02, 2012, 09:48:41 PM
by David Makin
Ray Marching Distance Functions Programming asimes 13 7730 Last post November 11, 2014, 08:16:20 PM
by asimes
rod marching Programming willvarfar 14 2791 Last post August 02, 2012, 10:42:16 AM
by willvarfar
Hello all!! One more Newb in the marching ranks Meet & Greet mtnlivin23 3 647 Last post October 04, 2013, 06:33:03 PM
by Nahee_Enterprises
A collection of resources on Ray Marching Programming valera_rozuvan 1 1114 Last post August 21, 2016, 03:38:05 AM
by lycium

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.22 seconds with 24 queries. (Pretty URLs adds 0.01s, 2q)