Last modified: 2025-03-22 21:41:04
< 2025-03-21 2025-03-23 >I think the way I'm going to do this is add two new types to Peptide: "ifloat" and "ivec3", that do interval arithmetic.
And then some way to turn a straightforward expression into an interval
expression. You pass it something to say which of your variables will
transform into the interval equivalent (for me I think that is just p,
but no reason not to make it general).
Then DFS the tree and replace instances of those variables with the interval equivalent, and when any node that expects non-interval children has an interval child, it converts itself into the interval equivalent. If you have one child that is an interval and one that is regular, I guess you convert the regular one into a 0-sized interval first.
For a start I can just do some basic add/mul/sub/div of floats and then write tests for it, and then expand until I can turn SDFs into intervals.
Actually, a couple of other thoughts are:
I think the latter might be easiest, but it will unnecessarily do interval arithmetic even on subtrees that consist entirely of 0-sized intervals.
But premature optimisation is bad. I think let's do it this way.
OK, I have it passing quite a lot of tests with interval arithmetic. Not all of them.
smin()/smax() have divisions by intervals that cross 0, not sure
what is wrong there. And mvmul() is not implemented yet so tests that
use it can't work.
I am making floats and vec3s use intervals, but matrices are staying
as plain mat3s because matrices are only ever allowed to
be constants or input variables. You can't construct matrices using
Peptide, which means they never need to contain intervals.
Once all the tests are passing with interval arithmetic, I will want to do the "compiled JavaScript" version of interval arithmetic, and finally "compiled GLSL". And then I can make the shader do binary searching over intervals! And then I can make min/max skip paths that can't contribute to the interval.
OK, all tests now passing!
Next up is the "compiled JavaScript" version.
OK, done, pretty straightforward, one issue is that the trigonometric functions behave pretty weirdly in interval arithmetic.
I think uniquely, they don't necessarily reach min/max at the min/max of the operands.
OK, I now have interval arithmetic for sin/cos, and the compiled JS code is passing the tests.
Last thing is compiled GLSL interval arithmetic code, and then a binary search ray marching shader.
OK, I've also worked out that modulo is more complicated than I thought.
Currently the only place modulo is used is in the cubic lattice, is there a way to ditch it? Although I would probably also want to use it for domain repetition.
Meh, I probably want mod, I'll just do it. There's also the issue of how to handle modulo with negative values. I'm hoping to simply avoid taking a view on it, and then later on either take a view whenever I need to, or just ossify whatever happens by default.
OK, great success! All tests passing in interval mode, with direct evaluation, compiling to JS, and compiling to GLSL.
So now I need to write an interval mode binary search interval ray marching renderer.
First I guess I can duplicate the mouse cursor coordinate code using binary search interval ray marching, and verify that it is giving the same answers.
One issue is that the interval thing tells you if the ray might hit the surface within the interval, it doesn't tell you that it definitely will, especially if the scene gets rotated.
So far I have standard ray-marching code using the interval SDF with 0-sized interval, and plotting both results for the point under the cursor. It seems to basically agree, but the interval code is a lot slower, it triggers the performance logging quite often.
If I position the cursor right next to a flat surface, to max out the number of steps, then the standard code takes 12ms for 500 steps and the interval code takes 99ms. So maybe about 9x slower. But since we will be able to do a lot less than 9x as many iterations in the worst case, this may be a winner anyway. And then we get to do min/max pruning as well. I think for min/max pruning in the JS version I will have the call pass a second hash map to the generated function (one for the variables, like now, and one for the min/max state). And each min/max call can check whether it can skip a branch, and can assign whether it could have skipped a branch. I probably need to sleep on the actual implementation.
Given a directed graph, compute an integer that uniquely identifies that graph. 2 identical graphs should get the same Graph Number, and 2 different graphs should get different Graph Numbers.
You need to be able to efficiently compute the Graph Number, and bonus points if you can efficiently reverse it.
First idea:
Now you have an adjacency matrix that uniquely identifies the graph.
For each row, treat it as a binary number n_i, and accumulate 2^n_0 + 3^n_1 + 5^n_2 + 7^n_3 + ..., i.e. the Godel numbering of the columns.
And then you have your Graph Number.
But it's difficult to reverse because you need to find the prime factorisation.
So the next idea is to use "variable-base numbering" e.g. https://incoherency.co.uk/blog/stories/chess-steg.html to convey first the size of the matrix, and then a bitstream for the contents of the matrix.
So the only issue is how you permute the matrix into a canonical form.
And then we have a mapping from graphs to integers, which also proves that the set of graphs is not an uncountable infinity.
Apparently "nauty" has a scheme for canonical vertex labelling: https://math.stackexchange.com/questions/4315998/canonical-labelling-in-nauty-mckay
https://pallini.di.uniroma1.it/Introduction.html
< 2025-03-21 2025-03-23 >