Введение в компьютерные методы метрико-топологических построений.

Современная вычислительная среда.
Глобальная модель циркуляции «атмосфера-океан»(МITcgm)-107-109 узлов(кубов).
Обтекание «Аэробуса»-107 тетраэдров.
Биотомограф-1000х1000х1000(109) вокселов.
Фармацевтика- триангуляция молекулярной поверхности-107.
Перколяционные задачи- решетка 109.
Архитектура и строительство -минимальные поверхности.
Научно-техническая визуализация -107-108 треугольников.

Геометрико - топологические особенности.
Меры по сохранению устойчивости решения(число и геометрия тетраэдров).
Проведение оперативных преобразований среды.(кластеризация и разбиение для распараллеливания вычислений).
Сохранение при преобразованиях топологических инвариантов и заданных геометрических отношений(тел).

Digital geometry and topology
Discrete differential geometry
США ( MIT, Caltech, Stanford)
Франция(INRIA)
Германия (Un.Gumbold)
Швеция (Un.Upsala)
Венгрия (Un.Seged)
Нов.Зеландия (Un.Oakland)
Япония (Un.Chiba)

Комбинаторная топология.
Конечный элемент-симплекс.
Комплекс –множество правильно расположенных симплексов.
Звездный полиэдр-окрестность.
Преобразование комплексов -сумма допустимых преобразований звездных полиэдров.

Целые точки и простые ребра.
Симплексы с вершинами в целых точках и простыми ребрами (не имеющими внутренних целых точек).
Модельные множества (Zn, Up), n-размерность пространства, p-норма простых ребер(p=max IxiI;i=1-n).
Основные построения для n=3,4,5,6 ; p=1;

Основная последовательность базисных построений.
Построение однородных звездчатых полиэдров (стереоэдров) на простых симплексах.
Покрытие такими полиэдрами всего пространства(нормальное,правильное разбиение).
Определение симплициальных комплексов.
Аналоги гомотопных преобразований на комплексах-преобразования на граничных зв.полиэдрах (гомотопные волны).

(Z2, U1) и все 6 типов 2d зв.полиэдров

Перестройки разбиения - выделение параллелограммов и замена диагоналей.

Двоичный код-инвариант при перестройках
1-го типа (диагональ-диагональ)

Классификация типов зв. полиэдров.
1.Транслируемые.
2.Конгруэнтные.
3.Парнотранслируемые.

Перечисление всех неконгруэнтных триангуляций куба.
Любая триангуляция на вершинах куба порождает диагональное разбиение граней куба.
Каждому разбиению соответствует вектор степеней вершин (инцидентных диагоналей).
Разные векторы-неконгруэнтные триангуляции.
v1-1,v2-1,v3-2,v4-2,v5-3,v6-1, v7-0,v8-2;
(1,3,3,1)

Диофантовы уравнения.
i-число диагоналей сходящихся к вершине.
xi-число вершин с i сходящимися диагоналями.
Σ xi =8; i=0-3;
Σ i xi=12; i=0-3;
Решения: (2,2,2,2);(0,6,0,2); (1,3,3,1); (2,0,6,0);(4,0,4,0);(0,4,4,0);

Все типы неконгруэнтных триангуляций куба.
(0,6,0,2) (2,0,6,0) (1,3,3,1) (2,2,2,2) (4,0,0,4)

Решение (0,4,4,0) не соответствует никакой триангуляции.
Ни при какой диагонали внутри куба невозможно правильное разбиение на пирамиды.

Все 3d звездчатые полиэдры (4 типа симплексов) на (Z3,V1).

Разбиение кубов проекциями-транслируемая полиэдризация R3.
Разбиение единичного куба на 6 тетраэдров-симплексов.

Ребра и грани вокруг (0,0,0)
Трансляция построений во все кубы R3.
Звездный полиэдр для (0,0,0)

Cтруктура полиэдра.
24 симпплекса внутри транслируемого звездного полиэдра.
Объем полиэдра V=24x1/6=4.

Транслируемый 3d
звездчатый полиэдр MSP.
Кубододекаэдр-14,36,24.
Вершин-15 (1+14)
Ребер- 50(14+36)
Граней-48(24+24)
3d cимплексов-24
Объем=4
Строго выпуклый (по Малеру)

Дуальный полиэдр.

Построение транслируемых nd-полиэдров как отображение Rn на подпространства.

Транслируемый 4d зв. полиэдр.
Два полярных 4d куба с одной общей вершиной и доп. ребрами.

Структура n-куба.
f(In)=(f0,f1,f2,…fn-1,fn) – вектор граней.
f0-число вершин;
f1-число ребер;
f2-число квадратов;
f3-число кубов;…
fn-In;
fk=C(n,k)2n-k;
f(I4)=(16,32,24,8,1);

Характеристика Эйлера-Пуанкаре
Формула Эйлера:В-Р+Г=2
Топологический инвариант
χ=f0-f1+f2-f3+…+(-1)n-1fn-1;

Треугольник и пирамида Паскаля.
Треугольник C(x,y)=C(x-1,y)+C(x,y-1);C(0,0)=1;
Пирамида V(x,y,z)=V(x-1,y,z)+V(x,y-1,z)+V(x,y,z-1); V(0,0,0)=1;

Триномиальные коэффициенты.
(a+b+c)n
V(n,k,l)albkcn-k-l
l=x;k=y;n=x+y+z;
V(n,k,l)= n!/l!k!(n-k-l)!
Σ V(n,k,l)=C(n,k)2n-k; l=1-(n-k);
ΣV(n,k,l)=fk;
(16,32,24,8)

Кодирование k-граней.
Каждой k-грани соответствует кратчайший путь по решетке в вершину слоя n c y=k;
Каждый путь кодируется троичным кодом. {0,1,2}

Кодировка I4
0000 в 0001 в 0002 р 0010 в 0011 в 0012 р
0020 р 0021 р 0022 к 0100 в 0101 в 0102 р
0200 р 0201 р 0202 к 0210 р 0211 р 0212 к
0220 к … 2220 г 2221 г 2222 I4
Вершины- традиционная кодировка.
Ребра- коды с одной «двойкой»
К-грани- с к «двойками»

Геометрическая интерпретация
Код 2120
Ребра 0020 и 2000 -> грань 2020
Грань 2020 транслируется из (0000) в (0100)

Генерация примитивной триангуляции (путевые симплексы)
Симметрическая группа подстановок Sn.
si € Sn
1 2 3 … n
ai1 ai2 ai3… ain
eai1, eai1+eai2, eai1+eai2+eai3,… -последовательные вершины симплекса
Рис. -> 1 2 4 3

Примитивная триангуляция I4.
24 cимплекса могут быть закодированы 5-ью двоичными разрядами.

3d звезда-полиэдр и ее симплексы.
Вклад кубов (по числу симплексов) из 8 октантов, содержащих (000).

Симплициальная структура транслируемого nd звезды-полиэдра
W(k)-число симплексов с вершиной r=k
S(k)-число n-кубов с вершиной r=k в (00…0)
W(k)=k!(n-k)!;
S(k)=C(n,k);
S=Σ W(k)S(k)= (n+1)!;
V(P)=n+1;

Кодирование симплексов .
1234,1243,1324,1342,1423,1432,
0 1 2 3 4 5
2134,2143,2314,2341,2413,2431,
5 7 8 9 10 11
3124,3142,3214,3241,3412,3421,
12 13 14 15 16 17
4123,4132,4213,4231,4312,4321
18 19 20 21 22 23
a0 n!+a1(n-1)!+…+an-2 2!+an-1 1!=№; ak
21=(3,1,1) -> 4231:3+1=4, 1+1=2-ая из ост. ->2, 1+1=2-ая из ост.->3; и ост.1

Транслируемые звездчатые
nd-полиэдры.
2d 3d 4d 5d 6d 7d
В 6 14 30 62 126 254
S 6 24 120 720 5040 40320
V 3 4 5 6 7 8

Гомотопные расширения и сжатия комплексов-сумма преобразований MSP на границе комплексов.
Топологический контроль-проверка связности в MSP до и после преобразования.
Для общего 3d случая объем вычислений Q~ N3xVxExN (для N =103 Q= 1014 память M= 100Гb )
Для топол. процессора Q=1011 M=1Гb

Допустимые преобразования без склеек и разрывов.
Расширение «желтого» без склеек и разрывов «желтого» и «красного» зависит только от ситуации в «выколотом» зв.полиэдре.

Анализ связности множеств
М1 и М2 на границе полиэдра.
М1 на границе несвязно.
М2 на границе связно.
Если переход (000) в М1, то М1 и М2 связны- изменения в связностях недопустимы!

Три 2d комплекса

Расширение черного.

Расширение черного.

Сжатие черного.

Приближение к евклидовой метрике на Zn.
Метрика на ребрах звездчатых полиэдров (многогранная метрика) далека от евклидовой.
Расширить множество простых ребер (увеличить норму) в зависимости от заданной погрешности приближения.

Линейные преобразования на решетках.
Унимодулярные матрицы- модуль определителя =1.
Линейные унимодулярные преобразования сохраняют площадь (объем) фигур(тел).

Составление веера.
Стыковку секторов веера обеспечивают «соседние» унимодулярные матрицы.

Несократимые дроби и простые ребра (веер Фарея).
В каждом секторе целые точки образуют решетки с базисами {(0,1),(1,1)}; {(1,1),(1,0)}.
С увеличением порядка Ф(к) длина по ребрам решеток приближается к евклидовой.
Δ=L-Le/Le=~ φ2/4+o(φ4);

Увеличение порядка Ф(к).

Увеличение порядка Ф(к).

Отображения Z2(0,π/2) на Z2(i,i+1)

Веер Фарея 3-го порядка.

Неравномерность уменьшения углов в секторах веера.
Для веера Ф(3):
Сектор ((0/1)(1/3))~1/3.
Cектор ((1/3)(1/2))~1/6.
Коррекция процедуры генерации несократимых дробей-наибольшие углы разбивать чаще.

Приближение к евклидовой метрике.
Для сектора веера с базисом bi,bj и углом φ:
L=λ1ρ(bi)+λ2ρ(bj);на решетке,
Le-евклидова длина между этими точками.
Максимальная отн. погрешность в секторе:
Δm(φ)=L-Le/Le=φ2/4+O(φ4/16);

Для построения веера в Rn.
Множество целочисленных квадратных матриц:{Ai}.
Ai =1 сохраняет объемы.
Бесконечная группа с Е-ед.диагон.м.
Аналог несократимых дробей- простые целые n-мерные вектора (компоненты вектора, как целые числа не имеют общего делителя >1).

Построение 3d веера для заданной Δ-итерационная процедура на1/48 сферы.
Вырезанному сектору соответствует матрица Ао из простых векторов.
IAoI=1;
Замена строки в матрице суммой строки с другой не меняет основных свойств матрицы.

Веерная триангуляция.
Определение грани(ребра) с макс. углом и разбиение ребра сложением векторов (строк матрицы).
Продолжение процедуры, пока макс. угол <φ0(Δ).
Затем зеркальные отображения на всю сферу.
000

Nd-случай.
Для nd случая триангулируется (а затем и хранится в памяти) 1/2n n! – часть nd сферы.
Вся nd сфера может покрываться зеркальными отображениями.

Проекция 3d веера на сферу
(для Δ=L-Le/Le=0,001)
После зеркальных отображений 1/48 части на всю сферу.
Веер содержит 7610 ребер.

Сравнение по числу ребер
3d веера Фарея и решеточного расслоения .
K 2 3 4 5 6 … 19
Δ(%) 4,85 2,41 1,44 1,17 0,76 … 0,1
N(k) 98 290 578 1154 1730 … 50114 (~k3)
N* 74 194 266 530 722 … 7610 (~k2)

Основные операции прототипа топологического процессора.
Задание решетки и метода полиэдризации.
Задание границ и преград.
Задание комплексов. Индексные массивы(1:128)
Определение связности комплексов и характеристики Эйлера-Пуанкаре.
Задание преобразований и их режимов(целевых функций).
Проведение преобразований. Анализ MSP-один такт!
Выделение триангулированной границы.
Генерация решеточного веера по заданной погрешности.
Прогон метрической волны от множества-источника и построение эквидистантного графа.
Операции над эквидистантными графами.
Все операции эмулированы и верифицированы на решетках до 200х200х200.
Видеопоказ на http://www.vizcom.srcc.msu.ru

Построение «сферы» как 2d многообразия.
Заданы центр «сферы» и преграды(2пластины).
Построить «сферу» минимального радиуса.
Условие: преграды внутри «сферы», Δ = 0,01;
Cхема решения-генерация веера для Δ=0,01;метрическая волна и эквидистантный граф;сжатие комплекса до преград; выделение трианг. границы.
(750 000 симплексов)
Т(2Ггц,512Mb)=2мин.

Ближайшие задачи.
Перенос комплекса на кластер НИВЦ МГУ с целями:
1.Решение задач на решетках:3d-20003,4d-5004,5d-2005,6d-506.
2.Использование распараллеливания, потенциально близкого к клеточным автоматам.
3.Полиэкранная визуализация сечений многомерных комплексов.

Основные ссылки.
Л.С.Понтрягин. Основы комбинаторной топологии.
П.С.Александров. Комбинаторная топология.
Б.Н.Делоне. Теория стереоэдров.
К.Чандрасекхаран. Введение в аналитическую теорию чисел.
Д.Касселс. Введение в геометрию чисел.
И.М.Гельфанд. Лекции по линейной алгебре.
В.А.Ковалевский. Конечная топология.
Ж.Бертран, М.Купри. Гомотопные преобразования.
И.Кенмочи, А.Имийя. Глобальная полиэдризация.
Г.Г.Рябов. Метрические и топологические волны на решетках.
О.Д.Авраамова. Язык VRML.