[libre-riscv-dev] [isa-dev] 3D Matrix-style operations / primitives

[Jacob Lifshay]

On Tue, Sep 17, 2019, 22:24 lkcl <luke.leighton at gmail.com> wrote:

> does anyone know of some mathematics for analysing which would be the best
> "primitives" for Matrix operations, suited to transposition and inversion,
> determinant and normalisation?
>
> for 3D that generally means just 2x2, 3x3 and 4x4.
>

Generally, for 3D graphics, matrix left/right-multiplication by
vector/matrix and transpose is by far more common than all the other matrix
operations combined, so having special HW support for inverse, determinant,
and normalize (never heard of that applied to matrices before) is probably
unnecessary.


> i'm looking up how matrix inverses are calculated and, hoo-boy :)
> https://integratedmlai.com/matrixinverse/
> https://www.wikihow.com/Find-the-Inverse-of-a-3x3-Matrix
>
> normalisation looks to be just "divide by the determinant":
> http://mymathforum.com/linear-algebra/18218-how-do-i-normalize-matrix.html
>
> so... i am logically deducing that if you wanted something RISC-like,
> you'd have operations for transpose and determinant?  or... can determinant
> be broken down further into something elegant?
> https://en.wikipedia.org/wiki/Determinant
>
> whilst 2x2 looks pretty obvious - 0,0 x 1,1 - 1,0 x 0,1 - it looks like it
> goes recursive from there, with permutations:
> https://en.wikipedia.org/wiki/Determinant#n_%C3%97_n_matrices
>
> at that point, honestly, i'm scared/alarmed to even recommend a Matrix
> Determinant opcode!
>

yeah, determinant is an O(n^3) operation (though there may be something
faster for really big n)

>
> likewise, Transpose appears to be a series of MV operations with offsets,
> which tends to suggest that there may be some vector primitives that would
> be really good to have, that could be added to this:
>
> https://libre-riscv.org/simple_v_extension/specification/mv.x/
>
>
> a quick search "matrix inverse swizzle" shows this:
>
> https://lxjk.github.io/2017/09/03/Fast-4x4-Matrix-Inverse-with-SSE-SIMD-Explained.html
>
> which mentions __mm_shuffle_epl32, _mm_shuffle_ps, _mm_movelp_ps and that
> leads on a merry search to SSE/AVX/AVX-512:
>
> https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=_mm_shuffle_ps
> https://www.cs.uaf.edu/2006/fall/cs301/lecture/11_17_sse.html
>
> looovely :)
>
> at which point i am definitely lost.  does anyone have any suggestions?
>

the algorithms I've generally used are an unrolled form of gauss jordan
elimination or just using the formula from a symbolic math program [1], at
which point, like operations can be grouped together.

[1]:
type the following into maxima:
m:apply(matrix, makelist(makelist(concat(v, i, j), j, 0, 3), i, 0, 3));
grind(invert(m))$

I've not generally had matrix inverse on a fast path, instead passing a
matrix and it's inverse together if needed and only calculating the inverse
when I generate the matrix.

For most 3D programs, matrices are used much more than they are generated,
so matrix inverse shouldn't generally be in the fast path, if the program
is designed well.

Jacob