Войти
ФлеймФорумПрограммирование

Обрезать многогранник по плоскости.

Страницы: 1 2 Следующая »
#0
(Правка: 0:20) 0:19, 28 апр. 2019

Задача казалось бы проста.
Есть многогранник, у которого есть список граней. Линия хранит какие точки она соединяет. Грань хранит список линий и точек. Причём в правильном порядке хранит.
Есть секущая плоскость. Задаётся нормалью и расстоянием до нуля. То есть на ней точки удовлетворяют соотношению dot(v, N)+C=0.
Надо найти многогранник, образованный пересечением исходного многогранника и этой плоскости. Требуется, чтоб у полученного многогранника на каждой грани площадь треугольника, образованного любыми трёмя последовательными точками, была не ноль.

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

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

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

На выходе такой скрин:
screen | Обрезать многогранник по плоскости.
И такой процесс "обрезания":


Как видно, везёт не всегда.

Чё думаете про это?

#1
1:33, 28 апр. 2019

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

#2
5:49, 28 апр. 2019

1 frag / 2 deaths
> многогранник
Выпуклый, или не обязательно?

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

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

#3
6:25, 28 апр. 2019

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

#4
6:43, 28 апр. 2019

Panzerschrek[CN]
> Можно пойти дальше и вообще изменить представление данных

Чует моё сердце, что 1 frag / 2 deaths пилит клон Quake и там так и есть.


1 frag / 2 deaths

Я в коде заметил что float. Rly?!

#5
(Правка: 11:47) 11:42, 28 апр. 2019

}:+()___ [Smile]
> , задача становится чисто топологической, координаты вершин уже ни на что
> влиять не должны
Казалось бы, ан нет. А, я забыл сказать: мне нужен выпуклый многогранник.
Так вот, после классификации может оказаться, что "пограничное множество" представляет собой странную хрень
screen | Обрезать многогранник по плоскости.
красные точки - они пограничные. Остальные - нет. Ты спросишь про грани, отмеченные знаком вопроса - как же так, ведь эти грани плоские, и у них три точки пограничные, а остальные нет. Как такое возможно с точки зрения геометрии? Нууу, плавающий питух, да-да.

Panzerschrek[CN]
> Предлагаю перед сечением плоскостью треангулировать все грани, ну или хотя бы
> те, что могут быть проблемными. После сечения пройтись по этим граням о
> объединить в одну смежные грани с почти одинаковой нормалью.
А вот это больно( То есть да, триангуляция избавит от бредовых случаев типа "три вершины на границе, остальные нет", но это ж долго жеж(

=A=L=X=
> Чует моё сердце, что 1 frag / 2 deaths пилит клон Quake и там так и есть.
Я его уже десять лет попиливаю: https://gamedev.ru/flame/forum/?id=181583

=A=L=X=
> Я в коде заметил что float. Rly?!
И в Хулионе тоже вовсю используется флоат.

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

#6
12:23, 28 апр. 2019

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

красиво и бесполезно

#7
12:42, 28 апр. 2019

Более регулярным способом результат стабильнее:
screen | Обрезать многогранник по плоскости.

#8
14:24, 28 апр. 2019

1 frag / 2 deaths
> Повысил чувствительность классификатора
Всё равно может стрельнуть. Так что лучше всё-же изменить представление данных.

> мне нужен выпуклый многогранник
Тогда не пойдёт вариант с триангуляцией, он может породить невыпуклый многогогранник.

#9
15:35, 28 апр. 2019

1 frag / 2 deaths
> Я его уже десять лет попиливаю

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

#10
15:46, 28 апр. 2019

Panzerschrek[CN]
> Всё равно может стрельнуть. Так что лучше всё-же изменить представление данных.
Да можно забить, замыкание мне не нужно на самом деле. А без него всё ок.

#11
19:00, 28 апр. 2019

1 frag / 2 deaths
> Казалось бы, ан нет. А, я забыл сказать: мне нужен выпуклый многогранник.
Если ты правильно определишь "выпуклость" с учетом питуха, то, по идее, тоже будет работать.

Правильно определишь = по сути, забьешь.

> Так вот, после классификации может оказаться, что "пограничное множество"
Мне кажется, что у тебя проблемы с классификацией.
После классификации каждая точка должна иметь бинарный флаг, никакого "пограничного" состояния быть не должно.

> Ты спросишь про грани, отмеченные знаком вопроса - как же так, ведь эти грани плоские, и у них три точки пограничные, а остальные нет.
Не спрошу. С учетом питуха, плоскости не существует; считай, что рассекаешь какой-то кривой поверхностью.

#12
19:11, 28 апр. 2019

}:+()___ [Smile]
> После классификации каждая точка должна иметь бинарный флаг, никакого
> "пограничного" состояния быть не должно.
Ну, это не сработает.
Во-первых, расстояние до плоскости 0.0 - это хорошая или плохая точка? Ну давай постановим, что плохая.
Вот есть грань. У неё три вершины A,B,C, с дистами 1.0, 1.0, 0.0. Говоришь, пограничного состояния быть не должно, C с её 0.0 - точно плохая точка. Ну ок, считаем C плохой, находим новую A` на отрезке AC (она совпала с C, но там-то что, да?), находим новую B' на отрезке BC (она тоже совпала с C...), строим грань ABB'A', потому что точка C улетела, вместо неё у нас A' и B'. Ииии... получаем грань, у которой две точки равны.

Ой, жаль. Давай постановим, что 0.0 - это хорошая точка. Берём грань ABC, у которой дисты точек 0.0, -1.0, -1.0. После стандартной процедуры нарезки (топологическая задача, всё такое) получаем AB'C' , причём B' и C' случайно совпали с A. Короче, получили грань, у которой все три точки равны.

А условие было - чтоб для любых трёх соседних точек любой грани была ненулевая площадь треугольника.

#13
19:47, 28 апр. 2019

1 frag / 2 deaths
> Ииии... получаем грань, у которой две точки равны.
> Короче, получили грань, у которой все три точки равны.
Вот я и предлагаю на такое забить. Получили и хрен с ним, и так сойдет.
Т. е. проще настроить последующие алгоритмы, чтобы работали с такими вещами, чем исправить это тут.
Тем более, это плавучка, если последующие алгоритмы с таким не работают, то они упадут и на других случаях.

> А условие было - чтоб для любых трёх соседних точек любой грани была ненулевая площадь треугольника.
Где такое условие? Тем более, на практике, с учетом плавучки, будет не нулевая, а ±eps.
В общем, на финальной стадии приведи все точки к целым числам и удали дубликаты и вырожденные примитивы.

#14
19:54, 28 апр. 2019

}:+()___ [Smile]
> Где такое условие?
У следующих стадий.

}:+()___ [Smile]
> В общем, на финальной стадии приведи все точки к целым числам и удали дубликаты
> и вырожденные примитивы.
Ну, некрасивенько...

Страницы: 1 2 Следующая »
ФлеймФорумПрограммирование