instructions

In short, 3D Computational Geometry is an algorithm for calculating geometric positions and relationships in 3D space, such as the distance from a point to a line or the intersection of a line and a plane. Rarely used by the average developer, but often encountered by 3D/AR developers. While 3D engines generally provide built-in features to help us calculate position and pose, occasionally a knowledge of computational geometry is needed.

This series of articles, is to explain the solution of similar problems in the project, and provide Swift version of the code for reference.

The basic agreement

The data structures commonly used in computational geometry are: vectors, matrices and quaternions. Commonly used operations are: vector dot product, vector cross product, matrix multiplication, matrix inverse operation, quaternion multiplication.

It should be noted that the computational geometry algorithm is generally independent of the left/right hand system and the column principal order/row principal order matrix representation. But for the sake of simplicity, this series of code and schematics will use right-handed series and column main order matrices (as in ARKit).

Basic knowledge of

In this series, I will use the SIMD framework of the Swift language to represent this data, and the arithmetic functions are also built into the SIMD framework. The data type uses a single-precision Float type.

It should also be noted that some of the solutions are subject to error due to Float precision limitations, which means that mathematically, point A is not on the plane, but our algorithm shows that point A is (within the error range). For this kind of situation, we generally do not deal with it in the project, and do not spend time and energy to forcibly maintain mathematical correctness.

Vector, Point, Point

In SIMD, we usesimd_float3orSIMD3<Float>To represent three dimensional vectors and points. The relationship between them is shown below:

It is also important to note that when performing vector/point operations with a matrix, we usually use homogeneous coordinates, that is, to go from simd_float3 to simd_float4. We need to complement points with 1 and vectors with 0, because points are affected by translation and vectors are not:

// The point is followed by 1 to form the homogeneous coordinate form
let point3 = simd_float3(1.1.1)
let point4 = simd_float4(point3, 1)
// Add 0 to the vector to make it homogeneous
let vector3 = simd_float3(1.1.1)
let vector4 = simd_float4(vector3, 0)
Copy the code
  • Dot product: also called dot product, function namedot, is usually used to calculate the Angle between two vectors, whether they are parallel/perpendicular, and also to calculate the length of the projection of one vector in the direction of the other.
  • Cross product: also called cross product, function namecross, usually used to calculate the direction of the rotation axis of two vectors, the normal line of the plane, and the area of the parallelogram line.

Matrix Matrix

Matrix_float4x4: simd_float4x4: matrix_float4x4: simd_float4x4: Matrix_float4x4

let _ = simd_float4x4(simd_float4(1.0.0.0),/ / 0
                        simd_float4(0.2.0.0),/ / column 1
                        simd_float4(0.0.3.0),
                        simd_float4(4.5.6.1))Copy the code

[ 1 0 0 4 0 2 0 5 0 0 3 6 0 0 0 1 ] \begin{bmatrix} 1 & 0 & 0 & 4 \\ 0 & 2 & 0 & 5 \\ 0 & 0 & 3 & 6 \\ 0 & 0 & 0 & 1 \end{bmatrix}

As shown in the figure below, each column of the matrix represents the position of the coordinate axis and the origin after the motion:A matrix can represent motion, so the inverse matrix represents the opposite motion (i.e. return to the original state). Matrix multiplication represents continuous motion. There’s only one matrix multiplication, so you can just use the multiplication operator*You can also use a functionmatrix_multiplyorsimd_mulSaid.

Note: Because the matrix is in column main order, when you multiply a matrix by a vector, the matrix is on the left and the dot is on the right. Geometry means: to move (transform) a point according to a matrix. If the dot is on the left, it is equivalent to transposing the matrix and multiplying it left:

let m = matrix_float4x4(simd_float4(1.0.0.0),/ / 0
                        simd_float4(0.2.0.0),/ / column 1
                        simd_float4(0.0.3.0),
                        simd_float4(4.5.6.1))// Apply the point to the matrix m (motion)
let transformPoint = m * simd_float4(point, 1) / / (5.0, 9.0, 15.0, 1.0)
// The following two forms are equivalent
let transformPoint2 = simd_float4(point, 1) * m / / (1.0, 4.0, 9.0, 33.0)
let transfromPoint3 = m.transpose * simd_float4(point, 1) / / (1.0, 4.0, 9.0, 33.0)
Copy the code

Quaternions Quaternion

Quaternions use the simd_quatf type, which represents rotations, and quaternions multiplication represents continuous rotations. In quaternion multiplication, the order of application is different from that of matrix:

  • The matrix A * B represents: B motion first, then A motion;
  • The quaternion A * b represents: rotate A first, then rotate B;

The resources

This series code has been published in making: ComputationalGeometrySwift

  • Computer Graphics Geometry Tool Algorithm details
  • Mathematical methods in 3D games and computer graphics. 3rd edition
  • 3D Mathematical Basic Graphics and Game development, 2nd edition