servo/euclid

Geometry primitives (basic linear algebra) for Rust

The Servo Parallel Browser Engine Project

Servo is a prototype web browser engine written in the Rust language. It is currently developed on 64-bit macOS, 64-bit Linux, 64-bit Windows, and Android.

Servo welcomes contribution from everyone. See CONTRIBUTING.md and HACKING_QUICKSTART.md for help getting started.

Visit the Servo Project page for news and guides.

Getting Servo

git clone https://github.com/servo/servo
cd servo

• Your CARGO_HOME needs to point to (or be in) the same drive as your Servo repository (#28530).
• The Servo repository is big! If you have an unreliable network connection, consider making a shallow clone.

Build Setup

• macOS
• Linux
• Windows
• Android

If these instructions fail or you would like to install dependencies manually, try the manual build setup.

macOS

• Ensure that the version showed by python --version is >= 3.10:
• Install Xcode
• Install Homebrew
• Run curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
• Run ./mach bootstrap
  Note: This will install the recommended version of GStreamer globally on your system.

Linux

• Run curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
• Install Python (version >= 3.10):
  • Debian-like: Run sudo apt install python3-pip python3-venv
  • Fedora: Run sudo dnf install python3 python3-pip python3-devel
  • Arch: Run sudo pacman -S --needed python python-pip
  • Gentoo: Run sudo emerge dev-python/pip
• Run ./mach bootstrap

Windows

• Download and run rustup-init.exe
• Make sure to select Quick install via the Visual Studio Community installer or otherwise install Visual Studio 2022.
• In the Visual Studio Installer ensure the following components are installed for Visual Studio 2022:
  • Windows 10 SDK (10.0.19041.0) (Microsoft.VisualStudio.Component.Windows10SDK.19041)
  • MSVC v143 - VS 2022 C++ x64/x86 build tools (Latest) (Microsoft.VisualStudio.Component.VC.Tools.x86.x64)
  • C++ ATL for latest v143 build tools (x86 & x64) (Microsoft.VisualStudio.Component.VC.ATL)
  • C++ MFC for latest v143 build tools (x86 & x64) (Microsoft.VisualStudio.Component.VC.ATLMFC)
• Install chocolatey
• Install Python 3.11
• Run mach bootstrap
  • This will install CMake, Git, and Ninja via choco in an Administrator console. Allow the scripts to run and once the operation finishes, close the new console.
• Run refreshenv

See also Windows Troubleshooting Tips.

Android

• Ensure that the following environment variables are set:
  • ANDROID_SDK_ROOT
  • ANDROID_NDK_ROOT: $ANDROID_SDK_ROOT/ndk/25.2.9519653/ ANDROID_SDK_ROOT can be any directory (such as ~/android-sdk). All of the Android build dependencies will be installed there.
• Install the latest version of the Android command-line tools to $ANDROID_SDK_ROOT/cmdline-tools/latest.
• Run the following command to install the necessary components:

  sudo $ANDROID_SDK_ROOT/cmdline-tools/latest/bin/sdkmanager --install
   "build-tools;33.0.2" \
   "emulator" \
   "ndk;25.2.9519653" \
   "platform-tools" \
   "platforms;android-33" \
   "system-images;android-33;google_apis;x86_64"

For information about building and running the Android build, see the Android documentation.

Building

Servo is built with Cargo, the Rust package manager. We also use Mozilla's Mach tools to orchestrate the build and other tasks. You can call Mach like this:

On Unix systems:

./mach [command] [arguments]

On Windows Commandline:

mach.bat [command] [arguments]

The examples below will use Unix, but the same applies to Windows.

The Rust compiler

Servo's build system uses rustup.rs to automatically download a Rust compiler. This is a specific version of Rust Nightly determined by the rust-toolchain.toml file.

Normal build

To build Servo in development mode. This is useful for development, but the resulting binary is very slow:

./mach build --dev
./mach run tests/html/about-mozilla.html

Release build

For benchmarking, performance testing, or real-world use. Add the --release flag to create an optimized build:

./mach build --release
./mach run --release tests/html/about-mozilla.html

Android build

For an armv7 Android build run the following command.

./mach build --android

Checking for build errors, without building

If you’re making changes to one crate that cause build errors in another crate, consider this instead of a full build:

./mach check

It will run cargo check, which runs the analysis phase of the compiler (and so shows build errors if any) but skips the code generation phase. This can be a lot faster than a full build, though of course it doesn’t produce a binary you can run.

Running

Run Servo with the command:

./servo [url] [arguments] # if you run with nightly build
./mach run [url] [arguments] # if you run with mach

# For example
./mach run https://www.google.com

Commandline Arguments

• -p INTERVAL turns on the profiler and dumps info to the console every INTERVAL seconds
• -s SIZE sets the tile size for painting; defaults to 512
• -z disables all graphical output; useful for running JS / layout tests
• -Z help displays useful output to debug servo

Keyboard Shortcuts

• Ctrl+L opens URL prompt (Cmd+L on Mac)
• Ctrl+R reloads current page (Cmd+R on Mac)
• Ctrl+- zooms out (Cmd+- on Mac)
• Ctrl+= zooms in (Cmd+= on Mac)
• Alt+left arrow goes backwards in the history (Cmd+left arrow on Mac)
• Alt+right arrow goes forwards in the history (Cmd+right arrow on Mac)
• Esc or Ctrl+Q exits Servo (Cmd+Q on Mac)

Runtime dependencies

Linux

• GStreamer >=1.18
• gst-plugins-base >=1.18
• gst-plugins-good >=1.18
• gst-plugins-bad >=1.18
• gst-plugins-ugly >=1.18
• libXcursor
• libXrandr
• libXi
• libxkbcommon
• vulkan-loader

Developing

There are lots of mach commands you can use. You can list them with ./mach --help.

The generated documentation can be found on https://doc.servo.org/servo/index.html

euclid's Issues

Make the serde dependency optional.

It's quite a heavy-weight dependency that isn't necessarily used with euclid outside of servo.

Proposal: Add Ray3D type

Just saw this: https://github.com/servo/webrender/blob/f299539c4f36834b633d6a6bb7b34cd8acef4574/src/geometry.rs

It might make sense to move that arithmetic into this crate? I imagine a new struct Ray3D that has a method fn intersects(self, r: Rect) -> bool. Thoughts? I'd be happy to make the changes if others agree.

TypedRect::from_points soundness

It actually produces the bounding rectangle of points, yet the name does not imply that.
I suggest having separate methods for the inner/outer rectangle produced, and deprecate the original from_points.
cc @nical

[RFC] MoveFactor

Similarly to how we have scale factors that change the coordinate space type, we need to have the move factors (from A->B), so that translate(move_factor) changes the coordinate space from A to B, and translate(-move_factor) changes it from B to A. This would be very useful for jumping between reference frame / clip node / scroll node coordinate systems.

cc @mrobinson @nical

Make cast methods infallible and add try_cast for checked casts.

Users of these methods tend to just unwrap, so let's have the ergonomics of a short name for the common pattern and a longer name for the cases where we go through the boilerplate of checking the result.

This would be a B͇ŗe̸̗͉a̰̖̼͚̭k̯͙̱i̧̩̞̹͕͈̹̞ṇ̯͘g̴ ̘̗͖̥͝c̸͉h̘̯͚̖̥̣ͅa҉͉͖̥̲̮n̛͚̟͎̝͇g͎e̕.

Publish on crates.io?

Just wanted to know if you plan to publish this repo on crates.io, now gleam et al are being moved.

The only problem I see is that the geom crate name is already taken.

cc @metajack @Manishearth @SimonSapin

Create generic versions of Matrix and Point objects, parametrised by field type

See servo/servo#8509 (comment). The W3C geometry spec requires 64bit floats, while the existing Euclid library only supports f32 values.

The new versions should be more consistently named. For example there are existing objects called Matrix4 and Matrix2D.

The existing objects can then become aliases to the new ones, and be marked as deprecated.

Add a way to convert Transform2D into Transform3D

There doesn't appear to be any function to promote a 2D transform into a 3D transform. This would be useful.

Add method to subtract TypedSideOffsets2D from Rect

In servo there is currently a function called calculate_inner_bounds that takes a rectangle and side offsets to subtract the offsets from the rectangle and return a new one. This is for example useful if you have a big rect and want to subtract the borders to get the inner rect. Do you think that this is a useful addition to euclid? It could be called TypedRect::inner_rect(&self, offsets: TypedSideOffsets2D) -> TypedRect.

/// Subtract offsets from a bounding box.
///
/// As an example if the bounds are the border-box and the border
/// is provided as offsets the result will be the padding-box.
fn calculate_inner_bounds(mut bounds: Rect<Au>, offsets: SideOffsets2D<Au>) -> Rect<Au> {
    bounds.origin.x += offsets.left;
    bounds.origin.y += offsets.top;
    bounds.size.width -= offsets.horizontal();
    bounds.size.height -= offsets.vertical();
    bounds
}

Breaking change in euclid 0.11.2

#182 is a breaking change that was accidentally published in a patch version. We should yank version 0.11.2, then either re-publish it as 0.12.0 or re-add the old method and publish it as 0.11.3.

TypedRect from_points needs to use Borrow

The current signature of from_points is designed for the case where we already have those points in some sort of storage, but it's not a slice. It doesn't work for the case where we try to generate the points on the fly, since those don't live long enough.
In order to address it, the following signature can be used:

fn from_points<I>(points: I) -> Self
where
    I: IntoIterator,
    I: Iter: Borrow<TypedPoint>
{
...
}

I wonder if we can even consider this a non-breaking change, given that the old use cases are covered by this new API.

Figure out a good rule of thumb about what should be passed by value/ref.

...and apply it consistently.

For example, I think that we should pass rectangles by reference by default. But maybe we want to keep passing smaller things by value? or just everything by reference. In anyway, a simple rule applied consistently would make the API a lot nicer.

This would be a B͇ŗe̸̗͉a̰̖̼͚̭k̯͙̱i̧̩̞̹͕͈̹̞ṇ̯͘g̴ ̘̗͖̥͝c̸͉h̘̯͚̖̥̣ͅa҉͉͖̥̲̮n̛͚̟͎̝͇g͎e̕

Multiply Lengths with Scalars

Right now a Length can only be multiplied and divided with a ScaleFactor. But for the simple case where I want to calculate something like double or half a length, it would be nice to be able to write my_length * 0.5. This would multiply/divide the value but keep the unit.

On the other hand, Points and other types can be multiplied with either scalars or with ScaleFactor. Is the lack of this for Length a design decision or an oversight? In the latter case, I'd be happy to write a PR.

Document why Matrix4 and other types are reversed with regard to the WhatWG specs

It confuses me why they are reversed, and it could confuse other people in the future.

Proposal: implement strongly typed units the way Gecko does

Euclid currently implements strongly typed units by wrapping the Point/Rect/Matrix/etc.'s scalar type in a wrapper that implements the same type of arithmetic operations as the basic types (f32, i32, etc). I am referring to the Length and ScaleFactor types. This approach lets most of the vector and matrix types not have to deal with units, which is nice. However, I believe that the way gecko implements strongly typed units has several advantages over euclid's current approach.

I put together a little experiment here: https://github.com/nical/misc/tree/master/math_api_experiments/src

In v1.rs I implement a very small subset of an hypothetical vector math library (Matrix4x4 and Point3D structs with just a handful of methods), and in v2.rs the same feature set using euclid's approach.
One of the features implemented in both cases does not currently exist in euclid: It is the ability to express that a matrix transforms points from a space to another (for example multiplying a Matrix<WorldSpace, ScreenSpace> with a Point3D would return a Point3D. Likewise multiplying matrices use the source and destination spaces so that Matrix<Foo, Bar> * Matrix<Bar, Baz> = Matrix<Foo, Baz>.
I believe that this is really useful feature to have, we can come back to why I think that is if there is any disagreement there.

Back to the experiment linked above, it is interesting to compare the two implementations. My goal here being to convince people that v1.rs is the best approach, I invite you to help me the other approach as much as possible to provide a fair comparison:

Advantages of gecko's approach (v1.rs):

• The code is a lot smaller and simpler to understand. It was also a lot simpler to write. I actually had a hard time implementing the same features in v2.rs.
• When units don't match compiler error refer to the Matrix type while v1.rs (euclid-like) refers to the underlying TransformComponent (a beefier version of ScaleFactor if you will) which is not obvious for people mistakenly adding a CssPoint to a LayerPoint withhout knowing euclid's internals.
• The api is a more ergonomic. There are a few examples of that in the code towards the bottom of the files v1.rs and v2.rs. See generic_over_the_unit_f32 for example where euclid's approach will force you to wrap and unwrap the scalar values of your vectors and matrices every time you need to interface with third party code that deals directly with specific types like floats). This is problematic because it means Point2D is a lot nicer to use than Point2D<Length<CssPixel, f32>>, which encourages using the non-typed versions to get the work done quickly. With gecko's approach, whatever the unit, if a vector is using floats my_vec.x is always a float, period.
• This is debatable, but it is gecko's approach which means it would make onboarding for gecko devs easier (to be honest, I think the discussion should be on focused on the merits of the approaches themselves rather than technical debt, but it's a bit like icing on the cake).

Advantage(s) of eculid's approach (v2.rs):

• It is already implemented in euclid (except the ability for matrices to express a transformation from a space to the other) but again this is technical debt.

When I brought this up on irc, one interesting concern was that Gecko's approach puts the units in the vector and matrix types themselves, but some users of euclid may not want to use the strongly typed units feature. In reality for these users, the experience is exactly the same either way (see the examples in v1.rs and v2.rs). Since rust has default generic parameters, using Point3D is equivalent to Point3D<f32, Untyped> and thus the API is identical with both approaches for users of the library that don't use units.

Having hacked on Gecko for years I am pretty happy with the way Moz2D's vectors work. My experience trying to use euclid with units in my pet projects has been less pleasant (arguably I haven't used it nearly as much).

Sorry, this is a bit of a long piece. I'll be happy to help with converting euclid if you guys are interested in this.

Drop rustc-serialize dependency

It has been deprecated: announcement.

Is there any functionality you would require from Serde or another library before this would be possible?

Make euclid build on stable

Euclid currently don't build on stable because it uses some #{features(...)] stuff. Most of the library don't use these features so it'd be nice to be able to opt into a subset that works on stable (using cargo features).

Proposal: Use Gecko's convention for matrices.

Rather than detailing all of the differences, I encourage you to look at Gecko's matrix classes.

It is terribly dangerous to have Servo and Gecko use different conventions for matrices. Especially since the plan is to share more code in the future. Unless there are very good reasons for euclid's matrices to be the way they are, it is more realistic to change Servo than Gecko for obvious reasons (feel free to ask if you want to argue about that).

Also gecko's matrix multiplication works a lot more naturally with units when building transforms up, because Mat<A,B> * Mat<B,C> * Mat<C,D> = Mat<A,D> which reads nicely from left to right, while euclid goes Mat<C, D> * Mat<B, C> * Mat<A,B> = Mat<A, D>. But honestly, the massive interop foot-gun between servo and gecko is what terrifies me.

This is a much bigger change than the units discussion. Basically everything in servo that uses matrices is affected in non-trivial ways.

I apologize for my "We gotta change everything" attitude between this proposal and the other one. I hope that there will be more direct cooperation between gecko and servo devs (at least on the gfx side) and it simply cannot go well if the basic math structures that are all over the rendering engines aren't compatible between the two. I also believe that gecko's math is well battle-tested by now and has grown into a better design than euclid (in the way units are handled and other things that I haven't nagged you about yet).
As a (meager) consolation, I am willing to help with implementing these changes as opposed to just starting bikesheds.

Question: invalid calculation of Point3D transformation?

When writing code with euclid, I discovered that Point3Ds were transformed as if they were Vector3D, thus making it impossible to perform translation transforms on Point3Ds. Normally, when working with affine transformations in three dimensions, points are defined as P = (x, y, z, 1) whereas vectors are defined as V = (x, y, z, 0), thus allowing points to be translated and vectors will remain unaffected. In euclid, this seems not to be the case. Is this expected behaviour? What is the reasoning behind this? I used the following test function to check the behaviour.

use euclid::{Transform3D, Point3D, Vector3D};

#[test]
fn test_point_vs_vector() {
    let m: Transform3D<f64> = Transform3D::row_major(
        1.0, 0.0, 0.0, 0.0,
        0.0, 1.0, 0.0, 0.0,
        0.0, 0.0, 1.0, -5.0,
        0.0, 0.0, 0.0, 1.0
    );
    let p: Point3D<f64> = Point3D::new(1.0, 0.0, 0.0);
    let v: Vector3D<f64> = Vector3D::new(1.0, 0.0, 0.0);

    assert_eq!(m.transform_point3d(&p), Point3D::new(1.0, 0.0, -5.0));
    assert_eq!(m.transform_vector3d(&v), Vector3D::new(1.0, 0.0, 0.0));
}

EDIT fixed a typo in the test function.

Static const scale factors

It would be very useful to be able to declare ScaleFactor things as const. Would allow ergonomic conversion of rectangles from one space to another (by multiplying/dividing by the scale factor).

Currently this is not possible because of PhantomData private member, which requires us to call new() in order to construct an instance, and method calls are not allowed in const declarations (yet).

Requesting cargo ownership

I'm requesting either cargo ownership or an update of the package on crates.io. Thanks!

Get the updated Euclid documentation online

@nical has added a substantial amount of detailed documentation, but the version deployed here is quite out of date.

What needs to be done to update that with the latest from the source code?

Proposal: Add Vector types and remove Point4D

Currently, euclid and servo use points to describe vectors. It works out but it is a tad dangerous in some cases because we use the same type to express different things and also because transforming a point and transforming a vector does not involve the same computation (translations apply to points but don't apply to vectors, for instance). Euclid currently can't express transforming a vector, you have to transform two points and compute the difference, which is easy to forget when you also use the point types to store vectors).

I Propose adding TypedVector2D, TypedVector3D, types which would implement the usual arithmetic operations. Points would be changed so that:

• Points + Point is not implemented
• Point + Vector = Point
• Point - Vector = Point
• Point - Point = Vector

Places where we currently use points to express vectors (like Rect::translate) would take vectors instead. points and vectors would implement conversion helpers to_vector/to_point to avoid the burden of writing my_point - Point2D::origin() and Point2D::origin() + my_vector

Matrix transformation would be implemented separately for points (homogeneous coordinate w = 1) and vectors (homogeneous coordinate w = 0).

This would let us remove Point4D which is very awkward because it exposes the homogeneous coordinate, but we always expect it to be 1.
At a glance, Servo only uses Point4D in one place (rust-layers) where Point3D could (should) be used instead, and gecko does not use Point4D at all, so the 4d type is mostly dead weight and a source of confusion since its member w is mostly ignored.

As opposed to my other proposals to euclid, this is actually not implemented in gecko. However it has been a source of confusion for me and having distinct types for points and vectors would have avoided a few mistakes and helped make better self-documented APIs.

I have a prototype of this in my vectors branch if you would like to have a look at what the API would be like.

Thoughts?

Implement abs() for vectors and sizes.

This would be handy in some code I am writing in webrender.

Line support?

Aka TypedLine2D, TypedLine3D. Something like QLine.

Write plenty, plenty, plenty of tests

I want one test per serde implementation, using serde_test. I also want one test per trait impl in general, checking each bound etc.

Add TypedRect::from_size

I regularly run into cases in webrender where we create rects with origin (0, 0) and end up going through:

dirty_rect = DeviceUintRect::new(DeviceUintPoint::zero(), img_size);

where a simple:

dirty_rect = DeviceUintRect::from_size(img_size);

would have been nicer.

Proposal: adjective form with functions returning a modified version of self without mutating

For example:

fn translate(&self, by: TypedVector2D<T, U>) -> Self

would become

fn translated(&self, by: TypedVector2D<T, U>) -> Self

A mutable version of the function (if we want one) could be:

fn translate(&mut self, by: TypedVector2D<T, U>)

The idea is that reading foo.translate(v); looks like we modify foo by applying a translation to it which is misleading. Also we already use the adjective form with the matrix types so this change would make the API more consistent. I would like to go through all methods and apply this rule if there is no objection. Since I am already doing a large refactoring with the Matrix/Transform PR and the Point/Vector stuff, now is the best time to introduce this type of breaking changes.

break with the latest num_traits

the latest release of num_traits adds a new std default feature. euclid is using no-default features of num_traits, in which Float is not available.

rust-num/num@351dfc6

Link repository in Cargo.toml

It's just important to have for provenance, transparency, and ease of evaluation of the package! Thank you!

Result of Rect::from_points does not contain input points along right or bottom edge

let rect = Rect::from_points(&[point2(1, 1), point2(10, 10)]);
assert!(rect.contains(&point2(1, 1))); // Assert succeeds
assert!(rect.contains(&point2(10, 10))); // Assert fails

Given that it's an arbitrary point cloud that does not have a specific exclusive bottom-right point, this does not feel like the correct behavior.

Move Euclid tests into separate modules

Add scalar multiplication, element-wise min, and element-wise max to points

We're open-coding these right now and it would be better to have real methods so we can SIMDify them.

Proposal: Rename Matrix4D

Matrix4D is a 4 by 4 matrix for 3D transformations.
The "4D" in the name apparently comes from the 4 by 4 matrix layout, but besides that Matrix2D is a 2 by 3 matrix for 2D transformations.

In the pull request #151 I am removing Point4D, leaving us with Matrix4D as the only 4D-labelled thing in euclid.

I am proposing that we rename Matrix4D into Matrix3D, so that the name reflects what type of operations we are doing, rather than the internal layout of the matrix.

There are also suggestions such as:

• AffineTransform3D (I am not a fan of this one)
• Transform3D

Thoughts? This is really just about the name, not the implementation. Since I am pushing a series of breaking changes, now is a good time to bikeshed about aesthetics (I wouldn't want to go through all of servo just to fix names).

cc @nox @peterjoel

Rect usability improvements

Currently, the API is pretty unusable comparing to similar libraries.

Examples:

Now	Proposal
Rect::new(Point2D::new(0, 0), Size2D::new(10, 10))	Rect::from_xywh(0, 0, 10, 10)
Rect::new(Point2D::new(0, 0), Size2D::new(10, 10))	Rect::from((0, 0, 10, 10)) // From trait
rect.origin.x	rect.x()
rect.origin.y	rect.y()
rect.size.width	rect.width()
rect.size.height	rect.height()
rect.min_x()	rect.left()
rect.max_x()	rect.right()
rect.min_y()	rect.top()
rect.max_y()	rect.bottom()

New:

• Rect::set_x
• Rect::set_y
• Rect::set_width
• Rect::set_height

Source of inspiration: QRect.

Make serde optional.

For small projects that use euclid (like, not servo), the build times are dominated by serde stuff. It would be nice to make this cost optional.

Unfortunately this will be a breaking change. Maybe a good time to bundle it with other breaking changes that have been postponed to avoid having to bump euclid in all of servo.

make check is failing with "Illegal instruction"

As part of running make check on servo, tests in rust-geom are failing. This is what I get:

: ./geom-test 

running 9 tests
test length::tests::test_length ... ok
test matrix::test_ortho ... ok
test rect::test_contains ... ok
test rect::test_intersection ... ok
test rect::test_min_max ... ok
test rect::test_union ... ok
test rect::test_translate ... ok
test scale_factor::tests::test_scale_factor ... ok
Illegal instruction

It appears that the failing test is side_offsets::test_is_zero.

Since this seems to have something to do with the inline assembly in is_zero, you probably want something about my processor information? I'm not sure exactly what you need. My OS is 64-bit Arch Linux.

Rect::is_empty should return true if a Rect has any dimension == 0

Currently it checks if both are equal to zero, but we almost never want to differentiate that situation from one where only one dimension is zero.

`uint` vs `usize`

There are to_uint methods for TypedRect, TypedSize2D, TypedPoint2D and TypedPoint3D.

However, these methods generate types that are using usize, not uint. This makes the naming confusing.

There seem to be 4 possible ways forward:

• Leave things as they are now.
• Change the return types and documentation to uint.
• Rename the methods to to_usize.
• Rename these methods to to_usize and then add to_uint methods that actually return uint-based types.

Add TypedSize2D::to_u32

Implement Eq and friends traits for rect, point and size types.

Represent rectangles using the coordinates of top-left and bottom-right corners

Gecko is about to change the internal representation of its rectangle structure from { top-left, size } (what euclid does) to {top-left, bottom-right }.

I copy-pasted below the relevant part of the dev-platform announcement. I think that the motivations apply to Servo. WebRender even has some its rectangles already expressed this way (the ones that are sent to the GPU) using another type.
And if anything, following Gecko has the advantage of facilitating interop.

We currently represent a rectangle by storing the coordinates of its
top-left corner, its width, and its height. I'll refer to this
representation as "x/y/w/h".

I would like to propose storing instead the coordinates of the
top-left corner, and the coordinates of the bottom-right corner. I'll
refer to this representation as "x1/y1/x2/y2".

The x1/y1/x2/y2 representation has several advantages over x/y/w/h:

  - Several operations are more efficient with x1/y1/x2/y2, including
intersection,
    union, and point-in-rect.
  - The representation is more symmetric, since it stores two quantities of the
    same kind (two points) rather than a point and a dimension (width/height).
  - The representation is less susceptible to overflow. With x/y/w/h,
computation
    of x2/y2 can overflow for a large range of values of x/y and w/h. However,
    with x1/y1/x2/y2, computation of w/h cannot overflow if the coordinates are
    signed and the resulting w/h is unsigned.

A known disadvantage of x1/y1/x2/y2 is that translating the rectangle
requires translating both points, whereas translating x/y/w/h only
requires translating one point. I think this disadvantage is minor in
comparison to the above advantages.

Row vs column major matrices

Gecko and euclid's matrices are currently row-major. Web standards use column-major matrices.

@peterjoel proposed in issue #145 to make eulid matrices compatible with the web rather than gecko. I am filing this to keep it a separate discussion since issue #145 is about pre/post multiplications.

I personally think that there is more value in having all internal usage of matrices on the same convention. If/when WebRender makes it into gecko, all of the features are aren't supported (SVG for instance) will be gecko code. The prospect of starting to build a transform in rust-land with a certain layout, keep building it cpp-land with another layout and then debug that is not a happy one.
I am less worried about having to transpose matrices when exposing the DOM, because it happens at a separation between two very different worlds. I don't think I'll find myself hack bits of the rendering engine on both sides of a DOM interface at the same time while I can totally see the rendering engine becoming a mix of rust and cpp code.

So my (biased) opinion is that compatibility with gecko is more important.

That said I am looking into Gecko's matrices to see how dangerous it would be to change the transposition (ideally gecko, servo and the web would agree about matrix layout), so far I haven't come across a lot of code outside of Moz2D that make assumptions about the layout. I'll see what the rest of the gfx team thinks about changing it.

To give an idea of the different matrices involved:

• euclid: row-major
• moz2D: row-major
• cairo: row-major
• D2D: row-major
• skia: column-major
• web standard: column-major

[RFC] Wrap existing library

This is a crazy idea that is quite far from the rough reality, but we can at least discuss/consider it here.
Spawned by discussion in #159:

The more I look at it, the more I become obsessed with an idea that euclid could just be a shim around cgmath with a few typedefs (and maybe Size?) defined. That would reduce the library fragmentation and benefit the community.

The major thing missing from cgmath is typed spaces - the U generic parameter. I suggest having a wrapper defined like type Wrap<V, U> = (V, PhantomType<U>) and defining all our unit-related operations on it, but also having it to inherit all the operations of V, just used on the same Wrap<V, U> type. This is roughly the idea to explore.

cc @nical @nox

Quaternion type?

I realize this probably isn't too directly interesting to servo, but does anyone want a dedicated 3D quaternion/rotation type?

Advantages:

• Some operations can be more efficient (composing rotations in particular, without needing normalization)
• Might be nice to have "rotation" be its own type in the API, since there's already "translation" (Vector)

Disadvantages:

• More complexity
• Limited applicability?

I'd happily contribute such a thing if people were interested.

Confusing TypedRect::from_points doc comment

euclid/src/rect.rs

Line 230 in 1a5cdc3

/// Returns the smallest rectangle containing the four points.

Doc comment talks about "four points", but the method works for any number of points.

Implement Saturating trait

I can imagine cases where we want to prevent underflow being possible with things like Length.

Implement Default for TypedTransform2D

The same as TypedTransform2D::identity().

rustfmt?

I have my editor set up to automatically run rustfmt on Rust code as I edit it (due to me wanting that on my own projects). It looks like rustfmt hasn't been used on euclid much (and there are indentation errors in places).

Would a patch that only runs rustfmt on everything be okay? Or is everyone pretty happy with the current situation?

(There are some big pending changes hanging out ... so not sure if this would inconvenience them or not, but they'd just have to run rustfmt, so probably not that terrible.)

Implement AddAssign and related traits for Length

They're useful, if unstable.