Алгоритм для геодезической сферы
Я должен сделать сферу из шариков меньшего размера, равномерно распределенных. Я думаю, что оптимальный способ — построить геодезическую сферу на основе треугольников и использовать вершины в качестве средних точек моих шаров. Но я не могу написать алгоритм, генерирующий вершины.
Ответ в C ++ или псевдокоде будет лучше.
Пример геодезической сферы: http://i.stack.imgur.com/iNQfP.png
Решение
Используя ссылку, которую мне дал @Muckle_ewe, я смог написать следующий алгоритм:
Вне main()
class Vector3d { // this is a pretty standard vector class
public:
double x, y, z;
...
}
void subdivide(const Vector3d &v1, const Vector3d &v2, const Vector3d &v3, vector<Vector3d> &sphere_points, const unsigned int depth) {
if(depth == 0) {
sphere_points.push_back(v1);
sphere_points.push_back(v2);
sphere_points.push_back(v3);
return;
}
const Vector3d v12 = (v1 + v2).norm();
const Vector3d v23 = (v2 + v3).norm();
const Vector3d v31 = (v3 + v1).norm();
subdivide(v1, v12, v31, sphere_points, depth - 1);
subdivide(v2, v23, v12, sphere_points, depth - 1);
subdivide(v3, v31, v23, sphere_points, depth - 1);
subdivide(v12, v23, v31, sphere_points, depth - 1);
}
void initialize_sphere(vector<Vector3d> &sphere_points, const unsigned int depth) {
const double X = 0.525731112119133606;
const double Z = 0.850650808352039932;
const Vector3d vdata[12] = {
{-X, 0.0, Z}, { X, 0.0, Z }, { -X, 0.0, -Z }, { X, 0.0, -Z },
{ 0.0, Z, X }, { 0.0, Z, -X }, { 0.0, -Z, X }, { 0.0, -Z, -X },
{ Z, X, 0.0 }, { -Z, X, 0.0 }, { Z, -X, 0.0 }, { -Z, -X, 0.0 }
};
int tindices[20][3] = {
{0, 4, 1}, { 0, 9, 4 }, { 9, 5, 4 }, { 4, 5, 8 }, { 4, 8, 1 },
{ 8, 10, 1 }, { 8, 3, 10 }, { 5, 3, 8 }, { 5, 2, 3 }, { 2, 7, 3 },
{ 7, 10, 3 }, { 7, 6, 10 }, { 7, 11, 6 }, { 11, 0, 6 }, { 0, 1, 6 },
{ 6, 1, 10 }, { 9, 0, 11 }, { 9, 11, 2 }, { 9, 2, 5 }, { 7, 2, 11 }
};
for(int i = 0; i < 20; i++)
subdivide(vdata[tindices[i][0]], vdata[tindices[i][1]], vdata[tindices[i][2]], sphere_points, depth);
}
Тогда в main():
vector<Vector3d> sphere_points;
initialize_sphere(sphere_points, DEPTH); // where DEPTH should be the subdivision depth
for(const Vector3d &point : sphere_points)
const Vector3d point_tmp = point * RADIUS + CENTER; // Then for the sphere I want to draw, I iterate over all the precomputed sphere points and with a linear function translate the sphere to its CENTER and chose the proper RADIUS
Вам на самом деле нужно всего лишь использовать initialize_sphere() один раз и используйте результат для каждой сферы, которую вы хотите нарисовать.
Другие решения
Хорошо известны алгоритмы триангуляции поверхностей. Вы должны быть в состоянии использовать Библиотека триангулированных поверхностей GNU создать подходящую сетку, если вы не хотите кодировать одну из них самостоятельно.
Я делал это раньше для графического проекта, алгоритм, который я использовал, подробно описан на этом сайте.
http://www.opengl.org.ru/docs/pg/0208.html
просто игнорируйте любые вызовы рисования openGL и кодируйте только те части, которые имеют дело с созданием реальных вершин
Это зависит от количества треугольников, которые вы хотите, чтобы сфера имела. Вы можете потенциально иметь бесконечное разрешение.
Сначала сфокусируйтесь на создании купола, позже вы можете удвоить его, взяв отрицательные координаты вашего верхнего купола. Вы будете генерировать сферу, связывая ряды треугольников.
Ваши треугольники равносторонние, поэтому определитесь с длиной.
Разделите 2 (pi) r на количество треугольников в нижнем ряду купола.
Это будет длина каждой стороны каждого треугольника.
Далее необходимо создать концентрический круг, который пересекает поверхность сферы.
Между этим кругом и основанием купола будет ваш первый ряд.
Вам нужно будет найти угол наклона каждого треугольника. (Я опубликую позже, когда я это выясню)
Повторяйте процесс для каждого концентрического круга (генерирующей строки), пока высота строки * не станет равной числу строк приблизительно 2 (pi) r, с которого вы начали.
Я постараюсь запрограммировать это позже, если у меня будет шанс. Вы также можете попробовать опубликовать на форуме по математике.