0

My current solution is to iterate NxNxN steps - just as if I were building a cube of cubes - except only placing a cube at each step if the position of that cube is within a given radius (N * cube size). Simple pseudocode: 

for x = x_min -> x_max
    for y = y_min -> y_max
        for z = z_min -> z_max
            cube_origin = Vec3(x,y,z)
            if (cube_origin.magntidue() < R)
                place_cube(cube_origin)

Is there anything more efficient for generating a sphere of cubes? Even better if there was a way to construct it in such a way as to only have to generate the outer hull of cubes, and the core could be filled in dynamically as needed.

mbradber
  • 489
  • 5
  • 17
  • 1
    It's always going to be `O(N^3)` (unless you only generate the surface). But you can reduce the number of cell processed by *scanline rasterizing* the sphere, using its symmetry properties and Pythagoras. [Bresenham's circle algorithm](https://www.geeksforgeeks.org/bresenhams-circle-drawing-algorithm/) can be used to efficiently rasterize each layer. – meowgoesthedog Mar 26 '18 at 21:07
  • 1
    You could generate one octant of the sphere, then copy it seven times. – Beta Mar 26 '18 at 21:46
  • A friend of mine suggested starting at the Sphere axes end points (R,0,0 etc.) and then running a flood fill, recursively checking the 8 candidate spots around the known points. This seems promising but I'm concerned about keeping all the blocks 'flush' with this approach... – mbradber Mar 26 '18 at 23:31
  • Possible duplicate of [Drawing 3D sphere in C/C++](https://stackoverflow.com/questions/25057471/drawing-3d-sphere-in-c-c) – Spektre Mar 27 '18 at 07:20
  • see the duplicate [Drawing 3D sphere in C/C++](https://stackoverflow.com/questions/25057471/drawing-3d-sphere-in-c-c) also you can speed up by comparing `distance_from_center ^ 2 < R^2` no need for `sqrt` to slow things down ... The surface generation used in the link is `O(N^2)` so that is way faster than yours `O(N^3)` – Spektre Mar 27 '18 at 07:21

0 Answers0