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