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.
CPP
#include <iostream>#include <cmath>// this header file contains get<0> and get<1> function#include <utility>#include <list>#include <map>using namespace std;// map to store the voxelsmap<int, list<pair<int, int> > > mymap;map<int, list<pair<int, int> > >::iterator itr;// this function will store single voxelvoid putpixelone(int m, int n, int p){ mymap[m].push_back(make_pair(n, p));}// function to store some particular type of voxelvoid 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 voxelsvoid 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 abovevoid 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 spherevoid showallpoints(map<int, list<pair<int, int> > >& mymap){ int count = 0; for (itr = mymap.begin(); itr != mymap.end(); ++itr) { list<pair<int, int> > l = itr->second; list<pair<int, int> >::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 programint main(){ int cx, cy, cz; cin >> cx >> cy >> cz; int r; cin >> r; drawsphere(cx, cy, cz, r); showallpoints(mymap);} |
Python3
#Python codefrom typing import List, Tuplefrom collections import defaultdictimport math# defaultdict to store the voxelsmymap = defaultdict(list)# this function will store single voxeldef putpixelone(m, n, p): mymap[m].append((n, p)) # function to store some particular type of voxeldef putpixelmiddle(a, b, c, x, y, 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 voxelsdef putpixeldouble(a, b, c, x, y, z): for j in range(3): putpixelone(a + x, b + y, c + z) b, c = c, b a, b = b, a for j in range(3): putpixelone(-a + x, b + y, c + z) b, c = c, b a, b = b, a for j in range(3): putpixelone(a + x, -b + y, c + z) b, c = c, b a, b = b, a for j in range(3): putpixelone(-a + x, -b + y, c + z) b, c = c, b a, b = b, a for j in range(3): putpixelone(a + x, b + y, -c + z) b, c = c, b a, b = b, a for j in range(3): putpixelone(-a + x, b + y, -c + z) b, c = c, b a, b = b, a for j in range(3): putpixelone(a + x, -b + y, -c + z) b, c = c, b a, b = b, a for j in range(3): putpixelone(-a + x, -b + y, -c + z) b, c = c, b a, b = b, a# Explained abovedef putpixelsingle(a, b, c, x, y, 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.def putpixeledge2(a, b, c, x, y, z): for j in range(3): putpixelone(a + x, b + y, c + z) a, b = b, a b, c = c, b for j in range(3): putpixelone(-a + x, b + y, c + z) a, b = b, a b, c = c, b for j in range(3): putpixelone(a + x, -b + y, c + z) a, b = b, a b, c = c, b for j in range(3): putpixelone(-a + x, -b + y, c + z) a, b = b, a b, c = c, b for j in range(3): putpixelone(a + x, b + y, -c + z) a, b = b, a b, c = c, b for j in range(3): putpixelone(-a + x, b + y, -c + z) a, b = b, a b, c = c, b for j in range(3): putpixelone(a + x, -b + y, -c + z) a, b = b, a b, c = c, b for j in range(3): putpixelone(-a + x, -b + y, -c + z) a, b = b, a b, c = c, b# 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.def putpixeledge1(a, b, c, x, y, 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.def putpixelall(a, b, c, x, y, 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.def drawsphere(x, y, z, r): i = 0 j = 0 k0 = r k = k0 s0 = 0 s = s0 v0 = r - 1 v = v0 l0 = 2 * v0 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 and (s != v or j != k): # this if, else and else if condition # can easily build using figure 2, 3 if i == 0 and 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 elif i == j and j != k and i != 0: putpixeledge2(i, j, k, x, y, z) # center voxel of c-octants elif i == j and j == k: putpixelsingle(i, j, k, x, y, z) # voxels shared between q1 and q6 elif j == k and i < k and i < j: putpixeldouble(i, j, k, x, y, z) # starting voxel of q-octant elif i == 0 and 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 and 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 spheredef showallpoints(mymap: dict) -> None: count = 0 for key, values in mymap.items(): for value in values: print(f"{key}, {value[0]}, {value[1]}") count += 1 print() print(count)# Driver programif __name__ == "__main__": cx, cy, cz = map(int, input().split()) r = int(input()) drawsphere(cx, cy, cz, r) showallpoints(mymap) # This code is contributed by Utkrash |
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)
References : http://www.sciencedirect.com/science/article/pii/S0304397515010178#tl0010
If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.uk or mail your article to review-team@neveropen.co.uk. See your article appearing on the neveropen main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
