Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 49
Божественно
Вроде бы всего лишь еще одна математическая абстракция, но все же что-то есть в нем завораживающего и таинственного, в этом четвертом измерении.
Симпатично отрисовани и популярно объяснено, благодарствую!
И мне еще доказывали, что математика убивает творческое мышление.
И мне еще доказывали, что математика убивает творческое мышление.
Побочные эффекты проекции). Это и оптический обман и в контексте 3D она действительно прорастает сама в себя.
На самом деле я нечасто наблюдаю вращающегося симплексы Серпинского, а значит не могу утверждать, что все изображается правильно. Тем не менее, предположу что все так и есть. Фигура никуда не прорастает, просто вы видите не саму фигуру, а только ее проекцию. Проекция действительно «прорастает». Такое происходит и при проекции 3d объекта на 2d пространство — если смотреть на тень от вращающегося листа бумаги, можно увидеть как он в проекции постепенно «прорастает сам в себя», при этом проекция выроджается в линию, а потом «вырастает сам из себя».
Выглядит красиво. Вопрос-просьба: нельзя как-нибудь сделать, чтобы можно было вращать самостоятельно или интерактивно? Просто понять вращение 4-хмерной фигуры на видео достаточно сложно, а детали рассмотреть хотелось бы :)
Приходит на ум, только Java applet или Flash, естественно фотографии могут быть подготовлены заранее и их должно быть немного.
Приходит на ум, только Java applet или Flash, естественно фотографии могут быть подготовлены заранее и их должно быть немного.
Можно, но сложно. В рамках этой статьи точно не получится. Мне на ум приходит с++ + OpenGL.
Так сложно не надо, в смысле OpenGL. Я говорю просто подготовить 500 фотографий в различных поворотах и 6 кнопок поворотов сделать (дискретных).
В принципе если фотографии подготовите могу какой-нибудь UI на Java сделать с кнопками.
Примеры, как в интернет-магазине 3D панорамные делают. Например для 2D с поворотом 30 градусов, 12 фотографий, а учитывая симметричность фигуры, только 2.
Для 3-хмерной, если вращать относительно точки (относительно прямой не так интересно тоже 12), 12*12? Но думаю симметричность поможет :)
В принципе если фотографии подготовите могу какой-нибудь UI на Java сделать с кнопками.
Примеры, как в интернет-магазине 3D панорамные делают. Например для 2D с поворотом 30 градусов, 12 фотографий, а учитывая симметричность фигуры, только 2.
Для 3-хмерной, если вращать относительно точки (относительно прямой не так интересно тоже 12), 12*12? Но думаю симметричность поможет :)
для 4D, если вокруг каждой плоскости реализовать, будет 12 'степеней свободы'. Если брать по 20 градусов дискретизацию, то получится необходимость 12^18 картинок. Если учесть симметрию и прочие — будет на несколько порядков меньше и все-же циферки заоблачные. Согласен, можно что-то придумать чтобы как-то было похоже на правду, но думать несколько дней будем.
Единственное, что я могу посоветовать — взять исходники и переделать код поворота в point.cpp, чтоб оно вращало только по одной паре измерений, потом по другой…
Единственное, что я могу посоветовать — взять исходники и переделать код поворота в point.cpp, чтоб оно вращало только по одной паре измерений, потом по другой…
18^12
20 плохое число 90 градусов не получается, лучше уже тогда 15 :) Я может неправильно считаю
для 3D вращение вокруг точки центра (30 град) :(360/30)^2=144.
Почему 12 степеней свободы? Фигура однозначно задается точкой вершины на гиперсфере (все остальные точки тоже лежат на гиперсфере), а точка на гиперсфере имеет n-1 степеней свободы
для 3D вращение вокруг точки центра (30 град) :(360/30)^2=144.
Почему 12 степеней свободы? Фигура однозначно задается точкой вершины на гиперсфере (все остальные точки тоже лежат на гиперсфере), а точка на гиперсфере имеет n-1 степеней свободы
Не, неправильно я сказал, точка не задает на гиперсфере. В 3D 2 точки задают.
Я 360 делил на 20. Для 3D камера еще может быть повернута вокруг прямой, что проходит через центры камеры и объекта. (360/30)^3 = 1728. Хотя согласен, на практике, камеру лучше не вращать.
Да, что-то я не подумал, вы совершенно правы. Можно задавать положение камеры 3 углами и тогда будет 1728 картинок, что вполне можно реализовать. Вот только их нужно будет 50 часов рендерить)) на Core i5-2500k).
P. S. нужно еще времени подумать, мне кажется что что-то я упускаю с числом 1728.
Да, что-то я не подумал, вы совершенно правы. Можно задавать положение камеры 3 углами и тогда будет 1728 картинок, что вполне можно реализовать. Вот только их нужно будет 50 часов рендерить)) на Core i5-2500k).
P. S. нужно еще времени подумать, мне кажется что что-то я упускаю с числом 1728.
Ночью спать нужно, я понял, что неправильно вас понял).
2D (30 градусов) — 4 различных, (15 градусов) — 8 различных.
Посчитал для 3D. Точнее верхнюю и нижнюю оценку. 2 важных момента:
1. Тетраэдр задается 2 точками на сфере (необходимо и достаточно!)
2. Если зафиксировать 1 точку, то количество разных поворотов равно поворотам относительно 2D (4 или 8).
Позиция наблюдателя неизменна смотрит в точку (0), а тетраэдр вращается вокруг этой точки, что однозначно соответствует вращаемой сфере, описывающей его, что и задается 3 углами.
Количество одной точки в 30 градусов равно 12 * 4 (только одна половина) + 2 (полюса) = 50. Верхняя граница 50 * 4 = 200 для 15 градусов — (24*10+2)*8.
Для подсчета симметрий воспользуемся фактом, что при повороте все точки тетраэдра остаются в сетке (!) 50 точек — легко увидеть. Соответственно из сетки вырезать 4 треугольника (проекция тетраэдра на сферу) это и есть всевозможные точки одной вершины, так как вершины не занумерованы и симметричны. Точек сетки в этом треугольнике (1+2+3+4) умножим на количество поворотов * 4.
Верхняя граница (!) = 40, для 15 градусов — 36*8.
Но и тут есть симметрии :) Когда вершина лежит на краях треугольника, у меня получилось необходимо 1+6*4+4=29 (хотя не уверен что нижняя граница).
Боюсь в 4D простой геометрии не хватит, надо искать другие формулы.
Посчитал для 3D. Точнее верхнюю и нижнюю оценку. 2 важных момента:
1. Тетраэдр задается 2 точками на сфере (необходимо и достаточно!)
2. Если зафиксировать 1 точку, то количество разных поворотов равно поворотам относительно 2D (4 или 8).
Позиция наблюдателя неизменна смотрит в точку (0), а тетраэдр вращается вокруг этой точки, что однозначно соответствует вращаемой сфере, описывающей его, что и задается 3 углами.
Количество одной точки в 30 градусов равно 12 * 4 (только одна половина) + 2 (полюса) = 50. Верхняя граница 50 * 4 = 200 для 15 градусов — (24*10+2)*8.
Для подсчета симметрий воспользуемся фактом, что при повороте все точки тетраэдра остаются в сетке (!) 50 точек — легко увидеть. Соответственно из сетки вырезать 4 треугольника (проекция тетраэдра на сферу) это и есть всевозможные точки одной вершины, так как вершины не занумерованы и симметричны. Точек сетки в этом треугольнике (1+2+3+4) умножим на количество поворотов * 4.
Верхняя граница (!) = 40, для 15 градусов — 36*8.
Но и тут есть симметрии :) Когда вершина лежит на краях треугольника, у меня получилось необходимо 1+6*4+4=29 (хотя не уверен что нижняя граница).
Боюсь в 4D простой геометрии не хватит, надо искать другие формулы.
Судя по моему комментарию ниже представление точек в сферических координатах, поправьте если ошибаюсь. Всякий поворот можно представить как линейную комбинацию 2-х основных поворотов (для 3d). Соответственно комбинаций 6x12=72 (по поводу того, что какой-то поворот совпадает я похоже ошибся из-за 4-й точки она не может лежать в сетке).
Для 4D 6*12*12 = около 800. Для дискретизации в 2 раза больше, в 8 раз больше картинок, считаю это нормально.
Сможете отрендерить 800 картинок, используя формулу для сферичиских координаты (в ней повороты 3-м циклом делать по всем 3-м координатам, по первой координате можно в 2 раза меньше)?
Для 4D 6*12*12 = около 800. Для дискретизации в 2 раза больше, в 8 раз больше картинок, считаю это нормально.
Сможете отрендерить 800 картинок, используя формулу для сферичиских координаты (в ней повороты 3-м циклом делать по всем 3-м координатам, по первой координате можно в 2 раза меньше)?
> по первой координате можно в 2 раза меньше
Почему?
Почему?
Я снова ошибся. Все правильно для фигуры нельзя, это для выражения точки можно в 2-раза меньше. Хм.., может я еще что-то упустил. Главное это понять как вращается сфера в сферических координатах, а фигура сцеплена со сферой.
Можно, например, взять все самосовмещения 24-гранника. Их 24*6*4=576. Правда, «угол» между соседними это 60 градусов, а промежуточных положений (если на одно нажатие на стрелку выводить две картинки) будет гораздо больше.
Самосовмещений 600-гранника — 600*4*3=7200, угол между соседними 36 градусов. Многовато для отрисовки, но пространство они заполняют более равномерно.
Кстати, пространство вращений гиперсферы 6-мерно.
Самосовмещений 600-гранника — 600*4*3=7200, угол между соседними 36 градусов. Многовато для отрисовки, но пространство они заполняют более равномерно.
Кстати, пространство вращений гиперсферы 6-мерно.
Хотите покрутить? Легко. Только под Windows. Скачиваете astr73.narod.ru/4DView/serp4D.zip. Распаковываете, запускаете View4D.exe, загружаете в него serp.txt. Отключаете галку на Show Section, ставите на Show Projection. Левая кнопка — вращение, правая — Pan. Shift+левая кнопка — вращение в 4D. Ctrl+левая (вверх-вниз) — Zoom, Ctrl+правая (вправо-влево) — Pan в плоскости Z-W (в режиме Show Section увидите движение «пространства сечения» по фигуре).
Вот одна из интересных проекций этого ковра. В пространстве XYZ она выглядит, как 4-угольная пирамида, а при переходе в XYW превращается в правильный тетраэдр с еще одной вершиной в центре
video.yandex.ru/users/astr73/view/17
video.yandex.ru/users/astr73/view/17
quaternion.info/simplex.zip
404 Not Found
nginx/0.7.65
Исправьте, пожалуйста. Хочется посмотреть исходники.
404 Not Found
nginx/0.7.65
Исправьте, пожалуйста. Хочется посмотреть исходники.
Нашел правильную ссылку: quaternion.info/nts/simplex.zip
поправил. файл на месте, ссылка неправильной была(
Насчёт реализации с помощью OpenGL, DirectX. Нет никакой сложности в сортировке треугольников от дальних к ближним. Да, в общем случае, действительно, сортировка может потребовать деления треугольников на части. Но здесь не общий случай, ни одна из плоскостей на которых лежат треугольники не пересекает ни одного другого треугольника. Банальная BSP сортировка решит эту задачу.
Здесь сами треугольники пересекаются.
На рисунках этого не видно. Как в треугольнике Серпинского нет пересекающихся отрезков, так и в 3D симплексе нет пересекающихся треугольников. Это гарантируется IFS (iterated function system) с помощью которой строится фрактал, она копирует исходный симплекс (треугольник или тетраэдр) в 3 (или 4 для 3D) непересекающихся симплекса.
И на рисунках и на видео это сложно заметить, они перегружены количеством треугольников. Само по себе, в родном пространстве, ничего не пересекается. Но проекция 4D в 3D, которая изображена на видео, сопровождается огромным количеством таких пересечений.
Непонятно, каким образом пересечение проекций треугольников может помешать их сортировке в пространстве (BSP — binary SPACE partition), не важно какая у этого пространства размерность, хоть 2D, хоть 4D. Скажу больше, использовать BSP здесь даже слишком жирно. Все плоскости, на которых лежат, скажем, треугольники 3D симплексов, образуют 4 набора параллельных плоскостей, и это сводит сортировку к совсем уж простейшей процедуре.
1. Пересечение проекций в 3D не может помешать сортировке треугольников в 4D.
2. BSP тут жирно, но не достаточно.
3. В 3D, для тетраэдра Серпинского, сортировать еще проще, просто по центрам можно, даже не нужно знать, что есть только 4 набора параллельных плоскостей.
Еще раз. На видео — 2D анимация проекции с 3D, что была получена методом проекции с 4D.
Как вы и говорите, мы легко может отсортировать все треугольники в 4D пространстве, но проблема в том, что после проекции на 3D они не будут столь параллельными и ровными. Будут пересекаться. Проекция перспективная (все что было параллельным — пересекается в одной точке...). Итого, в 4D сортировать смысла нет, а 3D без резательных процессов не получится.
Еще одно уточнение: я гооврю про рендеринг 4D на OpenGL, DirectX.
2. BSP тут жирно, но не достаточно.
3. В 3D, для тетраэдра Серпинского, сортировать еще проще, просто по центрам можно, даже не нужно знать, что есть только 4 набора параллельных плоскостей.
Еще раз. На видео — 2D анимация проекции с 3D, что была получена методом проекции с 4D.
Как вы и говорите, мы легко может отсортировать все треугольники в 4D пространстве, но проблема в том, что после проекции на 3D они не будут столь параллельными и ровными. Будут пересекаться. Проекция перспективная (все что было параллельным — пересекается в одной точке...). Итого, в 4D сортировать смысла нет, а 3D без резательных процессов не получится.
Еще одно уточнение: я гооврю про рендеринг 4D на OpenGL, DirectX.
Теперь понял. Действительно, сортировка с помощью разделения пространства при двойной проекции предполагает, что части пространства сортируются уже не относительно точки, а относительно прямой. Придётся разбивать пространство гиперплоскостями параллельными этой прямой, и они будут пересекать треугольники симплексов.
Мои глаза!
Начал писать программу нашел ошибочку :) Вообще хороший признак рекурсии, если она начинается с минимального возможного шага. В данном случае начинается с 3-х, а должна с 2-х. Ошибка
Не -r/2!
Привожу пример для рекурсии начинающейся с 2-го измерения:
points[1][0] = + c; points[1][1] = - r / 2; //second point
points[2][0] = - c; points[2][1] = - r / 2; //3th point
Не -r/2!
Привожу пример для рекурсии начинающейся с 2-го измерения:
double c = (r * Math.sqrt(3) / 2);
double l = c * 2; // distance between points
points[0][0] = 0;
points[1][0] = r;
for (int i = 2; i < points.length; i++) {
double d = distanceToCenter(points[0]);
double q2 = (l * l - 2 * d * d) / (2 * Math.sqrt(l * l - d * d));
double q1 = Math.sqrt(d * d + q2 * q2);
for (int k = 0; k < i; k++) {
points[k][i - 1] = -q2; // set i-th dimension for all created points
points[i][k] = 0; // set all calculated dimension for new point
}
points[i][i - 1] = q1;
}
Ну это же не рекурсия, и не близко). Итеративный метод.
Перепроверил все расстояния. Все правильно считает. Можно было и с прямой начинать, но для наглядности я начал с треугольника, ошибки нет.
Код для проверки:
Перепроверил все расстояния. Все правильно считает. Можно было и с прямой начинать, но для наглядности я начал с треугольника, ошибки нет.
Код для проверки:
for (int i = 0; i <= dimensionalCount; i++)
qDebug() << points[i].distanceToCenter();
for (int i = 0; i <= dimensionalCount; i++)
for (int k = i + 1; k <= dimensionalCount; k++)
qDebug() << points[i].distanceTo(points[k]);
Похоже я ошибся, но проверьте сами. Запустил для 3-х мерного случая, выдало координату 1.06, что конечно близко к 1, но за рамками погрешности. Радиус задан 1. Как такое может быть?
Расстояние между точками — константа. Расстояние до центра — меняется.
Разобрался! Да ошибка была у меня, у вас все верно, только радиус сферы меняется (сбило с толку название переменной r).
Сумел перевести формулу точек симплекса в сферическую (n-полярную) систему координат. Как известно в этой системе поворот осуществляется очень просто (относительно центра координат), просто добавлением числа к одной из координат для всех точек.
Сумел перевести формулу точек симплекса в сферическую (n-полярную) систему координат. Как известно в этой системе поворот осуществляется очень просто (относительно центра координат), просто добавлением числа к одной из координат для всех точек.
// calculate points of simplex of specified radius
void simplex(double r, double[][] points){
int dimensions = points.length - 1;
// spherical coordinates
double[][] angles = new double[points.length][dimensions - 1];
simplexInSphericalCoordinates(0, 0, dimensions, angles);
// convert spherical into decart
for (int i = 0; i < points.length; i++) {
double sinMult = 1;
for (int d = 0; d < dimensions - 1; d++) {
points[i][d] = r * Math.cos(angles[i][d]) * sinMult;
sinMult *= Math.sin(angles[i][d]);
}
points[i][dimensions - 1] = r * sinMult;
}
}
void simplexInSphericalCoordinates(int pointsS, int dimensionsS, int d, double[][] angles) {
if (dimensionsS == angles[pointsS].length) {
angles[pointsS][dimensionsS - 1] += 2* Math.PI / 3;
return;
}
angles[pointsS][dimensionsS] = 0;
for (int i = pointsS + 1; i < angles.length; i++) {
angles[i][dimensionsS] = Math.acos(-1f / d);
}
simplexInSphericalCoordinates(pointsS + 1, dimensionsS + 1, d - 1, angles);
}
Я правильно понял, что этот метод выводит все треугольники объекта, в том числе и те, которые в 4-мерном пространстве не видны? И учитываются ли как-нибудь четырехмерные перекрытия одних симплексов другими?
Нет, не учитывается. Они все прозрачные). И в самом 4-мерном пространстве, все треугольники видны. Отсечения — беда проекции.
Задние треугольники отсекать просто. Это граница между невидимыми гранями, а видимость граней определяется по 4D-нормалям. Границы между видимыми и невидимыми показывать, очевидно, надо: для четырехмерного наблюдателя они образуют видимый контур. А вот в каком случае показывать границы между видимыми гранями, я для себя еще не решил. Пока не показываю их вообще, но, возможно, имеет смысл давать им прозрачность в зависимости от угла между гранями (чтобы на изображении гиперсферы их было почти не видно, а на гиперкубе — выглядели довольно четко).
А чтобы справиться с сортировкой полупрозрачных треугольников, просто режу их на маленькие кусочки (размером 3-5 пикселей), и только потом сортирую. Неуклюже, но крутить объекты можно. Надо будет изучить честный алгоритм поиска пересечений.
А чтобы справиться с сортировкой полупрозрачных треугольников, просто режу их на маленькие кусочки (размером 3-5 пикселей), и только потом сортирую. Неуклюже, но крутить объекты можно. Надо будет изучить честный алгоритм поиска пересечений.
Ну и, конечно, 4D-перекрытия — кошмарная задача. Она приводит к вычислениям пересечений и дополнений 3D-тел со всеми их внутренними «пленками»-ребрами… Пока браться за нее страшно.
4D-перекрытия — ненужны. Если отсекать все в 4D, а потом проецировать на 3D — будет куча визуальных разрывов. Зачем так жить?
Нет, здесь вариант — проектировать 4D на 3D без прозрачности, как есть («как видит 4-мерец»), при этом возникнут перекрытия — ближние (большие) тетраэдры и прочие проекции симплексов «загородят» (с нашей точки зрения — поглотят) задние (маленькие). Получится 3D-сцена, в которой кусочки маленьких тел торчат из граней больших. Чтобы мы могли ее увидеть, ее можно спроектировать в 2D в каком-нибудь направлении («сбоку»), на этот раз в полупрозрачном режиме. Но это хорошо для для сложных сцен. Если работать с красивым симметричным объектом, половина красоты может пропасть.3D- Губка Менгера красивее выглядит в полупрозрачном режиме? Или все-таки нет? ;)
Всё-таки нет. Я понял о чем речь. Но смею заверить, что если оставить лишь те части, которые видит 4-мерец, и потом всё что осталось проецироватьна 3D — получится разорванный на куски объект. Перспективная проекция не сохраняет параллельность, а без неё скучно жить. Ну и, соответственно, проекция на 2D с прозрачностью укажет нам на наличие разрывов.
Я границы рисовал четко, без прозрачностей. имхо, все правильно сделал.
Если все грани одним цветом, и нет сложных алгоритмов обработки света — можно просто инкрементить интенсивность пикселей, без сортировок всяких.
Если все грани одним цветом, и нет сложных алгоритмов обработки света — можно просто инкрементить интенсивность пикселей, без сортировок всяких.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Симплекс Серпинского