Raytracing and rimlight optimisation.

Started by Calin Leafshade, Thu 31/05/2012 19:00:55

Previous topic - Next topic

Calin Leafshade

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: AGS

void Light::Draw()
{
  int i;
  while (i < Game.CharacterCount)
  {
    if (character[i].Room == player.Room)
    {
      
      ViewFrame *vf = Game.GetViewFrame(character[i].View,character[i].Loop, character[i].Frame);
      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.
      vf.Graphic = charSprites[i].Graphic;
    }
    i++;
  }
  float u = 0.0;
  while (u < 360.0)
  {
    raycast(this.ID, u);   
    u += degStep;
  }
  ds.Release();
  
  while (i < Game.CharacterCount)
  {
    ViewFrame *vf = Game.GetViewFrame(character[i].View,character[i].Loop, character[i].Frame); 
    vf.Graphic = charSprites[i].Graphic; //set vf to sprite to remind the engine that the sprite has changed (bug?)
    i++;
  }
}


and the ray cast function

Code: AGS


void raycast(int light, float a) 
{
  int xx, yy;
  a = Maths.DegreesToRadians(a);
  float d = 0.0; // distance from light
  int str = 100; // light strength. Linear falloff, will do more believable falloff later.
  
  while (d < 100.0 && str > 0)
  {
    xx = FloatToInt(Maths.Sin(a) * d) + lights[light].X;
    yy = FloatToInt(Maths.Cos(a) * d) + lights[light].Y;
    
    if (xx < 0 || xx > 320 || yy < 0 || yy > 200) str = 0;
    else if (Character.GetAtScreenXY(xx, yy) != null)  // hit character
    {
      Character *c = Character.GetAtScreenXY(xx, yy);
      DrawingSurface *cds = charSprites[c.ID].GetDrawingSurface();
      int x = xx - (c.x - (charSprites[c.ID].Width / 2));
      int y = yy - (c.y - charSprites[c.ID].Height);
      
      int col = GetRFromColor(cds.GetPixel(x, y));
      col += str / 4;
      if (col > 255) col = 255;
      if (col < 0) col = 0;
      
      cds.DrawingColor = Game.GetColorFromRGB(col, col, col);
      cds.DrawPixel(x, y);
      cds.Release();
      str -= 50; // reduce strength from character hit to simulate rimlight
    }
    d += 1.0; // advance distance
    str --; // linear falloff
  }
  
}


Kweepa

#1
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: AGS

  float sa = Maths.Sin(a);
  float ca = Maths.Cos(a);
  
  int lx = lights[light].X;
  int ly = lights[light].Y;
  
  int cx = c.x - charSprites[c.ID].Width/2;
  int cy = c.y - charSprites[c.ID].Height;

  int lcx = lx - cx;
  int lcy = ly - cy;

  int x, y, col;
 
  // these are calculated from the box intersection
  d = startD;
  str = startStr;
  while (d < endD && str > 0)
  {
    x = lcx + FloatToInt(sa * d);
    y = lcy + FloatToInt(ca * d);
 
    if (charMaskSurf.GetPixel(x, y) != PURPLE)
    {
      col = cds.GetPixel(x, y) & 31; // or whatever GetRFromColor did
      col += str / 4;
      if (col > 255) col = 255;
	 
      cds.DrawingColor = Game.GetColorFromRGB(col, col, col);
      cds.DrawPixel(x, y);
      str -= 50; // reduce strength from character hit to simulate rimlight
    }
    d += 1.0; // advance distance
    str --; // linear falloff
  }


[EDIT] Rolled up lx and cx into loop invariant lcx. Also pulled variable declarations out of inner loop (might save a few cycles).
Still waiting for Purity of the Surf II

Kweepa

Here's the ray/box clipping code. Untested. Uncompiled.

Code: AGS

  float lx = IntToFloat(lights[light].X);
  float ly = IntToFloat(lights[light].Y);

  float bx1 = IntToFloat(c.x - charSprites[c.ID].Width/2);
  float bx2 = IntToFloat(bx1 + charSprites[c.ID].Width);
  float by1 = IntToFloat(c.y - charSprites[c.ID].Height);
  float by2 = IntToFloat(c.y);

  // clip character box to light bounding box and screen
  if (bx1 < lx - lr) bx1 = lx - lr;
  if (bx2 > lx + lr) bx2 = lx + lr;
  if (bx1 < 0.0) bx1 = 0.0;
  if (bx2 > 319.0) bx2 = 319.0;
  if (bx1 >= bx2) return;
  if (by1 < ly - lr) by1 = ly - lr;
  if (by2 > ly + lr) by2 = ly + lr;
  if (by1 < 0.0) by1 = 0.0;
  if (by2 > 199.0) by2 = 199.0;
  if (by1 >= by2) return;

  float u = 0.5; // to remove need for parallel checks
  float degStep = 1.0;
  while (u < 360.0)
  {
    float a = Maths.DegreesToRadians(u);
    u += degStep;
    float dx = Maths.Sin(a);
    float dy = Maths.Cos(a);
    
    float startD = 0.0;
    float endD = lr;
    float t1 = (bx1 - lx)/dx;
    float t2 = (bx2 - lx)/dx;
    // t1 is near intersection, t2 is far
    if (t1 > t2)
    {
      // swap
      float t3 = t2;
      t2 = t1;
      t1 = t3;
    }
    // slab intersection
    if (t1 > startD) startD = t1;
    if (t2 < endD) endD = t2;
    
    // intersection on x
    if (startD < endD)
    {
      t1 = (by1 - ly)/dy;
      t2 = (by2 - ly)/dy;
      // t1 is near intersection, t2 is far
      if (t1 > t2)
      {
        // swap
        float t3 = t2;
        t2 = t1;
        t1 = t3;
      }
      if (t1 > startD) startD = t1;
      if (t2 < endD) endD = t2;
    
      // intersection on y
      if (startD < endD)
      {
        raycast(c, light, startD, endD);
      }
    }
  }
Still waiting for Purity of the Surf II

Calin Leafshade

#3
Thanks kweepa!

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

EDIT: Ah nevermind, lr = Light Radius

Kweepa

That's just the light radius. (100 in your code.)
Still waiting for Purity of the Surf II

abstauber

Awesome idea! I hope to see it implemented soon .

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

Calin Leafshade

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.


Calin Leafshade

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.

Yoke 2.0

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

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.

Ryan Timothy B

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

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 :-)
 

Yoke 2.0

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

#14
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....

Yoke 2.0

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

Quote from: Yoke 2.0 on Thu 14/06/2012 00:06:48
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.

Yoke 2.0

#17
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.

Yoke 2.0

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?

SMF spam blocked by CleanTalk