Исследовательница Чэньси Лю и ее коллеги из Университета Британской Колумбии предлагают алгоритмическое решение под названием ConTesse, которое позволяет решить проблему «скрытых линий».
Под проблемой скрытых линий подразумевают ситуацию, когда наложение виртуальной сетки на 3D-объект не справляется с задачей генерации достаточно тонкой треугольной сетки, позволяющей избежать появления ошибочных, мерцающих линий в анимации.
«Новый алгоритм исследователей сначала прослеживает края трехмерной фигуры с помощью отрезков линий, затем сжимает этот приблизительный контур до 2D и пытается выложить его внутреннюю часть треугольниками. Везде, где эта внутренняя сетка ошибочно пересекает саму себя, алгоритм изменяет эту часть контура, например, раскручивая ее или добавляя более тонкие сегменты линии. Затем алгоритм восстанавливает сетку, используя восстановленный контур, и проецирует все это обратно на трехмерный объект для окончательной проверки видимости», объясняют в Scientific American.
Благодаря приближению масштаба сгенерированных контуров более чем в полторы тысячи раз, командой Лю были обнаружены изгибы, где линии неправильно пересекались, что мешало созданию плавных, правильных контуров. Инновация заключается в первую очередь в том, чтобы понять, в чем именно заключалась проблема.