Possible BVH Integration with Fidget?

[LukeP0WERS]

Hey, I'm currently planning on using fidget for procedural generation in a game I'm working on. So far it works (almost) perfectly for modelling detailed voxel objects (it would be nice if there could be multiple outputs for an evaluation function). However I am worried that things could start to get out of hand as I start to generate thousands or even millions of expressions.

Before I found fidget, my initial plan was to construct a BVH or similar spatial acceleration structure where only the expressions inside the volumes would need to be evaluated. Using a spatial acceleration structure like this is incredibly fast, so much so that IQ managed to get a pretty large mesh rendering in real time: https://iquilezles.org/articles/sdfbounding/ Unfortunately, IQ's implementation relies on every primitive in the KD tree being a triangle which defeats the purpose of using SDFs for proc gen.

Implementing any sort of spatial hierarchy in fidget is going to be pretty difficult. It either needs to be possible to support branching and conditional code, or shapes would need a simplification pass which can discard large numbers of expressions based on their bounding volumes without having to evaluate them.

The latter idea seems to me like it would be much more effective but would have to be tightly integrated with fidget in some way. Since I'm not super familiar with the internals of fidget yet I'm interested to hear what you think about this.

[LukeP0WERS]

Actually I think it might already be possible to handle large scale shapes in fidget by manually constructing a separate shape for each cell in a grid and sharing shapes that cross the boundaries of cells, but I think if there is a way to use a spatial hierarchy for shape simplification directly it would be a much better solution.

[mkeeter]

My intuition is that it would be better to build the BVH outside of Fidget, storing Fidget's Tree / Node / Shape objects in the BVH.

It really depends on how you're using those objects, though (re-rendering once per frame? only when things change? how often do the shapes change?).

One fun option could be to write your BVH, but make it implement Fidget's Function trait. Specifically, interval evaluation and the associated trace type could use the BVH as an additional basis for simplification (in addition to per-shape traces).

On a tangential note, can you say more about wanting multiple function outputs? That's been on my radar, so I'd be curious to hear how you want to use them.

[LukeP0WERS]

Yeah now that ive given this some more thought, I definitely overthought this. I don't need a per frame render so I can just simplify at construction. Anyhow I'm going to make a separate issue for the multiple function output thing.