Предисловие | 12
|
Основные обозначения, принятые в книге | 14
|
Часть 1. Основы дифференциальной геометрии | 15
|
Глава 1.1. Введение в дифференциальную геометрию | 16
|
1.1.1. Криволинейные системы координат. Простейшие примеры | 16
|
1.1.1.1. Мотивировка | 16
|
1.1.1.2. Декартовы и криволинейные координаты | 17
|
1.1.1.3. Простейшие примеры криволинейных систем координат | 22
|
1.1.2. Длина кривой | 24
|
1.1.2.1. Длина кривой в евклидовых координатах | 24
|
1.1.2.2. Длина кривой в криволинейных координатах | 26
|
1.1.2.3. Понятие римановой метрики в области евклидова пространства | 30
|
1.1.2.4. Индефинитные (знаконеопределенные) метрики | 32
|
1.1.3. Геометрия на плоскости и на сфере | 34
|
1.1.4. Псевдосфера и геометрия Лобачевского | 40
|
Глава 1.2. Кривые и поверхности | 54
|
1.2.1. Теория кривых. Формулы Френе | 54
|
1.2.1.1. Теория кривых на плоскости. Кривизна | 54
|
1.2.1.2. Теория пространственных кривых. Кривизна и кручение | 59
|
1.2.2. Поверхности. Первая и вторая квадратичные формы | 64
|
1.2.2.1. Определение поверхностей | 64
|
1.2.2.2. Первая квадратичная форма | 66
|
1.2.2.3. Вторая квадратичная форма | 69
|
1.2.2.4. Локальная теория гладких кривых на поверхности. Теорема Менье. Формула Эйлера | 73
|
1.2.2.5. Гауссова и средняя кривизны в точке на поверхности | 78
|
Глава 1.3. Общая топология | 88
|
1.3.1. Определения и простейшие свойства метрических и топологических пространств | 88
|
1.3.1.1. Метрические пространства | 88
|
1.3.1.2. Топологические пространства | 90
|
1.3.1.3. Непрерывные отображения | 91
|
1.3.1.4. Гомотопия и гомотопическая эквивалентность | 94
|
1.3.1.5. Фактортопологии | 95
|
1.3.2. Связность. Аксиомы отделимости | 97
|
1.3.3. Компактные топологические пространства | 101
|
1.3.4. Функциональная отделимость. Разбиение единицы | 104
|
1.3.4.1. Функциональная отделимость | 104
|
1.3.4.2. Разбиение единицы | 107
|
Глава 1.4. Гладкие многообразия (обобщение поверхностей) | 109
|
1.4.1. Понятие многообразия | 111
|
1.4.1.1. Основные определения | 111
|
1.4.1.2. Функции склейки. Определение гладкого многообразия | 114
|
1.4.1.3. Гладкие отображения многообразий. Диффеоморфизмы | 118
|
1.4.2. Задание многообразий уравнениями в Rn | 120
|
1.4.3. Касательные векторы и касательное пространство | 125
|
1.4.3.1. Простейшие примеры | 126
|
1.4.3.2. Общее определение касательного вектора | 128
|
1.4.3.3. Касательное пространство TP0(M) | 129
|
1.4.3.4. Производная функции по направлению | 130
|
1.4.4. Подмногообразия | 134
|
1.4.4.1. Дифференциал гладкого отображения | 134
|
1.4.4.2. Локальные свойства отображений и дифференциал | 137
|
1.4.4.3. Вложение многообразий в евклидово пространство | 139
|
1.4.4.4. Римановы метрики на многообразии | 140
|
1.4.5. Классификация двумерных поверхностей | 143
|
1.4.5.1. Многообразия с краем | 143
|
1.4.5.2. Ориентируемые многообразия | 145
|
1.4.5.3. Классификация двумерных гладких компактных связных многообразий без края | 147
|
1.4.6. Изометрии | 159
|
1.4.7. Двумерные многообразия как римановы поверхности алгебраических функций | 161
|
Часть 2. Компьютерная геометрия | 171
|
Глава 2.1. Гладкие кривые с вычислительной точки зрения | 172
|
2.1.1. Приблизительная локальная форма кривой, определяемая кривизной и кручением | 172
|
2.1.2. Формулы для кривизны и кручения кривой относительно произвольного параметра в координатах, задаваемых репером Френе | 174
|
2.1.3. Восстановление пространственной кривой по ее проекциям на координатные плоскости | 175
|
2.1.4. Приведение параметрического уравнения кривой к неявному виду | 177
|
Глава 2.2. Сплайны и кривые Безье | 180
|
2.2.1. Сплайны | 180
|
2.2.1.1. Примеры сплайнов | 180
|
2.2.1.2. Построение сплайнов Эрмита | 181
|
2.2.1.3. Псевдоупругие сплайны Эрмита | 183
|
2.2.1.4. Случай, когда на концах кривой заданы направления касательных векторов | 186
|
2.2.1.5. Кубические сплайны. Построение кубического сплайна | 187
|
2.2.1.6. Сплайн Лагранжа | 189
|
2.2.1.7. Сплайн Ньютона | 190
|
2.2.2. Кривые Безье | 191
|
2.2.2.1. Алгоритм де Кастелье | 196
|
2.2.2.2. Операторная форма кривой Безье | 196
|
2.2.2.3. Годографы кривых Безье | 198
|
2.2.2.4. Деление кривой Безье на две кривые Безье того же порядка в отношении t*:(1-t*) | 201
|
2.2.2.5. Условия сохранения гладкости сопряжения при делении кривой Безье | 203
|
2.2.2.6. Увеличение числа опорных точек без изменения формы кривой Безье | 203
|
Глава 2.3. Поверхности Безье | 205
|
2.3.1. Геометрический смысл поверхности Безье | 205
|
2.3.2. Формулы вычисления координат точек на поверхности Безье | 206
|
2.3.3. Деление поверхности Безье | 207
|
2.3.4. Геометрические свойства поверхности Безье в угловой точке | 207
|
2.3.5. Измельчение сетки при сохранении поверхности Безье | 208
|
Глава 2.4. Проективные (рациональные) кривые Безье | 210
|
2.4.1. Операция рационального деления отрезка | 210
|
2.4.2. Свойства рациональных кривых Безье | 213
|
2.4.3. Деление рациональной кривой Безье | 213
|
2.4.4. Увеличение числа опорных точек рациональной кривой Безье | 216
|
2.4.5. Производные на концах рациональной кривой Безье | 217
|
2.4.6. Рациональные поверхности Безье | 219
|
2.4.7. Представление кривых второго порядка рациональными кривыми Безье порядка 2 | 219
|
Глава 2.5. B-сплайны (бета-сплайны), B-кривые (бета-кривые) и B-поверхности (бета-поверхности) | 223
|
2.5.1. Постановка задачи | 223
|
2.5.2. Разделенные разности | 224
|
2.5.3. Свойства разделенных разностей | 229
|
2.5.4. Усеченная степенная функция | 230
|
2.5.5. Рекуррентные соотношения для B-сплайнов | 234
|
2.5.6. Алгоритм вычисления радиус-вектора B-кривой | 237
|
2.5.7. Алгоритм вычисления производных B-кривой при условии, что t1=…=tm, tn+1=…=tn+m | 242
|
2.5.8. Алгоритм Де Бура вычисления радиус-вектора B-кривой | 245
|
2.5.9. Интерполяция с помощью B-кривых | 249
|
2.5.10. Представление кубического сплайна в виде B-кривой | 249
|
2.5.11. B-поверхности | 252
|
Глава 2.6. Другие способы представления поверхностей в компьютерной геометрии | 254
|
2.6.1. Линейчатые поверхности | 254
|
2.6.2. Секториальные поверхности | 254
|
2.6.3. Поверхности Кунса | 255
|
2.6.3.1. Линейные поверхности Кунса | 255
|
2.6.3.2. Матричный вид уравнения поверхности Кунса | 256
|
2.6.3.3. Обобщенные поверхности Кунса | 257
|
2.6.4. Поверхности, построенные по остову из кривых | 258
|
2.6.4.1. Поверхности Эрмита | 259
|
2.6.4.2. Применение поверхностей Эрмита: поверхность перехода | 260
|
2.6.4.3. Поверхности Лагранжа | 261
|
2.6.4.4. Поверхности Гордона | 262
|
2.6.4.5. Поверхности, затягивающие сетку кривых заплатами Кунса | 263
|
2.6.4.6. Поверхности тензорного произведения | 264
|
2.6.5. Поверхности с треугольной параметрической областью | 266
|
2.6.5.1. Барицентрические координаты | 266
|
2.6.5.2. Билинейная треугольная поверхность | 267
|
2.6.5.3. Треугольная поверхность на трех кривых | 267
|
Глава 2.7. Компьютерная геометрия проективно преобразованных изображений (Г. В. Носовский, Е. С. Скрипка, А. А. Толченников) | 269
|
2.7.1. Введение | 269
|
2.7.2. Основные понятия проективной геометрии | 270
|
2.7.3. Метод распознавания сопряженных точек по разнесениям связанных признаков (Г. В. Носовский) | 272
|
2.7.4. Устойчивость проективного преобразования к возмущениям конфигурации сопряженных точек (Г. В. Носовский, Е. С. Скрипка) | 279
|
2.7.5. Вычисление матрицы проективного преобразования и оценка ее устойчивости (Е. С. Скрипка) | 283
|
2.7.5.1. Прямой алгоритм вычисления проективного преобразования | 283
|
2.7.5.2. Оценка погрешности матрицы проективного преобразования при возмущенных начальных данных | 285
|
2.7.6. Математическая модель камеры и пары камер | 288
|
2.7.6.1. Определение финитной камеры | 288
|
2.7.6.2. Восстановление характеристик финитной камеры по ее матрице | 291
|
2.7.6.3. Геометрия двух камер. Фундаментальная матрица | 292
|
2.7.6.4. Свойства фундаментальной матрицы | 295
|
2.7.6.5. Восстановление пары камер по фундаментальной матрице | 295
|
2.7.6.6. Канонические пары камер, порожденные фундаментальной матрицей | 298
|
2.7.7. ПЛА и НЛА алгоритмы приближенного вычисления проективного преобразования. Оценка их устойчивости (Г. В. Носовский, А. А. Толченников) | 300
|
2.7.7.1. Вычисление проективного преобразования по точно заданным сопряженным точкам | 300
|
2.7.7.2. Простой линейный алгоритм (ПЛА) вычисления проективного преобразования по приближенно заданным сопряженным точкам | 302
|
2.7.7.3. Вычисление вектора, соответствующего минимальному собственному значению матрицы | 304
|
2.7.7.4. Неинвариантность ПЛА относительно движений плоскости | 305
|
2.7.7.5. Нормализованный линейный алгоритм (НЛА) | 309
|
2.7.7.6. Оценка ошибки для алгоритмов ПЛА и НЛА | 311
|
Часть 3. Геометрическое моделирование | 319
|
Глава 3.1. Геометрические модели | 320
|
3.1.1. Оболочки и тела | 320
|
3.1.1.1. Оболочка | 320
|
3.1.1.2. Оболочки для геометрического моделирования | 322
|
3.1.1.3. Тело | 324
|
3.1.2. Простейшие тела | 324
|
3.1.2.1. Прямоугольная призма | 325
|
3.1.2.2. Цилиндрическое тело | 326
|
3.1.2.3. Коническое тело | 327
|
3.1.2.4. Сферическое тело | 328
|
3.1.2.5. Тело в форме тора | 329
|
3.1.3. Тела движения | 330
|
3.1.3.1. Тело выдавливания | 330
|
3.1.3.2. Тело вращения | 331
|
3.1.3.3. Тело сдвига | 332
|
3.1.3.4. Кинематическое тело | 333
|
3.1.3.5. Матричная функция кинематического тела | 333
|
3.1.3.6. Циклы граней тел движения | 335
|
3.1.4. Тело, построенное по сечениям | 336
|
3.1.5. Тело, построенное по поверхности | 338
|
3.1.6. Операции над телами | 340
|
3.1.7. Булевы операции над телами | 341
|
3.1.7.1. Объединение тел | 342
|
3.1.7.2. Пересечение тел | 347
|
3.1.7.3. Вычитание тел | 348
|
3.1.7.4. Пересекающиеся ребра | 348
|
3.1.7.5. Совпадающие ребра | 349
|
3.1.7.6. Правила для ребер пересечения | 349
|
3.1.7.7. Принадлежность точки пространству внутри тела | 351
|
3.1.7.8. Перекрывающиеся грани | 351
|
3.1.7.9. Тела с несколькими оболочками | 352
|
3.1.8. Разрезанное тело | 353
|
3.1.9. Симметричное тело | 354
|
3.1.10. Тело с достраиваемыми элементами | 357
|
3.1.11. Эквидистантное тело | 359
|
3.1.12. Тонкостенное тело | 363
|
3.1.13. Обработка ребер тела | 366
|
3.1.13.1. Скругление ребер | 366
|
3.1.13.2. Скругление сопряженных ребер | 368
|
3.1.13.3. Скругление вершин | 369
|
3.1.13.4. Скругление звезд | 369
|
3.1.13.5. Скругление с сохранением кромки | 370
|
3.1.13.6. Гладкое сопряжение | 371
|
3.1.13.7. Переменный радиус скругления | 371
|
3.1.13.8. Фаски ребер | 372
|
3.1.14. Геометрические ограничения | 372
|
3.1.14.1. Цель введения геометрических ограничений | 372
|
3.1.14.2. Формулировка задачи геометрических ограничений | 374
|
3.1.14.3. Консервативный метод | 375
|
3.1.14.4. Метод дополнительных ограничений | 376
|
3.1.14.5. Метод кластерной декомпозиции | 377
|
3.1.15. Геометрическая модель | 378
|
Глава 3.2. Построения на кривых и поверхностях | 381
|
3.2.1. Построения в геометрических моделях | 381
|
3.2.1.1. Движение по кривой | 382
|
3.2.1.2. Движение по поверхности | 383
|
3.2.2. Проекция точки на кривую | 384
|
3.2.2.1. Проекция точки на прямую линию | 384
|
3.2.2.2. Частные случаи | 385
|
3.2.2.3. Общий случай | 385
|
3.2.2.4. Принадлежность точки двумерной области | 386
|
3.2.3. Проекция точки на поверхность | 387
|
3.2.3.1. Проекция точки на плоскость | 387
|
3.2.3.2. Частные случаи | 388
|
3.2.3.3. Общий случай | 388
|
3.2.3.4. Положение точки относительно оболочки | 389
|
3.2.4. Точки пересечения кривой и поверхности | 390
|
3.2.4.1. Пересечение прямой и плоскости | 390
|
3.2.4.2. Общий случай | 391
|
3.2.5. Точки пересечения кривых | 392
|
3.2.5.1. Пересечение прямых линий | 393
|
3.2.5.2. Пересечение отрезков | 394
|
3.2.5.3. Частные случаи | 394
|
3.2.5.4. Общий случай пересечения кривых в двумерном пространстве | 394
|
3.2.5.5. Пересечение пространственных кривых | 395
|
3.2.6. Точки пересечения трех поверхностей | 396
|
3.2.6.1. Пересечение трех плоскостей | 396
|
3.2.6.2. Пересечение трех поверхностей | 397
|
3.2.7. Линии пересечения поверхностей | 397
|
3.2.7.1. Пересечение плоскостей | 397
|
3.2.7.2. Частные случаи пересечения поверхностей | 399
|
3.2.7.3. Общий случай пересечения поверхностей | 400
|
3.2.7.4. Алгоритм построения линий пересечения | 402
|
3.2.7.5. Радиус-вектор линии пересечения поверхностей | 405
|
3.2.8. Поверхности сопряжения | 407
|
3.2.8.1. Поверхности скругления | 407
|
3.2.8.2. Переменный радиус скругления | 409
|
3.2.8.3. Поверхность скругления с сохранением кромки | 411
|
3.2.8.4. Поверхность скругления с заданной хордой | 412
|
3.2.8.5. Гладкое сопряжение | 413
|
3.2.8.6. Поверхность фаски | 414
|
3.2.8.7. Фаска с переменными катетами | 415
|
3.2.9. Погрешность геометрических построений | 415
|
Глава 3.3. Геометрические вычисления | 417
|
3.3.1. Моменты инерции плоского сечения | 417
|
3.3.1.1. Площадь и центр масс плоского сечения | 417
|
3.3.1.2. Моменты инерции плоского сечения | 418
|
3.3.1.3. Вычисление моментов инерции плоского сечения | 419
|
3.3.2. Площадь поверхности, объем и центр масс тела | 422
|
3.3.2.1. Площадь поверхности тела | 422
|
3.3.2.2. Объем тела | 422
|
3.3.2.3. Статические моменты тела | 423
|
3.3.2.4. Центр масс тела | 424
|
3.3.3. Моменты инерции тела | 425
|
3.3.3.1. Тензор инерции | 426
|
3.3.3.2. Собственные значения матрицы инерции | 427
|
3.3.3.3. Главные оси инерции | 428
|
3.3.3.4. Эллипсоид инерции | 431
|
3.3.3.5. Тензорное поле | 432
|
3.3.3.6. Вычисление моментов инерции тела | 433
|
3.3.4. Численное интегрирование по поверхности | 436
|
3.3.4.1. Разбиение поверхности | 436
|
3.3.4.2. Построение четырехугольных областей | 436
|
3.3.4.3. Построение треугольных областей | 437
|
3.3.4.4. Кубатурная формула для четырехугольной области | 439
|
3.3.4.5. Кубатурная формула для треугольной области | 441
|
Глава 3.4. Методы компьютерной графики | 445
|
3.4.1. Полигоны кривых и поверхностей | 445
|
3.4.1.1. Полигоны | 445
|
3.4.1.2. Сетки полигонов | 448
|
3.4.2. Силуэтные линии | 449
|
3.4.3. Определение видимой части моделей | 452
|
3.4.4. Триангуляция | 455
|
3.4.4.1. Триангуляция плоскости | 455
|
3.4.4.2. Триангуляция Делоне | 456
|
3.4.4.3. Итеративная триангуляция Делоне | 459
|
3.4.4.4. Триангуляция Делоне ограниченной области | 460
|
3.4.4.5. Триангуляция поверхностей | 462
|
3.4.4.6. Триангуляция оболочек | 467
|
3.4.5. Моделирование оптических свойств | 468
|
3.4.5.1. Свет | 468
|
3.4.5.2. Модель оптических свойств | 468
|
3.4.5.3. Диффузное отражение | 469
|
3.4.5.4. Зеркальное отражение | 469
|
3.4.5.5. Рассеяние света | 470
|
3.4.5.6. Прозрачность | 470
|
3.4.5.7. Наблюдение света | 471
|
3.4.5.8. Описание цвета | 473
|
3.4.6. Построение реалистических изображений | 474
|
3.4.6.1. Переход в систему координат проекционной плоскости | 475
|
3.4.6.2. Определение яркости и цвета точки изображения | 476
|
3.4.6.3. Методы закраски | 476
|
3.4.6.4. Детализация поверхностей | 478
|
3.4.6.5. Тени | 479
|
3.4.6.6. Прозрачность | 479
|
Литература | 481
|
Предметный указатель | 484
|
Настоящая книга является учебником повышенного уровня по компьютерной геометрии для студентов высших учебных заведений. Книга написана коллективом авторов из Московского государственного университета имени М. В. Ломоносова (кафедра дифференциальной геометрии и приложений механико-математического факультета) и из математического отдела российской фирмы АСКОН, разрабатывающей компьютерную систему автоматизированного проектирования КОМПАС-3D.
Компьютерная геометрия — молодая и бурно развивающая область прикладной математики. Ее возникновение было вызвано, в первую очередь, изобретением и широким внедрением в нашу жизнь персональных компьютеров, неотъемлемым элементом которых является плоский экран, через который и осуществляется обратная связь с пользователем.
С изобретением персональных компьютеров впервые возникла доступная возможность работать с плоским электронным изображением, управляя им «напрямую» (в режиме реального времени) с помощью достаточно мощного вычислительного устройства. Это, в свою очередь, вызвало революцию (или, по крайней мере, существенные изменения) в тех областях человеческих знаний, которые были так или иначе связаны с геометрией и с наглядным (обычно — плоским) представлением пространственных объектов. Например — в черчении, проектировании, конструировании, различного рода моделировании (как техническом, так и художественном), медицинской диагностике, оформительском деле и т. п. В наше время применение персональных компьютеров во всех этих областях никого не удивит — хотя еще 40 лет назад во многих из них работали вообще без каких-либо вычислительных устройств. При этом, конечный пользователь далеко не всегда отдает себе отчет в том, что в основе тех программ, которые позволяют ему работать с экранным изображением, лежит достаточно сложная и современная математика. В первую очередь это — дифференциальная геометрия. Подчеркнем, что именно дифференциальная геометрия является главной основой и источником многих важных идей для современной компьютерной геометрии.
Книга разделена на три части. В первой части излагаются необходимые сведения из дифференциальной геометрии и топологии. Представлены только те разделы дифференциальной геометрии, которые действительно важны или полезны для специалистов, работающих в прикладной компьютерной геометрии (как с точки зрения результатов, так и с точки зрения идей и понятий). Изложение здесь является полным, замкнутым и математически строгим. Все используемые понятия вводятся в тексте, леммы и теоремы снабжаются полными доказательствами. В то же время, подача материала максимально упрощена и доступна для читателей-нематематиков, имеющих техническое образование. Более легкому восприятию материала способствует большое количество рисунков, дополняющих и поясняющих основной текст. Данная часть написана А. Т. Фоменко. В ее редактировании принимали участии Г. В. Носовский и Д. П. Ильютко.
Вторая часть посвящена основным понятиям и определениям собственно компьютерной геометрии. Это — различные виды сплайнов, используемых в компьютерной графике, кривые и поверхности Безье, рациональные кривые и поверхности Безье, B-сплайны, B-кривые (NURBS curves в англоязычной терминологии) и B-поверхности, поверхности Кунса, поверхности Гордона и т. п. Эта часть книги также написана на математически строгом языке с полными доказательствами почти всех сформулированных утверждений. В последней главе второй части излагаются новые результаты, недавно полученные авторами и их учениками Е. С. Скрипкой и А. А. Толченниковым, и относящиеся к важной проблеме современной компьютерной геометрии — автоматической склейке проективно преобразованных изображений (multiple view geometry). Эта часть написана Г. В. Носовским и Д. П. Ильютко. Последняя глава второй части написана Г. В. Носовским, Е. С. Скрипкой и А. А. Толченниковым.
Третья часть посвящена геометрическому моделированию, в частности, математическому описанию конкретных алгоритмов, применяемых при разработке САПР. В ней описан состав, методы построения и применение математических моделей к геометрии реальных и воображаемых объектов, приведены методы компьютерной графики. Фундаментом геометрического моделирования являются дифференциальная геометрия и топология, рабочим материалом — различные кривые и поверхности.
В то же время геометрическое моделирование разрабатывает собственные методы. В основу изложения положен опыт разработки геометрического ядра системы КОМПАС-3D. Материал третьей части преподносится в максимально доступном виде и снабжен большим количеством рисунков. Третья часть написана Н. Н. Головановым. Более подробно с содержанием книги можно ознакомиться по оглавлению.
Н. Н. Голованов, Д. П. Ильютко.