Author Topic: Raytracing and rimlight optimisation.  (Read 3290 times)

Calin Leafshade

  • Long live King Cat!
    • I can help with making music
    • I can help with voice acting
    • Calin Leafshade worked on one or more games that won an AGS Award!
    •  
    • Calin Leafshade worked on one or more games that was nominated for an AGS Award!
Raytracing and rimlight optimisation.
« on: 31 May 2012, 19:00 »
So, i made this: http://dl.dropbox.com/u/27247158/shadow.zip
(move the mouse around the character to see the effect)

Its a ray tracer that adds rim lighting to sprites when they are near a light.

However its *very* expensive.

Currently the light 'searches' for characters and draws the light as it finds them.
Surely since the lighting is *only* applied to characters I should be able to draw the effect per character without tracing a full circle around the light.
Does anyone have any insight on how to do this?

I will post some code snippets with how i did it. (messily)



Code: Adventure Game Studio
  1. void Light::Draw()
  2. {
  3.   int i;
  4.   while (i < Game.CharacterCount)
  5.   {
  6.     if (character[i].Room == player.Room)
  7.     {
  8.      
  9.       ViewFrame *vf = Game.GetViewFrame(character[i].View,character[i].Loop, character[i].Frame);
  10.       charSprites[i] = DynamicSprite.CreateFromExistingSprite(1); //reset the sprite. this will need to be more complex with actual animating sprites but thats by the by atm.
  11.       vf.Graphic = charSprites[i].Graphic;
  12.     }
  13.     i++;
  14.   }
  15.   float u = 0.0;
  16.   while (u < 360.0)
  17.   {
  18.     raycast(this.ID, u);  
  19.     u += degStep;
  20.   }
  21.   ds.Release();
  22.  
  23.   while (i < Game.CharacterCount)
  24.   {
  25.     ViewFrame *vf = Game.GetViewFrame(character[i].View,character[i].Loop, character[i].Frame);
  26.     vf.Graphic = charSprites[i].Graphic; //set vf to sprite to remind the engine that the sprite has changed (bug?)
  27.     i++;
  28.   }
  29. }
  30.  

and the ray cast function

Code: Adventure Game Studio
  1.  
  2. void raycast(int light, float a)
  3. {
  4.   int xx, yy;
  5.   a = Maths.DegreesToRadians(a);
  6.   float d = 0.0; // distance from light
  7.   int str = 100; // light strength. Linear falloff, will do more believable falloff later.
  8.  
  9.   while (d < 100.0 && str > 0)
  10.   {
  11.     xx = FloatToInt(Maths.Sin(a) * d) + lights[light].X;
  12.     yy = FloatToInt(Maths.Cos(a) * d) + lights[light].Y;
  13.    
  14.     if (xx < 0 || xx > 320 || yy < 0 || yy > 200) str = 0;
  15.     else if (Character.GetAtScreenXY(xx, yy) != null)  // hit character
  16.     {
  17.       Character *c = Character.GetAtScreenXY(xx, yy);
  18.       DrawingSurface *cds = charSprites[c.ID].GetDrawingSurface();
  19.       int x = xx - (c.x - (charSprites[c.ID].Width / 2));
  20.       int y = yy - (c.y - charSprites[c.ID].Height);
  21.      
  22.       int col = GetRFromColor(cds.GetPixel(x, y));
  23.       col += str / 4;
  24.       if (col > 255) col = 255;
  25.       if (col < 0) col = 0;
  26.      
  27.       cds.DrawingColor = Game.GetColorFromRGB(col, col, col);
  28.       cds.DrawPixel(x, y);
  29.       cds.Release();
  30.       str -= 50; // reduce strength from character hit to simulate rimlight
  31.     }
  32.     d += 1.0; // advance distance
  33.     str --; // linear falloff
  34.   }
  35.  
  36. }
  37.  
  38.  
« Last Edit: 31 May 2012, 19:17 by Calin Leafshade »

Kweepa

  • Mutated Guano Deviser
    • Best Innovation Award Winner 2009, for his modules and plugins
    • Kweepa worked on one or more games that won an AGS Award!
    •  
    • Kweepa worked on one or more games that was nominated for an AGS Award!
Re: Raytracing and rimlight optimisation.
« Reply #1 on: 31 May 2012, 21:57 »
First off, looks awesome!

I would try doing it per character that overlaps the light.
First, draw the character sprite into a new sprite with a purple background, so you can pick the transparent parts.
Determine the visible part of the character box (V).
Then find the angle range that V spans - this could be 360 degrees in the worst case.
When casting the ray, determine the start and end of the line that overlaps V.
Do your raycast as before, but you don't need to get and release the drawing surface in the inner loop since you're doing it per character.
Optimize that inner loop a bit: don't need to check if (col < 0), don't call GetRFromColor (inline the code), might be faster to pull out lights[light].X/Y, Maths.Sin/Cos(a), c.x - charSprites[c.ID].Width/2 etc into loop invariant constants.

Code: Adventure Game Studio
  1.   float sa = Maths.Sin(a);
  2.   float ca = Maths.Cos(a);
  3.  
  4.   int lx = lights[light].X;
  5.   int ly = lights[light].Y;
  6.  
  7.   int cx = c.x - charSprites[c.ID].Width/2;
  8.   int cy = c.y - charSprites[c.ID].Height;
  9.  
  10.   int lcx = lx - cx;
  11.   int lcy = ly - cy;
  12.  
  13.   int x, y, col;
  14.  
  15.   // these are calculated from the box intersection
  16.   d = startD;
  17.   str = startStr;
  18.   while (d < endD && str > 0)
  19.   {
  20.     x = lcx + FloatToInt(sa * d);
  21.     y = lcy + FloatToInt(ca * d);
  22.  
  23.     if (charMaskSurf.GetPixel(x, y) != PURPLE)
  24.     {
  25.       col = cds.GetPixel(x, y) & 31; // or whatever GetRFromColor did
  26.       col += str / 4;
  27.       if (col > 255) col = 255;
  28.          
  29.       cds.DrawingColor = Game.GetColorFromRGB(col, col, col);
  30.       cds.DrawPixel(x, y);
  31.       str -= 50; // reduce strength from character hit to simulate rimlight
  32.     }
  33.     d += 1.0; // advance distance
  34.     str --; // linear falloff
  35.   }
  36.  

[EDIT] Rolled up lx and cx into loop invariant lcx. Also pulled variable declarations out of inner loop (might save a few cycles).
« Last Edit: 01 Jun 2012, 04:48 by Kweepa »
Still waiting for Purity of the Surf II

Kweepa

  • Mutated Guano Deviser
    • Best Innovation Award Winner 2009, for his modules and plugins
    • Kweepa worked on one or more games that won an AGS Award!
    •  
    • Kweepa worked on one or more games that was nominated for an AGS Award!
Re: Raytracing and rimlight optimisation.
« Reply #2 on: 01 Jun 2012, 00:37 »
Here's the ray/box clipping code. Untested. Uncompiled.

Code: Adventure Game Studio
  1.   float lx = IntToFloat(lights[light].X);
  2.   float ly = IntToFloat(lights[light].Y);
  3.  
  4.   float bx1 = IntToFloat(c.x - charSprites[c.ID].Width/2);
  5.   float bx2 = IntToFloat(bx1 + charSprites[c.ID].Width);
  6.   float by1 = IntToFloat(c.y - charSprites[c.ID].Height);
  7.   float by2 = IntToFloat(c.y);
  8.  
  9.   // clip character box to light bounding box and screen
  10.   if (bx1 < lx - lr) bx1 = lx - lr;
  11.   if (bx2 > lx + lr) bx2 = lx + lr;
  12.   if (bx1 < 0.0) bx1 = 0.0;
  13.   if (bx2 > 319.0) bx2 = 319.0;
  14.   if (bx1 >= bx2) return;
  15.   if (by1 < ly - lr) by1 = ly - lr;
  16.   if (by2 > ly + lr) by2 = ly + lr;
  17.   if (by1 < 0.0) by1 = 0.0;
  18.   if (by2 > 199.0) by2 = 199.0;
  19.   if (by1 >= by2) return;
  20.  
  21.   float u = 0.5; // to remove need for parallel checks
  22.   float degStep = 1.0;
  23.   while (u < 360.0)
  24.   {
  25.     float a = Maths.DegreesToRadians(u);
  26.     u += degStep;
  27.     float dx = Maths.Sin(a);
  28.     float dy = Maths.Cos(a);
  29.    
  30.     float startD = 0.0;
  31.     float endD = lr;
  32.     float t1 = (bx1 - lx)/dx;
  33.     float t2 = (bx2 - lx)/dx;
  34.     // t1 is near intersection, t2 is far
  35.     if (t1 > t2)
  36.     {
  37.       // swap
  38.       float t3 = t2;
  39.       t2 = t1;
  40.       t1 = t3;
  41.     }
  42.     // slab intersection
  43.     if (t1 > startD) startD = t1;
  44.     if (t2 < endD) endD = t2;
  45.    
  46.     // intersection on x
  47.     if (startD < endD)
  48.     {
  49.       t1 = (by1 - ly)/dy;
  50.       t2 = (by2 - ly)/dy;
  51.       // t1 is near intersection, t2 is far
  52.       if (t1 > t2)
  53.       {
  54.         // swap
  55.         float t3 = t2;
  56.         t2 = t1;
  57.         t1 = t3;
  58.       }
  59.       if (t1 > startD) startD = t1;
  60.       if (t2 < endD) endD = t2;
  61.    
  62.       // intersection on y
  63.       if (startD < endD)
  64.       {
  65.         raycast(c, light, startD, endD);
  66.       }
  67.     }
  68.   }
  69.  
Still waiting for Purity of the Surf II

Calin Leafshade

  • Long live King Cat!
    • I can help with making music
    • I can help with voice acting
    • Calin Leafshade worked on one or more games that won an AGS Award!
    •  
    • Calin Leafshade worked on one or more games that was nominated for an AGS Award!
Re: Raytracing and rimlight optimisation.
« Reply #3 on: 01 Jun 2012, 04:35 »
Thanks kweepa!

One question. What is 'lr' its referenced but never defined anywhere.

EDIT: Ah nevermind, lr = Light Radius
« Last Edit: 01 Jun 2012, 04:43 by Calin Leafshade »

Kweepa

  • Mutated Guano Deviser
    • Best Innovation Award Winner 2009, for his modules and plugins
    • Kweepa worked on one or more games that won an AGS Award!
    •  
    • Kweepa worked on one or more games that was nominated for an AGS Award!
Re: Raytracing and rimlight optimisation.
« Reply #4 on: 01 Jun 2012, 04:38 »
That's just the light radius. (100 in your code.)
Still waiting for Purity of the Surf II

abstauber

  • Cavefish
  • Mittens Knight
  • still mowing the lawn
    • abstauber worked on one or more games that won an AGS Award!
    •  
    • abstauber worked on one or more games that was nominated for an AGS Award!
Re: Raytracing and rimlight optimisation.
« Reply #5 on: 01 Jun 2012, 10:17 »
Awesome idea! I hope to see it implemented soon .

* abstauber is dying to get to know for which game this might be

Calin Leafshade

  • Long live King Cat!
    • I can help with making music
    • I can help with voice acting
    • Calin Leafshade worked on one or more games that won an AGS Award!
    •  
    • Calin Leafshade worked on one or more games that was nominated for an AGS Award!
Re: Raytracing and rimlight optimisation.
« Reply #6 on: 01 Jun 2012, 14:42 »
Well after making some changes it seems much much better, thanks kweepa

Now i need to deal with the colour, implement HSL and cache the viewframes properly.

Re: Raytracing and rimlight optimisation.
« Reply #7 on: 10 Jun 2012, 20:40 »
Looks pretty awesome!

Calin Leafshade

  • Long live King Cat!
    • I can help with making music
    • I can help with voice acting
    • Calin Leafshade worked on one or more games that won an AGS Award!
    •  
    • Calin Leafshade worked on one or more games that was nominated for an AGS Award!
Re: Raytracing and rimlight optimisation.
« Reply #8 on: 11 Jun 2012, 10:44 »
As an update, it doesnt actually look like this is possible with a proper moving, animating character.

The problem is that the engine updates the walking and viewframes *after* running the scripts (which is ludicrous tbh). So when the VF changes and the player moves, the script will always be one frame behind causing the whole thing to stutter.

Sorry guys.

Re: Raytracing and rimlight optimisation.
« Reply #9 on: 11 Jun 2012, 14:14 »
When does the stutter occur? Is it when the frames change? If so, would it be possible to draw the effect to the current frame and the next one each loop? Or does it stutter on position?

Calin Leafshade

  • Long live King Cat!
    • I can help with making music
    • I can help with voice acting
    • Calin Leafshade worked on one or more games that won an AGS Award!
    •  
    • Calin Leafshade worked on one or more games that was nominated for an AGS Award!
Re: Raytracing and rimlight optimisation.
« Reply #10 on: 11 Jun 2012, 14:48 »
The problem is that i cant really draw directly to the frame without quite a lot of complications. So i need to get the current frame and overlay it. But i cant find a good way getting the current frame because i need to anticipate a frame change which doesnt seem to be possible when you factor in loop changes and stuff.

If i just get the current frame using char.frame then the character will moonwalk because the movement is not tied to the animation anymore.

Re: Raytracing and rimlight optimisation.
« Reply #11 on: 11 Jun 2012, 19:08 »
It definitely is a terrible design to have the viewframe change after you run through your scripts and before drawing. I've had to deal with this as well and it's not fun.

Monsieur OUXX

  • Mittens Vassal
  • Cavefish
  • Mittens Half Initiate
    • I can help with proof reading
    • I can help with translating
    • I can help with voice acting
    • Monsieur OUXX worked on one or more games that won an AGS Award!
    •  
    • Monsieur OUXX worked on one or more games that was nominated for an AGS Award!
Re: Raytracing and rimlight optimisation.
« Reply #12 on: 12 Jun 2012, 16:11 »
I've always thought of a similar design to implement anti-aliased characters: first, computing their outline, then omit to draw some of the outline's pixels, and finally draw the missing pixels with transparency.
Your idea is very interesting, and very unexpected.

PS: I think your demo would be super impressive if you applied the effect to the cars and to the metals pillars as well :-)
 

Re: Raytracing and rimlight optimisation.
« Reply #13 on: 12 Jun 2012, 17:44 »
I've replicated your effect (admittedly by standing on the shoulders of giants) to get a grasp of the problem. And grasp it I did...
How fast did you get it to run before you abandoned the idea? As far as I can see you would have to calculate at least four other frames in addition to the one currently displayed to get it skip free. Does that even seem feasible?

Yeppoh

  • Murphy's Ginea Pig
    • I can help with animation
    • I can help with backgrounds
    • I can help with characters
    • I can help with scripting
    • I can help with story design
    • Yeppoh worked on one or more games that was nominated for an AGS Award!
Re: Raytracing and rimlight optimisation.
« Reply #14 on: 13 Jun 2012, 01:13 »
I can enlighten you (haha! Get it?....... *cough*) about the mechanics behind that 1 loop frame offset problem.

As already said the script are run before the screen is rendered. Additionally, all values are updated before the rendering, but after the scripts are run. Which means functions that run before the update are working with one frame old values.
Because in the sequence of events in the main loop, the repeatedly_execute_always and repeatedly_execute functions are run before the values are updated just in case the values were changed when those function are run.
There's a way to correct this. By making an update before the functions are run and another after for a double check.
I don't know if it will affect the frame rate, because it means going through huge arrays twice with the current engine architecture.

I have to test that, because I ran into the same problem, but resolved it by using a 0.5 frame offset hack; which only works with prerendered sprites though.

EDIT: Holy my holy! It works, but it runs twice its framerate. Which actually makes kind of sense. Needs more testing....
« Last Edit: 13 Jun 2012, 01:36 by Nefasto »

Re: Raytracing and rimlight optimisation.
« Reply #15 on: 14 Jun 2012, 00:06 »
My code is slow and amateurish as of yet, but...
I set character to be transparent and assigned the rendered graphic to an object that follows it exactly. That got rid of the blinking at least. The actual character is of course one game loop ahead of the rendered image, but I don't think that will be noticeable at walking speeds(?).

Calin Leafshade

  • Long live King Cat!
    • I can help with making music
    • I can help with voice acting
    • Calin Leafshade worked on one or more games that won an AGS Award!
    •  
    • Calin Leafshade worked on one or more games that was nominated for an AGS Award!
Re: Raytracing and rimlight optimisation.
« Reply #16 on: 14 Jun 2012, 02:34 »
but I don't think that will be noticeable at walking speeds(?).

Yes, it will. The problem is that to avoid sliding a character has to move on the *exact* loop where the frame changes. If its before or after then it will be very obvious and in scrolling rooms it will be even worse.

Re: Raytracing and rimlight optimisation.
« Reply #17 on: 14 Jun 2012, 05:28 »
As far as I can see there is no evidence of moonwalking. And there shouldn't be any either since the object follows the character frame and position exactly, except one game loop later. I can see the problem with scrolling but I haven't gotten around to testing that properly yet.

Edit: Scrolling seems fine as long as the viewport is following the object and not the character.
« Last Edit: 14 Jun 2012, 20:16 by Yoke 2.0 »

Re: Raytracing and rimlight optimisation.
« Reply #18 on: 16 Jun 2012, 02:30 »
This is what I've got so far: https://dl.dropbox.com/u/2642029/rimlight.zip
Please ignore all the bugs and such. Still I think it does all the important bits?