firefox-main/gfx/wr/webrender/src/util.rs (file symbol)

Source code

Revision control

Copy as Markdown

Other Tools

/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
use api::BorderRadius;
use api::units::*;
use euclid::{Point2D, Rect, Box2D, Size2D, SideOffsets2D};
use euclid::{Transform2D, Transform3D, Vector2D};
use plane_split::{Clipper, Polygon};
use std::{fmt, ptr};
use std::num::NonZeroUsize;
use std::sync::Arc;
use std::mem::replace;
use crate::internal_types::FrameVec;
pub use api::{ScaleOffset, FastTransform, LayoutFastTransform, LayoutToWorldFastTransform};
// Matches the definition of SK_ScalarNearlyZero in Skia.
const NEARLY_ZERO: f32 = 1.0 / 4096.0;
/// A typesafe helper that separates new value construction from
/// vector growing, allowing LLVM to ideally construct the element in place.
pub struct Allocation<'a, T: 'a> {
vec: &'a mut Vec<T>,
index: usize,
}
impl<'a, T> Allocation<'a, T> {
// writing is safe because alloc() ensured enough capacity
// and `Allocation` holds a mutable borrow to prevent anyone else
// from breaking this invariant.
#[inline(always)]
pub fn init(self, value: T) -> usize {
unsafe {
ptr::write(self.vec.as_mut_ptr().add(self.index), value);
self.vec.set_len(self.index + 1);
}
self.index
}
}
/// An entry into a vector, similar to `std::collections::hash_map::Entry`.
pub enum VecEntry<'a, T: 'a> {
Vacant(Allocation<'a, T>),
Occupied(&'a mut T),
}
impl<'a, T> VecEntry<'a, T> {
#[inline(always)]
pub fn set(self, value: T) {
match self {
VecEntry::Vacant(alloc) => { alloc.init(value); }
VecEntry::Occupied(slot) => { *slot = value; }
}
}
}
pub trait VecHelper<T> {
/// Growns the vector by a single entry, returning the allocation.
fn alloc(&mut self) -> Allocation<T>;
/// Either returns an existing elemenet, or grows the vector by one.
/// Doesn't expect indices to be higher than the current length.
fn entry(&mut self, index: usize) -> VecEntry<T>;
/// Equivalent to `mem::replace(&mut vec, Vec::new())`
fn take(&mut self) -> Self;
/// Functionally equivalent to `mem::replace(&mut vec, Vec::new())` but tries
/// to keep the allocation in the caller if it is empty or replace it with a
/// pre-allocated vector.
fn take_and_preallocate(&mut self) -> Self;
}
impl<T> VecHelper<T> for Vec<T> {
fn alloc(&mut self) -> Allocation<T> {
let index = self.len();
if self.capacity() == index {
self.reserve(1);
}
Allocation {
vec: self,
index,
}
}
fn entry(&mut self, index: usize) -> VecEntry<T> {
if index < self.len() {
VecEntry::Occupied(unsafe {
self.get_unchecked_mut(index)
})
} else {
assert_eq!(index, self.len());
VecEntry::Vacant(self.alloc())
}
}
fn take(&mut self) -> Self {
replace(self, Vec::new())
}
fn take_and_preallocate(&mut self) -> Self {
let len = self.len();
if len == 0 {
self.clear();
return Vec::new();
}
replace(self, Vec::with_capacity(len + 8))
}
}
// TODO: Implement these in euclid!
pub trait MatrixHelpers<Src, Dst> {
/// A port of the preserves2dAxisAlignment function in Skia.
/// Defined in the SkMatrix44 class.
fn preserves_2d_axis_alignment(&self) -> bool;
fn has_perspective_component(&self) -> bool;
/// Returns true if this transform maps coplanar `z=0` content exactly as the
/// plain 2D transform in its `m11`/`m12`/`m21`/`m22`/`m41`/`m42` terms would,
/// *and* `inverse()` maps it back the same way. Content that is rasterized
/// and positioned in device space (e.g. text) needs both halves, because it
/// round-trips through device space: the CPU places it with this transform
/// and the shader maps the result back with `inv_m`, forcing `z` to 0 again.
///
/// This is `Transform3D::is_2d()` weakened where the extra 3D terms can't be
/// observed on that plane:
/// * `m33` is free: nothing reads the mapped `z`.
/// * only *one* of the third row (`m31`/`m32`/`m34`) and the third column
/// (`m13`/`m23`/`m43`) has to vanish, not both. Mapping the plane reads
/// rows and columns 1, 2 and 4, and that block of the inverse picks up a
/// `-b*c/m33` correction from those two groups - so with either one zero
/// the block is still the 2D inverse. A flat `perspective` (bug 2052019)
/// and a bare `translateZ` are each clean on one side; pairing them, or
/// rotating in 3D, is not, and no longer round-trips (bug 2060342).
///
/// `m14`/`m24` and `m44` must still be 2D-exact: a `w` that varies across the
/// plane is a true keystone, which can't be rasterized into an axis-aligned
/// device rect at all, and a constant `w != 1` would need the perspective
/// divide that mapping through `inv_m` skips.
fn is_2d_on_z_plane(&self) -> bool;
/// Scale factors for content that is coplanar in the source space (z=0),
/// which is the case for the contents of a picture surface. Returns `None`
/// if the perspective divide varies across that plane, where no single
/// scale factor is correct.
///
/// Much weaker than `is_2d_on_z_plane`: this only asks how the plane is
/// mapped, not that mapping it back through `inverse()` agrees, so a
/// constant `w != 1` is fine (it divides out) and the `z` terms don't
/// matter at all.
fn coplanar_scale_factors(&self) -> Option<(f32, f32)>;
fn has_2d_inverse(&self) -> bool;
/// Check if the matrix post-scaling on either the X or Y axes could cause geometry
/// transformed by this matrix to have scaling exceeding the supplied limit.
fn exceeds_2d_scale(&self, limit: f64) -> bool;
fn inverse_project(&self, target: &Point2D<f32, Dst>) -> Option<Point2D<f32, Src>>;
fn inverse_rect_footprint(&self, rect: &Box2D<f32, Dst>) -> Option<Box2D<f32, Src>>;
fn is_simple_translation(&self) -> bool;
fn is_simple_2d_translation(&self) -> bool;
fn is_2d_scale_translation(&self) -> bool;
/// If this transform is a rotation or reflection by a multiple of 90 degrees
/// (with unit scale, no z-coupling and no perspective), decompose it into a
/// `ScaleOffset` plus whether the x and y axes are swapped (the 90/270-degree
/// case, where the `ScaleOffset` applies after the swap). Returns `None`
/// otherwise. Such a transform keeps content on the same pixel grid, so a
/// rect can be snapped across it losslessly. Unlike
/// `preserves_2d_axis_alignment`, this also rejects perspective (`m34`) and
/// rescaling.
fn as_grid_aligned_rotation(&self) -> Option<(ScaleOffset, bool)>;
/// Return the determinant of the 2D part of the matrix.
fn determinant_2d(&self) -> f32;
/// Turn Z transformation into identity. This is useful when crossing "flat"
/// transform styled stacking contexts upon traversing the coordinate systems.
fn flatten_z_output(&mut self);
fn cast_unit<NewSrc, NewDst>(&self) -> Transform3D<f32, NewSrc, NewDst>;
}
impl<Src, Dst> MatrixHelpers<Src, Dst> for Transform3D<f32, Src, Dst> {
fn preserves_2d_axis_alignment(&self) -> bool {
if self.m14 != 0.0 || self.m24 != 0.0 {
return false;
}
let mut col0 = 0;
let mut col1 = 0;
let mut row0 = 0;
let mut row1 = 0;
if self.m11.abs() > NEARLY_ZERO {
col0 += 1;
row0 += 1;
}
if self.m12.abs() > NEARLY_ZERO {
col1 += 1;
row0 += 1;
}
if self.m21.abs() > NEARLY_ZERO {
col0 += 1;
row1 += 1;
}
if self.m22.abs() > NEARLY_ZERO {
col1 += 1;
row1 += 1;
}
col0 < 2 && col1 < 2 && row0 < 2 && row1 < 2
}
fn has_perspective_component(&self) -> bool {
self.m14.abs() > NEARLY_ZERO ||
self.m24.abs() > NEARLY_ZERO ||
self.m34.abs() > NEARLY_ZERO ||
(self.m44 - 1.0).abs() > NEARLY_ZERO
}
fn is_2d_on_z_plane(&self) -> bool {
if self.m14.abs() > NEARLY_ZERO ||
self.m24.abs() > NEARLY_ZERO ||
(self.m44 - 1.0).abs() > NEARLY_ZERO {
return false;
}
let z_in = self.m31.abs() > NEARLY_ZERO ||
self.m32.abs() > NEARLY_ZERO ||
self.m34.abs() > NEARLY_ZERO;
let z_out = self.m13.abs() > NEARLY_ZERO ||
self.m23.abs() > NEARLY_ZERO ||
self.m43.abs() > NEARLY_ZERO;
!z_in || !z_out
}
fn coplanar_scale_factors(&self) -> Option<(f32, f32)> {
// `w` varies across the z=0 plane: a true keystone, with no single scale.
if self.m14.abs() > NEARLY_ZERO ||
self.m24.abs() > NEARLY_ZERO {
return None;
}
// `w` is constant over that plane, so the mapping is affine with its
// 2d part divided through by `m44`. A non-positive `w` means the plane
// is degenerate or behind the eye.
if self.m44 < NEARLY_ZERO {
return None;
}
let (major, minor) = scale_factors(self);
Some((major / self.m44, minor / self.m44))
}
fn has_2d_inverse(&self) -> bool {
self.determinant_2d() != 0.0
}
fn exceeds_2d_scale(&self, limit: f64) -> bool {
let limit2 = (limit * limit) as f32;
self.m11 * self.m11 + self.m12 * self.m12 > limit2 ||
self.m21 * self.m21 + self.m22 * self.m22 > limit2
}
/// Find out a point in `Src` that would be projected into the `target`.
fn inverse_project(&self, target: &Point2D<f32, Dst>) -> Option<Point2D<f32, Src>> {
// form the linear equation for the hyperplane intersection
let m = Transform2D::<f32, Src, Dst>::new(
self.m11 - target.x * self.m14, self.m12 - target.y * self.m14,
self.m21 - target.x * self.m24, self.m22 - target.y * self.m24,
self.m41 - target.x * self.m44, self.m42 - target.y * self.m44,
);
let inv = m.inverse()?;
// we found the point, now check if it maps to the positive hemisphere
if inv.m31 * self.m14 + inv.m32 * self.m24 + self.m44 > 0.0 {
Some(Point2D::new(inv.m31, inv.m32))
} else {
None
}
}
fn inverse_rect_footprint(&self, rect: &Box2D<f32, Dst>) -> Option<Box2D<f32, Src>> {
Some(Box2D::from_points(&[
self.inverse_project(&rect.top_left())?,
self.inverse_project(&rect.top_right())?,
self.inverse_project(&rect.bottom_left())?,
self.inverse_project(&rect.bottom_right())?,
]))
}
fn is_simple_translation(&self) -> bool {
if (self.m11 - 1.0).abs() > NEARLY_ZERO ||
(self.m22 - 1.0).abs() > NEARLY_ZERO ||
(self.m33 - 1.0).abs() > NEARLY_ZERO ||
(self.m44 - 1.0).abs() > NEARLY_ZERO {
return false;
}
self.m12.abs() < NEARLY_ZERO && self.m13.abs() < NEARLY_ZERO &&
self.m14.abs() < NEARLY_ZERO && self.m21.abs() < NEARLY_ZERO &&
self.m23.abs() < NEARLY_ZERO && self.m24.abs() < NEARLY_ZERO &&
self.m31.abs() < NEARLY_ZERO && self.m32.abs() < NEARLY_ZERO &&
self.m34.abs() < NEARLY_ZERO
}
fn is_simple_2d_translation(&self) -> bool {
if !self.is_simple_translation() {
return false;
}
self.m43.abs() < NEARLY_ZERO
}
/* is this...
* X 0 0 0
* 0 Y 0 0
* 0 0 1 0
* a b 0 1
*/
fn is_2d_scale_translation(&self) -> bool {
(self.m33 - 1.0).abs() < NEARLY_ZERO &&
(self.m44 - 1.0).abs() < NEARLY_ZERO &&
self.m12.abs() < NEARLY_ZERO && self.m13.abs() < NEARLY_ZERO && self.m14.abs() < NEARLY_ZERO &&
self.m21.abs() < NEARLY_ZERO && self.m23.abs() < NEARLY_ZERO && self.m24.abs() < NEARLY_ZERO &&
self.m31.abs() < NEARLY_ZERO && self.m32.abs() < NEARLY_ZERO && self.m34.abs() < NEARLY_ZERO &&
self.m43.abs() < NEARLY_ZERO
}
fn as_grid_aligned_rotation(&self) -> Option<(ScaleOffset, bool)> {
let is_zero = |v: f32| v.abs() < NEARLY_ZERO;
let is_one = |v: f32| (v - 1.0).abs() < NEARLY_ZERO;
let is_unit = |v: f32| (v.abs() - 1.0).abs() < NEARLY_ZERO;
// Must be a flat 2D transform: no z coupling and no perspective.
// Translation (m41, m42) is unconstrained; tz (m43) must be zero.
if !(is_zero(self.m13) && is_zero(self.m14) && is_zero(self.m23) && is_zero(self.m24) &&
is_zero(self.m31) && is_zero(self.m32) && is_one(self.m33) && is_zero(self.m34) &&
is_zero(self.m43) && is_one(self.m44)) {
return None;
}
// The remaining 2x2 must only rotate/flip by a right angle, never scale.
// A 0/180-degree rotation or axis flip (entries on the diagonal) maps to
// a `ScaleOffset` directly; a 90/270-degree rotation (entries off the
// diagonal) maps to the same `ScaleOffset` applied after swapping x and y.
if is_unit(self.m11) && is_unit(self.m22) && is_zero(self.m12) && is_zero(self.m21) {
Some((ScaleOffset::new(self.m11, self.m22, self.m41, self.m42), false))
} else if is_unit(self.m12) && is_unit(self.m21) && is_zero(self.m11) && is_zero(self.m22) {
Some((ScaleOffset::new(self.m21, self.m12, self.m41, self.m42), true))
} else {
None
}
}
fn determinant_2d(&self) -> f32 {
self.m11 * self.m22 - self.m12 * self.m21
}
fn flatten_z_output(&mut self) {
self.m13 = 0.0;
self.m23 = 0.0;
self.m33 = 1.0;
self.m43 = 0.0;
//Note: we used to zero out m3? as well, see "reftests/flatten-all-flat.yaml" test
}
fn cast_unit<NewSrc, NewDst>(&self) -> Transform3D<f32, NewSrc, NewDst> {
Transform3D::new(
self.m11, self.m12, self.m13, self.m14,
self.m21, self.m22, self.m23, self.m24,
self.m31, self.m32, self.m33, self.m34,
self.m41, self.m42, self.m43, self.m44,
)
}
}
pub trait VectorHelpers<U>
where
Self: Sized,
{
fn snap(&self) -> Self;
}
impl<U> VectorHelpers<U> for Vector2D<f32, U> {
fn snap(&self) -> Self {
Vector2D::new(
self.x.round(),
self.y.round(),
)
}
}
pub trait RectHelpers<U>
where
Self: Sized,
{
fn from_floats(x0: f32, y0: f32, x1: f32, y1: f32) -> Self;
fn snap(&self) -> Self;
}
impl<U> RectHelpers<U> for Rect<f32, U> {
fn from_floats(x0: f32, y0: f32, x1: f32, y1: f32) -> Self {
Rect::new(
Point2D::new(x0, y0),
Size2D::new(x1 - x0, y1 - y0),
)
}
fn snap(&self) -> Self {
let origin = Point2D::new(
(self.origin.x + 0.5).floor(),
(self.origin.y + 0.5).floor(),
);
Rect::new(
origin,
Size2D::new(
(self.origin.x + self.size.width + 0.5).floor() - origin.x,
(self.origin.y + self.size.height + 0.5).floor() - origin.y,
),
)
}
}
impl<U> RectHelpers<U> for Box2D<f32, U> {
fn from_floats(x0: f32, y0: f32, x1: f32, y1: f32) -> Self {
Box2D {
min: Point2D::new(x0, y0),
max: Point2D::new(x1, y1),
}
}
fn snap(&self) -> Self {
self.round()
}
}
pub fn lerp(a: f32, b: f32, t: f32) -> f32 {
(b - a) * t + a
}
#[repr(u32)]
#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
pub enum TransformedRectKind {
AxisAligned = 0,
Complex = 1,
}
#[inline(always)]
pub fn pack_as_float(value: u32) -> f32 {
value as f32 + 0.5
}
#[inline]
fn extract_inner_rect_impl<U>(
rect: &Box2D<f32, U>,
radii: &BorderRadius,
inset: &SideOffsets2D<f32, U>,
k: f32,
) -> Option<Box2D<f32, U>> {
// `k` defines how much border is taken into account
// We enforce the offsets to be rounded to pixel boundaries
// by `ceil`-ing and `floor`-ing them
// In case of a corner shape below "round" (superellipse parameter < 1),
// we need to add the inset to the radii for correctness. This will slightly
// overestimate the corner area for sub-ellipses (-1 < parameter < 1), but
// keeps the computation cheap.
let mut top_left_width = radii.top_left.width;
let mut top_left_height = radii.top_left.height;
let mut top_right_width = radii.top_right.width;
let mut top_right_height = radii.top_right.height;
let mut bottom_left_width = radii.bottom_left.width;
let mut bottom_left_height = radii.bottom_left.height;
let mut bottom_right_width = radii.bottom_right.width;
let mut bottom_right_height = radii.bottom_right.height;
if radii.shape_top_left < 1.0 {
top_left_width += inset.top;
top_left_height += inset.left;
}
if radii.shape_top_right < 1.0 {
top_right_width += inset.top;
top_right_height += inset.right;
}
if radii.shape_bottom_left < 1.0 {
bottom_left_width += inset.bottom;
bottom_left_height += inset.left;
}
if radii.shape_bottom_right < 1.0 {
bottom_right_width += inset.bottom;
bottom_right_height += inset.right;
}
let xl = (k * top_left_width.max(bottom_left_width)).ceil();
let xr = (rect.width() - k * top_right_width.max(bottom_right_width)).floor();
let yt = (k * top_left_height.max(top_right_height)).ceil();
let yb =
(rect.height() - k * bottom_left_height.max(bottom_right_height)).floor();
if xl <= xr && yt <= yb {
Some(Box2D::from_origin_and_size(
Point2D::new(rect.min.x + xl, rect.min.y + yt),
Size2D::new(xr - xl, yb - yt),
))
} else {
None
}
}
/// Return an aligned rectangle that is inside the clip region and doesn't intersect
/// any of the bounding rectangles of the rounded corners.
pub fn extract_inner_rect_safe<U>(
rect: &Box2D<f32, U>,
radii: &BorderRadius,
inset: &SideOffsets2D<f32, U>,
) -> Option<Box2D<f32, U>> {
// `k == 1.0` excludes each corner's full bounding box, so the result is the
// region that the edge and center parts of a nine-patch can cover. See the
// rounded-rect case of `SegmentBuilder::push_clip_rect` in segment.rs, which
// builds that nine-patch.
extract_inner_rect_impl(rect, radii, inset, 1.0)
}
/// Return an aligned rectangle that is inside the clip region and doesn't intersect
/// any of the bounding rectangles of the rounded corners, with a specific k factor
/// to control how much of the rounded corner is included.
pub fn extract_inner_rect_k<U>(
rect: &Box2D<f32, U>,
radii: &BorderRadius,
inset: &SideOffsets2D<f32, U>,
k: f32,
) -> Option<Box2D<f32, U>> {
// When using corner shape, corners can go inside the shape and create
// clipping issues, we need the 'safe' (k == 1.0) version in that case.
// This could be refined by computing the superellipse half corners but
// would make the calculation a bit more expensive.
if radii.shapes_all_round() {
extract_inner_rect_impl(rect, radii, inset, k)
} else {
extract_inner_rect_impl(rect, radii, inset, 1.0)
}
}
#[cfg(test)]
use euclid::vec3;
#[cfg(test)]
pub mod test {
use super::*;
use euclid::default::{Box2D, Point2D, Size2D, Transform3D};
use euclid::{Angle, approxeq::ApproxEq};
use std::f32::consts::PI;
use crate::clip::{is_left_of_line, polygon_contains_point};
use crate::prim_store::PolygonKey;
use api::FillRule;
#[test]
fn is_2d_on_z_plane() {
// A z=0 point mapped by each of these, then mapped back by the inverse
// with its z forced to 0 again (what the device-space text path does),
// lands where it started exactly when this returns true.
let flat_perspective = Transform3D::new(
1.0, 0.0, 0.0, 0.0,
0.0, 1.0, 0.0, 0.0,
-7.9, -1.8375, 1.0, -0.025,
0.0, 0.0, 0.0, 1.0,
);
let translate_z = Transform3D::translation(0.0, 0.0, 5.0);
// Neither side is clean once the two are paired.
let perspective_and_translate_z = translate_z.then(&flat_perspective);
let rotate_y = Transform3D::rotation(0.0, 1.0, 0.0, Angle::degrees(35.0));
let mut w_scale = Transform3D::identity();
w_scale.m44 = 2.0;
assert!(flat_perspective.is_2d_on_z_plane());
assert!(translate_z.is_2d_on_z_plane());
assert!(Transform3D::scale(2.0, 3.0, 4.0).is_2d_on_z_plane());
assert!(!perspective_and_translate_z.is_2d_on_z_plane());
assert!(!rotate_y.is_2d_on_z_plane());
assert!(!w_scale.is_2d_on_z_plane());
assert!(!Transform3D::perspective(40.0).pre_translate(
euclid::vec3(0.0, 0.0, 1.0)).is_2d_on_z_plane());
}
#[test]
fn inverse_project() {
let m0 = Transform3D::identity();
let p0 = Point2D::new(1.0, 2.0);
// an identical transform doesn't need any inverse projection
assert_eq!(m0.inverse_project(&p0), Some(p0));
let m1 = Transform3D::rotation(0.0, 1.0, 0.0, Angle::radians(-PI / 3.0));
// rotation by 60 degrees would imply scaling of X component by a factor of 2
assert_eq!(m1.inverse_project(&p0), Some(Point2D::new(2.0, 2.0)));
}
#[test]
fn inverse_project_footprint() {
let m = Transform3D::new(
0.477499992, 0.135000005, -1.0, 0.000624999986,
-0.642787635, 0.766044438, 0.0, 0.0,
0.766044438, 0.642787635, 0.0, 0.0,
1137.10986, 113.71286, 402.0, 0.748749971,
);
let r = Box2D::from_size(Size2D::new(804.0, 804.0));
{
let points = &[
r.top_left(),
r.top_right(),
r.bottom_left(),
r.bottom_right(),
];
let mi = m.inverse().unwrap();
// In this section, we do the forward and backward transformation
// to confirm that its bijective.
// We also do the inverse projection path, and confirm it functions the same way.
info!("Points:");
for p in points {
let pp = m.transform_point2d_homogeneous(*p);
let p3 = pp.to_point3d().unwrap();
let pi = mi.transform_point3d_homogeneous(p3);
let px = pi.to_point2d().unwrap();
let py = m.inverse_project(&pp.to_point2d().unwrap()).unwrap();
info!("\t{:?} -> {:?} -> {:?} -> ({:?} -> {:?}, {:?})", p, pp, p3, pi, px, py);
assert!(px.approx_eq_eps(p, &Point2D::new(0.001, 0.001)));
assert!(py.approx_eq_eps(p, &Point2D::new(0.001, 0.001)));
}
}
// project
let rp = project_rect(&m, &r, &Box2D::from_size(Size2D::new(1000.0, 1000.0))).unwrap();
info!("Projected {:?}", rp);
// one of the points ends up in the negative hemisphere
assert_eq!(m.inverse_project(&rp.min), None);
// inverse
if let Some(ri) = m.inverse_rect_footprint(&rp) {
// inverse footprint should be larger, since it doesn't know the original Z
assert!(ri.contains_box(&r), "Inverse {:?}", ri);
}
}
fn validate_convert(xref: &LayoutTransform) {
let so = ScaleOffset::from_transform(xref).unwrap();
let xf = so.to_transform();
assert!(xref.approx_eq(&xf));
}
#[test]
fn negative_scale_map_unmap() {
let xref = LayoutTransform::scale(1.0, -1.0, 1.0)
.pre_translate(LayoutVector3D::new(124.0, 38.0, 0.0));
let so = ScaleOffset::from_transform(&xref).unwrap();
let local_rect = LayoutRect {
min: LayoutPoint::new(50.0, -100.0),
max: LayoutPoint::new(250.0, 300.0),
};
let mapped_rect = so.map_rect::<LayoutPixel, DevicePixel>(&local_rect);
let xf_rect = project_rect(
&xref,
&local_rect,
&LayoutRect::max_rect(),
).unwrap();
assert!(mapped_rect.min.x.approx_eq(&xf_rect.min.x));
assert!(mapped_rect.min.y.approx_eq(&xf_rect.min.y));
assert!(mapped_rect.max.x.approx_eq(&xf_rect.max.x));
assert!(mapped_rect.max.y.approx_eq(&xf_rect.max.y));
let unmapped_rect = so.unmap_rect::<DevicePixel, LayoutPixel>(&mapped_rect);
assert!(unmapped_rect.min.x.approx_eq(&local_rect.min.x));
assert!(unmapped_rect.min.y.approx_eq(&local_rect.min.y));
assert!(unmapped_rect.max.x.approx_eq(&local_rect.max.x));
assert!(unmapped_rect.max.y.approx_eq(&local_rect.max.y));
}
#[test]
fn scale_offset_convert() {
let xref = LayoutTransform::translation(130.0, 200.0, 0.0);
validate_convert(&xref);
let xref = LayoutTransform::scale(13.0, 8.0, 1.0);
validate_convert(&xref);
let xref = LayoutTransform::scale(0.5, 0.5, 1.0)
.pre_translate(LayoutVector3D::new(124.0, 38.0, 0.0));
validate_convert(&xref);
let xref = LayoutTransform::scale(30.0, 11.0, 1.0)
.then_translate(vec3(50.0, 240.0, 0.0));
validate_convert(&xref);
}
fn validate_inverse(xref: &LayoutTransform) {
let s0 = ScaleOffset::from_transform(xref).unwrap();
let s1 = s0.inverse().pre_transform(&s0);
assert!((s1.scale.x - 1.0).abs() < NEARLY_ZERO &&
(s1.scale.y - 1.0).abs() < NEARLY_ZERO &&
s1.offset.x.abs() < NEARLY_ZERO &&
s1.offset.y.abs() < NEARLY_ZERO,
"{:?}",
s1);
}
#[test]
fn scale_offset_inverse() {
let xref = LayoutTransform::translation(130.0, 200.0, 0.0);
validate_inverse(&xref);
let xref = LayoutTransform::scale(13.0, 8.0, 1.0);
validate_inverse(&xref);
let xref = LayoutTransform::translation(124.0, 38.0, 0.0).
then_scale(0.5, 0.5, 1.0);
validate_inverse(&xref);
let xref = LayoutTransform::scale(30.0, 11.0, 1.0)
.then_translate(vec3(50.0, 240.0, 0.0));
validate_inverse(&xref);
}
fn validate_accumulate(x0: &LayoutTransform, x1: &LayoutTransform) {
let x = x1.then(&x0);
let s0 = ScaleOffset::from_transform(x0).unwrap();
let s1 = ScaleOffset::from_transform(x1).unwrap();
let s = s0.pre_transform(&s1).to_transform();
assert!(x.approx_eq(&s), "{:?}\n{:?}", x, s);
}
#[test]
fn scale_offset_accumulate() {
let x0 = LayoutTransform::translation(130.0, 200.0, 0.0);
let x1 = LayoutTransform::scale(7.0, 3.0, 1.0);
validate_accumulate(&x0, &x1);
}
#[test]
fn scale_offset_invalid_scale() {
let s0 = ScaleOffset::new(0.0, 1.0, 10.0, 20.0);
let i0 = s0.inverse();
assert_eq!(i0, ScaleOffset::new(0.0, 0.0, 0.0, 0.0));
let s1 = ScaleOffset::new(1.0, 0.0, 10.0, 20.0);
let i1 = s1.inverse();
assert_eq!(i1, ScaleOffset::new(0.0, 0.0, 0.0, 0.0));
}
#[test]
fn polygon_clip_is_left_of_point() {
// Define points of a line through (1, -3) and (-2, 6) to test against.
// If the triplet consisting of these two points and the test point
// form a counter-clockwise triangle, then the test point is on the
// left. The easiest way to visualize this is with an "ascending"
// line from low-Y to high-Y.
let p0_x = 1.0;
let p0_y = -3.0;
let p1_x = -2.0;
let p1_y = 6.0;
// Test some points to the left of the line.
assert!(is_left_of_line(-9.0, 0.0, p0_x, p0_y, p1_x, p1_y) > 0.0);
assert!(is_left_of_line(-1.0, 1.0, p0_x, p0_y, p1_x, p1_y) > 0.0);
assert!(is_left_of_line(1.0, -4.0, p0_x, p0_y, p1_x, p1_y) > 0.0);
// Test some points on the line.
assert!(is_left_of_line(-3.0, 9.0, p0_x, p0_y, p1_x, p1_y) == 0.0);
assert!(is_left_of_line(0.0, 0.0, p0_x, p0_y, p1_x, p1_y) == 0.0);
assert!(is_left_of_line(100.0, -300.0, p0_x, p0_y, p1_x, p1_y) == 0.0);
// Test some points to the right of the line.
assert!(is_left_of_line(0.0, 1.0, p0_x, p0_y, p1_x, p1_y) < 0.0);
assert!(is_left_of_line(-4.0, 13.0, p0_x, p0_y, p1_x, p1_y) < 0.0);
assert!(is_left_of_line(5.0, -12.0, p0_x, p0_y, p1_x, p1_y) < 0.0);
}
#[test]
fn polygon_clip_contains_point() {
// We define the points of a self-overlapping polygon, which we will
// use to create polygons with different windings and fill rules.
let p0 = LayoutPoint::new(4.0, 4.0);
let p1 = LayoutPoint::new(6.0, 4.0);
let p2 = LayoutPoint::new(4.0, 7.0);
let p3 = LayoutPoint::new(2.0, 1.0);
let p4 = LayoutPoint::new(8.0, 1.0);
let p5 = LayoutPoint::new(6.0, 7.0);
let poly_clockwise_nonzero = PolygonKey::new(
&[p5, p4, p3, p2, p1, p0].to_vec(), FillRule::Nonzero
);
let poly_clockwise_evenodd = PolygonKey::new(
&[p5, p4, p3, p2, p1, p0].to_vec(), FillRule::Evenodd
);
let poly_counter_clockwise_nonzero = PolygonKey::new(
&[p0, p1, p2, p3, p4, p5].to_vec(), FillRule::Nonzero
);
let poly_counter_clockwise_evenodd = PolygonKey::new(
&[p0, p1, p2, p3, p4, p5].to_vec(), FillRule::Evenodd
);
// We define a rect that provides a bounding clip area of
// the polygon.
let rect = LayoutRect::from_size(LayoutSize::new(10.0, 10.0));
// And we'll test three points of interest.
let p_inside_once = LayoutPoint::new(5.0, 3.0);
let p_inside_twice = LayoutPoint::new(5.0, 5.0);
let p_outside = LayoutPoint::new(9.0, 9.0);
// We should get the same results for both clockwise and
// counter-clockwise polygons.
// For nonzero polygons, the inside twice point is considered inside.
for poly_nonzero in vec![poly_clockwise_nonzero, poly_counter_clockwise_nonzero].iter() {
assert_eq!(polygon_contains_point(&p_inside_once, &rect, &poly_nonzero), true);
assert_eq!(polygon_contains_point(&p_inside_twice, &rect, &poly_nonzero), true);
assert_eq!(polygon_contains_point(&p_outside, &rect, &poly_nonzero), false);
}
// For evenodd polygons, the inside twice point is considered outside.
for poly_evenodd in vec![poly_clockwise_evenodd, poly_counter_clockwise_evenodd].iter() {
assert_eq!(polygon_contains_point(&p_inside_once, &rect, &poly_evenodd), true);
assert_eq!(polygon_contains_point(&p_inside_twice, &rect, &poly_evenodd), false);
assert_eq!(polygon_contains_point(&p_outside, &rect, &poly_evenodd), false);
}
}
// Ensures that mapping or unmapping an input rect with negative size returns a rect
// with size 0, and the origin transformed as expected.
#[test]
fn map_unmap_negative_size() {
let scale_offset = ScaleOffset::new(2.0, 2.0, 1.0, 1.0);
let rect = Box2D::new(Point2D::new(5.0, 5.0), Point2D::new(0.0, 0.0));
let mapped_rect: Box2D<f32> = scale_offset.map_rect(&rect);
assert_eq!(mapped_rect, Box2D::new(Point2D::new(11.0, 11.0), Point2D::new(11.0, 11.0)));
let unmapped_rect: Box2D<f32> = scale_offset.unmap_rect(&rect);
assert_eq!(unmapped_rect, Box2D::new(Point2D::new(2.0, 2.0), Point2D::new(2.0, 2.0)));
}
// Ensures that mapping or unmapping two adjoining input rects returns two rects that
// are still adjoining.
#[test]
fn map_unmap_adjoining_rects() {
let so = ScaleOffset::new(0.3, 0.3, 0.0, 0.0);
let p1 = Point2D::new(15.0, 15.0);
let p2 = Point2D::new(45.0, 45.0);
let p3 = Point2D::new(75.0, 75.0);
let rect_1 = Box2D::new(p1, p2);
let rect_2 = Box2D::new(p2, p3);
let mapped_rect_1: Box2D<f32> = so.map_rect(&rect_1);
let mapped_rect_2: Box2D<f32> = so.map_rect(&rect_2);
assert_eq!(mapped_rect_1.max, mapped_rect_2.min);
let unmapped_rect_1: Box2D<f32> = so.unmap_rect(&rect_1);
let unmapped_rect_2: Box2D<f32> = so.unmap_rect(&rect_2);
assert_eq!(unmapped_rect_1.max, unmapped_rect_2.min);
}
}
pub trait MaxRect {
fn max_rect() -> Self;
}
impl MaxRect for DeviceIntRect {
fn max_rect() -> Self {
DeviceIntRect::from_origin_and_size(
DeviceIntPoint::new(i32::MIN / 2, i32::MIN / 2),
DeviceIntSize::new(i32::MAX, i32::MAX),
)
}
}
impl<U> MaxRect for Rect<f32, U> {
fn max_rect() -> Self {
// Having an unlimited bounding box is fine up until we try
// to cast it to `i32`, where we get `-2147483648` for any
// values larger than or equal to 2^31.
//
// Note: clamping to i32::MIN and i32::MAX is not a solution,
// with explanation left as an exercise for the reader.
const MAX_COORD: f32 = 1.0e9;
Rect::new(
Point2D::new(-MAX_COORD, -MAX_COORD),
Size2D::new(2.0 * MAX_COORD, 2.0 * MAX_COORD),
)
}
}
impl<U> MaxRect for Box2D<f32, U> {
fn max_rect() -> Self {
// Having an unlimited bounding box is fine up until we try
// to cast it to `i32`, where we get `-2147483648` for any
// values larger than or equal to 2^31.
//
// Note: clamping to i32::MIN and i32::MAX is not a solution,
// with explanation left as an exercise for the reader.
const MAX_COORD: f32 = 1.0e9;
Box2D::new(
Point2D::new(-MAX_COORD, -MAX_COORD),
Point2D::new(MAX_COORD, MAX_COORD),
)
}
}
pub fn project_rect<F, T>(
transform: &Transform3D<f32, F, T>,
rect: &Box2D<f32, F>,
bounds: &Box2D<f32, T>,
) -> Option<Box2D<f32, T>>
where F: fmt::Debug
{
let homogens = [
transform.transform_point2d_homogeneous(rect.top_left()),
transform.transform_point2d_homogeneous(rect.top_right()),
transform.transform_point2d_homogeneous(rect.bottom_left()),
transform.transform_point2d_homogeneous(rect.bottom_right()),
];
// Note: we only do the full frustum collision when the polygon approaches the camera plane.
// Otherwise, it will be clamped to the screen bounds anyway.
if homogens.iter().any(|h| h.w <= 0.0 || h.w.is_nan()) {
let mut clipper = Clipper::new();
let polygon = Polygon::from_rect(rect.to_rect().cast().cast_unit(), 1);
let planes = match Clipper::<usize>::frustum_planes(
&transform.cast_unit().cast(),
Some(bounds.to_rect().cast_unit().to_f64()),
) {
Ok(planes) => planes,
Err(..) => return None,
};
for plane in planes {
clipper.add(plane);
}
let results = clipper.clip(polygon);
if results.is_empty() {
return None
}
Some(Box2D::from_points(results
.into_iter()
// filter out parts behind the view plane
.flat_map(|poly| &poly.points)
.map(|p| {
let mut homo = transform.transform_point2d_homogeneous(p.to_2d().to_f32().cast_unit());
homo.w = homo.w.max(0.00000001); // avoid infinite values
homo.to_point2d().unwrap()
})
))
} else {
// we just checked for all the points to be in positive hemisphere, so `unwrap` is valid
Some(Box2D::from_points(&[
homogens[0].to_point2d().unwrap(),
homogens[1].to_point2d().unwrap(),
homogens[2].to_point2d().unwrap(),
homogens[3].to_point2d().unwrap(),
]))
}
}
/// Run the first callback over all elements in the array. If the callback returns true,
/// the element is removed from the array and moved to a second callback.
///
/// This is a simple implementation waiting for Vec::drain_filter to be stable.
/// When that happens, code like:
///
/// let filter = |op| {
/// match *op {
/// Enum::Foo | Enum::Bar => true,
/// Enum::Baz => false,
/// }
/// };
/// drain_filter(
/// &mut ops,
/// filter,
/// |op| {
/// match op {
/// Enum::Foo => { foo(); }
/// Enum::Bar => { bar(); }
/// Enum::Baz => { unreachable!(); }
/// }
/// },
/// );
///
/// Can be rewritten as:
///
/// let filter = |op| {
/// match *op {
/// Enum::Foo | Enum::Bar => true,
/// Enum::Baz => false,
/// }
/// };
/// for op in ops.drain_filter(filter) {
/// match op {
/// Enum::Foo => { foo(); }
/// Enum::Bar => { bar(); }
/// Enum::Baz => { unreachable!(); }
/// }
/// }
///
pub fn drain_filter<T, Filter, Action>(
vec: &mut Vec<T>,
mut filter: Filter,
mut action: Action,
)
where
Filter: FnMut(&mut T) -> bool,
Action: FnMut(T)
{
let mut i = 0;
while i != vec.len() {
if filter(&mut vec[i]) {
action(vec.remove(i));
} else {
i += 1;
}
}
}
#[derive(Debug)]
pub struct Recycler {
pub num_allocations: usize,
}
impl Recycler {
/// Maximum extra capacity that a recycled vector is allowed to have. If the actual capacity
/// is larger, we re-allocate the vector storage with lower capacity.
const MAX_EXTRA_CAPACITY_PERCENT: usize = 200;
/// Minimum extra capacity to keep when re-allocating the vector storage.
const MIN_EXTRA_CAPACITY_PERCENT: usize = 20;
/// Minimum sensible vector length to consider for re-allocation.
const MIN_VECTOR_LENGTH: usize = 16;
pub fn new() -> Self {
Recycler {
num_allocations: 0,
}
}
/// Clear a vector for re-use, while retaining the backing memory buffer. May shrink the buffer
/// if it's currently much larger than was actually used.
pub fn recycle_vec<T>(&mut self, vec: &mut Vec<T>) {
let extra_capacity = (vec.capacity() - vec.len()) * 100 / vec.len().max(Self::MIN_VECTOR_LENGTH);
if extra_capacity > Self::MAX_EXTRA_CAPACITY_PERCENT {
// Reduce capacity of the buffer if it is a lot larger than it needs to be. This prevents
// a frame with exceptionally large allocations to cause subsequent frames to retain
// more memory than they need.
//TODO: use `shrink_to` when it's stable
*vec = Vec::with_capacity(vec.len() + vec.len() * Self::MIN_EXTRA_CAPACITY_PERCENT / 100);
self.num_allocations += 1;
} else {
vec.clear();
}
}
}
/// Record the size of a data structure to preallocate a similar size
/// at the next frame and avoid growing it too many time.
#[derive(Copy, Clone, Debug)]
pub struct Preallocator {
size: usize,
}
impl Preallocator {
pub fn new(initial_size: usize) -> Self {
Preallocator {
size: initial_size,
}
}
/// Record the size of a vector to preallocate it the next frame.
pub fn record_vec<T>(&mut self, vec: &[T]) {
let len = vec.len();
if len > self.size {
self.size = len;
} else {
self.size = (self.size + len) / 2;
}
}
/// The size that we'll preallocate the vector with.
pub fn preallocation_size(&self) -> usize {
// Round up to multiple of 16 to avoid small tiny
// variations causing reallocations.
(self.size + 15) & !15
}
/// Preallocate vector storage.
///
/// The preallocated amount depends on the length recorded in the last
/// record_vec call.
pub fn preallocate_vec<T>(&self, vec: &mut Vec<T>) {
let len = vec.len();
let cap = self.preallocation_size();
if len < cap {
vec.reserve(cap - len);
}
}
/// Preallocate vector storage.
///
/// The preallocated amount depends on the length recorded in the last
/// record_vec call.
pub fn preallocate_framevec<T>(&self, vec: &mut FrameVec<T>) {
let len = vec.len();
let cap = self.preallocation_size();
if len < cap {
vec.reserve(cap - len);
}
}
}
impl Default for Preallocator {
fn default() -> Self {
Self::new(0)
}
}
/// Computes the scale factors of this matrix; that is,
/// the amounts each basis vector is scaled by.
///
/// This code comes from gecko gfx/2d/Matrix.h with the following
/// modifications:
///
/// * Removed `xMajor` parameter.
/// * All arithmetics is done with double precision.
pub fn scale_factors<Src, Dst>(
mat: &Transform3D<f32, Src, Dst>
) -> (f32, f32) {
let m11 = mat.m11 as f64;
let m12 = mat.m12 as f64;
// Determinant is just of the 2D component.
let det = m11 * mat.m22 as f64 - m12 * mat.m21 as f64;
if det == 0.0 {
return (0.0, 0.0);
}
// ignore mirroring
let det = det.abs();
let major = (m11 * m11 + m12 * m12).sqrt();
let minor = if major != 0.0 { det / major } else { 0.0 };
(major as f32, minor as f32)
}
#[test]
fn scale_factors_large() {
let mat = Transform3D::<f32, (), ()>::new(
1.6534229920333123e27, 3.673100922561787e27, 0.0, 0.0,
-3.673100922561787e27, 1.6534229920333123e27, 0.0, 0.0,
0.0, 0.0, 1.0, 0.0,
-828140552192.0, -1771307401216.0, 0.0, 1.0,
);
let (major, minor) = scale_factors(&mat);
assert!(major.is_normal() && minor.is_normal());
}
/// Clamp scaling factor to a power of two.
///
/// This code comes from gecko gfx/thebes/gfxUtils.cpp with the following
/// modification:
///
/// * logs are taken in base 2 instead of base e.
pub fn clamp_to_scale_factor(val: f32, round_down: bool) -> f32 {
// Arbitary scale factor limitation. We can increase this
// for better scaling performance at the cost of worse
// quality.
const SCALE_RESOLUTION: f32 = 2.0;
// Negative scaling is just a flip and irrelevant to
// our resolution calculation.
let val = val.abs();
let (val, inverse) = if val < 1.0 {
(1.0 / val, true)
} else {
(val, false)
};
let power = val.log2() / SCALE_RESOLUTION.log2();
// If power is within 1e-5 of an integer, round to nearest to
// prevent floating point errors, otherwise round up to the
// next integer value.
let power = if (power - power.round()).abs() < 1e-5 {
power.round()
} else if inverse != round_down {
// Use floor when we are either inverted or rounding down, but
// not both.
power.floor()
} else {
// Otherwise, ceil when we are not inverted and not rounding
// down, or we are inverted and rounding down.
power.ceil()
};
let scale = SCALE_RESOLUTION.powf(power);
if inverse {
1.0 / scale
} else {
scale
}
}
/// Rounds a value up to the nearest multiple of mul
pub fn round_up_to_multiple(val: usize, mul: NonZeroUsize) -> usize {
match val % mul.get() {
0 => val,
rem => val - rem + mul.get(),
}
}
#[macro_export]
macro_rules! c_str {
($lit:expr) => {
unsafe {
std::ffi::CStr::from_ptr(concat!($lit, "\0").as_ptr()
as *const std::os::raw::c_char)
}
}
}
/// This is inspired by the `weak-table` crate.
/// It holds a Vec of weak pointers that are garbage collected as the Vec
pub struct WeakTable {
inner: Vec<std::sync::Weak<Vec<u8>>>
}
impl WeakTable {
pub fn new() -> WeakTable {
WeakTable { inner: Vec::new() }
}
pub fn insert(&mut self, x: std::sync::Weak<Vec<u8>>) {
if self.inner.len() == self.inner.capacity() {
self.remove_expired();
// We want to make sure that we change capacity()
// even if remove_expired() removes some entries
// so that we don't repeatedly hit remove_expired()
if self.inner.len() * 3 < self.inner.capacity() {
// We use a different multiple for shrinking then
// expanding so that we we don't accidentally
// oscilate.
self.inner.shrink_to_fit();
} else {
// Otherwise double our size
self.inner.reserve(self.inner.len())
}
}
self.inner.push(x);
}
fn remove_expired(&mut self) {
self.inner.retain(|x| x.strong_count() > 0)
}
pub fn iter(&self) -> impl Iterator<Item = Arc<Vec<u8>>> + '_ {
self.inner.iter().filter_map(|x| x.upgrade())
}
}
#[test]
fn weak_table() {
let mut tbl = WeakTable::new();
let mut things = Vec::new();
let target_count = 50;
for _ in 0..target_count {
things.push(Arc::new(vec![4]));
}
for i in &things {
tbl.insert(Arc::downgrade(i))
}
assert_eq!(tbl.inner.len(), target_count);
drop(things);
assert_eq!(tbl.iter().count(), 0);
// make sure that we shrink the table if it gets too big
// by adding a bunch of dead items
for _ in 0..target_count*2 {
tbl.insert(Arc::downgrade(&Arc::new(vec![5])))
}
assert!(tbl.inner.capacity() <= 4);
}
#[test]
fn scale_offset_pre_post() {
let a = ScaleOffset::new(1.0, 2.0, 3.0, 4.0);
let b = ScaleOffset::new(5.0, 6.0, 7.0, 8.0);
assert_eq!(a.then(&b), b.pre_transform(&a));
assert_eq!(a.then_scale(10.0), a.then(&ScaleOffset::from_scale(Vector2D::new(10.0, 10.0))));
assert_eq!(a.pre_scale(10.0), a.pre_transform(&ScaleOffset::from_scale(Vector2D::new(10.0, 10.0))));
}