|
|
Post by trejkaz on Feb 28, 2022 0:13:42 GMT
So I ran across this apparently well-known algorithm: en.wikipedia.org/wiki/LU_decompositionCalculating inverse of a 4x4 matrix, best times for 10,000 runs: Algorithm in the book: 61.3729 ms Using LU decomposition: 12.0178 ms Not too bad! In the grand scheme though, it only shaves a second off a render time of ~ 40 seconds. |
|
|
|
Post by Jamis on Feb 28, 2022 23:58:04 GMT
Thanks for pointing that other algorithm out! Ultimately, it came down to which algorithm I felt I could describe and decompose sufficiently in the space I had, such that it could be implemented test-first.
|
|
|
|
Post by trejkaz on Mar 22, 2022 6:51:23 GMT
I was talking with a friend about this one and they reminded me that at school we were taught a different way to calculate determinants, which might also be fairly performant for 4x4 matrices, but I haven't tried coding it up yet: - Set resultSign to 1
- If the top left cell is a zero:
- If everything below is zero, then your determinant is zero, so you can return 0
- If something below was non-zero, swap the rows and flip the sign on resultSign
- Now that the top-left cell is non-zero, for every row below which was also non-zero, add or subtract the top row until you get 0
- Repeat for the next diagonal. (Could even use recursion still, if you wanted to get the 2x2 case right first and then work up to 3x3 and then 4x4.)
- If you get to the end without returning 0, compute the product of the cells on the diagonal and multiply by the sign, and bam, there's your determinant.
But actually, the reason why I was looking at faster ways was that I wanted to compute the determinant of a 200x200 matrix and it was taking minutes to run.  |
|
|
|
Post by bit101 on Oct 23, 2022 15:29:26 GMT
As the inverse and transposed inverse are directly based on the base transform and will not change unless that changes, I just made a setter to set the transform rather than a property that can be set directly. The setter sets the transform, then calculates the inverse and transposed inverse and saves them. I make sure that any code that affects the transform uses the setter. Then I'm only calculating the other properties one, rather than every time they are accessed. It saves a ton of time.
|
|
|
|
Post by bit101 on Oct 23, 2022 23:36:02 GMT
As the inverse and transposed inverse are directly based on the base transform and will not change unless that changes, I just made a setter to set the transform rather than a property that can be set directly. The setter sets the transform, then calculates the inverse and transposed inverse and saves them. I make sure that any code that affects the transform uses the setter. Then I'm only calculating the other properties one, rather than every time they are accessed. It saves a ton of time. And now that I've read the forum a bit, I see that I'm about the 10,000th person to make this discovery.  |
|
|
|
Post by vorpal on Jan 27, 2023 19:02:16 GMT
Calculating the determinants and storing them (I am working in Kotlin and using lazy initialization on them as properties) is a pretty negligible part of the rendering. I think that minimizing the matrix multiplications and using a faster multiplication algorithm will probably speed things up significantly.
A k-d tree on triangular meshes sped things up dramatically, but it doesn't work in all cases.
|
|
