sdf function performance issues

[slapin]

Hi!

Current architecture puts heavy time constraint on sdf function. Especially with complex noise formulas and polygon inside/outside calculations might result in serious performance problems for calculation of sdf values. The first idea which comes out of my mind is using of data compression would be nice especially knowing that all these data are quite sparse but it looks like there is no good algorithm oriented to random access to the data except for lossy texture methods. Hoping I just have poor research skills is there some good algorithm to compress SDF data or lossless data array compression oriented to fast random access?

[Zylann]

The main things you can do with SDF and voxels are mentionned in this doc: https://voxel-tools.readthedocs.io/en/latest/generators/#performance-tuning
It might not apply to you if you use a custom generator, but you could take inspiration on the approaches used.

As for noise, using SIMD is the last optimization I have in mind, like integrating parts of FastNoise2 which comes with faster implementations. Also you could sometimes get away with a cheaper algorithm (using value noise instead of simplex), or simply look at what your algorithm actually does, find what it does redundantly and strip it out. For example the FastNoiseLite library has cellular noise, but you have to sample it multiple times to get various pieces of info (distance, ID...), which could rather be obtained all at once. But you can't do the latter just because of how the API is designed (that's an issue I found out while integrating it, but did not address it).

Using compute shaders is considered in the future but it will require recent graphics cards and will probably lack support for a few edge case features, like querying random singular non-cached areas of the volume (because it would see it's not generated on CPU, but because the generator is on GPU it would require a full round-trip just to get that particular voxel).

Your issue is quite vague so there isn't much else I can answer. "Polygon inside/out" is not something this module does, looks like it's your own system, so you may research that, I don't know more than you do on this. This module mainly focuses on procedural techniques. Anything that involves existing data (polygons, splines, images...) may need some pre-processing to generate a data structure that makes queries faster.

[slapin]

It looks like most expensive parts in my sdf are point in polygon and distance to line segment which are kind of tough to optimize... I guess the most fruitful way would be to cache some most expensive calculations (noise is not among them). I wonder how No Man's Sky optimize their calculations though for their complex multi-layered noise functions. I guess they use interpolation a lot...