Sparse Element Algebra For Unreal

Sparse Element Algebra For Unreal

So, I was trying to do higher dimensional algebra in unreal, but realized that there weren’t any structures for it; so I made some. This is a small module that contains implementations of Vector and Matrix which store values in TMaps. Using TMaps allows us to just NOT store “0” entries, hence the “Sparse Element” in the title, operations are only executed over non-0 entries and no consideration of size is taken, as every vector and matrix is ultimately infinite in size. When it tries to read an undefined region of a matrix, or vector, it just returns an associated 0-value, if you try to modify an undefined region, it defines it as the 0-value, and then performs the operation, and then trims out 0-values to keep the data lean.

I’m open to constructive criticism, please let me know if you think this is useful, what might make it more useful, or if you just don’t care I guess. Currently I’m just fleshing it out as I need.


I’ve worked to make the SparseVector and SparseMatrix structures more robust and easier to extend with less code repetition, in preparation for the determinant implementation.
Next I’ll be implementing the Matrix Determinants, Matrix Minors, Matrix Cofactors, Vector Cross Products, and Matrix Inverse… And then I’ll probably give it a rest and work on other things using what I’ve made.

this could be very handy in procedural generation or pathfinnding on tiled maps! Good luck with progress!

Thanks, I was working on this for that express purpose. I was working on a PCG algorithm in which I needed to find circumspheres of tetrahedra, for which I needed to find the determinant of the Cayley-Menger matrix representation of the simplex. For 3D tetrahedra this requires a 5D matrix, which just narrowly avoids being implementable in unreal without rolling your own representation. I figured while I was at it I’d make it as useful as possible. Ultimately, I’ll just keep implementing functions as I need them. Right now I’m working on the Determinant implemented using Laplace’s formula, but I’m trying to think of the best dynamic programming approach so I avoid recomputing sub determinants unnecessarily in the recursions. I would like this to be relatively optimized.

I finished work on a recursive determinant, although as stated above, it’s redundantly recursive. Initially I thought I’d build up a TMap mapping Matrices to determinant solutions, and only work out determinants I hadn’t worked out prior. But that could lead to an huge memory hog. In the future since I know I’ll be generating cofactor matrices for calculating inverse matrices, I’ll probably just make that a member of the struct, so I can use it as a scratch pad for cofactor heavy calculations. Only problem is I have to use dirty bits or something to indicate when a previously calculated cofactor is invalidated. I’ll work on that later, for now this works fine.

Keep up the good work man !

I’d been thinking about the performance of this implementation… it’s actually really bad. Mostly because it’s doing multiple hash searches for even the simplest matrix operations. I’ve decided this was a dead end. I’m going to back peddle, and instead of using TMaps I’ll just use linear std::vectors, and just implement the BLAS algorithms to wrap for unreal.

Ah, yes. For these kind of operations TMaps would introduce a huge amount of slowdown. Using a wrapper for BLAS seems like a good way to do it.

Wrapping a third party library is an immense pain in the ***, if for no other reason than the Unreal Build Tool does not play well with others. I have a cursory wrapping of OpenCV on my github that I was working on (it needs a full rewrite), and ultimately much of the functions available in OpenCV are easier and better achieved by just writing it yourself with unreal in mind when and if possible. The tutorial information for wrapping third party libraries is out of date where it isn’t just blatantly misleading. And not to mention that trying to expose these functions to Blueprints is an exercise in futility when you realize that they use Doubles extensively (as they should) and want to do other things that Blueprint (or Kismet) just doesn’t like (and to it’s own detriment). It’s like a battle of attrition where you are trying to convert Blueprint got data into the right form to feed it into the library function, and then convert the Library function’s output to something the Blueprint system will work with, all while trying to maintain consistency throughout. If you’re lucky enough to be working with source of your library, and have somehow tricked Unreal Build Tool to build it successfully. Congratulations, you definitely could have rolled your own in that time. Otherwise you’re using prebuilt dll libraries, which introduces it’s own bag of worms. What the unreal community needs is an automated process to make Build scripts based on makefiles. That would be huge, and something I might pursue in the future.

Anyway I was looking for a simple blas I could just wrap for unreal, but I couldn’t really find one that didn’t make Unreal Build Tool throw a fit. So I’m implementing my own single precision BLAS just for Unreal. Underlying everything now is stl vectors, and I’m kind of shocked how much easier it is to implement these BLAS functions using stl vectors. I’ve already implemented Blas level 1 entirely, just two more levels of functions, and then I just wrap these function translating vectors to and from TArrays or something. I don’t know why I didn’t start here to begin with.