Skip to content

Experiment 1 Raycasting Shadows : Iterative Optimizations

Sarthak Agrawal edited this page Jun 18, 2019 · 1 revision

The problem

With batching we have been able to reduce the triangle count by a significant amount without compromising with the resolving power. But 180 rays don't really provide that neat of a resolving power. Heck, even 360 rays or 720 rays don't cut it. You need at least 1000 rays. But what's the real problem with resolving power? This -

Zoomed in view of a corner of obstacle

What you see in zoomed-in view of corner of obstacle cube. The white thing is our generated mesh. Look how the generated mesh overlaps with the obstacle instead of passing sharply through the corner. It's pretty easy to easy why this is the case. It is because none of rays (denoted by red) we cast happen to pass through the corner of our obstacle. As we increase the number of rays the rays would pass closer and closer to the obstacle and at about 1000 rays the difference is less enough to ignore.

But, this is just a zoomed in picture. In actual scale you won't really see that much of a difference even with 180 rays. Unless you look very carefully you will find that 180 rays are good enough. So what's the big deal?

Everything works fine until you start moving your raycaster. As you move it around, the overlap you mesh with obstacle you see right now increases and decreases depending on how and where you move it. At any instant the overlap is insignificant enough to ignore but what you would notice is that the movement is jittery! Although the eyes don't really notice the overlap, our eyes do notice that overlap is changing with movement. This not only gives a jitter but also unrealistic rendering. Once you catch the jitter you start noticing the flaws in the system.

The Solution

There is only one way to prevent this. We need to somehow be able to have rays pass through the corner. Until and unless the rays don't pass through corner the changing overlap would produce jitter. Now, there are 3 ways to achieve this -

  1. Increase resolving power by increasing number or rays. As I said many time, 1000 is the mark.
  2. Pre-store the location of all vertices (corners to check for) in the scene in raycaster and only casts rays at these pre-selected vertices. Perhaps, the most efficient method of all but you need to have information about corners before hand plus this method can not handle curved surfaces.
  3. And this is what is actually used, iteration to make rays pass closer to obstacle.

The iterative method of optimization

In the previous article on mesh optimization I already stated that slope change is an indication of either change in surface or a curved surface. First, let's look at how can we ascertain that which of these is the current case.

It's easy. Cast another ray (yes, another!) along the angular bisector of the 2 rays whose slope shows change. Record the normal of this ray, let's call it mid_normal. Under reasonably accurate set of assumptions, following can be said -

  1. if mid_normal == normal_before or normal_now, this is a change in surface.
  2. else, this is a curved surface.

Now, if we find that there is a change in surface, we apply a iterative process to get closer to the corner point with each iteration.

    _theta = theta_before
    theta_ = theta_now
    loop for n times:
        cast ray at (_theta + theta_)/2 , store data : mid_normal, mid_end_point
        if mid_normal == normal_now:
            replace the last position in array of end points with mid_end_point
            _theta = mid_theta
        else:
            make current_end_point = mid_end_point
            theta_ = mid_theta

As might be obvious, after each iteration the we double the resolving power. That is to say, before any iteration the corner was resolved with an error of 2 degrees. After one iteration the error become 1 degree, after second iteration the error becomes 0.5 degrees and so on. Let's see how this looks in action.

4 Iterations

(The same case as before, this time applied iterative optimization with 4 iterations)

8 iterations

(This time, with 8 iterations, the difference is invisible to the eyes)

Now you can appreciate the power of this method. The triangle count remains same and we only have to cast a handful of extra rays to achieve even more resolving power than that is possible even by using 1000 rays.

You can play with the number to best suit your needs. I think 4 iterations is a good start. After 4 iterations, corners look as sharp as object and jitter is negligible. For better results you can try 8 iterations.

After all is said and done, this is how this all looks put together -

The final image