Грани и границы алмаза: решаем «проблемы» алгоритма огранки

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

Итак, меня зовут Алексей Тарасов, я математик и уже пятнадцать лет работаю со сложными задачами для бизнеса. В портфеле найдутся разные кейсы, от логистики железнодорожных и авиаперевозок до оптимизации продаж и маршрутизации трафика. А среди клиентов — Т-банк, Huawei, РИВЦ-Пулково, КРОК, ТрансКонтейнер, Octonus, WildTeam и крупные ретейлеры.

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

Заданная нами целевая функция (подробнее — смотрите в этой статье) должна самостоятельно приводить к решению с максимальным возможным объемом, что и является целью алгоритма. Вот только если в начальном положении решение вырожденное, то солвер фактически «буксует» и не может двигаться. А связано с это с тем, что идет процесс вычисления производной целевой функции. И если все переменные в начале равны нулю, то и первая производная тоже равна нулю.

Чтобы решить эту проблему, пришлось написать строгие ограничения на выпуклость бриллианта.

Но строгое неравенство не работает в солверах. Что нужно сделать?

Допустим, 1 микрон, то есть 1e-6. Ведь необходимая для математической модели точность — 10 микрон, и для узких граней в районе павильона подойдет примерно такое расстояние, вычисленное нами.

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

Вуаля, сработало!

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

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

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

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

Здесь появляется еще один параметр для отделимости — r. Но у него, в отличие от выведенного прежде параметра h, есть еще одно свойство. И оно помогает отделить не просто точку, а «шарик» радиуса r. Это позволяет упростить структуру дефектов, которых может быть очень много (точнее, много может быть не дефектов как таковых, а вершин в их полигональном представлении). Дальше мы просто покрываем дефекты подобными «шариками» и получаем десятки более мелких, задавая для каждого разделяющую плоскость.

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

Так сказать, добро пожаловать в новую размерность.

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

Существуют специальные лаборатории, которые классифицируют бриллиант по ряду параметров, включая красоту, и дают заключение. И красота эта разделяется на типы EX/VG/DG/FN — то есть excellent, very good, good, fine. Алгоритму необходимо производить только EX и VG.

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

Фактически зона EX — такая 6-мерная область из кубиков. Что, к сожалению, довольно плохо параметризуется.

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

Но это скорее формальная красота бриллианта. А есть и реальная, самая что ни на есть будничная и очевидная даже непрофессионалу: бриллиант должен выглядеть хорошо. И для этого создан замечательный метод Hearts & Arrows (сердца и стрелы).

Итак, что такое красивый бриллиант? Ну, во-первых, он не выглядит кривым. А во-вторых, красиво блестит и сверкает. Для проверки этих качеств существует специальная лупа, раскрашенная в белый, красный и черный цвета. И если смотреть на круглый бриллиант с одной из сторон, видишь характерные стрелки, а с другой — характерные сердечки. Способ оценки не только простой, но и весьма романтичный, и воспользоваться им может любой желающий. Например, любой читатель этого текста: достаточно найти специальную лупу Hearts & Arrows и захватить ее с собой при покупке украшения с бриллиантом.

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

Если записать уравнение на отражение точки относительно заданной плоскости, получится достаточно простая математика. Пусть у нас есть точка p (p_x, p_y, p_z) и плоскость Ax + By + Cz - D = 0. Нам нужно найти точку p, которая симметрична относительно плоскости. Для этого надо вычислить расстояние до плоскости и сдвинуть p на два расстояния вдоль нормали плоскости.

Проще говоря, возвращаемся к уравнениям:

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

Отмечу, что здесь мы сталкиваемся с парадоксом: большие отклонения в 3D-геометрии могут не влиять на 2D-картинку, но порой даже минимальные 3D-отклонения значительно искажают 2D-картинку. Придется постоянно проверять.

Но вот бриллиант наконец-то стал красивым! К сожалению, прирост массы после этого уменьшился.

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

Нам остается принять так называемый «метод дробовика» и считать одновременно 8 и более вариантов решения с разными настройками. Максимум по массе без ограничений, жесткое задание сердец и стрел и так далее. А уж после того как пользователь получает результаты расчета, он самостоятельно анализирует полученные результаты по массе и красоте — и выбирает лучший.

Что ж, алгоритм готов, но даже не специалист увидит, что получился он очень сложным. Как думаете, сколько времени ему нужно на выполнение одной конкретной задачи? Требование заказчика казалось невозможным: всего 1 минута!

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

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

Вскоре я продолжу делиться своими кейсами и наблюдениями, а пока — буду рад ответить на любые вопросы.