Coverage for src/manimgx/drawing/geometry.py: 97%

1007 statements  

« prev     ^ index     » next       coverage.py v7.16.1, created at 2026-10-26 05:52 +0000

1# SPDX-FileCopyrightText: 2026 Academa, Inc. 

2# SPDX-FileCopyrightText: 2024 the Manim Community Developers 

3# SPDX-FileCopyrightText: 2018 3Blue1Brown LLC 

4# SPDX-License-Identifier: MIT 

5 

6"""Geometry as values: vectors, cubic curves, polygon queries, shapes and affine blends. 

7 

8A shape owns immutable points. A blend places shapes as Σ Mₖ·Sₖ; a path describes 

9how its coefficients change. The numerical operations here construct, query and 

10subdivide that geometry without scene objects or rendering state. 

11""" 

12 

13from __future__ import annotations 

14 

15import functools 

16import heapq 

17import itertools 

18import math 

19from collections.abc import Callable, Iterable, Sequence 

20from dataclasses import dataclass, field 

21from types import ModuleType 

22from typing import TYPE_CHECKING, Final, Literal, NamedTuple, overload 

23from warnings import deprecated 

24 

25import numpy as np 

26import numpy.typing as npt 

27 

28from manimgx._engine import digest 

29from manimgx.caches import Memo, forgets, unchanged 

30from manimgx.typing import ( 

31 MatrixMN, 

32 PathFunc, 

33 Point3D, 

34 Point3D_Array, 

35 Point3DLike, 

36 Point3DLike_Array, 

37 Vec, 

38 Vector3D, 

39 Vector3DLike, 

40) 

41 

42if TYPE_CHECKING: 

43 from pathops import Path as SkiaPath 

44 

45 from manimgx.typing import ( 

46 Point2D, 

47 Point2D_Array, 

48 Point2DLike, 

49 Point2DLike_Array, 

50 PointND, 

51 PointND_Array, 

52 ) 

53 

54 

55__all__ = [ 

56 "STRAIGHT_PATH_THRESHOLD", 

57 "Coefficients", 

58 "Floats", 

59 "Path", 

60 "QuickHull", 

61 "R3_to_complex", 

62 "Step", 

63 "angle_axis_from_quaternion", 

64 "angle_between_vectors", 

65 "angle_of_vector", 

66 "bezier", 

67 "bezier_remap", 

68 "carried", 

69 "cartesian_to_spherical", 

70 "center_of_mass", 

71 "clockwise_path", 

72 "compass_directions", 

73 "complex_func_to_R3_func", 

74 "complex_to_R3", 

75 "counterclockwise_path", 

76 "cross2d", 

77 "earclip_triangulation", 

78 "find_intersection", 

79 "get_smooth_cubic_bezier_handle_points", 

80 "get_unit_normal", 

81 "get_winding_number", 

82 "integer_interpolate", 

83 "interpolate", 

84 "inverse_interpolate", 

85 "is_closed", 

86 "line_intersection", 

87 "midpoint", 

88 "norm_squared", 

89 "normalize", 

90 "normalize_along_axis", 

91 "partial_bezier_points", 

92 "path_along_arc", 

93 "path_along_circles", 

94 "perpendicular_bisector", 

95 "polylabel", 

96 "quaternion_conjugate", 

97 "quaternion_from_angle_axis", 

98 "quaternion_mult", 

99 "regular_vertices", 

100 "rotate_vector", 

101 "rotation_about_z", 

102 "rotation_matrix", 

103 "rotation_matrix_from_quaternion", 

104 "rotation_matrix_transpose", 

105 "rotation_matrix_transpose_from_quaternion", 

106 "shoelace", 

107 "shoelace_direction", 

108 "sigmoid", 

109 "spherical_to_cartesian", 

110 "spiral_path", 

111 "straight_path", 

112 "subdivide_bezier", 

113 "thick_diagonal", 

114 "z_to_vector", 

115] 

116 

117_OUT = np.array([0.0, 0.0, 1.0]) 

118_RIGHT = np.array([1.0, 0.0, 0.0]) 

119_UP = np.array([0.0, 1.0, 0.0]) 

120_DOWN = np.array([0.0, -1.0, 0.0]) 

121 

122 

123def normalize(vect: Vector3DLike) -> Vector3D: 

124 """The unit vector in a vector's direction. 

125 

126 Args: 

127 vect: The vector. 

128 

129 Returns: 

130 The vector divided by its length; the zero vector stays zero. 

131 """ 

132 v = np.asarray(vect, dtype=float) 

133 norm = np.linalg.norm(v) 

134 return v / norm if norm > 0 else np.zeros(len(v)) 

135 

136 

137def rotation_matrix(angle: float, axis: Vector3DLike = _OUT) -> MatrixMN: 

138 """The matrix of a rotation about an axis through the origin. 

139 

140 Raises ValueError for a zero axis: a turn about no axis is no turn at all. 

141 

142 Args: 

143 angle: The angle, in radians, counterclockwise as seen from the tip of `axis`. 

144 axis: The axis's direction (its length does not matter). 

145 

146 Returns: 

147 The 3×3 rotation matrix. 

148 """ 

149 # Rodrigues' formula; identical to scipy's 

150 # `Rotation.from_rotvec(angle * axis).as_matrix()` 

151 x, y, z = normalize(axis) 

152 if x == y == z == 0: 

153 raise ValueError(f"a rotation's axis must not be zero, not {axis}") 

154 c, s = np.cos(angle), np.sin(angle) 

155 C = 1 - c 

156 return np.array( 

157 [ 

158 [c + x * x * C, x * y * C - z * s, x * z * C + y * s], 

159 [y * x * C + z * s, c + y * y * C, y * z * C - x * s], 

160 [z * x * C - y * s, z * y * C + x * s, c + z * z * C], 

161 ] 

162 ) 

163 

164 

165@deprecated("Manim CE's machinery: ManimGX calls it itself", category=None) 

166def rotation_about_z(angle: float) -> MatrixMN: 

167 """The matrix of a rotation about the z axis. 

168 

169 Args: 

170 angle: The angle, in radians, counterclockwise. 

171 

172 Returns: 

173 The 3×3 rotation matrix. 

174 """ 

175 c, s = np.cos(angle), np.sin(angle) 

176 return np.array([[c, -s, 0], [s, c, 0], [0, 0, 1]]) 

177 

178 

179def rotate_vector( 

180 vector: Vector3DLike, angle: float, axis: Vector3DLike = _OUT 

181) -> Vector3D: 

182 """A vector rotated about an axis through the origin. 

183 

184 Args: 

185 vector: The vector; a two-dimensional one gets a z of 0. 

186 angle: The angle, in radians, counterclockwise as seen from the tip of `axis`. 

187 axis: The axis's direction. 

188 

189 Returns: 

190 The rotated vector. 

191 """ 

192 v = np.asarray(vector, dtype=float) 

193 if len(v) == 2: 

194 v = np.append(v, 0) 

195 return rotation_matrix(angle, axis) @ v 

196 

197 

198@deprecated("Manim CE's machinery: ManimGX calls it itself", category=None) 

199def z_to_vector(vector: Vector3DLike) -> MatrixMN: 

200 """A rotation that takes the z axis to a vector's direction. 

201 

202 Args: 

203 vector: The direction. 

204 

205 Returns: 

206 The 3×3 rotation matrix, whose columns are where the x, y and z axes go. 

207 """ 

208 axis_z = normalize(vector) 

209 axis_y = normalize(np.cross(axis_z, _RIGHT)) 

210 axis_x = np.cross(axis_y, axis_z) 

211 if np.linalg.norm(axis_y) == 0: 

212 axis_x = normalize(np.cross(_UP, axis_z)) 

213 axis_y = -np.cross(axis_x, axis_z) 

214 return np.array([axis_x, axis_y, axis_z]).T 

215 

216 

217def angle_of_vector(vector: Vector3DLike) -> float: 

218 """The angle of a vector in the xy plane, counterclockwise from the x axis (its z is 

219 ignored). 

220 

221 Returns: 

222 The angle, in radians, from −π to π. 

223 """ 

224 v = np.asarray(vector) 

225 return float(np.angle(complex(v[0], v[1]))) 

226 

227 

228def angle_between_vectors(v1: Vector3DLike, v2: Vector3DLike) -> float: 

229 """The angle between two vectors. 

230 

231 Args: 

232 v1: A vector. 

233 v2: Another vector. 

234 

235 Returns: 

236 The angle, in radians, from 0 to π. 

237 """ 

238 a, b = normalize(v1), normalize(v2) 

239 return float(2 * np.arctan2(np.linalg.norm(a - b), np.linalg.norm(a + b))) 

240 

241 

242def turn_between(v1: Vector3DLike, v2: Vector3DLike) -> tuple[float, Vector3D]: 

243 """The smallest turn taking one direction to another, as (angle, axis). 

244 

245 The axis is perpendicular to both; for directions along one line (a half turn, or 

246 none), it is the part of OUT across them, so a half turn in the plane of the screen 

247 stays in it, or RIGHT for directions along OUT. 

248 

249 Args: 

250 v1: The direction turned. 

251 v2: The direction it is turned to. 

252 

253 Returns: 

254 The angle, from 0 to π, and the unit axis. 

255 """ 

256 a, b = np.asarray(v1, dtype=float), np.asarray(v2, dtype=float) 

257 cross = np.cross(a, b) 

258 norm = np.linalg.norm(cross) 

259 if norm > 0: 

260 return angle_between_vectors(a, b), cross / norm 

261 across = _OUT - (_OUT @ a) / max(float(a @ a), 1e-300) * a 

262 size = np.linalg.norm(across) 

263 return angle_between_vectors(a, b), ( 

264 across / size if size > 1e-9 else _RIGHT.copy() 

265 ) 

266 

267 

268@deprecated("Manim CE's machinery: ManimGX calls it itself", category=None) 

269def get_unit_normal(v1: Vector3DLike, v2: Vector3DLike, tol: float = 1e-6) -> Vector3D: 

270 """A unit vector perpendicular to two vectors: their cross product, normalized. 

271 

272 For vectors along one line (or a zero vector), it is the part of the z axis 

273 perpendicular to them, normalized; [DOWN][manimgx.DOWN] if they lie along the z axis 

274 or are both zero. 

275 

276 Args: 

277 v1: A vector. 

278 v2: Another vector. 

279 tol: How small, relative to the vectors, a cross product counts as zero. 

280 

281 Returns: 

282 The unit vector. 

283 """ 

284 a, b = np.asarray(v1, dtype=float), np.asarray(v2, dtype=float) 

285 d1, d2 = max(np.abs(a)), max(np.abs(b)) 

286 if d1 == 0.0: 

287 if d2 == 0.0: 

288 return _DOWN.copy() 

289 u = b / d2 

290 elif d2 == 0.0: 

291 u = a / d1 

292 else: 

293 cp = np.cross(a / d1, b / d2) 

294 n = np.linalg.norm(cp) 

295 if n > tol: 

296 return cp / n 

297 u = a / d1 

298 if abs(u[0]) < tol and abs(u[1]) < tol: 

299 return _DOWN.copy() 

300 cp = np.array([-u[0] * u[2], -u[1] * u[2], u[0] * u[0] + u[1] * u[1]]) 

301 return cp / np.linalg.norm(cp) 

302 

303 

304@deprecated("Manim CE's machinery: ManimGX calls it itself", category=None) 

305def compass_directions(n: int = 4, start_vect: Vector3DLike = _RIGHT) -> Point3D_Array: 

306 """Vectors evenly spread around the z axis, counterclockwise from a first one. 

307 

308 Args: 

309 n: How many vectors. 

310 start_vect: The first vector. 

311 

312 Returns: 

313 The vectors, as an (n, 3) array. 

314 """ 

315 angles = np.arange(n) * (2 * np.pi / n) 

316 vector = np.asarray(start_vect, dtype=float) 

317 x, y, z = np.append(vector, 0) if len(vector) == 2 else vector 

318 c, s = np.cos(angles), np.sin(angles) 

319 # Matrix reductions start from +0.0; retain those zero signs in shape keys. 

320 return ( 

321 np.column_stack([x * c - y * s, x * s + y * c, np.full(len(angles), z)]) + 0.0 

322 ) 

323 

324 

325@deprecated("Manim CE's machinery: ManimGX calls it itself", category=None) 

326def regular_vertices( 

327 n: int, *, radius: float = 1, start_angle: float | None = None 

328) -> tuple[Point3D_Array, float]: 

329 """The vertices of a regular polygon centered at the origin, counterclockwise. 

330 

331 Args: 

332 n: How many vertices. 

333 radius: How far they are from the center, in scene units. 

334 start_angle: The first vertex's angle, in radians, counterclockwise from the x 

335 axis; None for 0 when `n` is even and π/2 (a vertex on top) when it is odd. 

336 

337 Returns: 

338 The vertices, as an (n, 3) array, and the first vertex's angle. 

339 """ 

340 if start_angle is None: 

341 start_angle = 0 if n % 2 == 0 else np.pi / 2 

342 vertices = compass_directions(n, rotate_vector(_RIGHT * radius, start_angle)) 

343 return vertices, start_angle 

344 

345 

346def line_intersection(line1: Point3DLike_Array, line2: Point3DLike_Array) -> Point3D: 

347 """Where two lines in the xy plane cross, each line through two points (their z is 

348 ignored). 

349 

350 Raises an exception if the lines are parallel. 

351 

352 Args: 

353 line1: Two points on the first line. 

354 line2: Two points on the second line. 

355 

356 Returns: 

357 The point, with a z of 0. 

358 """ 

359 padded = [ 

360 np.pad(np.array(line)[:, :2], ((0, 0), (0, 1)), constant_values=1) 

361 for line in (line1, line2) 

362 ] 

363 l1, l2 = (np.cross(*p) for p in padded) 

364 x, y, z = np.cross(l1, l2) 

365 if z == 0: 

366 raise ValueError( 

367 "The lines are parallel, there is no unique intersection point." 

368 ) 

369 return np.array([x / z, y / z, 0]) 

370 

371 

372@deprecated("Manim CE's machinery: ManimGX calls it itself", category=None) 

373def find_intersection( 

374 p0s: Point3DLike_Array, 

375 v0s: Point3DLike_Array, 

376 p1s: Point3DLike_Array, 

377 v1s: Point3DLike_Array, 

378 threshold: float = 1e-5, 

379) -> list[Point3D]: 

380 """For each pair of lines, the point of the first nearest the second: where they 

381 cross, if they do. 

382 

383 The first line of each pair is `p0 + t·v0`, the second `p1 + s·v1`. 

384 

385 Args: 

386 p0s: A point on each first line. 

387 v0s: Each first line's direction. 

388 p1s: A point on each second line. 

389 v1s: Each second line's direction. 

390 threshold: The least the division is by, so that parallel lines give `p0` 

391 rather than divide by zero. 

392 

393 Returns: 

394 One point per pair. 

395 """ 

396 result = [] 

397 arrays = (np.asarray(a, dtype=float) for a in (p0s, v0s, p1s, v1s)) 

398 for p0, v0, p1, v1 in zip(*arrays, strict=True): 

399 normal = np.cross(v1, np.cross(v0, v1)) 

400 denom = max(np.dot(v0, normal), threshold) 

401 result.append(p0 + np.dot(p1 - p0, normal) / denom * v0) 

402 return result 

403 

404 

405def midpoint(p1: Point3DLike, p2: Point3DLike) -> Point3D: 

406 """The point halfway between two points. 

407 

408 Args: 

409 p1: A point. 

410 p2: Another point. 

411 

412 Returns: 

413 The point between them. 

414 """ 

415 return (np.asarray(p1) + np.asarray(p2)) / 2 

416 

417 

418def cartesian_to_spherical(vec: Vector3DLike) -> Vec: 

419 """A vector's spherical coordinates. 

420 

421 Args: 

422 vec: The vector. 

423 

424 Returns: 

425 Its length r, its azimuth θ (the angle of its xy part from the x axis, from −π 

426 to π) and its polar angle φ (from the z axis, from 0 to π); zeros for the zero 

427 vector. 

428 """ 

429 v = np.asarray(vec, dtype=float) 

430 r = np.linalg.norm(v) 

431 if r == 0: 

432 return np.zeros(3) 

433 # the polar angle by its tangent: arccos(z / r) loses digits near the poles 

434 return np.array([r, np.arctan2(v[1], v[0]), np.arctan2(np.hypot(v[0], v[1]), v[2])]) 

435 

436 

437def spherical_to_cartesian(spherical: np.ndarray) -> Vector3D: 

438 """The vector of spherical coordinates (see 

439 [cartesian_to_spherical][manimgx.cartesian_to_spherical]). 

440 

441 Args: 

442 spherical: The length r, the azimuth θ and the polar angle φ, in radians. 

443 

444 Returns: 

445 The vector (r cos θ sin φ, r sin θ sin φ, r cos φ). 

446 """ 

447 r, theta, phi = spherical 

448 return np.array( 

449 [ 

450 r * np.cos(theta) * np.sin(phi), 

451 r * np.sin(theta) * np.sin(phi), 

452 r * np.cos(phi), 

453 ] 

454 ) 

455 

456 

457@deprecated("Manim CE's machinery: ManimGX calls it itself", category=None) 

458def shoelace(xy: np.ndarray) -> float: 

459 """The signed area of the polygon through points in turn, back to the first: the 

460 integral of y dx around it. 

461 

462 It is positive if the polygon runs clockwise, negative if counterclockwise. A 

463 polygon given closed, its first point repeated last, has the same area. 

464 

465 Args: 

466 xy: The polygon's vertices, x and y first in each row. 

467 

468 Returns: 

469 The signed area, in square scene units. 

470 """ 

471 x, y = xy[:, 0], xy[:, 1] 

472 return float((np.roll(x, -1) - x) @ (np.roll(y, -1) + y) / 2) 

473 

474 

475@deprecated("Manim CE's machinery: ManimGX calls it itself", category=None) 

476def shoelace_direction(xy: np.ndarray) -> str: 

477 """Which way a polygon runs around: "CW" (clockwise) if its 

478 [shoelace][manimgx.shoelace] area is positive, "CCW" (counterclockwise) otherwise. 

479 

480 Args: 

481 xy: The polygon's vertices, x and y first in each row. 

482 

483 Returns: 

484 "CW" or "CCW". 

485 """ 

486 return "CW" if shoelace(xy) > 0 else "CCW" 

487 

488 

489def perpendicular_bisector( 

490 line: Point3DLike_Array, norm_vector: Vector3DLike = _OUT 

491) -> Point3D_Array: 

492 """Two points on the perpendicular bisector of a segment, in the plane perpendicular 

493 to a vector. 

494 

495 Args: 

496 line: The segment's two ends. 

497 norm_vector: The normal of the plane the bisector lies in. 

498 

499 Returns: 

500 The segment's midpoint plus and minus its direction crossed with 

501 `norm_vector`; for a unit normal, each a segment's length from the midpoint. 

502 """ 

503 p1, p2 = np.asarray(line[0]), np.asarray(line[1]) 

504 direction = np.cross(p1 - p2, np.asarray(norm_vector)) 

505 m = midpoint(p1, p2) 

506 return np.array([m + direction, m - direction]) 

507 

508 

509@deprecated("Manim CE's machinery: ManimGX calls it itself", category=None) 

510def cross2d(a: np.ndarray, b: np.ndarray) -> npt.NDArray[np.float64] | float: 

511 """The z of the cross product of vectors in the xy plane: `a.x·b.y − a.y·b.x`. 

512 

513 Args: 

514 a: A vector, or an (n, 2) array of them. 

515 b: Another, or as many. 

516 

517 Returns: 

518 The number, or one per row. 

519 """ 

520 if len(a.shape) == 2: 

521 return a[:, 0] * b[:, 1] - a[:, 1] * b[:, 0] 

522 return a[0] * b[1] - b[0] * a[1] 

523 

524 

525@deprecated("use numpy: np.mean(points, axis=0)", category=None) 

526def center_of_mass(points: Point3DLike_Array) -> Point3D: 

527 """The average of points. 

528 

529 Returns: 

530 Their mean. 

531 """ 

532 return np.average(np.asarray(points), 0) 

533 

534 

535@deprecated("Manim CE's machinery: ManimGX calls it itself", category=None) 

536def angle_axis_from_quaternion(quaternion: np.ndarray) -> tuple[float, Vector3D]: 

537 """The angle and axis of a unit quaternion (w, x, y, z): the angle 2·arccos(w), 

538 taken from 2π when it is larger than π, and the axis (x, y, z), normalized. 

539 

540 Args: 

541 quaternion: The unit quaternion. 

542 

543 Returns: 

544 The angle, in radians, from 0 to π, and the axis. 

545 """ 

546 axis = normalize(quaternion[1:]) 

547 angle = 2 * np.arccos(quaternion[0]) 

548 if angle > np.pi: 

549 angle = 2 * np.pi - angle 

550 return angle, axis 

551 

552 

553@deprecated("use numpy: 1 / (1 + np.exp(-x))", category=None) 

554def sigmoid(x: float) -> float: 

555 """The logistic function, 1 / (1 + e^(−x)): from 0 to 1, 1/2 at 0. 

556 

557 Args: 

558 x: The number. 

559 """ 

560 return 1.0 / (1 + np.exp(-x)) 

561 

562 

563def complex_to_R3(complex_num: complex) -> Vec: 

564 """The point of a complex number: its real part as x, its imaginary part as y. 

565 

566 Args: 

567 complex_num: The number. 

568 

569 Returns: 

570 The point, with a z of 0. 

571 """ 

572 return np.array((complex_num.real, complex_num.imag, 0)) 

573 

574 

575def R3_to_complex(point: Point3D) -> complex: 

576 """The complex number of a point: x + iy (its z is ignored).""" 

577 return complex(*point[:2]) 

578 

579 

580def complex_func_to_R3_func( 

581 complex_func: Callable[[complex], complex], 

582) -> Callable[[Point3D], Point3D]: 

583 """A function of complex numbers as a function of points: a point (x, y, z) goes 

584 where the function sends x + iy, with a z of 0. 

585 

586 Args: 

587 complex_func: The function of complex numbers. 

588 

589 Returns: 

590 The function of points. 

591 """ 

592 return lambda p: complex_to_R3(complex_func(R3_to_complex(p))) 

593 

594 

595@deprecated("Manim CE's machinery: ManimGX calls it itself", category=None) 

596def norm_squared(v: Vector3DLike) -> float: 

597 """A vector's length, squared. 

598 

599 Args: 

600 v: The vector. 

601 

602 Returns: 

603 The sum of the squares of its coordinates. 

604 """ 

605 v = np.asarray(v) 

606 return float(np.dot(v, v)) 

607 

608 

609@deprecated("Manim CE's machinery: ManimGX calls it itself", category=None) 

610def rotation_matrix_transpose(angle: float, axis: Vector3DLike) -> MatrixMN: 

611 """The transpose of [rotation_matrix][manimgx.rotation_matrix]: the rotation by 

612 `-angle`. 

613 

614 Args: 

615 angle: The angle, in radians. 

616 axis: The axis's direction. 

617 

618 Returns: 

619 The 3×3 matrix. 

620 """ 

621 return rotation_matrix(angle, axis).T 

622 

623 

624@deprecated("Manim CE's machinery: ManimGX calls it itself", category=None) 

625def rotation_matrix_from_quaternion(quat: np.ndarray) -> MatrixMN: 

626 """The matrix of the rotation by a unit quaternion. 

627 

628 Args: 

629 quat: The unit quaternion (w, x, y, z). 

630 

631 Returns: 

632 The 3×3 rotation matrix. 

633 """ 

634 w, x, y, z = quat 

635 return np.array( 

636 [ 

637 [1 - 2 * (y * y + z * z), 2 * (x * y - w * z), 2 * (x * z + w * y)], 

638 [2 * (x * y + w * z), 1 - 2 * (x * x + z * z), 2 * (y * z - w * x)], 

639 [2 * (x * z - w * y), 2 * (y * z + w * x), 1 - 2 * (x * x + y * y)], 

640 ] 

641 ) 

642 

643 

644@deprecated("Manim CE's machinery: ManimGX calls it itself", category=None) 

645def get_winding_number(points: Point3DLike_Array) -> float: 

646 """How many times the closed polygon through points winds counterclockwise around 

647 the origin, in the xy plane. 

648 

649 Args: 

650 points: The polygon's vertices, in order; it closes from the last back to the 

651 first. 

652 

653 Returns: 

654 The number of turns, negative for clockwise, and whole unless a side passes 

655 through the origin. 

656 """ 

657 total = 0.0 

658 pts = np.asarray(points, dtype=float) 

659 for p1, p2 in zip(pts, np.roll(pts, -1, axis=0), strict=True): 

660 d_angle = angle_of_vector(p2) - angle_of_vector(p1) 

661 d_angle = ((d_angle + np.pi) % (2 * np.pi)) - np.pi 

662 total += d_angle 

663 return total / (2 * np.pi) 

664 

665 

666@deprecated("Manim CE's machinery: ManimGX calls it itself", category=None) 

667def quaternion_mult(*quats: Sequence[float] | npt.NDArray[np.float64]) -> list[float]: 

668 """The product of quaternions (w, x, y, z), in order: the first times the second, 

669 and so on. 

670 

671 Args: 

672 *quats: The quaternions. 

673 

674 Returns: 

675 The product as a list of four floats; (1, 0, 0, 0) for none. 

676 """ 

677 result = [float(x) for x in quats[0]] if quats else [1.0, 0.0, 0.0, 0.0] 

678 for quat in quats[1:]: 

679 (w1, x1, y1, z1), (w2, x2, y2, z2) = result, (float(x) for x in quat) 

680 result = [ 

681 w1 * w2 - x1 * x2 - y1 * y2 - z1 * z2, 

682 w1 * x2 + x1 * w2 + y1 * z2 - z1 * y2, 

683 w1 * y2 + y1 * w2 + z1 * x2 - x1 * z2, 

684 w1 * z2 + z1 * w2 + x1 * y2 - y1 * x2, 

685 ] 

686 return result 

687 

688 

689@deprecated("Manim CE's machinery: ManimGX calls it itself", category=None) 

690def quaternion_from_angle_axis( 

691 angle: float, axis: np.ndarray, axis_normalized: bool = False 

692) -> list[float]: 

693 """The unit quaternion (w, x, y, z) of a rotation about an axis. 

694 

695 Raises ValueError for a zero axis: a turn about no axis is no turn at all. 

696 

697 Args: 

698 angle: The angle, in radians. 

699 axis: The axis's direction. 

700 axis_normalized: Whether `axis` has length 1 already. 

701 

702 Returns: 

703 The quaternion, cos(angle/2) followed by the axis times sin(angle/2). 

704 """ 

705 unit = axis if axis_normalized else normalize(axis) 

706 if not np.any(unit): 

707 raise ValueError(f"a rotation's axis must not be zero, not {axis}") 

708 return [np.cos(angle / 2), *np.sin(angle / 2) * unit] 

709 

710 

711@deprecated("Manim CE's machinery: ManimGX calls it itself", category=None) 

712def quaternion_conjugate( 

713 quaternion: Sequence[float] | npt.NDArray[np.float64], 

714) -> Vec: 

715 """A quaternion's conjugate: (w, −x, −y, −z), the inverse rotation of a unit one. 

716 

717 Args: 

718 quaternion: The quaternion (w, x, y, z). 

719 """ 

720 result = np.array(quaternion, dtype=float) 

721 result[1:] *= -1 

722 return result 

723 

724 

725@deprecated("Manim CE's machinery: ManimGX calls it itself", category=None) 

726def rotation_matrix_transpose_from_quaternion(quat: np.ndarray) -> list[Vec]: 

727 """The transpose of the matrix of the rotation by a unit quaternion: its rows are 

728 where the x, y and z axes go. 

729 

730 Args: 

731 quat: The unit quaternion (w, x, y, z). 

732 

733 Returns: 

734 The three rows. 

735 """ 

736 inverse = quaternion_conjugate(quat) 

737 return [ 

738 np.array(quaternion_mult(quat, [0, *basis], inverse)[1:]) 

739 for basis in np.identity(3) 

740 ] 

741 

742 

743@deprecated("Manim CE's machinery: ManimGX calls it itself", category=None) 

744def thick_diagonal(dim: int, thickness: int = 2) -> npt.NDArray[np.uint8]: 

745 """A square matrix of ones in a band along its diagonal, and zeros elsewhere. 

746 

747 Args: 

748 dim: How many rows and columns. 

749 thickness: The band's width: ones where the row and column differ by less. 

750 

751 Returns: 

752 The matrix, of 8-bit integers. 

753 """ 

754 rows = np.arange(dim).repeat(dim).reshape((dim, dim)) 

755 return (np.abs(rows - rows.T) < thickness).astype("uint8") 

756 

757 

758@deprecated("Manim CE's machinery: ManimGX calls it itself", category=None) 

759def normalize_along_axis(array: np.ndarray, axis: int) -> npt.NDArray[np.float64]: 

760 """Divide the vectors along an array's last axis by their lengths, in place (zero 

761 vectors are left as they are). 

762 

763 Args: 

764 array: The array, of floats. 

765 axis: Its last axis (along another, the lengths are not matched to their 

766 vectors). 

767 

768 Returns: 

769 The same array. 

770 """ 

771 norms = np.sqrt((array * array).sum(axis)) 

772 norms[norms == 0] = 1 

773 array /= np.repeat(norms, array.shape[axis]).reshape(array.shape) 

774 return array 

775 

776 

777@deprecated("Manim CE's machinery: ManimGX calls it itself", category=None) 

778def earclip_triangulation( 

779 verts: Point3DLike_Array, ring_ends: Sequence[int] 

780) -> list[int]: 

781 """Triangles covering a polygon with holes, by ear clipping. 

782 

783 Each hole is joined to the outline at their closest vertices, and ears are then 

784 clipped from the one ring, in order. 

785 

786 Args: 

787 verts: The rings' vertices, one ring after another: the outline, then the holes 

788 (x and y count). 

789 ring_ends: Where each ring ends in `verts`: the index after its last vertex. 

790 

791 Returns: 

792 The triangles, as indices into `verts`, three per triangle. 

793 """ 

794 points = np.asarray(verts, dtype=float)[:, :2] 

795 rings = [ 

796 list(range(a, b)) for a, b in zip([0, *ring_ends[:-1]], ring_ends, strict=True) 

797 ] 

798 

799 def area(ring: list[int]) -> float: # signed: positive counterclockwise 

800 x, y = points[ring].T 

801 return float(np.sum(x * np.roll(y, -1) - np.roll(x, -1) * y) / 2) 

802 

803 def cross(o: int, a: int, b: int) -> float: 

804 (ax, ay), (bx, by) = points[a] - points[o], points[b] - points[o] 

805 return float(ax * by - ay * bx) 

806 

807 outline = rings[0] 

808 for hole in rings[1:]: 

809 if np.sign(area(hole)) == np.sign(area(outline)): 

810 hole = hole[ 

811 ::-1 

812 ] # a hole winds against its outline, or the bridged ring crosses itself 

813 gaps = np.linalg.norm(points[outline][:, None] - points[hole][None], axis=2) 

814 i, j = np.unravel_index(int(np.argmin(gaps)), gaps.shape) 

815 outline = outline[: i + 1] + hole[j:] + hole[: j + 1] + outline[i:] 

816 turn = np.sign(area(outline)) or 1.0 

817 ring, triangles = list(outline), [] 

818 while len(ring) > 3: 

819 for k in range(len(ring)): 

820 a, b, c = ring[k - 1], ring[k], ring[(k + 1) % len(ring)] 

821 if cross(a, b, c) * turn > 0 and not any( 

822 cross(a, b, q) * turn >= 0 

823 and cross(b, c, q) * turn >= 0 

824 and cross(c, a, q) * turn >= 0 

825 for q in ring 

826 if not any(np.allclose(points[q], points[v]) for v in (a, b, c)) 

827 ): 

828 break 

829 else: 

830 k = 1 # no proper ear (degenerate input): clip anyway rather than loop forever 

831 a, b, c = ring[0], ring[1], ring[2] 

832 triangles += [a, b, c] 

833 del ring[k] 

834 return triangles + ring 

835 

836 

837class Polygon: 

838 """A polygon with holes, as [polylabel][manimgx.polylabel] reads it: its edges, its 

839 area and its centroid. 

840 

841 Args: 

842 rings: Its rings, each closed (its first vertex repeated at its end): the 

843 outline, then any holes. 

844 """ 

845 

846 def __init__(self, rings: Sequence[Point2DLike_Array]) -> None: 

847 np_rings: list[Point2D_Array] = [np.asarray(ring) for ring in rings] 

848 csum = np.cumsum([ring.shape[0] for ring in np_rings]) 

849 self.array: Point2D_Array = np.concatenate(np_rings, axis=0) 

850 self.start: Point2D_Array = np.delete(self.array, csum - 1, axis=0) 

851 self.stop: Point2D_Array = np.delete(self.array, csum % csum[-1], axis=0) 

852 self.diff: Point2D_Array = np.delete( 

853 np.diff(self.array, axis=0), csum[:-1] - 1, axis=0 

854 ) 

855 self.norm: Point2D_Array = self.diff / np.einsum( 

856 "ij,ij->i", self.diff, self.diff 

857 ).reshape(-1, 1) 

858 x, y = (self.start[:, 0], self.start[:, 1]) 

859 xr, yr = (self.stop[:, 0], self.stop[:, 1]) 

860 self.area: float = 0.5 * (np.dot(x, yr) - np.dot(xr, y)) 

861 if self.area: 

862 factor = x * yr - xr * y 

863 cx = np.sum((x + xr) * factor) / (6.0 * self.area) 

864 cy = np.sum((y + yr) * factor) / (6.0 * self.area) 

865 self.centroid = np.array([cx, cy]) 

866 

867 def compute_distance(self, point: Point2DLike) -> float: 

868 """How far a point is from the polygon's edges: positive inside, negative 

869 outside. 

870 

871 Args: 

872 point: The point, x and y. 

873 

874 Returns: 

875 The distance, in scene units. 

876 """ 

877 scalars = np.einsum("ij,ij->i", self.norm, point - self.start) 

878 clips = np.clip(scalars, 0, 1).reshape(-1, 1) 

879 d: float = np.min( 

880 np.linalg.norm(self.start + self.diff * clips - point, axis=1) 

881 ) 

882 return d if self.inside(point) else -d 

883 

884 def inside(self, point: Point2DLike) -> bool: 

885 """Whether a point is inside the polygon or on its edges: a ray from it toward 

886 +x crosses the edges an odd number of times. 

887 

888 Args: 

889 point: The point, x and y. 

890 """ 

891 x, y = point 

892 x0, y0 = self.start[:, 0], self.start[:, 1] 

893 x1, y1 = self.stop[:, 0], self.stop[:, 1] 

894 on = ( 

895 (np.minimum(x0, x1) <= x) 

896 & (x <= np.maximum(x0, x1)) 

897 & (np.minimum(y0, y1) <= y) 

898 & (y <= np.maximum(y0, y1)) 

899 & (np.abs((x1 - x0) * (y - y0) - (y1 - y0) * (x - x0)) <= 1e-8) 

900 ) 

901 if on.any(): 

902 return True 

903 with np.errstate(divide="ignore", invalid="ignore"): 

904 crossed = ((y0 > y) != (y1 > y)) & ( 

905 x < (x1 - x0) / (y1 - y0) * (y - y0) + x0 

906 ) 

907 return bool(np.count_nonzero(crossed) % 2) 

908 

909 

910class Cell: 

911 """A square cell of the search [polylabel][manimgx.polylabel] makes: its center `c`, 

912 its half-size `h`, its center's distance `d` from the polygon's edges, and `p`, the 

913 most any point of the cell can be from them. 

914 Cells are ordered for the search by decreasing `p`. 

915 

916 Args: 

917 c: Its center, x and y. 

918 h: Half its side, in scene units. 

919 """ 

920 

921 def __init__(self, c: Point2DLike, h: float, polygon: Polygon) -> None: 

922 self.c: Point2D = np.asarray(c) 

923 self.h = h 

924 self.d = polygon.compute_distance(self.c) 

925 self.p = self.d + self.h * np.sqrt(2) 

926 

927 def __lt__(self, other: Cell) -> bool: 

928 return self.p > other.p 

929 

930 

931def polylabel(rings: Sequence[Point3DLike_Array], precision: float = 0.01) -> Cell: 

932 """The pole of inaccessibility of a polygon: the point inside it farthest from its 

933 edges, where a label fits best. 

934 

935 Args: 

936 rings: The polygon's rings, each closed (its first vertex repeated at its end): 

937 the outline, then any holes. Their x and y count. 

938 precision: How far, at most, the point found may be from the best, in its 

939 distance from the edges, in scene units. 

940 

941 Returns: 

942 The cell found, whose `c` is the point (x and y) and `d` its distance from the 

943 nearest edge. 

944 """ 

945 np_rings: list[Point2D_Array] = [np.asarray(ring)[:, :2] for ring in rings] 

946 polygon = Polygon(np_rings) 

947 mins = np.min(polygon.array, axis=0) 

948 maxs = np.max(polygon.array, axis=0) 

949 dims = maxs - mins 

950 s = np.min(dims) 

951 h = s / 2.0 

952 queue: list[Cell] = [] 

953 xv, yv = np.meshgrid(np.arange(mins[0], maxs[0], s), np.arange(mins[1], maxs[1], s)) 

954 for corner in np.vstack([xv.ravel(), yv.ravel()]).T: 

955 heapq.heappush(queue, Cell(corner + h, h, polygon)) 

956 best = Cell(polygon.centroid, 0, polygon) 

957 bbox = Cell(mins + dims / 2, 0, polygon) 

958 if bbox.d > best.d: 

959 best = bbox 

960 # No inscribed circle is wider than the bounding box. 

961 if best.d >= h: 

962 return best 

963 directions = np.array([[-1, -1], [1, -1], [-1, 1], [1, 1]]) 

964 while queue: 

965 cell = heapq.heappop(queue) 

966 if cell.d > best.d: 

967 best = cell 

968 if cell.p - best.d > precision: 

969 h = cell.h / 2.0 

970 offsets = cell.c + directions * h 

971 for offset in offsets: 

972 heapq.heappush(queue, Cell(offset, h, polygon)) 

973 return best 

974 

975 

976class SubFacet: 

977 """A face of a facet (an end of an edge, an edge of a triangle), equal to another of 

978 the same points. Its topology identity captures those coordinates at construction. 

979 """ 

980 

981 def __init__(self, coordinates: PointND_Array) -> None: 

982 self.coordinates = coordinates 

983 # Numeric tuples keep topology hashes independent of Python's byte-hash seed. 

984 self.points = frozenset(tuple(c.tolist()) for c in coordinates) 

985 

986 def __hash__(self) -> int: 

987 return hash(self.points) 

988 

989 def __eq__(self, other: object) -> bool: 

990 if not isinstance(other, SubFacet): 

991 raise ValueError 

992 return self.points == other.points 

993 

994 

995class Facet: 

996 """A facet of a hull (an edge in two dimensions, a triangle in three): its points, 

997 its center, its outward normal and its subfacets. 

998 

999 Args: 

1000 coordinates: Its points, one per row. 

1001 internal: A point inside the hull, which its normal points away from. 

1002 """ 

1003 

1004 def __init__(self, coordinates: PointND_Array, internal: PointND) -> None: 

1005 self.coordinates = coordinates 

1006 self.center: PointND = np.mean(coordinates, axis=0) 

1007 self.normal = self.compute_normal(internal) 

1008 self.subfacets = frozenset( 

1009 SubFacet(np.delete(self.coordinates, i, axis=0)) 

1010 for i in range(self.coordinates.shape[0]) 

1011 ) 

1012 

1013 def compute_normal(self, internal: PointND) -> PointND: 

1014 """The facet's unit normal, pointing away from a point inside the hull. 

1015 

1016 Args: 

1017 internal: The point inside. 

1018 """ 

1019 centered = self.coordinates - self.center 

1020 _, _, vh = np.linalg.svd(centered) 

1021 normal: PointND = vh[-1, :] 

1022 normal /= np.linalg.norm(normal) 

1023 

1024 # If the normal points towards the internal point, flip it! 

1025 if np.dot(normal, self.center - internal) < 0: 

1026 normal *= -1 

1027 

1028 return normal 

1029 

1030 def __hash__(self) -> int: 

1031 return hash(self.subfacets) 

1032 

1033 

1034class Horizon: 

1035 """What a point outside a hull sees of it: the facets it sees, and the subfacets 

1036 between those and the facets it doesn't.""" 

1037 

1038 def __init__(self) -> None: 

1039 self.facets: set[Facet] = set() 

1040 self.boundary: list[SubFacet] = [] 

1041 

1042 

1043@deprecated( 

1044 "Manim CE's machinery for ConvexHull: use ConvexHull, or ConvexHull3D", 

1045 category=None, 

1046) 

1047class QuickHull: 

1048 """The convex hull of points, in two dimensions or more, by the Quickhull algorithm. 

1049 

1050 [build][manimgx.QuickHull.build] computes it: the hull's facets (its edges in two 

1051 dimensions, its triangles in three) are then those of `facets` not in `removed`. 

1052 

1053 Args: 

1054 tolerance: How far beyond a facet a point must be to count as outside it. 

1055 """ 

1056 

1057 def __init__(self, tolerance: float = 1e-5) -> None: 

1058 self.facets: list[Facet] = [] 

1059 self.removed: set[Facet] = set() 

1060 self.outside: dict[Facet, tuple[PointND_Array | None, PointND | None]] = {} 

1061 self.neighbors: dict[SubFacet, set[Facet]] = {} 

1062 self.unclaimed: PointND_Array | None = None 

1063 self.internal: PointND | None = None 

1064 self.tolerance = tolerance 

1065 

1066 def initialize(self, points: PointND_Array) -> None: 

1067 """Start the hull as a simplex of extreme points, and share the points outside 

1068 it among its facets; [build][manimgx.QuickHull.build] calls it first. 

1069 

1070 Args: 

1071 points: The points, one per row. 

1072 """ 

1073 # The initial simplex from extreme points, each the farthest from the span of those before 

1074 # (CE sampled it with an unseeded generator: the same input gave a different hull layout 

1075 # on every run) 

1076 chosen = [int(np.argmin(points[:, 0]))] 

1077 while len(chosen) < points.shape[1] + 1: 

1078 offsets = points - points[chosen[0]] 

1079 if len(chosen) > 1: 

1080 basis, _ = np.linalg.qr((points[chosen[1:]] - points[chosen[0]]).T) 

1081 offsets = offsets - offsets @ basis @ basis.T 

1082 chosen.append(int(np.argmax(np.linalg.norm(offsets, axis=1)))) 

1083 simplex = points[chosen] 

1084 self.unclaimed = points 

1085 new_internal: PointND = np.mean(simplex, axis=0) 

1086 self.internal = new_internal 

1087 

1088 # Build Simplex 

1089 for c in range(simplex.shape[0]): 

1090 facet = Facet(np.delete(simplex, c, axis=0), internal=new_internal) 

1091 self.classify(facet) 

1092 self.facets.append(facet) 

1093 

1094 # Attach Neighbors 

1095 for f in self.facets: 

1096 for sf in f.subfacets: 

1097 self.neighbors.setdefault(sf, set()).add(f) 

1098 

1099 def classify(self, facet: Facet) -> None: 

1100 """Give a new facet the points no facet has yet that lie beyond it, and among 

1101 them the farthest, the next point to add; [build][manimgx.QuickHull.build] calls 

1102 it for each facet it makes. 

1103 """ 

1104 assert self.unclaimed is not None, ( 

1105 "Call .initialize() before using .classify()." 

1106 ) 

1107 

1108 if not self.unclaimed.size: 

1109 self.outside[facet] = (None, None) 

1110 return 

1111 

1112 # Compute Projections 

1113 projections = (self.unclaimed - facet.center) @ facet.normal 

1114 arg = np.argmax(projections) 

1115 mask = projections > self.tolerance 

1116 

1117 # Identify Eye and Outside Set 

1118 eye = self.unclaimed[arg] if projections[arg] > self.tolerance else None 

1119 outside = self.unclaimed[mask] 

1120 self.outside[facet] = (outside, eye) 

1121 self.unclaimed = self.unclaimed[~mask] 

1122 

1123 def compute_horizon(self, eye: PointND, start_facet: Facet) -> Horizon: 

1124 """What a point outside the hull sees of it, from a facet it sees: the hull 

1125 grows to the point from the edge of what it sees. 

1126 

1127 Args: 

1128 eye: The point. 

1129 start_facet: A facet it sees. 

1130 

1131 Returns: 

1132 The facets it sees and the subfacets bounding them. 

1133 """ 

1134 horizon = Horizon() 

1135 self._recursive_horizon(eye, start_facet, horizon) 

1136 return horizon 

1137 

1138 def _recursive_horizon(self, eye: PointND, facet: Facet, horizon: Horizon) -> bool: 

1139 visible = np.dot(facet.normal, eye - facet.center) > 0 

1140 if not visible: 

1141 return False 

1142 

1143 # If the eye is visible from the facet: 

1144 # Label the facet as visible and cross each edge 

1145 horizon.facets.add(facet) 

1146 for subfacet in facet.subfacets: 

1147 neighbor = (self.neighbors[subfacet] - {facet}).pop() 

1148 # If the neighbor is not visible, then the edge shared must be on the boundary 

1149 if neighbor not in horizon.facets and not self._recursive_horizon( 

1150 eye, neighbor, horizon 

1151 ): 

1152 horizon.boundary.append(subfacet) 

1153 return True 

1154 

1155 def build(self, points: PointND_Array) -> None: 

1156 """Compute the convex hull of points. 

1157 

1158 Raises an exception for points in one dimension, or fewer than one more than 

1159 their dimensions. 

1160 

1161 Args: 

1162 points: The points, one per row, each of two coordinates or more. 

1163 """ 

1164 num, dim = points.shape 

1165 if (dim == 0) or (num < dim + 1): 

1166 raise ValueError("Not enough points supplied to build Convex Hull!") 

1167 if dim == 1: 

1168 raise ValueError("The Convex Hull of 1D data is its min-max!") 

1169 

1170 self.initialize(points) 

1171 

1172 # This helps the type checker. 

1173 assert self.unclaimed is not None 

1174 assert self.internal is not None 

1175 

1176 while True: 

1177 updated = False 

1178 for facet in self.facets: 

1179 if facet in self.removed: 

1180 continue 

1181 _outside, eye = self.outside[facet] 

1182 if eye is not None: 

1183 updated = True 

1184 horizon = self.compute_horizon(eye, facet) 

1185 for f in horizon.facets: 

1186 points_to_append = self.outside[f][0] 

1187 # TODO: is this always true? 

1188 assert points_to_append is not None 

1189 self.unclaimed = np.vstack((self.unclaimed, points_to_append)) 

1190 self.removed.add(f) 

1191 for sf in f.subfacets: 

1192 self.neighbors[sf].discard(f) 

1193 if self.neighbors[sf] == set(): 

1194 del self.neighbors[sf] 

1195 for sf in horizon.boundary: 

1196 nf = Facet( 

1197 np.vstack((sf.coordinates, eye)), internal=self.internal 

1198 ) 

1199 self.classify(nf) 

1200 self.facets.append(nf) 

1201 for nsf in nf.subfacets: 

1202 self.neighbors.setdefault(nsf, set()).add(nf) 

1203 if not updated: 

1204 break 

1205 

1206 

1207@overload 

1208def interpolate(start: float, end: float, alpha: float) -> float: ... 

1209@overload 

1210def interpolate(start: complex, end: complex, alpha: float) -> complex: ... 

1211@overload 

1212def interpolate(start: float, end: float, alpha: np.ndarray) -> np.ndarray: ... 

1213@overload 

1214def interpolate( 

1215 start: np.ndarray, end: np.ndarray, alpha: float | np.ndarray 

1216) -> np.ndarray: ... 

1217def interpolate( 

1218 start: complex | np.ndarray, end: complex | np.ndarray, alpha: float | np.ndarray 

1219) -> complex | np.ndarray: 

1220 """The value a fraction of the way from one value to another: (1 − alpha)·start + 

1221 alpha·end. 

1222 

1223 Args: 

1224 start: The value at 0: a number or an array. 

1225 end: The value at 1, of the same kind. 

1226 alpha: How far from `start` to `end`: 0 gives `start`, 1 `end`, and beyond them 

1227 it goes on along the line; an array gives one value per entry. 

1228 

1229 Returns: 

1230 The value between. 

1231 """ 

1232 return (1 - alpha) * start + alpha * end 

1233 

1234 

1235def integer_interpolate(start: float, end: float, alpha: float) -> tuple[int, float]: 

1236 """Which whole step from `start` toward `end` a fraction falls in, and how far into 

1237 it: for `start` 0 and `end` n, which of n curves, and where along it. 

1238 

1239 Args: 

1240 start: The first step's start, a whole number. 

1241 end: The last step's end, a whole number past `start`. 

1242 alpha: How far from `start` to `end`, from 0 to 1. 

1243 

1244 Returns: 

1245 The step, from `start` to `end` − 1, and the fraction of it, from 0 to 1: step + 

1246 fraction is `start` + (`end` − `start`)·`alpha`; at 1, the last step, wholly. 

1247 """ 

1248 if alpha >= 1: 

1249 return int(end - 1), 1.0 

1250 if alpha <= 0: 

1251 return int(start), 0.0 

1252 reached = (end - start) * alpha 

1253 # whole steps down (floor, not toward 0), and never past the last, however it rounds 

1254 whole = min(math.floor(reached), int(end - start) - 1) 

1255 return int(start) + whole, reached - whole 

1256 

1257 

1258def inverse_interpolate(start: float, end: float, value: float) -> float: 

1259 """How far a value is from one value to another: the inverse of 

1260 [interpolate][manimgx.interpolate]. 

1261 

1262 Args: 

1263 start: The value at 0. 

1264 end: The value at 1. 

1265 

1266 Returns: 

1267 The fraction, (value − start) / (end − start). 

1268 """ 

1269 return float(np.true_divide(value - start, end - start)) 

1270 

1271 

1272_NPPCC = 4 

1273 

1274 

1275def sample( 

1276 function: Callable[..., object], *args: np.ndarray, checked: bool = True 

1277) -> np.ndarray: 

1278 """Evaluate a function at every point of a grid of arguments. 

1279 

1280 `args` are arrays of one shape, one per argument of `function`. The function is 

1281 called once on the whole arrays, as most numeric functions allow, and checked 

1282 against single calls at the first, middle and last points; a function written for 

1283 one value at a time (`math.cos`, `if t < 0`) raises or differs there, and is then 

1284 called once per point. A value given as its components (`(t, t**2, 0)`) takes a 

1285 component that is one number across the grid. 

1286 

1287 Args: 

1288 function: The function, from the arguments to a value. 

1289 *args: The arguments' values: arrays of one shape. 

1290 checked: Whether the whole arrays' values are checked against single calls; 

1291 unchecked, a function that takes arrays is trusted to give what single 

1292 calls would. 

1293 

1294 Returns: 

1295 The values: an array of the arguments' shape, followed by a value's. 

1296 """ 

1297 shape, n = args[0].shape, args[0].size 

1298 flat = [a.ravel() for a in args] 

1299 try: 

1300 value = function(*args) 

1301 if isinstance(value, (tuple, list)): # its components: a number taken across 

1302 value = np.broadcast_arrays(*(np.asarray(c, dtype=float) for c in value)) 

1303 out = np.asarray(value, dtype=float) 

1304 k = len(shape) 

1305 if out.shape[:k] != shape and out.shape[-k:] == shape: # values first 

1306 out = np.moveaxis(out, range(out.ndim - k, out.ndim), range(k)) 

1307 values = out.reshape(n, -1) 

1308 for i in {0, n // 2, n - 1} if checked else (): 

1309 one = np.asarray(function(*(float(f[i]) for f in flat)), dtype=float) 

1310 if not np.allclose(values[i], one.ravel(), rtol=1e-9, atol=1e-12): 

1311 raise ValueError(i) 

1312 return out 

1313 except Exception: # not vectorizable: one point at a time 

1314 out = np.array( 

1315 [function(*(float(f[i]) for f in flat)) for i in range(n)], float 

1316 ) 

1317 return out.reshape(*shape, *out.shape[1:]) 

1318 

1319 

1320def subpath_ranges( 

1321 points: Point3D_Array, atol: float, dims: int = 3 

1322) -> list[tuple[int, int, bool]]: 

1323 """(start, end, closed) per subpath: one starts where a curve does not begin at the previous 

1324 curve's end (CE's rule); it is closed when its ends coincide.""" 

1325 n = len(points) - len(points) % _NPPCC 

1326 if n < _NPPCC: 

1327 return [] 

1328 ends, starts = ( 

1329 points[_NPPCC - 1 : n - 1 : _NPPCC, :dims], 

1330 points[_NPPCC:n:_NPPCC, :dims], 

1331 ) 

1332 breaks = ~np.all(np.abs(ends - starts) <= atol + 1e-5 * np.abs(starts), axis=1) 

1333 splits = [0, *((np.flatnonzero(breaks) + 1) * _NPPCC).tolist(), n] 

1334 return [ 

1335 (a, b, bool(np.allclose(points[a, :dims], points[b - 1, :dims], atol=atol))) 

1336 for a, b in itertools.pairwise(splits) 

1337 if b - a >= _NPPCC 

1338 ] 

1339 

1340 

1341def _pathops() -> ModuleType: 

1342 """skia-pathops, which finds the regions (imported when first needed: it has no build for 

1343 Pyodide, so in the browser these shapes can't be made).""" 

1344 try: 

1345 import pathops 

1346 except ImportError as error: 

1347 raise ImportError( 

1348 "Union, Difference, Intersection and Exclusion need skia-pathops, which has" 

1349 " no build for the browser (Pyodide) yet" 

1350 ) from error 

1351 return pathops 

1352 

1353 

1354def _to_path(points: Point3D_Array, tolerance: float) -> SkiaPath: 

1355 """An outline's planar path, with the same complete subpaths and closure tolerance.""" 

1356 path = _pathops().Path() 

1357 if not np.all(np.isfinite(points)): 

1358 return path 

1359 for start, end, closed in subpath_ranges(points, tolerance, dims=2): 

1360 path.moveTo(*points[start, :2]) 

1361 for _p0, p1, p2, p3 in points[start:end].reshape(-1, 4, 3): 

1362 path.cubicTo(*p1[:2], *p2[:2], *p3[:2]) 

1363 if closed: 

1364 path.close() 

1365 return path 

1366 

1367 

1368def bezier(points: Point3DLike_Array) -> Callable[[float], Point3D]: 

1369 """A cubic Bézier curve as a function: from its first control point at 0 to its last 

1370 at 1. 

1371 

1372 Args: 

1373 points: Its four control points: anchor, handle, handle, anchor. 

1374 

1375 Returns: 

1376 A function of the curve's parameter, from 0 to 1, giving its point there. 

1377 """ 

1378 P = np.asarray(points) 

1379 

1380 def cubic(t: float) -> Point3D: 

1381 mt = 1 - t 

1382 return mt**3 * P[0] + 3 * t * mt**2 * P[1] + 3 * t**2 * mt * P[2] + t**3 * P[3] 

1383 

1384 return cubic 

1385 

1386 

1387def partial_bezier_points( 

1388 points: Point3DLike_Array, a: float, b: float 

1389) -> Point3D_Array: 

1390 """The control points of part of a cubic Bézier curve, from its parameter `a` to 

1391 `b`. 

1392 

1393 Args: 

1394 points: The curve's four control points. 

1395 a: Where the part starts, from 0 to 1. 

1396 b: Where it ends, from `a` to 1. 

1397 

1398 Returns: 

1399 The part's four control points. 

1400 """ 

1401 if a == 1: 

1402 arr = np.array(points) 

1403 arr[:] = arr[-1] 

1404 return arr 

1405 if b == 0: 

1406 arr = np.array(points) 

1407 arr[:] = arr[0] 

1408 return arr 

1409 ma, mb = 1 - a, 1 - b 

1410 a2, b2, ma2, mb2 = a * a, b * b, ma * ma, mb * mb 

1411 a3, b3, ma3, mb3 = a2 * a, b2 * b, ma2 * ma, mb2 * mb 

1412 m = np.array( 

1413 [ 

1414 [ma3, 3 * ma2 * a, 3 * ma * a2, a3], 

1415 [ma2 * mb, 2 * ma * a * mb + ma2 * b, a2 * mb + 2 * ma * a * b, a2 * b], 

1416 [ma * mb2, a * mb2 + 2 * ma * mb * b, 2 * a * mb * b + ma * b2, a * b2], 

1417 [mb3, 3 * mb2 * b, 3 * mb * b2, b3], 

1418 ] 

1419 ) 

1420 return m @ np.asarray(points) 

1421 

1422 

1423_SUBDIVISION: Memo[int, np.ndarray] = Memo(1 << 10) 

1424 

1425 

1426def _subdivision_matrix(n: int | np.integer) -> np.ndarray: 

1427 m = _SUBDIVISION.get(n) 

1428 if m is not None: 

1429 return m 

1430 n = int(n) 

1431 m = np.empty((4 * n, 4)) 

1432 for i in range(n): 

1433 i2, i3 = i * i, i * i * i 

1434 ip1 = i + 1 

1435 ip12, ip13 = ip1 * ip1, ip1 * ip1 * ip1 

1436 nmi = n - i 

1437 nmi2, nmi3 = nmi * nmi, nmi * nmi * nmi 

1438 nmim1 = nmi - 1 

1439 nmim12, nmim13 = nmim1 * nmim1, nmim1 * nmim1 * nmim1 

1440 m[4 * i : 4 * (i + 1)] = [ 

1441 [nmi3, 3 * nmi2 * i, 3 * nmi * i2, i3], 

1442 [ 

1443 nmi2 * nmim1, 

1444 2 * nmi * nmim1 * i + nmi2 * ip1, 

1445 nmim1 * i2 + 2 * nmi * i * ip1, 

1446 i2 * ip1, 

1447 ], 

1448 [ 

1449 nmi * nmim12, 

1450 nmim12 * i + 2 * nmi * nmim1 * ip1, 

1451 2 * nmim1 * i * ip1 + nmi * ip12, 

1452 i * ip12, 

1453 ], 

1454 [nmim13, 3 * nmim12 * ip1, 3 * nmim1 * ip12, ip13], 

1455 ] 

1456 m /= n**3 

1457 return _SUBDIVISION.keep(n, m) 

1458 

1459 

1460def subdivide_bezier( 

1461 points: Point3DLike_Array, n_divisions: int | np.integer 

1462) -> Point3D_Array: 

1463 """Split a cubic Bézier curve into curves over equal stretches of its parameter. 

1464 

1465 Args: 

1466 points: The curve's four control points. 

1467 n_divisions: How many curves. 

1468 

1469 Returns: 

1470 Their control points, four per curve, one curve after another. 

1471 """ 

1472 points = np.asarray(points) 

1473 if n_divisions == 1: 

1474 return points 

1475 return _subdivision_matrix(n_divisions) @ points 

1476 

1477 

1478def bezier_remap(tuples: npt.ArrayLike, new_count: int) -> np.ndarray: 

1479 """Split cubic Bézier curves into more, their shape unchanged. 

1480 

1481 Each curve is split over equal stretches of its parameter, the new curves spread 

1482 among the curves as evenly as can be: curve i of m gets the new curves j of 

1483 `new_count` with j·m // `new_count` = i (4 curves into 6: 2, 1, 2, 1). 

1484 

1485 Args: 

1486 tuples: The curves' control points: an array of shape (curves, 4, dimensions). 

1487 new_count: How many curves to make, at least as many as there are. 

1488 

1489 Returns: 

1490 The new curves' control points, an array of shape (new_count, 4, dimensions). 

1491 """ 

1492 tuples = np.asarray(tuples) 

1493 count, nppc, dim = tuples.shape 

1494 if new_count == count: 

1495 return np.array(tuples, dtype=float, order="C") 

1496 if count and new_count % count == 0: 

1497 pieces = _subdivision_matrix(new_count // count) @ tuples 

1498 return np.asarray(pieces, dtype=float).reshape(new_count, nppc, dim) 

1499 starts = (np.arange(count + 1) * new_count + count - 1) // count 

1500 out = np.empty((new_count, nppc, dim)) 

1501 for curve, start, end in zip(tuples, starts[:-1], starts[1:], strict=True): 

1502 factor = end - start 

1503 out[start:end] = subdivide_bezier(curve, factor).reshape(factor, nppc, dim) 

1504 return out 

1505 

1506 

1507def is_closed(points: Point3D_Array) -> bool: 

1508 """Whether points end where they start: the last equal to the first, within 1e-8 

1509 plus 1e-5 of the first's coordinates. 

1510 """ 

1511 # np.isclose's tolerances, independent of the sign 

1512 start, end = points[0], points[-1] 

1513 return bool(np.all(np.abs(end - start) <= 1e-08 + 1e-05 * np.abs(start))) 

1514 

1515 

1516def get_smooth_cubic_bezier_handle_points( 

1517 anchors: Point3D_Array, 

1518) -> tuple[Point3D_Array, Point3D_Array]: 

1519 """The handles of a smooth curve through anchors: a cubic spline, bending with no 

1520 change of curvature at any anchor, and closed smoothly if the last anchor is the 

1521 first. 

1522 

1523 Args: 

1524 anchors: The anchors, in order. 

1525 

1526 Returns: 

1527 Each curve's first handles and second handles, as two arrays with one row per 

1528 curve (one fewer than the anchors). 

1529 """ 

1530 A = np.asarray(anchors, dtype=float) 

1531 n = A.shape[0] 

1532 if n == 1: 

1533 return np.zeros((0, A.shape[1])), np.zeros((0, A.shape[1])) 

1534 if n == 2: 

1535 return ( 

1536 interpolate(A[0], A[1], 1 / 3)[None], 

1537 interpolate(A[0], A[1], 2 / 3)[None], 

1538 ) 

1539 closed = is_closed(A) 

1540 if n > _SMOOTHING_UP_TO: 

1541 return _smooth_closed(A) if closed else _smooth_open(A) 

1542 to_h1, to_h2 = _smoothing(n, closed) 

1543 return to_h1 @ A, to_h2 @ A 

1544 

1545 

1546# anchors; beyond, the solve itself (linear time) beats a dense map 

1547_SMOOTHING_UP_TO = 256 

1548 

1549 

1550@forgets 

1551@functools.lru_cache(maxsize=64) 

1552def _smoothing(n: int, closed: bool) -> tuple[np.ndarray, np.ndarray]: 

1553 """(K1, K2): smooth handles are K1·A and K2·A, maps that depend only on the number of anchors 

1554 (the solve, run once on the identity).""" 

1555 k1, k2 = (_smooth_closed if closed else _smooth_open)(np.eye(n)) 

1556 k1.flags.writeable = k2.flags.writeable = False 

1557 return k1, k2 

1558 

1559 

1560def _smooth_closed(A: np.ndarray) -> tuple[np.ndarray, np.ndarray]: 

1561 N, dim = A.shape[0] - 1, A.shape[1] 

1562 cp, up = np.empty(N - 1), np.empty(N - 1) 

1563 cp[0], up[0] = 1 / 3, 1 / 3 

1564 for i in range(1, N - 1): 

1565 cp[i] = 1 / (4 - cp[i - 1]) 

1566 up[i] = -cp[i] * up[i - 1] 

1567 cp_last = 1 / (3 - cp[N - 2]) 

1568 up_last = cp_last * (1 - up[N - 2]) 

1569 q = np.empty((N, dim)) 

1570 q[N - 1] = up_last 

1571 for i in range(N - 2, -1, -1): 

1572 q[i] = up[i] - cp[i] * q[i + 1] 

1573 Dp = np.empty((N, dim)) 

1574 AUX = 4 * A[:N] + 2 * A[1:] 

1575 Dp[0] = AUX[0] / 3 

1576 for i in range(1, N - 1): 

1577 Dp[i] = cp[i] * (AUX[i] - Dp[i - 1]) 

1578 Dp[N - 1] = cp_last * (AUX[N - 1] - Dp[N - 2]) 

1579 Y = Dp 

1580 for i in range(N - 2, -1, -1): 

1581 Y[i] = Dp[i] - cp[i] * Y[i + 1] 

1582 H1 = Y - 1 / (1 + q[0] + q[N - 1]) * q * (Y[0] + Y[N - 1]) 

1583 H2 = np.empty((N, dim)) 

1584 H2[: N - 1] = 2 * A[1:N] - H1[1:N] 

1585 H2[N - 1] = 2 * A[N] - H1[0] 

1586 return H1, H2 

1587 

1588 

1589def _smooth_open(A: np.ndarray) -> tuple[np.ndarray, np.ndarray]: 

1590 N, dim = A.shape[0] - 1, A.shape[1] 

1591 cp = np.empty(N - 1) 

1592 cp[0] = 0.5 

1593 for i in range(1, N - 1): 

1594 cp[i] = 1 / (4 - cp[i - 1]) 

1595 Dp = np.empty((N, dim)) 

1596 Dp[0] = 0.5 * A[0] + A[1] 

1597 AUX = 4 * A[1 : N - 1] + 2 * A[2:N] 

1598 for i in range(1, N - 1): 

1599 Dp[i] = cp[i] * (AUX[i - 1] - Dp[i - 1]) 

1600 Dp[N - 1] = 1 / (7 - 2 * cp[N - 2]) * (8 * A[N - 1] + A[N] - 2 * Dp[N - 2]) 

1601 H1 = Dp 

1602 for i in range(N - 2, -1, -1): 

1603 H1[i] = Dp[i] - cp[i] * H1[i + 1] 

1604 H2 = np.empty((N, dim)) 

1605 H2[: N - 1] = 2 * A[1:N] - H1[1:N] 

1606 H2[N - 1] = 0.5 * (A[N] + H1[N - 1]) 

1607 return H1, H2 

1608 

1609 

1610type Floats = npt.NDArray[np.float64] 

1611"""A NumPy array of floats.""" 

1612type Coefficients = tuple[Floats, Floats, Floats] # Lₛ, Lₑ, k 

1613"""A path's rule at one moment: the 3×3 matrices Lₛ and Lₑ and the vector k that take 

1614each point to Lₛ·start + Lₑ·end + k.""" 

1615type Step = tuple[float, Floats, Floats] | Floats | Callable[[float], Floats] 

1616"""A step of a motion: a turn (an angle, an axis and a pivot, a point of the object as 

1617it began), a move by a vector, or a move along a curve (a function of α giving where the 

1618object has been carried at α).""" 

1619 

1620STRAIGHT_PATH_THRESHOLD: Final = 0.01 

1621"""The smallest angle, in radians, [path_along_arc][manimgx.path_along_arc] and 

1622[spiral_path][manimgx.spiral_path] turn through: with less, they are the 

1623[straight path][manimgx.straight_path].""" 

1624_PATH_AXIS: Final = np.array([0.0, 0.0, 1.0]) 

1625_EYE: Final = np.eye(3) 

1626_ZERO: Final = np.zeros(3) 

1627 

1628 

1629def _cross(axis: Floats) -> Floats: 

1630 """K with K·v = axis × v.""" 

1631 x, y, z = axis 

1632 return np.array([[0.0, -z, y], [z, 0.0, -x], [-y, x, 0.0]]) 

1633 

1634 

1635@dataclass(frozen=True, slots=True, eq=False) 

1636class Path: 

1637 """How the points of a shape travel in a transform, from where they start to where 

1638 they end, as a value. 

1639 

1640 A path takes each point to Lₛ·start + Lₑ·end + k, where Lₛ, Lₑ and k depend on the 

1641 animation's progress α alone: so a shape moves without its points being touched. 

1642 Call it as `path(start, end, alpha)`, on arrays of points; the functions below make 

1643 the paths ManimGX provides. 

1644 

1645 Args: 

1646 kind: What the path is. "motion": the shape is carried by the motion G of its 

1647 `steps` while it changes along straight lines in the moving frame, 

1648 G(α)·((1 − α)·start + α·G(1)⁻¹·end); with no steps, the straight path. 

1649 "arc": each point travels along a circular arc from its start to its end, 

1650 turning through `angle` (and at a steady rate along `axis`, if its ends 

1651 differ along it). "spiral": each point spirals out from its start to 

1652 its end, start + α·R((α − 1)·`angle`)·(end − start). 

1653 angle: The angle an "arc" or "spiral" path turns through, in radians, 

1654 counterclockwise about `axis`. 

1655 axis: The axis the path turns about. 

1656 steps: The steps of a "motion" path, taken in order: each a move (a vector), a 

1657 move along a curve, or a turn about a pivot. 

1658 """ 

1659 

1660 kind: Literal["motion", "arc", "spiral"] = "motion" 

1661 angle: float = 0.0 

1662 axis: Floats = field(default_factory=lambda: _PATH_AXIS.copy()) 

1663 steps: tuple[Step, ...] = () 

1664 _end: list[Floats] = field(default_factory=list, init=False, repr=False) # G(1) 

1665 

1666 @deprecated("ManimGX's machinery: a transform calls it", category=None) 

1667 def coefficients(self, alpha: float) -> Coefficients: 

1668 """The path's rule at a moment: each point goes to Lₛ·start + Lₑ·end + k. 

1669 

1670 Args: 

1671 alpha: The animation's progress, from 0 to 1. 

1672 

1673 Returns: 

1674 The 3×3 matrices Lₛ and Lₑ, and the vector k. 

1675 """ 

1676 if self.kind == "motion": 

1677 if not self.steps: 

1678 return (1 - alpha) * _EYE, alpha * _EYE, _ZERO 

1679 if not self._end: 

1680 self._end.append(self.motion(1.0)) 

1681 g, end = self.motion(alpha), self._end[0] 

1682 le = alpha * g[:3, :3] @ end[:3, :3].T 

1683 return ( 

1684 (1 - alpha) * g[:3, :3], 

1685 le, 

1686 g[:3, 3] - le @ end[:3, 3], 

1687 ) 

1688 if self.kind == "spiral": 

1689 rot = rotation_matrix((alpha - 1) * self.angle, self.axis) 

1690 return _EYE - alpha * rot, alpha * rot, _ZERO 

1691 # across the axis, an arc about the center; along it, a steady move (the turn and 

1692 # (I − R) leave a point's height along the axis alone, so it is moved apart) 

1693 rot = rotation_matrix(alpha * self.angle, self.axis) 

1694 along = alpha * np.outer(self.axis, self.axis) 

1695 if self.angle == np.pi: 

1696 cs = ce = 0.5 * _EYE 

1697 else: 

1698 k = _cross(self.axis) / (2 * np.tan(self.angle / 2)) 

1699 cs, ce = 0.5 * _EYE - k, 0.5 * _EYE + k 

1700 return (_EYE - rot) @ cs + rot - along, (_EYE - rot) @ ce + along, _ZERO 

1701 

1702 @deprecated("ManimGX's machinery: a transform calls it", category=None) 

1703 def motion(self, alpha: float) -> Floats: 

1704 """The motion the path's steps have carried the shape by at a moment. 

1705 

1706 Args: 

1707 alpha: The animation's progress, from 0 to 1. 

1708 

1709 Returns: 

1710 The 4×4 affine matrix G(α). 

1711 """ 

1712 return carried((step, alpha) for step in self.steps) 

1713 

1714 def __call__( 

1715 self, start: Point3D_Array, end: Point3D_Array, alpha: float 

1716 ) -> Point3D_Array: 

1717 ls, le, k = self.coefficients(alpha) 

1718 return start @ ls.T + end @ le.T + k 

1719 

1720 

1721@deprecated("ManimGX's machinery: a transform calls it", category=None) 

1722def carried(steps: Iterable[tuple[Step, float]]) -> Floats: 

1723 """The motion of steps taken in order, each as far as its own fraction. 

1724 

1725 A move goes that fraction of its vector, and a move along a curve to where the curve 

1726 has carried the object at that fraction; a turn turns through that fraction of its 

1727 angle, about its pivot where the steps before it have carried the pivot. 

1728 

1729 Args: 

1730 steps: The steps (see [Step][manimgx.Step]), each with its fraction, from 0 to 

1731 1. 

1732 

1733 Returns: 

1734 The 4×4 affine matrix of the motion. 

1735 """ 

1736 g = np.eye(4) 

1737 for step, alpha in steps: 

1738 if isinstance(step, np.ndarray): 

1739 g[:3, 3] += alpha * step 

1740 elif isinstance(step, tuple): 

1741 angle, axis, pivot = step 

1742 turn = rotation_matrix(alpha * angle, axis) 

1743 p = g[:3, :3] @ pivot + g[:3, 3] 

1744 g[:3] = turn @ g[:3] 

1745 g[:3, 3] += p - turn @ p 

1746 else: 

1747 g[:3, 3] += step(alpha) - step(0.0) 

1748 return g 

1749 

1750 

1751def _unit(axis: Vector3DLike) -> Floats: 

1752 unit = normalize(axis) 

1753 if not unit.any(): 

1754 raise ValueError(f"a path's axis must not be zero, not {axis}") 

1755 return unit 

1756 

1757 

1758def straight_path() -> Path: 

1759 """The straight path: each point goes along the line from its start to its end, as 

1760 a transform moves points by default. 

1761 """ 

1762 return Path() 

1763 

1764 

1765def path_along_arc(arc_angle: float, axis: Vector3DLike = _PATH_AXIS) -> Path: 

1766 """A path along arcs: each point travels along a circular arc from its start to its 

1767 end, turning through an angle, as a transform's `path_arc` makes it move. 

1768 

1769 Args: 

1770 arc_angle: The angle each arc turns through, in radians, counterclockwise about 

1771 `axis`; smaller in size than 

1772 [STRAIGHT_PATH_THRESHOLD][manimgx.STRAIGHT_PATH_THRESHOLD], the straight 

1773 path. 

1774 axis: The axis the arcs turn about. 

1775 """ 

1776 if abs(arc_angle) < STRAIGHT_PATH_THRESHOLD: 

1777 return straight_path() 

1778 return Path("arc", arc_angle, _unit(axis)) 

1779 

1780 

1781def path_along_circles( 

1782 arc_angle: float, 

1783 centers: Point3DLike | Point3DLike_Array, 

1784 axis: Vector3DLike = _PATH_AXIS, 

1785) -> PathFunc: 

1786 """A path about centers: each point turns about its center through an angle while 

1787 it moves from its start to its end, as a transform's `path_arc_centers` makes it 

1788 move. 

1789 

1790 With one center, the shape turns about it as a whole, as a [Path][manimgx.Path]; 

1791 with a center per point, each point turns about its own, as a plain function of 

1792 `(start, end, alpha)`. 

1793 

1794 Args: 

1795 arc_angle: The angle, in radians, counterclockwise about `axis`. 

1796 centers: One center, or one per point, in scene coordinates. 

1797 axis: The axis the points turn about. 

1798 """ 

1799 unit_axis = _unit(axis) 

1800 points: Floats = np.asarray(centers, dtype=np.float64) 

1801 if points.ndim == 1: 

1802 return Path(steps=((arc_angle, unit_axis, points),)) 

1803 

1804 def path(start: Point3D_Array, end: Point3D_Array, alpha: float) -> Point3D_Array: 

1805 detransformed = ( 

1806 points + (end - points) @ rotation_matrix(-arc_angle, unit_axis).T 

1807 ) 

1808 rot = rotation_matrix(alpha * arc_angle, unit_axis) 

1809 return points + ((1 - alpha) * start + alpha * detransformed - points) @ rot.T 

1810 

1811 return path 

1812 

1813 

1814def clockwise_path() -> Path: 

1815 """A path along half circles, clockwise: each point turns through π on its way from 

1816 its start to its end. 

1817 """ 

1818 return path_along_arc(-np.pi) 

1819 

1820 

1821def counterclockwise_path() -> Path: 

1822 """A path along half circles, counterclockwise: each point turns through π on its 

1823 way from its start to its end. 

1824 """ 

1825 return path_along_arc(np.pi) 

1826 

1827 

1828def spiral_path(angle: float, axis: Vector3DLike = _PATH_AXIS) -> Path: 

1829 """A spiral path: each point spirals out from its start to its end, its offset from 

1830 its start growing as it turns counterclockwise through `angle` (for a positive 

1831 angle) into line with its end. 

1832 

1833 Args: 

1834 angle: How far each point turns, in radians, about `axis`; smaller in size than 

1835 [STRAIGHT_PATH_THRESHOLD][manimgx.STRAIGHT_PATH_THRESHOLD], the straight 

1836 path. 

1837 axis: The axis the points turn about. 

1838 """ 

1839 if abs(angle) < STRAIGHT_PATH_THRESHOLD: 

1840 return straight_path() 

1841 return Path("spiral", angle, _unit(axis)) 

1842 

1843 

1844type Matrix = Floats # 3×4: [linear 3×3 | translation] 

1845type Term = tuple[Matrix, "Shape"] 

1846 

1847IDENTITY: Final = np.hstack([np.eye(3), np.zeros((3, 1))]) 

1848IDENTITY.flags.writeable = False # a shape's placement, shared 

1849CANONICAL: Final = 1024 # the most points of a shape reduced to a canonical form 

1850_T: Final = np.linspace(0.0, 1.0, 10)[:, None] 

1851_BERNSTEIN: Final = np.hstack( 

1852 [(1 - _T) ** 3, 3 * (1 - _T) ** 2 * _T, 3 * (1 - _T) * _T**2, _T**3] 

1853) 

1854 

1855 

1856class Shape: 

1857 """Immutable control points (n × 3). Content-addressed, so equal shapes share GPU memory.""" 

1858 

1859 __slots__ = ("_affine", "_boxes", "_key", "array", "log") 

1860 

1861 def __init__(self, array: Floats, log: Log | None = None) -> None: 

1862 array.flags.writeable = False 

1863 self.array: Floats = array 

1864 # the append-only points this shape is a prefix of (a growing path) 

1865 self.log = log 

1866 self._key: int | None = None 

1867 self._affine: tuple[int, Floats, Matrix] | None = None 

1868 self._boxes: dict[bool, Floats] | None = None 

1869 

1870 def box(self, curves: bool) -> Floats: 

1871 """(2, 3): the box of what the points make — for a path (`curves`), its curves' tight box 

1872 (`curve_box`). Kept, as the shape never changes, and read-only: a value.""" 

1873 boxes = self._boxes 

1874 if boxes is None: 

1875 boxes = self._boxes = {} 

1876 box = boxes.get(curves) 

1877 if box is None: 

1878 box = boxes[curves] = _frozen(extent(self.array, curves)) 

1879 return box 

1880 

1881 def extended(self, rows: Floats) -> Shape: 

1882 """This shape with rows appended — in place, when it is its log's longest prefix (a 

1883 growing path costs what it grows); else into a log of its own.""" 

1884 log = self.log 

1885 if log is None or log.length != len(self.array): 

1886 log = Log(self.array) 

1887 return log.extended(rows) 

1888 

1889 @property 

1890 def key(self) -> int: 

1891 """Content address; shapes equal to 1e-9 are the same shape.""" 

1892 if self._key is None: 

1893 self._key = digest( 

1894 str(self.array.shape).encode(), np.round(self.array, 9).tobytes() 

1895 ) 

1896 return self._key 

1897 

1898 @property 

1899 def affine(self) -> tuple[int, Floats, Matrix]: 

1900 """(key, canonical points C, A) with the shape = A·C: C names its affine class (every segment, 

1901 circle or triangle is one), uploaded once, so a shape that only moves, turns, scales or shears is 

1902 never uploaded again. A has zero columns where the shape is flat. A shape of more than 

1903 CANONICAL points is not reduced to a canonical form, which would cost about what uploading 

1904 it does: it is an affine image of the last such shape of its size, if it is one (a surface 

1905 raised, turned or moved by setting its points), or else its own class (C, its points; A, 

1906 the identity), which its key finds again if it recurs as itself.""" 

1907 if self._affine is None: 

1908 if len(self.array) > CANONICAL: 

1909 self._affine = _big_class(self) 

1910 return self._affine 

1911 # equal content, seen before: its class and place 

1912 self._affine = _CLASSES.recall(self.key, lambda: _affine_class(self.array)) 

1913 return self._affine 

1914 

1915 def __deepcopy__(self, memo: dict[int, object]) -> Shape: 

1916 return self 

1917 

1918 

1919_CLASSES: Memo[int, tuple[int, Floats, Matrix]] = Memo(1 << 14) # content → class 

1920# (n, 3) → the class of the last shape of n > CANONICAL points given a class of its own 

1921_LAST: Memo[tuple[int, ...], tuple[int, Floats, Matrix]] = Memo(1 << 6) 

1922_LOGS = itertools.count(1) 

1923 

1924 

1925def _big_class(shape: Shape) -> tuple[int, Floats, Matrix]: 

1926 """A shape of more than CANONICAL points: the last such shape's class if it is an affine image of 

1927 that shape's points, placed by the map; else a class of its own.""" 

1928 last = _LAST.get(shape.array.shape) 

1929 if last is not None: 

1930 a = _affine_image(last[1], shape.array) 

1931 if a is not None: 

1932 return last[0], last[1], a 

1933 return _LAST.keep(shape.array.shape, (shape.key, shape.array, IDENTITY)) 

1934 

1935 

1936def _affine_image(base: Floats, points: Floats) -> Matrix | None: 

1937 """The affine map A (3×4) with points = A·base, if there is one to 1e-9 of their size: the 

1938 identity for the same points (not a fit, which would be off by rounding); else fitted at 16 

1939 points spread along them (where a shape that is not one fails), then checked at every 

1940 point.""" 

1941 if unchanged(points, base): 

1942 return IDENTITY 

1943 probe = np.linspace(0, len(base) - 1, 16).astype(int) 

1944 rows = np.hstack([base[probe], np.ones((len(probe), 1))]) 

1945 fit = np.linalg.lstsq(rows, points[probe], rcond=None)[0] # points ≈ [base 1]·fit 

1946 tolerance = 1e-9 * (1.0 + np.abs(points[probe]).max()) 

1947 if np.abs(rows @ fit - points[probe]).max() > tolerance: 

1948 return None 

1949 if np.abs(base @ fit[:3] + fit[3] - points).max() > tolerance: 

1950 return None 

1951 return np.ascontiguousarray(fit.T) 

1952 

1953 

1954class Log: 

1955 """Control points that only grow: every prefix is a shape sharing the array, and appending to the 

1956 longest writes in place, so a traced path grows by a curve, not by a copy.""" 

1957 

1958 __slots__ = ("array", "id", "length") 

1959 

1960 def __init__(self, rows: Floats) -> None: 

1961 self.array = np.empty((max(64, 2 * len(rows)), 3)) 

1962 self.array[: len(rows)] = rows 

1963 self.length = len(rows) 

1964 self.id = next(_LOGS) 

1965 

1966 def extended(self, rows: Floats) -> Shape: 

1967 end = self.length + len(rows) 

1968 if end > len(self.array): 

1969 grown = np.empty((2 * end, 3)) 

1970 grown[: self.length] = self.array[: self.length] 

1971 self.array = grown 

1972 self.array[self.length : end] = rows 

1973 self.length = end 

1974 return Shape(self.array[:end], self) 

1975 

1976 

1977def _affine_class(points: Floats) -> tuple[int, Floats, Matrix]: 

1978 """Center and whiten the points (unit covariance in the subspace they span), then fix the 

1979 remaining rotation by the points themselves: the first farthest point on +x, the first farthest 

1980 from that line in the +y half-plane, then +z (ties within 1e-6 keep their order). Canonical 

1981 points are O(1), well within float32.""" 

1982 n = len(points) 

1983 if n == 0: 

1984 return digest(str(points.shape).encode()), points, IDENTITY.copy() 

1985 center = points.mean(axis=0) 

1986 d = points - center 

1987 values, vectors = np.linalg.eigh(d.T @ d / n) 

1988 # a direction thinner than 1e-6 of the shape's size is flat 

1989 spanned = values > values[-1] * 1e-12 if values[-1] > 0 else values > 1.0 

1990 rank = int(spanned.sum()) 

1991 canonical = np.zeros_like(points) 

1992 linear = np.zeros((3, 3)) 

1993 if rank: 

1994 roots = np.sqrt(values[spanned]) 

1995 x = d @ (vectors[:, spanned] / roots) # whitened: n × rank 

1996 frame = np.zeros((rank, rank)) 

1997 rest = x 

1998 for axis in range(rank): 

1999 norms = np.einsum("ij,ij->i", rest, rest) 

2000 pick = int(np.argmax(norms >= norms.max() * (1 - 1e-6))) 

2001 frame[axis] = rest[pick] / np.sqrt(norms[pick]) 

2002 rest = rest - np.outer(rest @ frame[axis], frame[axis]) 

2003 canonical[:, :rank] = x @ frame.T 

2004 linear[:, :rank] = (vectors[:, spanned] * roots) @ frame.T 

2005 canonical.flags.writeable = False 

2006 key = digest( # + 0.0: no negative zeros 

2007 str(points.shape).encode(), (np.round(canonical, 7) + 0.0).tobytes() 

2008 ) 

2009 return key, canonical, np.hstack([linear, center[:, None]]) 

2010 

2011 

2012_DEFINED: Memo[tuple[object, ...], Shape] = Memo(1 << 12) 

2013 

2014 

2015def defined(definition: tuple[object, ...], make: Callable[[], Floats]) -> Shape: 

2016 """The shape a definition names (`("arc", start, angle, n)`), made once and shared — with its 

2017 affine class and upload — by every mobject that draws it.""" 

2018 return _DEFINED.recall(definition, lambda: Shape(np.array(make(), dtype=float))) 

2019 

2020 

2021SEGMENT: Final = Shape( 

2022 np.array([[0.0, 0, 0], [1 / 3, 0, 0], [2 / 3, 0, 0], [1.0, 0, 0]]) 

2023) 

2024 

2025 

2026def _frozen(array: Floats) -> Floats: 

2027 """`array`, read-only: what is cached is handed out as a value.""" 

2028 array.setflags(write=False) # (cheaper than `flags.writeable`: no flags object) 

2029 return array 

2030 

2031 

2032def curve_box(points: Floats) -> Floats: 

2033 """(2, D): the tight box of cubic Bézier curves (control points in fours). The anchors lie on 

2034 the curves, and each curve lies in its control points' hull, so the anchors' box is tight 

2035 unless a handle leaves it; only such curves are solved for their turning points: per 

2036 coordinate, the roots of the derivative, a quadratic (solved without cancellation, so a 

2037 vanishing leading term is harmless). Any parameter in [0, 1] is a point of the curve, so a 

2038 clipped or spurious root is harmless too.""" 

2039 ends = np.concatenate([points[0::4], points[3::4]]) 

2040 lo, hi = ends.min(axis=0), ends.max(axis=0) 

2041 p = points.reshape(-1, 4, points.shape[-1]) 

2042 p = p[((p < lo) | (p > hi)).any(axis=(1, 2))] 

2043 if len(p) == 0: 

2044 return np.array([lo, hi]) 

2045 p0, p1, p2, p3 = p[:, 0], p[:, 1], p[:, 2], p[:, 3] 

2046 c = p1 - p0 # B'(t)/3 = a t² + 2 h t + c, per coordinate 

2047 h = p2 - p1 - c 

2048 a = p3 - p0 - 3 * (p2 - p1) 

2049 q = -(h + np.copysign(np.sqrt(np.maximum(h * h - a * c, 0)), h)) # roots q/a, c/q 

2050 t = np.clip([q / np.where(a == 0, 1, a), c / np.where(q == 0, 1, q)], 0, 1) 

2051 turns = p0 + t * (3 * c + t * (3 * h + t * a)) # B(t), by Horner 

2052 return np.array( 

2053 [np.minimum(lo, turns.min(axis=(0, 1))), np.maximum(hi, turns.max(axis=(0, 1)))] 

2054 ) 

2055 

2056 

2057def extent(points: Floats, curves: bool) -> Floats: 

2058 """(2, D): the box of what the points make: a path's (`curves`: complete cubic curves) is its 

2059 curves' tight box, anything else's its points'.""" 

2060 if curves and len(points) and len(points) % 4 == 0: 

2061 return curve_box(points) 

2062 return np.array([points.min(axis=0), points.max(axis=0)]) 

2063 

2064 

2065def placed_box(m: Matrix, shape: Shape, curves: bool) -> Floats: 

2066 """(2, 3): the box of `shape` placed by `m`. A map along the axes keeps each coordinate's 

2067 extremes: there it is the shape's own box, mapped; else the placed points' box.""" 

2068 linear = m[:, :3] 

2069 d = linear.diagonal() 

2070 if np.count_nonzero(linear) == np.count_nonzero(d): # along the axes 

2071 ends = shape.box(curves) * d + m[:, 3] 

2072 return np.array([ends.min(axis=0), ends.max(axis=0)]) 

2073 return extent(shape.array @ linear.T + m[:, 3], curves) 

2074 

2075 

2076def segment(start: Floats, end: Floats) -> Blend: 

2077 """A straight segment (one cubic curve, handles at its thirds, as CE makes it): the one 

2078 segment shape, placed by [end − start | start].""" 

2079 m = np.zeros((3, 4)) 

2080 m[:, 0], m[:, 3] = np.subtract(end, start), start 

2081 return Blend(((m, SEGMENT),), 4) 

2082 

2083 

2084def _compose(linear: Floats, matrix: Matrix) -> Matrix: 

2085 """linear ∘ matrix, where `linear` is 3×3 (no translation of its own): one product, as the 

2086 translation column transforms like any other.""" 

2087 return linear @ matrix 

2088 

2089 

2090class Blend: 

2091 """points = Σ M·S over `terms`. Immutable: every edit returns a new blend.""" 

2092 

2093 __slots__ = ("_boxes", "_pace", "_pieces", "_points", "n", "terms") 

2094 

2095 def __init__(self, terms: tuple[Term, ...], n: int) -> None: 

2096 self.terms = terms 

2097 self.n = n # number of points, known without materializing 

2098 self._points: Floats | None = None 

2099 self._pieces: Floats | None = None 

2100 self._pace: tuple[Floats, Floats] | None = None 

2101 self._boxes: dict[bool, Floats] | None = None 

2102 

2103 def box(self, curves: bool) -> Floats: 

2104 """(2, 3): the box of what the points make — for a path (`curves`), its curves' tight box: 

2105 not its anchors' (a curve bulges between them), not its handles' (they overshoot). 

2106 Cached, as a blend never changes, and read-only: a value.""" 

2107 boxes = self._boxes 

2108 if boxes is None: 

2109 boxes = self._boxes = {} 

2110 box = boxes.get(curves) 

2111 if box is None: 

2112 box = boxes[curves] = _frozen( 

2113 placed_box(*self.terms[0], curves) # one shape placed 

2114 if len(self.terms) == 1 

2115 else extent(self.points(), curves) 

2116 ) 

2117 return box 

2118 

2119 @staticmethod 

2120 def of(points: npt.ArrayLike, dim: int = 3) -> Blend: 

2121 """A blend of one fresh shape. Translation is factored out, so translated copies share it.""" 

2122 array = np.array(points, dtype=float).reshape(-1, dim) 

2123 if len(array) == 0: 

2124 return EMPTY 

2125 origin = array[0].copy() 

2126 matrix = IDENTITY.copy() 

2127 matrix[:, 3] = origin 

2128 return Blend(((matrix, Shape(array - origin)),), len(array)) 

2129 

2130 def points(self) -> Floats: 

2131 if self._points is None: 

2132 out = np.zeros((self.n, 3)) 

2133 for m, shape in self.terms: 

2134 out += shape.array @ m[:, :3].T + m[:, 3] 

2135 out.flags.writeable = False 

2136 self._points = out 

2137 return self._points 

2138 

2139 @property 

2140 def cached(self) -> Floats | None: 

2141 """The points, if they have been read; else None (what is compared with them for free).""" 

2142 return self._points 

2143 

2144 def point(self, k: int) -> Floats: 

2145 """Point k (from the end if negative) without materializing the blend: a path being 

2146 built reads where it ends once a curve, not all its points.""" 

2147 if self._points is not None or not self.terms: 

2148 return self.points()[k] 

2149 out = np.zeros(3) 

2150 for m, shape in self.terms: 

2151 out += shape.array[k] @ m[:, :3].T + m[:, 3] 

2152 return out 

2153 

2154 def translated(self, vector: Floats) -> Blend: 

2155 """The blend moved by `vector`: one term's offset, no product (a move is the commonest 

2156 edit of all) — and its boxes moved with it, when known.""" 

2157 if not self.terms: 

2158 return self 

2159 (first, shape), *rest = self.terms 

2160 moved = first.copy() 

2161 moved[:, 3] += vector 

2162 blend = Blend(((moved, shape), *rest), self.n) 

2163 if self._boxes: 

2164 blend._boxes = {k: _frozen(box + vector) for k, box in self._boxes.items()} 

2165 return blend 

2166 

2167 def scaled(self, factor: float, about: Floats) -> Blend: 

2168 """The blend scaled by `factor` about `about` — x ↦ f·x + (1 − f)·about: every term's 

2169 map times f, the rest added once; its boxes, when known, scaled with it.""" 

2170 if not self.terms: 

2171 return self 

2172 terms = [(m * factor, shape) for m, shape in self.terms] 

2173 terms[0][0][:, 3] += about * (1.0 - factor) 

2174 blend = Blend(tuple(terms), self.n) 

2175 if self._boxes: 

2176 blend._boxes = {} 

2177 for k, box in self._boxes.items(): 

2178 ends = (box - about) * factor + about 

2179 blend._boxes[k] = _frozen(ends if factor >= 0 else ends[::-1].copy()) 

2180 return blend 

2181 

2182 def transformed(self, m: Matrix) -> Blend: 

2183 """The blend after the affine map `m` (its boxes follow a map along the axes).""" 

2184 if not self.terms: 

2185 return self 

2186 terms = [(_compose(m[:, :3], a), shape) for a, shape in self.terms] 

2187 terms[0][0][:, 3] += m[:, 3] 

2188 blend = Blend(tuple(terms), self.n) 

2189 if self._boxes: 

2190 d = m.diagonal() 

2191 if np.count_nonzero(m[:, :3]) == np.count_nonzero(d): # along the axes 

2192 blend._boxes = {} 

2193 for k, box in self._boxes.items(): 

2194 ends = box * d + m[:, 3] 

2195 blend._boxes[k] = _frozen( 

2196 np.array([ends.min(axis=0), ends.max(axis=0)]) 

2197 ) 

2198 return blend 

2199 

2200 @staticmethod 

2201 def mix(a: Blend, b: Blend, coefficients: Coefficients) -> Blend: 

2202 """`Lₛ·a + Lₑ·b + k` point by point; terms of the same shape merge, so a morph between copies 

2203 of one shape stays one matrix.""" 

2204 ls, le, offset = coefficients 

2205 if len(a.terms) == 1 and len(b.terms) == 1 and a.terms[0][1] is b.terms[0][1]: 

2206 mixed = _compose(ls, a.terms[0][0]) + _compose(le, b.terms[0][0]) 

2207 mixed[:, 3] += offset 

2208 return Blend(((mixed, a.terms[0][1]),), a.n) 

2209 merged: dict[int, Term] = {} 

2210 for linear, blend in ((ls, a), (le, b)): 

2211 for m, shape in blend.terms: 

2212 term = _compose(linear, m) 

2213 if shape.key in merged: 

2214 term = merged[shape.key][0] + term 

2215 merged[shape.key] = (term, shape) 

2216 if not merged: 

2217 return Blend((), a.n) 

2218 terms = list(merged.values()) 

2219 terms[0][0][:, 3] += offset 

2220 return Blend(tuple(terms), a.n) 

2221 

2222 def piece_lengths(self) -> Floats: 

2223 """(curves, 9): lengths of each curve's polyline through 10 points — the path's own 

2224 measure of length, which its reveals, proportions and lengths all go by.""" 

2225 pieces = self._pieces 

2226 if pieces is None: 

2227 pts = self.points() 

2228 curves = pts[: len(pts) // 4 * 4].reshape(-1, 4, 3) 

2229 samples = np.einsum("tk,ckd->ctd", _BERNSTEIN, curves) 

2230 pieces = np.linalg.norm(np.diff(samples, axis=1), axis=2) 

2231 pieces.flags.writeable = False 

2232 self._pieces = pieces 

2233 return pieces 

2234 

2235 def curve_lengths(self) -> Floats: 

2236 """Length of each cubic curve.""" 

2237 return self.piece_lengths().sum(axis=1) 

2238 

2239 def pace(self) -> tuple[Floats, Floats]: 

2240 """(s, u): the fraction s of the length reached at curve parameter u. A reveal reads it once: 

2241 constant pen speed, and the drawn part stays put under later transforms.""" 

2242 pieces = self.piece_lengths() 

2243 curves = len(pieces) 

2244 u = np.concatenate( 

2245 [ 

2246 [0.0], 

2247 (np.arange(curves)[:, None] + np.arange(1, 10)[None, :] / 9).ravel(), 

2248 ] 

2249 ) 

2250 s = np.concatenate([[0.0], np.cumsum(pieces.ravel())]) 

2251 return (s / s[-1] if s[-1] > 0 else u / max(curves, 1)), u 

2252 

2253 def parameter_at(self, fraction: float) -> float: 

2254 """The curve parameter u ∈ [0, curves] a fraction of the length along the path: 

2255 the inverse of `fraction_at`, through the pace.""" 

2256 if self._pace is None: 

2257 self._pace = self.pace() 

2258 s, u = self._pace 

2259 return float(np.interp(fraction, s, u)) 

2260 

2261 def fraction_at(self, parameter: float) -> float: 

2262 """The fraction of the path's length reached at curve parameter u ∈ [0, curves].""" 

2263 if self._pace is None: 

2264 self._pace = self.pace() 

2265 s, u = self._pace 

2266 return float(np.interp(parameter, u, s)) 

2267 

2268 def __deepcopy__(self, memo: dict[int, object]) -> Blend: 

2269 return self 

2270 

2271 

2272EMPTY: Final = Blend((), 0) 

2273 

2274 

2275def linear_about(linear: Floats, about: Floats) -> Matrix: 

2276 """The affine map x ↦ L(x − about) + about.""" 

2277 m = np.empty((3, 4)) 

2278 m[:, :3] = linear 

2279 m[:, 3] = about - linear @ about 

2280 return m 

2281 

2282 

2283@forgets 

2284@functools.cache 

2285def grid_triangles(u: int, v: int) -> np.ndarray: 

2286 """Two triangles per lattice cell, in the same u-major cell order.""" 

2287 index = np.arange((u + 1) * (v + 1)).reshape(u + 1, v + 1) 

2288 a, b, c, d = index[:-1, :-1], index[1:, :-1], index[1:, 1:], index[:-1, 1:] 

2289 triangles = np.stack([a, b, c, a, c, d], axis=-1).reshape(-1, 3) 

2290 triangles.flags.writeable = False 

2291 return triangles 

2292 

2293 

2294class Lattice(NamedTuple): 

2295 """A sampled surface's topology: its samples a (u + 1) by (v + 1) grid, its faces the 

2296 u by v cells between them in u-major order, of which it draws `first` to `end`: all, 

2297 or a part's (the faces a reveal over the part's stretch shows).""" 

2298 

2299 u: int 

2300 v: int 

2301 first: int 

2302 end: int 

2303 

2304 @classmethod 

2305 def of(cls, u: int, v: int) -> Lattice: 

2306 """All the faces of a u by v lattice.""" 

2307 return cls(u, v, 0, u * v) 

2308 

2309 def triangles(self) -> np.ndarray: 

2310 """The faces it draws, two triangles each: indices into its samples, read-only, 

2311 and one array for equal lattices.""" 

2312 return _lattice_triangles(*self) 

2313 

2314 

2315@forgets 

2316@functools.cache 

2317def _lattice_triangles(u: int, v: int, first: int, end: int) -> np.ndarray: 

2318 """A lattice's drawn faces' triangles: the whole grid's array when it draws them all.""" 

2319 every = grid_triangles(u, v) 

2320 return every if (first, end) == (0, u * v) else every[2 * first : 2 * end]