Animating and Compositing | Web Browser Engineering

Complex web application use animations when transitioning between states. These animations help users understand the change and improve visual polish by replacing sudden jumps with gradual changes. But to execute these animations smoothly, the browser must minimize time in each animation frame, using GPU acceleration to speed up visual effects and compositing to minimize redundant work.

JavaScript Animations

An animation is a sequence of still pictures shown in quick succession that create an illusion of movement to the human eye.Here movement should be construed broadly to encompass all of the kinds of visual changes humans are used to seeing and good at recognizing—not just movement from side to side, but growing, shrinking, rotating, fading, blurring, and sharpening. The rule is that an animation is not an arbitrary sequence of pictures; the sequence must feel continuous to a human mind trained by experience in the real world. Typical web page animations include changing an element’s color, fading it in or out, or resizing it. Browsers also use animations in response to user actions like scrolling, resizing, and pinch-zooming. Plus, some types of animated media (like videos) can be included in web pages.Video-like animations also include animated images and animated canvases. Since our browser doesn’t support images yet, this topic is beyond the scope of this chapter; video alone has its own fascinating complexities.

In this chapter we’ll focus on animations of web page elements. Let’s start by writing a simple animation using the requestAnimationFrame API implemented in Chapter 12. This method requests that some JavaScript code run on the next frame; to run repeatedly over many frames, we can just have that JavaScript code call requestAnimationFrame itself:

The animate function then makes some small change to the page to give the impression of continuous change.It returns true while it’s animating, and then stops. By changing what animate does we can change what animation occurs.

For example, we can fade an element in by smoothly transitioning its opacity value from 0.1 to 0.999.Real browsers apply certain optimizations when opacity is exactly 1, so real-world websites often start and end animations at 0.999 so that each frame is drawn the same way and the animation is smooth. Starting and ending animations at 0.999 is also a common trick used on websites that want to avoid visual popping of the content as it goes in and out of GPU-accelerated mode. I chose 0.999 because the visual difference from 1.0 is imperceptible. Doing this over 120 frames (about two seconds) means increasing the opacity by about 0.008 each frame.

This animation almost runs in our browser, except that we need to add support for changing an element’s style attribute from JavaScript. To do that, register a setter on the style attribute of Node in the JavaScript runtime:

Importantly, the style_set function sets the needs_render flag to make sure that the browser re-renders the web page with the new style parameter. With these changes, you should now be able to open and run this animation in your browser.

GPU acceleration

Try the fade animation in your browser, and you’ll probably notice that it’s not particularly smooth. And that shouldn’t be surprising; after all, last chapter had the following running times for our browser:

With 66ms per frame, our browser is barely doing fifteen frames per second; for smooth animations we want sixty! So we need to speed up raster and draw.

The best way to do that is to move raster and draw to the GPU. A GPU is essentially a chip in your computer that runs programs, much like your CPU but specialized toward running very simple programs with massive parallelism—it was developed to apply simple operations, in parallel, for every pixel on the screen. This makes GPUs faster for drawing simple shapes and much faster for applying visual effects.

At a high level, to raster and draw on the GPU our browser must:These steps vary a bit in the details by GPU architecture.

Luckily, SDL and Skia support all of these steps; it’s mostly a matter of passing them the right parameters. So let’s do that. Note that a real browser typically implements both CPU and GPU raster and draw, because in some cases CPU raster and draw can be faster than using the GPU, or it may be necessary to work around bugs.Any of the four steps can make GPU raster and draw slow. Large display lists take a while to upload. Complex display list commands take longer to compile. Raster can be slow if there are many surfaces, and draw can be slow if surfaces are deeply nested. On a CPU, the upload step and compile steps aren’t necessary, and more memory is available for raster and draw. Of course, many optimizations are available for both GPU and CPU, so choosing the best way to raster and draw a given page can be quite complex. In our browser, for simplicity, we’ll always use the GPU.

Now we’ll need to configure SDL to use OpenGL and and start/stop a GL context at the beginning/end of the program. For our purposes, just consider this API boilerplate:Starting a GL context is just OpenGL’s way of saying “set up the surface into which subsequent OpenGL commands will draw”. After creating one you can even execute OpenGL commands manually, without using Skia at all, to draw polygons or other objects on the screen.

That print statement shows the GPU vendor and renderer that the browser is using; this will help you verify that it’s actually using your GPU. I’m using a Chromebook to write this chapter, so for me it says:The virgl renderer stands for “virtual GL”, a way of hardware-accelerating the Linux subsystem of ChromeOS that works with the ChromeOS Linux sandbox. This is a bit slower than using the GPU directly, so you’ll probably see even faster raster and draw than I do.

Now we can configure Skia to draw directly to the screen. The incantation is:Weirdly, this code draws to the window without referencing gl_context or sdl_window directly. That’s because OpenGL is a strange API with a lot of hidden global state; the MakeGL Skia method implicitly binds to the existing GL context.

An extra advantage of using OpenGL is that we won’t need to copy data between Skia and SDL anymore. Instead we just flush the Skia surface (Skia surfaces draw lazily) and call SDL_GL_SwapWindow to activate the new framebuffer (because of OpenGL double-buffering):

Finally, our browser also creates Skia surfaces for the chrome_surface and tab_surface. We don’t want to draw these straight to the screen, so the incantation is a bit different:

Again, you should think of these changes mostly as boilerplate, since the details of GPU operation aren’t our focus here.Example detail: a different color space is required for GPU mode. Make sure to apply the same treatment to tab_surface (with different width and height arguments).

Thanks to SDL’s and Skia’s thorough support for GPU rendering, that should be all that’s necessary for our browser to raster and draw on the GPU. And as expected, speed is much improved:

That’s about three times faster, almost fast enough to hit sixty frames per second. (And on your computer, you’ll likely see even more speedup than I did, so for you it might already be fast enough in this example.) But if we want to go faster yet, we’ll need to find ways to reduce the total amount of work in raster and draw.

Compositing

So, how do we do less work in the raster and draw phase? The answer is a technique called compositing, which just means caching some rastered images on the GPU and reusing them during later frames.The term compositing means combining multiple images together into a final output. In the context of browsers, it typically means combining rastered images into the final on-screen image, but a similar technique is used in many operating systems to combine the contents of multiple windows. “Compositing” can also refer to multi-threaded rendering.

To explain compositing, we’ll need to think about our browser’s display list, and to do that it’s useful to print it out. Printing it is going to require similar code in every display command, so let’s give them all a new DisplayItem superclass. This also makes it easy to create default behavior that’s overridden for specific display commands. For example, we can make sure that every display command has a children field:

We’ll need that children field to use print_tree to print the display list.

Now each display command needs to be a subclass of DisplayItem; to do that, you need to name the superclass when the class is declared and also use some special syntax in the constructor:

Commands that already had a children field need to pass it to the __init__ call:

To print the display list in a useful form, let’s add a printable form to each display command. For example, for DrawRect you might print:

Some of our display commands have a flag to do nothing, like ClipRRect’s should_clip flag. It’s useful to explicitly indicate that:

In each case, rastering this display list means first raster the three words to a Skia surface created by saveLayer, and then copying that to the root surface while applying transparency. Crucially, the raster is identical in both frames; only the copy differs. This means we can speed it up with caching.

The idea is to first raster the three words to a separate surface (but this time owned by us, not Skia), which we’ll call a composited layer:

Now instead of drawing those three words, we can just copy over the composited layer with a DrawCompositedLayer command:

Importantly, on the next frame, the SaveLayer changes but the DrawTexts don’t, so on that frame all we need to do is rerun the SaveLayer:

In other words, the idea behind compositing is to split the display list into two pieces: a set of composited layers, which are rastered during the browser’s raster phase and then cached, and a draw display list, which is drawn during the browser’s draw phase and which uses the composited layers.

Compositing helps when different frames of an animation have the same composited layers, which can then be reused. That’s the case here, because the only difference between frames is the SaveLayer, which is in the draw display list.

How exactly to split up the display list is up to the browser. Typically, visual effects like opacity are very fast to execute on a GPU, but paint commands that draw shapes—in our browser, DrawText, DrawRect, DrawRRect, and DrawLine—can be slower.And there are usually a lot more of them to execute. Since it’s the visual effects that are typically animated, this means browsers usually leave animated visual effects in the draw display list and move everything else into composited layers. Of course, in a real browser, hardware capabilities, GPU memory, and application data all play into these decisions, but the basic idea of compositing is the same no matter what goes where.

Some animations can’t be composited because they affect more than just the display list. For example, imagine we animate the width of the div above, instead of animating its opacity. Here’s how it looks; click the buttons to animate.

Here, different frames have different layout trees, not just different display lists. That totally changes the coordinates for the DrawText calls, and we wouldn’t necessarily be able to reuse any composited layers. Such animations are called layout-inducing, and speeding them up requires different techniques.Because layout-inducing animations can’t easily make use of compositing, they’re usually not a good idea on the web. Not only are they slower, but they also cause page elements to jump around suddenly and don’t create that illusion of continuous movement. An exception is resizing the browser window with your mouse. That’s layout-inducing, but it’s very useful for the user to see the new layout as the window size changes. Modern browsers are fast enough to do this, but it used to be that they’d only redraw the screen every couple of frames, leaving a visual gutter between content and the edge of the window.

Compositing leaves

Let’s implementing compositing. We’ll need to traverse the display list, identify paint commands, and move them to composited layers. Then we’ll need to create the draw display list that combines these composited layers. To keep things simple, we’ll start by creating a composited layer for every paint command.

We’ll want an is_paint_command method on display items to identify paint commands. It’ll return False by default:

But for DrawLine, DrawRRect, DrawRect, and DrawText it’ll return True instead. For example, here’s DrawLine:

Next we need to group paint commands into layers. For now, let’s do the simplest possible thing and put each paint command into its own CompositedLayer:

Here, a CompositedLayer just stores a list of display items (and a surface that they’ll be drawn to).For now, it’s just one display item, but that will change pretty soon.

Now we need a draw display list that combines the composited layers. To build this we’ll walk up from each composited layer build a chain of all of the visual effects applied to it, with a DrawCompositedLayer at the bottom of the chain.

First, to make it easy to access those ancestor visual effects and compare them, let’s add parent pointers to our display list tree:

Next, we’ll need to clone each of the ancestors of the layer’s paint commands and injecting new children, so let’s add a new clone method to the visual effects classes. For SaveLayer, it’ll create a new SaveLayer with the same parameters but new children:

The other visual effect, ClipRRect, should do something similar. We won’t be cloning paint commands, since they’re all going to be inside a composited layer, so we don’t need to implement clone for them.

We can now build the draw display list. For each composited layer, create a DrawCompositedLayer command (which we’ll define in just a moment). Then, walk up the display list, wrapping that DrawCompositedLayer in each visual effect that applies to that composited layer:

Now that we’ve split the display list into composited layers and a draw display list, we need to update the rest of the browser to use them for raster and draw.

Let’s start with raster. In the raster step, the browser needs to walk the list of composited layers and raster every display command in the composited layer:

Inside raster, the composited layer needs to allocate a surface to raster itself into. To start, it’ll need to know how big a surface to allocate. That’s just the union of the bounding boxes of all of its paint commands. First add a rect field to display items:

Drawing commands then need to pass that argument to the superclass constructor. Here’s DrawText, for example:

These bounds can then be used to make a surface with the right size. Note that we’re creating a surface just big enough to store the items in this composited layer; this reduces how much GPU memory we need.

To raster the composited layer, draw all of its display items to this surface. The only tricky part is the need to offset by the top and left of the composited bounds, since the surface bounds don’t include that offset:

That’s all for the raster phase. For the draw phase, we’ll first need to implement the DrawCompositedLayer command. It takes a composited layer to draw:

Executing a DrawCompositedLayer is straightforward—just draw its surface into the parent surface, adjusting for the correct offset:

All that’s left is wiring these methods up; let’s rename raster_and_draw to composite_raster_and_draw to remind us that there’s now an additional composite step and add our two new methods. (And don’t forget to rename the corresponding dirty bit and call sites.)

So simple and elegant! Now, on every frame, we are simply splitting the display list into composited layers and the draw display list, and then running each of those it their own phase. We’re now half-way toward getting super-smooth animations. What remains is skipping the raster step if the display list didn’t change much between frames.

CSS transitions

The key to not re-rastering layers is to know which layers have changed, and which haven’t. Right now, we’re basically always assuming all layers have changed, but ideally we’d know exactly what’s changed between frames. Browsers have all sorts of complex methods to achieve this,Chromium, for example, tries to diff the old and new styles any time a style changes on the page. But this is tricky, because a change in style on one element could be inherited by a different element, so diffing will always be somewhat brittle and incomplete. but to keep things simple, let’s implement a CSS feature that’s perfect for compositing: CSS transitions.

CSS transitions take the requestAnimationFrame loop we used to implement animations and move it into the browser. The web page just needs to interpret the CSS transition property, which defines properties to animate and how long to animate them for. Here’s how to say opacity changes to a div should animate for two seconds:

Now, whenever the opacity property of a div changes for any reason—like from changing its style attribute—the browser smoothly interpolates between the old and new values for two seconds. Here is an example:

Visually, it looks more or less identicalIt’s not exactly the same, because our JavaScript code uses a linear interpolation (or easing function) between the old and new values. Real browsers use a non-linear default easing function for CSS transitions because it looks better. We’ll implement a linear easing function for our browser, so it will look identical to the JavaScript and subtly different from real browsers. to the JavaScript animation. But since the browser understands the animation, it can optimize how the animation is run. For example, since opacity only affects SaveLayer commands that end up in the draw display list, the browser knows that this animation does not require layout or raster, just paint and draw.

To implement CSS transitions, we’ll need to move JavaScript variables like current_frame and change_per_frame into some kind of animation object inside the browser. Since multiple elements can animate at a time, let’s store an animations dictionary on each node, keyed by the property being animated:For simplicity, this code leaves animations in the animations dictionary even when they’re done animating. Removing them would be necessary, however, for really long-running tabs where just looping over all the already-completed animations can take a while.

Much like in JavaScript, we’ll need an animate method that increments the frame count, computes the new value and returns it; this value will be placed in the style of an element.

We’ll create these animation objects every time a style value changes, which we can detect in style by diffing the old and new styles of each node:

This diff_styles function is going to look for all properties that are mentioned in the transition property and are different between the old and the new style. So first, we’re going to have to parse the transition value:Note that this returns a dictionary mapping property names to transition durations, measured in frames.

Now diff_style can loop through all of the properties mentioned in transition and see which ones changed. It returns a dictionary containing only the transitioning properties, and mapping each such property to its old value, new value, and duration (again in frames).Note also that this code has to deal with subtleties like the transition property being added or removed, or properties being removed instead of changing values.

Back inside style, we’re going to want to create a new animation object for each transitioning property. Let’s allow animating just opacity for now; we can expand this to more properties by writing new animation types.

The style function can animate any changed properties listed in ANIMATED_PROPERTIES:

Any time a property listed in a transition changes its value, we’ll create an animation and get ready to run it.Note that we need to call set_needs_render here to make sure that the animation will run on the next frame.

With the animations created, we now need to run them on every later frame. Basically, on every frame, iterate through all the active animations on the page and call animate on them. Since CSS transitions are similar to requestAnimationFrame animations, let’s run animations right after handling requestAnimationFrame callbacks:

Inside this loop we need to do two things. First, we must call the animation’s animate method and save the new value to the node’s style. Second, since that changes the web page, we need to set a dirty bit. Recall that render exits early if needs_render isn’t set, so that dirty bit is supposed to be set if there’s rendering work to do. When an animation is active, there is.We also need to schedule an animation frame for the next frame of the animation, but set_needs_render already does that for us.

However, it’s not as simple as just setting needs_render any time an animation is active. Setting needs_render means re-running style, which would notice that the animation changed a property value and start a new animation! During an animation, we want to run layout and paint, but we don’t want to run style:While a real browser definitely has an analog of the needs_layout and needs_paint flags, our fix for restarting animations doesn’t handle a bunch of edge cases. For example, if a different style property than the one being animated changes, the browser shouldn’t re-start the animation. Real browsers do things like storing multiple copies of the style—the computed style and the animated style—to solve issues like this.

To implement set_needs_layout, we’ve got to replace the single needs_render flag with three flags: needs_style, needs_layout, and needs_paint. In our implementation, setting a dirty bit earlier in the pipeline will end up causing everything after it to also run, so set_needs_render still just sets the needs_style flag:This is yet another difference from real browsers, which optimize some cases that just require style and paint, or other combinations.

Now we can write a set_needs_layout method that sets flags for the layout and paint phases, but not the style phase:

To support these new dirty bits, render must check each phase’s bit instead of checking needs_render at the start:By the way, this does obsolete our timer for how long rendering takes. Rendering now does different work on different frames, so measuring rendering overall doesn’t really make sense! I’m going to leave this be and just not look at the rendering measures anymore, but the best fix would be to have three timers for the three phases of render.

Well—with all that done, our browser now supports animations with just CSS. And importantly, we can have the browser optimize these animations to avoid re-rastering composited layers.

Composited animations

We’re finally ready to teach the browser how to avoid raster (and layout) when running certain animations. These are called composited animations, since they are compatible with the compositing optimization to avoid raster on every frame. Avoiding raster and composite is simple in concept: keep track of what is animating, and re-run only paint, paint_draw_list and draw on each frame if the only changes are to visual effects like opacity.

This is harder than it sounds. We’ll need to split the new display list into the old composited layers and a new draw display list. To do this we’ll need know how the new and old display lists are related, and what parts of the display list changed. To do that, we’ll add a node field to each display item, storing the node that painted it, as a sort of identifier:

Now, when an animation runs—but nothing else changes—we’ll use these nodes to determine which display items in the draw display list we need to update.

First, when a composited animation runs, save the Element whose style was changed in a new array called composited_updates. We’ll also only set the needs_paint flag, not needs_layout, in this case:

Now, when we commit a frame which only needed the paint phase, we send the composited_updates over to the browser thread. The browser thread can use that to skip composite and raster. The data to be sent across for each animation update will be an Element and a SaveLayer.

To accomplish this we’ll need several steps. First, when painting a SaveLayer, record it on the Element:

Next rename CommitForRaster to CommitData and add a list of composited updates (each of which will contain the Element and SaveLayer pointers).

Now for the browser thread. First, add needs_composite, needs_raster and needs_draw dirty bits and corresponding set_needs_composite, set_needs_raster, and set_needs_draw methods (and remove the old dirty bit):

Then, call set_needs_raster from the places that currently call set_needs_raster_and_draw, such as handle_down:

Use the data passed in commit to decide whether to call set_needs_composite or set_needs_draw, and store off the updates in composited_updates:

Now let’s think about the draw step. Normally, we create the draw display list from the composited layers. But that won’t quite work now, because the composited layers come from the old display list. If we just try re-running paint_draw_list, we’ll get the old draw display list! We need to update draw_list to take into account the new display list based on the composited_updates.

To do so, define a method clone_latest that clones an updated visual effect from composited_updates if there is one, and otherwise clones the original:

Now the draw display list will be based on the new display list, and animations that only require the draw step, like our example opacity animation, will now run super smoothly.

Optimizing Compositing

At this point, our browser now successfully runs composited animations while avoiding needless rasters. But compared to a real browser, there are way too many composited layers—one per paint command! That is a big waste of GPU memory: each composited layer allocates a surface, and each of those allocates and holds on to GPU memory. GPU memory is limited, and we want to use less of it when possible.

To that end, we’d like to use fewer composited layers. The simplest thing we can do is put paint commands into the same composited layer if they have the exact same set of ancestor visual effects in the display list.

Let’s implement that. We’ll need two new methods on composited layers: add and can_merge. The add method just adds a new display item to a composited layer:

But we should only add compatible display items to the same composited layer, determined by the can_merge method. Two composited layers can be merged if they have the same parents:

Now we want to use these methods in composite. Basically, instead of making a new composited layer for every single paint command, walk backwardsBackwards, because we can’t draw things in the wrong order. Later items in the display list have to draw later. through the composited_layers trying to find a composited layer to merge the command into:If you’re not familiar with Python’s for ... else syntax, the else block executes only if the loop never executed break.

With this implementation, multiple paint commands will sometimes end up in the same composited layer, but if the ancestor effects don’t exactly match, they won’t.

We can do even better by placing entire display list subtrees that aren’t animating into the same composited layer. This will let us run some visual effects in the raster phase, reducing the number of composited layers even more.

To implement this, replace the is_paint_command method on DisplayItems with a new needs_compositing field, which is True when a visual effect should go in the draw display list and False when it should go into a composited layer. As a simple heuristic, we’ll always set it to True for SaveLayers (when they actually do something, not for no-ops), regardless of whether they are animating, but we’ll set it to False for ClipRRect commands, since those can’t animate in our browser.

We’ll also need to mark a visual effect as needing compositing if any of its descendants do (even if it’s a ClipRRect). That’s because if one effect is run on the GPU, then one way or another the ones above it will have to be as well:

Now, instead of layers containing bare paint commands, they can contain subtrees of non-composited commands:

Since internal nodes can now be in a CompositedLayer, there is also a bit of added complexity to composited_bounds. We’ll need to recursively union the rects of the subtree of non-composited display items, so let’s add a DisplayItem method to do that:

Our compositing algorithm now creates way fewer layers! It does a good job of grouping together non-animating content to reduce the number of composited layers (which saves GPU memory), and doing as much work as possible in raster rather than draw (which makes composited animations faster).

Overlap and transforms

The compositing algorithm we implemented works great in many cases. Unfortunately, it doesn’t work correctly for display list commands that overlap each other. Let me explain why with an example.

Consider a light blue square overlapped by a light green one, with a white background behind them:

Now suppose we want to animate opacity on the blue square, but not the green square. So the blue square goes in its own composited layer—but what about the green square? It has the same ancestor visual effects as the background. But we don’t want to put the green square in the same composited layer as the background, because the blue square has to be drawn in between the background and the green square.

Therefore, the green square has to go in its own composited layer. This is called an overlap reason for compositing, and is a major complication—and potential source of extra memory use and slowdown—faced by all real browsers.

Let’s modify our compositing algorithm to take overlap into account. Basically, when considering which composited layer a display item goes in, also check if it overlaps with an existing composited layer. If so, start a new CompositedLayer for this display item:

It’s a bit hard to test this code, however, because our browser doesn’t yet support any ways to moveIt’s not possible to create the overlapping squares example of this section without some way of moving an element around. Real browsers have many methods for this, such as position. or growBy grow, I mean that the pixel bounding rect of the visual effect when drawn to the screen is larger than the pixel bounding rect of a paint command like DrawText within it. After all, blending, compositing, and opacity all change the colors of pixels, but don’t expand the set of affected ones. And clips and masking decrease rather than increase the set of pixels, so they can’t cause additional overlap either (though they might cause less overlap). Certain CSS filters, such as blurs, can also expand pixel rects. an element as part of a visual effect, so nothing ever overlaps. Oops! In real browsers there are lots of visual effects that cause overlap, the most important (for animations) being transforms, which let you move the painted output of a DOM element around the screen.Technically, transform is not always just a visual effect. In real browsers, transformed element positions contribute to scrolling overflow. Real browsers mostly do this correctly, but sometimes cut corners to avoid slowing down transform animations. Plus, transforms can be executed efficiently on the GPU.

The transform CSS property is quite powerful, and lets you apply any linear transform in 3D space, but let’s stick to basic 2D translations. That’s enough to implement the example with the blue and green square:The green square has a transform property also so that paint order doesn’t change when you try the demo in a real browser. That’s because there are various rules for painting, and “positioned” elements (such as elements with a transform) are supposed to paint after regular (non-positioned) elements. This particular rule is purely a historical artifact.

Supporting these transforms is simple. First let’s parse the property values:The CSS transform syntax allows multiple transforms in a space-separated sequence; the end result involves applying each in sequence. I won’t implement that, just like I didn’t implement many other parts of the standardized transform syntax.

Then, add some code to paint_visual_effects to add new Transform visual effects:

These Transform display items just call the conveniently built-in Skia canvas translate method:

We also need to fix the hit testing algorithm to take into account translations in click. Instead of just comparing the locations of layout objects with the click point, compute an absolute—in coordinates of what the user sees, including the translation offset—bound and compare against that. Let’s use two helper methods that compute such bounds. The first maps a rect through a translation, and the second walks up the node tree, mapping through each translation found.

However, if you try to load the example above, you’ll find that it still looks wrong—the blue square is supposed to be under the green one, but it’s on top.Hit testing is correct though, because the rendering problem is in compositing, not geometry of layout objects.

That’s because when we test for overlap, we’re comparing the composited_bounds of the display item to the composited_bounds of the composited layer. That means we’re comparing the original location of the display item, not its shifted version. We need to compute the absolute bounds instead:

To implement absolute_bounds, we first need a new map method on Transform that takes a rect in the coordinate space of the “contents” of the transform and outputs a rect in post-transform space. For example, if the transform was translate(20px, 0px) then the output of calling map on a rect would translate it by 20 pixels in the x direction.

Now we can compute the absolute bounds of a display item mapping its composited bounds through all of the visual effects applied to it. This looks a lot like absolute_bounds_for_obj, except that it works on the display list and not the layout object tree:

The blue square should now be underneath the green square, so overlap testing is now complete.Actually, even the current code is not correct now that we have transforms. Since a transform animation moves content around, overlap depends on where it moved to during the animation. Thus animations can cause overlap to appear and disappear during execution. I conveniently chose a demo that starts out overlapping and remains so throughout, but if it didn’t, our browser would not correctly notice when overlap starts happening during the animation. I’ve left solving this to an exercise.

And while we’re here, let’s also make transforms animatable via a new TranslateAnimation class:

And with that, we now have completed the story of a pretty high-performance implementation of composited animations.

You should now be able to create this animation:In this example, I added in a simultaneous opacity animation to demonstrate that our browser supports it. In addition, transforms are compatible with composited animations, but it’s not implemented in our browser. Doing so is a lot like numeric animations, so I’ve left implementing it to an exercise.

Summary

Outline

The complete set of functions, classes, and methods in our browser should now look something like this:

WIDTH

HEIGHT

HSTEP

VSTEP

SCROLL_STEP

class Text:
    def __init__(text, parent)

    def __repr__()

class Element:
    def __init__(tag, attributes, parent)

    def __repr__()

def print_tree(node, indent)

class HTMLParser:
    def __init__(body)

    def parse()

    def get_attributes(text)

    def add_text(text)

    SELF_CLOSING_TAGS

    def add_tag(tag)

    HEAD_TAGS

    def implicit_tags(tag)

    def finish()

BLOCK_ELEMENTS

class TagSelector:
    def __init__(tag)

    def matches(node)

    def __repr__()

class DescendantSelector:
    def __init__(ancestor, descendant)

    def matches(node)

    def __repr__()

INHERITED_PROPERTIES

def cascade_priority(rule)

def compute_style(node, property, value)

def resolve_url(url, current)

def tree_to_list(tree, list)

CHROME_PX

INPUT_WIDTH_PX

def layout_mode(node)

EVENT_DISPATCH_CODE

COOKIE_JAR

def request(url, top_level_url, payload)

def url_origin(url)

FONTS

def get_font(size, weight, style)

def parse_color(color)

def parse_blend_mode(blend_mode_str)

def linespace(font)

def draw_line(canvas, x1, y1, x2, y2)

def draw_text(canvas, x, y, text, font, color)

class MeasureTime:
    def __init__(name)

    def start_timing()

    def stop_timing()

    def text()

class SingleThreadedTaskRunner:
    def __init__(tab)

    def schedule_task(callback)

    def run_tasks()

    def clear_pending_tasks()

    def start_thread()

    def set_needs_quit()

    def run()

class TaskRunner:
    def __init__(tab)

    def schedule_task(task)

    def set_needs_quit()

    def clear_pending_tasks()

    def start_thread()

    def run()

    def handle_quit()

class Task:
    def __init__(task_code)

    def run()

REFRESH_RATE_SEC

class DisplayItem:
    def __init__(rect, children, node)

    def is_paint_command()

    def map(rect)

    def add_composited_bounds(rect)

def map_translation(rect, translation)

class Transform:
    def __init__(translation, rect, node, children)

    def execute(canvas)

    def map(rect)

    def clone(children)

    def __repr__()

class DrawLine:
    def __init__(x1, y1, x2, y2)

    def is_paint_command()

    def execute(canvas)

    def __repr__()

class DrawRRect:
    def __init__(rect, radius, color)

    def is_paint_command()

    def execute(canvas)

    def print(indent)

    def __repr__()

class DrawText:
    def __init__(x1, y1, text, font, color)

    def is_paint_command()

    def execute(canvas)

    def __repr__()

def draw_rect(canvas, l, t, r, b, fill_color, border_color, width)

class DrawRect:
    def __init__(x1, y1, x2, y2, color)

    def is_paint_command()

    def execute(canvas)

    def __repr__()

class ClipRRect:
    def __init__(rect, radius, children, should_clip)

    def execute(canvas)

    def clone(children)

    def __repr__()

class SaveLayer:
    def __init__(sk_paint, node, children, should_save)

    def execute(canvas)

    def clone(children)

    def __repr__()

class DrawCompositedLayer:
    def __init__(composited_layer)

    def execute(canvas)

    def __repr__()

def parse_transform(transform_str)

class CSSParser:
    def __init__(s)

    def whitespace()

    def literal(literal)

    def word()

    def until_semicolon()

    def pair()

    def ignore_until(chars)

    def body()

    def selector()

    def parse()

class BlockLayout:
    def __init__(node, parent, previous)

    def layout()

    def recurse(node)

    def new_line()

    def text(node)

    def input(node)

    def paint(display_list)

    def __repr__()

class DocumentLayout:
    def __init__(node)

    def layout()

    def paint(display_list)

    def __repr__()

class LineLayout:
    def __init__(node, parent, previous)

    def layout()

    def paint(display_list)

    def __repr__()

class TextLayout:
    def __init__(node, word, parent, previous)

    def layout()

    def paint(display_list)

    def __repr__()

class InputLayout:
    def __init__(node, parent, previous)

    def layout()

    def paint(display_list)

    def __repr__()

def paint_visual_effects(node, cmds, rect)

SETTIMEOUT_CODE

XHR_ONLOAD_CODE

class JSContext:
    def __init__(tab)

    def run(script, code)

    def dispatch_event(type, elt)

    def get_handle(elt)

    def querySelectorAll(selector_text)

    def getAttribute(handle, attr)

    def innerHTML_set(handle, s)

    def style_set(handle, s)

    def dispatch_settimeout(handle)

    def setTimeout(handle, time)

    def dispatch_xhr_onload(out, handle)

    def XMLHttpRequest_send(method, url, body, isasync, handle)

    def now()

    def requestAnimationFrame()

def parse_transition(value)

def diff_styles(old_style, new_style)

class NumericAnimation:
    def __init__(old_value, new_value, num_frames)

    def animate()

    def __repr__()

class TranslateAnimation:
    def __init__(old_value, new_value, num_frames)

    def __repr__()

    def animate()

ANIMATED_PROPERTIES

def style(node, rules, tab)

def absolute_bounds_for_obj(obj)

def absolute_bounds(display_item)

class CompositedLayer:
    def __init__(skia_context, display_item)

    def can_merge(display_item)

    def add(display_item)

    def composited_bounds()

    def absolute_bounds()

    def raster()

    def __repr__()

def raster(display_list, canvas)

def clamp_scroll(scroll, tab_height)

class Tab:
    def __init__(browser)

    def allowed_request(url)

    def script_run_wrapper(script, script_text)

    def load(url, body)

    def set_needs_render()

    def set_needs_layout()

    def set_needs_paint()

    def request_animation_frame_callback()

    def run_animation_frame(scroll)

    def render()

    def click(x, y)

    def submit_form(elt)

    def keypress(char)

    def go_back()

class CommitData:
    def __init__(url, scroll, height, display_list, composited_updates)

def print_composited_layers(composited_layers)

def add_parent_pointers(nodes, parent)

class Browser:
    def __init__()

    def render()

    def commit(tab, data)

    def set_needs_animation_frame(tab)

    def set_needs_raster()

    def set_needs_composite()

    def set_needs_draw()

    def composite()

    def clone_latest(visual_effect, current_effect)

    def paint_draw_list()

    def composite_raster_and_draw()

    def schedule_animation_frame()

    def handle_down()

    def clear_data()

    def set_active_tab(index)

    def handle_click(e)

    def handle_key(char)

    def schedule_load(url, body)

    def handle_enter()

    def load(url)

    def load_internal(url)

    def raster_tab()

    def raster_chrome()

    def draw()

    def handle_quit()

def add_main_args()

if __name__ == "__main__"

Exercises

Background-color: Implement animations of the background-color CSS property. You’ll have to define a new kind of interpolation that applies to all the color channels.

Easing functions: Our browser only implements a linear interpolation between start and end values, but there are many other easing functions (in fact, the default one in real browsers is cubic-bezier(0.25, 0.1, 0.25, 1.0), not linear). Implement this easing function, and one or two others.

Composited transform animations: Our browser supports transform animations, but they are not composited (i.e., they cause raster on every frame). Implement composited animations for transform. It just requires edits to the code to handle transform in all the same places as opacity. The transform animation example should then become noticeably faster.

Threaded animations: Despite Chapter 12 being all about threading, we didn’t actually implement threaded animations in this chapter—they are all driven by code running on the main thread. But just like scrolling, in a real browser this is not good enough, since there could be many main-thread tasks slowing things down. Add support for threaded animations. Doing so will require replicating some event loop code from the main thread, but if you’re careful you should be able to reuse all of the animation classes. (Don’t worry too much about how to synchronize these animations with the main thread, except to cause them to stop after the next commit when DOM changes occur that invalidate the animation. Real browsers encounter a lot of complications in this area.)

Width animations: Implement the CSS width and height properties; when width is set to some number of pixels on an element, the element should be that many pixels wide, regardless of how its width would normally be computed; the same goes for height. Make them animatable; you’ll need a variant of NumericAnimation that parses and produces pixel values (the “px” suffix in the string). Since width and height are layout-inducing, make sure that animating them sets needs_layout. Check that animating width in your browser changes line breaks. This example should work once you’ve implemented width animations.

CSS animations: Implement the basics of the CSS animations API, in particular enough of the animation CSS property and parsing of @keyframe to implement the demos here and here.

Overlap testing w/transform animations: As mentioned in a footnote, our browser currently does not overlap test correctly in the presence of transform animations that cause overlap to come and go. First create a demo that exhibits the bug, and then fix it. One way to fix it is to enter “assume overlap mode” whenever an animated transform display item is encountered. This means that every subsequent display item is assumed to overlap the animating one (even if it doesn’t at the moment), and therefore can’t merge into any CompositedLayer earlier in the list than the animating one. Another way is to run overlap testing on every animation frame in the browser thread, and if the results differ from the prior frame, re-do compositing and raster. And if you’ve done the CSS animations exercise, and a transform animation is defined in terms of a CSS animation, you can analytically determine the bounding box of the animation, and use that for overlap instead.

Avoiding sparse composited layers: Our browser’s algorithm currently always merges paint chunks that have compatible ancestor effects. But this can lead to inefficient situations, such as where two paint chunks that are visually very far away on the web page (e.g. one at the very top and one thousands of pixels lower down) end up in the same CompositedLayer. That can be very bad, because it results in a huge skia.Surface that is mostly wasted GPU memory. One way to reduce that problem is to stop merging paint chunks that would make the total area of the skia.Surface larger than some fixed value. Implement that.Another way is via surface tiling (this technique was briefly discussed in a Go Further block in Chapter 11).

Short display lists: it’s relatively common in real browsers to encounter CompositedLayers that are only a single solid color, or only a few simple paint commands.A real browser would use as among its criteria whether the time to raster the provided display items is low enough to not justify a GPU texture. This will be true for solid colors, but probably not complex shapes or text. Implement an optimization that skips storing a skia.Surface on a CompositedLayer with less than a fixed number (3, say) of paint commands, and instead execute them directly. In other words, raster on these CompositedLayers will be a no-op and draw will execute the paint commands instead.

Atomic effects: Our browser currently uses a simplistic algorithm for building the draw list which doesn’t handle nested, composited visual effects correctly, especially when there are overlapping elements on the page(this was discussed in a Go Further block as well). Fix this. You can still walk up the display list from each composited layer, but you’ll need to avoid making two clones of the same visual effect node. You should end up with the following draw display list for this example, with one (probably internal-to-Skia) render surface:See the Go Further block about render surfaces for more information.

Animated scrolling: Real browsers have many kinds of animations during scroll. For example, pressing the down key or the down-arrow in a scrollbar causes a pleasant animated scroll, rather than the immediate scroll our browser current implements. Or on mobile, a touch interaction often causes a “fling” scroll according to a physics-based model of scroll momentum with friction. Implement the scroll-behavior CSS property on the <body> element, and use it to cause animated scroll in handle_down, by delegating scroll to a main thread animation.This will result in your browser losing threaded scrolling. If you’ve implemented the threaded animations exercise, you could build on that code to animate scroll on the browser thread. You’ll need to implement a new ScrollAnimation class and some logic in run_animation_frame. Scrolling in the transform transition example should now be smooth, as that example uses scroll-behavior.