Вставка одной поверхности в другую (многопоточный алгоритм) (комментарии) (2 стр)

Булева операция ничего про треугольники не знает, так как границы тела могут быть аналитическими поверхностями типа сферы-цилиндра-конуса

roserg

Мой совет -  не трать время на споры, лучше напиши другой алгоритм или изучи новую матчасть

innuendo
я говорю про алгоритм, а именно классический вариант. А не очередной творческий поиск с кучей артефактов. Если бы хоть одну ссылку посмотрели что я давал, там описывается множество способов на каждый этап, как с подобными артефактами как и у ТС так и без них.

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

Mira
так я об этом и говорю, со времен когда каждый пытался булевы операции над мешами выполнить, столько модификаций было написано, каждый алгоритм косолапил по своему. Большинство косяков были связанны с точностью. Остальные с подходом поиска пересечений и тесселяцией. Вот ТС автор еще одного варианта. Но есть более классические алгоритмы, у них единственный косяк это точность из за которой могут получится дырки или треугольники не в тех местах. Опять же вопрос в подходе реализации.

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

foxes

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

roserg
> не булевы операции.
нет чувак, ты не понял, это именно булева операция.
еще раз можно озвучить уже в тему:
innuendo
> Булева операция ничего про треугольники не знает

То о чем я говорю применимо к Mesh, ее каноническое представление алгоритма, к чему стремится большинство велосипедо строителей.
а у тебя ее корявое подобие, к чему собственно обычно приходят велосипедо строители.
О чем собственно товарищ с КРИ очень долго и нудно рассказывал.
http://kriconf.ru/2004/rec/KRI-2004.Programming_08.ogg
но ты видимо это так и не услышал.
И то как ты к нему прикрутил Surface Deformation выглядит весьма коряво.
http://sites.fas.harvard.edu/~cs277/papers/deformation_survey.pdf

Операция Boolean при Mesh моделировании имеет широкую область применения, и множество вариаций в реализации, а вот ее каноническое представление полностью сохраняет нормали и плоскости поверхностей каждого треугольника моделей.
И то что ты к ее неудачной реализации прикрутил Surface Deformation, не делает его абсолютно из рядя вон уникальным и не классифицируемым алгоритмом, как операция Surface Deformation + Boolean

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

но как на зло есть какаято фигня, с использованием БСП дерева, и этого во всем интернете просто навалом. я в него особо даже не вникал, потому что результат там ну просто уродливый, совсем для моделирования не подходит. 
берем 2 меша по 10 треугольников, а на выходе получаем + 100 +200 треугольников, ну куда это годится ?

если чтото и делать то чтото годное, что потом может пригодится, инфу нормальную пока не нашел ((

roserg

так что видишь, твой метод  очень даже не плох )))
не важно какие методы ты применяешь, такие  деяния над объектами и называют булевыми операциями)
можно то же самое делать с воксельными объектами, всеравно это будут булевы операции.
например в ZBrush это эффективно используется

stupid bot
> а какие методы реализации есть?
Та же булева операция, "вычитание". Логика алгоритма для бучевых операций на меше вообще не отличается для вычитания объединения/сложения пересечения и исключения. Это все обсуждалось здесь же на форуме поэтапно. BSP нужно для оптимизации.
Логика вычисления всегда была одна:
- Выбираешь какие треугольники нужны какие спрятать (внутренние/внешние). Соответственно этому выбору будет реализовано вычитание, объединение/сложение, пересечение, исключение.
- Находишь контур пересечения объектов.
- тесселяция контуров с пересеченными треугольниками, или контурами плоскостей пересеченных объектов.
Все эти алгоритмы по отдельности широко известны подробно описаны, и хорошо документированы, алгоритмов их реализации тьма.

stupid bot
>инфу нормальную пока не нашел ((
Она на столько устарела что уже не доступна в захламленном интернете, только в библиотеке под кучей православной пыли.
http://www.gamedev.ru/code/forum/?id=206335#m3
http://www.finalmesh.com/boolean3d.htm

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

stupid bot
> только на чтото подобное.
Здесь в примере явно показан вид тесселяции контуров, не треугольников.

Вообще лучше начать изучение с азов. К примеру есть такой алгоритм заливки 2D полигона в котором определяется где находиться пиксель, внутри или снаружи полигона. От точки пикселя проводиться лучь и считается количество пересечений луча с гранями полигона, четно - снаружи не четно - внутри. Точно также можно в 3D установить для каждой вершины находиться ли она снаружи или внутри другого объекта, и промаркировать их. Если это односторонняя плоскость то луч направлен соответственно нормали ближайшей плоскости треугольника, или (0.0,0.0,1.0).
C лучем (0.0,0.0,1.0) все упрощается до определения точки внутри/снаружи двухмерных треугольников, и определения их числа по положительной части оси Z.

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

Точно также как искались внешние/внутренние вершины можно найти пересечение граней (лучей) одних треугольников с плоскостью других треугольников. Таким образом находим контуры пересечений между треугольниками.

Все вычисления касаются пересечения луча и треугольника. Ни какой другой документации не нужно + голова на плечах.

roserg
1) как генерируется инфа о смежности (типа о соседних треугольниках каждого ребра) и как она хранится?
2) твой метод работает только для двусторонних и "водонепроницаемых" мешей?

PVSector
> типа о соседних треугольниках каждого ребра
Это не обязательно, достаточно после вычисления контура пересечения отсортировать полученные отрезки по совпадающим вершинам.

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

Такая же работа чтоб их сделать. На BSP дереве будет проще. Чтоб не гемороиться с BSP есть простой вариант "просеивания". Устанавливается размер минимального пространства "сита" - это размер куба в которое попадает вершина. Можно рассчитать, поделив минимум и максимум значений вершин на 64 например. Далее создаются списки из треугольников/граней для каждой ячейки "сита", по этим спискам определяются ближайшие элементы.
Просто вычислять, создается за один проход.

PVSector
1) генерируется заранее, каждый треугольник хранит индексы соседних трех
так хранится на gpu

struct Triangle
{
  ivec3 indexes;
  int dummy1;
  ivec3 neighbours;
  int dummy2;
  vec4 color;
};
layout (binding = 0, std430) buffer Triangles
{
  Triangle triangles[];
};

2) Нет, но у него есть другие ограничения
Если называть это булевой операцией, то это фейковая булева операция (она дает не корректное положение вершин с точки зрения булевых операций)
Почему я решил про нее написать, потому что это линейная операция + параллелится и реализуется на GPU. И она может моделировать некоторые вещи.