Jump to content
  • Advertisement
  • Remove ads and support GameDev.net for only $3. Learn more: The New GDNet+: No Ads!

  • 08/21/18 03:56 AM

    A Brief Introduction to Lerp

    General and Gameplay Programming

    mattdesl

    Linear interpolation (sometimes called 'lerp' or 'mix') is a really handy function for creative coding, game development and generative art.

    The function interpolates within the range [start..end] based on a 't' parameter, where 't' is typically within a [0..1] range.

    carbon (24).png

     

    For example, divide 'loop time' by 'loop duration' and you get a 't' value between 0.0 and 1.0.

    Now you can map this 't' value to a new range, such as `lerp(20, 50, t)` to gradually increase a circle's radius, or `lerp(20, 10, t)` to gradually decrease its line thickness.

    2018.08.19-22.40.29.gif

     

    Another example: you can use linear interpolation to smoothly animate from one coordinate to another. Define a start point (x1, y1) and end point (x2, y2), then interpolate the 'x' and 'y' dimensions separately to find the computed point in between.

    2018.08.19-22.41.19.gif

     

    Or use linear interpolation to spring toward a moving target. Each frame, interpolate from the current value to the target value with a small 't' parameter, such as 0.05.

    It's like saying: walk 5% toward the target each frame.

    2018.08.19-22.40.53.gif

     

    A more advanced example, but built on the same concept, is interpolating from one color (red) to another (blue).

    To do this, we interpolate the (R, G, B) or (H, S, L) channels of the color individually, just like we would with a 2D or 3D coordinate.

    2018.08.19-22.39.52.gif

     

    Another quick example is to choose a random point along a line segment.

    There are lots of ways to use linear interpolation, and lots more types of interpolation (cubic, bilinear, etc). These concepts also lead nicely into areas like: curves, splines and parametric equations.

    carbon (25).png

     

    Source code for each of these examples is available here: https://gist.github.com/mattdesl/3675c85a72075557dbb6b9e3e04a53d9

     

    About the author:
    Matt DesLauriers is a creative coder and generative artist based in London. He combines code and emergent systems to make art for the web, print media, and physical installations.

     

    Note:
    This brief introduction to lerp was originally published as a Twitter thread and is republished here with the kind permission of the original author.

    [Wayback Machine Archive]



      Report Article


    User Feedback


    Very cool article! :) I use linear interpolation to smooth out visual movement, it works very nicely with variable render rates. It's also nice for visual effects like shown above. :) 

    Thanks for sharing!

    Share this comment


    Link to comment
    Share on other sites

    Nice article! I loved the visual examples.

    I can't say how many times lerp has been the tool of choice to achieve zillions of nice looking effects using shaders, plus is the basis of rasterization!

    Keep the good work :)

    Share this comment


    Link to comment
    Share on other sites

    Note that your "springing toward" example (lerping a fraction of the remaining distance each time) is highly frame-rate dependent.  So if your game isn't frame-rate locked (i.e. web-games running on machines with different monitor refresh rates, or even a locked 60 fps game running on a machine too slow to support it) different people may see different behaviors.  The spaceship rotation in George Prosser's DRILL_BIT, for instance, is much harder to use on a slow machine.

    And the way you're doing it, scaling by the deltaTime, will only partly correct for that.  For instance, if your framerate is twice as fast (deltaTime is half the length) then you actually need the square root of the rate (you lerp twice in the same time, essentially multiplying by the factor twice, i.e. squaring it).  In the general case you need Math.pow:

    // Return a lerp factor for the given frame time which will result in
    // the value getting convergenceFraction of the way to the target in
    // smoothTime time units.  I usually just use 0.9 or 0.95 for the fraction
    // and vary the smoothTime to get the effect I want.
    function smoothOver(dt, smoothTime, convergenceFraction) {
    	return 1 - Math.pow(1 - convergenceFraction, dt / smoothTime)
    }

    For further adventures in non-linear interpolation things, Squirrel Eiserloh's Fast and Funky 1D Non-linear Transformations GDC talk is well worth a watch.  Although note that with his later (curved) functions, he only mumbles once that he's "normalizing" them (meaning scaling them up so they are exactly one unit tall).  Without knowing that, if you try to use some of the formulas he gives as written, you'll end up with something very flat that does almost nothing.  But he gives a good intuitive introduction to how to think about constructing some of these things.

    Share this comment


    Link to comment
    Share on other sites


    Create an account or sign in to comment

    You need to be a member in order to leave a comment

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

  • Advertisement
  • Advertisement
  • Latest Featured Articles

  • Featured Blogs

  • Popular Now

  • Similar Content

    • By Adeilton Alves
      Hello everyone, I'm new here and sorry if this isn't the right place to ask but i asked in a few forums around the internet and no one yet help with it.. I'm have been trying to mod this game for years, but I still stuck with the raw files from RACJIN games, 
      Raw Files [ Mod edit: Removed ]
      I would like to identify the compression algorithm used to compress these files so that they can be decompressed and analyzed.

      Game : Naruto Uzumaki Chronicles 2... A.K.A Naruto Konoha Spirits in Japan.
    • By Waaayoff
      I'm looking for an algorithm that I can use to remove vertices that are close to each other within a margin of error in a triangular mesh. Pretty much similar to Blender's "Remove Doubles" feature, if anyone is familiar with it.
      I think the issue isn't just removing the doubles, but also how would I handle the face indices once I remove "duplicate" vertices?
    • By iGrfx
      I've learned that the triangle clipping in the rasterization process usually using Sutherland–Hodgman algorithm. I also found an algorithm called "Guard-band". I'm writing a software raster so I want to know what technical the GPU use, I want to implement it for study. Thanks!
      updated: what's the more proper triangulate algorithm?
    • By Vilem Otte
      Welcome to the first part of multiple effect articles about soft shadows. In recent days I've been working on area light support in my own game engine, which is critical for one of the game concepts I'd like to eventually do (if time will allow me to do so). For each area light, it is crucial to have proper soft shadows with proper penumbra. For motivation, let's have the following screenshot with 3 area lights with various sizes:

      Fig. 01 - PCSS variant that allows for perfectly smooth, large-area light shadows
       
      Let's start the article by comparison of the following 2 screenshots - one with shadows and one without:
       
      Fig. 02 - Scene from default viewpoint lit with light without any shadows (left) and with shadows (right)
       
      This is the scene we're going to work with, and for the sake of simplicity, all of the comparison screenshots will be from this exact same viewpoint with 2 different scene configurations. Let's start with the definition of how shadows are created. Given a scene and light which we're viewing. Shadow umbra will be present at each position where there is no direct visibility between given position and any existing point on the light. Shadow penumbra will be present at each position where there is visibility of any point on the light, yet not all of them. No shadow is everywhere where there is full direct visibility between each point on the light and position.
      Most of the games tend to simplify, instead of defining a light as area or volume, it gets defined as an infinitely small point, this gives us few advantages:
      For single point, it is possible to define visibility in a binary way - either in shadow or not in shadow From single point, a projection of the scene can be easily constructed in such way, that definition of shadow becomes trivial (either position is occluded by other objects in the scene from lights point of view, or it isn't) From here, one can follow into the idea of shadow mapping - which is a basic technique for all others used here.
       
      Standard Shadow Mapping
      Trivial, yet should be mentioned here.
      inline float ShadowMap(Texture2D<float2> shadowMap, SamplerState shadowSamplerState, float3 coord) { return shadowMap.SampleLevel(shadowSamplerState, coord.xy, 0.0f).x < coord.z ? 0.0f : 1.0f; } Fig. 03 - code snippet for standard shadow mapping, where depth map (stored 'distance' from lights point of view) is compared against calculated 'distance' between point we're computing right now and given light position. Word 'distance' may either mean actual distance, or more likely just value on z-axis for light point of view basis.
       
      Which is well known to everyone here, giving us basic results, that we all well know, like:

      Fig. 04 - Standard Shadow Mapping
       
      This can be simply explained with the following image:

      Fig. 05 - Each rendered pixel calculates whether its 'depth' from light point is greater than what is written in 'depth' map from light point (represented as yellow dot), white lines represent computation for each pixel.
       
      Percentage-Close-Filtering (PCF)
      To make shadow more visually appealing, adding soft-edge is a must. This is done by simply performing NxN tests with offsets. For the sake of improved visual quality I've used shadow mapping with bilinear filter (which requires resolving 4 samples), along with 5x5 PCF filtering:
       
      Fig. 06 - Percentage close filtering (PCF) results in nice soft-edged shadows, sadly the shadow is uniformly soft everywhere
       
      Clearly, none of the above techniques does any penumbra/umbra calculation, and therefore they're not really useful for area lights. For the sake of completeness, I'm adding basic PCF source code (for the sake of optimization, feel free to improve for your uses):
      inline float ShadowMapPCF(Texture2D<float2> tex, SamplerState state, float3 projCoord, float resolution, float pixelSize, int filterSize) { float shadow = 0.0f; float2 grad = frac(projCoord.xy * resolution + 0.5f); for (int i = -filterSize; i <= filterSize; i++) { for (int j = -filterSize; j <= filterSize; j++) { float4 tmp = tex.Gather(state, projCoord.xy + float2(i, j) * float2(pixelSize, pixelSize)); tmp.x = tmp.x < projCoord.z ? 0.0f : 1.0f; tmp.y = tmp.y < projCoord.z ? 0.0f : 1.0f; tmp.z = tmp.z < projCoord.z ? 0.0f : 1.0f; tmp.w = tmp.w < projCoord.z ? 0.0f : 1.0f; shadow += lerp(lerp(tmp.w, tmp.z, grad.x), lerp(tmp.x, tmp.y, grad.x), grad.y); } } return shadow / (float)((2 * filterSize + 1) * (2 * filterSize + 1)); } Fig. 07 - PCF filtering source code
       
      Representing this with image:

      Fig. 08 - Image representing PCF, specifically a pixel with straight line and star in the end also calculates shadow in neighboring pixels (e.g. performing additional samples). The resulting shadow is then weighted sum of the results of all the samples for a given pixel.
       
      While the idea is quite basic, it is clear that using larger kernels would end up in slow computation. There are ways how to perform separable filtering of shadow maps using different approach to resolve where the shadow is (Variance Shadow Mapping for example). They do introduce additional problems though.
       
      Percentage-Closer Soft Shadows
      To understand problem in both previous techniques let's replace point light with area light in our sketch image.

      Fig. 09 - Using Area light introduces penumbra and umbra. The size of penumbra is dependent on multiple factors - distance between receiver and light, distance between blocker and light and light size (shape).
       
      To calculate plausible shadows like in the schematic image, we need to calculate distance between receiver and blocker, and distance between receiver and light. PCSS is a 2-pass algorithm that does calculate average blocker distance as the first step - using this value to calculate penumbra size, and then performing some kind of filtering (often PCF, or jittered-PCF for example). In short, PCSS computation will look similar to this:
      float ShadowMapPCSS(...) { float averageBlockerDistance = PCSS_BlockerDistance(...); // If there isn't any average blocker distance - it means that there is no blocker at all if (averageBlockerDistance < 1.0) { return 1.0f; } else { float penumbraSize = estimatePenumbraSize(averageBlockerDistance, ...) float shadow = ShadowPCF(..., penumbraSize); return shadow; } } Fig. 10 - Pseudo-code of PCSS shadow mapping
       
      The first problem is to determine correct average blocker calculation - and as we want to limit search size for average blocker, we simply pass in additional parameter that determines search size. Actual average blocker is calculated by searching shadow map with depth value smaller than of receiver. In my case I used the following estimation of blocker distance:
      // Input parameters are: // tex - Input shadow depth map // state - Sampler state for shadow depth map // projCoord - holds projection UV coordinates, and depth for receiver (~further compared against shadow depth map) // searchUV - input size for blocker search // rotationTrig - input parameter for random rotation of kernel samples inline float2 PCSS_BlockerDistance(Texture2D<float2> tex, SamplerState state, float3 projCoord, float searchUV, float2 rotationTrig) { // Perform N samples with pre-defined offset and random rotation, scale by input search size int blockers = 0; float avgBlocker = 0.0f; for (int i = 0; i < (int)PCSS_SampleCount; i++) { // Calculate sample offset (technically anything can be used here - standard NxN kernel, random samples with scale, etc.) float2 offset = PCSS_Samples[i] * searchUV; offset = PCSS_Rotate(offset, rotationTrig); // Compare given sample depth with receiver depth, if it puts receiver into shadow, this sample is a blocker float z = tex.SampleLevel(state, projCoord.xy + offset, 0.0f).x; if (z < projCoord.z) { blockers++; avgBlockerDistance += z; } } // Calculate average blocker depth avgBlocker /= blockers; // To solve cases where there are no blockers - we output 2 values - average blocker depth and no. of blockers return float2(avgBlocker, (float)blockers); } Fig. 11 - Average blocker estimation for PCSS shadow mapping
       
      For penumbra size calculation - first - we assume that blocker and receiver are plannar and parallel. This makes actual penumbra size is then based on similar triangles. Determined as:
      penmubraSize = lightSize * (receiverDepth - averageBlockerDepth) / averageBlockerDepth This size is then used as input kernel size for PCF (or similar) filter. In my case I again used rotated kernel samples. Note.: Depending on the samples positioning one can achieve different area light shapes. The result gives quite correct shadows, with the downside of requiring a lot of processing power to do noise-less shadows (a lot of samples) and large kernel sizes (which also requires large blocker search size). Generally this is very good technique for small to mid-sized area lights, yet large-sized area lights will cause problems.
       
      Fig. 12 - PCSS shadow mapping in practice
       
      As currently the article is quite large and describing 2 other techniques which I allow in my current game engine build (first of them is a variant of PCSS that utilizes mip maps and allows for slightly larger light size without impacting the performance that much, and second of them is sort of back-projection technique), I will leave those two for another article which may eventually come out. Anyways allow me to at least show a short video of the first technique in action:
       
      Note: This article was originally published as a blog entry right here at GameDev.net, and has been reproduced here as a featured article with the kind permission of the author.
      You might also be interested in our recently featured article on Contact-hardening Soft Shadows Made Fast.
    • By lilbump
      Hi guys i'm new here, i really hope my question won't sound utterly stupid..
      I'd like to know whether it's better to use a PRNG or a regular RNG, if you are trying to program your own video slot machine. Actually i don't even have clearly understood the difference between the two =D
      2nd question is: which developer i should rely on? I'm following this guide, they talk about RNG but not which one or where to find it.
      Thank you in advance :)
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!