home / twitter / github / rss

Instanced Line Rendering Part II: Alpha blending

Rye Terrell
October 01, 2021

A couple of years ago I published Instanced Line Rendering, which covered rendering lines with various joins and end caps and in 2D and 3D with an instancing approach. One feature not covered in the first write-up was proper management of the instance geometry to support alpha blending. Let’s take a look at one way to address that.

The problem

The original line rendering approach works fine if you’re not using alpha blending:

When alpha blending is used, however, the overlap in the geometry becomes visible:

It should look like this:

In order to prevent that from happening, we’ll separate the line into multiple non-overlapping geometries and render them independently:

Intermediate segments

[source]

Let’s take a look at what our original algorithm looks like when we render segments with alpha and no caps or joins:

Note that on each end of a segment, there’s at most one vertex that intersects the neighboring segment. We’ll identify this vertex and shift it such that it no longer intersects its neighbor. First we’ll do this with the intermediate segments, then we’ll adjust the terminal segments on either end of the line strip.

Adjusting the intersecting vertices of intermediate segments to prevent overlap.

Let’s take a look at the vertex shader we’ll use to accomplish this. We’ll pull in our instance geometry in position and the line width. We’ll also pull in the four vertices composing the three segments that we’ll need for this calculation: our central segment pB to pC, and the segments on either side of it, pA to pB and pC to pD.

precision highp float;
attribute vec2 position;
attribute vec2 pA, pB, pC, pD;
uniform float width;
uniform mat4 projection;

In the vertex shader, we’re working with one vertex at a time, and we need to figure out which one - which side of the segment, and whether it is intersecting or not. We can figure out which side we’re working on by looking at the x-coordinate of our position. If it’s zero, we’re working on the pA, pB, pC side, if it’s one, we’re working on the pD, pC, pB side. We can then map those vertices to p0, p1, and p2 so that we can proceed without caring which side we’re operating on. We’ll also need to adjust the instance position if we’re working on the pD, pC, pB side so that everything lines up in the right direction. We’ll do this and store it in a new variable pos.

void main() {
  vec2 p0 = pA;
  vec2 p1 = pB;
  vec2 p2 = pC;
  vec2 pos = position;
  if (position.x == 1.0) {
    p0 = pD;
    p1 = pC;
    p2 = pB;
    pos = vec2(1.0 - position.x, -position.y);
  }

Next we’ll find tangent and normal vectors where our two line segments meet, along with the vector perpendicular to p0 to p1:

  // Find the normal vector.
  vec2 tangent = normalize(normalize(p2 - p1) + normalize(p1 - p0));
  vec2 normal = vec2(-tangent.y, tangent.x);

  // Find the vector perpendicular to p0 -> p1.
  vec2 p01 = p1 - p0;
  vec2 p21 = p1 - p2;
  vec2 p01Norm = normalize(vec2(-p01.y, p01.x));

The normal and tangent vectors between two segments.

Now we can determine the direction of the bend, which we’ll assign to sigma as \(-1\) or \(+1\):

  // Determine the bend direction.
  float sigma = sign(dot(p01 + p21, normal));

If we compare pos.y to sigma, we can determine whether or not we’re the intersecting vertex and adjust it accordingly. Otherwise we’ll give it the usual instanced line segment treatment.

  if (sign(pos.y) == -sigma) {
    // This is an intersecting vertex. Adjust the position so that there's no overlap.
    vec2 point = 0.5 * normal * -sigma * width / dot(normal, p01Norm);
    gl_Position = projection * vec4(p1 + point, 0, 1);
  } else {
    // This is a non-intersecting vertex. Treat it normally.
    vec2 xBasis = p2 - p1;
    vec2 yBasis = normalize(vec2(-xBasis.y, xBasis.x));
    vec2 point = p1 + xBasis * pos.x + yBasis * width * pos.y;
    gl_Position = projection * vec4(point, 0, 1);
  }
}

Here’s the attribute definitions. Note that since we’re utilizing three segments, we organize our data into four points:

attributes: {
  position: {
    buffer: geometry.positions,
    divisor: 0,
  },
  pA: {
    buffer: regl.prop<any, any>("points"),
    divisor: 1,
    offset: Float32Array.BYTES_PER_ELEMENT * 0,
  },
  pB: {
    buffer: regl.prop<any, any>("points"),
    divisor: 1,
    offset: Float32Array.BYTES_PER_ELEMENT * 2,
  },
  pC: {
    buffer: regl.prop<any, any>("points"),
    divisor: 1,
    offset: Float32Array.BYTES_PER_ELEMENT * 4,
  },
  pD: {
    buffer: regl.prop<any, any>("points"),
    divisor: 1,
    offset: Float32Array.BYTES_PER_ELEMENT * 6,
  },
},

If we render our intermediate segments, we can see that they are no longer overlapping. Great!

interleavedStrip({
  points,
  segments: points.length - 3,
  width,
  color,
  projection,
  viewport,
});

Intermediate segments adjusted to prevent overlap.

Terminal segments

[source]

Let’s take a look at rendering the terminal segments of our line strip now. The vertex shader is very similar, we simply give any vertex with a position.x value of zero the usual instanced line segment treatment, and otherwise use the same procedure we used for the intermediate segments. Since we don’t need to determine which side the intersecting point is on, we don’t need to perform any mapping from pA to p0, etc.

void main() {
  if (position.x == 0.0) {
    vec2 xBasis = pB - pA;
    vec2 yBasis = normalize(vec2(-xBasis.y, xBasis.x));
    vec2 point = pA + xBasis * position.x + yBasis * width * position.y;
    gl_Position = projection * vec4(point, 0, 1);
    return;
  }

  // Find the normal vector.
  vec2 tangent = normalize(normalize(pC - pB) + normalize(pB - pA));
  vec2 normal = vec2(-tangent.y, tangent.x);

  // Find the perpendicular vectors.
  vec2 ab = pB - pA;
  vec2 cb = pB - pC;
  vec2 abNorm = normalize(vec2(-ab.y, ab.x));

  // Determine the bend direction.
  float sigma = sign(dot(ab + cb, normal));

  if (sign(position.y) == -sigma) {
    // This is an intersecting vertex. Adjust the position so that there's no overlap.
    vec2 position = 0.5 * normal * -sigma * width / dot(normal, abNorm);
    gl_Position = projection * vec4(pB + position, 0, 1);
  } else {
    // This is a non-intersecting vertex. Treat it normally.
    vec2 xBasis = pB - pA;
    vec2 yBasis = normalize(vec2(-xBasis.y, xBasis.x));
    vec2 point = pA + xBasis * position.x + yBasis * width * position.y;
    gl_Position = projection * vec4(point, 0, 1);
  }
}`,

Our attribute definitions are similar, but we add a stride so that we can render more than one terminal segment at a time:

attributes: {
  position: {
    buffer: geometry.positions,
    divisor: 0,
  },
  pA: {
    buffer: regl.prop<any, any>("points"),
    divisor: 1,
    offset: Float32Array.BYTES_PER_ELEMENT * 0,
    stride: Float32Array.BYTES_PER_ELEMENT * 6,
  },
  pB: {
    buffer: regl.prop<any, any>("points"),
    divisor: 1,
    offset: Float32Array.BYTES_PER_ELEMENT * 2,
    stride: Float32Array.BYTES_PER_ELEMENT * 6,
  },
  pC: {
    buffer: regl.prop<any, any>("points"),
    divisor: 1,
    offset: Float32Array.BYTES_PER_ELEMENT * 4,
    stride: Float32Array.BYTES_PER_ELEMENT * 6,
  },
},

We can invoke our line rendering command with the three points on either end of our line strip, being careful to list them in order of most to least terminal:

interleavedStripTerminal({
  points: [
    points[0],
    points[1],
    points[2],
    points[points.length - 1],
    points[points.length - 2],
    points[points.length - 3],
  ],
  segments: 2,
  width,
  color,
  projection,
  viewport,
});

Now let’s render our intermediate and terminal segments to see how we’re doing:

Non-overlapping intermediate (red) and terminal (green) segments.

Bevel joins

[source]

There’s two pieces left to render - caps and joins. Let’s take a look at joins next. First up, bevel joins. I’ve already covered bevel joins in detail here, so we’ll focus on what has changed. The primary difference is that since the segments have shifted their vertices so that they don’t overlap, we can no longer rely on knowing the position of the midpoint of each segment for use as one of the vertices of the bevel geometry.

First, let’s tweak our instance geometry a little bit to allow the third vertex to be adjusted in our shader:

const geometry = [
  [1, 0, 0],
  [0, 1, 0],
  [0, 0, 1],
];

Then in our vertex shader, we introduce the adjustment to that vertex as p2 and use it when calculating the vertex position:

vec2 p0 = 0.5 * sigma * width * (sigma < 0.0 ? abn : cbn);
vec2 p1 = 0.5 * sigma * width * (sigma < 0.0 ? cbn : abn);
vec2 p2 = -0.5 * normal * sigma * width / dot(normal, abn);
vec2 point = pointB + position.x * p0 + position.y * p1 + position.z * p2;

And that’s it! Let’s invoke it and take a look a the output.

join({
  points,
  instances: points.length - 2,
  width,
  color,
  projection,
  viewport,
});

Bevel joins in blue.

Miter joins

[source]

I covered miter joins originally here. The change required for them is nearly identical to that required for bevel joins. First we update the instance geometry to accommodate a fourth component instead of the previous three:

const geometry = {
  positions: [
    [1, 0, 0, 0],
    [0, 1, 0, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 1],
  ],
  cells: [
    [0, 1, 2],
    [0, 2, 3],
  ],
};

Then we calculate an adjustment to the fourth vertex as p3 and use it when calculating the final vertex position:

vec2 p0 = 0.5 * width * sigma * (sigma < 0.0 ? abNorm : cbNorm);
vec2 p1 = 0.5 * miter * sigma * width / dot(miter, abNorm);
vec2 p2 = 0.5 * width * sigma * (sigma < 0.0 ? cbNorm : abNorm);
vec2 p3 = -0.5 * miter * sigma * width / dot(miter, abNorm);
vec2 point = pointB + position.x * p0 + position.y * p1 + position.z * p2 + position.w * p3;

We can invoke the join command the same way to see how we’ve done:

Miter joins in blue.

Round joins

[source]

We’ll need a bit more work to get round joins working. Since we originally relied on overdraw to simplify our round joins, we need to overhaul the instance geometry and how it’s used.

Since we can utilize a variable resolution for our round joins (number of “slices” in the join geometry), we’ll write a function that takes a resolution and returns our geometry:

function roundGeometry(resolution: number) {
  const ids: number[] = [];
  const cells: number[][] = [];
  for (let i = 0; i < resolution + 2; i++) {
    ids.push(i);
  }
  for (let i = 0; i < resolution; i++) {
    cells.push([0, i + 1, i + 2]);
  }
  return {
    ids,
    cells,
  };
}

If you read that function carefully, you’ll see that there’s little indication of anything “round” or even “geometric” in it! Here’s the deal: each incremental “id” is used to convey which slice of our semicircle each vertex belongs to:

The id of each vertex indicates which slice it belongs to in the round join.

Let’s see how we use that in our vertex shader. We’ll pull in all this data and perform the usual calculations to determine our basis vectors, normal vectors, and bend direction:

precision highp float;
attribute vec2 pointA, pointB, pointC;
attribute float id;
uniform float width;
uniform mat4 projection;

// Insert the resolution directly into our shader.
const float resolution = ${resolution.toExponential()};

void main() {
  // Calculate the x- and y- basis vectors.
  vec2 xBasis = normalize(normalize(pointC - pointB) + normalize(pointB - pointA));
  vec2 yBasis = vec2(-xBasis.y, xBasis.x);

  // Calculate the normal vectors for each neighboring segment.
  vec2 ab = pointB - pointA;
  vec2 cb = pointB - pointC;
  vec2 abn = normalize(vec2(-ab.y, ab.x));
  vec2 cbn = -normalize(vec2(-cb.y, cb.x));

  // Determine the direction of the bend.
  float sigma = sign(dot(ab + cb, yBasis));

If this is the zeroth id, it’s the center of our circle. Stretch it to meet the intersection of the two segments and return:

  if (id == 0.0) {
    gl_Position = projection * vec4(pointB + -0.5 * yBasis * sigma * width / dot(yBasis, abn), 0, 1);
    return;
  }

Otherwise we’ll calculate the angle for this vertex, determine its position from that angle, and multiply it by our basis vectors to obtain the final position:

  float theta = acos(dot(abn, cbn));
  theta = (sigma * 0.5 * ${Math.PI}) + -0.5 * theta + theta * (id - 1.0) / resolution;
  vec2 pos = 0.5 * width * vec2(cos(theta), sin(theta));
  pos = pointB + xBasis * pos.x + yBasis * pos.y;

  gl_Position = projection * vec4(pos, 0, 1);
}

Now we can invoke our join command to see our non-overlapping round joins:

Round joins in blue.

Caps

[source]

The last and simplest piece of our non-overlapping line geometry is the caps. We can reuse the same vertex shader for both round and square caps. All we’re going to do is calculate the basis vectors and apply them to the square or round geometries:

precision highp float;
attribute vec2 position;
attribute vec2 pA, pB;
uniform float width;
uniform mat4 projection;

void main() {
  vec2 xBasis = normalize(pA - pB);
  vec2 yBasis = vec2(-xBasis.y, xBasis.x);
  vec2 point = pA + xBasis * width * position.x + yBasis * width * position.y;
  gl_Position = projection * vec4(point, 0, 1);
}`,

Like the terminal segment attributes, we’ll define a stride that will allow us to render both caps in a single draw call:

    attributes: {
      position: {
        buffer: geometry.positions,
        divisor: 0,
      },
      pA: {
        buffer: regl.prop<any, any>("points"),
        divisor: 1,
        offset: Float32Array.BYTES_PER_ELEMENT * 0,
        stride: Float32Array.BYTES_PER_ELEMENT * 4,
      },
      pB: {
        buffer: regl.prop<any, any>("points"),
        divisor: 1,
        offset: Float32Array.BYTES_PER_ELEMENT * 2,
        stride: Float32Array.BYTES_PER_ELEMENT * 4,
      },
    },

And of course, we’ll need the geometries:

export function roundCapGeometry(resolution: number) {
  const positions = [[0, 0]];
  for (let i = 0; i <= resolution; i++) {
    const theta = -0.5 * Math.PI + (Math.PI * i) / resolution;
    positions.push([0.5 * Math.cos(theta), 0.5 * Math.sin(theta)]);
  }
  const cells: number[][] = [];
  for (let i = 0; i < resolution; i++) {
    cells.push([0, i + 1, i + 2]);
  }
  return { positions, cells };
}

export function squareCapGeometry() {
  return {
    positions: [
      [0, 0.5],
      [0, -0.5],
      [0.5, -0.5],
      [0.5, 0.5],
    ],
    cells: [
      [0, 1, 2],
      [0, 2, 3],
    ],
  };
}

Finally we’ll invoke our cap rendering command and check out the results. Note that we again provide the position information for the two terminal segments, most terminal points first:

cap({
  points: [points[0], points[1], points[points.length - 1], points[points.length - 2]],
  instances: 2,
  width,
  color,
  projection,
  viewport,
});

Round caps in pink.

Square caps in pink.

Wrap up

Now that we’ve got all the pieces in place, we can finally render our line with alpha blending, with no overlap artifacts:

Round join, square caps.

Round join, round caps.

Miter join, round caps.

Bevel join, round caps.

Further optimization

Final notes

Credits