How to form a sphere from Voxels

I want to form a Sphere given radius from blocks given size. And can't figure out the code / algorithm. Any help appreciated.

Edit: I dont wan't the Sphere to be filled, just the outer shell

Edit: I tried this

function ds(r)
for tx=-r, r do
for ty=-r, r do
for tz=-r, r do
if math.sqrt(math.pow(tx, 2)  +  math.pow(ty, 2)  +  math.pow(tz, 2)) <= r-2 then
Terrain:FillBlock(Vector3.new(tx, ty, tz), Vector3.new(1,1,1), material)
end
end
end
end
end


But it's very much iterations and so slow and odes the filling that is extra calls.

2 Answers

There are a couple of micro-optimizations you can do here.

1. math.pow(value, 2) is often slower than just doing value * value (although this might be something worth benchmarking - I do not know your technology stack).
2. The value of tx * tx is not going to change during the outermost loop
3. The value of ty * ty is not going to change during the second outermost loop
4. The condition math.sqrt(something) > r is equivalent to the condition something > r * r. But square-roots are usually much more expensive than multiplication, and you only have to do a multiplication once because r stays constant throughout the algorithm.
5. You are creating a new Vector3(1,1,1) for each block. Does Terrain:FillBlock actually require a completely new vector object for each block? Can't you reuse the same vector?

This is how I would optimize this:

function ds(r)
size_vector = Vector3.new(1,1,1)
r_squared = (r - 2) * (r - 2)
for tx=-r, r do
tx_squared = tx * tx
for ty=-r, r do
ty_squared = ty * ty
for tz=-r, r do
tz_squared = tz * tz
if (tx_squared  +  ty_squared  +  tz_square) <= r_squared then
Terrain:FillBlock(Vector3.new(tx, ty, tz), size_vector, material)
end
end
end
end
end


There is of course also the question if you really need to iterate through a whole cube if you only want to fill a sphere. So you could use trigonometry to calculate the beginning and the end of each loop. But I doubt that this is worth it. Trigonometric functions are again pretty expensive and you are saving less than half of the inner loop iterations (a sphere has 0.5236 times the volume of a cube with the same diameter).

• That's the thing. I don't want the Sphere to be filled, I want just to create the outer shell. Nov 15, 2019 at 12:47
• And i guess that would make much less calls / loops Nov 15, 2019 at 12:50
• @JanisTaranda Please don't change the problem of the question after you received an answer. If you have a different problem, please ask a new question. Nov 15, 2019 at 16:51
• in the original I also wrote that I prefer the Sphere not to be filled. So not much is changed in terms if The problem. Nov 15, 2019 at 19:41

Found this https://jsfiddle.net/mtimmerm/ay2adpwb/

I think it needs some tweaking for spacing between voxels, but it works and was what I wanted.

Code:

var radiusInVoxels=10.5
var voxelsize=1/radiusInVoxels;
var shrink=0.9;
var material = new THREE.MeshLambertMaterial( { color: 0xd0d0d0, transparent: true, opacity: 0.85 } );
var group = new THREE.Group();

function drawSphere(R) {
var maxR2 = Math.floor(R*R);
var x,y,z;
var zx = Math.floor(R);
for (x=0; ;++x)
{
//max z for this x value.
while(x*x+zx*zx > maxR2 && zx>=x)
--zx;
if (zx<x)
break; //with this x, z can't be largest
z=zx;
for(y=0; ;++y)
{
while(x*x+y*y+z*z > maxR2 && z>=x && z>=y)
--z;
if (z<x||z<y)
break; //with this x and y, z can't be largest
fillAll(x,y,z); //... and up to 23 reflections of it
}
}
}

function fill1(x,y,z) {
var box = new THREE.BoxGeometry( voxelsize*shrink, voxelsize*shrink, voxelsize*shrink );
box = new THREE.Mesh( box, material );
box.translateX(x*voxelsize);
box.translateY(y*voxelsize);
box.translateZ(z*voxelsize);
group.add( box );
}
function fillSigns(x,y,z) {
fill1(x,y,z);
for (;;) {
if ((z=-z) >= 0) {
if ((y=-y) >= 0) {
if ((x=-x) >= 0) {
break;
}
}
}
fill1(x,y,z);
}
}
function fillAll(x,y,z) {
fillSigns(x,y,z);
if (z>y) {
fillSigns(x,z,y);
}
if (z>x && z>y) {
fillSigns(z,y,x);
}
}

var scene = new THREE.Scene();
var camera = new THREE.PerspectiveCamera( 75,
window.innerWidth/window.innerHeight, 0.1, 1000 );

var renderer = new THREE.WebGLRenderer();
renderer.setSize( window.innerWidth, window.innerHeight );
document.body.appendChild( renderer.domElement );

scene.add(new THREE.AmbientLight( 0xFFFFFF, .1 ));
var light = new THREE.DirectionalLight( 0xFFFFFF, .9 );
light.position.set( 5, 10, 10 );
scene.add( light );

drawSphere(radiusInVoxels);
scene.add( group );

camera.position.z = 2;
camera.position.x = 0;

var render = function (ms) {
requestAnimationFrame( render );

var angle1 = ms/10000;angle1-=Math.floor(angle1);
var angle2 = (ms+1200)/17000;angle2-=Math.floor(angle2);
group.rotation.x= Math.sin(angle2*Math.PI*2)*0.25+0.6;
group.rotation.y = angle1*Math.PI*2;
renderer.render(scene, camera);
};

requestAnimationFrame( render );