This is a small library for geometric types with a focus on 2d graphics and layout.
servo / euclid Goto Github PK
View Code? Open in Web Editor NEWGeometry primitives (basic linear algebra) for Rust
License: Other
Geometry primitives (basic linear algebra) for Rust
License: Other
This is a small library for geometric types with a focus on 2d graphics and layout.
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.
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):
Advantage(s) of eculid's approach (v2.rs):
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.
We're open-coding these right now and it would be better to have real methods so we can SIMDify them.
It has been deprecated: announcement.
Is there any functionality you would require from Serde or another library before this would be possible?
It's just important to have for provenance, transparency, and ease of evaluation of the package! Thank you!
Aka TypedLine2D
, TypedLine3D
. Something like QLine.
#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.
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.
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.
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.
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).
It confuses me why they are reversed, and it could confuse other people in the future.
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, Point
s 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.
I want one test per serde implementation, using serde_test. I also want one test per trait impl in general, checking each bound etc.
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.
I realize this probably isn't too directly interesting to servo, but does anyone want a dedicated 3D quaternion/rotation type?
Advantages:
Disadvantages:
I'd happily contribute such a thing if people were interested.
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̕.
They're useful, if unstable.
Line 230 in 1a5cdc3
Doc comment talks about "four points", but the method works for any number of points.
It's quite a heavy-weight dependency that isn't necessarily used with euclid outside of servo.
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
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:
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
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.)
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.
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
}
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.
I'm requesting either cargo ownership or an update of the package on crates.io. Thanks!
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.
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:
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.
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.
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.
This would be handy in some code I am writing in webrender.
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.
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
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.
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.
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.
The same as TypedTransform2D::identity()
.
...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̕
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:
uint
.to_usize
.to_usize
and then add to_uint
methods that actually return uint
-based types.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.
I can imagine cases where we want to prevent underflow being possible with things like Length.
There doesn't appear to be any function to promote a 2D transform into a 3D transform. This would be useful.
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).
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:
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?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.