Собственно, столкнулся на производстве с такой вот задачей. Дан 3-мерный не обязательно выпуклый многогранник (mesh), грани — треугольники. Задача такая: построить один или несколько многогранников вложенных в данный так, чтобы суммарный объем этих многогранников был максимальным и никакая точка внутренних многогранников не была ближе k мм от внешнего. Проще говоря — вырезать полость (полости) максимального объема так, чтобы "стенки" везде были толщины не менее k мм.
Нужно это, естественно, для 3Д печати. Вот здесь показано как это делать, например, для куба: https://www.shapeways.com/tutorials/creating-hollow-objects Наши модели, само собой, более сложные — фигурки людей и пр.
Сейчас решаем проблему приближенно, строим внутри полости из "кубиков" (вокселей). При большом количестве вокселей результат хороший, но в модели получается очень много вершин и граней и принтеру иногда сносит крышу.
Соответственно требования такие:
максимальный внутренний объем
толщина стенок
количество "внутренних" граней должно быть не больше, чем количество граней в исходном меше
работает быстро и не жрет память, в идеале O(количество вершин)
естественно, никаких самопересечений, вырожденных граней и прочего
У кого нибудь есть идеи как написать такой алгоритм? Буду рад любым идеям — можно начать с решения в 2мерном случае, например. Заранее спасибо :)
Можно ли каким-нибудь образом размер вокселя выбирать адаптивно? Вблизи областей большой кривизны исходного многогранника — брать воксели помельче, в других областях — покрупнее.
А remeshing пробовали делать?
Вообще говоря, 3D-принтеры умеют обрабатывать мелкие нарушения в геометрии; я бы поэкспериментировал, как ваш к ним отнесётся.
В двумерном случае вроде всё относительно легко, можно погуглить по polygon offset. В трёхмерном аналогичные методы думаю не прокатят.
В общем случае область максимального объема не является объединением конечного числа многогранников, ее поверхность может состоять из кусков цилиндров и сфер. Их можно аппроксимировать многогранниками, но это сразу гробит требование на количество граней.
А можно пример? Просто не верится. Если строить внешний бордер, то да, верится, но тут внутренний.
Тут как раз все просто, такое и в 2-мерном случае происходит, см. например среднюю фигуру вот здесь: http://i.stack.imgur.com/QCYwM.png
Да, совершенно верно. Понятно, что идеальное решение нельзя получить только многогранниками.
Есть ощущение, что может сработать следующее. Пусть F_i — изначальные грани, P_i — плоскости, в которых они лежат. S_i будет полупространство с границей P_i и локально содержащее многогранник (отвечает за ориентацию грани). Сдвигаем каждую P_i внутрь на k и получаем P_i^k, а также S_i^k \subset S_i. Далее, нужно определить форму получившейся грани ( F_i^k). В простейшем случае возьмём все полуплоскости, заданные пересечением P_i^k и S_j^k для всех j, и пересечём их, получив выпуклую грань для каждого i (возможно, пустую). Если изначальный многогранник не имеет сужений, то всё ок. В противном случае грань может быть невыпуклой, иметь дырки, быть несвязной. Предлагаю следующий вариант. Для начала, определим предварительную форму грани, заданную её соседями. То есть пересечём P_i^k с тремя S_j^k её соседей (отдельно разбираем случай отсутствия угла с соседней гранью, либо объединяем их заблаговременно). Назовём их F'_i^k, они пока выпуклы, и у них есть сторона, с которой от них многогранник (ориентация). Вероятно, их тоже хватит, чтобы в простейшем случае задать результат. Чтобы вычислить настоящие F_i^k, делаем следующее. Пересекаем каждое F'_j^k с P_i^k, получаем отрезок L_{ij}^k, который наследует ориентацию от F'_j^k. Утверждается, что из этих отрезков можно собрать набор многоугольников с дырками, которые, после пересечения с F'_i^k, дадут нам F_i^k.
И, кстати, да. Для внутренних углов будет что-то округлое, как и сказал I_love_Nastya. Вроде бы, это принципиально алгоритм не меняет, но веселья добавит.
В общем, после чтения литературы по теме я понял, что проблемка это та еще :) Реализовать такой алгоритм без багов и качественно протестировать будет непросто — возможно, этим стоит заняться создателям какой-нибудь библиотеки, но для моих текущих задач это слишком сложно. Пока допилю алгоритм с вокселями, его будет достаточно. Всем спасибо за ответы!
Кстати говоря, пока читал всякие статьи, наткнулся еще и на такую задачу: http://en.wikipedia.org/wiki/Straight_skeleton
Во-первых мне нравится название, а во-вторых, я никогда не встречал олимпиадных задач, связанных со straight skeleton — мне кажется здесь есть потенциал.
Да, это как раз то, что я имел в виду изначально. Без округлостей как раз оно и получается. Вроде даже видел эту штуку, но забыл уже всё.
Кстати задача на straight_skeleton уже где-то была. Называлась она примерно так — "постройка крыши". Был дан выпуклый многоугольник. Делаем ровно straight_skeleton и нужно было посчитать суммарную длину полученных ребер этой самой крыши. А решалась она вот так inscribed_circle. Для невыпуклых фигур дело обстоит примерно так же, только эта задача становится более технической.