(System.Numerics) Cross Product for Vector2 and Vector4

danmoseley commented 5 years ago

I am proposing that a Cross Product function be added to both Vector2 and Vector4 of System.Numerics because its use in geometry is so common.

Rationale and Usage

The structs, Vector2, Vector3, and Vector4 are intended to model geometry functions that often need to be performed quickly and which would greatly benefit from SIMD inlining. Dot Product is just as popular and it is properly implemented in these structs. Cross Product is only possible for vectors of length 3 (yes, and 7, but that is not important right now). However, Vector2 and Vector4 are essentially modelling vectors in 3D space. In Vector2 the cross product is commonly used for functions like offsetting, for determining if the next edge in a polygon turns right or left (or convex or concave), or determining overlap/collisions. A cross-product of two Vector2 's would always result in an out-of-plane or z-direction, but it's value and sign is very useful and just as quick to process as Dot. Vector4 is defined for use as a homogeneous 3D coordinate vector, and so it will be necessary for a Cross function to exist for it just as much as for Vector3.

Proposed Changes And API

The addition of two new methods are quite simple and the functions that these invoke are nothing other than add (+) and multiply (*). To Vector2_Instrinsics.cs (under Dot() line 109):

         /// <summary>
        /// Returns the z-value of the cross product of two vectors.
        /// Since the Vector2 is in the x-y plane, a 3D cross product
        /// only produces the z-value
        /// </summary>
        /// <param name="value1">The first vector.</param>
        /// <param name="value2">The second vector.</param>
        /// <returns>The value of the z-coordinate from the cross product.</returns>
        [JitIntrinsic]
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static float Cross(Vector2 value1, Vector2 value2)
        {
            return value1.X * value2.Y 
                   - value1.Y * value2.X;
        }

to Vector4_Instrinsics.cs (under Dot() line 157):

        /// <summary>
        /// Computes the cross product of two vectors. For homogeneous
        /// coordinates, the product of the weights is the new weight
        /// for the resulting product.
        /// </summary>
        /// <param name="vector1">The first vector.</param>
        /// <param name="vector2">The second vector.</param>
        /// <returns>The cross product.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static Vector4 Cross(Vector4 vector1, Vector4 vector2)
        {
            return new Vector4(
                vector1.Y * vector2.Z - vector1.Z * vector2.Y,
                vector1.Z * vector2.X - vector1.X * vector2.Z,
                vector1.X * vector2.Y - vector1.Y * vector2.X,
                vector1.W * vector2.W);
        }

Other Details

One will note that the 'Cross' for 'Vector2' looks like the 'Dot' except the values have moved around. Yes, essentially the 'Cross' for 'Vector2' is the same as taking the 'Dot' with a vector that has been rotate 90-degrees from the original. As such, this is the work around to invoking geometric functions - create a new vector 90-degrees from the original, and then use Dot. This process is not intuitive and requires extra steps. A simple function, like the one shown above, is both more intuitive and quicker.
The proposed Cross function for Vector4 is nearly the same as that for Vector3 with the addition of the fourth value which is the product of the original two w's. This can be derived by symbolically performing the cross product for Vector3 with values [x_1/w_1, y_1/w_1, z_1/w_1] and [x_2/w_2, y_2/w_2, z_2/w_2].

Open Questions

Will the name Cross be misleading for Vector2? If so, one could name it CrossZValue, but I think this is an unwarranted complication. In implementing 2D algorithms, the literature has called this the cross product and one would write the code to mimic the presentation of scientific papers. However, since the result is a single scalar (float), it could be confusing as to why a Cross product function is not returning a new vector.

Pull Request

A PR with the proposed changes is forthcoming.

Updates

danmoseley commented 5 years ago

From @RussKeldorph on February 19, 2019 21:58

https://github.com/dotnet/corefx/blob/master/Documentation/project-docs/api-review-process.md

@karelz @danmosemsft I don't seem to have permission to Transfer this to dotnet/corefx. Could you move it?

@CarolEidt @eerhardt @tannergooding

danmoseley commented 5 years ago

From @tannergooding on February 19, 2019 22:30

I don't seem to have permission to Transfer this to dotnet/corefx. Could you move it?

Unfortunately, you currently require admin permissions on both the source and destination repositories to use the built-in GitHub functionality.

danmoseley commented 5 years ago

From @tannergooding on February 19, 2019 22:35

I think the proposal, overall, is reasonable.

Looking at a couple of other graphics oriented vector math libraries:

Unity nor XNA/FNA provides Cross for Vector2/Vector4
DirectXMath does provide Cross for Vector2/Vector4

danmoseley commented 5 years ago

@RussKeldorph for those with contributor access to move issues, we recommend using https://github-issue-mover.appspot.com

tannergooding commented 5 years ago

@micampbell, could you please add a post that follows the "good example" template detailed here: https://github.com/dotnet/corefx/blob/master/Documentation/project-docs/api-review-process.md#steps

Once that is done, I can update the original post and mark this as api-ready-for-review

micampbell commented 5 years ago

I am proposing that a Cross Product function be added to both Vector2 and Vector4 of System.Numerics because its use in geometry is so common.

Rationale and Usage

The structs, Vector2, Vector3, and Vector4 are intended to model geometry functions that often need to be performed quickly and which would greatly benefit from SIMD inlining. Dot Product is just as popular and it is properly implemented in these structs. Cross Product is only possible for vectors of length 3 (yes, and 7, but that is not important right now). However, Vector2 and Vector4 are essentially modelling vectors in 3D space. In Vector2 the cross product is commonly used for functions like offsetting, for determining if the next edge in a polygon turns right or left (or convex or concave), or determining overlap/collisions. A cross-product of two Vector2 's would always result in an out-of-plane or z-direction, but it's value and sign is very useful and just as quick to process as Dot. Vector4 is defined for use as a homogeneous 3D coordinate vector, and so it will be necessary for a Cross function to exist for it just as much as for Vector3.

Proposed Changes And API

The addition of two new methods are quite simple and the functions that these invoke are nothing other than add (+) and multiply (*). To Vector2_Instrinsics.cs (under Dot() line 109):

         /// <summary>
        /// Returns the z-value of the cross product of two vectors.
        /// Since the Vector2 is in the x-y plane, a 3D cross product
        /// only produces the z-value
        /// </summary>
        /// <param name="value1">The first vector.</param>
        /// <param name="value2">The second vector.</param>
        /// <returns>The value of the z-coordinate from the cross product.</returns>
        [JitIntrinsic]
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static float Cross(Vector2 value1, Vector2 value2)
        {
            return value1.X * value2.Y 
                   - value1.Y * value2.X;
        }

to Vector4_Instrinsics.cs (under Dot() line 157):

        /// <summary>
        /// Computes the cross product of two vectors. For homogeneous
        /// coordinates, the product of the weights is the new weight
        /// for the resulting product.
        /// </summary>
        /// <param name="vector1">The first vector.</param>
        /// <param name="vector2">The second vector.</param>
        /// <returns>The cross product.</returns>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static Vector4 Cross(Vector4 vector1, Vector4 vector2)
        {
            return new Vector4(
                vector1.Y * vector2.Z - vector1.Z * vector2.Y,
                vector1.Z * vector2.X - vector1.X * vector2.Z,
                vector1.X * vector2.Y - vector1.Y * vector2.X,
                vector1.W * vector2.W);
        }

Other Details

One will note that the 'Cross' for 'Vector2' looks like the 'Dot' except the values have moved around. Yes, essentially the 'Cross' for 'Vector2' is the same as taking the 'Dot' with a vector that has been rotate 90-degrees from the original. As such, this is the work around to invoking geometric functions - create a new vector 90-degrees from the original, and then use Dot. This process is not intuitive and requires extra steps. A simple function, like the one shown above, is both more intuitive and quicker.
The proposed Cross function for Vector4 is nearly the same as that for Vector3 with the addition of the fourth value which is the product of the original two w's. This can be derived by symbolically performing the cross product for Vector3 with values [x_1/w_1, y_1/w_1, z_1/w_1] and [x_2/w_2, y_2/w_2, z_2/w_2].

Open Questions

Will the name Cross be misleading for Vector2? If so, one could name it CrossZValue, but I think this is an unwarranted complication. In implementing 2D algorithms, the literature has called this the cross product and one would write the code to mimic the presentation of scientific papers. However, since the result is a single scalar (float), it could be confusing as to why a Cross product function is not returning a new vector.

Pull Request

A PR with the proposed changes is forthcoming.

Updates

tannergooding commented 5 years ago

@micampbell thanks!

I have updated the original post and marked this as ready-for-review. At some point in the future (depending on reviewer availability and the location of this issue in the general backlog), this will go to API review and either be approved, rejected, or marked as "needs more work".

terrajobst commented 5 years ago

Video

Generally this seems like a reasonable API. The only sticking point is that it seems undefined and only DirectX exposes this operation for Vector2 and Vector4. This may be odd, but doesn't seem to be a blocker to us.

micampbell commented 5 years ago

I'm unclear what you mean by "undefined".

Also - with the change in flag - should I produce a pull-request? or is this unnecessary?

tannergooding commented 5 years ago

should I produce a pull-request

If you would like to submit a PR adding the functionality, that would be greatly appreciated 😄

tannergooding commented 5 years ago

I'm unclear what you mean by "undefined".

It was raised that a cross product vectors in non 3 or 7 dimensional space is "technically" not defined and the algorithm for 2/4 dimensions is realistically just a simplification/optimization on the higher dimensioned versions.

That is, 3-dimensions is:

e0: (lhs.e1 * rhs.e2) - (lhs.e2 * rhs.e1)
e1: (lhs.e2 * rhs.e0) - (lhs.e0 * rhs.e2)
e2: (lhs.e0 * rhs.e1) - (lhs.e1 * rhs.e0)

If you assume a 2-dimensional vector has 0 for the e2 component, you end up with:

e0: (lhs.e1 * 0) - (0 * rhs.e1)
e1: (0 * rhs.e0) - (lhs.e0 * 0)
e2: (lhs.e0 * rhs.e1) - (lhs.e1 * rhs.e0)

Which simplifies to the following, so you only return the e2 component:

e0: 0
e1: 0
e2: (lhs.e0 * rhs.e1) - (lhs.e1 * rhs.e0)

Likewise, the 7-dimensional cross product is:

0: (lhs.e1 * rhs.e3) − (lhs.e3 * rhs.e1) + (lhs.e2 * rhs.e6) − (lhs.e6 * rhs.e2) + (lhs.e4 * rhs.e5) − (lhs.e5 * rhs.e4)
1: (lhs.e2 * rhs.e4) − (lhs.e4 * rhs.e2) + (lhs.e3 * rhs.e0) − (lhs.e0 * rhs.e3) + (lhs.e5 * rhs.e6) − (lhs.e6 * rhs.e5)
2: (lhs.e3 * rhs.e5) − (lhs.e5 * rhs.e3) + (lhs.e4 * rhs.e1) − (lhs.e1 * rhs.e4) + (lhs.e6 * rhs.e0) − (lhs.e0 * rhs.e6)
3: (lhs.e4 * rhs.e6) − (lhs.e6 * rhs.e4) + (lhs.e5 * rhs.e2) − (lhs.e2 * rhs.e5) + (lhs.e0 * rhs.e1) − (lhs.e1 * rhs.e0)
4: (lhs.e5 * rhs.e0) − (lhs.e0 * rhs.e5) + (lhs.e6 * rhs.e3) − (lhs.e3 * rhs.e6) + (lhs.e1 * rhs.e2) − (lhs.e2 * rhs.e1)
5: (lhs.e6 * rhs.e1) − (lhs.e1 * rhs.e6) + (lhs.e0 * rhs.e4) − (lhs.e4 * rhs.e0) + (lhs.e2 * rhs.e3) − (lhs.e3 * rhs.e2)
6: (lhs.e0 * rhs.e2) − (lhs.e2 * rhs.e0) + (lhs.e1 * rhs.e5) − (lhs.e5 * rhs.e1) + (lhs.e3 * rhs.e4) − (lhs.e4 * rhs.e3)

So, assuming dimensions 4 through 6 are zero, you get:

0: (lhs.e1 * rhs.e3) − (lhs.e3 * rhs.e1) + (lhs.e2 * 0) − (0 * rhs.e2) + (0 * 0) − (0 * 0)
1: (lhs.e2 * 0) − (0 * rhs.e2) + (lhs.e3 * rhs.e0) − (lhs.e0 * rhs.e3) + (0 * 0) − (0 * 0)
2: (lhs.e3 * 0) − (0 * rhs.e3) + (0 * rhs.e1) − (lhs.e1 * 0) + (0 * rhs.e0) − (lhs.e0 * 0)
3: (0 * 0) − (0 * 0) + (0 * rhs.e2) − (lhs.e2 * 0) + (lhs.e0 * rhs.e1) − (lhs.e1 * rhs.e0)
4: (0 * rhs.e0) − (lhs.e0 * 0) + (0 * rhs.e3) − (lhs.e3 * 0) + (lhs.e1 * rhs.e2) − (lhs.e2 * rhs.e1)
5: (0 * rhs.e1) − (lhs.e1 * 0) + (lhs.e0 * 0) − (0 * rhs.e0) + (lhs.e2 * rhs.e3) − (lhs.e3 * rhs.e2)
6: (lhs.e0 * rhs.e2) − (lhs.e2 * rhs.e0) + (lhs.e1 * 0) − (0 * rhs.e1) + (lhs.e3 * 0) − (0 * rhs.e3)

Simplified:

0: (lhs.e1 * rhs.e3) − (lhs.e3 * rhs.e1)
1: (lhs.e3 * rhs.e0) − (lhs.e0 * rhs.e3)
2: 0
3: (lhs.e0 * rhs.e1) − (lhs.e1 * rhs.e0)
4: (lhs.e1 * rhs.e2) − (lhs.e2 * rhs.e1)
5: (lhs.e2 * rhs.e3) − (lhs.e3 * rhs.e2)
6: (lhs.e0 * rhs.e2) − (lhs.e2 * rhs.e0)

However, for four dimensions, the proposed algorithm is different and is also different from what DirectX Math does for their XMVector4Cross method (which takes three inputs).

micampbell commented 5 years ago

Sorry for taking so long to respond. The 4D vector is meant to represent homogeneous 3D coordinates where the fourth dimensions, w, is just the common denominator of x, y, and z. So, it is not really in 4 dimensions. Hence, why my suggested is so close to the 3D one. As for the XMVector4Cross (in DirectX Math), I have no idea where they are getting this formula and can find no description of the "science" behind it online (just in "logic" behind it). Taking the cross product of 3 vectors does not make sense to me. So, I promised a pull request. You can find my minor changes here.https://github.com/dotnet/corefx/pull/41413

huoyaoyuan commented 2 years ago

@tannergooding Do we need to revisit this? Is current approved api shape still OK?

deeprobin commented 2 years ago

Is there some Generic Math for CrossProducts?

deeprobin commented 1 year ago

@tannergooding Is there anything against submitting a PR here?

dotnet / runtime