use super::gpu;
use super::{
Column, ColumnFormat, KindUniforms, Mark, MarkCommon, MarkKind, MarkView, PrepareContext,
};
use crate::captions::CaptionFont;
use std::collections::HashMap;
const RASTER: f32 = 48.0;
const ATLAS_WIDTH: u32 = 1024;
fn spread_for(raster: f32) -> i32 {
((raster / 6.0).round() as i32).max(2)
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum GlyphField {
#[default]
Sdf,
Msdf,
}
#[derive(Debug, Clone, PartialEq)]
pub struct LabelIcon {
pub name: String,
pub size: f32,
pub color: [u8; 4],
pub gap: f32,
}
impl LabelIcon {
pub fn new(name: impl Into<String>, size: f32) -> Self {
Self {
name: name.into(),
size,
color: [255, 255, 255, 255],
gap: 4.0,
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum LabelAnchor {
#[default]
Center,
Right,
Left,
Above,
Below,
BelowRight,
BelowLeft,
AboveRight,
AboveLeft,
}
#[derive(Debug, Clone, PartialEq)]
pub struct TextLabel {
pub position: [f64; 3],
pub text: String,
pub color: [u8; 4],
pub priority: f32,
pub anchor: LabelAnchor,
pub offset: [f32; 2],
pub offset_em: [f32; 2],
pub path: Option<Vec<[f64; 3]>>,
pub icon: Option<LabelIcon>,
pub reserve: Option<[f32; 4]>,
pub background: Option<LabelBackground>,
}
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct LabelBackground {
pub color: [u8; 4],
pub padding: [f32; 4],
pub border_color: [u8; 4],
pub border_width: f32,
}
impl TextLabel {
pub fn new(position: [f64; 3], text: impl Into<String>) -> Self {
Self {
position,
text: text.into(),
color: [255, 255, 255, 255],
priority: 0.0,
anchor: LabelAnchor::Center,
offset: [0.0, 0.0],
offset_em: [0.0, 0.0],
path: None,
icon: None,
reserve: None,
background: None,
}
}
pub fn with_icon(mut self, icon: LabelIcon) -> Self {
self.icon = Some(icon);
self
}
pub fn along(path: Vec<[f64; 3]>, text: impl Into<String>) -> Self {
let mut l = Self::new(path.first().copied().unwrap_or_default(), text);
l.path = Some(path);
l
}
}
#[derive(Debug, Clone, Copy)]
struct PathGlyph {
along: f32,
rect: [f32; 4],
}
type GlyphSlot = (u32, u32, u32, u32, i32, i32);
type ViewKey = ([f32; 16], (u32, u32), [f64; 3], [u32; 5]);
type Quad = ([f32; 4], [f32; 4], [u8; 4], f32);
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
enum GlyphKey {
Char(u8, char),
Icon(String),
Solid,
}
struct Atlas {
raster: f32,
spread: i32,
msdf: bool,
height: u32,
pixels: Vec<u8>,
glyphs: HashMap<GlyphKey, Option<GlyphSlot>>,
shelf_x: u32,
shelf_y: u32,
shelf_h: u32,
dirty: bool,
}
impl Atlas {
fn new(raster: f32, msdf: bool) -> Self {
Self {
raster,
spread: spread_for(raster),
msdf,
height: 128,
pixels: vec![0; (ATLAS_WIDTH * 128 * 4) as usize],
glyphs: HashMap::new(),
shelf_x: 0,
shelf_y: 0,
shelf_h: 0,
dirty: true,
}
}
fn pack(&mut self, w: u32, h: u32, texels: &[[u8; 4]]) -> (u32, u32) {
if self.shelf_x + w + 1 > ATLAS_WIDTH {
self.shelf_y += self.shelf_h + 1;
self.shelf_x = 0;
self.shelf_h = 0;
}
while self.shelf_y + h + 1 > self.height {
self.height *= 2;
self.pixels
.resize((ATLAS_WIDTH * self.height * 4) as usize, 0);
}
let (x, y) = (self.shelf_x, self.shelf_y);
for row in 0..h {
let dst = (((y + row) * ATLAS_WIDTH + x) * 4) as usize;
let src = &texels[(row * w) as usize..((row + 1) * w) as usize];
self.pixels[dst..dst + 4 * w as usize].copy_from_slice(bytemuck::cast_slice(src));
}
self.shelf_x += w + 1;
self.shelf_h = self.shelf_h.max(h);
self.dirty = true;
(x, y)
}
fn ensure(&mut self, font: &mut CaptionFont, index: u8, c: char) {
let key = GlyphKey::Char(index, c);
if self.glyphs.contains_key(&key) {
return;
}
let spread = self.spread;
let field = if self.msdf {
let grow = font.synthetic_outset(self.raster);
font.outline(c, self.raster)
.and_then(|o| super::msdf::msdf(&o, spread, grow))
} else {
None
};
let slot = match field {
Some(f) => {
let (x, y) = self.pack(f.width, f.height, &f.texels);
Some((x, y, f.width, f.height, f.offset_x, f.offset_y))
}
None => {
let g = font.glyph(c, self.raster).clone();
if g.is_blank() {
None
} else {
let w = g.width + 2 * spread as u32;
let h = g.height + 2 * spread as u32;
let texels: Vec<[u8; 4]> =
distance_field(&g.coverage, g.width, g.height, spread)
.into_iter()
.map(|v| [v; 4])
.collect();
let (x, y) = self.pack(w, h, &texels);
Some((x, y, w, h, g.offset_x - spread, g.offset_y - spread))
}
}
};
self.glyphs.insert(key, slot);
}
fn ensure_icon(&mut self, name: &str, w: u32, h: u32, alpha: &[u8]) {
let key = GlyphKey::Icon(name.to_owned());
if self.glyphs.contains_key(&key) {
return;
}
let spread = self.spread;
let texels: Vec<[u8; 4]> = distance_field(alpha, w, h, spread)
.into_iter()
.map(|v| [v; 4])
.collect();
let (fw, fh) = (w + 2 * spread as u32, h + 2 * spread as u32);
let (x, y) = self.pack(fw, fh, &texels);
self.glyphs
.insert(key, Some((x, y, fw, fh, -spread, -spread)));
}
}
fn edt_1d(f: &[f32], out: &mut [f32], v: &mut [usize], z: &mut [f32]) {
let n = f.len();
let mut k = 0usize;
v[0] = 0;
z[0] = f32::NEG_INFINITY;
z[1] = f32::INFINITY;
for q in 1..n {
loop {
let p = v[k];
let s = ((f[q] + (q * q) as f32) - (f[p] + (p * p) as f32))
/ (2.0 * q as f32 - 2.0 * p as f32);
if s <= z[k] && k > 0 {
k -= 1;
continue;
}
if s <= z[k] {
v[0] = q;
z[0] = f32::NEG_INFINITY;
z[1] = f32::INFINITY;
break;
}
k += 1;
v[k] = q;
z[k] = s;
z[k + 1] = f32::INFINITY;
break;
}
}
k = 0;
for (q, o) in out.iter_mut().enumerate() {
while z[k + 1] < q as f32 {
k += 1;
}
let p = v[k];
let d = q as f32 - p as f32;
*o = d * d + f[p];
}
}
fn edt_2d(set: &[bool], w: usize, h: usize) -> Vec<f32> {
const BIG: f32 = 1e20;
let mut grid: Vec<f32> = set.iter().map(|&s| if s { 0.0 } else { BIG }).collect();
let n = w.max(h);
let mut f = vec![0.0; n];
let mut out = vec![0.0; n];
let mut v = vec![0usize; n];
let mut z = vec![0.0; n + 1];
for x in 0..w {
for y in 0..h {
f[y] = grid[y * w + x];
}
edt_1d(&f[..h], &mut out[..h], &mut v, &mut z);
for y in 0..h {
grid[y * w + x] = out[y];
}
}
for y in 0..h {
f[..w].copy_from_slice(&grid[y * w..y * w + w]);
edt_1d(&f[..w], &mut out[..w], &mut v, &mut z);
grid[y * w..y * w + w].copy_from_slice(&out[..w]);
}
grid
}
fn distance_field(coverage: &[u8], w: u32, h: u32, spread: i32) -> Vec<u8> {
let pw = (w as i32 + 2 * spread) as usize;
let ph = (h as i32 + 2 * spread) as usize;
let mut inside = vec![false; pw * ph];
for y in 0..h as usize {
for x in 0..w as usize {
inside[(y + spread as usize) * pw + x + spread as usize] =
coverage[y * w as usize + x] >= 128;
}
}
let outside: Vec<bool> = inside.iter().map(|&b| !b).collect();
let to_inside = edt_2d(&inside, pw, ph);
let to_outside = edt_2d(&outside, pw, ph);
to_inside
.iter()
.zip(&to_outside)
.map(|(&di, &dout)| {
let d = if di > 0.0 {
di.sqrt() - 0.5
} else {
-(dout.sqrt() - 0.5)
};
let v = 0.5 - d / (2.0 * spread as f32);
(v.clamp(0.0, 1.0) * 255.0 + 0.5) as u8
})
.collect()
}
pub struct TextLabels {
pub common: MarkCommon,
fonts: Vec<CaptionFont>,
labels: Vec<TextLabel>,
pub raster_size: f32,
pub glyph_field: GlyphField,
icons: HashMap<String, (u32, u32, Vec<u8>)>,
pub font_size: f32,
pub halo_width: f32,
pub line_height: f32,
pub halo_color: [u8; 4],
pub collision: bool,
pub padding: f32,
pub collision_index: Option<super::SharedCollision>,
pub reserve_scale: f32,
pub publish_visibility: Option<super::SharedVisibility>,
pub stickiness: f32,
pub max_bend: f32,
pub max_width: Option<f32>,
pub break_anywhere: bool,
path_layout: Vec<Option<(Vec<PathGlyph>, f32)>>,
atlas: Atlas,
atlas_gpu: Option<(u32, gpu::Texture, gpu::BindGroup)>,
layout: Vec<(usize, usize, [f32; 4])>,
halo_scale: Vec<f32>,
halo_copies: bool,
layout_dirty: bool,
laid_out_size: f32,
laid_out_line_height: f32,
laid_out_wrap: (Option<f32>, bool),
visible: Vec<bool>,
last_view: Option<ViewKey>,
placed_generation: Option<u64>,
owner: u64,
anchors: Column,
rects: Column,
uvs: Column,
colors: Column,
states: Column,
}
impl std::fmt::Debug for TextLabels {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("TextLabels")
.field("labels", &self.labels.len())
.field("font_size", &self.font_size)
.finish()
}
}
impl Drop for TextLabels {
fn drop(&mut self) {
if let (Some(index), true) = (&self.collision_index, self.placed_generation.is_some()) {
let mut index = index.lock().unwrap_or_else(|e| e.into_inner());
index.remove_owner(self.owner);
index.invalidate();
}
}
}
impl TextLabels {
pub fn new(font: CaptionFont) -> Self {
let mut common = MarkCommon::default();
common.style.depth_test = false;
Self {
common,
fonts: vec![font],
labels: Vec::new(),
raster_size: RASTER,
glyph_field: GlyphField::Sdf,
icons: HashMap::new(),
halo_scale: Vec::new(),
halo_copies: false,
font_size: 14.0,
halo_width: 0.0,
line_height: 1.2,
halo_color: [0, 0, 0, 200],
collision: true,
padding: 2.0,
atlas: Atlas::new(RASTER, false),
atlas_gpu: None,
layout: Vec::new(),
layout_dirty: true,
laid_out_size: 0.0,
laid_out_line_height: 0.0,
laid_out_wrap: (None, false),
visible: Vec::new(),
last_view: None,
placed_generation: None,
owner: super::collision::next_owner(),
collision_index: None,
stickiness: 0.0,
reserve_scale: 1.0,
publish_visibility: None,
max_bend: 0.8,
max_width: None,
break_anywhere: false,
path_layout: Vec::new(),
anchors: Column::new(ColumnFormat::PositionF64),
rects: Column::float(4),
uvs: Column::float(4),
colors: Column::new(ColumnFormat::Unorm8x4),
states: Column::float(4),
}
}
pub fn set_labels(&mut self, labels: Vec<TextLabel>) {
self.labels = labels;
self.layout_dirty = true;
}
pub fn labels(&self) -> &[TextLabel] {
&self.labels
}
pub fn add_fallback(&mut self, font: CaptionFont) {
self.fonts.push(font);
self.reset_atlas();
}
pub fn add_icon(&mut self, name: impl Into<String>, width: u32, height: u32, alpha: &[u8]) {
assert_eq!(alpha.len(), (width * height) as usize, "one byte a pixel");
let name = name.into();
self.atlas.glyphs.remove(&GlyphKey::Icon(name.clone()));
self.icons.insert(name, (width, height, alpha.to_vec()));
self.layout_dirty = true;
}
fn reset_atlas(&mut self) {
self.atlas = Atlas::new(
self.raster_size.max(4.0),
self.glyph_field == GlyphField::Msdf,
);
self.layout_dirty = true;
}
fn font_for(&self, c: char) -> u8 {
self.fonts.iter().position(|f| f.has_glyph(c)).unwrap_or(0) as u8
}
fn wrap(&mut self, text: &str, max: f32, raster: f32) -> String {
let size = self.font_size.max(1.0);
let mut out: Vec<String> = Vec::new();
for line in text.split('\n') {
let mut current = String::new();
let mut width = 0.0f32;
let advance = |this: &mut Self, s: &str| -> f32 {
s.chars()
.map(|c| {
let f = this.font_for(c);
this.fonts[f as usize].advance(c, size) * raster / size
})
.sum()
};
let units: Vec<String> = if self.break_anywhere {
line.chars().map(String::from).collect()
} else {
let mut u = Vec::new();
for (i, w) in line.split(' ').enumerate() {
u.push(if i == 0 {
w.to_string()
} else {
format!(" {w}")
});
}
u
};
for unit in units {
let w = advance(self, &unit);
if !current.is_empty() && width + w > max {
out.push(std::mem::take(&mut current));
let unit = unit.trim_start().to_string();
width = advance(self, &unit);
current = unit;
} else {
width += w;
current.push_str(&unit);
}
}
out.push(current);
}
out.join("\n")
}
pub fn visible(&self) -> &[bool] {
&self.visible
}
fn relayout(&mut self) {
let raster = self.atlas.raster;
let s = self.font_size / raster;
let metrics = self.fonts[0].metrics(raster);
let (ascent, descent) = (metrics.ascent * s, metrics.descent * s);
if self.labels.iter().any(|l| l.background.is_some())
&& !self.atlas.glyphs.contains_key(&GlyphKey::Solid)
{
let (x, y) = self.atlas.pack(8, 8, &[[255u8; 4]; 64]);
self.atlas
.glyphs
.insert(GlyphKey::Solid, Some((x, y, 8, 8, 0, 0)));
}
let wrapped: Vec<String> = (0..self.labels.len())
.map(|li| {
let text = self.labels[li].text.clone();
match self.max_width.filter(|_| self.labels[li].path.is_none()) {
Some(w) => self.wrap(&text, w / s, raster),
None => text,
}
})
.collect();
for li in 0..self.labels.len() {
let chars: Vec<char> = self.labels[li].text.chars().collect();
for c in chars {
let f = self.font_for(c);
self.atlas.ensure(&mut self.fonts[f as usize], f, c);
}
if let Some(icon) = &self.labels[li].icon
&& let Some((w, h, alpha)) = self.icons.get(&icon.name)
{
self.atlas.ensure_icon(&icon.name, *w, *h, alpha);
}
}
let ah = self.atlas.height as f32;
let aw = ATLAS_WIDTH as f32;
let uv_of = |x: u32, y: u32, w: u32, h: u32| {
[
x as f32 / aw,
y as f32 / ah,
(x + w) as f32 / aw,
(y + h) as f32 / ah,
]
};
let mut anchors = Vec::new();
let mut rects = Vec::new();
let mut uvs = Vec::new();
let mut colors = Vec::new();
self.layout.clear();
self.path_layout.clear();
self.halo_scale.clear();
let lh = self.line_height * self.font_size;
let solid = self.atlas.glyphs.get(&GlyphKey::Solid).copied().flatten();
for (l, wrapped) in self.labels.iter().zip(&wrapped) {
let start = anchors.len();
let mut quads: Vec<Quad> = Vec::new();
let mut pen = 0.0f32;
let text: std::borrow::Cow<str> = if l.path.is_some() && wrapped.contains('\n') {
wrapped.replace('\n', " ").into()
} else {
wrapped.as_str().into()
};
let lines: Vec<&str> = text.split('\n').collect();
let extra = (lines.len() - 1) as f32 * lh;
let icon = l
.icon
.as_ref()
.filter(|_| l.path.is_none())
.and_then(|icon| {
let (iw, ih, _) = self.icons.get(&icon.name)?;
let slot = self.atlas.glyphs.get(&GlyphKey::Icon(icon.name.clone()))?;
Some((icon, *iw, *ih, (*slot)?))
});
if let Some((icon, iw, ih, (x, y, w, h, ox, oy))) = icon {
let k = icon.size / ih.max(1) as f32;
let mid = (descent - ascent + extra) * 0.5;
quads.push((
[
ox as f32 * k,
mid - icon.size * 0.5 + oy as f32 * k,
w as f32 * k,
h as f32 * k,
],
uv_of(x, y, w, h),
icon.color,
k / s,
));
pen = (iw as f32 * k + icon.gap) / s;
}
let text_start = pen;
let mut line_runs: Vec<(usize, f32)> = Vec::with_capacity(lines.len());
for (li, line) in lines.iter().enumerate() {
pen = text_start;
let first = quads.len();
let mut prev: Option<(u8, char)> = None;
for c in line.chars() {
let f = self.font_for(c);
let font = &mut self.fonts[f as usize];
let size = self.font_size.max(1.0);
if let Some((pf, p)) = prev
&& pf == f
{
pen += font.kerning(p, c, size) * raster / size;
}
if let Some(Some((x, y, w, h, ox, oy))) =
self.atlas.glyphs.get(&GlyphKey::Char(f, c)).copied()
{
quads.push((
[
(pen + ox as f32) * s,
oy as f32 * s + li as f32 * lh,
w as f32 * s,
h as f32 * s,
],
uv_of(x, y, w, h),
l.color,
1.0,
));
}
pen += font.advance(c, size) * raster / size;
prev = Some((f, c));
}
line_runs.push((first, (pen - text_start) * s));
}
let text_width = line_runs.iter().map(|r| r.1).fold(0.0f32, f32::max);
let justify = match l.anchor {
LabelAnchor::Right | LabelAnchor::BelowRight | LabelAnchor::AboveRight => 0.0,
LabelAnchor::Left | LabelAnchor::BelowLeft | LabelAnchor::AboveLeft => 1.0,
_ => 0.5,
};
for (k, &(first, w)) in line_runs.iter().enumerate() {
let end = line_runs.get(k + 1).map_or(quads.len(), |r| r.0);
let shift = (text_width - w) * justify;
for q in &mut quads[first..end] {
q.0[0] += shift;
}
}
let width = text_start * s + text_width;
let middle = (ascent - descent - extra) * 0.5;
let (dx, dy) = match l.anchor {
LabelAnchor::Center => (-width * 0.5, middle),
LabelAnchor::Right => (0.0, middle),
LabelAnchor::Left => (-width, middle),
LabelAnchor::Above => (-width * 0.5, -descent - extra),
LabelAnchor::Below => (-width * 0.5, ascent),
LabelAnchor::BelowRight => (0.0, ascent),
LabelAnchor::BelowLeft => (-width, ascent),
LabelAnchor::AboveRight => (0.0, -descent - extra),
LabelAnchor::AboveLeft => (-width, -descent - extra),
};
let em = self.font_size;
let (dx, dy) = (
dx + l.offset[0] + l.offset_em[0] * em,
dy + l.offset[1] + l.offset_em[1] * em,
);
let (mut top, mut bottom) = (dy - ascent, dy + extra + descent);
if let Some((icon, _, _, _)) = icon {
let mid = dy + (descent - ascent + extra) * 0.5;
top = top.min(mid - icon.size * 0.5);
bottom = bottom.max(mid + icon.size * 0.5);
}
let (mut left, mut right) = (dx, dx + width);
if let (Some(bg), Some((x, y, _, _, _, _)), None) = (l.background, solid, &l.path) {
let [pl, pt, pr, pb] = bg.padding;
let outer = [dx - pl, top - pt, width + pl + pr, bottom - top + pt + pb];
let uv = uv_of(x + 3, y + 3, 2, 2);
let mut boxes: Vec<Quad> = Vec::new();
let bw = bg.border_width.max(0.0);
if bw > 0.0 && bg.border_color[3] > 0 {
boxes.push((
[outer[0] - dx, outer[1] - dy, outer[2], outer[3]],
uv,
bg.border_color,
0.0,
));
}
let inner = [
outer[0] + bw,
outer[1] + bw,
(outer[2] - 2.0 * bw).max(0.0),
(outer[3] - 2.0 * bw).max(0.0),
];
boxes.push((
[inner[0] - dx, inner[1] - dy, inner[2], inner[3]],
uv,
bg.color,
0.0,
));
boxes.extend(quads);
quads = boxes;
(left, right) = (outer[0], outer[0] + outer[2]);
(top, bottom) = (outer[1], outer[1] + outer[3]);
}
if l.path.is_some() {
let mid = (ascent - descent) * 0.5;
let mut glyphs = Vec::with_capacity(quads.len());
for (r, uv, color, halo) in &quads {
let centre = r[0] + r[2] * 0.5;
glyphs.push(PathGlyph {
along: centre,
rect: [r[0] - centre, r[1] + mid, r[2], r[3]],
});
anchors.push(l.position);
rects.extend_from_slice(&[r[0] - centre, r[1] + mid, r[2], r[3]]);
uvs.extend_from_slice(uv);
colors.push(*color);
self.halo_scale.push(*halo);
}
self.path_layout.push(Some((glyphs, width)));
} else {
for (r, uv, color, halo) in quads {
anchors.push(l.position);
rects.extend_from_slice(&[r[0] + dx, r[1] + dy, r[2], r[3]]);
uvs.extend_from_slice(&uv);
colors.push(color);
self.halo_scale.push(halo);
}
self.path_layout.push(None);
}
self.layout
.push((start, anchors.len(), [left, top, right, bottom]));
}
self.halo_copies = self.halo_width > 0.0;
if self.halo_copies {
anchors.extend_from_within(..);
rects.extend_from_within(..);
uvs.extend_from_within(..);
colors.extend_from_within(..);
}
self.anchors.set_positions(&anchors);
self.rects.set_f32(&rects);
self.uvs.set_f32(&uvs);
self.colors.set_rgba(&colors);
if self.visible.len() != self.labels.len() {
self.visible = vec![true; self.labels.len()];
}
self.last_view = None;
self.layout_dirty = false;
self.laid_out_size = self.font_size;
self.laid_out_line_height = self.line_height;
self.laid_out_wrap = (self.max_width, self.break_anywhere);
}
pub fn place(&mut self, view: &MarkView) {
let mut optical = false;
for f in &mut self.fonts {
optical |= f.set_optical_size(Some(self.font_size.max(1.0)));
}
if optical
|| self.atlas.raster != self.raster_size.max(4.0)
|| self.atlas.msdf != (self.glyph_field == GlyphField::Msdf)
{
self.reset_atlas();
}
if self.layout_dirty
|| self.font_size != self.laid_out_size
|| self.line_height != self.laid_out_line_height
|| (self.max_width, self.break_anywhere) != self.laid_out_wrap
|| (self.halo_width > 0.0) != self.halo_copies
{
self.relayout();
self.last_view = None;
}
let settings = [
self.padding.to_bits(),
u32::from(self.collision),
self.stickiness.to_bits(),
self.max_bend.to_bits(),
self.reserve_scale.to_bits(),
];
let key = (
view.view_proj,
view.viewport,
view.origin.position,
settings,
);
let shared = self.collision_index.clone();
let generation = shared
.as_ref()
.map_or(0, |s| s.lock().unwrap().generation());
if self.last_view == Some(key)
&& self.states.len() == self.anchors.len()
&& Some(generation) == self.placed_generation
{
return;
}
if let Some(s) = &shared {
s.lock()
.unwrap()
.reclaim(self.owner, self.placed_generation);
}
self.last_view = Some(key);
self.placed_generation = Some(generation);
let n = self.labels.len();
let (vw, vh) = (view.viewport.0 as f32, view.viewport.1 as f32);
let was = std::mem::take(&mut self.visible);
let score = |i: usize| {
let bonus = if was.get(i).copied().unwrap_or(false) {
self.stickiness
} else {
0.0
};
self.labels[i].priority + bonus
};
let mut order: Vec<usize> = (0..n).collect();
order.sort_by(|&a, &b| {
score(b)
.partial_cmp(&score(a))
.unwrap_or(std::cmp::Ordering::Equal)
});
let mut private = super::CollisionIndex::new();
let mut shared_guard = shared.as_ref().map(|s| s.lock().unwrap());
let index: &mut super::CollisionIndex = match shared_guard.as_deref_mut() {
Some(g) => g,
None => &mut private,
};
self.visible = vec![false; n];
let pad = self.padding;
let owner = self.owner;
let mut angles = vec![0.0f32; self.anchors.len()];
let mut moved: Vec<(usize, [f64; 3])> = Vec::new();
for i in order {
if let Some((glyphs, width)) = self.path_layout.get(i).and_then(|p| p.as_ref()) {
let path = self.labels[i].path.as_deref().unwrap_or(&[]);
let start = self.layout[i].0;
let Some(placed) = place_on_path(view, path, glyphs, *width, self.max_bend) else {
continue;
};
let boxes: Vec<[f32; 4]> = placed
.iter()
.zip(glyphs)
.map(|(&(p, a, _), g)| {
let (sn, cs) = a.sin_cos();
let (hw, hh) = (g.rect[2] * 0.5, g.rect[3] * 0.5);
let c = [g.rect[0] + hw, g.rect[1] + hh];
let cx = p[0] + c[0] * cs - c[1] * sn;
let cy = p[1] + c[0] * sn + c[1] * cs;
let ex = hw * cs.abs() + hh * sn.abs() + pad;
let ey = hw * sn.abs() + hh * cs.abs() + pad;
[cx - ex, cy - ey, cx + ex, cy + ey]
})
.collect();
if boxes
.iter()
.any(|r| r[2] < 0.0 || r[3] < 0.0 || r[0] > vw || r[1] > vh)
{
continue;
}
if self.collision {
if boxes.iter().any(|r| index.collides(*r)) {
continue;
}
for r in &boxes {
index.insert_owned(owner, *r);
}
}
for (k, &(_, a, w)) in placed.iter().enumerate() {
angles[start + k] = a;
moved.push((start + k, w));
}
self.visible[i] = true;
continue;
}
let Some(p) = view.project(self.labels[i].position) else {
continue;
};
let (start, end, mut b) = self.layout[i];
if let Some(q) = self.labels[i].reserve {
let q = q.map(|v| v * self.reserve_scale);
b = if start == end {
q
} else {
[
b[0].min(q[0]),
b[1].min(q[1]),
b[2].max(q[2]),
b[3].max(q[3]),
]
};
}
let r = [
p[0] + b[0] - pad,
p[1] + b[1] - pad,
p[0] + b[2] + pad,
p[1] + b[3] + pad,
];
if r[2] < 0.0 || r[3] < 0.0 || r[0] > vw || r[1] > vh {
continue;
}
if self.collision && !index.try_insert_owned(owner, r) {
continue;
}
self.visible[i] = true;
}
drop(shared_guard);
if let Some(v) = &self.publish_visibility {
v.lock().unwrap().clone_from(&self.visible);
}
let n = self.halo_scale.len();
let copies: &[(usize, f32)] = if self.halo_copies {
&[(0, -1.0), (n, 1.0)]
} else {
&[(0, 1.0)]
};
for (row, w) in moved {
for &(at, _) in copies {
self.anchors.update_positions(at + row, &[w]);
}
}
let mut states = vec![0.0f32; self.anchors.len() * 4];
for (i, &(start, end, _)) in self.layout.iter().enumerate() {
let v = if self.visible[i] { 1.0 } else { 0.0 };
for (g, &angle) in angles.iter().enumerate().take(end).skip(start) {
for &(at, sign) in copies {
let r = (at + g) * 4;
let boxed = self.halo_scale.get(g).is_some_and(|&h| h == 0.0);
states[r] = if sign < 0.0 && boxed { 0.0 } else { v };
states[r + 1] = i as f32;
states[r + 2] = angle;
states[r + 3] = sign * self.halo_scale.get(g).copied().unwrap_or(1.0);
}
}
}
self.states.set_f32(&states);
}
}
type PlacedGlyph = ([f32; 2], f32, [f64; 3]);
fn place_on_path(
view: &MarkView,
path: &[[f64; 3]],
glyphs: &[PathGlyph],
width: f32,
max_bend: f32,
) -> Option<Vec<PlacedGlyph>> {
if path.len() < 2 || glyphs.is_empty() {
return None;
}
let mut screen: Vec<[f32; 2]> = Vec::with_capacity(path.len());
for p in path {
let s = view.project(*p)?;
screen.push([s[0], s[1]]);
}
let seg = |a: [f32; 2], b: [f32; 2]| ((b[0] - a[0]).powi(2) + (b[1] - a[1]).powi(2)).sqrt();
let mut cum = vec![0.0f32];
for w in screen.windows(2) {
cum.push(cum.last().unwrap() + seg(w[0], w[1]));
}
let total = *cum.last().unwrap();
if total < width {
return None;
}
let at = |d: f32| -> (usize, f32) {
let k = cum.partition_point(|&c| c <= d).clamp(1, screen.len() - 1) - 1;
let len = (cum[k + 1] - cum[k]).max(1e-6);
(k, ((d - cum[k]) / len).clamp(0.0, 1.0))
};
let (km, _) = at(total * 0.5);
let forward = screen[km + 1][0] >= screen[km][0];
let start = (total - width) * 0.5;
let mut out = Vec::with_capacity(glyphs.len());
let mut last: Option<f32> = None;
for g in glyphs {
let d = if forward {
start + g.along
} else {
total - start - g.along
};
let (k, t) = at(d);
let (a, b) = (screen[k], screen[k + 1]);
let p = [a[0] + (b[0] - a[0]) * t, a[1] + (b[1] - a[1]) * t];
let mut angle = (b[1] - a[1]).atan2(b[0] - a[0]);
if !forward {
angle += std::f32::consts::PI;
}
if let Some(prev) = last {
let mut turn = (angle - prev).abs() % std::f32::consts::TAU;
if turn > std::f32::consts::PI {
turn = std::f32::consts::TAU - turn;
}
if turn > max_bend {
return None;
}
}
last = Some(angle);
let (wa, wb) = (path[k], path[k + 1]);
let t = t as f64;
let world = [
wa[0] + (wb[0] - wa[0]) * t,
wa[1] + (wb[1] - wa[1]) * t,
wa[2] + (wb[2] - wa[2]) * t,
];
out.push((p, angle, world));
}
Some(out)
}
impl Mark for TextLabels {
fn kind(&self) -> MarkKind {
MarkKind::Glyph
}
fn common(&self) -> &MarkCommon {
&self.common
}
fn common_mut(&mut self) -> &mut MarkCommon {
&mut self.common
}
fn instance_count(&self) -> usize {
if self.layout_dirty {
self.labels
.iter()
.map(|l| l.text.len())
.sum::<usize>()
.min(1)
} else {
self.anchors.len()
}
}
fn kind_uniforms(&self) -> KindUniforms {
let halo = (self.halo_width.max(0.0) * self.atlas.raster / self.font_size.max(1.0))
/ (2.0 * self.atlas.spread as f32);
(
[
halo.min(0.5),
self.font_size.max(1.0),
if self.atlas.msdf { 1.0 } else { 0.0 },
0.0,
],
[2.0 * self.atlas.spread as f32, 0.0, 0.0, 0.0],
super::points::srgb_u8_to_linear(self.halo_color),
)
}
fn prepare(&mut self, ctx: &PrepareContext) {
self.place(ctx.view);
let stale = self
.atlas_gpu
.as_ref()
.is_none_or(|(h, _, _)| *h != self.atlas.height);
if stale {
let tex = ctx.device.create_texture(&wgpu::TextureDescriptor {
label: Some("threers label atlas"),
size: wgpu::Extent3d {
width: ATLAS_WIDTH,
height: self.atlas.height,
depth_or_array_layers: 1,
},
mip_level_count: 1,
sample_count: 1,
dimension: wgpu::TextureDimension::D2,
format: wgpu::TextureFormat::Rgba8Unorm,
usage: wgpu::TextureUsages::TEXTURE_BINDING | wgpu::TextureUsages::COPY_DST,
view_formats: &[],
});
let view = tex.create_view(&Default::default());
let bg = ctx.device.create_bind_group(&gpu::BindGroupDescriptor {
label: Some("threers label atlas bind group"),
layout: &ctx.resources.texture_layout,
entries: &[
gpu::BindGroupEntry {
binding: 0,
resource: gpu::BindingResource::TextureView(&view),
},
gpu::BindGroupEntry {
binding: 1,
resource: gpu::BindingResource::Sampler(&ctx.resources.linear_sampler),
},
],
});
self.atlas_gpu = Some((self.atlas.height, tex, bg));
self.atlas.dirty = true;
}
if self.atlas.dirty {
let (_, tex, _) = self.atlas_gpu.as_ref().unwrap();
ctx.queue.write_texture(
gpu::TexelCopyTextureInfo {
texture: tex,
mip_level: 0,
origin: wgpu::Origin3d::ZERO,
aspect: wgpu::TextureAspect::All,
},
&self.atlas.pixels,
wgpu::TexelCopyBufferLayout {
offset: 0,
bytes_per_row: Some(ATLAS_WIDTH * 4),
rows_per_image: Some(self.atlas.height),
},
wgpu::Extent3d {
width: ATLAS_WIDTH,
height: self.atlas.height,
depth_or_array_layers: 1,
},
);
self.atlas.dirty = false;
}
}
fn release_gpu(&mut self) {
self.atlas_gpu = None;
super::release_columns(self);
}
fn gpu_bytes(&mut self) -> u64 {
let atlas = self
.atlas_gpu
.as_ref()
.map_or(0, |(_, t, _)| t.width() as u64 * t.height() as u64 * 4);
super::column_bytes(self) + atlas
}
fn columns(&mut self) -> Vec<&mut Column> {
vec![
&mut self.anchors,
&mut self.rects,
&mut self.uvs,
&mut self.colors,
&mut self.states,
]
}
fn extra_bind_group(&self) -> Option<&gpu::BindGroup> {
self.atlas_gpu.as_ref().map(|(_, _, bg)| bg)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::marks::Origin;
fn ortho_view() -> MarkView {
let mut m = [0.0f32; 16];
m[0] = 1.0;
m[5] = 1.0;
m[10] = 1.0;
m[15] = 1.0;
MarkView {
view_proj: m,
projection_scale: 1.0,
viewport: (200, 100),
origin: Origin::ZERO,
light_direction: [0.0, 1.0, 0.0],
eye: [0.0, 0.0, 1.0, 0.0],
tone_mapping: (crate::ToneMapping::None, 1.0),
reversed_z: false,
focal_distance: 0.0,
clip_epsilon: 0.001,
subpixel_snap: None,
flip_y: false,
swiftshader_sampling: false,
swiftshader_depth: false,
scene_lights: None,
}
}
#[test]
fn distance_field_is_half_on_the_outline() {
let spread = spread_for(RASTER);
let field = distance_field(&[255; 16], 4, 4, spread);
let w = 4 + 2 * spread as usize;
let at = |x: usize, y: usize| field[y * w + x];
let c = spread as usize;
assert!(at(c + 1, c + 1) > 128, "inside is above half");
assert!(at(0, 0) < 20, "far outside is near zero");
assert!(at(c, c + 2) >= 128 && at(c - 1, c + 2) < 128);
}
#[test]
fn a_shared_index_skips_placement_while_nothing_changes() {
let index = crate::marks::CollisionIndex::new().shared();
let layer = |text: &str| {
let mut l = TextLabels::new(CaptionFont::builtin());
l.collision_index = Some(index.clone());
l.set_labels(vec![TextLabel::new([0.0, 0.0, 0.0], text)]);
l
};
let (mut a, mut b) = (layer("AAAA"), layer("BBBB"));
let view = ortho_view();
let frame = |a: &mut TextLabels, b: &mut TextLabels| {
let cleared = index.lock().unwrap().begin_frame(&view);
a.place(&view);
b.place(&view);
cleared
};
assert!(frame(&mut a, &mut b));
assert_eq!((a.visible(), b.visible()), (&[true][..], &[false][..]));
assert_eq!(index.lock().unwrap().len(), 1);
assert!(!frame(&mut a, &mut b));
assert_eq!(index.lock().unwrap().len(), 1);
a.set_labels(vec![TextLabel::new([0.0, 0.0, 0.0], "AAAAA")]);
assert!(!frame(&mut a, &mut b));
assert_eq!(a.visible(), &[true]);
assert!(frame(&mut a, &mut b));
assert_eq!((a.visible(), b.visible()), (&[true][..], &[false][..]));
a.set_labels(vec![TextLabel::new([0.8, 0.8, 0.0], "AAAA")]);
assert!(!frame(&mut a, &mut b));
assert_eq!(a.visible(), &[true]);
assert!(frame(&mut a, &mut b));
assert_eq!((a.visible(), b.visible()), (&[true][..], &[true][..]));
}
#[test]
fn a_new_font_size_lays_the_labels_out_again() {
let mut l = TextLabels::new(CaptionFont::builtin());
l.set_labels(vec![
TextLabel::new([-0.3, 0.0, 0.0], "AB"),
TextLabel::new([0.3, 0.0, 0.0], "CD"),
]);
l.place(&ortho_view());
assert_eq!(l.visible(), &[true, true]);
l.font_size = 40.0;
l.place(&ortho_view());
assert_eq!(
l.visible(),
&[true, false],
"three times the size, they overlap"
);
}
#[test]
fn overlapping_labels_keep_the_higher_priority() {
let mut l = TextLabels::new(CaptionFont::builtin());
let mut a = TextLabel::new([0.0, 0.0, 0.0], "AAAA");
a.priority = 1.0;
let mut b = TextLabel::new([0.01, 0.0, 0.0], "BBBB");
b.priority = 2.0;
let c = TextLabel::new([0.8, 0.8, 0.0], "C");
l.set_labels(vec![a, b, c]);
l.place(&ortho_view());
assert_eq!(l.visible(), &[false, true, true]);
l.collision = false;
l.last_view = None;
l.place(&ortho_view());
assert_eq!(l.visible(), &[true, true, true]);
}
#[test]
fn stickiness_keeps_a_shown_label_against_a_slightly_better_rival() {
let mut l = TextLabels::new(CaptionFont::builtin());
l.stickiness = 0.5;
let label = |x: f64, text: &str, p: f32| {
let mut t = TextLabel::new([x, 0.0, 0.0], text);
t.priority = p;
t
};
l.set_labels(vec![label(0.0, "AAAA", 1.0), label(0.01, "BBBB", 0.9)]);
l.place(&ortho_view());
assert_eq!(l.visible(), &[true, false]);
l.set_labels(vec![label(0.0, "AAAA", 1.0), label(0.01, "BBBB", 1.3)]);
l.place(&ortho_view());
assert_eq!(l.visible(), &[true, false], "sticky");
l.set_labels(vec![label(0.0, "AAAA", 1.0), label(0.01, "BBBB", 1.6)]);
l.place(&ortho_view());
assert_eq!(l.visible(), &[false, true]);
}
#[test]
fn labels_off_screen_or_behind_are_hidden() {
let mut l = TextLabels::new(CaptionFont::builtin());
l.set_labels(vec![TextLabel::new([5.0, 0.0, 0.0], "far right")]);
l.place(&ortho_view());
assert_eq!(l.visible(), &[false]);
}
#[test]
fn path_labels_follow_the_line_and_read_left_to_right() {
let glyph_xs = |l: &TextLabels| -> (Vec<f64>, Vec<f32>) {
let pos = l.anchors.positions_f64(None).unwrap();
let st: Vec<f32> = bytemuck::pod_collect_to_vec(l.states.bytes());
(
pos.iter().map(|p| p[0]).collect(),
st.chunks(4).map(|s| s[2]).collect(),
)
};
let mut l = TextLabels::new(CaptionFont::builtin());
l.font_size = 10.0;
for path in [
vec![[-0.9, 0.0, 0.0], [0.0, 0.0, 0.0], [0.9, 0.0, 0.0]],
vec![[0.9, 0.0, 0.0], [0.0, 0.0, 0.0], [-0.9, 0.0, 0.0]],
] {
l.set_labels(vec![TextLabel::along(path, "ROAD")]);
l.place(&ortho_view());
assert_eq!(l.visible(), &[true]);
let (xs, angles) = glyph_xs(&l);
assert_eq!(xs.len(), 4);
assert!(xs.windows(2).all(|w| w[1] > w[0]), "left to right: {xs:?}");
for a in angles {
let a = a.rem_euclid(std::f32::consts::TAU);
assert!(
!(1e-3..=std::f32::consts::TAU - 1e-3).contains(&a),
"upright: {a}"
);
}
}
l.set_labels(vec![TextLabel::along(
vec![[0.0, 0.9, 0.0], [0.0, -0.9, 0.0]],
"UP",
)]);
l.place(&ortho_view());
assert_eq!(l.visible(), &[true]);
let (_, angles) = glyph_xs(&l);
assert!(
(angles[0].abs() - std::f32::consts::FRAC_PI_2).abs() < 1e-3,
"{angles:?}"
);
l.set_labels(vec![TextLabel::along(
vec![[0.0, 0.0, 0.0], [0.05, 0.0, 0.0]],
"LONG NAME",
)]);
l.place(&ortho_view());
assert_eq!(l.visible(), &[false]);
l.set_labels(vec![TextLabel::along(
vec![[-0.3, 0.3, 0.0], [0.0, -0.3, 0.0], [0.3, 0.3, 0.0]],
"VVVVVVVV",
)]);
l.place(&ortho_view());
assert_eq!(
l.visible(),
&[false],
"the V bends too sharply under the text"
);
}
#[test]
fn each_glyph_row_records_its_label() {
let mut l = TextLabels::new(CaptionFont::builtin());
l.set_labels(vec![
TextLabel::new([0.0, -0.5, 0.0], "ab"),
TextLabel::new([0.0, 0.5, 0.0], "c d"),
]);
l.place(&ortho_view());
let states: Vec<f32> = bytemuck::pod_collect_to_vec(l.states.bytes());
assert_eq!(states.len(), 16);
assert_eq!(
states.chunks(4).map(|s| s[1]).collect::<Vec<_>>(),
[0.0, 0.0, 1.0, 1.0]
);
}
}