Can I quickly test if a DE exists inside a cube?

[DaveH]

Hi, I'm not sure if this is possible but, here goes just in case:  

I'm experimenting with an octree of a DE function like a Mandelbox, and I need to build the tree as efficiently as I can.

Is it possible to find out if a cube is occupied by anything using DE functions? Do I really have step through a cube fractionally to find out if it's occupied? I may miss something doing that, and it's a bit brute force.

The location of any negative DE area doesn't matter at all, I just need to know if a cube is occupied or not.


Thanks,

Dave H.

[eiffie]

For a sphere it is simple, for a box you would have to test several points and triangulate.

[DaveH]

For a sphere it is simple, for a box you would have to test several points and triangulate.

Triangulate? Me-not-understand!  
Any small part of the cube could have the DE within it, like a tiny spire shape just poking through the side of the cube needs to be recognised an returning 'occupied' from the algorithm. Is that possible? I don't know how that's done, if at all.

[DaveH]

OK I'm getting there, it's taking me a while to get back into DE functions.
So for a sphere I simply calculate how far the centre of the sphere is from function.
For a cube check, I can test the sphere which intersects the corners of the cube as a quick cull test.
Then do I test the all the corners? I can't figure it out how to do the test.
Can anybody help please?

[Pauldelbrot]

A cube of side length x has a corner-to-center distance of sqrt(3*(0.5*x)²) or sqrt(0.75)*x. The cube just fits inside a sphere of that radius with the same center.

So, start by testing the cube's center. If the DE is greater than sqrt(0.75)*x, the cube is empty.

If the cube is not empty, you might try recursively subdividing it into 8 cubes half the size and testing them. Stop the subdivisions when a certain minimum size is reached. For voxel output (for 3D printing) this would be the same everywhere; for generating a 2D image (still or frame of a video) it should probably be larger farther from the camera and smaller closer to it (with some sane cut-off so the thing doesn't freeze or slow to a crawl if the camera bumps into the fractal). However, I'm not sure why you'd want to do this for 2D generation when raymarching works so well.

[eiffie]

I used the word triangulation loosely. You can determine the position of an object in 3d if you know its distance from 4 non-coplanar points. But now that I think about it you need the EXACT distance not an estimate. I am thinking like Pauldebrot that this will wind up being just as many DE checks. I could see a strategy for CPUs mainly where you start with a DE check on the camera position and then move ALL rays within this radius ahead to meet that sphere. Then branch into quadrants and repeat. That would save DE checks.

[DaveH]

Thanks for the useful replies. I wonder how much I'll have to subdivide it for it to be always correct in finding an empty cube? I suppose it depends on the DE function. I'll use a an OpenGL Shader for speed.
So there's no way around the leftover error of the cube/sphere intersection? I'm guessing it probably won't matter in the end as it's telling the truth about the cube being empty because it's inside the sphere!
Subdivision is probable the best way to do it anyhow, as always, it seems.
Thanks again,
Dave H.