Русский
Русский
English
Статистика
Реклама

Геометрия

Красивая теорема, которую Блез Паскаль доказал в 16 лет

24.05.2021 08:13:54 | Автор: admin

Блез Паскаль - один из основателей математического анализа, блестящий физик и философ. С ранних лет он проявлял недюжинные способности во всех областях науки и техники, за которые брался его пытливый ум. Например, в возрасте 8 лет Блез, даже не зная толком названий геометрических фигур (окружность он называл "колечком", а прямую - "палочкой"), доказал 32-ю теорему Евклида о сумме углов треугольника.

Неудивительно, что в 16-летнем возрасте юный гений стал доказывать уже свои теоремы. С одной из таких теорем я бы хотел Вас познакомить. Доказательство теоремы не тривиально (доказательство дял жаждущих), поэтому я просто хочу показать каждому красоту геометрии. Начнем с простого предварительного построения:

На рисунке выше изображена одна из классических теорем проективной геометрии - теорема Паппа, названная в честь Паппа Александрийского - математика позднего эллинизмаНа рисунке выше изображена одна из классических теорем проективной геометрии - теорема Паппа, названная в честь Паппа Александрийского - математика позднего эллинизма

Мы взяли две непараллельные прямые, отметили три пары точек (произвольных в известной степени), а затем соединили каждую точку с её противоположными собратьями. О чудо! Все три точки пересечения лежат на одной прямой! Паскаль пошел дальше своего предшественника: "А что, если попробовать сделать то же самое с окружностью?"

Да в целом получилось то же самое!Да в целом получилось то же самое!

А что, если пойти дальше? Ведь окружность - это частный случай эллипса, который, в свою очередь, является одним из трех главных типов т.н. конических сечений:

К коническим сечениям относятся: парабола, эллипс и гипербола + три вырожденных случая - точка, прямая и пара прямых. Именно такую форму принимает пересечение плоскости с поверхностью кругового конуса. Как Вы уже догадываетесь, для параболы результат оказался таким же:

Такого рода построения позволили сформулировать 16-летнему мальчику первую из теорем, названных его именем:

"Если шестиугольник вписан в коническое сечение, то точки пересечения трех пар противоположных сторон лежат на одной прямой".

Современники настолько были поражены теоремой Паскаля, что на латинице она известна как "Hexagrammum Misticum":

 Шестиугольник AECFBD вписан в эллипс. Прямая, проходящая через точки G,H,K называется прямой Паскаля. Шестиугольник AECFBD вписан в эллипс. Прямая, проходящая через точки G,H,K называется прямой Паскаля.

Информация об этой теореме вместе с более чем (!!!) 400 следствиями вошла в "Полный труд о конических сечениях", написанный Паскалем в 31 год. Восхищения этой уникальной рукописью уже после смерти гения не скрывал сам Готфрид Лейбниц, но, к сожалению, работа была утеряна племянником Паскаля и так и не была опубликована.

Хотя имеется множество вариантов доказательства теоремы Паскаля, историкам математики не известно, как она была доказана в первоисточнике, хотя многие и сходятся к использованию теоремы Менелая.

Подробнее..

Перевод Математически оптимальные рождественские печеньки

31.12.2020 10:15:49 | Автор: admin

Чрезвычайно оптимальная форма для печенья Мартина Лерша.

Однажды в декабре норвежский химик и страстный любитель готовки Мартин Лерш раскатал самодельное тесто и приступил к работе. Он поворачивал форму для печенья то в одном, то в другом направлении, создавая лоскутки в виде рождественских ёлок. Но основной целью Лерша была не просто горка вкусного праздничного печенья. Он хотел испечь математически идеальные фигуры.

В течение предыдущих нескольких лет Лерш пытался решить проблему, часто терзающую пекарей. Мы хотим наиболее оптимально использовать тесто, чтобы не приходилось собирать остатки и раскатывать их все заново. На самом деле это вопрос экономии времени, говорит Лерш.

Лерш выбрал приготовление рождественского печенья в качестве проекта для своего блога Khymos, в котором он исследует химию и научную сторону готовки. Он обнаружил, что стандартные формы праздничного печенья обычно не очень плотно соединяются друг с другом. Пухлые Санты, карамельные палочки и пряничные человечки обычно оставляют много лишнего теста. Поставив перед собой задачу создания красивой, но при этом оптимальной формы для печенья, Мартин спроектировал форму, способную выдавливать красивые ряды печенек с минимум остатков теста. Как оказалось, его рождественскую ёлку можно тесселировать.

Тесселяции, получившие известность благодаря голландскому гравёру и художнику Морису Эшеру, являющиеся давней частью исламского искусства это геометрические фигуры, идеально соединяющиеся между собой. (Для примера можно вспомнить мозаику, фрагменты пазлов или тесно упакованные фигуры Тетриса.) Многие из таких тесселяций повторяются снова и снова, подобно рисункам на обоях, а при взгляде издалека ошеломляют.

Лерш решил спроектировать форму для печенья, способную превратить раскатанное тесто в тесселированную плоскость, то есть чтобы между фигурками не оставалось пространства. Эшер когда-то написал, что находит в сложности этих странных паттернов большое удовольствие, поскольку они способны смешивать два и три измерения. И тесселяции действительно давно сбивали с толку и величайшие умы математики, и самые сложные алгоритмы.


В течение предыдущих нескольких лет Лерш экспериментировал с дизайном форм.

Готовка печенья не похожа на то, как будто вы придумываете уравнение на тесте, но, согласно a недавнему исследованию, с точки зрения математики это именно так. Ведущий автор статьи, математик Копенгагенского университета Миккель Абрахамсен, изучает задачу об упаковке. С этой задачей ежедневно сталкиваются предприятия и дизайнеры, когда вычисляют, как уместить максимальное количество объектов в ограниченное пространство. Как можно понять, задача об упаковке влияет на всё, от транспортной отрасли до хранения специй в кухонном шкафу.

Абрахамсен специализируется на изучении того, как алгоритмы можно выражать в геометрической форме именно это и происходит, когда вы вдавливаете форму для печенья в двухмерный холст теста. Мы хотели доказать, что при решении подобных задач об упаковке необходимо решать очень сложные уравнения, рассказывает Абрахамсен.

Команда Абрахамсена утверждает, что задача об упаковке это R-полное уравнение, делающее дальнейший шаг в сложности за пределы нестепенных уравнений, долгое время изучавшихся компьютерными учёными. Сложность задачи частично связана с количеством возможных вариантов. По словам Абрахамсена, чтобы решить задачу оптимальной упаковки тесселяции, занимающей максимально возможное пространство раскатанного теста, нужно заранее знать идеальное расположение каждого отдельного печенья. Однако проблема в том, что существует бесконечное количество способов размещения печенек на листе теста. Плюс при каждом вырезании формой пространство для новых печений уменьшается. Без помощи компьютерной программы вы поймёте уровень оптимальности своей упаковки, только когда кончится место. Для поиска наилучшего решения вам потребуется бесконечное количество попыток, утверждает Абрахамсен.


Эти тесселированные плитки в дворцовом комплексе Альгамбра стали источником вдохновения для Эшера.

Однако это не остановило Лерша, создавшего собственные тематические рождественские тесселяции из колокольчиков, ёлок и других фигур при помощи бесплатной платформы Tess. Друг помог ему напечатать на 3D-принтере несколько форм для печенья, после чего он замесил тесто. Любимое пепперкаке (pepperkake) Лерша это великолепное норвежское имбирное печенье. Работающий химиком Лерш рассказал, что когда-то оно изготавливалось с карбонатом аммония из толчёных оленьих рогов, однако сегодня большинство людей заменяет его разрыхлителем для теста.

Остановившись на рождественской ёлке как на наиболее оптимальной фигуре, Мартин приступил к работе. Подражая узорам Эшера, он расставлял каждую вторую фигуру вниз головой, чтобы их границы идеально совпадали с соседними фигурами. В результате получились переплетённые ряды печенек, между границами которых нет остатков теста.

Однако даже при использовании формы Лерша куски теста остаются по краям паттерна. Именно об этом несовершенстве предупреждал Абрахамсен: существует слишком много переменных при создании формы для печенья сложного контура, чтобы она целиком и каждый раз использовала всё тесто. Для максимизации эффективности можно упростить форму печенек: например, квадратные печенья, вырезаемые из квадратного куска теста. Но, как говорит Лерш, Кому интересно квадратное печенье?


Ещё одна форма Лерша эффективная, но гораздо менее праздничная.

Абрахамсен утверждает, что в случае сложных фигур наподобие рождественских ёлок, нахождение одного наиболее эффективного способа их расположения на плоскости теста на сегодняшний день является нерешаемой задачей. В 1999 году алгоритм был способен решать задачу об упаковке только для квадратного контейнера, содержащего до четырёх объектов (простых восьмиугольников), и для полных расчётов программе требовалось 24 часа. При добавлении в уравнение каждого нового многоугольника алгоритму становилось всё сложнее решать задачу, потому что становится труднее упаковать объект в контейнер, когда пространство уже занято. Насколько известно Абрахамсену, с тех пор не было найдено более быстрого алгоритма.

Однако готовка не всегда заключается в стремлении к совершенству. Нужно поддерживать любые попытки создания наиболее оптимального способа разрезания праздничных печений. Я бы посоветовал людям пробовать это, ради самого удовольствия решения головоломки, говорит Миккель. Об этом полезно размышлять, но не стоит при этом ожидать нахождения оптимального решения.

image

Лерш согласен с тем, что в настоящее время может и не существовать способа создания математически идеальной партии праздничного печенья. Миру придётся подождать ещё более подходящей фигуры, чем его ёлка (которую друг Лерша несколько лет назад выложил онлайн для свободного скачивания. Счастливого Рождества!) Но он всё равно призывает печь тесселяции, пусть даже для собственного развлечения. Если это позволит кому-то избавиться от страха математики или естественных наук, то так даже лучше.





На правах рекламы


Вдсина поздравляет всех с Новым Годом! Пускай 2021 приносит только хорошее, а всякого рода неприятности и ковиды остаются в старом году!
Абсолютно всегда наши виртуальные серверы работают безупречно и без сбоев. Используем исключительно брендовое оборудование, лучшую в своём роде панель управления серверами собственной разработки и одни из лучших дата-центров в России и ЕС. В Новом Году порадуем множеством приятных сюрпризов.

Подробнее..

Опубликован Scheme Request For Implementation 203 A Simple Drawing Language in the Style of SICP

18.09.2020 18:11:01 | Автор: admin
Функциональная геометрияФункциональная геометрия

SICP

Обложка SICPОбложка SICP

Structure and Interpretation of Computer Programs -- это один из самых известных учебников программирования в мире, на основе которого несколько десятков лет преподавался начальный курс программирования в MIT, а во многих унивеситетах, в том числе в Беркли, преподаётся до сих пор.

SICP использует Scheme в качестве основного (практически единственного) языка программирования. Тем не менее, нельзя сказать, что это учебник Scheme, потому что он выходит далеко за пределы того, что обычно входит в программу "изучения языка". Стоит только упомянуть, что в программу входят системы распространения ограничений, интерпретаторы языков программирования, симуляторы цифровых схем, а также симулятор целого процессорного модуля.

Большая часть тем, входящих в учебник, выполнимы на "стандартной" (в смысле, соответствующего последнему на текущий момент стандарту Revised^7 Report on Algorithmic Language Scheme) Scheme.

Особенные темы

Цифовой сумматор, реализуемый в качестве одного из упражений SICPЦифовой сумматор, реализуемый в качестве одного из упражений SICP

Однако, для нескольких тем, встроенных средств языке недостаточно. В частности, темы случайных чисел, измерения времени выполнения, многопоточности и графического вывода стандартом языка не рассматриваются.

Принятая по-умолчанию в учебнике реализация MIT/GNU-Scheme содержит необходимые примитивы, расширяющие базовый язык так, чтобы курс становился проходим.

За многие годы, прошедшие с момента выхода SICP, некоторые реализации Scheme также реализовали многие примитивы, требуемые для прохождения курса.

Однако, до текущего момента не существовало какого-либо нормативного документа, специфицирующего, каким именно требованиям должен удовлетворять интерпретатор, чтобы "поддерживать" прохождение курса.

SRFI

Логотип community processЛоготип community process

Scheme Requests for Implementation -- это community process, принятый в семействе языков Scheme. В некоторых аспектах он Java Community Process или Python Enhancement Proposals. Так или иначе, это главный инструмент обсуждения развития языкового семейства, а также главный инструмент обеспечения переносимости кода.

Написание SRFI показалось автору сей заметки естественным выбором для формализации требований к программным системам.

В связи с тем, что ассортимент тем, предлагаемых для выполнения, достаточно велик, показалось разумным ограничить предлагаемый документ узкой, хорошо формализованной, хотя в тоже время очень абстрактной темой графического вывода.

Функциональная геометрия

Основой главы, посвящённой графической подсистема компьютера, в SICP послужила статься Питера Хендерсона "Функциональная Геометрия". (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.137.1503, https://eprints.soton.ac.uk/257577/1/funcgeo2.pdf)

Образец рисунка, сделанный методом функциональной геометрииОбразец рисунка, сделанный методом функциональной геометрии

Знакомым с творчеством Морица Эшера это изображение может показаться смутно знакомым.

В основе техник функциольнальной геометрии лежат две идеи.

  • Первая идея в том, что должен существовать некоторый языковой объект painter, который при активации должен рисовать в нужном месте холста (экрана) что-то заданное программистом. (В Scheme painter -- это функция.)

  • Вторая идея в том, что нужен какой-то способ комбинировать painter'ы, получая новые painter'ы.

В КДПВ вынесена иллюстрация этого подхода.

Реализация

В предложенном SRFI не предоставленно исчерпывающей реализации метода функциональной геометрии. Однако, предложен субстрат, достаточный для того, чтобы активный студент мог сам реализовать подмножество функциональной геометрии, предложенной в SICP на любом интерпретаторе, поддерживающем SRFI-203 (результат работы автора сей заметки).

Полный текст предложения находится по ссылке:

https://srfi.schemers.org/srfi-203/srfi-203.html

Абстракт и технические детали можно найти здесь:

https://srfi.schemers.org/srfi-203/

SRFI находился на обсуждении два месяца, и за это время было предложено две реализации, для интерпретатора Chibi, и для интерпретатора Kawa.

Логотип Chibi-SchemeЛоготип Chibi-Scheme

Заключение

Автор сей заметки (он же автор SRFI) надеется, что предложенное им расширение языка будет позитивно воспринято сообществом. (Те, кто уже сейчас пользуются Scheme, могут предложить поставщикам своего интерпретатора включить это расширение в следующий выпуск.) Автор также надеется, что тем, кто начинает изучать Scheme, SICP или компьютерную графику, данное расширение также поможет сэкономить усилия, затрачиваемые на технические детали, и там самым освободить больше ресурсов для собственно обучения.

Подписка

Те, кому кажется целесообразным выполняемая работа, приглашаются задонатить по PayPal-ссылке. Также все желающие приглашаются подписаться на обновления.

  • Telegram :: http://t.me/unobvious

  • GitLab :: http://gitlab.com/lockywolf

  • Twitter :: https://twitter.com/VANikishkin

  • PayPal :: https://paypal.me/independentresearch

Подробнее..

OpenCASCADE и Невидимое солнце Дао

09.09.2020 18:05:36 | Автор: admin

Тот лучший путник, что следов не оставляет
Тот лучший лидер, что без речи вдохновляет
План совершенен, если плана вовсе нет
И если мудрый двери закрывает,
Вам никогда не разгадать секрет.

Великая книга Дао - Стих 27 ( Перевод Ю. Полежаевой)

Привет, Хабр! Хочу сегодня пригласить в увлекательное 3D-путешествие. Мне нравится 3D. И хотя я пробовал работать в разных программах, но меня не покидало чувство, что мне чего-то не хватает. Даже если пользоваться встроенным скриптингом.

Поэтому я постепенно пришел к идее, что для реализации моих безумных творческих идей, наверное лучше подойдут CAD-системы. Вот там есть где разгуляться 3D-фантазии. Мощные алгоритмы создания поверхностей пересечений, проекций, аппроксимаций. Это как раз то, что нужно. Вообще, мне кажется, что разработчики промышленных геометрических CAD-ядер относятся к остальному 3D миру по принципу "Солдат ребенка не обидит".

Конечно, в своих поисках я не мог пройти мимо открытого CAD-ядра OpenCascade. Эта библиотека предоставляет уникальную возможность ближе познакомится с принципами внутреннего устройства современных CAD-систем. Вдвойне приятно, что это можно сделать на дружелюбном языке Python.

От одной мысли о всех этих чудесах, мое сердце начинает биться сильнее. Как поется в одной песне - я приятную дрожь ощущаю с головы до ног. Тех у кого в этот вечер похожее настроение - прошу под кат. Будем рисовать Инь и Янь в объеме.

Главное - поставить сильную задачу

Для того, чтобы испытать CAD-ядро, я решил нарисовать в объеме символ Дао. Какой практический смысл в рисовании древнего китайского символа? Да практически никакого, кроме того, что в процессе рисования потребуются нетривиальные операции и мы сможем проверить, насколько ядро устойчиво ко всяким творческим 3D-махинациям.

Мне в этом смысле понравилась идея, которую я услышал по телевизору от одного астронома. Ведущий его спросил: "Какой практический смысл имеется в астрономии для экономики и народного хозяйства?" Любой ученый от подобных вопросов может легко впасть в депрессию. Но в данном случае астроном не растерялся и ответил, что главный смысл астрономии для народного хозяйства в том, что она ставит перед инженерами по настоящему сильные задачи. Благодаря этому появились сверхчувствительные приемники, сверхточная обработка поверхностей, и много еще чего сверх.

Задача поставлена. И все на что мы можем надеяться - это на древние силы даосизма и на современные силы 3D-моделирования. Как гласит древняя китайская мудрость даже самый далекий и сложный путь начинается с первого шага.

Шаг 1. Настройка среды

Приведу ссылку на разработанный мною документ по настройке OpenCascade в среде Анаконда. Инструкция расcчитана на Win64. Но я думаю, что на Linux можно настроить, не намного сложнее, а может даже и проще.

Установка OpenCascade - Python 3.7 - Win64

Здесь же я оставлю еще несколько ссылок, которые помогут ближе познакомится с OpenCascade

При запуске команд, conda (пакетный менеджер Анаконды) будет пыхтеть и ворчать, считать и пересчитывать зависимости. Когда же он завершит свою нелегкую работу и все нормально запустится, будет ощущение что вам крупно повезло. Возможно так оно и есть.

Шаг 2. Небольшая самодельная библиотека

Чтобы не загромождать код ненужными деталями я написал небольшой набор функций. Ничего выдающегося в нем нет, но я приведу описание этих функций, чтобы было понятно что происходит в примерах.

#initMode = 'screen','web','stl'def ScInit(initMode, decoration, precision, exportDir):  pass#default styles#'stInfo' - for service objects#'stMain' - for main object of drawing#'stFocus' - for important detailsdef ScStyle(styleVal):  pass#draw objectsdef ScPoint(pnt, style):  passdef ScLine(pnt1, pnt2, style):  passdef ScCircle(pnt1, pnt2, pnt3, style):  passdef ScShape(shape, style):  passdef ScLabel(pnt, text, style):  pass#start renderdef ScStart()    

К слову сказать, в библиотеке PythonOCC, кроме непосредственно интерфейса к функциям ядра OpenCascade (cгенерированного с помощью SWIG) понаписано еще много всякого Python-кода, сильно облегчающего жизнь, и за это хочется сказать спасибо тем, кто это сделал.

Шаг 3. Немного о структуре OpenCASCADE

Библиотека OpenCascade неплохо структурирована - в ней все разнесено по уровням. Вначале это кажется излишним, но потом понимаешь, что это разделение вполне логично и полезно. Я бы выделил четыре основных уровня. Чтобы на экране что-то появилось нужно пройти все эти уровни. К счастью, переходы между уровнями довольно легко организованы с помощью различных конструкторов и деструкторов

  1. Математический уровень (линейная алгебра) - точки, вектора, направления, оси, преобразования. Названия пакетов начинаются с gp (что это значит я так и не понял - может geometry primitives)

  2. Геометрический уровень - здесь мы сталкиваемся с различными двухмерными и трехмерными кривыми и поверхностями, задаваемыми различными способами. Названия пакетов начинаются с Geom

  3. Топологический (структурный уровень) - на этом уровне из геометрических объектов, как лоскутное одеяло, сшиваются рабочие объекты. Основные понятия - вершина (vertex), ребро(edge) отрезок кривой или прямой, соединяющий две вершины, контур (wire) - замкнутый набор из ребер, грань (face) - поверхность ограниченная контуром, оболочка (shell) - замкнутый набор граней, ограничивающий некоторый объем, тело (solid) - непосредственно сам объем, ограниченный оболочкой. Согласитесь, что разделение понятий оболочки и тела - граничит с деструктивным педантизмом и во многих 3D-приложениях данное различие просто не принимается во внимание. Здесь же все разложено по полочкам. Топологический уровень - основное отличие библиотек, основанных на граничном представлении объектов (boundary representation), поэтому пакеты данного уровня начинаются с префикса BRep и Topo

  4. Уровень отображения - здесь мы конструируем объекты, которые непосредственно появляются на экране и взаимодействуют с пользователем. Геометрические формы обретают цвет, материал, положение в пространстве, могут быть выбраны мышкой и вообще ведут себя с пользователем очень дружелюбно, за что им был дан префикс AIS).

Еще хотелось бы поделится некоторыми наблюдениями, которые могут вам помочь в работе.

  1. Имя каждого объекта имеет префикс, совпадающий с именем пакета в котором он находится. Это железная необходимость, которая позволяет создателям библиотеки самим не запутаться во всем этом зоопарке. Поэтому при импорте в Python смело пишите в качестве пакета префикс объекта - вы никогда не ошибетесь. Кроме того, зная префикс, можно посмотреть, какие объекты еще есть в пакете. Возможно они подойдут для ваших целей больше, чем тот объект, который вы увидели в примере.

  2. Создатели OpenCascade в плане придумывания имен и сокращений обладают буйной фантазией и имена объектов OpenCascade не пересекаются с именами никаких других библиотек. Поэтому если вы хотите получить справку по объекту - смело вводите его имя в Google. Ссылка на документацию на этот объект окажется в первой строчке выдачи.

  3. Имена и методы объектов не изменяются в зависимости от языка на котором происходит общение с OpenCascade, поэтому вы легко можете использовать примеры и на родном для библиотеки C++, и на ставшем уже экзотикой Tcl, также можно встретить примеры на Java. При должных навыках компьютерного полиглотства все эти примеры легко транслируются в Python.

  4. При использовании объектов будьте внимательны, педантичны и действуйте аккуратно. Очень часто имена объектов и методов отличаются всего на одну букву, а результат их работы отличается кардинально. Я так обжигался несколько раз, и только удача спасала мое психическое здоровье.

Теперь можно приступать к рисованию. Начнем с классики.

Шаг 4. Классические формы Инь и Янь.

Будем использовать принципы параметрического моделирования и единственный параметр который нам потребуется - это r - базовый радиус даосского символа. Как известно символ состоит из большой дуги и двух малых дуг. Я разобью малую дугу головы символа на две дуги. Я это делаю, потому что хочу чтобы в топологии присутствовала точка - вершина символа. Она нам в дальнейшем сильно поможет в построениях.

Первое, что мы сделаем - наметим базовые точки, на которых будет построен нужный нам контур. Базовые точки включают в себя вершины дуг, а также центральные точки для каждой дуги. Построение дуги по трем точкам - это самый удобный способ построения дуги как на плоскости, так и в пространстве. Поверьте мне на слово - если вы задумайте построить дугу каким-то другим способом вы надолго выпадите из культурной, рабочей и семейной жизни.

Вот что получилось (обращаю внимание здесь и далее - это не полный код, а важные для шага процедуры, ссылка на полный код в конце поста):

def getPntsBase(r):        r2 = r/2        gpPntMinC = gp_Pnt(0,r2,0)        p0 = gp_Pnt(0,0,0)          p1 = getPntRotate(gpPntMinC , p0, -pi/4)          p2 = gp_Pnt(-r2,r2,0)          p3 = getPntRotate(gpPntMinC , p0, -pi/4*3)          p4 = gp_Pnt(0,r,0)          p5 = gp_Pnt(r,0,0)          p6 = gp_Pnt(0,-r,0)          p7 = gp_Pnt(r2,-r2,0)              return p0, p1, p2, p3, p4, p5, p6, p7  def getWireDaoClassic(ppBase):        p0, p1, p2, p3, p4, p5, p6, p7  = ppBase        arc1 =  GC_MakeArcOfCircle(p0,p1,p2).Value()    arc2 =  GC_MakeArcOfCircle(p2,p3,p4).Value()    arc3 =  GC_MakeArcOfCircle(p4,p5,p6).Value()    arc4 =  GC_MakeArcOfCircle(p6,p7,p0).Value()     edge1 = BRepBuilderAPI_MakeEdge(arc1).Edge()    edge2 = BRepBuilderAPI_MakeEdge(arc2).Edge()    edge3 = BRepBuilderAPI_MakeEdge(arc3).Edge()    edge4 = BRepBuilderAPI_MakeEdge(arc4).Edge()      shape =  BRepBuilderAPI_MakeWire(edge1, edge2, edge3, edge4).Wire()        return shape def slide_01_DaoClassic(r):        drawCircle(r, 'stInfo')    pntsBase = getPntsBase(r)    drawPoints(pntsBase, 'stFocus', 'b')    shapeDaoClassic = getWireDaoClassic(pntsBase)    ScShape(shapeDaoClassic, 'stMain')
Рис 01. Контур классического ДаоРис 01. Контур классического Дао

Прикладываю ссылку на WebGL-презентацию: Слайд 01 Контур классического Дао

Здесь вы можете посмотреть этот чертеж в объеме. Если у вас есть 3D-телевизор или 3D-проектор то возможен просмотр в стерео-режиме. Просто нажмите иконку 3D - 1 раз - перекрестный взгляд - 2 раза - режим SideBySide.

В завершение этого этапа хочу немного поразмышлять - это у меня такая беда - размышлять по самым пустяковым поводам.


Если вы задумайте определять координаты точек и расстояния, с помощью теоремы Пифагора и тригонометрических знаний, полученных в 6-ом классе, то это конечно сработает, но настоящие CAD-индейцы так не поступают. Все что вам нужно в плане нахождения координат, углов, расстояний и направлений делается с помощью векторной алгебры без привлечения каких-либо других допотопных методов. Создатели 3D-библиотек очень расстроятся, если вы вдруг для поворотов в пространстве не будете использовать квартернионы, которые они так заботливо реализовали специально, чтобы облегчить вам жизнь.

Не вздумайте задавать углы в градусах и писать функции типа DegreeToRadian. Импортируйте константу pi и задавайте углы поворота только как pi, pi/4, -pi/8 и так далее. Если кто-то из ваших знакомых прознает, что вы все еще мыслите в градусах, о вас поползет дурная слава. В мире математики вы станете изгоем и даже выпускники 9-ых классов никогда не подадут вам руки. Чтобы как-то обосновать эту мысль, скажу, что вся тригонометрия вычисляется на компьютере при помощи рядов и значение в радианах сразу можно подставить в ряд без каких-либо преобразований. В общем, давайте беречь ресурсы наших компьютеров.

На самом деле вопрос не столь очевиден. Так когда мне в 8 классе сказали, что теперь начинается другая жизнь и отныне мы будем измерять углы в естественных единицах - радианах, я очень удивился. Ничего естественного в том, чтобы задавать углы иррациональными числами я не увидел. Наиболее естественным мне представлялась измерять углы а оборотах - 1 - 1 оборот, 2 - 2 оборота. Конечно я тогда был наивен и не знал про ряды, пределы, гармонический анализ , и про то что вся математическая кухня намного упрощается если исходить из радианов.


Здесь уже можно перейти к следующему шагу и попробовать немного улучшить, то что придумали китайцы шесть тысяч лет назад.

Шаг 5. Улучшаем совершенство

Давайте сделаем так, чтобы между нашими Инь и Янь был некоторый отступ. Так мы подготовим базу для объемных построений. Согласитесь, если объемные тела будут соприкасаться это будет не очень красиво.

Здесь мы проведем первое испытание библиотеки на математическую прочность. Используем функцию отступа. Она называется Offset. Для этого нам понадобится еще один параметр - размер отступа.

def getShapeOffset(shape, offset):    tool = BRepOffsetAPI_MakeOffset()    tool.AddWire(shape)    tool.Perform(offset)    shape = tool.Shape()      return shapedef slide_02_DaoConcept(r, offset):        drawCircle(r + offset, 'stInfo')    pntsBase = getPntsBase(r)    wireDaoClassic = getWireDaoClassic(pntsBase)    wireDao0 = getShapeOffset(wireDaoClassic, -offset)    ScShape(wireDao0, 'stMain')      pntsDao0 = getPntsOfShape(wireDao0)    drawPoints(pntsDao0, 'stFocus', 'd')      wireDao1 = getShapeOZRotate(wireDao0, pi)    ScShape(wireDao1, 'stInfo')
Рис 02. Контур Дао с отступомРис 02. Контур Дао с отступом

Ссылка на WebGL-презентацию: Слайд 02 Контур Дао с отступом

Ура, получилось. Обратите внимание, как бережно библиотека обошлась с топологией. Количество точек было сохранено и они оказались именно там где нужно. Я считаю это большое достижение для создателей библиотеки. Настало время для серьезных дел - выходим в 3D.

Шаг 6. Строим сечение. Заметки о самом главном.

Как задать форму объемного тела? Один из методов заключается в том, чтобы задать сечения объекта. Причем если нам удастся сделать это непрерывным образом - считайте дело в шляпе. С точки зрения математики наша задача решена. Кому-то этот шаг может показаться невзрачным, но именно он является САММ ГЛАВНМ с точки зрения построения объекта.

Если мы внимательно посмотрим на наш объект, то с геометрической точки зрения мы отчетливо можем выделить две составляющие - голову круглой формы и хвост, форма которого вообще не имеет определенного названия. Сечения для головы и хвоста должны строится по-разному.

Голову мы будем рассекать параллельными прямыми. Понятно, что в результате получится полусфера, но чтобы сохранить общий подход мы все-таки построим ее с помощью сечений. Сечения же для хвоста будем проецировать из некоего фокуса. Где должен быть этот фокус? Фокус должен находится в точке, откуда все сечения будут максимально условно перпендикулярны к объекту. Путем подбора я определил, что наилучшие результаты получаются когда фокус находится на оси Y на расстоянии -r/4 от центра.

Сечение будем задавать с помощью параметра k. При к = 0 мы находимся в начале нашей фигуры. При k = 1 в конце. Во всех промежуточных значениях алгоритм должен строить сечение объекта. Что касается самого сечения - предположим что это окружность (раз уж здесь везде окружности)

def getPntDaoFocus(r):    return gp_Pnt(0,-r/4,0)def getPntsForDaoSec(pntDaoStart, pntUpLimit, pntDaoEnd, pntDownLimit, pntFocus, k):    angleLimit = 0    pntLimit = getPntScale(pntFocus, pntUpLimit, 1.2)    angleStart = getAngle(pntFocus, pntLimit, pntDaoStart)    angleEnd = getAngle(pntFocus, pntLimit, pntDaoEnd)    kLimit = (angleLimit - angleStart)/(angleEnd - angleStart)    if k < kLimit: #head        kHead = (k - 0) / (kLimit- 0)        xStart = pntUpLimit.X()        xEnd = pntDaoStart.X()        dx = (xEnd-xStart)*(1 - kHead)        pnt0 = getPntTranslate(pntFocus, dx, 0, 0)        pnt1 = getPntTranslate(pntLimit, dx, 0, 0)    else: #tail            kTail = (k - kLimit) / (1 - kLimit)        angle = -angleEnd*kTail        pnt0 = pntFocus        pnt1 = getPntRotate(pntFocus, pntLimit, angle)    return pnt0, pnt1def getWireDaoSec(shapeDao, pntFocus, k):        pntsDao = getPntsOfShape(shapeDao)    pntDownLimit, pntDaoStart, pntUpLimit, pntDaoEnd = pntsDao        p1, p2 = getPntsForDaoSec(pntDaoStart, pntUpLimit, pntDaoEnd, pntDownLimit,                               pntFocus, k)    sectionPlane = getFacePlane(p1, p2, 3)        pnt0, pnt1 =  getPntsEdgesFacesIntersect(shapeDao, sectionPlane)    pntUp = getPntSectionUp(pnt0, pnt1)    circle = GC_MakeCircle(pnt0, pntUp, pnt1).Value()    edge = BRepBuilderAPI_MakeEdge(circle).Edge()    wire =  BRepBuilderAPI_MakeWire(edge).Wire()    return wire   def slide_03_DaoSecPrincipe(r, offset, k, h):        drawCircle(r + offset,  'stInfo')    pntsBase = getPntsBase(r)    wireDaoClassic = getWireDaoClassic(pntsBase)    wireDao0 = getShapeOffset(wireDaoClassic, -offset)    ScShape(wireDao0, 'stMain')        # for oure goal we need divide Dao on Head and Tail    # Head sections is parallell    # Tail sections is focused on focus point    pntsDao0 = getPntsOfShape(wireDao0)    pntDownLimit, pntDaoStart, pntUpLimit, pntDaoEnd  = pntsDao0        # we need focus to determine tail sections     pntFocus = getPntDaoFocus(r)    ScPoint(pntFocus, 'stMain')    ScLabel(pntFocus, 'F' ,'stMain')        # we need two points to determine section    pnt1, pnt2 = getPntsForDaoSec(pntDaoStart, pntUpLimit, pntDaoEnd,                                   pntDownLimit, pntFocus, k)    ScLine(pnt1, pnt2, 'stFocus')        # !!! we need use plane to detect intercsect (not line) becouse 3D    planeSec = getFacePlane(pnt1, pnt2, h)    ScShape(planeSec, 'stFocus')    pntsSec =  getPntsEdgesFacesIntersect(wireDao0, planeSec)    drawPoints(pntsSec, 'stFocus')        wireSec = getWireDaoSec(wireDao0, pntFocus, k)    ScShape(wireSec, 'stFocus') 
Рис 03 Принцип построения сеченийРис 03 Принцип построения сечений

Ссылка на WebGL-презентацию: Слайд 03 Принцип построения сечений

Здесь понадобилась еще одна нетривиальная операция - пересечение кривой и поверхности. В качестве кривой выступает построенный нами двухмерный дао-контур. В качестве поверхности выступает вспомогательная плоскость, она проходит из фокуса под углом, определяемым нашим k. Алгоритм пересечения работает надежно и устойчиво. При первых попытках мне показалось, что он выдает ошибку. Но в результате оказалось что ошибался я, а алгоритм отрабатывает на пятерочку.

Хотелось бы еще немного порассуждать вот на какую тему? Почему мы ищем пересечение кривой и плоскости - не проще ли найти пересечение прямой и кривой? Ответ в том, что не проще. Не забывайте, что мы в 3D а здесь пересечение двух кривых необычное и редкое событие. Данный алгоритм попросту не существует.

Можно конечно вернуться в 2D, но это сложный путь. Из 2D в 3D перейти просто, а обратно гораздо сложнее. Поэтому думаю, что выйдя однажды в 3D лучше оставаться там до конца карьеры :) Хорошая новость заключается в том что практически для любой проблемы существуют изящные 3D решения.


Раз уж была затронута эта тема, хочу немного сказать о 3D-мышлении. Мне очень нравится все что касается объемного конструирования, это затрагивает какие-то базовые нейронные структуры, возможно где-то в глубине, на уровне мозжечка и я от всего этого испытываю реальный кайф. Откуда это у меня - я думаю все дело в близких мне людях.

Хочется рассказать про отца. Это боевой конструктор старой закалки. И я до сих пор учусь у него использовать инженерный подход к различным проблемам, начиная от философских и заканчивая бытовыми.

Еще хочется рассказать о моих институтских друзьях. Когда я учился в институте в нашем небольшом провинциальном городке, мне повезло и я, так сказать, попал в 3D-обойму. Это была группа студентов, которых посылали от кафедры графики по всей России на различные соревнования по начертательной геометрии, черчению, конструированию, и прочим вещам. Замечу, что это были лихие девяностые и перед руководителями кафедры часто стоял прямой выбор - выплатить зарплату, купить принтер, или послать группу студентов на соревнования. К чести кафедры выбор почти всегда делался в пользу соревнований. Так вот в этой 3D-обойме были действительно уникальные личности (похоже, что я там был самый бестолковый).

Расскажу один эпизод (а таких эпизодов был вовсе не один). Мой хороший друг Сергей (а он тоже был в обойме), в смутные времена, когда все сидели без денег устроился на некую сомнительную работу. Работа заключалась в том, что где-то на окраине города в сыром и темном подвале стоял высокоточный современный американский металлообрабатывающий центр (я все это видел своими глазами). И Сергей вытачивал на нем на заказ детали весьма причудливой формы. Никакого специального ПО, кроме карандаша и бумаги у него не было. Все команды он вводил непосредственно с пульта станка. Однажды между делом он выточил некую деталь, основу которой составляла коническая многозаходная резьба весьма сложного профиля. Про это узнали. Среди научно-технической элиты города поползли нехорошие слухи, что где-то на задворках происходит какая-то технологическая чертовщина. Слухи достигли авиационного моторного завода и об этом узнал начальник одного из серьезных цехов. Этот начальник все выяснил и лично спустился в сырой и темный подвал, чтобы увидеть все эти чудеса. Потому что весь его отдел, вооруженный Юниграфиксами, очень часто не мог сделать то что нужно.


Надеюсь, я вас немного поразвлек и можно двигаться дальше по узкой китайской тропинке.

Итак, в результате работы алгоритма пересечения получаем две искомые точки, через которые просто проводим симметрично расположенную окружность. Сечение готово. Чтобы проверить, как это работает построим сечения для k от 0 до 1 c постоянным шагом.

def slide_04_DaoManySec(r, offset, kStart, kEnd, cnt):        drawCircle(r + offset, 'stInfo')    pntsBase = getPntsBase(r)    wireDaoClassic = getWireDaoClassic(pntsBase)    wireDao0 = getShapeOffset(wireDaoClassic, -offset)    ScShape(wireDao0, 'stMain')        pntsDao0 = getPntsOfShape(wireDao0)    pntDownLimit, pntDaoStart, pntUpLimit, pntDaoEnd  = pntsDao0        pntFocus = getPntDaoFocus(r)        for i in range(cnt+1):        k = i/cnt        kkScale = kEnd - kStart        kk = kStart + k* kkScale        p0,p1 = getPntsForDaoSec(pntDaoStart, pntUpLimit, pntDaoEnd,         pntDownLimit, pntFocus, kk)        ScLine(p0, p1, 'stFocus')        wireSec = getWireDaoSec(wireDao0, pntFocus, kk)        ScShape(wireSec, 'stMain') 
Рис 04 Форма Дао из сеченийРис 04 Форма Дао из сечений

Ссылка на WebGL-презентацию: Слайд 04 Форма Дао из сечений

Итак мы проникли в святая святых и выяснили форму бесформенного Дао. Что теперь делать с этим сакральным знанием? Как из всего этого получить нормальное тело?

Предлагаю воспользоваться методом, который называется протягиванием. Он заключается в том, что специальному алгоритму предъявляются последовательные сечения тела и он пытается построить поверхность. Все это относится к широкой области моделирования с ограничениями. Еще можно встретить термины скининг (натягивание кожи), пайпинг (делание трубы).

Должен отметить что главное при протягивании - не протянуть ноги, подбирая различные параметры различных алгоритмов. Посмотрим как поведет себя наше ядро.

Шаг 7. Получаем готовую геометрию

Первая мысль - задать как можно больше сечений и алгоритм разберется, что к чему. К сожалению так не получится. Процесс аппроксимации - сложная штука. И в принципе нужно стремится к тому, чтобы ограничений накладываемых на алгоритм было как можно меньше. Если кто-нибудь рисовал сплайны, то он знает, что наиболее красивые формы получаются, когда мы уменьшаем количество точек а не увеличиваем. Нужно выбрать минимальное количество сечений, которые сформируют максимально точную геометрию.

Чтобы процесс протягивания был конструктивным и приятным я сделал следующие вещи.

  • Создал в Python список, содержащий коэффициенты опорных сечений и вывел эти сечения их на экран.

  • Кроме того я вывел на экран сам контур Дао, который мы нарисовали на втором шаге. Как известно этот контур является Абсолютной Истиной. По отношению к этой истине мы и будем оценивать наши результаты.

Не буду утомлять описанием подбора количества и расположения сечений. Скажу лишь, что это не заняло много времени, потому что была организована хорошая обратная связь - сразу было видно где форма отклоняется от идеала. Представляю конечный результат усилий.

def slide_05_DaoSkinning (r, offset):        drawCircle(r + offset,  'stInfo')    pntsBase = getPntsBase(r)    wireDaoClassic = getWireDaoClassic(pntsBase)    wireDao0 = getShapeOffset(wireDaoClassic, -offset)    ScShape(wireDao0, 'stMain')        pntsDao0 = getPntsOfShape(wireDao0)    pntDownLimit, pntDaoStart, pntUpLimit, pntDaoEnd  = pntsDao0        pntFocus = getPntDaoFocus(r)    drawPoints(pntFocus, 'stMain')      ks = [ 3, 9 , 16, 24, 35, 50, 70, 85]     wiresSec = []     for k in  ks:       wireSec = getWireDaoSec(wireDao0, pntFocus, k/100)       ScShape(wireSec, 'stMain')       wiresSec += [wireSec]            solidDao0 = getShapeSkin(pntDaoStart, wiresSec, pntDaoEnd)    ScShape(solidDao0, 'stFocus')
Рис 05 Протягивание поверхности через сеченияРис 05 Протягивание поверхности через сечения

Ссылка на WebGL-презентацию: Слайд 05 Протягивание поверхности через сечения

Хочу обратить внимание на то, как получились начальная и конечные точки геометрии. Алгоритм понял, что начало должно быть гладким, а кончик острым. Честно говоря, я на это не надеялся и предвидел большие проблемы. Но все как-то получилось само собой. Давайте придадим нашей форме законченность. Во первых для придания динамизма и необычности - слегка приплюснем ее по вертикали.

Хочется немного рассказать с какой неожиданной проблемой я столкнулся. Никак не ожидал забуксовать на таком ровном месте. За различные преобразования в OpenCascade отвечает объект gp_Trsf. До сих пор он вел себя прилично и удовлетворительно. Но когда я с помощью его попытался приплюснуть геометрию у меня ничего не получалось. Началось с того, что я не нашел метода изменения масштаба отдельно по осям. Затем я пытался вручную задавать коэффициенты трансформации. Ничего не получалось. Объект магическим способом сопротивлялся всем попыткам.

Истина оказалась проста. OpenCascade конструкторское ядро и оно не для дешевых эффектов Поэтому базовый объект трансформации не позволяет искажать геометрию. Он защищает объекты от нелогичных изменений. Для тех же кто хочет большего и понимает зачем он это делает существует другой объект gp_GTrsf. Вот с помощью его то у меня все и получилось.

Далее мы скопируем нашу форму с разворотом на 180 градусов... Ой, простите на pi ... Да, да... конечно наpi :) И раскрасим все это в приятные цвета.

def getSolidDao(r, offset):        pntsBase = getPntsBase(r)    wireDaoClassic = getWireDaoClassic(pntsBase)    wireDao = getShapeOffset(wireDaoClassic, -offset)        pntsDao = getPntsOfShape(wireDao)    pntDownLimit, pntDaoStart, pntUpLimit, pntDaoEnd  = pntsDao        pntFocus = getPntDaoFocus(r)       ks = [ 3, 9 , 16, 24, 35, 50, 70, 85]     wiresSec = []     for k in  ks:       wireSec = getWireDaoSec(wireDao, pntFocus, k/100)       wiresSec += [wireSec]            solidDao = getShapeSkin(pntDaoStart, wiresSec, pntDaoEnd)    solidDao = getShapeZScale(solidDao, 0.7)    return solidDao   def slide_06_DaoComplete (r, offset):        solidDao0 = getSolidDao(r, offset)    ScShape(solidDao0, stDao0)    solidDao1  = getShapeOZRotate(solidDao0, pi)    ScShape(solidDao1, stDao1)
Рис 06 Окончательная форма Дао Рис 06 Окончательная форма Дао

Ссылка на WebGL-презентацию: Слайд 06 Окончательная форма Дао

Шаг 8. Современная основа для древней философии

Согласитесь, даже гениальные идеи не могут висеть в воздухе, поэтому сделаем небольшую подставку для нашего объемного Дао. А заодно и проверим наше геометрическое ядро на прочность в плане булевых операций с объектами.

Вычесть куб из сферы - и так нелегкая задача. А когда в булевых операциях участвует геометрия, сформированная нетривиальным образом - результат не может предсказать никто. Вот и посмотрим на что действительно способен Open Source.

Код следующего шага несложный, чего не скажешь о стоящей за ним математике. Замечу, что для того, чтобы наши Инь и Янь удобно лежали на подставке я ввел параметр gap - технологический зазор по всему контуру - где-то 1 мм.

def getDaoCase(r, offset, h):    r2 = r*2                                        h2 = h/2    rTop = r + offset    rSphere = gp_Vec(0,rTop,h2).Magnitude()    sphere = BRepPrimAPI_MakeSphere(rSphere).Shape()    limit = BRepPrimAPI_MakeBox( gp_Pnt(-r2, -r2, -h2), gp_Pnt(r2, r2, h2) ).Shape()    case = BRepAlgoAPI_Common(sphere, limit).Shape()    case = getShapeTranslate(case, 0,0,-h2)         solidDao0 = getSolidDao(r, offset)    solidDao1  = getShapeOZRotate(solidDao0, pi)       case = BRepAlgoAPI_Cut(case, solidDao0).Shape()    case = BRepAlgoAPI_Cut(case, solidDao1).Shape()      return case    def slide_07_DaoWithCase (r, offset, caseH, caseZMove ,gap):        solidDao0 = getSolidDao(r, offset+gap)    ScShape(solidDao0, stDao0)    solidDao1  = getShapeOZRotate(solidDao0, pi)    ScShape(solidDao1, stDao1)        case = getDaoCase(r, offset, caseH)        case = getShapeTranslate(case, 0,0, caseZMove)    ScShape(case, stCase)
Рис 07. Форма Дао с основаниемРис 07. Форма Дао с основанием

Ссылка на WebGL-презентацию: Слайд 07 Форма Дао с основанием

Должен сказать, что получилось не сразу, но все-таки получилось. Да, обидно, что ядро спотыкается и мы вынуждены прибегать к шаманизму для получения результата. Но учитывая, какая сложная математика здесь присутствует можно сделать на это поправку.

Невидимое солнце Open Source

Вот и закончилось это увлекательное 3D-мистичекое-приключение. Боги к нам были благосклонны и практически все получилось. Оставляю несколько ссылок:

  • GitHub - Точка сборки - ссылка на репозиторий с проектом, в рамках которого было проделано это исследование.

  • makeDaoShape.py - ссылка на полный текст примера

  • Инь, Янь, Подставка. - ссылки на STL-файлы (мало ли кому пригодятся). Только пожалуйста - не перепутайте Инь и Янь - понятно что отличия минимальны, но кто знает этот загадочный Китай :)

Если подвести итог в целом, то мне понравилось знакомство с OpenCascade. Это просто чудо, что такие вещи лежат в открытом доступе и их можно изучать со всех сторон. Пусть порой было не все гладко. Да и код, который я написал совсем не совершенен. Но ведь идеального не бывает ничего. И это наверное самое интересное свойство нашего мира.

Нам надо знать, когда остановиться
Сосуд нельзя сверх меры наполнять
Большие ценности труднее охранять
И слишком острый меч быстрее притупится
Добром ли чином через чур гордится
Беду на дом свой накликать
Твой труд закончен, так умей уйти
Вот смысл силы, жизни и пути.

Великая книга Дао - Стих 9 ( Перевод Ю. Полежаевой)

Подробнее..

Перевод Поле течения алгоритмы применения

18.11.2020 14:04:51 | Автор: admin

Поля течения - невероятно мощный и гибкий инструмент для создания необычных линий. Это один из основных инструментов, который я несколько лет использовал в моих генеративных произведениях, и я осознаю, что обращаюсь к нему снова и снова. Вполне возможно, что я использовал его столько раз при написании кода, сколько не использовал никто другой.

Также поля течения - то, на что программисты натыкаются в первую очередь, когда только начинают заниматься генеративным искусством, но немногие уделяют время детальному изучению принципов их работы и тому, как их можно использовать. В этой статье я освечу основы полей течения, предложу разные варианты их использования и дам советы как сделать из них что-то красивое.

СЕТКА УГЛОВ

Поля течения основаны на сетке (grid). Грубо говоря, сетка покрывает всю картину. В каждой точке сетки хранится угол. Сетка должна храниться в виде 2D массива чисел с плавающей запятой. Каждая единица в сетке хранит значение угла и одновременно представляет собой точку на сетке.

При созданию сетки надо выбрать ее разрешение. Другими словами, расстояние между точками в сетке. Чем выше разрешение, тем мельче детали, которые вы можете проработать, и плавнее линии. Недостатком является то, что может пострадать функциональность, если увеличите его слишком сильно. Обычно я использую около 0.5% ширины изображения в качестве расстояния между точками. Ещё я использую ту же длину для длины пространства между точками, чтобы упростить расчёты и избежать ошибок точности плавающей запятой.

Последняя настройка, над которой надо подумать - это границы сетки. Вам, наверно, захочется сделать их такими же, как границы самой картина или кадра. Я понял, что лучше делать их ещё больше. Иногда намного больше. Зачем? Если линии выходят за пределы изображения, то это лучше, чем если они просто пропадают. Мне нравится иметь возможность их поворачивать в пределах изображения. Ещё иногда лучше работает, если начинать линии за границами картины и давать им влиться в неё.

Предположим, что перед нами картина 1000 x 1000 пикселей, и мы хотим залить ещё 50% площади вне ее границ. Мы можем установить нашу сетку вот так (псевдокод):

left_x = int(width * -0.5)right_x = int(width * 1.5)top_y = int(height * -0.5)bottom_y = int(height * 1.5) resolution = int(width * 0.01) num_columns = (right_x - left_x) / resolutionnum_rows = (bottom_y - top_y) / resolutiongrid = float[num_columns][num_rows]default_angle = PI * 0.25for (column in num_columns) {    for (row in num_rows) {        grid[column][row] = default_angle    }}

Если бы мы запустили программу для визуализации кода этой сетки в таком виде, то это выглядело бы приблизительно так (качество отрегулировано для лучшей видимости).

Стандартная сетка со всеми углами, установленными на pi* 0.25Стандартная сетка со всеми углами, установленными на pi* 0.25

Теперь у нас есть поле, с которым можно работать. Но к сожалению, пока будут рисоваться только прямые линии. Поработаем над этим. Пока давайте заставим сетку проворачиваться в процессе изменения положения точек на картине.

for (column in num_columns) {     for (row in num_rows) {         angle = (row / float(num_rows)) * PI         grid[column][row] = angle     }}

Это выглядит как-то так:

Изогнутая сеткаИзогнутая сетка

РИСОВАНИЕ КРИВХ ЛИНИЙ ЧЕРЕЗ ПОЛЕ

Теперь мы используем сетку для рисования линий. Вот базовый алгоритм: выбираем начальную точку. Находим подходящую точку рядом на сетке. Берём угол с этой точки на сетке и делаем небольшой шаг в сторону этого угла. На новом месте мы снова делаем поиск и повторяем предыдущие шаги раз за разом. Выглядит это так (псевдокод).

// starting pointx = 500y = 100begin_curve()for (n in [0..num_steps]) {    draw_vertex(x, y)    x_offset = x - left_x    y_offset = y - top_y    column_index = int(x_offset / resolution)    row_index = int(y_offset / resolution)    // ПРИМЕЧАНИЕ: обычно на этом этапе стоит проверить границы    grid_angle = grid[column_index][row_index]    x_step = step_length * cos(grid_angle)    y_step = step_length * sin(grid_angle)    x = x + x_step    y = y + y_step}end_curve()

Если мы это проделаем только для одной кривой, это будет выглядеть как-то так:

Рисование единственной простой кривой на полеРисование единственной простой кривой на поле

Нам нужно выбрать значения для нескольких ключевых параметров для рисования линий: step_length, num_steps, и starting position (x, y). Step_length - самый простой параметр. Как правило, он должен быть настолько мал, чтобы нельзя было увидеть никаких резких углов на кривой линии. Как по мне, он должен быть около 0.1%-0.5% ширины картины. Я делаю больше, если мне нужен более быстрый рендеринг, и меньше, если есть углы, которые надо подкорректировать. Другие переменные требуют больше разъяснений.

num_steps

Значение num_steps повлияет на текстуру результата. Небольшие линии могут выглядеть более пушистыми. Длинные - более жидкими. Вот пример одного и того же кода, выполняемого с разными значениями num_steps. Для начала, с короткими линиями:

С короткими линиямиС короткими линиями

И теперь с длинными:

С длинными линиямиС длинными линиями

Обратите внимание, как резко выглядят линии на первой картине и как плавно на второй. На первой картине можно увидеть отдельные пятна светлых и тёмных оттенков, но все выглядит более системно и уравновешено. На второй картине больше видимых длинных линий, по которым следует взгляд и которые как бы разламывают всю картину.

Следующий вопрос, требующий ответа - собираетесь ли вы смешивать цвета. Короткие линии сохраняют цвет изолировано, отдельно от других, а длинные - вливают цвет в участки другого цвета. Когда я использую много цветов, то обычно выбираю короткие или средние линии, чтобы избежать создания участков, где цвета слишком сильно смешиваются.

Unfenced ExistenceUnfenced ExistenceFragments of ThoughtFragments of Thought

С другой стороны, если я использую близкие цвета, то работа с длинными линиями в самый раз. Посмотрите на задний план: здесь используются лишь едва отличающиеся кремовые цвета.

Loxodography 0.26Loxodography 0.26

starting_point

Все кривые линии должны где-то начинаться. Обычно я использую один из трёх вариантов выбора начальной позиции:

  • Использовать стандартную сетку для начальных позиций

  • Использовать единообразный случайный выбор точек

  • Использовать круговую укладку

  • Стандартная сетка - самый простой вариант, но иногда она может казаться чрезмерно негибкой. Однотипно случайный выбор кажется свободнее, но он сделает некоторые места либо слишком нагромождёнными, либо пустыми, а это не всегда то, что нужно. Подход укладки круга самый сбалансированный: всё достаточно хорошо распределено и с достаточной рандомностью, из-за чего выглядит более расслаблено. Эти различия еле заметны, если рисовать просто длинные линии без цвета или других особенностей:

Стандартная сетка - самый простой вариант, но иногда она может быть слишком негибкой. Единообразно случайный выбор кажется лучше, но он сделает некоторые места либо слишком загромождёнными, либо пустыми, а это не всегда то, что нужно. Подход круговой укладки самый сбалансированный: всё достаточно хорошо распределено и с достаточной рандомностью, из-за чего выглядит более расслаблено. Эти различия еле заметны, если рисовать просто длинные линии без цвета или других особенностей:

Сетка - Случайный выбор - Круговая укладкаСетка - Случайный выбор - Круговая укладка

Но если укоротить линии, разница станет очевидной.

Сетка - Случайный выбор - Круговая укладкаСетка - Случайный выбор - Круговая укладка

Поля течения могут быть очень важны для некоторых дизайнерских решений, поэтому рекомендую изучить эту тему внимательно. Также вам может быть интересно поэкспериментировать с базовыми установками, например, изменить изначальный размер залития картины, начать с краев или середины и т.п.

ДЕФОРМАЦИЯ ВЕКТОРОВ

Важная дизайнерская дилемма: каким образом деформировать векторы в поле. Выбранный способ определит форму искривлений. Определит, будут ли это завитки, резкие повороты или накладывающиеся друг на друга линии.

Шум Перлина

В 90% случаев шум Перлина используется для отстройки векторов. Это удобно и просто, ибо даёт гладкие и продолжительные значения параметров по всей 2D плоскости. Есть ещё разные параметры шума - их множество от значимых до почти не влияющих на итоговую картину. Все это очень легко использовать в Processing. Функция noise() задает значения шума Перлина (между 0,0 и 1,0) с учётом координат.

Вернувшись к коду, мы вместо вставки default_angle можем сделать что-то такое:

for (column in num_columns) {  for (row in num_rows) {      //noise() в // Processing работает лучше всего в середине      // точки примерно 0.005, поэтому уменьшаем до      scaled_x = column * 0.005      scaled_y = row * 0.005      // получаем наше значение шума между 0,0 и 0,1      noise_val = noise(scaled_x, scaled_y)      // перенести значение шума к углу (между 0 0 2 * PI)      angle = map(noise_val, 0.0, 1.0, 0.0, PI * 2.0)      grid[column][row] = angle  }}

Вам нужно будет поиграть с опцией noiseDetail() и с параметрами масштабирования значения шума к углам, чтобы получить нужный вам эффект.

Использование шума Перлина в углахИспользование шума Перлина в углах

Как бы то ни было, я рекомендую придумать собственный способ деформации векторов, а не полагаться на шум Перлина, ибо он слишком явный и массовый. Но есть ещё один инструмент, о котором лучше знать или начинать с него.

Непродолжающиеся деформации

Важный аттрибут для деформации, который вы можете задать - это будет ли деформация продолжающейся или нет. Под продолжающейся я имею в виду плавный переход между соседними векторами, без прыжков Как я уже упоминал, шум Перлина как раз так и работает. У меня есть своя техника деформации, у которой есть это качество, и которую я люблю использовать. Когда вы используете продолжающуюся деформацию, кривые не пересекают друг друга, они плавные и систематизированные. Однако стоит поэкспериментировать ещё и с непродолжающейся деформацией векторов. Простой пример, как это можно сделать, - начать с шума Перлина, но округлить угол каждого вектора до pi/10:

Так мы получим более скульптурные, каменистые формы. Если увеличим до pi/4, то результат станет странным:

Как вариант, можно выбрать случайный угол (между 0 и pi) для каждого ряда векторов:

Или выбрать случайный угол для каждого вектора.

Суть в том, что и непродолжающиеся деформации тоже могут генерировать хорошие штуки.

СОЧЕТАНИЕ С ДРУГИМИ ТЕХНИКАМИ

Существует бесконечное множество способов экспериментов с полями течения и использования их по-новому. Вот несколько вещей, опробованных мною, вам для вдохновения.

Можно установить минимально возможное расстояние между кривыми. На каждой стадии кривой проверяйте, не слишком ли близко другая линия. Если близко, то останавливайтесь. Я использовал эту технику на зеркальном рисунке в 2019 году:

Mirror Removal #5Mirror Removal #5

Можно нарисовать точки на месте продолжающихся деформаций. Если вы настроите проверку и избежите коллизий, то сможете получить что-то крутое:

Side Effects Inclue\dSide Effects Inclue\d

Можно слегка деформировать сетку между циклами рисования. Это немного изменит линии, которые вы получаете, предоставляя вам разнообразие и накладывающиеся друг на друга линии без полного изменения всей картины:

Festival Notes 0.161Festival Notes 0.161

Можно делать переход между соседними линиями для создания контура многоугольника. Если интерполировать между двумя соседями (возможно, с нелинейным ослаблением), то можно получить плавные, прекрасные формы:

Stripes 0.30Stripes 0.30

Можно вставлять объекты, которые деформируют сетку вокруг самих себя. В Ectogenesis я просчитал, как вода будет двигаться и преломляться вокруг объекта.

(Отмечу, что это было сложно)

Суммируя

Это почти всё, что я могу сказать о полях течения. Я думаю, что как и в любой технике, самое важное - понять их от А до Я, а затем расслабиться и делать все по-своему. Просто не используйте шум Перлина, и всё.

Популярные посты по генеративному искусству:

Подробнее..

Из песочницы Основы компьютерной геометрии. Написание простого 3D-рендера

21.09.2020 22:05:33 | Автор: admin
Привет меня зовут Давид, а вот я собственной персоной отрендеренный своим самописным рендером:

image

К сожалению я не смог найти более качественную бесплатную модель, но все равно выражаю благодарность заморскому скульптору запечатлевшему меня в цифре! И как вы уже догадались, речь пойдет о написании CPU рендера.

Идея


С развитием шейдерных языков и увеличением мощностей GPU все больше людей заинтересовались программированием графики. Появились новые направления, такие как например Ray marching со стремительным ростом своей популярности.

В преддверии выхода нового монстра от NVidia я решил написать свою (ламповую и олдскульную) статью про основы рендеринга на CPU. Она является отражением моего личного опыта написания рендера, и в ней я попытаюсь довести понятия и алгоритмы с которыми я столкнулся в процессе кодинга. Стоит понимать, что производительность данного софта будет весьма низкая в силу непригодности процессора для выполнения подобных задач.

Выбор языка изначально падал на c++ или rust, но я остановился на c# из-за простоты написания кода и широких возможностей для оптимизации. Итоговым продуктом данной статьи будет рендер, способный выдавать подобные картинки:

image

image

Все модели, использованные мной здесь, распространяются в открытом доступе, не занимайтесь пиратством и уважайте труд художников!

Математика


Само собой куда же писать рендеры без понимания их математических основ. В этом разделе я изложу только те концепции, которые я использовал в коде. Тем кто не уверен в своих знаниях пропускать данный раздел не советую, без понимания этих основ трудно будет понять дальнейшее изложение. Так же я рассчитываю, что тот кто решил изучать computation geometry будет иметь базовые знания в линейной алгебре, геометрии, а так же тригонометрии(углы, вектора, матрицы, скалярное произведение). Для тех кто хочет понять вычислительную геометрию глубже, могу порекомендовать книгу Е. Никулина Компьютерная геометрия и алгоритмы машинной графики.

Повороты вектора. Матрица поворота


Поворот это одно из основных линейных преобразований векторного пространства. Так же оно является еще и ортогональным преобразованием, так как сохраняет длины преобразованных векторов. В двумерном пространстве существует два типа поворотов:

  • Поворот относительно начала координат
  • Поворот относительно некоторой точки

Здесь я рассмотрю только первый тип, т.к. второй является производным от первого и отличается лишь сменой системы координат вращения (системы координат мы разберем далее).

Давайте выведем формулы для вращения вектора в двумерном пространстве. Обозначим координаты исходного вектора {x, y}. Координаты нового вектора, повернутого на угол f, обозначим как {x y}.

image

Мы знаем, что длина у этих векторов общая и поэтому можем использовать понятия косинуса и синуса для того, чтобы выразить эти вектора через длину и угол относительно оси OX:

image

Заметьте, что мы можем использовать формулы косинуса и синуса суммы для того, чтобы разложить значения x' и y'. Для тех, кто подзабыл я напомню эти формулы:

image

Разложив координаты повернутого вектора через них получим:

image

Здесь нетрудно заметить, что множители l * cos a и l * sin a это координаты исходного вектора: x = l * cos a, y = l * sin a. Заменим их на x и y:

image

Таким образом мы выразили повернутый вектор через координаты исходного вектора и угол его поворота. В виде матрицы это выражение будет выглядеть так:

image

Умножьте и проверьте что результат эквивалентен тому, что мы вывели.

Поворот в трехмерном пространстве


Мы рассмотрели поворот в двумерном пространстве, а так же вывели матрицу для него. Теперь возникает вопрос, а как получить подобные преобразования для трех измерений? В двумерном случае мы вращали вектора на плоскости, здесь же бесконечное количество плоскостей относительно которых мы можем это сделать. Однако существует три базовых типа вращений, при помощи которых можно выразить любой поворот вектора в трехмерном пространстве это XY, XZ, YZ вращения.

XY вращение.

При таком повороте мы вращаем вектор относительно оси OZ координатной системы. Представьте, что вектора это вертолётные лопасти, а ось OZ это мачта на которой они держаться. При XY вращении вектора будут поворачиваться относительно оси OZ, как лопасти вертолета относительно мачты.

image

Заметьте, что при таком вращении z координаты векторов не меняются, а меняются x и x координаты поэтому это и называется XY вращением.

image

Нетрудно вывести и формулы для такого вращения: z координата остается прежней, а x и y изменяются по тем же принципам, что и в 2д вращении.

image

То же в виде матрицы:

image

Для XZ и YZ вращений все аналогично:

image
image

Проекция


Понятие проекции может варьироваться в зависимости от контекста в котором его используют. Многие, наверное, слышали про такие понятия, как проекция на плоскость или проекция на координатную ось.

В том понимании которое мы используем здесь проекция на вектор это тоже вектор. Его координаты точка пересечения перпендикуляра опущенного из вектора a на b с вектором b.

image

Для задания такого вектора нам нужно знать его длину и направление. Как мы знаем прилегающий катет и гипотенуза в прямоугольном треугольнике связаны отношением косинуса, поэтому используем его, чтобы выразить длину вектора проекции:

image

Направление вектора проекции по определению совпадает с вектором b, значит проекция определяется формулой:

image

Здесь мы получаем направление проекции в виде единичного вектора и умножаем его на длину проекции. Несложно понять, что результатом будет как раз-таки то, что мы ищем.

Теперь представим все через скалярное произведение:

image

Получаем удобную формулу для нахождения проекции:

image

Системы координат. Базисы


Многие привыкли работать в стандартной системе координат XYZ, в ней любые 2 оси будут перпендикулярны друг другу, а координатные оси можно представить в виде единичных векторов:

image

На деле же систем координат бесконечное множество, каждая из них является базисом. Базис n-мерного пространства является набором векторов {v1, v2 vn} через которые представляются все вектора этого пространства. При этом ни один вектор из базиса нельзя представить через другие его вектора. По сути каждый базис является отдельной системой координат, в которой вектора будут иметь свои, уникальные координаты.

Давайте разберем, что из себя представляет базис для двумерного пространства. Возьмём для примера всем знакомую декартову систему координат из векторов X {1, 0}, Y {0, 1}, которая является одним из базисов для двумерного пространства:

image


Любой вектор на плоскости можно представить в виде суммы векторов этого базиса с некими коэффициентами или же в виде линейной комбинации. Вспомните, что вы делаете когда записываете координаты вектора вы пишете x координату, а далее y. Таким образом вы на самом деле определяете коэффициенты разложения по векторам базиса.

image


Теперь возьмём другой базис:

image


Через его вектора также можно представить любой 2д вектор:

image


А вот такой набор векторов не является базисом двухмерного пространства:

image


В нем два вектора {1,1} и {2,2} лежат на одной прямой. Какие бы их комбинации вы не брали получать будете только вектора, лежащие на общей прямой y = x. Для наших целей такие дефектные не пригодятся, однако, понимать разницу, я считаю, стоит. По определению все базисы объединяет одно свойство ни один из векторов базиса нельзя представить в виде суммы других векторов базиса с коэффициентами или же ни один вектор базиса не является линейной комбинацией других. Вот пример набора из 3-х векторов который так же не является базисом:

image


Через него можно выразить любой вектор двумерной плоскости, однако вектор {1, 1} в нем является лишним так как сам может быть выражен через вектора {1, 0} и {0,1} как {1,0} + {0,1}.

Вообще любой базис n-мерного пространства будет содержать ровно n векторов, для 2д это n соответственно равно 2.

Перейдем к 3д. Трехмерный базис будет содержать в себе 3 вектора:

image


Если для двумерного базиса достаточно было двух векторов не лежащих на одной прямой, то в трехмерном пространстве набор векторов будет базисом если:

  • 1)2 вектора не лежат на одной прямой
  • 2)3-й не лежит на плоскости образованной двумя другими.


С данного момента базисы, с которыми мы работаем будут ортогональными (любые их вектора перпендикулярны) и нормированными (длина любого вектора базиса 1). Другие нам просто не понадобятся. К примеру стандартный базис

image


удовлетворяет этим критериям.

Переход в другой базис


До сих пор мы записывали разложение вектора как сумму векторов базиса с коэффициентами:

image

Снова рассмотрим стандартный базис вектор {1, 3, 6} в нем можно записать так:

image

Как видите коэффициенты разложения вектора в базисе являются его координатами в этом базисе. Разберем следующий пример:

image


Этот базис получен из стандартного применением к нему XY вращения на 45 градусов. Возьмем вектор a в стандартной системе имеющий координаты {0 ,1, 1}

image


Через вектора нового базиса его можно разложить таким образом:

image


Если вы посчитаете эту сумму, то получите {0, 1, 1} вектор а в стандартном базисе. Исходя из этого выражения в новом базисе вектор а имеет координаты {0.7, 0.7, 1} коэффициенты разложения. Это будет виднее если взглянуть с другого ракурса:

image


Но как находить эти коэффициенты? Вообще универсальный метод это решение довольно сложной системы линейных уравнений. Однако как я сказал ранее использовать мы будем только ортогональные и нормированные базисы, а для них есть весьма читерский способ. Заключается он в нахождении проекций на вектора базиса. Давайте с его помощью найдем разложение вектора a в базисе X{0.7, 0.7, 0} Y{-0.7, 0.7, 0} Z{0, 0, 1}

image


Для начала найдем коэффициент для y. Первым шагом мы находим проекцию вектора a на вектор y (как это делать я разбирал выше):

image


Второй шаг: делим длину найденной проекции на длину вектора y, тем самым мы узнаем сколько векторов y помещается в векторе проекции это число и будет коэффициентом для y, а также y координатой вектора a в новом базисе! Для x и z повторим аналогичные операции:

image


Теперь мы имеем формулы для перехода из стандартного базиса в новый:

image


Ну а так как мы используем только нормированные базисы и длины их векторов равны 1 отпадет необходимость делить на длину вектора в формуле перехода:

image


Раскроем x-координату через формулу проекции:

image


Заметьте, что знаменатель (x', x') и вектор x' в случае нормированного базиса так же равен 1 и их можно отбросить. Получим:

image


Мы видим, что координата x базисе выражается как скалярное произведение (a, x), координата y соответственно как (a, y), координата z (a, z). Теперь можно составить матрицу перехода к новым координатам:

image


Системы координат со смещенным центром


У всех систем координат которые мы рассмотрели выше началом координат была точка {0,0,0}. Помимо этого существуют еще системы со смещенной точкой начала координат:

image


Для того, чтобы перевести вектор в такую систему нужно сначала выразить его относительно нового центра координат. Сделать это просто вычесть из вектора этот центр. Таким образом вы как бы передвигаете саму систему координат к новому центу, при этом вектор остается на месте. Далее можно использовать уже знакомую нам матрицу перехода.

Пишем геометрический движок. Создание проволочного рендера.



Ну вот, думаю тому кто прошел раздел с математикой и не закрыл статью можно промывать мозги более интересными вещами! В этом разделе мы начнем писать основы 3д движка и рендеринга. Вообще рендеринг это довольно сложная процедура, которая включает в себя много разных операций: отсечение невидимых граней, растеризация, расчет света, обработку различных эффектов, материалов(иногда даже физику). Все это мы частично разберем в дальнейшем, а сейчас мы займемся более простыми вещами напишем проволочный рендер. Суть его в том, что он рисует объект в виде линий, соединяющих его вершины, поэтому результат выглядит похожим на сеть из проволок:

image


Полигональная графика


Традиционно в компьютерной графике используется полигональное представление данных трехмерных объектов. Таким образом представляются данные в форматах OBJ, 3DS, FBX и многих других. В компьютере такие данные хранятся в виде двух множеств: множество вершин и множество граней(полигонов). Каждая вершина объекта представлена своей позицией в пространстве вектором, а каждая грань(полигон) представлена тройкой целых чисел которые являются индексами вершин данного объекта. Простейшие объекты(кубы, сферы и т.д.) состоят из таких полигонов и называются примитивами.

В нашем движке примитив будет основным объектом трехмерной геометрии все остальные объекты будут наследоваться от него. Опишем класс примитива:

    abstract class Primitive    {        public Vector3[] Vertices { get; protected set; }        public int[] Indexes { get; protected set; }    }

Пока все просто есть вершины примитива и есть индексы для формирования полигонов. Теперь можно использовать этот класс чтобы создать куб:

   public class Cube : Primitive      {        public Cube(Vector3 center, float sideLen)        {            var d = sideLen / 2;            Vertices = new Vector3[]                {                    new Vector3(center.X - d , center.Y - d, center.Z - d) ,                    new Vector3(center.X - d , center.Y - d, center.Z) ,                    new Vector3(center.X - d , center.Y , center.Z - d) ,                    new Vector3(center.X - d , center.Y , center.Z) ,                    new Vector3(center.X + d , center.Y - d, center.Z - d) ,                    new Vector3(center.X + d , center.Y - d, center.Z) ,                    new Vector3(center.X + d , center.Y + d, center.Z - d) ,                    new Vector3(center.X + d , center.Y + d, center.Z + d) ,                };            Indexes = new int[]                {                    1,2,4 ,                    1,3,4 ,                    1,2,6 ,                    1,5,6 ,                    5,6,8 ,                    5,7,8 ,                    8,4,3 ,                    8,7,3 ,                    4,2,8 ,                    2,8,6 ,                    3,1,7 ,                    1,7,5                };        }    }int Main(){        var cube = new Cube(new Vector3(0, 0, 0), 2);}

image

Реализуем системы координат


Мало задать объект набором полигонов, для планирования и создания сложных сцен необходимо расположить объекты в разных местах, поворачивать их, уменьшать или увеличивать их в размере. Для удобства этих операций используются так называемые локальные и глобальная системы координат. Каждый объект на сцене имеет свои свою собственную систему координат локальную, а так же собственную точку центра.

image

Представление объекта в локальных координатах позволяет легко производить любые операции с ним. Например, для перемещения объекта на вектор a достаточно будет сдвинуть центр его системы координат на этот вектор, для вращения объекта повернуть его локальные координаты.

При работе с объектом мы будем производить операции с его вершинами в локальной системе координат, при рендеринге будем предварительно переводить все объекты сцены в единую систему координат глобальную. Добавим системы координат в код. Для этого создадим объект класса Pivot (стержень, точка опоры) который будет представлять локальный базис объекта и его центральную точку. Перевод точки в систему координат представленную Pivot будет производиться в 2 шага:

  • 1)Представление точки относительно центра новых координат
  • 2)Разложение по векторам нового базиса

Наоборот же, чтобы представить локальную вершину объекта в глобальных координатах необходимо выполнить эти действия в обратном порядке:

  • 1)Разложение по векторам глобального базиса
  • 2)Представление относительно глобального центра

Напишем класс для представления систем координат:

    public class Pivot    {        //точка центра        public Vector3 Center { get; private set; }        //вектора локального базиса - локальные координатные оси        public Vector3 XAxis { get; private set; }        public Vector3 YAxis { get; private set; }        public Vector3 ZAxis { get; private set; }        //Матрица перевода в локальные координаты        public Matrix3x3 LocalCoordsMatrix => new Matrix3x3            (                XAxis.X, YAxis.X, ZAxis.X,                XAxis.Y, YAxis.Y, ZAxis.Y,                XAxis.Z, YAxis.Z, ZAxis.Z            );        //Матрица перевода в глобальные координаты        public Matrix3x3 GlobalCoordsMatrix => new Matrix3x3            (                XAxis.X , XAxis.Y , XAxis.Z,                YAxis.X , YAxis.Y , YAxis.Z,                ZAxis.X , ZAxis.Y , ZAxis.Z            );        public Vector3 ToLocalCoords(Vector3 global)        {            //Находим позицию вектора относительно точки центра и раскладываем в локальном базисе            return LocalCoordsMatrix * (global - Center);        }        public Vector3 ToGlobalCoords(Vector3 local)        {            //В точности да наоборот - раскладываем локальный вектор в глобальном базисе и находим позицию относительно глобального центра            return (GlobalCoordsMatrix * local)  + Center;        }        public void Move(Vector3 v)        {            Center += v;        }        public void Rotate(float angle, Axis axis)        {            XAxis = XAxis.Rotate(angle, axis);            YAxis = YAxis.Rotate(angle, axis);            ZAxis = ZAxis.Rotate(angle, axis);        }    }

Теперь используя данный класс добавим в примитивы функции вращения, передвижения и увеличения:

    public abstract class Primitive    {        //Локальный базис объекта        public Pivot Pivot { get; protected set; }        //Локальные вершины        public Vector3[] LocalVertices { get; protected set; }        //Глобальные вершины        public Vector3[] GlobalVertices { get; protected set; }        //Индексы вершин        public int[] Indexes { get; protected set; }        public void Move(Vector3 v)        {            Pivot.Move(v);            for (int i = 0; i < LocalVertices.Length; i++)                GlobalVertices[i] += v;        }        public void Rotate(float angle, Axis axis)        {            Pivot.Rotate(angle , axis);            for (int i = 0; i < LocalVertices.Length; i++)                GlobalVertices[i] = Pivot.ToGlobalCoords(LocalVertices[i]);        }        public void Scale(float k)        {            for (int i = 0; i < LocalVertices.Length; i++)                LocalVertices[i] *= k;            for (int i = 0; i < LocalVertices.Length; i++)                GlobalVertices[i] = Pivot.ToGlobalCoords(LocalVertices[i]);        }    }

image

Вращение и перемещение объекта с помощью локальных координат

Рисование полигонов. Камера


Основным объектом сцены будет камера с помощью нее объекты будут рисоваться на экране. Камера, как и все объекты сцены, будет иметь локальные координаты в виде объекта класса Pivot через него мы будем двигать и вращать камеру:

image

Для отображения объекта на экране будем использовать немудреный способ перспективной проекции. Принцип на котором основан этом метод заключается в том, что чем дальше от нас расположен объект тем меньше он будет казаться. Наверное многие решали когда-то в школе задачу про измерение высоты дерева находящимся на некотором расстоянии от наблюдателя:

image

Представьте, что луч от верхней точки дерева падает на некую проекционную плоскость находящуюся на расстоянии C1 от наблюдателя и рисует на ней точку. Наблюдатель видит эту точку и хочет по ней определить высоту дерева. Как вы могли заметить высота дерева и высота точки на проекционной плоскости связанны отношением подобных треугольников. Тогда наблюдатель может определить высоту точки используя это отношение:

image


Наоборот же, зная высоту дерева он может найти высоту точки на проекционной плоскости:

image


Теперь вернемся к нашей камере. Представьте, что к оси z координат камеры прикреплена проекционная плоскость на расстоянии z' от начала координат. Формула такой плоскости z = z', ее можно задать одним числом z'. На эту плоскость падают лучи от вершин различных объектов. Попадая на плоскость луч будет оставлять на ней точку. Соединяя такие точки можно нарисовать объект.

image


Такая плоскость будет представлять экран. Координату проекции вершины объекта на экран будем находить в 2 этапа:

  • 1)Переводим вершину в локальные координаты камеры
  • 2)Находим проекцию точки через отношение подобных треугольников

image


Проекция будет 2-мерным вектором, ее координаты x' и y' и будут определять позицию точки на экране компьютера.

Класс камеры 1
public class Camera{    //локальные координаты камеры    public Pivot Pivot { get; private set; }    //расстояние до проекционной плоскости    public float ScreenDist { get; private set; }    public Camera(Vector3 center, float screenDist)    {        Pivot = new Pivot(center);        ScreenDist = screenDist;    }    public void Move(Vector3 v)    {        Pivot.Move(v);    }    public void Rotate(float angle, Axis axis)    {        Pivot.Rotate(angle, axis);    }    public Vector2 ScreenProection(Vector3 v)    {        var local = Pivot.ToLocalCoords(v);        //через подобные треугольники находим проекцию        var delta = ScreenDist / local.Z;        var proection = new Vector2(local.X, local.Y) * delta;        return proection;    }}


Данный код имеет несколько ошибок, о исправлении которых мы поговорим далее.

Отсекаем невидимые полигоны


Спроецировав таким образом на экран три точки полигона мы получим координаты треугольника который соответствует отображению полигона на экране. Но таким образом камера будет обрабатывать любые вершины, включая те, чьи проекции выходят за область экрана, если попытаться нарисовать такую вершину велика вероятность словить ошибок. Камера так же будет обрабатывать полигоны которые находятся позади нее (координаты z их точек в локальном базисе камеры меньше z') такое затылковое зрение нам тоже ни к чему.

image


Для отсечения невидимых вершин в open gl используются метод усекающей пирамиды. Заключается он в задании двух плоскостей ближней(near plane) и дальней(far plane). Все, что лежит между этими двумя плоскостями будет подлежать дальнейшей обработке. Я же использую упрощенный вариант с одной усекающей плоскостью z'. Все вершины, лежащие позади нее будут невидимыми.

Добавим в камеру два новых поля ширину и высоту экрана.
Теперь каждую спроецированную точку будем проверять на попадание в область экрана. Так же отсечем точки позади камеры. Если точка лежит сзади или ее проекция не попадает на экран то метод вернет точку {float.NaN, float.NaN}.

Код камеры 2
public Vector2 ScreenProection(Vector3 v){    var local = Pivot.ToLocalCoords(v);    //игнорируем точки сзади камеры    if (local.Z < ScreenDist)    {        return new Vector2(float.NaN, float.NaN);    }    //через подобные треугольники находим проекцию    var delta = ScreenDist / local.Z;    var proection = new Vector2(local.X, local.Y) * delta;    //если точка принадлежит экранной области - вернем ее    if (proection.X >= 0 && proection.X < ScreenWidth && proection.Y >= 0 && proection.Y < ScreenHeight)    {        return proection;    }    return new Vector2(float.NaN, float.NaN);}


Переводим в экранные координаты


Здесь я разъясню некоторый момент. Cвязан он с тем, что во многих графических библиотеках рисование происходит в экранной системе координат, в таких координатах начало это верхняя левая точка экрана, x увеличивается при движении вправо, а y при движении вниз. В нашей проекционной плоскости точки представлены в обычных декартовых координатах и перед отрисовкой необходимо переводить эти координаты в экранные. Сделать это нетрудно, нужно только сместить начало координат в верхний левый угол и инвертировать y:

image


Код камеры 3
public Vector2 ScreenProection(Vector3 v){    var local = Pivot.ToLocalCoords(v);    //игнорируем точки сзади камеры    if (local.Z < ScreenDist)    {        return new Vector2(float.NaN, float.NaN);    }    //через подобные треугольники находим проекцию    var delta = ScreenDist / local.Z;    var proection = new Vector2(local.X, local.Y) * delta;    //этот код нужен для перевода проекции в экранные координаты    var screen = proection + new Vector2(ScreenWidth / 2, -ScreenHeight / 2);    var screenCoords = new Vector2(screen.X, -screen.Y);    //если точка принадлежит экранной области - вернем ее    if (screenCoords.X >= 0 && screenCoords.X < ScreenWidth && screenCoords.Y >= 0 && screenCoords.Y < ScreenHeight)    {        return screenCoords;    }    return new Vector2(float.NaN, float.NaN);}


Корректируем размер спроецированного изображения


Если вы используете предыдущий код для того, чтобы нарисовать объект то получите что-то вроде этого:

image


Почему то все объекты рисуются очень маленькими. Для того, чтобы понять причину вспомните как мы вычисляли проекцию умножали x и y координаты на дельту отношения z' / z. Это значит, что размер объекта на экране зависит от расстояния до проекционной плоскости z'. А ведь z' мы можем задать сколь угодно маленьким значением. Значит нам нужно корректировать размер проекции в зависимости от текущего значения z'. Для этого добавим в камеру еще одно поле угол ее обзора.

image


Он нам нужен для сопоставления углового размера экрана с его шириной. Угол будет сопоставлен с шириной экрана таким образом: максимальный угол в пределах которого смотрит камера это левый или правый край экрана. Тогда максимальный угол от оси z камеры составляет o / 2. Проекция, которая попала на правый край экрана должна иметь координату x = width / 2, а на левый: x = -width / 2. Зная это выведем формулу для нахождения коэффициента растяжения проекции:

image


Код камеры 4
public float ObserveRange { get; private set; }public float Scale => ScreenWidth / (float)(2 * ScreenDist * Math.Tan(ObserveRange / 2));public Vector2 ScreenProection(Vector3 v){    var local = Pivot.ToLocalCoords(v);    //игнорируем точки сзади камеры    if (local.Z < ScreenDist)    {        return new Vector2(float.NaN, float.NaN);    }    //через подобные треугольники находим проекцию и умножаем ее на коэффициент растяжения    var delta = ScreenDist / local.Z * Scale;    var proection = new Vector2(local.X, local.Y) * delta;    //этот код нужен для перевода проекции в экранные координаты    var screen = proection + new Vector2(ScreenWidth / 2, -ScreenHeight / 2);    var screenCoords = new Vector2(screen.X, -screen.Y);    //если точка принадлежит экранной области - вернем ее    if (screenCoords.X >= 0 && screenCoords.X < ScreenWidth && screenCoords.Y >= 0 && screenCoords.Y < ScreenHeight)    {        return screenCoords;    }    return new Vector2(float.NaN, float.NaN);}


Вот такой простой код отрисовки я использовал для теста:

Код рисования объектов
public DrawObject(Primitive primitive , Camera camera){    for (int i = 0; i < primitive.Indexes.Length; i+=3)    {        var color = randomColor();        // индексы вершин полигона        var i1 = primitive.Indexes[i];        var i2 = primitive.Indexes[i+ 1];        var i3 = primitive.Indexes[i+ 2];        // вершины полигона        var v1 = primitive.GlobalVertices[i1];        var v2 = primitive.GlobalVertices[i2];        var v3 = primitive.GlobalVertices[i3];        // рисуем полигон        DrawPolygon(v1,v2,v3 , camera , color);    }}public void DrawPolygon(Vector3 v1, Vector3 v2, Vector3 v3, Camera camera , color){    //проекции вершин    var p1 = camera.ScreenProection(v1);    var p2 = camera.ScreenProection(v2);    var p3 = camera.ScreenProection(v3);    //рисуем полигон    DrawLine(p1, p2 , color);    DrawLine(p2, p3 , color);    DrawLine(p3, p2 , color);}


Давайте проверим рендер на сцене и кубов:

image


И да, все прекрасно работает. Для тех, кому разноцветные кубики не кажутся пафосными я написал функцию парсинга моделей формата OBJ в объекты типа Primitive, залил фон черным и отрисовал несколько моделей:

Результат работы рендера

image

image


Растеризация полигонов. Наводим красоту.



В прошлом разделе мы написали проволочный рендер. Теперь мы займемся его модернизацией реализуем растеризацию полигонов.

По простому растеризировать полигон это значит закрасить его. Казалось бы зачем писать велосипед, когда есть уже готовые функции растеризации треугольника. Вот что будет если нарисовать все дефолтными инструментами:

image


Современное искусство, полигоны сзади нарисовались поверх передних, одним словом каша. К тому же как таким образом текстурировать объекты? Да, никак. Значит нам нужно написать свой имба-растерайзер, который будет уметь в отсечение невидимых точек, текстуры и даже в шейдеры! Но для того чтобы это сделать стоит понять как вообще красить треугольники.

Алгоритм Брезенхема для рисования линии.


Начнем с линий. Если кто не знал алгоритм Брезенхема это основной алгоритм рисования прямых в компьютерной графике. Он или его модификации используется буквально везде: рисование прямых, отрезков, окружностей и т.п. Кому интересно более подробное описание читайте вики. Алгоритм Брезенхема

Имеется отрезок соединяющий точки {x1, y1} и {x2, y2}. Чтобы нарисовать отрезок между ними нужно закрасить все пиксели которые попадают на него. Для двух точек отрезка можно найти x-координаты пикселей в которых они лежат: нужно лишь взять целые части от координат x1 и x2. Чтобы закрасить пиксели на отрезке запускаем цикл от x1 до x2 и на каждой итерации вычисляем y координату пикселя который попадает на прямую. Вот код:

void Brezenkhem(Vector2 p1 , Vector2 p2){    int x1 = Floor(p1.X);    int x2 = Floor(p2.X);    if (x1 > x2) {Swap(x1, x2); Swap(p1 , p2);}    float d = (p2.Y - p1.Y) / (x2 - x1);    float y = p1.Y;    for (int i = x1; i <= x2; i++)    {        int pixelY = Floor(y);        FillPixel(i , pixelY);        y += d;    }}

image

Картинка из вики

Растеризация треугольника. Алгоритм заливки


Линии рисовать мы умеем, а вот с треугольниками будет чуть посложнее(не намного)! Задача рисования треугольника сводится к нескольким задачам рисования линий. Для начала разобьем треугольник на две части предварительно отсортировав точки в порядке возрастания x:

image


Заметьте теперь у нас есть две части в которых явно выражены нижняя и верхняя границы. все что осталось это залить все пиксели находящиеся между ними! Сделать это можно в 2 цикла: от x1 до x2 и от x3 до x2.

void Triangle(Vector2 v1 , Vector2 v2 , Vector2 v3){    //хардкодим BubbleSort для упорядочивания по x    if (v1.X > v2.X) { Swap(v1, v2); }    if (v2.X > v3.X) { Swap(v2, v3); }    if (v1.X > v2.X) { Swap(v1, v2); }    //узнаем на сколько увеличивается y границ при увеличении x    //избегаем деления на 0: если x1 == x2 значит эта часть треугольника - линия    var steps12 = max(v2.X - v1.X , 1);    var steps13 = max(v3.X - v1.X , 1);    var upDelta = (v2.Y - v1.Y) / steps12;    var downDelta = (v3.Y - v1.Y) / steps13;    //верхняя граница должна быть выше нижней    if (upDelta < downDelta) Swap(upDelta , downDelta);    //изначально у координаты границ равны y1    var up = v1.Y;    var down = v1.Y;    for (int i = (int)v1.X; i <= (int)v2.X; i++)    {        for (int g = (int)down; g <= (int)up; g++)        {            FillPixel(i , g);        }        up += upDelta;        down += downDelta;    }    //все то же самое для другой части треугольника    var steps32 = max(v2.X - v3.X , 1);    var steps31 = max(v1.X - v3.X , 1);    upDelta = (v2.Y - v3.Y) / steps32;    downDelta = (v1.Y - v3.Y) / steps31;    if (upDelta < downDelta) Swap(upDelta, downDelta);    up = v3.Y;    down = v3.Y;    for (int i = (int)v3.X; i >=(int)v2.X; i--)    {        for (int g = (int)down; g <= (int)up; g++)        {            FillPixel(i, g);        }        up += upDelta;        down += downDelta;    }}

Несомненно этот код можно отрефакторить и не дублировать цикл:

void Triangle(Vector2 v1 , Vector2 v2 , Vector2 v3){    if (v1.X > v2.X) { Swap(v1, v2); }    if (v2.X > v3.X) { Swap(v2, v3); }    if (v1.X > v2.X) { Swap(v1, v2); }    var steps12 = max(v2.X - v1.X , 1);    var steps13 = max(v3.X - v1.X , 1);    var steps32 = max(v2.X - v3.X , 1);    var steps31 = max(v1.X - v3.X , 1);    var upDelta = (v2.Y - v1.Y) / steps12;    var downDelta = (v3.Y - v1.Y) / steps13;    if (upDelta < downDelta) Swap(upDelta , downDelta);    TrianglePart(v1.X , v2.X , v1.Y , upDelta , downDelta);    upDelta = (v2.Y - v3.Y) / steps32;    downDelta = (v1.Y - v3.Y) / steps31;    if (upDelta < downDelta) Swap(upDelta, downDelta);    TrianglePart(v3.X, v2.X, v3.Y, upDelta, downDelta);}void TrianglePart(float x1 , float x2 , float y1  , float upDelta , float downDelta){    float up = y1, down = y1;    for (int i = (int)x1; i <= (int)x2; i++)    {        for (int g = (int)down; g <= (int)up; g++)        {            FillPixel(i , g);        }        up += upDelta; down += downDelta;    }}

Отсечение невидимых точек.


Для начала подумайте каким образом вы видите. Сейчас перед вами экран, а то что находится позади него скрыто от ваших глаз. В рендеринге работает примерно такой же механизм если один полигон перекрывает другой рендер нарисует его поверх перекрытого. Наоборот же, закрытую часть полигона рисовать он не будет:

image


Для того, чтобы понять видима точки или нет, в рендеринге применяют механизм zbuffer-а(буфера глубины). zbuffer можно представить как двумерный массив (можно сжать в одномерный) с размерностью width * height. Для каждого пикселя на экране он хранит значение z координаты на исходном полигоне откуда эта точка была спроецирована. Соответственно чем ближе точка к наблюдателю, тем меньше ее z координата. В конечном итоге если проекции нескольких точек совпадают растеризировать нужно точку с минимальной z координатой:

image


Теперь возникает вопрос как находить z-координаты точек на исходном полигоне? Это можно сделать несколькими способами. Например можно пускать луч из начала координат камеры, проходящий через точку на проекционной плоскости {x, y, z'}, и находить его пересечение с полигоном. Но искать пересечения крайне затратная операция, поэтому будем использовать другой способ. Для рисования треугольника мы интерполировали координаты его проекций, теперь, помимо этого, мы будем интерполировать также и координаты исходного полигона. Для отсечения невидимых точек будем использовать в методе растеризации состояние zbuffer-а для текущего фрейма.

Мой zbuffer будет иметь вид Vector3[] он будет содержать не только z координаты, но и интерполированные значения точек полигона(фрагменты) для каждого пикселя экрана. Это сделано в целях экономии памяти так как в дальнейшем нам все равно пригодятся эти значения для написания шейдеров! А пока что имеем следующий код для определения видимых вершин(фрагментов):

Код
public void ComputePoly(Vector3 v1, Vector3 v2, Vector3 v3 , Vector3[] zbuffer){    //находим проекцию полигона    var v1p = Camera.ScreenProection(v1);    var v2p = Camera.ScreenProection(v2);    var v3p = Camera.ScreenProection(v3);    //упорядочиваем точки по x - координате    //Заметьте, также меняем исходные точки - они должны соответствовать проекциям    if (v1p.X > v2p.X) { Swap(v1p, v2p); Swap(v1p, v2p); }    if (v2p.X > v3p.X) { Swap(v2p, v3p); Swap(v2p, v3p); }    if (v1p.X > v2p.X) { Swap(v1p, v2p); Swap(v1p, v2p); }    //считаем количество шагов для построения линии алгоритмом Брезенхема    int x12 = Math.Max((int)v2p.X - (int)v1p.X, 1);    int x13 = Math.Max((int)v3p.X - (int)v1p.X, 1);    //теперь помимо проекций будем интерполировать и исходные точки    float dy12 = (v2p.Y - v1p.Y) / x12; var dr12 = (v2 - v1) / x12;    float dy13 = (v3p.Y - v1p.Y) / x13; var dr13 = (v3 - v1) / x13;    Vector3 deltaUp, deltaDown; float deltaUpY, deltaDownY;    if (dy12 > dy13) { deltaUp = dr12; deltaDown = dr13; deltaUpY = dy12; deltaDownY = dy13;}    else { deltaUp = dr13; deltaDown = dr12; deltaUpY = dy13; deltaDownY = dy12;}    TrianglePart(v1 , deltaUp , deltaDown , x12 , 1 , v1p , deltaUpY , deltaDownY , zbuffer);    //вторую часть треугольника аналогично - думаю вы поняли}public void ComputePolyPart(Vector3 start, Vector3 deltaUp, Vector3 deltaDown,    int xSteps, int xDir, Vector2 pixelStart, float deltaUpPixel, float deltaDownPixel , Vector3[] zbuffer){    int pixelStartX = (int)pixelStart.X;    Vector3 up = start - deltaUp, down = start - deltaDown;    float pixelUp = pixelStart.Y - deltaUpPixel, pixelDown = pixelStart.Y - deltaDownPixel;    for (int i = 0; i <= xSteps; i++)    {        up += deltaUp; pixelUp += deltaUpPixel;        down += deltaDown; pixelDown += deltaDownPixel;        int steps = ((int)pixelUp - (int)pixelDown);        var delta = steps == 0 ? Vector3.Zero : (up - down) / steps;        Vector3 position = down - delta;        for (int g = 0; g <= steps; g++)        {            position += delta;            var proection = new Point(pixelStartX + i * xDir, (int)pixelDown + g);            int index = proection.Y * Width + proection.X;            //проверка на глубину            if (zbuffer[index].Z == 0 || zbuffer[index].Z > position.Z)            {                zbuffer[index] = position;            }        }    }}


image

Анимация шагов растеризатора(при перезаписи глубины в zbuffer-е пиксель выделяется красным):

Для удобства я вынес весь код в отдельный модуль Rasterizer:

Класс растеризатора
    public class Rasterizer    {        public Vertex[] ZBuffer;        public int[] VisibleIndexes;        public int VisibleCount;        public int Width;        public int Height;        public Camera Camera;        public Rasterizer(Camera camera)        {            Shaders = shaders;            Width = camera.ScreenWidth;            Height = camera.ScreenHeight;            Camera = camera;        }        public Bitmap Rasterize(IEnumerable<Primitive> primitives)        {            var buffer = new Bitmap(Width , Height);            ComputeVisibleVertices(primitives);            for (int i = 0; i < VisibleCount; i++)            {                var vec = ZBuffer[index];                var proec = Camera.ScreenProection(vec);                buffer.SetPixel(proec.X , proec.Y);            }            return buffer.Bitmap;        }        public void ComputeVisibleVertices(IEnumerable<Primitive> primitives)        {            VisibleCount = 0;            VisibleIndexes = new int[Width * Height];            ZBuffer = new Vertex[Width * Height];            foreach (var prim in primitives)            {                foreach (var poly in prim.GetPolys())                {                    MakeLocal(poly);                    ComputePoly(poly.Item1, poly.Item2, poly.Item3);                }            }        }        public void MakeLocal(Poly poly)        {            poly.Item1.Position = Camera.Pivot.ToLocalCoords(poly.Item1.Position);            poly.Item2.Position = Camera.Pivot.ToLocalCoords(poly.Item2.Position);            poly.Item3.Position = Camera.Pivot.ToLocalCoords(poly.Item3.Position);        }    }


Теперь проверим работу рендера. Для этого я использую модель Сильваны из известной RPG WOW:

image


Не очень понятно, правда? А все потому что здесь нет ни текстур ни освещения. Но вскоре мы это исправим.

Текстуры! Нормали! Освещение! Мотор!


Почему я объединил все это в один раздел? А потому что по своей сути текстуризация и расчет нормалей абсолютно идентичны и скоро вы это поймете.

Для начала рассмотрим задачу текстуризации для одного полигона. Теперь помимо обычных координат вершин полигона мы будем хранить еще и его текстурные координаты. Текстурная координата вершины представляется двумерным вектором и указывает на пиксель изображения текстуры. В интернете я нашел хорошую картинку чтобы показать это:

image

Заметьте, что начало текстуры (левый нижний пиксель) в текстурных координатах имеет значение {0, 0}, конец (правый верхний пиксель) {1, 1}. Учитывайте систему координат текстуры и возможность выхода за границы картинки когда текстурная координата равна 1.

Сразу создадим класс для представления данных вершины:

  public class Vertex    {        public Vector3 Position { get; set; }        public Color Color { get; set; }        public Vector2 TextureCoord { get; set; }        public Vector3 Normal { get; set; }        public Vertex(Vector3 pos , Color color , Vector2 texCoord , Vector3 normal)        {            Position = pos;            Color = color;            TextureCoord = texCoord;            Normal = normal;        }    }

Зачем нужны нормали я объясню позже, пока что просто будем знать, что у вершин они могут быть. Теперь для текстуризации полигона нам необходимо каким-то образом сопоставить значение цвета из текстуры конкретному пикселю. Помните как мы интерполировали вершины? Здесь нужно сделать то же самое! Я не буду еще раз переписывать код растеризации, а предлагаю вам самим реализовать текстурирование в вашем рендере. Результатом должно быть корректное отображение текстур на модели. Вот, что получилось у меня:

текстурированная модель
image


Вся информация о текстурных координатах модели находятся в файле OBJ. Для того, чтобы использовать это изучите формат: Формат OBJ.

Освещение



С текстурами все стало гораздо веселее, но по настоящему весело будет когда мы реализуем освещение для сцены. Для имитации дешевого освещения я буду использовать модель Фонга.

Модель Фонга


В общем случае этот метод имитирует наличие 3х составляющих освещения: фоновая(ambient), рассеянная(diffuse) и зеркальная(reflect). Сумма этих трех компонент в итоге даст имитацию физического поведения света.

image

Модель Фонга

Для расчета освещения по Фонгу нам будут нужны нормали к поверхностям, для этого я и добавил их в классе Vertex. Где же брать значения этих нормалей? Нет, ничего вычислять нам не нужно. Дело в том, что великодушные 3д редакторы часто сами считают их и предоставляют вместе с данными модели в контексте формата OBJ. Распарсив файл модели мы получаем значение нормалей для 3х вершин каждого полигона.

image

Картинка из вики

Для того, чтобы посчитать нормаль в каждой точке на полигоне нужно интерполировать эти значения, мы уже умеем делать это. Теперь разберем все составляющие для вычисления освещения Фонга.

Фоновый свет (Ambient)


Изначально мы задаем постоянное фоновое освещение, для нетекстурированных объектов можно выбрать любой цвет, для объектов с текстурами я делю каждую из компонент RGB на некий коэффициент базового затенения (baseShading).

Рассеянный свет (Diffuse)


Когда свет падает на поверхность полигона он равномерно рассеивается. Для расчета diffuse значения на конкретном пикселе учитывается угол под которым свет падает на поверхность. Чтобы рассчитать этот угол можно применить скалярное произведение падающего луча и нормали(само собой вектора перед этим нужно нормализировать). Этот угол будет умножаться на некий коэффициент интенсивности света. Если скалярное произведение отрицательно это значит, что угол между векторами больше 90 градусов. В этом случае мы начнем рассчитывать уже не осветление, а, наоборот, затенение. Стоит избегать этого момента, сделать это можно с помощью функции max.

Код
public interface IShader    {        void ComputeShader(Vertex vertex, Camera camera);    }    public struct Light    {        public Vector3 Pos;        public float Intensivity;    }public class PhongModelShader : IShader    {        public static float DiffuseCoef = 0.1f;        public Light[] Lights { get; set; }        public PhongModelShader(params Light[] lights)        {            Lights = lights;        }        public void ComputeShader(Vertex vertex, Camera camera)        {            if (vertex.Normal.X == 0 && vertex.Normal.Y == 0 && vertex.Normal.Z == 0)            {                return;            }            var gPos = camera.Pivot.ToGlobalCoords(vertex.Position);            foreach (var light in Lights)            {                var ldir = Vector3.Normalize(light.Pos - gPos);                var diffuseVal = Math.Max(VectorMath.Cross(ldir, vertex.Normal), 0) * light.Intensivity;                vertex.Color = Color.FromArgb(vertex.Color.A,                    (int)Math.Min(255, vertex.Color.R * diffuseVal * DiffuseCoef),                    (int)Math.Min(255, vertex.Color.G * diffuseVal * DiffuseCoef,                    (int)Math.Min(255, vertex.Color.B * diffuseVal * DiffuseCoef));            }        }    }


Давайте применим рассеянный свет и рассеем тьму:

image

Зеркальный свет (Reflect)


Для расчета зеркальной компоненты нужно учитывать точку из которой мы смотрим на объект. Теперь мы будем брать скалярное произведение луча от наблюдателя и отраженного от поверхности луча умноженное на коэффициент интенсивности света.

image

Найти луч от наблюдателя к поверхности легко это будет просто позиция обрабатываемой вершины в локальных координатах. Для того, чтобы найти отраженный луч я использовал следующий способ. Падающий луч можно разложить на 2 вектора: его проекцию на нормаль и второй вектор который можно найти вычитанием из падающего луча этой проекции. Чтобы найти отраженный луч нужно из проекции на нормаль вычесть значение второго вектора.

код
    public class PhongModelShader : IShader    {        public static float DiffuseCoef = 0.1f;        public static float ReflectCoef = 0.2f;        public Light[] Lights { get; set; }        public PhongModelShader(params Light[] lights)        {            Lights = lights;        }        public void ComputeShader(Vertex vertex, Camera camera)        {            if (vertex.Normal.X == 0 && vertex.Normal.Y == 0 && vertex.Normal.Z == 0)            {                return;            }            var gPos = camera.Pivot.ToGlobalCoords(vertex.Position);            foreach (var light in Lights)            {                var ldir = Vector3.Normalize(light.Pos - gPos);                //Следующие три строчки нужны чтобы найти отраженный от поверхности луч                var proection = VectorMath.Proection(ldir, -vertex.Normal);                var d = ldir - proection;                var reflect = proection - d;                var diffuseVal = Math.Max(VectorMath.Cross(ldir, -vertex.Normal), 0) * light.Intensivity;                //луч от наблюдателя                var eye = Vector3.Normalize(-vertex.Position);                var reflectVal = Math.Max(VectorMath.Cross(reflect, eye), 0) * light.Intensivity;                var total = diffuseVal * DiffuseCoef + reflectVal * ReflectCoef;                vertex.Color = Color.FromArgb(vertex.Color.A,                    (int)Math.Min(255, vertex.Color.R * total),                    (int)Math.Min(255, vertex.Color.G * total),                    (int)Math.Min(255, vertex.Color.B * total));            }        }    }


Теперь картинка выглядит следующим образом:

image


Тени


Конечной точкой моего изложения будет реализация теней для рендера. Первая тупиковая идея которая зародилась у меня в черепушке для каждой точки проверять не лежит ли между ней и светом какой-нибудь полигон. Если лежит значит не нужно освещать пиксель. Модель Сильваны содержит 220к с лихвой полигонов. Если так для каждой точки проверять пересечение со всеми этими полигонами, то нужно сделать максимум 220000 * 1920 * 1080 * 219999 вызовов метода пересечения! За 10 минут мой компьютер смог осилить 10-у часть всех вычислений (2600 полигонов из 220000), после чего у меня случился сдвиг и я отправился на поиски нового метода.

В интернете мне попался очень простой и красивый способ, который выполняет те же вычисления в тысячи раз быстрее. Называется он Shadow mapping(построение карты теней). Вспомните как мы определяли видимые наблюдателю точки использовали zbuffer. Shadow mapping делает тоже самое! В первом проходе наша камера будет находиться в позиции света и смотреть на объект. Таким образом мы сформируем карту глубин для источника света. Карта глубин это знакомый нам zbuffer. Во втором проходе мы используем эту карту, чтобы определять вершины которые должны освещаться. Сейчас я нарушу правила хорошего кода и пойду читерским путем просто передам шейдеру новый объект растеризатора и он используя его создаст нам карту глубин.

Код
public class ShadowMappingShader : IShader{    public Enviroment Enviroment { get; set; }    public Rasterizer Rasterizer { get; set; }    public Camera Camera => Rasterizer.Camera;    public Pivot Pivot => Camera.Pivot;    public Vertex[] ZBuffer => Rasterizer.ZBuffer;    public float LightIntensivity { get; set; }    public ShadowMappingShader(Enviroment enviroment, Rasterizer rasterizer, float lightIntensivity)    {        Enviroment = enviroment;        LightIntensivity = lightIntensivity;        Rasterizer = rasterizer;        //я добвил события в объекты рендера, привязав к ним перерасчет карты теней        //теперь при вращении/движении камеры либо при изменение сцены шейдер будет перезаписывать глубину        Camera.OnRotate += () => UpdateDepthMap(Enviroment.Primitives);        Camera.OnMove += () => UpdateDepthMap(Enviroment.Primitives);        Enviroment.OnChange += () => UpdateDepthMap(Enviroment.Primitives);        UpdateVisible(Enviroment.Primitives);    }    public void ComputeShader(Vertex vertex, Camera camera)    {        //вычисляем глобальные координаты вершины        var gPos = camera.Pivot.ToGlobalCoords(vertex.Position);        //дистанция до света        var lghDir = Pivot.Center - gPos;        var distance = lghDir.Length();        var local = Pivot.ToLocalCoords(gPos);        var proectToLight = Camera.ScreenProection(local).ToPoint();        if (proectToLight.X >= 0 && proectToLight.X < Camera.ScreenWidth && proectToLight.Y >= 0            && proectToLight.Y < Camera.ScreenHeight)        {            int index = proectToLight.Y * Camera.ScreenWidth + proectToLight.X;            if (ZBuffer[index] == null || ZBuffer[index].Position.Z >= local.Z)            {                vertex.Color = Color.FromArgb(vertex.Color.A,                    (int)Math.Min(255, vertex.Color.R + LightIntensivity / distance),                    (int)Math.Min(255, vertex.Color.G + LightIntensivity / distance),                    (int)Math.Min(255, vertex.Color.B + LightIntensivity / distance));            }        }        else        {            vertex.Color = Color.FromArgb(vertex.Color.A,                    (int)Math.Min(255, vertex.Color.R + (LightIntensivity / distance) / 15),                    (int)Math.Min(255, vertex.Color.G + (LightIntensivity / distance) / 15),                    (int)Math.Min(255, vertex.Color.B + (LightIntensivity / distance) / 15));        }    }    public void UpdateDepthMap(IEnumerable<Primitive> primitives)    {        Rasterizer.ComputeVisibleVertices(primitives);    }}


Для статичной сцены достаточно будет один раз вызвать построение карты глубин, после во всех фреймах использовать ее. В качестве тестовой я использую менее полигональную модель пушки. Вот такое изображение получается на выходе:

image


Многие из вас наверное заметили артефакты данного шейдера(необработанные светом черные точки). Опять же обратившись в всезнающую сеть я нашел описание этого эффекта с противным названием shadow acne(да простят меня люди с комплексом внешности). Суть таких зазоров заключается в том, что для определения тени мы используем ограниченное разрешение карты глубин. Это значит, что несколько вершин при рендеринге получают одно значение из карты глубин. Такому артефакту наиболее подвержены поверхности на которые свет падает под пологим углом. Эффект можно исправить, увеличив разрешение рендера для света, однако существует более элегантный способ. Заключается он в том, чтобы добавлять определенный сдвиг для глубины в зависимости от угла между лучом света и поверхностью. Это можно сделать при помощи скалярного произведения.

Улучшенные тени
public class ShadowMappingShader : IShader{    public Enviroment Enviroment { get; set; }    public Rasterizer Rasterizer { get; set; }    public Camera Camera => Rasterizer.Camera;    public Pivot Pivot => Camera.Pivot;    public Vertex[] ZBuffer => Rasterizer.ZBuffer;    public float LightIntensivity { get; set; }    public ShadowMappingShader(Enviroment enviroment, Rasterizer rasterizer, float lightIntensivity)    {        Enviroment = enviroment;        LightIntensivity = lightIntensivity;        Rasterizer = rasterizer;        //я добвил события в объекты рендера, привязав к ним перерасчет карты теней        //теперь при вращении/движении камеры либо при изменение сцены шейдер будет перезаписывать глубину        Camera.OnRotate += () => UpdateDepthMap(Enviroment.Primitives);        Camera.OnMove += () => UpdateDepthMap(Enviroment.Primitives);        Enviroment.OnChange += () => UpdateDepthMap(Enviroment.Primitives);        UpdateVisible(Enviroment.Primitives);    }    public void ComputeShader(Vertex vertex, Camera camera)    {        //вычисляем глобальные координаты вершины        var gPos = camera.Pivot.ToGlobalCoords(vertex.Position);        //дистанция до света        var lghDir = Pivot.Center - gPos;        var distance = lghDir.Length();        var local = Pivot.ToLocalCoords(gPos);        var proectToLight = Camera.ScreenProection(local).ToPoint();        if (proectToLight.X >= 0 && proectToLight.X < Camera.ScreenWidth && proectToLight.Y >= 0            && proectToLight.Y < Camera.ScreenHeight)        {            int index = proectToLight.Y * Camera.ScreenWidth + proectToLight.X;            var n = Vector3.Normalize(vertex.Normal);            var ld = Vector3.Normalize(lghDir);            //вычисляем сдвиг глубины            float bias = (float)Math.Max(10 * (1.0 - VectorMath.Cross(n, ld)), 0.05);            if (ZBuffer[index] == null || ZBuffer[index].Position.Z + bias >= local.Z)            {                vertex.Color = Color.FromArgb(vertex.Color.A,                    (int)Math.Min(255, vertex.Color.R + LightIntensivity / distance),                    (int)Math.Min(255, vertex.Color.G + LightIntensivity / distance),                    (int)Math.Min(255, vertex.Color.B + LightIntensivity / distance));            }        }        else        {            vertex.Color = Color.FromArgb(vertex.Color.A,                    (int)Math.Min(255, vertex.Color.R + (LightIntensivity / distance) / 15),                    (int)Math.Min(255, vertex.Color.G + (LightIntensivity / distance) / 15),                    (int)Math.Min(255, vertex.Color.B + (LightIntensivity / distance) / 15));        }    }    public void UpdateDepthMap(IEnumerable<Primitive> primitives)    {        Rasterizer.ComputeVisibleVertices(primitives);    }}

image


Бонус

Играем с нормалями


Я подумал, стоит ли интерполировать значения нормалей, если можно посчитать среднее между 3мя нормалями полигона и использовать для каждой его точки. Оказывается, что интерполяция дает куда более естественный и гладкий материал картинки.

image


Двигаем свет


Реализовав простой цикл получим набор отрендеренных картинок с разными позициями света на сцене:

            float angle = (float)Math.PI / 90;            var shader = (preparer.Shaders[0] as PhongModelShader);            for (int i = 0; i < 180; i+=2)            {                shader.Lights[0] = = new Light()                    {                        Pos = shader.Lights[0].Pos.Rotate(angle , Axis.X) ,                        Intensivity = shader.Lights[0].Intensivity                    };                Draw();            }

image

Производительность


Для теста использовалась следующие конфигурации:

  • Модель Сильваны: 220к полигонов.
  • Разрешение экрана: 1920x1080.
  • Шейдеры: Phong model shader
  • Конфигурация компьютера: cpu core i7 4790, 8 gb ram

FPS рендеринга составлял 1-2 кадр/сек. Это далеко не realtime. Однако стоит все же учитывать, что вся обработка происходила без использования многопоточности, т.е. на одном ядре cpu.

Заключение


Я считаю себя новичком в 3д графике не исключаю ошибок допущенных мною в ходе изложения. Единственное на что я опираюсь это практический результат, полученный в процессе создания. Все поправки и оптимизации(если таковые будут) вы можете оставить в комментариях, я с радостью их прочту. Ссылка на репозиторий проекта.
Подробнее..

Бумажный бит создание механической памяти из оригами

28.08.2020 10:04:17 | Автор: admin


Бегущий по лезвию, Воздушная тюрьма, Heavy Rain что общего между этими представителями массовой культуры? Во всех в той или иной степени присутствует древнее японское искусство по складыванию бумаги оригами. В кино, играх и в реальной жизни оригами частенько используется в качестве символа определенных чувств, каких-то воспоминаний или своеобразного послания. Это скорее эмоциональная составляющая оригами, но с точки зрения науки в бумажных фигурках сокрыто множество интересных аспектов из самых разных направлений: геометрия, математика и даже механика. Сегодня мы с вами познакомимся с исследованием, в котором ученые из Американского института физики создали устройство хранения данных за счет складывания/раскладывания фигурок оригами. Как именно работает бумажная карта памяти, какие принципы в ней реализованы и сколько данных может хранить такое устройство? Ответы на эти вопросы мы найдем в докладе ученых. Поехали.

Основа исследования


Когда именно возникло оригами, сказать сложно. Но мы точно знаем, что не ранее 105 года н.э. Именно в этом году в Китае Цай Лунь изобрел бумагу. Конечно, до этого момента бумага уже существовала, но она изготавливалась не из древесины, а из бамбука или шелка. Первый вариант не отличался легкостью, а второй был крайне дорогой. Цай Луню поручили придумать новый рецепт бумаги, которая будет легкой, дешевой и простой в изготовлении. Задача не из простых, однако Цай Лунь обратился к самому популярному источнику вдохновения к природе. Он долгое время наблюдал за осами, чьи жилища были сделаны из древесины и растительных волокон. Цай Лунь провел множество опытов, в которых использовал самые разные материалы для будущей бумаги (кора деревьев, зола и даже рыболовные сети), перемешанные с водой. Полученная масса выкладывалась в специальную форму и сушилась на солнце. Результатом этого колоссального труда стал прозаичный для современного человека предмет бумага.


В 2001 году в городе Лэйян (Китай) был открыт парк, названный в честь Цай Луня.

Распространение бумаги по другим странам не произошло моментально, лишь в начале VII века ее рецепт достиг Кореи и Японии, а до Европы бумага добралась лишь в XIXII веке.

Самым очевидным применением бумаги, конечно же, является и рукописи и полиграфия. Однако японцы нашли ей и более изящное применение оригами, т.е. складывание фигурок из бумаги.


Коротенький экскурс в мир оригами и инженерии.

Вариантов оригами существует великое множество, как и техник их изготовления: простое оригами, кусудама (модульное), мокрое складывание, паттерн-оригами, киригами и т.д. (Иллюстрированная энциклопедия по оригами)

С точки зрения науки оригами это механический метаматериал, свойства которого определяются его геометрией, а не свойствами материала, из которого он изготовлен. Уже довольно давно было продемонстрировано, что универсальные трехмерные развертываемые структуры с уникальными свойствами могут быть созданы с использованием повторяющихся шаблонов оригами.


Изображение 1

На изображении 1b показан пример такой структуры развертываемый сильфон, построенный из одного листа бумаги по схеме на . Из имеющихся вариантов оригами ученые выделили вариант, в котором реализована мозаика из одинаковых треугольных панелей, расположенных в циклической симметрии, известной как оригами Креслинга.

Важно отметить, что структуры на базе оригами бывают двух типов: жесткие и нежесткие.

Жесткое оригами это трехмерные структуры, в которых только складки между панелями подвергаются деформации во время развертывания.

Ярким примером жестких оригами является Миура-ори, использованный для создания механических метаматериалов с отрицательным коэффициентом Пуассона. Такой материал имеет широкий спектр применения: изучения космоса, деформируемая электроника, искусственные мышцы и, естественно, перепрограммируемые механические метаматериалы.

Нежесткие оригами это трехмерные структуры, которые демонстрируют нежесткую упругую деформацию панелей между складками во время развертывания.

Примером такого варианта оригами является упомянутый ранее узор Креслинга, который успешно использовался для создания структур с настраиваемой мультистабильностью, жесткостью, деформациями, смягчением/упрочнением и/или с почти нулевой жесткостью.

Результаты исследования


Вдохновившись древним искусством, ученые решили использовать оригами Креслинга для разработки кластера механических бинарных переключателей, которые можно принудительно переключать между двумя разными статическими состояниями, используя один управляемый вход в виде гармонического возбуждения, прилагаемого к основанию переключателя.

Как видно из 1b, сильфон закреплен на одном конце и подвергается внешней нагрузке в направлении x на другом свободном конце. За счет этого он претерпевает одновременное отклонение и вращение вдоль и вокруг оси x. Энергия, накопленная в процессе деформации сильфона, высвобождается при снятии внешней нагрузки, в результате чего сильфон возвращается к своей первоначальной форме.

Проще говоря, мы видим торсионную пружину кручения, восстанавливающая способность которой зависит от формы функции потенциальной энергии сильфона. Это, в свою очередь, зависит от геометрических параметров (a0, b0, 0) составного треугольника, используемого для построения сильфона, а также от общего количества (n) этих треугольников ().

Для некоторой комбинации геометрических параметров конструкции функция потенциальной энергии сильфона имеет единственный минимум, соответствующий одной устойчивой точке равновесия. Для других комбинаций функция потенциальной энергии имеет два минимума, соответствующих двум устойчивым статическим конфигурациям сильфона, каждая из которых связана с разной равновесной высотой или, в качестве альтернативы, прогибом пружины (). Такой тип пружины часто называют бистабильной (видео ниже).


На изображении 1d показаны геометрические параметры, ведущие к формированию бистабильной пружины, и параметры, ведущие к формированию моностабильной пружины для n=12.

Бистабильная пружина может останавливаться в одном из своих положений равновесия при отсутствии внешних нагрузок и может быть активирована для переключения между ними при наличии надлежащего количества энергии. Именно это свойство и является основой данного исследования, в котором рассматривается создание механических переключателей Креслинга (KIMS от Kresling-inspired mechanical switches) с двумя двоичными состояниями.

В частности, как показано на 1c, переключатель может быть активирован для перехода между двумя его состояниями путем подачи энергии, достаточной для преодоления потенциального барьера (E). Энергия может подаваться в виде медленного квазистатического срабатывания или путем подачи гармонического сигнала на основание переключателя с частотой возбуждения, близкой к локальной резонансной частоте переключателя в его различных состояниях равновесия. В данном исследовании было решено использовать второй вариант, так как гармоническое резонансное срабатывание по некоторым параметрам превосходит квазистатическое.

Во-первых, резонансное срабатывание требует меньшего усилия для переключения и, как правило, происходит быстрее. Во-вторых, резонансное переключение нечувствительно к внешним возмущениям, которые не резонируют с переключателем в его локальных состояниях. В-третьих, поскольку потенциальная функция переключателя обычно асимметрична относительно точки неустойчивого равновесия U0, характеристики гармонического возбуждения, необходимые для переключения с S0 на S1, обычно отличаются от характеристик, необходимых для переключения с S1 на S0, что приводит к возможности селективного по возбуждению двоичного переключения.

Такая конфигурация KIMS прекрасно подходит для создания платы механической памяти из нескольких битов с использованием нескольких двоичных переключателей с разными характеристиками, размещенных на одной платформе с гармоническим возбуждением. Создание такого устройство обусловлено чувствительностью формы функции потенциальной энергии переключателя к изменениям геометрических параметров основных панелей ().

Следовательно, сразу несколько KIMS с различными конструктивными характеристиками могут быть размещены на одной платформе и возбуждены для перехода из одного состояния в другое по отдельности или в комбинации с использованием различных наборов параметров возбуждения.

На этапе практических испытаний были созданы переключатель из бумаги плотностью 180 г/м2 с геометрическими параметрами: 0 = 26.5; b0/a0 = 1.68; a0 = 40 мм и n = 12. Именно такие параметры, судя по расчетам (1d), и приводят к тому, что полученная пружина будет бистабильной. Расчеты же были выполнены посредством упрощенной модели осевой фермы (конструкция из стержней) сильфона.

Используя лазер, на листе бумаги были сделаны перфорированные линии (), которые являются местами складывания. Затем были сделаны складки по краям b0 (загнутые наружу) и 0 (загнутые внутрь), а края дальних концов были плотно соединены. Верхняя и нижняя поверхности переключателя были усилены акриловыми многоугольниками.

Кривая восстанавливающей силы переключателя была получена экспериментально посредством испытаний на сжатие и растяжение, выполненных на универсальной испытательной машине со специальной установкой, позволяющей вращать основание во время тестов (1f).

Концы акрилового многоугольника переключателя были жестко зафиксированы, а к верхнему многоугольнику применялось контролируемое смещение с заданной скоростью 0.1 мм/с. Смещения при растяжении и сжатии применялись циклически и ограничивались величиной 13 мм. Непосредственно перед фактическим тестированием устройства выключатель настраивается путем выполнения десяти таких циклов нагрузки, прежде чем восстанавливающая сила будет записана с помощью 50N датчика нагрузки. На 1g показана кривая восстанавливающей силы переключателя, полученная экспериментально.

Далее путем интегрирования средней восстанавливающей силы переключателя по диапазону срабатывания вычислялась функция потенциальной энергии (1h). Минимумы в функции потенциальной энергии представляют собой статические равновесия, связанные с двумя состояниями переключателя (S0 и S1). Для этой конкретной конфигурации S0 и S1 возникают при высоте развертывания u = 48 мм и 58.5 мм соответственно. Функция потенциальной энергии явно асимметрична с разными энергетическими барьерами E0 в точке S0 и E1 в точке S1.

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


Изображение 2

Было установлено, что локальная резонансная частота переключателя для двух его состояний составляет 11.8 Гц для S0 и 9.7 Гц для S1. Чтобы инициировать переход между двумя состояниями, то есть выход из потенциальной ямы*, была проведена очень медленная (0.05 Гц/с) двунаправленная линейная развертка частоты вокруг идентифицированных частот с ускорением основания 13 мс-2. В частности, KIMS изначально был расположен на S0, а возрастающая развертка по частоте была инициирована на 6 Гц.
Потенциальная яма* область, где присутствует локальный минимум потенциальной энергии частицы.
Как видно на 2b, когда частота возбуждения достигает примерно 7.8 Гц, переключатель выходит из потенциальной ямы S0 и входит в потенциальную яму S1. Переключатель продолжал оставаться в S1 по мере дальнейшего увеличения частоты.

Затем переключатель снова был установлен на S0, но на этот раз развертка по убывающей частоте была инициирована на 16 Гц. В этом случае, когда частота приближается к 8.8 Гц, переключатель выходит из S0 и входит и остается в потенциальной яме S1.

Состояние S0 имеет полосу активации 1 Гц [7.8, 8.8] при ускорении 13 мс-2, а S1 67.7 Гц (). Из этого следует, что KIMS может выборочно переключаться между двумя состояниями за счет гармонического возбуждения основания одинаковой величины, но разной частоты.

Ширина полосы переключения KIMS имеет сложную зависимость от формы его функции потенциальной энергии, характеристик демпфирования и параметров возбуждения гармоник (частоты и величины). Кроме того, из-за смягчающего нелинейного поведения переключателя ширина полосы активации необязательно включает в себя линейную резонансную частоту. Таким образом, важно, чтобы карта активации переключателей была создана для каждого KIMS индивидуально. Эта карта используется для характеристики частоты и величины возбуждения, что приводит к переключению из одного состояния в другое и наоборот.

Такую карту можно создать экспериментально путем частотной развертки на разных уровнях возбуждения, но этот процесс весьма трудоемкий. Посему ученые решили на этом этапе перейти к моделированию переключателя, используя функцию потенциальной энергии, определенной во время опытов (1h).

Модель предполагает, что динамическое поведение переключателя может быть хорошо аппроксимировано динамикой асимметричного бистабильного осциллятора ГельмгольцаДуффинга, уравнение движения которого может быть выражено так:



где u отклонение подвижной грани акрилового многоугольника относительно неподвижной; m эффективная масса переключателя; c коэффициент вязкого демпфирования, определенный экспериментально; ais бистабильные коэффициенты восстанавливающей силы; ab и базовая величина и частота ускорения.

Основная задача моделирования состоит в использовании данной формулы для установления комбинаций ab и , которые позволяют переключаться между двумя разными состояниями.

Ученые отмечают, что критические частоты возбуждения, при которых бистабильный осциллятор переходит из одного состояния в другое, могут быть аппроксимированы двумя частотами бифуркации*: бифуркация удвоения периода (PD) и бифуркация циклической складки (CF).
Бифуркация* качественное изменение системы посредством изменения параметров, от которых она зависит.
Используя аппроксимацию были построены кривые частотной характеристики KIMS в двух его состояниях. На графике показаны кривые частотной характеристики переключателя в S0 для двух различных базовых уровней ускорения.

При базовом ускорении 5 мс-2 кривая амплитудно-частотная кривая показывает небольшое смягчение, но без нестабильности или бифуркаций. Таким образом, переключатель остается в состоянии S0, независимо от того, как меняется частота.

Однако, когда базовое ускорение увеличивается до 13 мс-2, стабильность снижается за счет PD бифуркации при уменьшении частоты возбуждения.

По такой же схеме были получены кривые частотной характеристики переключателя в S1 (2f). При ускорении 5 мс-2 наблюдаемая картина остается прежней. Однако по мере увеличения базового ускорения до 10 мс-2 появляются PD и CF бифуркации. Возбуждение переключателя на любой частоте между этими двумя бифуркациями приводит к переключению с S1 на S0.

Данные моделирования говорят о том, что на карте активации есть обширные области, в которых каждое состояние может быть активировано уникальным образом. Это позволяет избирательно переключаться между двумя состояниями в зависимости от частоты и величины срабатывания. Также видно, что есть область, где оба состояния могут переключаться одновременно.


Изображение 3

Комбинация из нескольких KIMS может быть использована для создания механической памяти из нескольких битов. Меняя геометрию переключателя таким образом, чтобы форма функции потенциальной энергии любых двух переключателей была достаточно различной, можно спроектировать ширину полосы активации переключателей так, чтобы они не перекрывались. За счет этого для каждого переключателя будут уникальные параметры возбуждения.

Для демонстрации этой техники была создана 2-битная плата на базе двух переключателей с различными характеристиками потенциала (): бит 1 0 = 28; b00 = 1.5; а0 = 40 мм и n = 12; бит 2 0 = 27; b00 = 1.7; а0 = 40 мм и n = 12.

Поскольку каждый бит имеет два состояния, всего может быть достигнуто четыре различных состояния S00, S01, S10 и S11 (3b). Цифры после S обозначают значение левого (бит 1) и правого (бит 2) переключателя.

Поведение 2-битного переключателя показано на видео ниже:










На базе данного устройства можно также создать кластер переключателей, которые могут быть основой многобитовых плат механической памяти.

Для более детального ознакомления с нюансами исследования рекомендую заглянуть в доклад ученых и дополнительные материалы к нему.

Эпилог


Вряд ли кто-либо из создателей оригами мог себе представить, как их творение будет использоваться в современном мире. С одной стороны, это говорит о большом числе сложных элементов, сокрытых в обычных бумажных фигурках; с другой о том, что современная наука способна эти элементы применять для создания чего-то совершенно нового.

В данном труде ученые смогли использовать геометрию оригами Креслинга для создания простого механического переключателя, способного в зависимости от вводных параметров быть в двух разных состояниях. Это можно сравнить с 0 и 1, которые являются классическими единицами измерения информации.

Полученные устройства были объединены в систему механической памяти, способной хранить 2 бита. Зная, что одна буква занимает 8 бит (1 байт), возникает вопрос сколько же понадобится подобных оригами, чтобы записать Войну и мир, например.

Ученые прекрасно понимают скептицизм, который может вызывать их разработка. Однако, по их же словам, данное исследование является разведкой в области механической памяти. Кроме того, использованные в опытах оригами не должны быть большими, их габариты можно значительно уменьшить, при этом не ухудшив их свойства.

Как бы то ни было, этот труд нельзя назвать ординарным, банальным или скучным. Наука далеко не всегда используется для разработки чего-то конкретного, а ученые далеко не всегда изначально знают, что именно создают. Ведь большинство изобретений и открытий были результатом простого вопроса а что если?

Благодарю за внимание, оставайтесь любопытствующими и отличных всем выходных, ребята! :)

Немного рекламы


Спасибо, что остаётесь с нами. Вам нравятся наши статьи? Хотите видеть больше интересных материалов? Поддержите нас, оформив заказ или порекомендовав знакомым, облачные VPS для разработчиков от $4.99, уникальный аналог entry-level серверов, который был придуман нами для Вас: Вся правда о VPS (KVM) E5-2697 v3 (6 Cores) 10GB DDR4 480GB SSD 1Gbps от $19 или как правильно делить сервер? (доступны варианты с RAID1 и RAID10, до 24 ядер и до 40GB DDR4).

Dell R730xd в 2 раза дешевле в дата-центре Equinix Tier IV в Амстердаме? Только у нас 2 х Intel TetraDeca-Core Xeon 2x E5-2697v3 2.6GHz 14C 64GB DDR4 4x960GB SSD 1Gbps 100 ТВ от $199 в Нидерландах! Dell R420 2x E5-2430 2.2Ghz 6C 128GB DDR3 2x960GB SSD 1Gbps 100TB от $99! Читайте о том Как построить инфраструктуру корп. класса c применением серверов Dell R730xd Е5-2650 v4 стоимостью 9000 евро за копейки?
Подробнее..

Перевод Некоторые математические задачи нерешаемы, и это не так уж плохо

03.12.2020 10:23:07 | Автор: admin

Постройте выпуклый восьмиугольник с четырьмя прямыми углами.

Вероятно, то, что я даю такие задания, многое говорит обо мне, как об учителе. Я наблюдаю за тем, как студенты пытаются выстроить прямые углы последовательно. Когда у них это не получается, они пытаются перемежать прямые углы. Снова потерпев неудачу, они вставляют их в многоугольник случайным образом. Скрежет, издаваемый их мозгами во время мыслительных усилий музыка для ушей учителя.

Потом у них возникают подозрения и они начинают задавать вопросы. Вы сказали о прямых углах. Может, на самом деле вы имели в виду три угла?, Вы точно имели в виду выпуклый многоугольник?, Четыре прямых угла, по сути, образуют прямоугольник. Как мы можем получить ещё четыре стороны в восьмиугольнике? Я внимательно слушаю, киваю, подтверждая их догадки.

Наконец, кто-то задаёт вопрос, который никто не осмеливался задать, вопрос, которого я ждал: Слушайте, а это вообще возможно?

Этот вопрос обладает мощью, способной менять образ мышления в математике. Те, кто думал узко о конкретных условиях, теперь должны думать более широко о том, как соответствуют друг другу эти условия. Те, кто работает внутри системы, должны сделать шаг назад и изучить саму систему. На протяжении всей истории математики этот вопрос задавался множество раз, им озадачивались те, кто решал задачи квадратуры круга для обхождения города Кёнигсберга. И этот вопрос позволяет нам сформулировать, что же такое математика и как мы её понимаем.

Например, поиск восьмиугольника с определёнными свойствами сильно отличается от задачи демонстрации, что такого восьмиугольника существовать не может. Экспериментируя с разными восьмиугольниками, мы ведь можем и наткнуться на такой, где есть четыре прямых угла.


Это не пример. На самом деле у этого восьмиугольника нет четырёх прямых углов.

Но удача не играет никакой роли в доказательстве того, что подобный восьмиугольник не может существовать. Для него требуется глубокое знание, не только многоугольников, но и самой математики. Чтобы учесть невозможность, нам нужно понять, что простое допущение о существовании объекта не доказывает его существование. Математические определения, свойства и теоремы живут в условиях давления, вызванного их взаимосвязанностью. Пытаясь представить восьмиугольник с четырьмя прямыми углами, мы находимся внутри этих взаимосвязанных правил.

Но чтобы осознать, что восьмиугольник невозможен, нам нужно отступить на шаг назад и взглянуть на картину в целом. Какие математические и геометрические принципы могут быть нарушены восьмиугольником с четырьмя прямыми углами? Здесь хорошо будет начать с теоремы о сумме углов многоугольника.

Сумма внутренних углов n-стороннего многоугольника определяется по формуле:

S = (n 2) 180

Так получилось, потому что каждый n-сторонний многоугольник можно разрезать на (n 2) треугольников, сумма внутренних углов каждого из которых равна 180.

В случае восьмиугольника это означает, что сумма его внутренних углов равна (8 2) 180 = 6 180 = 1080. Тогда если четыре из его углов прямые, то есть каждый равен 90, то это составляет 4 90 = 360 от общей суммы углов. Значит, на оставшиеся четыре угла восьмиугольника остаётся 1080 360 = 720.

Это означает, что среднее для четырёх оставшихся углов должно быть равно:

$\frac{720}{4} = 180$


Но внутренние углы выпуклого многоугольника должны быть меньше 180, то есть это невозможно. Выпуклый восьмиугольник с четырьмя прямыми углами не может существовать.

Доказательство невозможности таким способом требует сделать шаг назад и посмотреть, как различные разные математические правила, например, формула суммы углов многоугольника и определение выпуклого многоугольника, существуют во взаимном давлении. И поскольку доказательства невозможности полагаются на более широкое рассуждение над множеством правил, часто существует несколько способов построения такого доказательства.

Давайте вернёмся к нашему предыдущему замечанию о том, что четыре прямых угла составляют прямоугольник.


Внешние углы многоугольника.

Если бы восьмиугольник имел четыре прямых угла, то обойдя только эти углы, мы бы совершили полный круг, как будто мы полностью обошли вокруг прямоугольника. Эта мысль приводит нас к правилу, дающему ещё одно доказательство невозможности. Известно, что сумма внешних углов выпуклого многоугольника всегда равна 360. Поскольку внешний угол прямого угла также является прямым углом, наши четыре прямых угла составят все 360 от суммы внешних углов восьмиугольника. То есть остальным четырём углам не остаётся ничего, и мы снова установили, что такой восьмиугольник невозможен.

Доказательство того, что что-то невозможно мощное математическое событие. Оно сдвигает нашу точку зрения, мы превращаемся из подчиняющихся правилам в контролирующих правила. А чтобы контролировать правила, нам нужно сначала их понять. Мы должны не только знать, как применять их, но и ситуации, в которых они неприменимы. А также находить ситуации, в которых правила могут конфликтовать друг с другом. В процессе исследования восьмиугольника мы выявили взаимосвязь многоугольников, выпуклости, прямых углов и сумм углов. И это подчёркивает, что S = (n 2) 180 не просто формула: это одно из условий в мире конфликтующих условий.

Доказательства невозможности могут помочь нам лучше понимать все области математики. В школе уроки по теории вероятностей часто начинаются с подбрасывания множества воображаемых монеток. Я предлагаю ученикам создать жульническую монету, имеющую склонность к выпадению орла или решки, обладающую следующим свойством: при подбрасывании монетки дважды результаты двух подбрасываний с большей вероятностью будут разными, чем одинаковыми. Другими словами, вы с большей вероятностью выбросите орла и решку, чем орла и орла или решку и решку.

После экспериментов и мыслительных неудач ученики приходят к интересной гипотезе: разные результаты никогда не имеют бОльшую вероятность, чем одинаковые. Алгебра выявляет это и указывает на лежащую в основе этого явления симметрию.

Допустим, монетка смещена в сторону выпадания орла. Мы назовём вероятность выпадания орла $\frac{1}{2} + k$, где $0 < k \frac{1}{2}$. Тот факт, что $k > 0$, гарантирует, что орёл более вероятен, чем решка, имеющая вероятность $\frac{1}{2} k$, поскольку сумма двух вероятностей должна быть равна 1.

Если мы подбросим монету дважды, то вероятность получения двух орлов или двух решек будет равна

$\left(\frac{1}{2}+k\right)^{2}+\left(\frac{1}{2}-k\right)^{2}$


Здесь мы складываем вероятность получения двух орлов (левая часть) с вероятностью получения двух решек (правая часть). При помощи алгебры мы можем упростить вероятность получения одинакового результата при обоих бросках:

$\left(\frac{1}{2}+k\right)^{2}+\left(\frac{1}{2}-k\right)^{2} = \frac{1}{4} + k + k^{2} + \frac{1}{4} k + k^{2} = \frac{1}{2} + 2k^{2}$

.
Поскольку $k > 0$, мы знаем, что $\frac{1}{2} + 2k^2 > \frac{1}{2}$$, а это означает, что с большей вероятностью результаты бросков будут одинаковыми. На самом деле, мы видим, что даже если $k = 0$ (монета не жульническая), вероятность одинаковых результатов равна $\frac{1}{2}$, из-за чего вероятность разных результатов бросков тоже равна $\frac{1}{2}$. Тот же результат никогда не будет менее вероятным, чем разные.

Как и в случае задачи с многоугольником, мы видим работу конкурирующих математических давлений: изменение вероятности получения одной стороны монеты изменяет вероятность получения другой, и эта взаимосвязанность управляет пространством возможностей результатов двух бросков. Мы выявили это давление, пытаясь выполнить невозможное.

Таким давлениям можно подвергнуть любую область математики. Попробуйте найти шесть последовательных целых чисел, сумма которых равна 342, и благодаря своей настойчивости вы придёте к более глубокому пониманию чётности. (Тот факт, что последовательные целые числа попеременно становятся чётными и нечётными, влияет на то, какими могут быть их суммы.) Нахождение кубического многочлена с целочисленными коэффициентами, имеющего три невещественных корня, научит вас важности сопряжённых комплексных чисел пар комплексных чисел, произведение и сумма которых всегда вещественны. А если вы попытаетесь вписать в окружность непрямоугольный ромб, то обнаружите важное свойство циклических четырёхугольников противоположные углы четырёхугольника, вершины которого лежат на окружности, должны иметь сумму 180 градусов.

Столкновение с невозможным позволяет нам исследовать границы наших математических миров. Невозможное само по себе является своего рода обобщением, поэтому естественно будет продолжить обобщение: восьмиугольник не может иметь четырёх прямых углов, но как насчёт десятиугольника? Как насчёт выпуклого многоугольника с n > 4 сторонами? Подобные вопросы упираются в границы наших математических миров и углубляют их понимание.

Если мы будем продавливать границы дальше, то невозможное может даже вдохновить к созданию новых математических миров. Чтобы доказать невозможность получения квадратуры круга (этой задаче уже не менее двух тысяч лет), необходима современная теория трансцендентных чисел, которые не могут являться корнями целочисленных многочленов. Для решения задачи о семи кёнигсбергских мостах Эйлер превратил острова и мосты в вершины и рёбра, дав жизнь обширным областям теории графов и теории сетей, а также множеству их сфер применения. Получение квадратного корня от 1 привело к созданию совершенно новой системы арифметики. А логик Курт Гёдель навсегда изменил математику, доказав, что невозможно доказать, что всё истинное истинно.

Поэтому когда в следующий раз вы столкнётесь с математической задачей, спросите себя: Возможно ли это? Столкновение с невозможностью может дать вам более глубокое понимание того, что возможно. При этом вы даже сможете создать новые области математики.

Упражнения


1. Найти площадь треугольника с длинами сторон 46, 85 и 38.

2. Пусть $f (x) = 2x^3 + bx^2 + cx + d$. Найти такие целые $b$, $c$ и $d$, при которых $f \left(\frac{1}{4}\right) = 0$.

3. Найти полный квадрат, в котором все составляющие его цифры принадлежат множеству {2, 3, 7, 8}.

Ответы


Ответ 1
Такой треугольник не существует. Длины его сторон не удовлетворяют теореме неравенства треугольника, гласящей, что сумма любых двух сторон должна быть больше третьей. Это можно показать геометрически: возьмём отрезок длиной 85 и на его концах построим окружности радиусами 38 и 46. Эти окружности не пересекутся, из-за чего невозможно найти третью вершину треугольника.


Любопытно будет применить что-нибудь типа формулы Герона для вычисления площади этого не-треугольника. Из этого последуют интересные вопросы!

Ответ 2
Существуют различные способы определения невозможности такого многочлена. Например, эти условия нарушают теорему о рациональных корнях, гласящую, что любые рациональные корни многочлена должны быть соотношением делителя свободного члена (d) и делителя старшего коэффициента (2).

Ответ 3
Любопытный факт о полных квадратах доказывает нам, что эта задача невозможна. В разряде единиц полного квадрата могут быть только цифры 0, 1, 4, 5, 6 или 9. Это можно показать возведением в квадрат каждой возможной цифры и наблюдением за возможными результатами. Поскольку ни один полный квадрат не может заканчиваться на 2, 3, 7 или 8, не существует полного квадрата, состоящего только из этих цифр.




На правах рекламы


Какими бы не были ваши задачи, всегда не помешают доступные и надёжные серверы. Даже для сложных математических расчётов, максимальная конфигурация 128 ядер CPU, 512 ГБ RAM, 4000 ГБ NVMe.

Подробнее..

Перевод Учёные раскрыли универсальную геометрию геологии, и оказалось, что мир состоит из кубов

18.12.2020 14:16:13 | Автор: admin

Упражнения в чистой математике привели к созданию масштабной теории об устройстве мира




Где-то в середине лета 2016 года венгерский математик Габор Домокош взошёл на крыльцо дома Дугласа Джерольмака, геофизика из Филадельфии. С собой у Домокоша были дорожные чемоданы, сильная простуда и жгучая тайна.

Чуть позже двое мужчин гуляли по гравийной дорожке на площадке за домом, где жена Джерольмака держала тележку для продажи тако. Под их ногами хрустел измельчённый известняк. Домокош указал под ноги.

Сколько граней у каждого из этих камушков? спросил он. Затем он ухмыльнулся. Что, если я скажу вам, что их количество обычно равно шести? А затем он задал ещё более общий вопрос, который, как он надеялся, надолго поселится в мозге его коллеги. Что, если мир состоит из кубов?

Джерольмак сначала возразил: может, дома и строятся из кирпичей, но Земля состоит из камней. А форма у камней, очевидно, разная. Слюда крошится на чешуйки, кристаллы ломаются по жёстко определённым осям. Однако Домокош утверждал, что из одной лишь чистой математики следует, что любые камни, ломающиеся случайным образом, будут порождать формы, имеющие в среднем по шесть граней и восемь вершин. Если взять среднее по всем им, оно будет стремиться к некоему идеальному кубу. Домокош сказал, что доказал это математически. Теперь ему нужно было, чтобы Джерольмак помог ему показать, что это происходит и в природе.

Это было чёткое геометрическое предсказание, порождённое природой, причём без какой-либо физики, сказал Джерольмак, профессор из Пенсильванского университета. Как, чёрт возьми, природа это вообще допустила?

В последовавшие несколько лет парочка изучала свою геометрическую идею, исследуя всё, от микроскопических фрагментов камней до обнажения геологических пород, поверхностей планет и даже диалога Платона "Тимей". Всё это покрывало проект налётом мистицизма. Один из величайших философов примерно в 360 году до н.э. сопоставил пять платоновых тел с пятью элементами мироздания: землёй, воздухом, огнём, водой и звёздной материей. По удачному совпадению и/или предвидению Платон сопоставил кубы, которые лучше всего складываются в штабеля, с землёй. И я подумал ладно, вот мы уже слегка зашли и на территорию метафизики, сказал Джерольмак.


Габор Домокош и Дуглас Джерольмак

Однако они продолжали находить средние кубоиды в природе, а также несколько форм, не похожих на кубы, но подчинявшихся той же теории. В итоге они создали новую математическую платформу: описательный язык, выражающий, как всякие вещи распадаются на части. Опубликованная в этом году их совместная работа названием напоминала эзотерический том из серии про Гарри Поттера: Куб Платона и естественная геометрия фрагментации.

Несколько геофизиков, с которыми связалась редакция журнала, говорят, что ту же математическую платформу можно использовать и для других задач, вроде изучения эрозии разломов скал, или предотвращения опасных оползней. Это очень интересно, сказал геоморфолог Микаэль Аттал из Эдинбургского университета, один из двух рецензентов этой работы. Другой рецензент, геофизик Дэвид Фёрбиш из университета Вандербильта, сказал: Подобные работы заставляют меня задуматься: не могу ли я как-то воспользоваться этими идеями?

Все возможные разломы


Задолго до визита в Филадельфию у Домокоша возник более безобидный математический вопрос.

Допустим, вы раскрошили нечто на множество кусочков. Теперь у вас есть мозаика набор фигур, которые можно составить вместе безо всяких наложений и разрывов, как пол в древнеримской бане. Также допустим, что все фигуры выпуклые.

Сначала Домокошу стало интересно, можно ли только средствами геометрии предсказать, из каких фигур в среднем будет состоять подобная мозаика. Затем он захотел научиться описывать все остальные возможные наборы таких фигур.

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

Для человека, изучающего геометрию, найти ответ на этот вопрос будет не так уж и сложно. Ставлю ящик пива, что смогу помочь вам вывести эту формулу за пару часов, сказал Домокош. В среднем у кусочков должно быть по четыре вершины и четыре стороны, а средняя форма у них будет прямоугольной.

Эту же задачу можно рассматривать и в трёх измерениях. Лет 50 назад русский физик-ядерщик, лауреат нобелевской премии мира, и позднее диссидент, Андрей Дмитриевич Сахаров задумался над такой же проблемой, когда со своей женой резал кочаны капусты. Сколько вершин в среднем будет у каждого из полученных кусочков? Сахаров передал эту задачу легендарному советскому математику Владимиру Игоревичу Арнольду и его студенту. Однако полного решения они не нашли, и их попытки по большей части были забыты.


Валуны Моераки в Новой Зеландии

Домокош, не знавший об их работе, написал доказательство, ответом которого стали кубы. Но он захотел проверить его правильность. Он решил, что если ответ к этой задаче уже существует, то он должен быть спрятан в непостижимом труде немецких математиков Вольфганга Вайля и Рольфа Шнайдера 80-летнего титана из области геометрии [в оригинале не указано название видимо, имеется в виду книга "Стохастическая и интегральная геометрия" / прим. пер.]. Домокош профессиональный математик, но текст книги оказался тяжеловат даже для него.

Я нашёл человека, согласившегося прочесть мне нужную часть книги, и перевести её обратно на человеческий, сказал Домокош. Он нашёл там теорему для любого количества измерений. Она подтвердила, что в трёх измерениях в ответе действительно фигурируют кубы.

Теперь Домокош нашёл усредненные фигуры, которые получаются при разрезании плоской поверхности или трёхмерного кирпичика. Появился более общий вопрос. Домокош понял, что он также мог разработать математическое описание не только средних фигур, но и потенциально любых: какой набор фигур в принципе можно получить при разделении предмета?

Вспомним, что фигуры, получающиеся после распада предмета, представляют собой мозаику. Их можно составить вместе без перекрытий и разрывов. Прямоугольники, на которые мы разрезали лист, легко можно составить так, чтобы они заполнили двухмерную мозаику. Способны на такое и шестиугольники в идеализированном случае набора, который математики называют "диаграмма Вороного". А вот пятиугольниками или восьмиугольниками плоскость не замостить.


Геометрия Марса. Для анализа поверхности в данном случае, поверхности кратера Марса, похожей на соты исследователи размечают все вершины и стороны. Они подсчитывают количество вершин для каждой из ячеек и количество ячеек, для которых каждая из вершин является общей.

Чтобы правильно классифицировать мозаики, Домокош начал описывать их двумя числами. Первое среднее число вершин на ячейку. Второе среднее количество разных ячеек, для которых есть одна общая вершина. Так, к примеру, в мозаике из шестиугольных плиток у каждой из них есть шесть вершин. А каждая вершина является общей для трёх шестиугольников.

В мозаиках работают только определённые комбинации из двух этих параметров, что даёт небольшой диапазон фигур, на которые что-то может в принципе распасться.

Опять-таки, этот диапазон достаточно легко найти в двух измерениях, но гораздо труднее в трёх. В трёхмерном пространстве кубы очень хорошо складываются вместе, но есть и другие виды фигур в том числе, формирующие трёхмерные версии диаграммы Вороного. Чтобы не переусложнять задачу, Домокош ограничился мозаикой из правильных выпуклых ячеек с общими вершинами. В итоге они с математиком Жолтом Ланги вывели новую гипотезу, набросав кривую, в которую укладываются все возможные трёхмерные мозаики. Они опубликовали работу в журнале Experimental Mathematics, а потом я отправил всё это Рольфу Шнайдеру, нашему божеству, сказал Домокош.


Пространство кубов. В трёх измерениях большинство камней разбиваются на кубы с восемью вершинами на ячейку. Карта допустимых мозаик из выпуклых фигур с правильными ячейками, имеющими общие вершины, укладывается в узкую полосу. Красным выделена область кубоидных форм.
По вертикали: количество вершин на ячейку
По горизонтали: количество общих ячеек у каждой вершины


Я спросил его, нужно ли объяснять, как я пришёл к такой гипотезе, но он сказал, что он знает об этом, смеётся Домокош. Для меня это было в сто раз более важным, чем принятие статьи любым журналом мира.

Что важнее, теперь у Домокоша была платформа. Математика давала способ классификации всех способов разбиения поверхностей и блоков. А геометрия предсказывала, что если разбить плоскую поверхность случайно, она будет разделяться на нечто вроде прямоугольников. В трёх измерениях разбиение приведёт к появлению чего-то, похожего на кубы.

Но чтобы всё это имело значение для кого-то, кроме небольшой группки математиков, Домокош должен был доказать, что этим правилам подчиняется и реальный мир.

От геометрии к геологии


К тому времени, как в 2016 году Домокош оказался в Филадельфии, в решении задачи применительно к реальному миру он уже кое-чего достиг. Они с коллегами из Будапештского технологическо-экономического университета собрали осколки доломита, отколовшиеся от скалы Хармашатархег, находящейся в Будапеште. Несколько дней сотрудник лаборатории без всякого предубеждения насчёт кубов усердно подсчитывал количество граней и вершин сотен кусочков. Какие средние показатели он получил? Шесть граней, восемь вершин. Домокош совместно с Яношом Тёроком, специалистом по компьютерным симуляциям, и Ференцем Куном, экспертом по фрагментационной физике, обнаружили, что средние кубоиды появлялись и в породах другого типа например, в гипсе и известняке.

Вооружившись математикой и ранними физическими свидетельствами, Домокош выдал свою идею поражённому Джерольмаку. Он будто загипнотизировал меня, и всё остальное на какое-то время просто исчезло, сказал Джерольмак.

Их альянс был не нов. Много лет назад Домокош обрёл известность, доказав существование гёмбёца забавной трёхмерной фигуры, упорно переворачивающейся в определённую позицию равновесия. Чтобы узнать, может ли гёмбёц существовать в реальности, он привлёк Джерольмака, помогшего применить эту концепцию для объяснения круглой формы гальки на Земле и Марсе [Владимир Арнольд приложил руку и тут, впервые поставив вопрос о существовании подобных тел / прим. пер.]. Теперь Домокош снова просил помочь превратить некие теоретические математические концепции в осязаемый камень.


Гёмбёц выпуклая трёхмерная однородная фигура, имеющая ровно одну точку устойчивого равновесия и одну неустойчивого

Парочка договорилась о новом плане. Чтобы доказать наличие платоновых кубов в природе, им нужно было показать нечто большее, чем просто случайное совпадение геометрии и горсточки камешков. Им нужно было рассмотреть все камни, а потом набросать убедительную теорию того, как абстрактная математика может проникнуть в беспорядочную геофизику, а потом в ещё более беспорядочную реальность.

Сначала всё вроде бы работало, сказал Джерольмак. Математика Домокоша предсказывала, что осколки камней в среднем должны быть кубами. Всё большее число реальных осколков вроде как укладывалось в эту теорию. Однако вскоре Джерольмак понял, что для доказательства теории необходимо разобраться и с исключениями из правил.

Ведь та же самая геометрия даёт возможность описать множество других мозаичных рисунков, существование которых допускается и в двух, и в трёх измерениях. Джерольмак прямо сразу мог назвать несколько типов реальных камней, не похожих на прямоугольники и кубы, которые всё же можно было уложить в эту более обширную классификацию.

Возможно, эти примеры полностью опровергли бы теорию кубического мира. А возможно, что было бы интереснее, они появлялись бы только в особых случаях, из которых геологи смогли бы извлечь новые уроки. Я сказал, что знаю, что это работает не везде, и мне нужно знать, почему, сказал Джерольмак.

В следующие несколько лет Джерольмак с командой, работая по обе стороны Атлантики, начали размечать, куда именно на платформе Домокоша попадают реальные примеры кусочков камней. Исследуя, по сути, двумерные поверхности растрескавшуюся вечную мерзлоту на Аляске, обнажение пород доломита, трещины на гранитном блоке они находили многоугольники, у которых в среднем было четыре стороны и четыре вершины, как и на разрезанной бумаге. Каждое из этих геологических явлений, казалось, проявляло себя там, где камни просто трескались. В этой области предсказание Домокоша сбылось.


Вселенная плиток. Все возможные выпуклые плитки, полностью закрывающие плоскость, можно нанести на график соответствия среднего числа вершин у плитки (ось y) и среднего количества клеток, делящих одну вершину (ось х). Примеры из реального мира:
6 мостовая гигантов, 7 вечная мерзлота на Аляске, 8 высохшая грязь, 9 поверхность гранита.


Но был один тип плоской поверхности, оправдавший надежды Джерольмака: он был исключением со своей собственной историей. Покрытые грязью плоские поверхности высыхают, растрескиваются, намокают, затягиваются, и потом снова растрескиваются. У ячеек на таких поверхностях в среднем по шесть сторон и шесть вершин примерно шестиугольная диаграмма Вороного. Похожий вид имеет каменистая поверхность, появившаяся после застывания лавы, которая отвердевает от поверхности и вниз.

Интересно, что именно такие системы формируются под воздействием иных сил, которые выдавливают их наружу, вместо того, чтобы вдавливать внутрь. Геометрия раскрывает геологические своства. Джерольмак и Домокош считали, что такая диаграмма Вороного, пусть и встречается довольно редко, также может появляться на куда более крупных масштабах, чем они изучали ранее.


Диаграмма Вороного делит плоскость на отдельные участки, каждый из которых состоит из всех точек, ближе всего расположенных к начальной.

Подсчёт корки


В процессе разработки команда встретилась в Будапеште и три безумных дня лихорадочно старалась включить в модель больше примеров из реальной жизни. Вскоре Джерольмак вывел на экран компьютера новый узор: мозаику тектонических плит Земли. Плиты располагаются на литосфере, почти двумерной коже на поверхности планеты. Узор выглядел знакомым, и Джерольмак подозвал других, чтобы полюбоваться им. Мы все были потрясены, сказал он.

На первый взгляд кажется, что плоскостные рисунки тяготеют к диаграмме Вороного, а не к квадратной сетки. А потом команда произвела подсчёты. В идеальной мозаике Вороного из шестиугольников на плоскости у каждой ячейки должно быть по шесть вершин. У реальных тектонических плит в среднем оказалось по 5,77 вершин.

На этом месте гефизик уже мог бы праздновать победу. Но математика это не устраивало. Настроение Дага поднималось. Он работал, как заведённый, сказал Домокош. А на следующий день я расстроился, поскольку размышлял об этом разрыве.

Вечером Домокош отправился домой, всё ещё снедаемый этой разницей. Он вновь записал все числа. И вдруг на него снизошло откровение. Мозаика из шестиугольников может замостить плоскость. Но Земля не плоская по крайней мере, за пределами некоторых одиозных уголков на YouTube. Представьте себе футбольный мяч, состоящий из пятиугольников и шестиугольников. Домокош обработал данные с учётом сферической поверхности и обнаружил, что на шаре у ячеек мозаики Вороного в среднем должно быть по 5,77 вершин.

Эта идея помогла исследователям решить один из важных и открытых вопросов в геофизике: как формируются тектонические плиты Земли? Одни считают, что эти плиты побочный продукт движущихся глубоко в мантии конвекционных потоков. Их противники полагают, что земная кора является отдельной системой. Она расширялась, стала хрупкой и сломалась. Соответствие плит диаграмме Вороного, напоминающей грязевую корку, может поддержать вторую теорию, сказал Джерольмак. А ещё это дало мне понять, насколько важной была та работа, сказал Аттал. Феноменально.

Переломный момент


В трёх измерениях же исключений из правила кубов встречалось достаточно мало. И их тоже можно было объяснить при помощи симуляции необычных сил, давящих наружу. Одна явно некубическая формация находится на побережье Северной Ирландии, где волны бьются о десятки тысяч базальтовых колонн. На ирландском языке это называется Clochn na bhFomhrach, дорога из камней для сверхъестественных существ. По-английски это называется "мостовой гигантов".

Важно, что эти колонны и другие похожие вулканические формации шестиугольные. Однако судя по симуляциям Тёрока, мозаики, похожие на эту мостовую, представляют собой просто трёхмерные структуры, выросшие из двумерной базы диаграмм Вороного после охлаждения вулканической породы.


Мостовая гигантов в Северной Ирландии

Команда утверждает, что если взять картину в целом, большую часть мозаик растрескавшегося камня можно классифицировать при помощи платоновых прямоугольников, двумерных диаграмм Вороного, а всё вместе платоновыми кубами в трёх измерениях. Каждый из узоров может рассказать свою геологическую историю. И, да, с учётом некоторых особенностей, можно сказать, что мир состоит из кубов.

Они должным образом проверили свою модель на соответствие реальности, сказала Марта-Кэри Эппс, специалист по естественным наукам из университета Северной Каролины. Мой изначальный скептицизм угас.

Математика говорит нам, что если мы будем дробить камни, как угодно, случайно или специально, у нас всё равно окажется ограниченный набор возможностей, сказал Фёрбиш. Разве это не умно?

Возможно, у вас получится взять для примера реальное место, состоящее из расколотой породы, подсчитать вершины и грани, и потом сделать вывод о шедших там геологических процессах.

Для некоторых мест у нас есть данные, позволяющие взглянуть на этот вопрос с такой стороны, сказал Роман Дибайас, геоморфолог из Пенсильванского государственного университета. Было бы круто, если бы мы могли делать выводы не из таких очевидных вещей, как мостовая гигантов просто ударив молотком по камню, и посмотрев, на что похожи осколки.

Джерольмак же, сначала считавший, что связь с платоновыми телами может быть случайной, теперь принял эту гипотезу. Ведь, в конце концов, греческий философ считал, что правильные геометрические формы необходимы для познания Вселенной, хотя сами невидимы глазу, и проявляются только в виде искажённых теней.

Это буквально самый очевидный из примеров, которые можно придумать. Статистическое среднее всех этих наблюдений представляет собой куб, сказал Джерольмак. Но такого куба не найти".
Подробнее..

Перевод Единый математический язык для физики и инженерного искусства в 21 веке

15.02.2021 14:04:42 | Автор: admin

Введение

Сегодня, старшеклассников обучающихся по уровням А или их эквивалентам в естественных науках, познакомят с понятием векторов направленных отрезков прямых, и научат манипулировать ими с помощью классической векторной алгебры. Фактически это алгебра, введенная Гиббсом в конце 19-го века; с тех пор она мало изменилась. Ученики практикуются в искусстве векторной алгебры и видят, насколько успешно она выражает большую часть двумерной и трехмерной геометрии. Манипулирование системой становится почти второй натурой.

Уильям Роуэн Гамильтон 1805-1865. Изобретатель кватернионов и один из ключевых научных деятелей 19 векаУильям Роуэн Гамильтон 1805-1865. Изобретатель кватернионов и один из ключевых научных деятелей 19 века

Понятное дело, что будет трудно отказаться от этой знакомой и, по-видимому, успешной системы в пользу новой алгебры (геометрической алгебры (ГА)), которая имеет дополнительные правила и нетрадиционные понятия. Однако, за умеренные затраты времени и усилий, вложенные в изучение ГА, наградой будет возможность получить в свое распоряжение инструмент, который позволяет пользователю проникать даже в самые мощные области современных научных исследований. По мере того, как мы переходим в 21-й век, мы достигли стадии, когда исследования в области физических наук часто специализируются в одной, как правило, очень ограниченной области. Тем не менее, всегда было так, что большие преимущества могут быть получены из взаимодействия между различными областями, что становится все более трудным, но все более желательным. Мы предполагаем, что в новом тысячелетии толчок к междисциплинарной деятельности возрастет во много раз. В следующих разделах мы попытаемся дать читателю некоторые доказательства того, что ГА может быть лучшей надеждой на достижение цели унификации математического языка для современной науки.

Немного истории

Многих выдающихся математиков начала 19-го века занимал вопрос заключавшийся в том, как лучше всего математически представить вращения в трех измерениях, то есть в обычном пространстве. Гамильтон провел большую часть своей жизни, работая над этой проблемой, и в конце концов создал кватернионы, которые были обобщением комплексных чисел. Алгебра содержит четыре элемента и правило

\{ 1,\,\mathbf i,\,\mathbf j,\,\mathbf k \} \\ i^2 = j^2 = k^2 = \mathbf i\mathbf j\mathbf k = -1

Хотя элементы i, j, k часто называют векторами, позже мы увидим, что они не обладают свойствами векторов. Несмотря на очевидную полезность кватернионов, всегда существовала небольшая загадка и путаница в их природе и использовании. Сегодня кватернионы все еще используются для представления трехмерных вращений во многих областях, поскольку признано, что они являются очень эффективным способом выполнения таких операций. Однако путаница все еще сохраняется, и глубокое и детальное понимание кватернионов было потеряно для целого поколения.

Герман Гюнтер Грассман (1809-1877). Немецкий математик и школьный учитель, прославившийся алгеброй, которая теперь носит его имяГерман Гюнтер Грассман (1809-1877). Немецкий математик и школьный учитель, прославившийся алгеброй, которая теперь носит его имя

В то время как Гамильтон разрабатывал свою кватернионную алгебру, Грассман формулировал свою собственную алгебру, ключом к которой было введение внешнего произведения; мы обозначаем это внешнее произведение как , так что внешнее произведение двух векторов a и b записывается как a b. Это произведение имеет определенные особенности. Одной из таких особенностей является его ассоциативность, т. е.

\mathbf a \wedge (\mathbf b \wedge \mathbf c) = (\mathbf a \wedge \mathbf b) \wedge \mathbf c

То, как мы группируем множители, не имеет значения. Другая особенность антикоммутативность, то есть, если мы изменим порядок векторов во внешнем произведении, то изменим его знак:

\mathbf{a}\wedge\mathbf{b} = -\mathbf{b}\wedge\mathbf{a}

Мы больше привыкли иметь дело с коммутативным произведением, то есть умножением между двумя числами, 25 = 52 = 10, но оказывается чрезвычайно полезным во многих областях физики, математики и техники иметь произведение, которое не обязательно коммутирует. Напротив, внутреннее (скалярное) произведение между двумя векторами, a и b, записанное как a b (что дает скаляр, величина которого равна ab cos , где угол между векторами), является коммутативным, т. е.

\mathbf a \cdot \mathbf b = \mathbf b \cdot \mathbf a

Грассман, немецкий школьный учитель, был в значительной степени проигнорирован при жизни, но после его смерти его работа стимулировала модные области дифференциальных форм и грассмановских (антикоммутирующих) переменных. Последние имеют фундаментальное значение для основ современной суперсимметрии и теории суперструн.

 Портрет Уильяма Кингдона Клиффорда (1845-1879), математика и философа, работы достопочтенного Дж. Джон Кольер. (Библиотека и архив Королевского общества.) Портрет Уильяма Кингдона Клиффорда (1845-1879), математика и философа, работы достопочтенного Дж. Джон Кольер. (Библиотека и архив Королевского общества.)

Следующий решающий этап истории происходит в 1878 году и связан с работой английского математика Уильяма Кингдона Клиффорда. Клиффорд был одним из немногих математиков, которые читали и понимали работу Грассмана, и в попытке объединить алгебры Гамильтона и Грассмана в единую структуру он ввел свою собственную геометрическую алгебру. В этой алгебре мы имеем одно геометрическое произведение, образованное объединением внутреннего и внешнего произведений; оно ассоциативно, как произведение Грассмана, но также обратимо, как произведения в алгебре Гамильтона. В геометрической алгебре Клиффорда уравнение типа ab = C имеет решение b = aC, где a существует и известно как обратное от a. Ни внутреннее, ни внешнее произведение не обладают этой обратимостью сами по себе. Большая часть силы геометрической алгебры заключается в этом свойстве обратимости.

Алгебра Клиффорда объединила все преимущества кватернионов с преимуществами векторной геометрии, так что геометрическая алгебра должна была тогда идти вперед как основная система математической физики. Однако два события помешали этому. Первой была безвременная смерть Клиффорда в возрасте всего 34 лет, а второй введение Гиббсом своего векторного исчисления. Векторное исчисление хорошо подходило к теории электромагнетизма в том виде, в каком она существовала в конце XIX века; это, а также значительная репутация Гиббса, привели к тому, что его система затмила работу Клиффорда и Грассмана. Ирония заключается в том, что сам Гиббс, похоже, был убежден, что подход Грассмана к множественным алгебрам был правильным.

С появлением специальной теории относительности физики поняли, что им нужна система, способная обрабатывать четырехмерное пространство, но к этому времени важнейшие идеи Грассмана и Клиффорда уже давно затерялись в бумагах конца 19-го века. В 1920-х годах алгебра Клиффорда вновь появилась как алгебра, лежащая в основе квантового спина. В частности, алгебра спиновых матриц Паули и Дирака стала незаменимой в квантовой теории. Однако к ним относились просто как к алгебрам: геометрический смысл был утрачен. Соответственно, мы будем использовать термин "алгебры Клиффорда", когда он используется исключительно в формальной алгебре. Говоря же о геометрической постановке, мы используем название данное Клиффордом геометрическая алгебра. Это также уступка Грассману, который фактически первым записал геометрическое (клиффордовское) произведение!

Ситуация оставалась в значительной степени неизменной до 1960-х годов, когда Дэвид Хестенес начал восстанавливать геометрический смысл алгебр Паули и Дирака. Хотя его первоначальная мотивация состояла в том, чтобы получить некоторое представление о природе квантовой механики, он очень скоро понял, что при правильном применении система Клиффорда была не чем иным, как универсальным языком для математики, физики и инженерии. Опять же, эта замечательная работа в значительной степени игнорировалась около 20 лет, но сегодня интерес к системе Гестенеса набирает обороты. В настоящее время во всем мире существует множество групп, работающих над применением геометрической алгебры к таким различным темам, как черные дыры и космология, квантовое туннелирование и квантовая теория поля, динамика пучков и дефформации, компьютерное зрение и робототехника, свертывание белков, нейронные сети и автоматизированное проектирование. Во всем используется одна и та же алгебраическая система, позволяющая людям одновременно вносить вклад в ряд этих областей

Краткий обзор

В нашей геометрической алгебре мы начинаем со скаляров, то есть обычных чисел, которые имеют величину, но не связаны с ориентацией, и векторов, то есть направленных отрезков как с величиной, так и с ориентацией/направлением. Давайте теперь возьмем эти векторы и посмотрим немного более внимательно на геометрию, лежащую за внешним произведением Грассмана. Внешнее произведение между двумя векторами a и b записывается как a b и представляет собой новую величину, называемую бивектором. Бивектор a b это направленная область, охватываемая двумя векторами a и b; таким образом, внешнее произведение двух векторов является новой математической сущностью, кодирующей понятие ориентированной плоскости.

Если мы пронесем b вдоль а, то получим тот же бивектор, но с противоположным знаком (ориентацией). Теперь, расширяя эту идею, мы видим, что внешнее произведение между тремя векторами, a b с, получается путем выметания бивектора a b вдоль c, что дает ориентированный объем или тривектор. Если мы пронесем a через область, представленную бивектором b с, мы получим тот же самый тривектор (можно показать, что он имеет ту же самую "ориентацию"); этот факт выражает ассоциативность внешнего произведения.

В n-мерном пространстве у нас будут n-векторы, которые являются просто ориентированными n-объемами; таким образом, мы видим, что внешнее произведение легко обобщается на более высокие измерения, в отличие от векторного произведения Гиббса, которое ограничено тремя измерениями. Решающий шаг в развитии геометрической алгебры теперь происходит с введением геометрического произведения. Мы уже знаем, что такое a b и a b; геометрическое произведение же их объединяет:

\mathbf{ab} = \mathbf a \cdot \mathbf b + \mathbf a \wedge \mathbf b

Этот шаг суммирования двух различных объектов не является совершенно чуждым актом; на самом деле мы уже давно делаем то же самое при выполнении операций с комплексными числами. Оказывается, что многие величины в физике могут быть выражены очень сжато и эффективно в терминах мультивекторов (линейные комбинации n-векторов, например скаляр плюс бивектор и т. д.); действительно, такое объединение объектов разных типов, по-видимому, происходит на глубоком уровне физической теории.

Геометрическая алгебра в двух измерениях

В двух измерениях (на плоскости) любая точка может быть достигнута путем принятия различных линейных комбинаций двух векторов с различными направлениями; мы говорим, что пространство тогда охватывается этими двумя базисными векторами. Теперь пусть эти два вектора ортонормированы, т. е. единичной длины и перпендикулярные друг другу, и назовем их e и e. Или на языке формул

\mathbf{e_1}^2 = \mathbf{e_2}^2 = 1 \\ \mathbf{e_1}\cdot\mathbf{e_2} = 0

Единственным новым элементом в нашей двумерной геометрической алгебре является бивектор e e; это самый высокий класс элемента в алгебре (часто называемый псевдоскаляром). Рассмотрим теперь свойства этого бивектора. Первое, на что следует обратить внимание

\mathbf{e_1e_2} = \mathbf{e_1} \cdot \mathbf{e_2} + \mathbf{e_1} \wedge \mathbf{e_2} = \mathbf{e_1} \wedge \mathbf{e_2} = - \mathbf{e_2} \wedge \mathbf{e_1} = -\mathbf{e_2e_1}

то есть геометрическое произведение является чистым бивектором, потому что перпендикулярность векторов гарантирует, что e e обращается в нуль. Теперь давайте разберем этот бивектор:

( \mathbf{e_1e_2} )^2 = \mathbf{e_1e_2e_1e_2} = -\mathbf{e_1e_1e_2e_2} = \mathbf{(e_1)^2 (e_2)^2} = -1

Обратите внимание, что у нас есть реальная геометрическая величина, которая в квадрате равна -1! Поэтому возникает соблазн связать эту величину с единицей мнимой комплексной системы счисления (комплексное число принимает форму x + iy, где i известна как мнимая единица и обладает свойством i = -1). Таким образом, в двух измерениях геометрическая алгебра воспроизводит свойства комплексных чисел, но использует только геометрические объекты. На самом деле, переходя к геометрическим алгебрам более высоких измерений, мы начинаем видеть, что есть много объектов, которые квадратичны к -1, и что мы можем использовать их все в их правильной геометрической постановке.

Давайте теперь посмотрим, что происходит, когда бивектор ee умножается на векторы слева и справа. Умножение e и e слева дает

 (\mathbf{e_1 e_2}) \mathbf{e_1} = - \mathbf{e_2 e_1 e_1} = - \mathbf{e_2} \\ (\mathbf{e_1e_2}) \mathbf{e_2} = \mathbf{e_1 e_2 e_2} = \mathbf{e_1}

Легко заметить, что умножение слева на бивектор вращает векторы на 90 по часовой стрелке. Точно так же, если мы умножаем справа, мы вращаемся на 90 против часовой стрелки

 \mathbf{e_1(e_1e_2)} = \mathbf{e_2} \\ \mathbf{e_2(e_1e_2)} = -\mathbf{e_1}

Вращения

Из свойств бивектора ee очень легко показать, что поворот вектора a на угол к вектору a' достигается уравнением

\mathbf{a^\prime} = R\mathbf{a}P

где R величина, которую мы будем называть ротором и которая состоит из суммы скаляра и бивектора

R = \cos\frac \theta 2 - \mathbf{e_1e_2}\sin\frac \theta 2

а P это то же самое выражение, но с "+". На первый взгляд это может показаться довольно громоздким выражением для выполнения простого двумерного вращения; однако оказывается, что оно обобщается на более высокие измерения и поэтому обладает огромной силой.

Ротор R, переводящий вектор a в вектор a'. Обратите внимание, что понятие перпендикулярного вектора больше не требуется; важен бивектор или плоскость вращения.Ротор R, переводящий вектор a в вектор a'. Обратите внимание, что понятие перпендикулярного вектора больше не требуется; важен бивектор или плоскость вращения.

Приведенное выше уравнение фактически является формулой, которая используется для вращения вектора в любом измерении; если мы перейдем к трем измерениям, ротор R будет вращаться на угол в плоскости, описываемой бивектором. Поэтому все, что нам нужно сделать, это заменить бивектор ee на бивектор, который определяет плоскость вращения. И все; используя это очень простое выражение, мы обнаружим, что можем вращать не только векторы, но и бивекторы и более высокоуровневые величины. Осуществить вращение в трех измерениях таким образом, чтобы расширить понятия, которые мы понимали в двух измерениях, было проблемой, с которой Гамильтон боролся в течение многих лет, прежде чем, наконец, получить в качестве своего решения кватернионы. На самом деле элементы кватернионной алгебры Гамильтона это не что иное, как элементарные бивекторы (плоскости). Вооружившись очень простой идеей ротора, который совершает вращения, мы можем дать удивительно простые геометрические интерпретации многих других сложных объектов.

Специальная теория относительности

Специальная теория относительности была введена в 1905 году и возвестила начало новой эры в физике; отход от чисто классического режима ньютоновской физики. В специальной теории относительности (СТО) мы имеем дело с четырехмерным пространством: тремя измерениями обычного евклидова пространства и временем. Предположим, что у нас есть стационарный наблюдатель, с которым мы можем связать координаты пространства и времени, и этот наблюдатель будет наблюдать события со своего пространственно-временного положения. Теперь предположим, что у нас есть другой наблюдатель, движущийся со скоростью v; он тоже будет наблюдать события из своего непрерывно меняющегося пространственно-временного положения.

Проблема того, как два наблюдателя воспринимают различные события, относительно проста, когда скорость |v| мала. Но когда |v| приближается к скорости света, c, и мы добавляем тот факт, что она должна быть постоянной в любой системе, и математика становится уже не такой простой. Условно можно получить преобразование координат между системами отсчета обоих наблюдателей, и для перемещения между этими двумя системами мы применяем матричное преобразование, известное как преобразование Лоренца. Геометрическая алгебра дает нам прекрасно простой способ работы со специальными релятивистскими преобразованиями, используя не что иное, как формулу для вращений, рассмотренную выше, а именно a' = RaP. Наше пространство теперь имеет четыре измерения, и наши базисные векторы это три пространственных направления и одно временное направление; назовем эти базисные векторы , , и . Для четырех измерений, у нас будет шесть бивекторов (три пространственных бивектора плюс бивекторы, состоящие из пространственно-временных "плоскостей").

Иллюстрация четырехмерных пространственно-временных осей. Показан один из пространственно-временных бивекторов, который, как и прежде, определяет плоскость в нашем пространстве и поэтому может быть использован для вращения осей.Иллюстрация четырехмерных пространственно-временных осей. Показан один из пространственно-временных бивекторов, который, как и прежде, определяет плоскость в нашем пространстве и поэтому может быть использован для вращения осей.

Преобразование Лоренца оказывается просто ротором R, который переводит ось времени в другое положение в четырех измерениях: RP. Таким образом, элегантным бескоординатным способом мы можем придать преобразованиям СТО интуитивный геометрический смысл. Все обычные результаты СТО совершенно естественно следуют из этой отправной точки. Например, сложные формулы для преобразования электрического (Е) и магнитного (В) полей при лоренцевом ускорении заменяются (гораздо более простым!) результатом

\mathbf {E^\prime} + I\mathbf {B^\prime} = R(\mathbf {E} + I\mathbf {B} )P

где I = псевдоскаляр четырехмерного пространства (4-объем), а штрихами обозначаем преобразованные величины.

Квантовая механика

В нерелятивистской квантовой механике существуют важные величины, известные как спиноры Паули; используя эти спиноры, мы можем записать уравнение Паули, которое управляет поведением квантово-механического состояния в некотором внешнем поле. Уравнение включает в себя величины, называемые спиновыми операторами, которые обычно рассматриваются как совершенно разные сущности для состояний. Используя трехмерную геометрическую алгебру, мы можем записать эквивалент уравнения Паули, в котором операторы и состояния являются мультивекторами реального пространства; действительно, спиноры становятся роторами того типа, о котором мы говорили ранее.

К тому же, переход к релятивистской квантовой механике будет сравнительно прост. Условно она описывается алгеброй Дирака, где уравнение Дирака говорит нам о состоянии частицы во внешнем поле. На этот раз мы используем четырехмерную геометрическую алгебру пространства-времени, и снова волновая функция в обычной квантовой механике становится инструкцией по вращению базисного набора осей и выравниванию их в определенных направлениях: аналогично теории механики твердого тела! Простота такого подхода имеет некоторые интересные последствия. При решении уравнения Дирака для некоторого внешнего потенциала А, видя, куда повернута временная ось , мы можем построить линии тока (линии, которые дают направление скорости частицы в каждой точке) движения частицы. Сравнение с общепринятой теорией можно проиллюстрировать простым примером.

Рассмотрим случай, когда пакет частиц с энергией, скажем, 5 эВ сталкивается с прямоугольным барьером потенциалом высотой 10 эВ и конечной шириной, скажем, 5 Ангстрем. Теория квантовой механики позволяет предсказать, что, несмотря на кажущийся непроницаемым барьер, часть пакета действительно возникает с другой стороны. Эффект называется туннелированием, и он имеет фундаментальное значение во многих современных полупроводниковых приборах. Однако, когда мы задаем кажущийся очевидным вопрос о том, сколько времени туннелирующая частица проводит внутри барьера, квантовая теория дает нам множество ответов:

  1. такое не обсуждается, поскольку время не является эрмитовой наблюдаемой;

  2. время тождественно нулю;

  3. время является мнимым.

Почему квантовая механика делает такие странные предсказания? Основная причина неспособности иметь дело с траекторией частицы/пакета внутри барьера заключается в использовании i, неинтерпретированного мнимого скаляра (i = -1); обычно импульс частицы внутри барьера принимается кратным i, и это приводит ко всяким довольно бесполезным представлениям о мнимом времени.

Однако подход геометрической алгебры говорит нам, что мы должны построить линии тока, представляющие путь частицы внутри барьера, и, следовательно, найти, сколько времени они действительно проводят внутри барьера. Скорее всего, в ближайшем будущем можно будет сравнить время, данное этой теорией, со временем, измеренным в реальных экспериментах. (Это будущее уже наступает - прим. перев.)

На рисунке изображены предсказанные линии тока частиц, начинающих движение из различных позиций внутри волнового пакета энергии 5 эВ, падающего на барьер высотой 10 эВ и шириной 5 Ангстрем, как показано выше. Здесь видно, что линии потока частиц замедляются, находясь в барьере. Это контрастирует с некоторыми недавними обсуждениями сверхсветовых скоростей внутри таких барьеров, которые были выведены из экспериментально наблюдаемого факта, что частицы, туннелирующие через барьер, достигают цели раньше, чем те, которые проходят эквивалентное расстояние в свободном пространстве. Это кажущееся противоречие объясняется здесь тем, что именно частицы вблизи фронта волнового пакета, которые уже имеют фору, передаются и способны достичь цели. Интересно отметить, что большая часть модной в настоящее время области квантовой космологии основана на понятиях мнимого времени.

Гравитация

Электромагнетизм это калибровочная теория. Калибровочная теория возникает, если мы оговариваем, что глобальные симметрии должны также стать локальными симметриями (в электромагнетизме эти симметрии называются фазовыми вращениями); цена, которую нужно заплатить, чтобы достичь этого, это введение сил. В геометрической алгебре гравитацию также можно рассматривать как калибровочную теорию, и здесь симметрии гораздо легче понять. Предположим, что мы требуем, чтобы физика во всех точках пространства-времени была инвариантна при произвольных локальных перемещениях и вращениях (вспомним, что под вращениями в четырех измерениях мы подразумеваем лоренцевы преобразования); калибровочное поле, которое вытекает из такого требования, является гравитационным полем.

Следствием этой теории является огромное упрощение возможности обсуждать гравитацию целиком на плоском пространственно-временном фоне. Нет необходимости в сложных понятиях искривленного пространства-времени, которые мы все привыкли связывать с общей теорией относительности Эйнштейна. Именно здесь подход ГА отличается от прошлых подходов калибровочной теории к гравитации, где эти прошлые теории все еще сохраняли идеи искривленного пространственно-временного фона. Локально гауссова калибровочная теория гравитации воспроизводит все результаты общей теории относительности, но глобально эти две теории будут отличаться, когда речь зайдет о топологии. Например, всякий раз, когда обсуждаются сингулярности или горизонты (как в случае с черными дырами), теория ГА может давать различные предсказания обычной ОТО. Некоторые усовершенствованные методы решения, работающие исключительно с физическими величинами, также были найдены в ГА. Калибровочная теория гравитации ГА имеет дело с экстремальными полями (то есть полями, в которых возникают сингулярности) иначе, чем ОТО. Эти особенности рассматриваются просто способом, аналогичным тому, который используется в электромагнетизме (с использованием интегральных теорем). Взаимодействие с квантовыми полями также отличается и предлагает альтернативный путь к квантовой теории гравитации. В этом контексте интересно также отметить, что многие другие модные попытки объединить гравитацию и квантовую теорию (твисторы, супергравитация, суперструны) также естественным образом вписываются в рамки ГА.

Стержни, оболочки и прогибающиеся балки

Геометрическая алгебра полезна не только в области фундаментальной физики. Концепция системы отсчета, изменяющейся в пространстве или во времени (или и в том, и в другом), лежит в основе многих работ, направленных на понимание деформирующихся тел. Возьмем в качестве простого примера однородную балку, которая подвергается некоторой нагрузке по своей длине; свойства балки и нагрузки будут определять, как она деформируется.

Математически мы можем описать деформацию, разделив балку на очень маленькие сегменты и прикрепив системы координат (три взаимно перпендикулярные оси) к центру масс каждого сегмента. Первоначально, при отсутствии нагрузки и кручения, мы ожидаем, что начало координат каждого набора осей будет находиться вдоль осевой линии балки и что каждая система отсчета будет выровнена так, что ось x будет направлена вдоль длины балки, а ось z вертикально вверх. Теперь, когда луч деформируется, мы можем описать его положение в данный момент времени, указав положение начала координат и ориентацию рамки для каждого сегмента.

Предположим, что у нас есть неподвижная система отсчета на одном конце балки. Тогда система координат на сегменте i будет связана с ней некоторым ротором, R. Таким образом, при движении вдоль балки ориентации описываются ротором, изменяющимся с расстоянием x. Для заданной нагрузки и заданных граничных условий можно было бы решить задачу для роторов, чтобы получить информацию о свойствах изгиба балки. Условно эта задача была выполнена с использованием различных средств кодирования вращений: углов Эйлера, параметров вращения, направляющих косинусов, матриц вращения и т. д. Преимущество использования роторов двоякое: во-первых, они автоматически имеют правильное число степеней свободы (три), в отличие, например, от направляющих косинусов (где у нас девять параметров, только три из которых независимы), а во-вторых, мы можем эффективно решать полные уравнения (без аппроксимаций).

Эту идею варьирования фреймов можно развить еще на одну ступень. Сегодня большая часть исследований в области современной строительной механики стала прерогативой математика. Чтобы иметь дело с тонкими структурами, такими как стержни и оболочки, где при деформации структура поверхности может быть довольно сложной, люди увидели, что области математики, такие как дифференциальная геометрия и дифференциальная топология, могут предоставить полезные инструменты. Действительно, большая часть конечно-элементного кода, используемого сегодня в стандартных конструкторских пакетах, написана на основе алгоритмов, основанных на этой математике. В результате, однако, многие инженеры больше не могут понять работу таких пакетов и должны считать само собой разумеющимся, что то, что они используют, является правильным. С другой стороны, при использовании геометрической алгебры, задача снова сводится к тому, чтобы работать с роторами, которые могут изменяться во времени и/или пространстве на любой заданной поверхности; математика не сложнее, чем можно было бы использовать для решения простых задач механики. Таким образом, внутренний конечно-элементный код становится доступным для инженеров с возможностью его модификации.

Компьютерное зрение и анализ движения

Компьютерное зрение это, по сути, искусство реконструировать или выводить вещи о реальном трехмерном мире из представлений о сцене, снятых одной или несколькими камерами. Положение и ориентация камер могут быть известны, а могут и не быть известны, и внутренние параметры камер (которые определяют, насколько изображения, которые мы видим, отличаются от тех, которые были бы результатом идеальной проекции на плоскость изображения) также могут быть неизвестны. Из этого довольно упрощенного описания видно, что будет задействовано значительное количество трехмерной геометрии. Фактически, с середины 1980-х годов большая часть компьютерного зрения была написана на языке проективной геометрии.

В классической проективной геометрии мы определяем трехмерное пространство, точки которого соотносятся линиям проходящим через некоторое начало координат (заданную точку) в четырехмерном пространстве. Использующая такую систему алгебра инцидентности (пересечения линий, плоскостей и т. д.) чрезвычайно изящна, и, кроме того, преобразования, которые кажутся сложными в трех измерениях (например, проекция точек, линий и т. д. вниз на данную плоскость), теперь становятся простыми. В последние годы люди начали использовать алгебру, называемую алгеброй Грассмана-Кэли для проективных геометрических вычислений и манипуляций; это фактически внешняя алгебра Грассмана, поскольку она ограничивает себя использованием только внешнего произведения. Геометрическая алгебра содержит внешнюю алгебру как подмножество и, следовательно, является идеальным языком для выражения всех идей проективной геометрии. Однако у ГА также есть понятие внутреннего произведения, часто позволяющее нам делать вещи, которые были бы очень трудными при наличии только внешнего произведения.

Чтобы проиллюстрировать еще один способ использования геометрической алгебры в компьютерном зрении, рассмотрим задачу, возникающую при анализе движения, при реконструкции сцены и регистрации изображения (мозаика ряда различных, перекрывающихся изображений при наличии ограниченной информации). Предположим, что у нас есть несколько камер, наблюдающих за объектом. Также предположим, для удобства, что маркеры размещены на объекте так, чтобы эти точки можно было легко извлечь из изображений.

На рисунке показан эскиз системы с тремя камерами. Теперь, если мы наблюдаем сцену, скажем, с помощью M камер, мы обнаружим, что в каждой паре камер есть подмножество общего числа маркеров, которые видны. Первая задача состоит в том, чтобы найти, используя эти М изображений, наилучшие оценки относительных положений и ориентаций каждой камеры. Как только мы узнаем положение камер, мы хотели бы провести триангуляцию, чтобы найти трехмерные координаты других точек мира, видимых на ряде изображений; эти задачи не слишком сложны для точно известных точек изображения, но становятся намного сложнее, если эти точки зашумлены. Конечно, существуют общепринятые методы решения этих проблем.

Действительно, фотограмметристы делают именно это в течение многих лет. Однако решения, как правило, требуют больших оптимизаций, которые часто нестабильны. Вот тут-то и может помочь геометрическая алгебра. Используя ГА, можно решить как калибровочные, так и триангуляционные задачи таким образом, чтобы одновременно учитывать все данные с каждой камеры. Оптимизации, участвующие в решениях, способны использовать как первую, так и вторую аналитическую (в отличие от численной) производную всех величин, которые должны быть оценены согласованным образом. Обычно гораздо сложнее взять производные от величин, представляющих вращения. Используя ГА таким образом, можно получить точные решения при одновременном снижении вычислительной нагрузки, что делает его полезным в приложениях, требующих множества таких оптимизаций.

Выводы

Мы попытались дать краткое введение в математическую систему, которую мы называем геометрической алгеброй, и проиллюстрировать ее полезность в различных областях. Хотя мы обсуждали целый ряд тем от квантовой механики до изгибающихся балок, есть много убедительных примеров использования ГА в физике и технике, которые мы не обсуждали. К ним относятся электромагнетизм, поляризация, геометрическое моделирование и линейная алгебра. Современные инструменты математики, с которыми большинство из нас знакомо, разнообразны и сложны. За одну жизнь исследований мы можем надеяться овладеть лишь очень немногими областями. Однако, если бы большинство физиков и математиков использовали один и тот же язык, ситуация, возможно, была бы иной. Мы надеемся, что в этой статье мы показали, что геометрическая алгебра является кандидатом на такой единый язык.

P.S.

Статья вышла в свет в 2000 году. И хотя с тех пор геометрическая алгебра может и не стала универсальным языком точных наук, но все же, она нашла множество применений и продолжает завоевывать сердца и умы исследователей по всему миру. Так что, было бы полезным продолжить дальнейшее погружение:

  1. Для начала следует уяснить отличия от алгебраической геометрии. Там тоже есть замахи на универсальность. В качестве примера можно посоветовать наработки Джона Баэза. Да и вообще, его блог стоит отдельного внимания.

  2. Про сравнение с векторной алгеброй смотрим в Википедии.

  3. Видео-лекция от одного из авторов статьи (спасибо, @sergehog).

  4. Поднимаем планку: более современное введение в ГА.

  5. Свежая книжка с приложениями.

  6. Более-200-страничный опус от одного из авторов.

  7. Grassmann.jl пакет для языка Julia

  8. + еще множество источников на одном сайте.

Подробнее..

Перевод Как решать упрямые уравнения?

20.05.2021 20:12:40 | Автор: admin

Учителя математики сотни лет мучили учеников, загоняя коз в поля странной формы. Из этой статьи вы узнаете, почему одна задачка о пасущихся козах уже более века не даёт покоя математикам. Если вы когда-нибудь сдавали экзамен по математике, то наверняка вам задавали задачку про пасущуюся козу. Её смысл заключается в следующем: рассеянный фермер оставил козу привязанной к столбу у забора или сарая, и теперь она подъедает вокруг себя всю траву, до которой может дотянуться. Ваша задача рассчитать общую площадь, на которой может пастись коза. Давно ли вы проходили математическое тестирование?


Учителя математики сотни лет мучили учеников, загоняя коз в поля странной формы, но одна конкретная проблема с пасущимися козами не даёт покоя математикам уже более ста лет. До прошлого года им удавалось решать такие проблемы лишь приблизительно, и для получения точного решения потребовалось применение нового подхода с использованием самых современных математических методов. Давайте посмотрим, как, казалось бы, элементарная задачка, предлагаемая студентам на экзамене по математике, может превратиться в проблему, уже более века ставящую математиков в тупик.

В самом простом варианте задачи голодное животное привязывается к боковой стенке длинного сарая верёвкой фиксированной длины.

Обычно в таких задачах просят определить площадь области, в которой может перемещаться коза на верёвке. Как выглядит эта область?

Натягивая верёвку, коза описывает полукруг и, соответственно, может дотянуться до всего, что находится внутри этого полукруга. Вот формула площади круга:

A = r^2

Значит, площадь полукруга в два раза меньше:

A = \frac12r^2

При длине верёвки 4 коза выщипает площадь (в квадратных единицах), равную

A = \frac12 4^2 = 8

Решение этой элементарной задачи не представляет особой сложности ни для математика, ни для козы, поэтому давайте сделаем её интереснее. Что, если коза будет привязана к боковой стенке сарая квадратной формы?

Предположим, что длина верёвки и длина стороны сарая равны 4 и что верёвка прикреплена к середине одной из сторон. На какой площади теперь может пастись коза? Коза по-прежнему может пастись в том же полукруге, что и в первой задаче.

Но она также может заходить за угол сарая. Дойдя до угла, коза может использовать ещё два участка верёвки, то есть может выщипать ещё четверть круга радиусом 2 по обе стороны сарая.

Коза может попасть в полукруг радиуса 4 плюс ещё в две четверти круга радиуса 2, общая площадь которых в квадратных единицах составляет

A = \frac12 4^2 + \frac14 2^2 + \frac14 2^2 = 10

Задачу можно усложнить, изменив форму препятствия. Я видел задачи с козами, привязанными к треугольникам, шестиугольникам и даже к вогнутым формам.

Также можно задать новое условие математической задачи, изменив её вопрос на противоположный: не указывать длину верёвки и просить найти площадь, а указать площадь и просить найти длину верёвки.

Давайте вернёмся к нашему квадратному сараю и зададим новый вопрос: какой длины должна быть верёвка, чтобы коза имела доступ к 50 квадратным единицам площади? Постановка математической задачи под новым углом может вдохнуть новую жизнь в старую идею, но при этом решение такой задачи может оказаться гораздо более сложным.

Во-первых, обратите внимание, что форма области зависит от длины верёвки. Например, если длина верёвки меньше 2 единиц, коза не сможет обогнуть угол сарая, поэтому формой области будет полукруг.

Если длина верёвки больше 2 единиц, коза сможет обогнуть угол.

А если длина верёвки будет больше 6 единиц, коза может добраться до задней части сарая и выщипать там ещё пару четвертей круга. (Если верёвка достаточно длинная, области будут перекрываться. Соответствующий пример приведён в упражнениях в конце статьи.)

Нам необходимо найти длину верёвки, при которой общая площадь будет составлять 50 квадратных единиц. Математически это можно выполнить следующим образом: подставить в формулу площадь, равную 50, и решить это уравнение относительно r. Но для каждой области имеется своя формула расчёта площади. Какую же использовать?

Для того чтобы это выяснить, проведём небольшие вычисления. Если r 2, площадь области составит

A = \frac12r^2

Самая большая площадь будет при r = 2, то есть общая площадь составит

A = \frac12 2^2 = 2 6,28

Это меньше 50, поэтому нам нужно более 2 единиц верёвки.

Если 2 < r 6, мы получаем полукруг плюс две четверти круга. Радиус полукруга равен r, а радиус четверти круга равен r 2, так как для того, чтобы добраться до угла, потребуется две единицы верёвки, а оставшаяся верёвка выступает в качестве радиуса четверти круга с центром в углу сарая.

Площадь этого полукруга равна

\frac12r^2

А площадь каждой четверти круга равна

\frac14(r 2)^2

Просуммировав выражения, получим общую площадь:

\begin{aligned}A&=\frac{1}{2} \pi r^{2} +\frac{1}{4}\pi (r-2)^{2} + \frac{1}{4}\pi (r-2)^{2}\\[1pt] \\A &=\frac{1}{2} \pi r^{2} + \frac{1}{2}\pi (r-2)^{2}.\end{aligned}

Наибольшую возможную площадь мы получим при r = 6, что даёт

A = \frac12 6^2 + \frac12 4^2 = 26 81,68

квадратных единиц. Поскольку 50 < 26, это означает, что значение r, дающее 50 квадратных единиц площади, должно быть меньше 6.

Знание того, что значение r должно быть от 2 до 6 единиц, снимает вопрос о том, какую формулу для расчёта площади нужно использовать: если 2 < r 6, площадь

A = \frac12r^2 + \frac12(r 2)^2

Чтобы найти точное значение r, которое даст 50 квадратных единиц площади, составим такое уравнение:

50 = \frac{1}{2}r^2 + \frac{1}{2}(r 2)^2.

Видите, я был прав, говоря, что перевёрнутую задачу решать сложнее, чем оригинальную: вместо того чтобы просто вычислить площадь, которую может выщипать коза, нам нужно решить уравнение, чтобы определить длину верёвки. Для этого нужно выделить r. Чтобы перенести r в одну сторону уравнения и узнать, таким образом, его точное значение, используем арифметические и алгебраические методы.

Сначала наше уравнение может показаться немного пугающим, но по отношению к r это всего лишь квадратное уравнение. Существует стандартная процедура решения таких уравнений: представим его в форме

ar^2 + br + c = 0

а затем воспользуемся формулой для решения квадратных уравнений. Немного алгебры и арифметики делают своё дело.

50 = \frac{1}{2}r^2 + \frac{1}{2}(r 2)^2\frac{100}{\pi} = r^2 + (r 2)^2\frac{100}{\pi} = 2r^2 4r + 40 = 2r^2 4r + 4 \frac{100}{\pi}.

Возможно, это не самое красивое математическое выражение в мире, но это всего лишь квадратное уравнение, с помощью которого можно найти точное значение r. Получаем ответ:

Поскольку мы смогли выделить r в уравнении, теперь мы точно знаем, какой длины должна быть верёвка, чтобы получить площадь в 50 квадратных единиц. (Обратите внимание, что найденное нами значение r, как и предполагалось, находится в пределах от 2 до 6.)

Думаете, это самая заковыристая задача с козой у сарая? Как бы не так! Математики обнаружили, что задача становится ещё более сложной, если поместить козу внутрь сарая.

Поместим козу внутрь квадратного сарая с длиной стороны 4 и прикрепим верёвку к середине стены. Какой длины должна быть верёвка, чтобы коза могла выщипать половину площади внутри сарая?

Как было сказано выше, часть проблемы заключается в том, что форма области зависит от значения r. Чтобы получить половину площади квадрата, нужно, чтобы значение r было больше половины длины стороны сарая, но меньше полной длины стороны, что даёт нам примерно такую область.

Найти формулу для такой площади не так просто. Мы можем представить область как один сектор круга радиуса r плюс два правильных треугольника, а затем для получения формулы воспользоваться геометрическими навыками из курса средней школы. Но, как мы скоро убедимся, смешение кругов и треугольников приведёт к ряду проблем.

Начнём с треугольников. Согласно теореме Пифагора длины катетов в каждом правильном треугольнике равны

\sqrt{r^{2}-4}

Таким образом, площадь одного из треугольников равна

\frac{1}{2}2\sqrt{r^{2} 4}=\sqrt{r^{2} 4}

Поэтому суммарная площадь обоих треугольников равняется

2\sqrt{r^{2}-4}

Перейдём к круговому сектору.

Площадь сектора равняется

A = \frac12r^2

где значение центрального угла (в радианах, не в градусах). Нам нужна формула для расчёта площади через r, для этого необходимо выразить угол через r. Для этого воспользуемся теоремой косинусов самой недооценённой теоремой из школьного курса тригонометрии.

Применяя теорему косинусов к равнобедренному треугольнику со сторонами r, r и 4, получаем:

4^2 = r^2 + r^2 - 2r^2\cos{\theta},

и это уравнение можно решить для cos:

\cos{\theta} = \frac{2 r^{2}-16}{2 r^{2}} = \frac{r^{2}-8}{r^{2}}

Чтобы выделить , нужно взять обратный косинус, или арккосинус, от обеих сторон уравнения. Это даёт:

\theta = \arccos{\left(\frac{r^{2}-8}{r^{2}}\right)}

Теперь у нас имеется угол , выраженный через r, поэтому площадь нашего сектора можно выразить только в r:

A = \frac12r^2\thetaA = \left(\frac{r^{2}-8}{r^{2}}\right) + 2\sqrt{r^{2}-4}

Окончательная формула площади это сумма площади сектора и площадей двух треугольников, то есть:

Мы получили формулу для расчёта площади области, в которой может перемещаться коза внутри квадрата, полностью через r. Теперь нужно просто найти значение r, дающее козе доступ к половине площади. Площадь всего квадрата равна 16, поэтому нам остаётся только подставить в наше уравнение A = 8, решить его относительно r, и дело сделано.

8 = \left(\frac{r^{2}-8}{r^{2}}\right) + 2\sqrt{r^{2}-4}

Однако возникает одна небольшая проблема: это уравнение невозможно решить относительно r.

Вернее, это уравнение невозможно решить точно относительно r. Для приблизительного определения значения r можно использовать калькулятор (получится примерно 2,331), но выделить r в нашем уравнении нельзя. Сочетание в уравнении тригонометрических и полиномиальных функций создаёт непреодолимые препятствия для его точного разрешения относительно r.

Можно попытаться вывести r из функции арккосинуса, но для этого придётся поместить другие r в функцию косинуса. В любом случае наше уравнение будет содержать трансцендентную функцию, например экспоненциальную или тригонометрическую. Трансцендентные функции нельзя выразить в терминах обычных алгебраических операций, таких как сложение и умножение, и поэтому в общем случае трансцендентные уравнения не подлежат точному решению.

Эта особенность трансцендентных функций лежит в основе известной проблемы XIX века о пасущейся козе, помещённой внутрь круглого сарая. Как и в нашей задаче с квадратным сараем, задача XIX века состояла в том, чтобы определить, какой длины должна быть верёвка, чтобы коза могла выщипать половину области.

Доступная для козы область имеет форму "линзы" два сложенных вместе круговых сегмента.

Площадь такой линзы можно, используя школьные знания по геометрии, определить по длине верёвки, однако формула получается намного сложнее, чем для квадрата. Если установить эту площадь равной половине площади круглого сарая, мы столкнемся с той же проблемой, что и при наших расчётах для козы внутри квадрата: Выделить r из уравнения не удастся. Значение r можно посчитать приближённо, но точно никогда.

Подобное упрямство уравнения сродни упрямству козы, не находите? Более 100 лет математики пытались найти точное решение головоломки "коза в круге", но только в прошлом году немецкий математик наконец её разгадал. Для поиска точного значения r он использовал методы комплексного анализа области математики, далёкой от геометрии кругов и квадратов, на которой основывается большинство задач о козах. И, хотя применение такого продвинутого математического инструмента, как контурный интеграл, для определения длины верёвки, к которой привязана коза, может показаться излишеством, всегда чувствуешь математическое удовлетворение после того, как делаешь то, что раньше считалось невозможным. И всегда существует вероятность, что эти новые методы, даже если они возникли в результате изучения детской задачки о козе, могут привести к открытиям, выходящим за границы деревенского сарая.

Упражнения

1. Если коза привязана к середине стороны квадратного сарая с длиной стороны 4 верёвкой длиной 8 единиц за пределами сарая, какова площадь области, которую может выщипать коза?

2. Если коза привязана к углу квадратного сарая с длиной стороны 4 верёвкой длиной 8 за пределами сарая, какова площадь области, которую может выщипать коза?

3. Предположим, что коза находится внутри равностороннего треугольника со стороной 4 и привязана к одной из его вершин. Какой длины должна быть верёвка, чтобы коза могла выщипать половину площади треугольника?

4. Если коза привязана к середине стороны квадратного сарая с длиной стороны 4 верёвкой длиной 10 за пределами сарая, какова площадь области, которую может выщипать коза?


Ответ на задачу 1

Область состоит из полукруга радиуса 8, двух четвертей окружности радиуса 6 и двух четвертей окружности радиуса 2. Поскольку 8 равно половине периметра сарая, два полукруга за сараем пересекаются в середине.

\frac12 8^2 + \frac12 6^2 + \frac12 2^2 = 52

Эта площадь состоит из трёх четвертей площади окружности радиуса 8 и двух четвертей площади окружности с радиусом 4.

И она равна

\frac{1}{2} 8^2 + \frac12 6^2 + \frac12 2^2= 56
Ответ на задачу 2

Эта область состоит из трёх четвертей окружности радиуса 8 и двух четвертей окружности радиуса 4.

И она равна

\frac34 8^2 + \frac12 4^2 = 56

Подумайте, что произойдёт, если длина верёвки будет равна 10.

Ответ на задачу 3

Поскольку углы равностороннего треугольника равны 60, доступная козе площадь составляет одну шестую часть круга радиуса r, площадь которой равна

\frac16r^2

Площадь равностороннего треугольника равна

\frac{\sqrt{3}}{4}s^2

Поэтому площадь треугольника с длиной стороны 4 равна

\frac{\sqrt{3}}{4} 4^2=4\sqrt3

Положим обе площади равными

\frac16r^2 = \frac12 4 \sqrt3

И с помощью этой формулы выразим r. Мы получим

r=\sqrt{\frac{12 \sqrt{3}}{\pi}}

Обратите внимание, что здесь мы можем точно определить r в отличие от случая, когда в области смешаны круговые секторы и треугольники.

Ответ на задачу 4

Площадь, по-видимому, состоит из полукруга радиуса 10, двух четвертей окружности радиуса 8 и двух четвертей окружности радиуса 4. Эта площадь составляет

\frac12 10^2 + \frac12 8^2 + \frac12 4^2 = 90

Но последние две четверти круга пересекаются за сараем.

Это перекрытие было учтено дважды, поэтому нам нужно вычесть его площадь из 90. Область перекрытия можно представить как две шестые окружности радиуса 4 минус равносторонний треугольник со стороной 4. Площадь этой области составляет

 2 \frac16 4^2 - \frac{\sqrt{3}}{4} 4^2 = \frac{16}{3} - 4{\sqrt{3}}

Таким образом, общая площадь равна

90 - \left(\frac{16}{3} \pi-4 \sqrt{3}\right) = \frac{254}{3} + 4 \sqrt3

Примечание: это пересечение было бы гораздо сложнее найти, если бы две окружности имели разные радиусы, именно поэтому так трудно найти площадь линзы, о которой говорилось выше.

Если вам интересна не только математика, но и её практические приложения, вы можете обратить внимание на курс по Data Science: область науки о данных развивается и будет актуальна как минимум в ближайшие десять лет.

Узнайте, как прокачаться и в других специальностях или освоить их с нуля:

Другие профессии и курсы
Подробнее..

Быстрый поиск касательных и пересечений у выпуклых многоугольников

15.11.2020 18:09:06 | Автор: admin

Я недавно сделал маленькую библиотеку для решения задачи поиска кратчайшего пути на 2D карте с выпуклыми препятствиями. В процессе реализации я придумал пару алгоритмов и трюков, описания которых я нигде не встречал. Поэтому делюсь этими "изобретениями" с общественностью.


Горжусь тем, что мое решение работает очень быстро. Для внушительного количества полигонов все операции можно выполнять каждый кадр. Т.е. не надо ничего запекать и вся геометрия карты может меняться в каждом кадре.


Касательные


Некоторые читатели могут возмутиться, что к полигонам, как не дифференцируемым кривым, касательных нет. Но тут я использую термин не из матанализа с таким же названием. В моем случае касательная к полигону это прямая, пересекающая его ровно в одной точке, или проходящая через сторону.


Откуда вообще эти касательные берутся? Несложными рассуждениями можно доказать, что все кратчайшие пути на карте с выпуклыми полигонами-препятствиями состоят из отрезков прямых, которые или совпадают со стороной одного из препятствия, или обоими концами являются или концом пути или касаются какого-то полигона.


Доказательство

Доказательство от противного. Допустим в кратчайшем пути какая-то часть не является прямым отрезком, или является прямым отрезком, не совпадающим со стороной полигона и один из его концов не является концом пути или касательной. У кривой всегда можно чуть-чуть срезать "угол". Ведь эта кривая не может идти по границе полигона, который состоит из прямых отрезков. Противоречие с тем, что путь кратчайший. Далее будем считать, что путь состоит из прямых отрезков.


Если же отрезок просто висит концом в пространстве или лежит на границе полигона, но не является касательной к нему, то можно этот конец чуть чуть подвинуть чтобы выпрямить угол со следующим отрезком, сократив тем самым путь. Опять противоречие.


Единственные случаи, когда мы не можем сократить путь слегка подвинув границу отрезка пути это если отрезок уже совпадает со стороной полигона или касается его.


Все случаи выше показаны на картинке. Красным показан какой-то путь, пунктиром сокращенный путь.



Из наблюдения выше получается следующий алгоритм построения кратчайшего пути по карте: Для всех вершин полигонов и внешних точек (возможные начала и концы путей) нужно построить касательные ко всем полигонам. Оставить только те, которые касаются обоих полигонов. Добавить к этому все границы полигонов и отрезки между внешними точками. Потом выкинуть все отрезки, которые пересекаются с каким-то препятствием. Построить граф где эти отрезки это ребра. Найти в нем кратчайший путь.


Наивный алгоритм


Самый простой метод построить касательные из точки это перебрать все вершины полигона и найти те, где обе стороны лежат по одну сторону от прямой точка-вершина. Понять. что стороны лежат по одну сторону можно проверив знаки векторных произведений векторов сторон (v1, v2) и вектора из точки (v):
касательная Не касательная


Получается что-то вроде такого:


// |p| хранит вершины полигона в порядке обхода против часовой стрелки.// Класс Point используется для хранения точек или векторов. // Оператор ^ переопределен для векторного произведения. // Оператор - переопределен для векторной разностиstd::pair<int, int> Polygon::GetTangentIds(const Point &a) {    int n = p.size();    std::pair<int, int> res = { -1, -1 };    for (int i = 0; i < n; ++i) {        if (p[i] == a) {            res = { i, i };            break;        }        Point v1 = p[i] - p[(i + n - 1) % n];        Point v = p[i] - a;        Point v2 = p[(i + 1) % n] - p[i];        double dir1 = v1 ^ v;        double dir2 = v ^ v2;        if (dir1 < eps && dir2 < -eps) {            res.first = i;        }        if (dir1 > eps && dir2 > -eps) {            res.second = i;        }    }    return res;}

Обратите внимание на сравнения с eps так правильно сравнивать вещественные числа, чтобы ошибки округления не ломали алгоритм. Плюс или минус выбираются в зависимости от строгости сравнения. < -eps это значит строго меньше 0, < eps значит меньше равно. Знаки расставлены в коде выше так, чтобы выбрать самую удаленную вершину, если точка a лежит на продолжении стороны.


Этот метод работает за O(n). Можно отдельно рассмотреть случай вершины номер 0 и номер n-1, чтобы избавиться от модуля.


Быстрый логарифмический алгоритм


Раз уж точки уже упорядочены в порядке обхода, то тут явно напрашивается применение бинарного или хотя бы троичного поиска. Искать сразу две далекие точки одним алгоритмом не получится, поэтому будем запускать наш логарифмический поиск два раза для левой и правой касательной.


Еще одна проблема очень сложно даже думать о каком-то упорядоченном поиске в зацикленном контейнере. Поэтому разорвем наш полигон в первой вершине. Просто проверим, вдруг она является искомым концом касательной. Если нет, то можно забыть про сторону между последней и первой вершиной и не думать о зацикленности полигона.


Если взять произвольную сторону полигона, то можно понять, лежит ли она на "лицевой" или обратной стороне полигона. Похожим методом считается освещенность граней в компьютерной графике достаточно посмотреть на скалярное произведение нормали к стороне и вектора из вершины. Но можно не считать нормали, а брать векторное произведение с вектором-стороной:


Если вектор-сторона идет слева направо относительно вектора на начало стороны, то это лицевая сторона. В противном случае это обратная сторона. Концы касательных это вершины между "лицевыми" и "обратными" сторонами.


Уже можно было бы запустить бинарный поиск, если бы мы точно знали, что одна граница отрезка лежит на лицевой стороне, а другая на обратной. Но их такие еще найти надо. Тут можно воспользоваться еще одним наблюдением вершины внутри одной стороны строго упорядочены: лицевая сторона идет слева направо, а обратная сторона справа налево. Если у нас есть две вершины на лицевой стороне (или обе на обратной), то мы можем легко понять, лежат ли концы касательных между них: Надо только посмотреть, лежит ли последняя вершина раньше первой в порядке вершин:



Если обе вершины на обратной стороне, то переключение между обратной и лицевой стороной происходит между ними (в порядке обхода) только если вторая вершина "перескочила" лицевую сторону и оказалась раньше первой вершины отрезка. Аналогичное правило действует для двух вершин на лицевой стороне.


Давайте для конкретики введем "знаки" у вершин. Все вершины, сторона из которых идет справа налево относительно вектора из точки начала касательных, обозначим как "+" вершины в них значение векторного произведения будет положительно. Все точки, сторона из которых лежит на лицевой стороне или идет слева направо относительно начала касательных, обозначим "-" в них значение векторного произведения отрицательно.
Есть еще один неприятный случай: некоторые вершины могут иметь нулевое векторное произведение, если касательная совпадает со стороной (обозначим такие вершины "0"-вершинами). Еще более странные случаи, если точка-начало касательных лежит на стороне полигона, или вообще совпадает с вершиной. Ниже приведены все возможные случаи расположения начала касательных и "знаки" вершин:


  1. Касательные не совпадают ни с одной стороной.
  2. Левая касательная совпадает со стороной.
  3. Точка лежит на пересечении двух сторон.
  4. Правая касательная совпадает со стороной.
  5. Точка лежит на стороне.
  6. Точка совпадает с вершиной.
  7. Точка внутри полигона.

Нули могут быть с обоих концов от отрезка из плюсов, минусов может и не быть. Одно точно видно плюсы есть всегда. Поэтому давайте в качестве левой касательной брать "0/-" вершину, перед которой идет "+" вершина, а в качестве правой касательной "+" вершину, перед которой идет "0/-" вершина. Этот подход из нескольких возможных концов (при совпадении стороны и касательной) найдет самую далекую. Если же нужен самый близкий конец, то можно после выполнения логарифмического алгоритма попытаться подвинуть левый конец вперед вдоль полигона, а правый назад. Еще, последний случай (точка внутри полигона) немного все портит. В полигоне ничего кроме "+" нет. И мы никогда не найдем границу между двумя областями. Надо аккуратно проверить, что наш поиск не повисает в этом случае и не выдает какие-то неправильные ответы.


Итак, алгоритм для левой касательной:


1. Проверить, вдруг самая первая вершина удовлетворяет условию касательной. Если это не так, то мы знаем, что переключение между "+" и "0/-" происходит (если оно вообще есть) где-то между вершинами с 0 по n-1.2. l=0, r=n-1.4. Пока r-l > 1:  4.1.  Подсчитать "знак" вершины l.  4.2. Взять m: ceil((l+r)/2). Обратите внимание, условие 4. означает, что l < m < r.  4.3. Подсчитать знак вершины m.  4.4. Присвоить r = m, если выполняется один из трех случаев:      l - "+" и m - "-/0"      l - "+" и m - "+" и l лежит левее m      l - "-/0" и m - "/0" и l лежит правее m (или на одной прямой с ней)  4.5. Иначе присвоить l = m.

Есть один нетривиальный момент, что делать, если l и m имеют одни и те же знаки лежат на одной прямой с точкой начала касательных? Т.е. вершина l не лежит ни строго левее ни строго правее m?


Это возможно только в случаях 2, 3, 6 когда левая касательная совпадает со стороной. Если правая касательная совпадает со стороной, то знаки у вершин будут разные (дальняя всегда +). При этом l и m указывают на 2 соседние вершины! Но, поскольку у нас поддерживается l < m, мы же разорвали цикл и ищем внутри не зацикленного массива, то это значит, что l тот самый искомый конец касательной. Т.е. в случае, если обе вершины имеют знаки "-/0" и лежат на одной прямой, мы должны сдвинуть правый конец. Поэтому в пункте 4.4 сравнения надо делать именно так, если знаки совпадают во втором случае.


Для поиска правой касательной строгость сравнения должна быть в обратную сторону. Если обе вершины "-/0" и они лежат на одной прямой, то надо сдвинуть левую границу.


Итак, весь код алгоритма:


Код
std::pair<int, int> Polygon::GetTangentIdsLogarithmic(const Point& a) const{    std::pair<int, int> res = { -1, -1 };    const int n = points_.size();    Point vl = points_[1] - points_[0];    Point to_l = points_[0] - a;    Point v_prev = points_[0] - points_[n - 1];    Point to_prev = points_[n - 1] - a;    double pointing_l = to_l ^ vl;    double pointing_prev = to_prev ^ v_prev;    int l = 0;    int r = n - 1;    // Проверка, что вершина 0 - левая касательная.    if (pointing_prev > eps && pointing_l < eps) {        res.first = 0;        // Случай совпадения касательной и стороны        if (pointing_l > -eps) {            Point v_next = points_[2] - points_[1];            Point to_next = points_[1] - a;            double pointing_next = to_next ^ v_next;            // точка начала еще может лежать на стороне            if (pointing_next < -eps) {                res.first = 1;            }            else if (pointing_next < eps) {                // Или совпадать с вершиной 1.                return { 1, 1 };            }        }    }    else {        // Бинарный поиск.        while (l < r - 1) {            int m = (r + l + 1) / 2;            Point vm = points_[m + 1] - points_[m];            Point to_m = points_[m] - a;            double pointing_m = to_m ^ vm;            double lm_dir = to_l ^ to_m;            if (((pointing_m < eps) || (lm_dir < -eps)) &&                ((pointing_l > eps) || (lm_dir > -eps))) {                r = m;            }            else {                l = m;                to_l = to_m;                pointing_l = pointing_m;            }        }        // На случай, если |a| лежит внутри полигона, надо проверить, что бинпоиск        // остановился на ответе, а не просто на случайной вершине.        int next = (r + 1) % n;        Point to_r = points_[r] - a;        Point vr = points_[next] - points_[r];        double pointing_r = to_r ^ vr;        if (pointing_r < eps && pointing_l > eps) {            res.first = r;            // Проверка, что |a| лежит на продолжении стороны.            Point v_next = points_[(next + 1) % n] - points_[next];            Point to_next = points_[next] - a;            double pointing_next = to_next ^ v_next;            if (pointing_r > -eps) {                // Проверка, что |a| не лежит на стороне.                if (pointing_next < -eps) {                    res.first = next;                }                else if (pointing_next < eps) {                    // Или совпадает с вершиной.                    return { next, next };                }            }        }        else return { -1, -1 };    }    // Теперь работаем с правой касательной.    vl = points_[1] - points_[0];    to_l = points_[0] - a;    v_prev = points_[0] - points_[n - 1];    to_prev = points_[n - 1] - a;    pointing_l = to_l ^ vl;    pointing_prev = to_prev ^ v_prev;    l = 0;    r = n - 1;    // Проверка первой вершины    if (pointing_prev < eps && pointing_l > eps) {        res.second = 0;        // Может ее надо подвинуть назад.        if (res.first != n - 1 && pointing_prev > -eps) {            res.second = n - 1;        }    }    else {        while (l < r - 1) {            int m = (r + l + 1) / 2;            Point vm = points_[m + 1] - points_[m];            Point to_m = points_[m] - a;            double pointing_m = to_m ^ vm;            double lm_dir = to_l ^ to_m;            if (((pointing_l < eps) || (lm_dir < eps)) &&                ((pointing_m > eps) || (lm_dir > eps))) {                r = m;            }            else {                l = m;                to_l = to_m;                pointing_l = pointing_m;            }        }        // Проверка, что бинпоиск остановился на ответе.        Point to_r = points_[r] - a;        Point vr = points_[(r + 1) % n] - points_[r];        double pointing_r = to_r ^ vr;        if (pointing_r > eps && pointing_l < eps) {            res.second = r;            // Проверка, что ответ нужно подвинуть назад.            if ((res.first != l) && pointing_l > -eps) {                res.second = l;            }        }    }    return res;}

Несмотря на длинный и, возможно, пугающий код, этот алгоритм работает быстрее наивного уже при n=4.


Проверка пересечения отрезка и полигона за O(1)


*terms and conditions apply.


Следующий трюк, которым я хотел поделиться это как пересекать отрезок и полигон за константу, при выполнении некоторых допущений. Во-первых, ни один конец отрезка не лежит внутри полигона, и, во-вторых, касательные уже должны быть известны. В противном случае, можно за логарифм построить касательные и проверить, что концы отрезка не лежат внутри полигона. Это дало бы логарифмический алогритм проверки на пересечение.


Оба этих допущения выполняются в моей библиотеке поиска кратчайшего пути вокруг препятствий. Возможных отрезков, которые нужно проверять на пересечение O(k*n^2), если у нас n полигонов с k вершинами. Когда как точек, из которых они торчат всего O(k*n). Поэтому гораздо быстрее сначала проверить все точки-концы отрезков по одному разу и вычеркнуть все отрезки из плохих точек. Второе допущение выполняется, потому что все касательные на все полигоны мы и так строим это же и есть кандидаты на ребра в графе кратчайших путей. Для проверки на пересечения они достаются бесплатно.


Итак, нам даны полигон, отрезок с концами вне полигона и касательные из одного конца отрезка. Если отрезок пересекает полигон, то он точно должен пересекать и хорду между двумя концами касательных (иначе один из его концов должен был бы лежать внутри полигона). Т.е. получается, что нужно проверить пересечение лишь с одним отрезком, а это можно сделать за O(1).

Подробнее..

Перевод Математики совершили новое открытие, связанное с додекаэдром

01.09.2020 16:17:46 | Автор: admin

Трое математиков получили ответ на фундаментальный вопрос о прямых путях на 12-гранном платоновом теле




Несмотря на то, что математики уже более 2000 лет [а, возможно, и ещё больше / прим. перев.] разбирают структуру пяти правильных многогранников (платоновых тел) тетраэдра, гексаэдра (куба), октаэдра, додекаэдра и икосаэдра мы ещё очень многого о них не знаем.

И вот трое математиков ответили на один из самых базовых вопросов, касающихся додекаэдра.

Допустим, вы стоите на одной из вершин правильного многогранника. Существует ли прямой путь, по которому можно вернуться в точку старта, не проходя ни через одну из остальных вершин? Для четырёх других правильных многогранников, составленных из квадратов или равносторонних треугольников тетраэдра, куба, октаэдра и икосаэдра математики недавно дали отрицательный ответ на этот вопрос. Любой прямой путь, начинающийся с одной из вершин, либо наткнётся на другую вершину, либо будет вечно виться по поверхности фигуры, так и не вернувшись в исходную точку. Однако математики не знали, чего можно ожидать от додекаэдра, состоящего из 12 пятиугольников.

Теперь Джейдев Атрейа, Дэвид Оличино и Патрик Хупер показали, что на додекаэдре действительно существует бесконечное множество подобных путей. В их работе, опубликованной в мае в журнале Experimental Mathematics, показано, что эти пути можно естественным способом разделить на 31 семейство.

Поиск решения потребовал использования современных технологий и составления компьютерных алгоритмов. Лет двадцать назад этот вопрос был вне досягаемости; лет 10 назад он потребовал бы невероятных усилий по написанию всех необходимых программ; и только сегодня все факторы сошлись, написал в емейле Антон Зорич из Математического института Жасси в Париже.

Этот проект стартовал в 2016 году, когда Атрейа из Вашингтонского университета и Оличино из Бруклинского колледжа начали играться с набором плоских фигур, складывавшихся в правильный многогранник. Во время сборки многогранника Оличино понял, что накопленный за последнее время материал по плоской геометрии может оказаться кстати для понимания прямых путей на додекаэдре. Мы буквально собирали эти штуки из разрозненных кусочков, сказал Атрейа. Простое любопытство исследователей совпало с новой возможностью.

Вместе с Хупером из Сити-колледжа в Нью-Йорке исследователи придумали, как классифицировать все прямые пути, выходящие из одного из углов и приходящие в него же, минуя остальные углы.

Их анализ является элегантным решением, как выразился Говард Мазур из Чикагского университета. Это один из тех случаев, когда я без колебаний могу заявить: Вот это да, почему же я этого не сделал!

Скрытые симметрии


Хотя математики уже более ста лет рассуждают о прямых путях на додекаэдре, в последние годы интерес к этой теме возродился благодаря полученным недавно новым знаниям в области поверхностей переноса. Такие поверхности формируются при помощи склейки параллельных сторон многогранника. Они оказались очень полезными для изучения широкого спектра тем, связанных с прямыми путями, идущими по фигурам с углами от траекторий биллиардных шаров до вопросов о том, может ли один луч света осветить всю комнату с зеркальными стенками.

Базовая идея во всех этих задачах так развернуть фигуру, чтобы идущие по ней пути стало проще изучать. Чтобы разобраться в прямых путях, идущим по правильному многограннику, можно начать с разрезания достаточного количества рёбер для того, чтобы их можно было развернуть на плоскости, сформировав, как говорят математики, сеть. Одна из сетей для куба, к примеру фигура в виде буквы Т, состоящая из шести квадратов.


Додекаэдр из бумаги, сделанный в 2018 году Дэвидом Оличиной и Джейдевом Атрейей для демонстрации возможности провести путь из одной вершины обратно в неё же без пересечения других.

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

Чтобы избежать всех этих прыжков и поворотов, при встрече с ребром мы могли бы приклеить на него новую, повёрнутую копию сети, и продолжать идти прямо. Тогда у нас добавится избыточности: у нас будет два разных пятиугольника, обозначающих пятиугольник оригинального додекаэдра. Мы усложнили наш мир, но упростили наш путь. Мы можем продолжать добавлять новую сеть каждый раз, когда нам необходимо выйти за границы нашего мира.

К тому времени, как наш путь пройдёт через 10 сетей, мы повернём нашу оригинальную сеть на все возможные варианты углов, делящиеся на 36, и ориентация следующей добавленной нами сети совпадёт с той, с которой мы начинали. Получается, что 11-я сеть получается из оригинальной простым сдвигом как говорят математики, переносом. Вместо того, чтобы приклеивать 11-ю сеть, мы можем просто приклеить ребро 10-й сети к соответствующему параллельному ребру оригинальной сети. Наша фигура уже не будет плоской, но математики считают, что она помнит плоскую геометрию своего предыдущего воплощения так что, к примеру, пути считаются прямыми, если они были прямыми на ещё не склеенной фигура. После того, как мы сделаем все возможные склейки соответствующих параллельных рёбер, мы получим т.н. поверхность переноса.


Атрейа на правой руке сделал себе татуировку своей любимой поверхности переноса двойного пятиугольника

Полученная поверхность это представление додекаэдра, сделанное с большой избыточностью, в котором участвует 10 копий каждого пятиугольника. И оно гораздо получилось более сложным оно склеено в виде пончика с 81 отверстиями. Тем не менее, эта сложная форма позволила троим исследователям разобраться в богатой теории поверхностей переноса.

Столкнувшись с такой гигантской поверхностью, математики закатали рукава как фигурально, так и буквально. Поработав с ней несколько месяцев, они поняли, что поверхность пончика с 81 отверстием формирует избыточную презентацию не только додекаэдра, но и одной из самых часто изучаемых поверхностей переноса. Это двойной пятиугольник, который получается, если склеить два пятиугольника по одному из рёбер, а затем склеить все идущие параллельно стороны, чтобы получился пончик с двумя отверстиями и большим набором симметрий.

Также эта фигура вытатуирована на руке Атрейи. Я уже знал и любил этот двойной пятиугольник, сказал Атрейа, сделавший эту татуировку за год до того, как они с Оличино начали размышлять о додекаэдре.

Поскольку двойной пятиугольник и додекаэдр геометрические родственники, высокая степень симметричности первого может помочь разобраться в структуре второго. Это потрясающая скрытая симметрия, сказал Алекс Эскин из Чикагского университета (консультировавший Атрейю по докторской диссертации 15 лет назад). То, что у додекаэдра есть такая скрытая группа симметрии, является весьма примечательным фактом.


Джейдев Атрейа рассказывает, как они с коллегами решили давнюю задачу поиска прямых путей на додекаэдре

Взаимосвязь между этими поверхностями позволила исследователям воспользоваться алгоритмом анализа поверхностей переноса с высокой симметричностью, который разработала Мириам Финстер из Технологического института Карлсруэ. Адаптировав её алгоритм, исследователи смогли найти все прямые пути на додекаэдре, выходящие из одной вершины и возвращающиеся в неё, и классифицировать их на основе скрытых симметрий додекаэдра.

Этот анализ стал одним из самых интересных проектов за всю мою карьеру, сказал Атрейа. Очень важно постоянно играться с разными вещами.

Новый результат говорит о том, что даже в тех объектах, которые люди изучают уже тысячи лет, могут скрываться секреты, сказал Эскин. Думаю, что даже для этих троих математиков было неожиданностью то, что они смогли сказать что-то новое по поводу додекаэдра.
Подробнее..

Что за зверь афинные преобразования?

26.01.2021 22:17:56 | Автор: admin

Скорее всего, каждый из Вас хоть раз в жизни слышал термин афинные преобразования. Действительно, все постоянно о них говорят: инвариантность к афинным преобразованиям, аугментация с помощью афинных преобразований, афинные преобразования в компьютерной графике и так далее. Однако, далеко не все могут сходу ответить на простой вопрос: А расскажите, что такое афинные преобразования простыми словами.

Вы сможете? В любом случае, давайте немного обсудим этот вопрос.

Что такое афинное преобразование?

Начнем с классики - определение из Википедии.

Аффинное преобразование (от лат. affinis соприкасающийся, близкий, смежный) отображение плоскости или пространства в себя, при котором параллельные прямые переходят в параллельные прямые, пересекающиеся в пересекающиеся, скрещивающиеся в скрещивающиеся.

Внесем немного ясности.

Во-первых, что значит отображение в себя? Это значит, что если мы находились в пространстве R^n , то после образования мы должны остаться в нем же. Например: если мы применили какое-то преобразование к прямоугольнику и получили параллелепипед, то мы вышли из R^2 в R^3 . А вот если из прямоугольника у нас получился другой прямоугольник, то все хорошо, мы отобразили исходное пространство в себя. Формально это описывается так: преобразование f отображает пространство R^n в R^n . Если записать с помощью формул: f: R^n \rightarrow R^n .

Во-вторых, что такое скрещивающиеся прямые? Конечно, все это проходили в школе, но на всякий случай напомним. Прямые называются скрещивающимися, если они не лежат в одной плоскости. Вот если бы они лежали в одной плоскости и пересекались, они назывались бы пересекающимися. А если в разных плоскостях, то скрещивающимися. Пример - на рисунке.

В целом, это определение уже нам что-то говорит и мы начинаем потихоньку рисовать для себя картинку. Как минимум, мы должны остаться в той же плоскости: значит мы представляем себе 2D декартову систему координат. Здесь речь идет о нескольких прямых, так что давайте представим 2 параллельных линии. Из определения мы понимаем, что после преобразования эти линии должны остаться параллельными. Ну что ж, тогда просто сдвигаем их куда-нибудь из исходного местоположения, да и все.

По сути, мы с Вами только что описали один из видов афинных преобразований - сдвиг.

Но давайте пойдем чуть дальше и дадим еще одно определение (не нами придуманное).

Преобразование плоскости называется аффинным, если оно непрерывно, взаимно однозначно и образом любой прямой является прямая.

Звучит это, пожалуй, чуть сложней и путанней, но дает нам больше конкретной информации, чем предыдущее определение.

Преобразование называется непрерывным, если близкие точки переходят в близкие. Т.е. иначе - если у нас есть две точки и они находятся рядом, то после преобразования они все равно будут находиться где-то поблизости друг от друга.

Далее - преобразование взаимооднозначно, если разные точки переводятся в разные точки и в каждую точку переводится какая-то точка. Например: если мы отобразили отрезок и он слипся в точку - это не взаимооднозначное преобразование. Из отрезка мы должны получить ровно такой же отрезок, тогда будет взаимооднозначно (если это сработает для всех отрезков, конечно).

Итак, с определениями мы разобрались. Давайте теперь запишем в общем виде, а как выглядит преобразование координат в формульном виде.

Пусть у нас есть исходная система координат. Точка в этой системе характеризуется двумя числами - x и y . Совершить переход к новым координатам x' и y' мы можем с помощью следующей системы:

\begin{cases} x' = \alpha x + \beta y + \lambda \\ y' = \gamma x + \delta y + \mu \end{cases}

При этом, числа \alpha, \beta, \gamma, \mu должны образовывать невырожденную матрицу:

\begin{pmatrix} \alpha & \beta \\ \gamma & \delta \end{pmatrix}

На всякий случай: матрица называется невырожденной, если ее определитель не равен нулю, т.е.

\begin{vmatrix} \alpha & \beta \\ \gamma & \delta \end{vmatrix} \neq 0

Можно записать и в более общем в виде.

Афинное преобразование f: R^n \rightarrow R^n - преобразование вида f(x) = Mx +v , где M - обратимая матрица, а v \in R^n . В данном случаеx, само собой, n -мерный вектор.

Примеры афинных преобразований

Мы с Вами достаточно подробно разобрали, что такое афинное преобразование и как его можно описать с помощью формул. Давайте теперь рассмотрим популярные примеры.

Приходят ли Вам в голову какие-нибудь претенденты на роль\alpha, \beta, \gamma, \mu, \delta, \lambda? Позвольте мы внесем свои предложения.

Поворот

Пусть \alpha = cos(\alpha), \beta = sin(\alpha), \gamma = -sin(\alpha), \delta = cos(\alpha), \lambda = \mu = 0 .

Значит, матрица M примет вид:

\begin{pmatrix} cos(\alpha) & sin(\alpha) \\ -sin(\alpha) & cos(\alpha) \end{pmatrix}

И новые координаты будут выглядеть так:

\begin{cases} x' = xcos\alpha + y sin\alpha \\ y' = -xsin\alpha + y cos\alpha \end{cases}

Ничего не напоминает? Если Вы еще не узнали, то встречайте - это просто повернутая система координат на угол \alpha . Т.е. мы применили афинное преобразование и наша система координат повернулась. Пример этого Вы можете видеть на графике.

Растяжение-сжатие

Теперь мы предлагаем сконструировать матрицуMнесколько иначе:

\begin{pmatrix} 1/k_x & 0 \\ 0 & 1/k_y \end{pmatrix}

Новые координаты тогда принимают вид:

\begin{cases} x' = x/k_x \\ y' = y/k_y \end{cases}

В целом, тут даже уже из вида системы уравнений понятно, что мы просто растягиваем наши оси, если коэффициент меньше 1 и сжимаем, если больше 1. Пример на рисунке.

Кстати говоря, а попробуйте поставить вместо k_x число -1, а вместо k_y просто 1. Что получится? Правильно, мы просто отразим нашу систему координат относительно оси OY .

Сдвиг

Ну и давайте напоследок еще один пример.

Пусть теперь матрица M никак не меняет исходные координаты (т.е. \alpha = \delta = 1 ,beta = \gamma = 0 ). А вот \lambda пусть равняется -dx , а \mu = -dy .

Таким образом, наша система принимает вид:

\begin{cases} x' = x - dx \\ y' = y - dy \end{cases}

Если отразить это на графике, то мы просто сдвинули начало координат в точку (dx, dy) . Вот, собственно, и вся премудрость.

Эпилог

Эта короткая статья позволит Вам чуть сильней прочувствовать внутренности афинных преобразований (мы надеемся на это). После прочтения попробуйте все-таки ответить на вопрос, который мы ставили в самом начале - А расскажите, что такое афинные преобразования простыми словами. Теперь сможете?

P.S. Кстати говоря, было бы неплохо не верить нам на слово и проверить самим - а матрицы M , которые мы использовали - точно невырожденные? Может мы вообще что-то противозаконное сделали?...

Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru