Плавные переходы между двумя пересекающимися полигонами (интересная задача) - PullRequest
Новая
       8

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

3 голосов
/ 02 августа 2011

У меня есть интересная проблема, которую я пытался решить некоторое время.Для этого нет «правильного» решения, так как нет строгих критериев успеха.Чего я хочу добиться, так это плавного перехода между двумя простыми многоугольниками от многоугольника A к многоугольнику B. Многоугольник A полностью содержится в многоугольнике B.

Мои критерии для этого перехода:

  1. Переход непрерывен во времени и пространстве
  2. Область, которая «заполняется» из многоугольника А в многоугольник В, должна заполняться так, как если бы в А находилась жидкость, которая выливалась в формуB
  3. Важно, чтобы эта анимация могла быть рассчитана либо на лету, либо определяться набором параметров, которые требуют небольшого пространства, скажем, менее нескольких килобайт.

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

Решения, которые я рассмотрел, и в основном исключают:

  • Объединение вершин вА и Б и просто интерполировать.Не будет хорошо выглядеть и не работает в случае вогнутых многоугольников.
  • Разделение области BA на выпуклые многоугольники, возможно, диаграмма Вороного, и вычисление дискретных состояний многоугольника путем выполнения BFS на меньшем выпукломмногоугольники.Затем я интерполирую между дискретными состояниями.Примечание: если многоугольник BA выпуклый, переход довольно тривиален.Я не пошел с этим решением, потому что разделить BA на маленькие выпуклые многоугольники одинакового размера было удивительно сложно
  • Моделирование: подразделить многоугольник A. Перемещайте каждую вершину вдоль линии многоугольника по нормали (наружу) дискретными, но небольшими шагами.Для каждого шага проверьте, находится ли вершина внутри B. Если нет, то вернитесь в предыдущую позицию.Повторяйте до тех пор, пока A не станет равным B. Мне не нравится это решение, потому что проверка, находится ли вершина внутри многоугольника, медленная.

У кого-нибудь есть другие идеи?

1 Ответ

0 голосов
/ 11 ноября 2014

Если вы хотите сохранить это простое и несколько быстрое, вы можете продолжить свою последнюю идею, где вы рассматриваете масштабирование многоугольника A так, чтобы оно постепенно заполняло многоугольник B. Вам не обязательно проверять, были ли уменьшенные вершины убраны все еще находятся внутри многоугольника B. В зависимости от того, на что похожа ваша кодовая среда и API, вы можете замаскировать пиксели расширяющегося многоугольника A контуром многоугольника B.

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

...