boolean на произвольных полигональных объектах

[f0x]

Товарищи! Есть вменяемый способ, без написания мегатонн кода?
_________________
кто сделал демку тот и выиграл (с) uncle night (?)

[Mikle]

Стенсил?

[f0x]

разверну: есть две пересекающихся как-либо полигональных колбасы (форма произвольна). на выходе нужно тоже полигональную колбасу.

http://www.madwomb.com/tutorials/imgMaya/MAYAp4i.jpg

и произвести сие надо на этапе рассчета модели, а не на рендере
_________________
кто сделал демку тот и выиграл (с) uncle night (?)

[Manwe]

[BiTL]

[BiTL]

[Mikle]

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

[BiTL]

[BiTL]

Ладно, может ссылочки в статье http://en.wikipedia.org/wiki/Constructive_solid_geometry наведут на готовое решение, или внятный разбор алгоритма

и ещё:

http://arxiv.org/pdf/1308.4434.pdf - сорри, на английском

http://www.gamedev.ru/code/forum/?id=61605 - тред на гэймдеве, люди делятся ссылками, может чтото есть полезное

[BiTL]

И всё же, на всякий случай, объясню, как я собирался применять Marching cubes для того, что хочет f0x:

Алгоритм "Шагающих кубиков" нам предоставляет простую возможность построить полигональную поверхность по некоему произвольному масиву вокселей, правильно? (поправочка: да, желательно, не по произвольному, а содержащему значения расстояния до поверхности)





Значит, нам ещё нужен алгоритм, который будет определять принадлежность точки пространству ограниченому поверхностью. Если нам не важен реалтайм, то думаю тут сложности не будет?

Далее, у нас есть два объекта, которые пересекаеются. Положим нам нужно откусить от объекта А объектом В.

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

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

Если применить тесселяцию, которая сейчас вроде нахаляву DirectX'ом предоставляется, то получаем вполне неплохой результат.

Точность результата конечно отсасывает перед "матановским" правильным способом, а оптимальность полигонизации будет неахти, но зато вроде не сложно?

Зато так можно строить какие-нибудь вот такие крутые штуки:





Я не пробовал, это просто идея )


- - - - - - - - - - - -

Алсо, а может октодеревья? http://habrahabr.ru/post/133769/

[f0x]

Битл, можно про marching cubes подробней? из вики нихрена не понял
_________________
кто сделал демку тот и выиграл (с) uncle night (?)

[BiTL]

[BiTL]

Ах да, тут ещё важен один момент. Почитай тред: http://www.gamedev.ru/code/forum/?id=172725

[f0x]

зы. нужен рилтайм, это раз.
определение принадлежности точки пространству - тут хз. форма-то не аналитически задана, сходу методов кроме как отрендерить орто, простите, гонально, фигуру 2 раза (бэк и фронт грани), забрать z-буфер, пройти куб точек отбросив ненужные - не приходит.
ну или проще, сенсилом сделать операцию нужную, забрать з-буфер, восстановить xyz точки. тоже 2 раза, для фронта и бэка.
короче, вычислительная сложность получается запредельной.
_________________
кто сделал демку тот и выиграл (с) uncle night (?)

[BiTL]