Операция *Boolean* над мешами

Добрый день!

Возникла необходимость моделировать вырезание одного меша из другого.
Возможно два варианта:
1) Первое тело ВЫРЕЗАЕТ из второго тела ту часть, на которую в него входит.
2) Первое тело СМИНАЕТ второе тело в той части, в которых они перекрываются.
Требования и по точности и по скорости.

Может быть кто подскажет хорошие ссылки по данному вопросу, какие есть алгоритмы и т.д.?

Большое спасибо! :)

google ->  "constructive solid geometry"

Nikopol
Спасибо конечно, но в таком море инфы нужен хороший лоцман :)

SXC
Эх... видел я где-то пример - как шарик вырезает из слоника разные части
То ли в ATI SDK то ли в NVIDIA SDK

Спасибо, попробую скачать NVIDIA SDK...

насколько я помню там было не вырезание как таковое (solid geometry) а фейковое, что то типа стенсила.

В DX9 SDK есть вырезание Clipping Volume. Чтобы такое делали с мешами - не видел, да и это вряд ли реально. Мешь - это поверхность, а не объем, поверхность его может быть в том числе и незамкнутой, тогда об объеме и говорить нечего.

Mikle
Здесь речь идет о вырезании треугольников попиксельно с помощью стенсила
Т. к меш чаще замкнут то можно говорить об "объеме"

Библиотека GTS имеет в своём составе CSG-операции.
http://gts.sourceforge.net/

Я видимо некорректно сформулировал вопрос, мне нужно вырезание именно солидов.

по ссылке http://gts.sourceforge.net/ ходил, но она особо не помогла, т.к. меня интересует именно технология, а в том коде разобраться сложновато...

Ну, в принципе, если подумать, можно и самому алгоритм придумать...

Типа (для intersect):

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

Короче геометрия рулит :)

Недавно я написал библиотеку для булевских операций для мешей из треугольников. При этом не обязательно, чтобы меши были замкнуты. Работает весьма стабильно. Успешно исползуются в игре Герои Уничтоженных Империй в редакторе ландшафта. Раньше использовали вызов длл-ки из Майи, но когда сами написали булевские операции, все стало работать раз в 10 стабильнее. Принцип таков:

1)находим пересечение всех ребер 1-го меша с треугольниками второго, затем ребер второго с треугольниками первого.
2)проходим по всем треугольникам как первого, так и второго мешей и строим на каждом треугольнике список линий, на концах которых - точки, полученные в пункте 1
3)в каждом треугольнике создаем список замкнутых контуров, образованных этими линиями, таким образом получаем набор полигонов, на которые разбиваеися треугольник. Если нужно, триангулируем эти полигоны. Важно помнить, что они могут быть невыпуклыми, и даже содержать дырки. Триангуляция - это отдельная и довольно нетривиальная тема.
4)в каждое из ребер, полученных в пункте 2 должно входить ровно 4 полигона. Суть булевской операции в том, что мы из этих 4-х оставляем только 2, а остальные 2 помечаем как "выброшенные". Принцип выбрасывания:  (а) для каждого граничного ребра (см 2) вычисляем векторное произведение нормали полигона на  направление ребра (б) находим скалярное произведение этого вектора на вектор нормали смежного полигона. Если больше 0 - то помечаем как выброшенный. (если реализуем вычитание, то наоборот, выбрасываем полигоны, для которых ск. произведение меньше 0)
5)рекурсивно проходим по всем полигонам, которые граничат с выброшенными не по линиям из пункта 2 и выбрасываем их тоже.
6)все

7)если нужно - убиваем короткие ребра среди (2)
8)если нужно - добавляем легкий бивел по линии (2)

В принципе алгоритм - вполне реалтаймовый для невысокополигональных мешей. Но вообще-то трудоемкое это дело. У меня ушло недели две весьма упорного труда чтоб сделать и отладить это. Месяц до того в оффлайне потихоньку придумывал алгоритм. Могу дать исходники. Но они - часть большого проекта, так что скомпилить их тоже не так уж элементарно.

AndrewShpagin
демку с исходниками могёшь сваять?

AndrewShpagin
Большое спасибо!
Все более-менее прояснилось :)