Dado el centro de la esfera y su radio. su tarea es almacenar de manera eficiente todos los puntos enteros necesarios para mostrar una esfera en la pantalla de la computadora de píxeles y este algoritmo generará una esfera ingenua creando vóxeles por sus arcos ingenuos. NS3 significa esfera ingenua por suma de cuadrados y LS3 significa esfera reticular por suma de cuadrados.
Ejemplos:
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)
Le sugiero encarecidamente que, si no tiene ningún requisito previo en este campo, vaya al siguiente enlace. Esto lo ayudará a obtener algunos requisitos previos y conceptos necesarios para comprender la implementación y el algoritmo siguientes.
El algoritmo LS3 se centra principalmente en generar los vóxeles de prima quadraginta . prima quadraginta se forma cuando una esfera discreta se divide en 48 partes, de modo que las 48 partes tienen alguna relación simétrica y todas pueden generarse utilizando cualquiera de sus partes. esa parte se llama prima quadraginta (ver figura 2). De manera similar, quadraginta octant se define como prima qudraginta excepto que se divide en 8 partes iguales en lugar de 48. quadaginta octant contiene 6 prima quadraginta que se muestran claramente en la figura a continuación. Q denota prima quadraginta (q-octante) y C denota quadraginta octante (c-octante). Un arco ingenuo son aquellos conjuntos de vóxeles que tienen la misma coordenada x en prima quadraginta (en la figura anterior, los vóxeles rojos están haciendo un arco ingenuo).
A fuerza de la propiedad simétrica 48, se puede desarrollar toda una esfera discreta a partir de su prima quadraginta. la limitación de usar la simetría 48 es que algunos de los vóxeles de q-octant se repetirán porque comparten un borde o vóxeles con otros prima quadraginta adyacentes. por ejemplo, en la figura anterior, los vóxeles que se muestran en gris pertenecen a dos o más octantes q .
Nuestro algoritmo generará algunos vóxeles repetidos, por lo tanto, debemos hacer algunas restricciones en los vóxeles de entrada.
Para hacer esto, he incluido algunas funciones en mi implementación que son:
Todos estos métodos se centran principalmente en los vóxeles grises (consulte la figura anterior), espere un putpixelall() que producirá todos los vóxeles excepto los vóxeles grises mediante el uso de simetría 48 sin ninguna restricción.
putpixeledge1 : Esta función producirá todos los vóxeles que tengan exactamente una coordenada cero
y si procedemos a buscar otro vóxel usando simetría y tomar una imagen con respecto a ese
eje de coordenadas cero (este (0, 2, -1) vóxel tendrá la misma image si tomamos una imagen con respecto al eje x) entonces resulta
ser el mismo voxel.
putpixeledge2 : este conjunto de vóxeles que tienen las coordenadas x e y son iguales (ver prima quadraginta figura 2). Para almacenar estos vóxeles, debemos buscar una relación entre los octantes q1 y q2 (ver la tabla anterior). puede lograr la coordenada general de cualquier vóxel en q2 desde q1 intercambiando primero (x, y) y luego (y, z).
putpixelsingle : estos píxeles se cuentan mucho menos. Están situados en el medio del quadraginta octante (c octante) y se comparten con todos los q-octantes que se encuentran en el mismo c-octante. Para obtener estos vóxeles podemos ver la tabla anterior y escribir todos los vóxeles correspondientes a su cooctante.
putpixeldouble : este conjunto de vóxeles que tienen coordenadas y y z son iguales (ver prima qudraginta figura 2). Para almacenar estos vóxeles, necesitamos encontrar una relación entre q1 y q6 octantes (ver tabla). puede lograr la coordenada general de cualquier vóxel en q6 desde q1 intercambiando primero (y, z) y luego (x, y).
putpixelmiddle : este conjunto de vóxeles se encuentra en aquellos puntos donde exactamente
el valor de dos coordenadas es NULO, lo que puede ayudarnos a encontrar las coordenadas de estos vóxeles (puede escribir las coordenadas
de estos vóxeles manualmente).
Necesitamos un almacenamiento eficiente de todos los puntos enteros (vóxeles) que serán formados por este algoritmo. Para almacenar estos puntos, usaremos hashmap y el valor clave de hashmap será la coordenada x del punto y el valor de los datos será una lista vinculada de pares de coordenadas y y z.
#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 voxels
map<int, list<pair<int, int> > > mymap;
map<int, list<pair<int, int> > >::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<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 program
int main()
{
int cx, cy, cz;
cin >> cx >> cy >> cz;
int r;
cin >> r;
drawsphere(cx, cy, cz, r);
showallpoints(mymap);
}
Entrada: Centro (0, 0, 0) Radio 3
Salida:
(-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)
Referencias:
http://www.sciencedirect.com/science/article/pii/S0304397515010178#tl0010
Este artículo es una contribución de Harsh kumar singh . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA