# LS3/NS3 sphere generation algorithm and its implementation

• Difficulty Level : Hard
• Last Updated : 09 Feb, 2018

Given center of the sphere and its radius. your task is to store efficiently all the integer points required to show a sphere on the computer screen of pixels and This algorithm will generate naive sphere by creating voxels by its naive arcs. NS3 stands for naive sphere by sum of squares and LS3 stands for lattice sphere by sum of squares.

Examples:

```Input : Center(0, 0, 0) Radius 1
Output : (-1, 0, 0), (0, 0, 1), (0, 0, -1), (0, 1, 0),
(0, -1, 0), (1, 0, 0)
6(Total no. of points)

Input : Center(0, 0, 0) Radius 2
Output :(-2, 0, 0)(-1, 1, 1)(-1, -1, 1)(-1, 1, -1)
(-1, -1, -1)(0, 0, 2)(0, 0, -2)(0, 2, 0)
(0, -2, 0)(0, 1, 2)(0, 2, 1)(0, -1, 2)
(0, 1, -2)(0, -1, -2)(0, -2, 1)(0, 2, -1)
(0, -2, -1)(1, 2, 0)(1, 0, 2)(1, -2, 0)
(1, 2, 0)(1, -2, 0)(1, 0, -2)(1, 0, 2)
(1, 0, -2)(1, 1, 1)(1, -1, 1)(1, 1, -1)
(1, -1, -1)(2, 0, 0)(2, 0, 1)(2, 0, 1)
(2, 0, -1)(2, 0, -1)(2, 1, 0)(2, -1, 0)
(2, 1, 0)(2, -1, 0)
38 (Total no. of points)
```

I strongly suggest you that if you do not have any prerequisites in this field than go to below link. This will help you to gain some prerequisites and concepts which are required to understand the following implementation and algorithm.

Algorithm LS3 primarily focuses on generating the voxels of prima quadraginta . prima quadraginta is formed when a discrete sphere is partitioned into 48 parts such that all 48 parts having some symmetrical relation and they all can be generated by using any one of its parts. that one part is called as prima quadraginta (see figure 2). similarly, quadraginta octant defined as same as prima qudraginta except that it is partitioned into 8 equal parts instead of 48. quadaginta octant contains 6 prima quadraginta which are clearly shown in the figure below. Q denotes to prima quadraginta (q-octant) and C denotes to quadraginta octant(c-octant).a naive arc are those set of voxels which are having same x coordinate in prima quadraginta (in above figure, the red voxels are making a naive arc).

By dint of 48 symmetric property, a whole discrete sphere can be developed from its prima quadraginta. the limitation of using 48 symmetry is that some of the voxels of q-octant will be repeated because they are sharing an edge or voxels with other adjacent prima quadraginta. for example, In above figure, the voxels shown in grey belongs to two or more q-octants.

Our algorithm will generate some repeated voxels therefore, we need to make some restrictions on input voxels.
In order to do this, I have included some functions in my implementation which are:

All these methods principally focuses on grey voxels (See above figure) expect one putpixelall() which is going to produce all voxels except grey voxels by using 48 symmetry without any restrictions.

putpixeledge1 : This function will produce all voxels which has exactly one coordinate zero
and if we proceed to find another voxel using symmetry and take an image with respect to that zero coordinate
axis (this (0, 2, -1) voxel will have the same image if we take an image with respect to the x-axis) then it comes
out to be the same voxel.

putpixeledge2 : These set of voxels having x and y coordinate are same (see prima quadraginta figure 2).In order to store these voxels we have to look for a relation between q1 and q2 octants( see above table). you can achieve the general coordinate of any voxel in q2 from q1 by swapping first (x, y) and then (y, z).

putpixelsingle : These pixels is very less in count.they are situated in the middle of quadraginta octant (c octant) and shared with all the q-octants which are lying in the same c-octant. to obtained these voxels we can see the above table and write all the voxels corresponding to its c-octant.

putpixeldouble : These set of voxels having y and z coordinate are same (see prima qudraginta figure 2).In order to store these voxels we need to find a relation between q1 and q6 octants( see table). you can achieve the general coordinate of any voxel in q6 from q1 by swapping first (y, z) and then (x, y).

putpixelmiddle : These set of voxels are located in those points where exactly two coordinate
value is NULL which can help us to find to obtain the coordinates of these voxels( you can write the coordinates
of these voxels manually).

We need an efficient storage of all the integer points (voxels) which will be formed by this algorithm. In order to store these points, we will use hashmap and key value of hashmap will be x coordinate of point and data value will be linked list of pair of y and z coordinate.

 `#include ``#include `` ` `// this header file contains get<0> and get<1> function``#include `` ` `#include ``#include ``using` `namespace` `std;`` ` `// map to store the voxels``map<``int``, list > > mymap;``map<``int``, list > >::iterator itr;`` ` `// this function will store single voxel``void` `putpixelone(``int` `m, ``int` `n, ``int` `p)``{``    ``mymap[m].push_back(make_pair(n, p));``}`` ` `// function to store some particular type of voxel``void` `putpixelmiddle(``int` `a, ``int` `b, ``int` `c, ``int` `x, ``int` `y, ``int` `z)``{``    ``putpixelone(a + x, b + y, c + z);``    ``putpixelone(a + x, b + y, -c + z);``    ``putpixelone(a + x, c + y, b + z);``    ``putpixelone(a + x, -c + y, b + z);``    ``putpixelone(c + x, a + y, b + z);``    ``putpixelone(-c + x, a + y, b + z);``}`` ` `// This program will generate 24 voxels``void` `putpixeldouble(``int` `a, ``int` `b, ``int` `c, ``int` `x, ``int` `y, ``int` `z)``{``    ``for` `(``int` `j = 0; j < 3; j++) {``        ``putpixelone(a + x, b + y, c + z);``        ``swap(b, c);``        ``swap(a, b);``    ``}``    ``for` `(``int` `j = 0; j < 3; j++) {``        ``putpixelone(-a + x, b + y, c + z);``        ``swap(b, c);``        ``swap(a, b);``    ``}``    ``for` `(``int` `j = 0; j < 3; j++) {``        ``putpixelone(a + x, -b + y, c + z);``        ``swap(b, c);``        ``swap(a, b);``    ``}``    ``for` `(``int` `j = 0; j < 3; j++) {``        ``putpixelone(-a + x, -b + y, c + z);``        ``swap(b, c);``        ``swap(a, b);``    ``}``    ``for` `(``int` `j = 0; j < 3; j++) {``        ``putpixelone(a + x, b + y, -c + z);``        ``swap(b, c);``        ``swap(a, b);``    ``}``    ``for` `(``int` `j = 0; j < 3; j++) {``        ``putpixelone(-a + x, b + y, -c + z);``        ``swap(b, c);``        ``swap(a, b);``    ``}``    ``for` `(``int` `j = 0; j < 3; j++) {``        ``putpixelone(a + x, -b + y, -c + z);``        ``swap(b, c);``        ``swap(a, b);``    ``}``    ``for` `(``int` `j = 0; j < 3; j++) {``        ``putpixelone(-a + x, -b + y, -c + z);``        ``swap(b, c);``        ``swap(a, b);``    ``}``}`` ` `// Explained above``void` `putpixelsingle(``int` `a, ``int` `b, ``int` `c, ``int` `x,``                    ``int` `y, ``int` `z)``{``    ``putpixelone(a + x, b + y, c + z);``    ``putpixelone(-a + x, b + y, c + z);``    ``putpixelone(a + x, -b + y, c + z);``    ``putpixelone(-a + x, -b + y, c + z);``    ``putpixelone(a + x, b + y, -c + z);``    ``putpixelone(-a + x, b + y, -c + z);``    ``putpixelone(a + x, -b + y, -c + z);``    ``putpixelone(-a + x, -b + y, -c + z);``}``// This program will generate 24 voxels.``void` `putpixeledge2(``int` `a, ``int` `b, ``int` `c, ``int` `x,``                   ``int` `y, ``int` `z)``{`` ` `    ``for` `(``int` `j = 0; j < 3; j++) {``        ``putpixelone(a + x, b + y, c + z);``        ``swap(a, b);``        ``swap(b, c);``    ``}``    ``for` `(``int` `j = 0; j < 3; j++) {``        ``putpixelone(-a + x, b + y, c + z);``        ``swap(a, b);``        ``swap(b, c);``    ``}``    ``for` `(``int` `j = 0; j < 3; j++) {``        ``putpixelone(a + x, -b + y, c + z);``        ``swap(a, b);``        ``swap(b, c);``    ``}``    ``for` `(``int` `j = 0; j < 3; j++) {``        ``putpixelone(-a + x, -b + y, c + z);``        ``swap(a, b);``        ``swap(b, c);``    ``}``    ``for` `(``int` `j = 0; j < 3; j++) {``        ``putpixelone(a + x, b + y, -c + z);``        ``swap(a, b);``        ``swap(b, c);``    ``}``    ``for` `(``int` `j = 0; j < 3; j++) {``        ``putpixelone(-a + x, b + y, -c + z);``        ``swap(a, b);``        ``swap(b, c);``    ``}``    ``for` `(``int` `j = 0; j < 3; j++) {``        ``putpixelone(a + x, -b + y, -c + z);``        ``swap(a, b);``        ``swap(b, c);``    ``}``    ``for` `(``int` `j = 0; j < 3; j++) {``        ``putpixelone(-a + x, -b + y, -c + z);``        ``swap(a, b);``        ``swap(b, c);``    ``}``}``// after excluding the repeated pixels from the set all 48``// pixels we will left with only 24 pixels so, we have``// defined all the voxels given below.``void` `putpixeledge1(``int` `a, ``int` `b, ``int` `c, ``int` `x, ``int` `y, ``int` `z)``{``    ``putpixelone(a + x, b + y, c + z);``    ``putpixelone(a + x, c + y, b + z);``    ``putpixelone(a + x, -b + y, c + z);``    ``putpixelone(a + x, b + y, -c + z);``    ``putpixelone(a + x, -b + y, -c + z);``    ``putpixelone(a + x, -c + y, b + z);``    ``putpixelone(a + x, c + y, -b + z);``    ``putpixelone(a + x, -c + y, -b + z);``    ``putpixelone(b + x, c + y, a + z);``    ``putpixelone(b + x, a + y, c + z);``    ``putpixelone(b + x, -c + y, a + z);``    ``putpixelone(b + x, c + y, -a + z);``    ``putpixelone(b + x, -c + y, -a + z);``    ``putpixelone(b + x, a + y, -c + z);``    ``putpixelone(b + x, -a + y, c + z);``    ``putpixelone(b + x, -a + y, -c + z);``    ``putpixelone(c + x, a + y, b + z);``    ``putpixelone(c + x, -a + y, b + z);``    ``putpixelone(c + x, a + y, -b + z);``    ``putpixelone(c + x, -a + y, -b + z);``    ``putpixelone(c + x, b + y, a + z);``    ``putpixelone(c + x, -b + y, a + z);``    ``putpixelone(c + x, b + y, -a + z);``    ``putpixelone(c + x, -b + y, -a + z);``}`` ` `// voxel formation by 48 symmetry.``void` `putpixelall(``int` `a, ``int` `b, ``int` `c, ``int` `x,``                 ``int` `y, ``int` `z)``{``    ``putpixelone(a + x, b + y, c + z);``    ``putpixelone(b + x, a + y, c + z);``    ``putpixelone(c + x, b + y, a + z);``    ``putpixelone(a + x, c + y, b + z);``    ``putpixelone(c + x, a + y, b + z);``    ``putpixelone(b + x, c + y, a + z);``    ``putpixelone(-a + x, -b + y, c + z);``    ``putpixelone(-b + x, -a + y, c + z);``    ``putpixelone(c + x, -b + y, -a + z);``    ``putpixelone(-a + x, c + y, -b + z);``    ``putpixelone(c + x, -a + y, -b + z);``    ``putpixelone(-b + x, c + y, -a + z);``    ``putpixelone(a + x, -b + y, -c + z);``    ``putpixelone(-b + x, a + y, -c + z);``    ``putpixelone(-c + x, -b + y, a + z);``    ``putpixelone(a + x, -c + y, -b + z);``    ``putpixelone(-c + x, a + y, -b + z);``    ``putpixelone(-b + x, -c + y, a + z);``    ``putpixelone(-a + x, b + y, -c + z);``    ``putpixelone(b + x, -a + y, -c + z);``    ``putpixelone(-c + x, b + y, -a + z);``    ``putpixelone(-a + x, -c + y, b + z);``    ``putpixelone(-c + x, -a + y, b + z);``    ``putpixelone(b + x, -c + y, -a + z);``    ``putpixelone(-a + x, b + y, c + z);``    ``putpixelone(b + x, -a + y, c + z);``    ``putpixelone(c + x, b + y, -a + z);``    ``putpixelone(-a + x, c + y, b + z);``    ``putpixelone(c + x, -a + y, b + z);``    ``putpixelone(b + x, c + y, -a + z);``    ``putpixelone(a + x, -b + y, c + z);``    ``putpixelone(-b + x, a + y, c + z);``    ``putpixelone(c + x, -b + y, a + z);``    ``putpixelone(a + x, c + y, -b + z);``    ``putpixelone(c + x, a + y, -b + z);``    ``putpixelone(-b + x, c + y, a + z);``    ``putpixelone(a + x, b + y, -c + z);``    ``putpixelone(b + x, a + y, -c + z);``    ``putpixelone(-c + x, b + y, a + z);``    ``putpixelone(a + x, -c + y, b + z);``    ``putpixelone(-c + x, a + y, b + z);``    ``putpixelone(b + x, -c + y, a + z);``    ``putpixelone(-a + x, -b + y, -c + z);``    ``putpixelone(-b + x, -a + y, -c + z);``    ``putpixelone(-c + x, -b + y, -a + z);``    ``putpixelone(-a + x, -c + y, -b + z);``    ``putpixelone(-c + x, -a + y, -b + z);``    ``putpixelone(-b + x, -c + y, -a + z);``}`` ` `// detailed explanation of this algorithm is``// given in above link.``void` `drawsphere(``int` `x, ``int` `y, ``int` `z, ``int` `r)``{``    ``int` `i = 0, j = 0;``    ``int` `k0 = r;``    ``int` `k = k0;``    ``int` `s0 = 0;``    ``int` `s = s0;``    ``int` `v0 = r - 1;``    ``int` `v = v0;``    ``int` `l0 = 2 * v0;``    ``int` `l = l0;`` ` `    ``// this while loop will form naive arcs``    ``while` `(i <= k) {`` ` `        ``// this while will form voxels in naive arcs``        ``while` `(j <= k) {``            ``if` `(s > v) {``                ``k = k - 1;``                ``v = v + l;``                ``l = l - 2;``            ``}``            ``if` `((j <= k) && ((s != v) || (j != k))) {`` ` `                ``// this if, else and else if condition``                ``// can easily build using figure 2, 3``                ``if` `(i == 0 && j != 0)`` ` `                    ``// First naive arc pixels and each``                    ``// pixel is shared with two q-octants``                    ``putpixeledge1(i, j, k, x, y, z);`` ` `                ``// voxels shared between q1 and q2``                ``else` `if` `(i == j && j != k && i != 0)``                    ``putpixeledge2(i, j, k, x, y, z);`` ` `                ``// center voxel of c-octants``                ``else` `if` `(i == j && j == k)``                    ``putpixelsingle(i, j, k, x, y, z);`` ` `                ``// voxels shared between q1 and q6``                ``else` `if` `(j == k && i < k && i < j)``                    ``putpixeldouble(i, j, k, x, y, z);`` ` `                ``// starting voxel of q-octant``                ``else` `if` `(i == 0 && j == 0)``                    ``putpixelmiddle(i, j, k, x, y, z);`` ` `                ``// voxels inside the q-octant``                ``else``                    ``putpixelall(i, j, k, x, y, z);``            ``}``            ``s = s + 2 * j + 1;``            ``j = j + 1;``        ``}``        ``s0 = s0 + 4 * i + 2;``        ``i = i + 1;`` ` `        ``while` `((s0 > v0) && (i <= k0)) {``            ``k0 = k0 - 1;``            ``v0 = v0 + l0;``            ``l0 = l0 - 2;``        ``}``        ``j = i;``        ``k = k0;``        ``v = v0;``        ``l = l0;``        ``s = s0;``    ``}``}``// Print out all the voxels of discrete sphere``void` `showallpoints(map<``int``, list > >& mymap)``{``    ``int` `count = 0;`` ` `    ``for` `(itr = mymap.begin(); itr != mymap.end(); ++itr) {``        ``list > l = itr->second;``        ``list >::iterator it;``        ``for` `(it = l.begin(); it != l.end(); ++it) {``            ``cout << itr->first << ``", "` `<< get<0>(*it)``                 ``<< ``", "` `<< get<1>(*it) << endl;``            ``count += 1;``        ``}``    ``}``    ``cout << endl;``    ``cout << count << endl;``}``// Driver program``int` `main()``{``    ``int` `cx, cy, cz;``    ``cin >> cx >> cy >> cz;``    ``int` `r;``    ``cin >> r;``    ``drawsphere(cx, cy, cz, r);``    ``showallpoints(mymap);``}`

Input : Center(0, 0, 0) Radius 3
Output:

```(-3, 0, 0)(-3, 1, 1)(-3, -1, 1)(-3, 1, -1)(-3, -1, -1)
(-2, 1, 2)(-2, 2, 1)(-2, -1, 2)(-2, -2, 1)(-2, 1, -2)
(-2, 2, -1)(-2, -1, -2)(-2, -2, -1)(-1, 1, 3)(-1, 3, 1)
(-1, -1, 3)(-1, -3, 1)(-1, 1, -3)(-1, 3, -1)(-1, -1, -3)
(-1, -3, -1)(-1, 2, 2)(-1, -2, 2)(-1, 2, -2)(-1, -2, -2)
(0, 0, 3)(0, 0, -3)(0, 3, 0)(0, -3, 0)(0, 1, 3)(0, 3, 1)
(0, -1, 3)(0, 1, -3)(0, -1, -3)(0, -3, 1)(0, 3, -1)
(0, -3, -1)(0, 2, 2)(0, 2, 2)(0, -2, 2)(0, 2, -2)
(0, -2, -2)(0, -2, 2)(0, 2, -2)(0, -2, -2)(1, 3, 0)
(1, 0, 3)(1, -3, 0)(1, 3, 0)(1, -3, 0)(1, 0, -3)(1, 0, 3)
(1, 0, -3)(1, 1, 3)(1, 3, 1)(1, -1, 3)(1, -3, 1)(1, 1, -3)
(1, 3, -1)(1, -1, -3)(1, -3, -1)(1, 2, 2)(1, -2, 2)(1, 2, -2)
(1, -2, -2)(2, 2, 0)(2, 0, 2)(2, -2, 0)(2, 2, 0)(2, -2, 0)
(2, 0, -2)(2, 0, 2)(2, 0, -2)(2, 0, 2)(2, 0, 2)(2, 0, -2)
(2, 0, -2)(2, 2, 0)(2, -2, 0)(2, 2, 0)(2, -2, 0)(2, 1, 2)
(2, 2, 1)(2, -1, 2)(2, -2, 1)(2, 1, -2)(2, 2, -1)(2, -1, -2)
(2, -2, -1)(3, 0, 0)(3, 0, 1)(3, 0, 1)(3, 0, -1)(3, 0, -1)
(3, 1, 0)(3, -1, 0)(3, 1, 0)(3, -1, 0)(3, 1, 1)(3, -1, 1)
(3, 1, -1)(3, -1, -1)
102 (Total no. of points)
```

This article is contributed by Harsh kumar singh. If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.