More about the z-algorithm and stacking contexts

In this post I explained how the concept of stacking context works and how it is useful to DomScape. I ended the post with a pseudo-algorithm to produce z-values on basis of the stacking context. I felt the need to explain it a bit more elaborately. But first a small introduction into HTML and stacking contexts.

HTML is a markup language that contains over 100 markup tags, also called HTML elements, that allow the web page author to describe the content of a web page. HTML is hierarchical: elements can (and will) contain other elements. The elements highest in the hierarchy often describe general sections on the website: a menu, a header, content section, etc. The elements that are deeper in the hierarchy often describe a particular section in more detail, e.g. a menu item.

Because of this hierarchical structure elements that are high in the HTML element hierarchy often have many descendants. These elements all render in the same location unless they are specifically told not to. It is easy to see that a web page of almost any size will thus contain a fair amount of overlap occurring between ancestors and descendants.

Elements can be also be displaced by applying certain CSS layout properties. This can make elements overlap that are not directly related to each other. HTML deals with these kind of situations by employing the stacking context. All elements in a web page are in a stacking context. When two elements overlap the stacking context is used to determine what element is rendered on top.

A stacking context consists of seven layers that each contains a different kind of elements. Every element in a web page belongs to one of these layers. Starting from back to front, the seven layers are rendered on top of each other. Elements in layer n always render on top elements in layer n - 1.

1. The background and borders of the element that establishes the stacking context
2. Positioned descendants with negative z-index
3. Block-level descendants in the normal flow
4. Floating descendants and their contents
5. Inline-level descendants in the normal flow
6. Positioned descendants with z-index set to auto or 0
7. Positioned descendants with z-index greater than 0

I will not go into detail what every layer means as this is covered here.

Important to note is that by default the stacking context is established by the highest element in the HTML hierarchy, the body element. If, however, an element is positioned, i.e. if the element is in layer 2, 6 or 7, it will establish a stacking context for all of its descendants. A web page can - and often will - contain more than one stacking context.

Algorithm
In DomScape all elements need a value on the z-axis in order to generate a 3D perspective, but how do we do that? In recent posts I formed two important constraints for the solution:

1. Elements cannot overlap in 3D space. All elements should be easily discernible from other elements. If elements occupy the same space on the x,y-plane they should have different z-values.
2. The 3D perspective should look exactly like the normal, 2D perspective when viewed orthogonally from the top. Elements that are rendered on top in a web page thus have higher z-values than elements that render at the bottom.

Considering the second point it becomes very obvious why the stacking context is so relevant to DomScape: it provides the correct order of elements. Although it does not give exact z-values, the order of the elements can be translated into z-values. That is what the following algorithm does.

e, f: element

E: collection of all elements  
Ei: collection of all elements in the initial stacking context
F: collection of elements with calculated z

assign_z_to Ei

function assign_z_to: context C
 source_sort C
 z-index_sort C
 layer_sort C

 for every element e in C:
   z of e = 0
    
for every element f in F:
  if e overlaps with f
       e.z = 1 + f.z

   add e to F
   if e establishes context C'
     assign_z_to C'     

In human language the algorithm does the following. It takes all elements in the initial stacking context, established by the body element, and sorts it in three ways so that the order of the elements represents the order of the stacking context. All elements that belong to this stacking context are sorted on their stacking layer. If the element is in layer two or seven, the elements are sorted by z-index as well. When elements are in the same stacking layer and have the same z-index (or no z-index), those elements are sorted by their order in the source code.

The algorithm then iterates through the sorted elements - starting at the element that is lowest in the stacking context. If an element overlaps with an earlier element, the element is given a higher z-value, because a later element should be rendered on top of an earlier element. Earlier elements - with a z-value assigned - are kept in a separate list to speed up the algorithm.

Whenever an element is in layer 2, 6 or 7 it establishes a stacking context for its descendants. The z-values for this new context are calculated first, because the next element in the current context might overlap with the elements of the new context.

I have now implemented this algorithm in my working prototype. It produces 3D models that meet both constraints I mentioned earlier. The following video shows a web snippet with all elements in level 3: Block-level descendants in the normal flow. In future videos I will show how the algorithm provides different z-values when the elements are in different layers.