Instanced Line Rendering Part II: Alpha blending
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
- Terminal segments
- Joins
- Caps
Intermediate segments
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
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
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
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
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
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
- I think it should be possible to design the intermediate segment geometry such that it includes the join geometry, combining two draw calls into one. I think the same could probably be done with the terminal segments, resulting in two total draw calls per line instead of four. Things start to get a little combinatorial explosion-y with the various cap and join geometries, but it could be useful to speed things up for specific cases.
- If you’re desperate to keep everything to a single draw call, you could use the stencil buffer to prevent overlapping alpha blending issues with the round join, round cap case. There are performance tradeoffs to consider, there, though.
Final notes
- I’ve skipped covering line segments here (as opposed to strips), but it should be straightforward to apply the end caps presented here to line segments from part one of this series.
- All the source is available here and is free in every way. Enjoy!
Credits
- This post was inspired and motivated through discussions with and experimentation by the excellent Ricky Reusser.
- regl for making WebGL awesome.