Vec, Point, SVector, ... in the codebase

[juliohm]

As I continue to study the source code to suggest improvements, I would like to clean up all the variations around the notion of a point as a static n-dimensional vector. Currently, the code uses Vec, Point, SVector in different places, and it is hard to understand if there is an actual reason behind these variations or if it is just a result of the code evolving quickly. Can we pick a single name and stick to it? I can submit a PR with a single name if that is ok.

[SimonDanisch]

I'm pretty convinced of having a Point type... I suppose the Vec type could be deprecated in favor of SVector though

[juliohm]

I remember this distinction between Point and Vec had to do with the origin of the coordinate system, correct? I will try to take a look at the code by the end of the day again.

[juliohm]

So I looked into the code again as someone that is trying to become more familiar with the codebase to be able more actively contribute, and I confess that I still couldn't figure out why so many different "point/vec" types. I understand that they are all defined in the fixed_arrays.jl file with a macro, but could you please elaborate on the differences?

For the sake of maintainability, could we reduce these types to a single point type or even use vanilla SVector and MVector as appropriate throughout the codebase?

[goretkin]

I have not looked into the usage here, but I am in favor of the distinction between something like point and vector.

from https://doc.cgal.org/latest/Kernel_23/index.html#Kernel_23PointsandVectors

In CGAL we strictly distinguish between points, vectors and directions. A point is a point in the Euclidean space Ed, a vector is the difference of two points p2, p1 and denotes the direction and the distance from p1 to p2 in the vector space ℝd, and a direction is a vector where we forget about its length. They are different mathematical concepts. For example, they behave different under affine transformations and an addition of two points is meaningless in affine geometry. By putting them in different classes we not only get cleaner code, but also type checking by the compiler which avoids ambiguous expressions. Hence, it pays twice to make this distinction.

If we wanted to carry out this distinction, I would expect the following:

(::Point + ::Vec)::Point
(::Vec + ::Point)::Point
(::Vec + ::Vec)::Vec
(::Point - ::Point)::Vec
(::Number * ::Vec)::Vec
(::Vec * ::Number)::Vec

The following should be undefined:
-(::Point)
::Point + ::Point
::Number * ::Point
::Point * ::Number

[juliohm]

Yes. I agree with this distinction. What is not clear to me is what is the current vector type basically. The codebase sometimes uses Tuples, SVector, Vec, and I was not sure if Point had the meaning described in the GDAL snippet above. We certainly need this to be officially documented in the code for future maintainers.

…

On Thu, Sep 24, 2020, 21:56 Gustavo Goretkin ***@***.***> wrote: I have not looked into the usage here, but I am in favor of the distinction between Point and Vector. from https://doc.cgal.org/latest/Kernel_23/index.html#Kernel_23PointsandVectors In CGAL we strictly distinguish between points, vectors and directions. A point is a point in the Euclidean space Ed, a vector is the difference of two points p2, p1 and denotes the direction and the distance from p1 to p2 in the vector space ℝd, and a direction is a vector where we forget about its length. They are different mathematical concepts. For example, they behave different under affine transformations and an addition of two points is meaningless in affine geometry. By putting them in different classes we not only get cleaner code, but also type checking by the compiler which avoids ambiguous expressions. Hence, it pays twice to make this distinction. — You are receiving this because you were assigned. Reply to this email directly, view it on GitHub <#91 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAZQW3P45PKGOLRGTXIG2VDSHPTFBANCNFSM4RXU2GFA> .

[SimonDanisch]

All those different uses are historical... I'm in favor of the snippet posted by @goretkin, and would be behind making that the definition for the point type - and then replace all uses of Vec by SVector, and disallow tuple etc ;)

[juliohm]

One more question before I start start working on the PR :) What is the semantic behind the Particle type? Compared to the other primitive types, which are purely geometrical and static concepts, this one seems a bit different in the sense that it has some dynamics attached to it. It feels a bit off. Do we have a shared vision of geometry primitives somewhere?

[SimonDanisch]

I think we can & should remove the Particle type!

[juliohm]

That is good to hear. I will add this to the PR 👍

[juliohm]

One more question. I am finding it difficult to understand the macro @fixed_vector. What is it trying to do? Can we get rid of it as well in favor of a simple AbstractPoint base class with a concrete subtype called Point that internally is simply a SVector?

In summary, can we simplify the complex machinery in fixed_arrays.jl to a point type

abstract type AbstractPoint{N,T} end
struct Point{N,T} <: AbstractPoint{N,T}
  coords::SVector{N,T}
end

and a vector type SVector/MVector?

Also I keep seeing this C pattern in the code base where various type alias are introduced for specific floating point types and dimensions like Vecf0{N}, Pointf0{N}, Point2, Mat4f0. Can we also clean that up in favor of explicit Point{N,T} and SVector{N,T}? My understanding is that there are two use cases: (1) The point or vector is constructed from some other object and the type and dimension are naturally inherited, which eliminates the need of {N,T}, and (2) one is interested in type conversion and the {N,T} is used explicitly. I think that use case (1)` is far more common than use case (2) and so I think we could simplify things a lot by removing all this noise around the same concept. As a potential maintainer, this would help a lot 🙏

[SimonDanisch]

In summary, can we simplify the complex machinery in fixed_arrays.jl to a point type

You'd need to overload lots of functions, to achieve the same functionality as inheriting from StaticArray.
We could though remove the macro part, if we don't use it for Vec anymore, and clean it up a bit ;)

Can we also clean that up in favor of explicit Point{N,T}

Pfew, I use those a lot in different packages, so I ended up moving them lower and lower in the dependency chain, until I finally moved them here. So, I don't really want to go back on that progression :D I don't think those type aliases are hard to maintain?

[juliohm]

You'd need to overload lots of functions, to achieve the same functionality as inheriting from StaticArray.

What about making AbstractPoint a subtype of some base type from StaticArrays.jl to inherit the behavior, and then add the missing implementations?

abstract AbstractPoint{N,T} <: StaticVector{...} end
struct Point{N,T} <: AbstractPoint{N,T}
  coords::SVector{N,T}
end

# add whatever is missing
foo(::Point) = "I am a point"

I don't think those type aliases are hard to maintain?

Assuming that most algorithms are agnostic to the coordinate type, and that we want to be as generic as possible (please correct me if I am wrong), I see these types as just an extra overhead to keep in mind. The codebase has various snippets like:

FRect2D(Vec2f0(0), Vec2f0(1.0))

which I think could be simplified to Rect{2,Float32}(0, 0, 1, 1)?

Maintainability-wise it would be nice to stick to a single name for point and a single name for vector. How can we improve this experience?

[sjkelly]

A brief history here. First there was ImmutableArrays around 0.2. Then came allowing integers in type parameters around 0.4 or 0.5, followed by the tuple revamp and we got FixedSizedArrays and StaticArrays so we could have the SVector{N,T} paradigm rather than SVectorN{T} in ImmutableArrays. A lot of what you see is fixed_arrays.jl is the remaining compatibility layer for ImmutableArrays -> FSA -> StaticArrays migrations.

I would say that before we start redesigning and breaking dependant projects, we should reduce that layer as much as possible and see what happens. E.g. there are a lot of @generated functions in there that were needed for performance in 0.6 but a faux pas in the 1.0 era. Reducing @generated has far more runtime+developer impact that restructuring the type hierarchy IMO.

[juliohm]

I am happy to help with this reduction of the base layer as much as possible, that is why I am pushing these changes now :) I love to improve readability and maintainability of code, and given that GeometryBasics.jl is such a fundamental base package, we should make it as clean as possible early on.

So even though these changes are breaking, they are breaking for a good long-term reason.

[juliohm]

Ok, I will implement these changes in a few steps:

1. First I will try to make const Vec = SVector the only definition of vector throughout the code base. This will also eliminate the need for the @fixed_vector macro for vectors. This also means that all conversions to tuple and other variants of the vector concept will go away 🙏
2. After that, I will take a look at the concept of point, and will try to implement it without the macro, including the existing behavior whenever possible. I see that many generated functions are just conversions between tuples, so I think these will also go away. We we will have a clear API for operating with points like subtracting points and querying the coordinates as a vector to be manipulated as desired with other vectors (not points).

Will submit a PR soon for your review 👍

[juliohm]

I would like to share an update regarding this issue. The above PRs have been merged into the cleanup branch, and they fix the problems around the concept of vector. Now, a vector is simply an alias for an efficient static array implementation.

In the next PR I will address the concept of point, which will definitely be the most challenging part to refactor.

[SimonDanisch]

Now, a vector is simply an alias for an efficient static array implementation.

Btw, this and some other comments make it sound, like we're currently re-implementing Vec & Point in GeometryBasics instead of using StaticArrays... I just want to make sure, that it's clear, that we absolutely don't do that, but instead inherit more than 95% of the functionality from StaticArrays, by using the official way of creating a new StaticArray vector type!

[juliohm]

I tried to say that we don't have a new static array type. It is a vanilla SVector to facilitate integration with other projects. 👍

[juliohm]

This issue is fixed in the cleanup branch. I am now working on a fork called Meshes.jl where I will be refactoring the codebase for more general functionality in computational geometry: https://github.com/JuliaGeometry/Meshes.jl