libosu 0.0.30

General-purpose osu! library.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

use crate::math::Point;

pub type P = Point<f64>;

fn subdivide(
  control_points: &[P],
  l: &mut [P],
  r: &mut [P],
  midpoints_buf: &mut [P],
) {
  let count = control_points.len();
  midpoints_buf.copy_from_slice(control_points);

  for i in 0..count {
    l[i] = midpoints_buf[0];
    r[count - i - 1] = midpoints_buf[count - i - 1];

    for j in 0..count - i - 1 {
      midpoints_buf[j] =
        (midpoints_buf[j] + midpoints_buf[j + 1]) / P::new(2.0, 2.0);
    }
  }
}

fn approximate(
  control_points: &[P],
  output: &mut Vec<P>,
  l_buf: &mut [P],
  r_buf: &mut [P],
  midpoints_buf: &mut [P],
) {
  let count = control_points.len();

  subdivide(control_points, l_buf, r_buf, midpoints_buf);

  l_buf[count..(count * 2) - 1].clone_from_slice(&r_buf[1..count]);

  output.push(control_points[0]);

  for i in 1..count - 1 {
    let index = 2 * i;
    let p =
      (l_buf[index] * P::new(2.0, 2.0) + l_buf[index - 1] + l_buf[index + 1])
        * P::new(0.25, 0.25);
    output.push(p);
  }
}

fn is_flat_enough(control_points: &[P], tolerance_sq: f64) -> bool {
  for i in 1..control_points.len() - 1 {
    if (control_points[i - 1] - control_points[i] * P::new(2.0, 2.0)
      + control_points[i + 1])
      .length_squared()
      > tolerance_sq
    {
      return false;
    }
  }

  true
}

/// The bezier algorithm as implemented by osu.
///
/// This seems to be an iterative version of [De Casteljau's algorithm][1], splitting curves in
/// half until they're "flat enough" as evaluated by [`is_flat_enough`], and then lerp'd.
///
/// [1]:
pub fn create_singlebezier(output: &mut Vec<P>, control_points: &[P]) {
  let count = control_points.len();
  const TOLERANCE: f64 = 0.25;
  const TOLERANCE_SQ: f64 = TOLERANCE * TOLERANCE;

  if count == 0 {
    return;
  }

  let mut to_flatten: Vec<Vec<P>> = Vec::new();
  let mut free_buffers: Vec<Vec<P>> = Vec::new();

  let last_control_point = control_points[count - 1];
  to_flatten.push(control_points.to_vec());

  let mut left_child = vec![P::new(0.0, 0.0); count * 2 - 1];

  let mut l_buf = vec![P::new(0.0, 0.0); count * 2 - 1];
  let mut r_buf = vec![P::new(0.0, 0.0); count];
  let mut midpoints_buf = vec![P::new(0.0, 0.0); count];

  while !to_flatten.is_empty() {
    let mut parent = to_flatten.pop().unwrap();
    if is_flat_enough(&parent, TOLERANCE_SQ) {
      approximate(
        &parent,
        output,
        &mut l_buf[..count * 2 - 1],
        &mut r_buf[..count],
        &mut midpoints_buf[..count],
      );
      free_buffers.push(parent);
      continue;
    }

    let mut right_child = free_buffers
      .pop()
      .unwrap_or_else(|| vec![P::new(0.0, 0.0); count]);

    subdivide(
      &parent,
      &mut left_child,
      &mut right_child,
      &mut midpoints_buf[..count],
    );

    // We re-use the buffer of the parent for one of the children, so that we save one allocation per iteration.
    parent[..count].clone_from_slice(&left_child[..count]);

    to_flatten.push(right_child);
    to_flatten.push(parent);
  }

  output.push(last_control_point);
}