🔒 Locked

Rendering Algorithm Idea (Feedback Wanted)

Started by Max_Payne Apr 12, 2006 at 2:32 PM 30 replies 3.2k views

Original Post

Apr 12, 2006 at 2:32 PM

Allright. Some of you probably saw my thread on lens simulation, and the idea of "forward raytracing" (from light to camera), and probably went "forward raytracing, why???". The reason why is because I had an idea for a new rendering algorithm. At least I believe it's new. I decided I might as well share it with you because I will need some help with the mathematical details and more people thinking about it could mean more ideas. I also think that it's good to share resources. So in other words, this thread is a request for feedback, and possibly for help if you're interested (I do plan on implementing it). A little introduction... A long time ago (in the 70s I believe), someone had the idea that by simulating light transport (individual photons) from lights to cameras (forward raytracing) in a geometric manner, it might be possible to generate synthetic images. However, this idea was quickly abandoned as calculations showed this would take decades to do in any 3D scene on any computer of the time. So raytracing was born, and died very soon after. It was only when Whitted brought the idea of backward raytracing that the whole concept of raytracing became conceivable and interesting to computer scientists in general. Then many techniques were developped to essentially develop efficient global illumination through extensions of backward raytracing. To this day, the idea of forward raytracing remained pretty much dead. It is still impractical. On a moden computer, it can take weeks to generate a decent image. However, if you notice, this is also true with backward raytracing, to some extent. If perfectly naive backward monte-carlo path tracing is performed (bouncing randomly, hoping rays may eventually hit lights), it can take weeks to generate an image too! The idea... What if we actually used the intelligent techniques developed for backward raytracing to do forward raytracing? I can hear some people say "HUH!" already... But wait... 1) Biasing the rays... If instead of tracing rays and making them bounce randomly, we biased rays at each point *towards the camera*. This would seemingly greatly increase the rate of convergence. This is similar to biasing rays towards lights in path tracing. A pinhole camera could be used (bias rays towards camera origin), but more naturally, a camera with an actual thin lens would be best. However, one point in the scene may hit multiple points in the image plane depending on the lens parameters and point in the scene. Hence, a method to compute what lens points correspond to image plane points given a scene point may be needed. For a given scene point, all of its contributions to image plane pixels could then be computed *at once*. Hence depth of field could come *for free*. The niceness here is that we are biasing rays towards the camera, but there is *only one camera*, and it should be very fast to know if a point is within the visible frustum of the camera and if it's worth doing some computations at all. 2) Photon mapping... A photon map could be built *as the path tracing is being performed* to store information about the *outradiance* (outgoing directions) instead of the irradiance (incoming photons). What should probably be stored is the directions of photons that eventually ended up contributing in the image plane, and possibly their degree of contribution. From this information, it could be possible to gather information about how likely a given emission direction is to result in contributions in the image plane. This could be used to perform importance sampling (more photons towards more important directions). 3) Progressive refinement If we need to get more samples at a particular point on the image plane to reduce the variance, it might be possible to "request" them by computing the world points that are visible from that image point and then biasing photons towards that point. Speed... I don't know exactly how fast this all would be... But it should be much faster than plain forward path tracing. It may even be able to compete with backward path tracing in fact, because of its inherent simplicity. If we assume that there is only *one* camera in the scene, then biasing rays so they hit this single camera should be fairly easy. I find there is some "neatness" in such an idea because forward raytracing is more "natural" than backward raytracing. It may also be easier to simulate some optical phenomena in a more realistic manner.

acid2

Apr 12, 2006 at 2:55 PM

My main question that you don't seem to have covered is - why? I can't see forward rt'ing have any visible impact that backwards couldn't accomplish. Granted, I don't know a lot about raytracing and sure haven't tried implementing anything so I'm not one to judge. I agree with the "natural" feel, and I do like that.

One thing, it won't be as fast as backwards rt from a quick think because you've got to do a calcusation on each ray/bounce just to make sure that it is going to hit the camera. Also, your going to effectivly guess the whole simulation.

Consider a light, and 2 spheres - 1 diffuse, 1 reflective. For you're technique to work as fast as you want, you need to bias all (3/4?) bounces to get the camera. Seems like a bit more hassle than its worth, imo.

Interested, but I'm not sold yet ;)

Max_Payne

Apr 12, 2006 at 3:26 PM

Quote:
Original post by acid2
One thing, it won't be as fast as backwards rt from a quick think because you've got to do a calcusation on each ray/bounce just to make sure that it is going to hit the camera. Also, your going to effectivly guess the whole simulation.

Well, in forward path tracing you're effectively biasing rays towards lights at each bounce (alot of them on the first estimate too). So it is in fact similar. Granted if you want DOF you're biasing more rays on subsequent bounces. However, each ray you bias to the camera is alot of useful information.

I might try it with a pinhole camera "just for kicks". The only problem I can see is specular surfaces, which are going to be a problem because the reflected direction is "exact"... So you can't just go and trace a ray from a perfectly specular point to the pinhole camera origin.

Quote:
Consider a light, and 2 spheres - 1 diffuse, 1 reflective. For you're technique to work as fast as you want, you need to bias all (3/4?) bounces to get the camera. Seems like a bit more hassle than its worth, imo.

Interested, but I'm not sold yet ;)

Well the whole idea is... In backwards raytracing, you want to shoot rays from the camera and sample *every possible path*, as much as possible. Because everything that potentially receives light is a direct/indirect light source, which affects the outcome. This can produce an expanding three of ray paths.

In this algorithm, we start from the (potentially multiple) light sources and try to hit the camera. This corresponds, at least it seems to me, to a narrowing tree of paths. At first there are multiple sources, but there really is only one target. Obviously you want to vary your paths, but the less probability there is of hitting the camera lens, the less importance there is to go and sample that light path. So basically, since there is only one small end target, it should be possible to more easily direct the computations at what is relevant.

I might try to implement this (just the camera biasing) with a diffuse box and a pinhole camera, to see how it goes... And if it has any potential at all in the speed and convergence department.

nefthy

Apr 12, 2006 at 6:17 PM

I don't know much about ray tracing, with that said.

In backward ray traycing you can garantee that every pixel has a ray passing through it. I don't see how you can garantee that with your aproach. You would very likely end up with "holes" in the image.

Eelco

Apr 12, 2006 at 6:28 PM

what do you mean by biasing? if you want a physical simulation, the laws of physics should pretty much dictate where your rays are going to go to: any biasing away from that is a step away from reality.

i think the most optimal method is a two-way system. trace both rays away from the camera, and away from the lights, store this information in some sort of photonmap, and make these trees of photons work towards eachother, making use of eachothers presence to give an indication of importance.

Max_Payne

Apr 12, 2006 at 7:47 PM

Quote:
Original post by Eelco
what do you mean by biasing? if you want a physical simulation, the laws of physics should pretty much dictate where your rays are going to go to: any biasing away from that is a step away from reality.

Actually, diffuse surfaces can emit ray in any direction of the hemisphere... So you can choose to sample wherever you want (eg: one random path ray and one ray towards the camera if it is reachable). Monte-carlo path tracers typically try to sample one light for each path bounce.

Eelco

Apr 13, 2006 at 3:21 AM

Quote:
Original post by Max_Payne
Quote:
Original post by Eelco
what do you mean by biasing? if you want a physical simulation, the laws of physics should pretty much dictate where your rays are going to go to: any biasing away from that is a step away from reality.

Actually, diffuse surfaces can emit ray in any direction of the hemisphere... So you can choose to sample wherever you want (eg: one random path ray and one ray towards the camera if it is reachable). Monte-carlo path tracers typically try to sample one light for each path bounce.

yeah, you can trace a ray directly onto the camera and have it stop there, there is no harm in that, but that wont help in most situations for convergence i believe.

Max_Payne

Apr 13, 2006 at 5:57 AM

Quote:
Original post by Eelco
Quote:
Original post by Max_Payne
Quote:
Original post by Eelco
what do you mean by biasing? if you want a physical simulation, the laws of physics should pretty much dictate where your rays are going to go to: any biasing away from that is a step away from reality.

Actually, diffuse surfaces can emit ray in any direction of the hemisphere... So you can choose to sample wherever you want (eg: one random path ray and one ray towards the camera if it is reachable). Monte-carlo path tracers typically try to sample one light for each path bounce.

yeah, you can trace a ray directly onto the camera and have it stop there, there is no harm in that, but that wont help in most situations for convergence i believe.

It will help. Just like biasing rays towards lights in path tracing helps. Rays that don't ever end up hitting the camera are of no interest in this case. More significant rays translates into less wasted work. How much it will help and whether the speed will be even close to that of a traditional path tracer is another question.

Max_Payne

Apr 14, 2006 at 12:06 AM

A quick "proof of concept" implementation.... Rendering time is 5 minutes. No special optimizations.

DonnieDarko

Apr 14, 2006 at 6:43 AM

Err, is that a screenshot of pure forward raytracing where photons are emitted from the lightsource, bounced around the scene and finally intersecting the image plane? How many photons are emitted?

Max_Payne

Apr 14, 2006 at 7:50 AM

Quote:
Original post by DonnieDarko
Err, is that a screenshot of pure forward raytracing where photons are emitted from the lightsource, bounced around the scene and finally intersecting the image plane? How many photons are emitted?

9.6 millions or so. And no it's not pure naive forward raytracing, it's Max Tracing (TM) ;)

Spoonbender

Apr 14, 2006 at 7:57 AM

Quote:
Original post by Max_Payne
It will help. Just like biasing rays towards lights in path tracing helps. Rays that don't ever end up hitting the camera are of no interest in this case.

So what's the point? Why not do backwards raytracing where you're *sure* that your rays will hit the camera?

What's the benefit supposed to be?

Second, the reasoning behind your algorithm seems to go something like this:
Forward raytracing is slow
Backward raytracing is slow too, but can be improved upon to become almost acceptable.
So if we apply the same improvements to forward raytracing, that will become almost acceptable too.

But there's one glaring hole in this. You assume that with no optimizations, forward and backward raytracing are equally slow.
What if someone were to point out that forward is *a lot* slower "by default", so even if you apply your improvements, the results will be *a lot* slower than a good backward raytracer?

And you might be able to "guess" at the likelyhood of a ray hitting the camera, but what if you're wrong? You'll end up either with big glaring "blank areas" on the image, or you'll waste time tracing rays that never contribute to the image. How do you propose to find out when all the neccesary input has been gathered? How do you ensure that you can actually find a way to hit every pixel on the resulting image? Even if you solve all the other problems, of actually hitting the camera, and hitting every pixel on the camera from every relevant light source, you'll still run into floating point precision problems. Hitting one tiny *exact* point (a point on the camera) from something at the other end of the scene (the light source) is pretty much impossible. Won't you get rounding errors, so your rays all hit the same few points on the camera?

Basically, as you say, lots of clever academics have spent decades poring over this. The only way they found to make it work was through backward raytracing. I'm guessing that "your" algorithm has been considered by them too. And found too slow.

Woodchuck

Apr 14, 2006 at 8:21 AM

Quote:
Original post by Max_Payne
A quick "proof of concept" implementation.... Rendering time is 5 minutes. No special optimizations.

So coool !

Max_Payne

Apr 14, 2006 at 10:19 AM

Quote:
I'm guessing that "your" algorithm has been considered by them too. And found too slow.

That kind of thinking has always helped scientific progress ;)

Max_Payne

Apr 14, 2006 at 11:16 AM

Quote:
Original post by Anonymous Poster
I'm guessing the grey spots are where no light ray found the camera?

The black parts on the front of the small box are. The cornell box is open, so there is a very small probability of rays hitting the front of that box (most will get lost in space). I think this could be improved through photon mapping.

Dmytry

Apr 14, 2006 at 1:56 PM

you can try doing that: on every bounce, trace one ray to the camera (with intensity proportional to probability of ray going in this direction. this ray doesn't bounce more)
and bounce second ray in random direction as normally.
It would increase intensity of image twice tho.

By the way, with biasing towards the camera, there's one large problem: consider mirror. for image in the mirror to look nice, you'll need to also bias rays towards the camera's reflection in the mirror. That would be impractical for complex scenes. And so, image in reflection would badly converge. What's the point in raytracer if it doesn't do reflections?

BTW, you may find metropolis light transport and other advanced "modern" methods interesting...

ApochPiQ

Apr 14, 2006 at 2:05 PM

Here's my thoughts, roughly in order:

Bias rays towards camera. This will cause problems in everything but painfully trivial scenes.

Consider a scene with the camera standing in a corner of an extremely large room, looking into the middle of the room. The distant walls are too far away to be lit. All light comes from diffuse interreflection from a spotlight on the back of the viewer's head pointing into the corner.

This approach will waste a monumental amount of time trying to render that really trivial scene.

So obviously the solution is to use heuristics that guarantee that biased rays eventually wind up on a path that reaches the camera.

Can we derive a heuristic that guarantees this 100% of the time?

As a matter of fact, we can. It's called backwards raytracing.

Think of it this way: neglect all GI phenomena and just do first-strike lighting. Your method will always be slower than Whitted raytracing.

Reintroducing GI, any bias you add to the GI simulator photons will bias the final result unless you're extremely careful. Biasing simulator photons into the camera will skew the results subtly in most scenes. In some cases it will just produce slow chaos, like the corner-of-the-room example above.

So really, any work you do here is just going to be a lot of effort to reach the ceiling of Whitted-visualization and, say, photon mapping. That is your theoretical maximum limit; you can't get it any faster except in certain contrived edge cases (and then only maybe).

Therefore, it makes a lot more sense to start with Whitted-visualization/photon mapping as your initial point, and work on improvement from there.

Rockoon1

Apr 15, 2006 at 2:17 PM

Please note that the rays are not going to be hitting the quantized rendering surface at equal intervals. Some sort of guasian filter seems implied, idealy performed during the accumulation phase but perhaps simply as a post-process?

taby

Apr 17, 2006 at 1:02 PM

Perhaps make a 3D float scalar field and store the light parameters at each spot in the environment, building up an environmental light map based on local opacity, surface normal, and all incoming/outgoing photons.

If you lower the resolution of the field so that it is apparently not per-pixel when projected to 2D, you can use it to blend into the final image by using the traditional forward ray-tracing method; perfectly straight marching rays that take into account the rgba data of both images, in whichever way you like.

Perhaps the blend could be:

vec4 R4_FinalImage.rgb = R4_ReverseTraceImage.rgb + (1.0 - R4_ReverseTraceImage.a)*R3_ScalarFieldTexture[R3_ReverseTraceLocation.xyz].rgb

R4_FinalImage.a = R4_ReverseTraceImage.a + R3_ScalarFieldTexture[R3_ReverseTraceLocation.xyz].a

R4_FinalImage = Clamp(R4_FinalImage, 0.0, 1.0)

[Edited by - taby on April 17, 2006 1:02:34 PM]

Max_Payne

Apr 17, 2006 at 2:25 PM

Quote:
Original post by taby
Perhaps make a 3D float scalar field and store the light parameters at each spot in the environment, building up an environmental light map based on local opacity, surface normal, and all incoming/outgoing photons.

If you lower the resolution of the field so that it is apparently not per-pixel when projected to 2D, you can use it to blend into the final image by using the traditional forward ray-tracing method; perfectly straight marching rays that take into account the rgba data of both images, in whichever way you like.

Perhaps the blend could be:

vec4 R4_FinalImage.rgb = R4_ReverseTraceImage.rgb + (1.0 - R4_ReverseTraceImage.a)*R3_ScalarFieldTexture[R3_ReverseTraceLocation.xyz].rgb

R4_FinalImage.a = R4_ReverseTraceImage.a + R3_ScalarFieldTexture[R3_ReverseTraceLocation.xyz].a

R4_FinalImage = Clamp(R4_FinalImage, 0.0, 1.0)

I don't see exactly what you mean. I tried using photon mapping directly for information about the local indirect irradiance once, and it looked really bad. It's true that photon mapping is kind of inefficient as an information storage though, it's really designed to get an estimate and not much else.

If there was a method to generate a 3D "texture" over the environment (if possible without resorting to an actual texture map), then it might actually be efficient and quick, however.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.