Comments 23
можно, профит даст, но там будет чуть другая формула, и это придётся проверять что-то есть, называется meshoptimizer, там не только эта проблема нужна, но и ряд смежных, что (мне было проще портировать свой формат) без этого всего покачто
так же частично это тема тесселяции, и теперь новшество mesh shaders, и LOD и геометрические задачи, которые вокруг этого начиная от точек и прочее их много как я понял
у вас идёт по кругу, в реале надо конкретно убедиться что вы хотите если не хотите повторов надо дать задание человеку чтобы он делал сетку sparse типо не знаю как назвать типо разряженая сетка из треугольников, там вобщем очень очень много подходов ну я пока для себя так понял
самое наивное это просто триангулировать и писать список индексов, или писать индексы по точкам сразу, еще есть повторители в самих АПИ, отсюда и сложность, если говорим о 3д так же учесть по какой стрелке идём, и учесть нормаль полигона - она должна смотреть в мир
еще есть тема, 4xs66m1Of4A может вы в неё попали, но тут если будете смотреть всё комплексно, на стадии отсекания лишнего уже получаем оптимизацию, делать гриди можно если мир реально большой будет, если поиграться то отсекателя достаточно, кстати эта тема помогает углубиться в структуры данных советую
еще вы близки к curve-bezie line но с курв надо читать как с ней работать как ею управлять, тоесть если реч о триангуляции от кривизны - вроде побольше треугольников будет или сверху еще оптимизиаторским алгоритмом придётся пройти или достать лоды ниже, мне вот пока проще делать сетку треугольниками, которую я понимаю и модель без проникновения тогда всё понимаю покачто
Спасибо. Не уверен, что все понял. У меня почти нет 3д опыта. Я понимаю задачу оптимизации меша, можно путем перекомпоновки индексов, можно чистить лишнии вершины например сгруппировав их по нормалям и с какой-то толерантностью провести union. Но я плохо понимаю где может понадобится триангуляция сложного контура.
если вы о безье, я с ним не так силён покачто, SO83KQuuZvg(про безье тут туториалист укажет пункт где посмотреть что почитать), поможет в сглаживании, там есть несколько подходов просто функции которые генерят из шума гладкость, а есть ситуация от безье где вроде по безье с коеффициентом можно паковать и распаковывать например террейн, вообщем вы верно идёте, но тема большая, по запаковке с безье + коффициент (вроде такое есть), +анимации пользуются пространством плавности движения, вобщем тема глубокая, +шрифт использует безье
Это, конечно, очень интересно. А зачем это нужно? В чем, собственно, смысл?
Earcut - базовый, почти учебный алгоритм триангуляции
Вы бы хоть термины объясняли, которые используете. Для меня триангуляция это, прежде всего, один из способов радиопеленгации. Потупил, пытаясь понять, что происходит на движущейся картинке, пока не дошло, что вы про что-то другое рассказыть пытаетесь.
Я даже не подумал, что может быть разночтение. В статье речь идет про один из алгоритмов компьютерной графики.
Я усвоил этот термин когда никакой компьютерной графики в массовом сознании ещё не существовало, а охота на лис уже была весьма популярна у школьников и не только ))
Вопрос от человека очень далекого от видеокарт и треугольников. Вот я разрезал руками вот так:
сделал 30 резов и получил 31 треугольник.
Вот кадр из вашей анимации:
получилось 31 реза и 32 треугольника. Есть ли тут ошибка с моей стороны? (я пересчитывал но не нашел) Это первый вопрос.
и второй - производительность как правило имеет прямую зависимость от используемой памяти. тот алгоритм который у меня сразу родился в голове использует дополнительную память, имеет теоретический максимум O(N*N), хотя скорее всего он будет очень близок к O(N) с большей стороны.
На всякий случай пошёл из хобота, разные цвета соответствую разным шагам алгоритма:
получается 31 рез.
придумал еще один способ, так же 31 рез и 32 треугольника, наверное в первом я где-то недоглядел
Кличество треугольников всегда одинаковое, если вы не создаете новых точек внутри.
Пусть у нас T треугльников и N изначальных точек. Если взять 3Т - мы взяли все стороны всех треугольников, но отрезки внутри были подсчитаны 2 раза от двух треугольников с двух сторон. Так что, если добавить N внешних отрезков еще раз, то мы получим каждый отрезок подсчитаным ровно 2 раза. Обозначим количество отрезков E. Получаем E=(3T+N)/2
С другой стороны, есть соотношение Эйлера : N+T-E=1 (тут не 2 как обычно, потому что есть еще внешняя область).
Подставив выражение выше и причесав все мы получаем T=N-2.
Ну, или можно по индукции доказывать этим же самым отрезанием "ушей". Мы выкидываем одну точку и один треугольник. Остановмися, когда будет в конце один треугольник и 3 точки. Т.е точек всегда на 2 больше, чем треугольников.
такое мне все равно непонятно, дома уже пересчитываю и всё равно на первой картинке 31 треугольник, а не 32.
Вы ошиблись в подсчете. Треугольников всегда ровно на 2 меньше, чем точек. Это математически доказывается.
) это я понял, оно же в самом конце комментария написано. я о том что:
Если взять 3Т - мы взяли все стороны всех треугольников, но отрезки внутри были подсчитаны 2 раза от двух треугольников с двух сторон.
это не ясно из чего следует
есть соотношение Эйлера
всех соотношений не запомнить
по индукции
а про это часто говорят но что за зверь никак не могу усвоить
PS: только прошу не тратьте время на ответ, это ничему не поможет
Да, вполне возможно, что где-то потерялся — я тоже пересчитал, но не увидел. Иногда в вырожденных случаях может такое проскочить и в "плохом"" алгоритме.
O(N) — это только грубая оценка, особенно на малых N она мало что говорит. На практике современные CPU предпочитают data-oriented подходы, где важнее не столько асимптотика, сколько поведение в кэше. Аллокации, пропуски по памяти, ветвления — всё это может легко перебить разницу между O(N) и O(N^2).
И как правильно заметили в первом комментарии — сама триангуляция это лишь первый этап. Потом важно эффективно передать mesh на GPU.
Глянте мою предыдущую статью она об алгоритме Nlog(N)
Нашел его
Добавил недостающий элемент.
PS. Не увидел, что уже нашли.
Earcut на битах