Все это важно, но иногда из-за стресса экзамен, собеседование, дедлайн не дают выспаться. И вот я нашел по истине простой и работающий метод. Вечером выходим гулять и в идеале быстрым шагом ходим не менее 2 часов, физически изматывая себя. После таких прогулок сплю как убитый. Надеюсь совет поможет и вам
Все верно, например, можно отсортировать по X и проверять только те точки, что лежат внутри проекции треугольника на ось oX. Это даст ощутимый буст на больших N.
Но Earcut64 — это про малые N (<= 64). Для больших N у меня уже есть более эффективный алгоритм с асимптотикой N log N.
А при малых N, особенно в простых случиях, ситуация будет такая: проекция "большого уха" затронет почти все точки, так что фильтрация не даст заметного выигрыша.
Резюмируя Earcut64 задумывался, как брут форс, для своей ниши - малых полигонов.
Это вы смотрите в сторону условия Делоны. Любую трингуляцию можно привести к "красивой" если пройти по всем парам и проверить на условие Делоне. В предыдущей статье про это было.
Да, вполне возможно, что где-то потерялся — я тоже пересчитал, но не увидел. Иногда в вырожденных случаях может такое проскочить и в "плохом"" алгоритме.
O(N) — это только грубая оценка, особенно на малых N она мало что говорит. На практике современные CPU предпочитают data-oriented подходы, где важнее не столько асимптотика, сколько поведение в кэше. Аллокации, пропуски по памяти, ветвления — всё это может легко перебить разницу между O(N) и O(N^2).
И как правильно заметили в первом комментарии — сама триангуляция это лишь первый этап. Потом важно эффективно передать mesh на GPU.
Глянте мою предыдущую статью она об алгоритме Nlog(N)
Спасибо. Не уверен, что все понял. У меня почти нет 3д опыта. Я понимаю задачу оптимизации меша, можно путем перекомпоновки индексов, можно чистить лишнии вершины например сгруппировав их по нормалям и с какой-то толерантностью провести union. Но я плохо понимаю где может понадобится триангуляция сложного контура.
iOverlay тоже очень стабилен. Я бы не стал разгонять шум вокруг неё, если бы не был в ней так уверен. Rust — как раз тот язык, который поощряет писать тесты на код, и мне это прям сильно зашло. Попробуйте запустить cargo test — там уже, наверное, ближе к двумстам тестам. И часть из них — рандомные. Если честно, я думаю, что она более стабильна, чем Clipper. Полгода назад iOverlay вошёл в состав GeoRust. Первое время, да, мне насыпали ошибок, но все они были ошибками имплементации, а не подхода как такового.
Так что пробуйте смело, а если найдете баг, тоже хорошо.
Это у вас какая прикладная область была? 3D-принтер? Я хорошо погружён во все эти алгоритмы — iOverlay — не первый мой заход на эту территорию. Были и другие: например, я очень долго пытался реализовать рабочее решение, используя алгоритм Greiner-Hormann. Clipper, как он сам пишет, использует алгоритм Vatti Clipping. Проблема всех этих алгоритмов в том, что они дают лишь общее направление — там очень много подводных камней, о которые и разбиваются все эти решения. И на продвинутом уровне интересен не сам базовый алгоритм, а то, как были решены все эти трудности. И да читать 2000 строк очень сложно, я сам честно пробовал несколько раз, как раз на C#
Вы про iOverlay я полагаю. Clipper очень известная библиотека и для меня она больше как старший брат с которым ты себя сравниваешь и с которого берёшь пример. Но как она реализована я до конца так и не понял. Polybooljs вот кто открыл мне глаза. Если кто сможет объяснить принцип работы Clipper я с удовольствием послушаю.
Я тоже большой фанат фиксированных вычислений, они предсказуемы и детерминированы на всех платформах. Мне показалось что в моем случай точности pi/512 за глаза поэтому я использовал табличный подход. Для корня я использовал побитовый поиск, быстр и прост. Но потом понял что нативный способ все равно быстрее и оставил так:
#[inline(always)]
fn sqrt(self) -> FixFloat {
let a = (self as f64).sqrt() as i64;
let b = a + 1;
if b * b > self { a } else { b }
}
Еще вопрос как вы храните дробную часть? У вас помножено на какую-то константу?
Хороший разбор, добавил себе в закладки. У меня на повестки алгоритм как собрать из точек кривую Безье и тоже надо будет думать о компромиссе количество точек/точность интерполяции
Все так, сам работал в одном их стартапе по разработки EDA, писал для них DRC правила. В первую очередь клиенты были их университеты где учат микросхемы проектировать. Интересно у нас есть такие университеты?
Все понятно, мой коммент был просто задуматься об этом. Это как с моделями солнечной системы, они не пропорциональны, а когда думаешь об этом масштаб тут же раскрывается
Проблему, экзотической арифметики, лучше оставить на уровне библиотек. Включение всех возможностей в стандартную библиотеку языка — это всегда компромисс между функциональностью и популярностью. Раздутый foundation может замедлить развитие других приоритетных частей.
Я пробовал данный алгоритм лет 5 назад, в нем гораздо сложнее победить дегенеративные случаи: общие вершины, ребра, элеменирующие ребра. Нет четкого подхода как их обрабатывать, остаешься с этим один на один. Мне так и не удалось довести результат до того, что бы он был корректен при любых входных данных. Из единственного плюса могу отметить его кажущуюся простоту.
Если ИИ мимикрировал под человека должны увидеть спад, а не плато ИИ текстов.
Все это важно, но иногда из-за стресса экзамен, собеседование, дедлайн не дают выспаться. И вот я нашел по истине простой и работающий метод. Вечером выходим гулять и в идеале быстрым шагом ходим не менее 2 часов, физически изматывая себя. После таких прогулок сплю как убитый. Надеюсь совет поможет и вам
Все верно, например, можно отсортировать по X и проверять только те точки, что лежат внутри проекции треугольника на ось oX. Это даст ощутимый буст на больших N.
Но Earcut64 — это про малые N (<= 64).
Для больших N у меня уже есть более эффективный алгоритм с асимптотикой N log N.
А при малых N, особенно в простых случиях, ситуация будет такая: проекция "большого уха" затронет почти все точки, так что фильтрация не даст заметного выигрыша.
Резюмируя Earcut64 задумывался, как брут форс, для своей ниши - малых полигонов.
Это вы смотрите в сторону условия Делоны. Любую трингуляцию можно привести к "красивой" если пройти по всем парам и проверить на условие Делоне. В предыдущей статье про это было.
Нашел его
Да, вполне возможно, что где-то потерялся — я тоже пересчитал, но не увидел. Иногда в вырожденных случаях может такое проскочить и в "плохом"" алгоритме.
O(N) — это только грубая оценка, особенно на малых N она мало что говорит. На практике современные CPU предпочитают data-oriented подходы, где важнее не столько асимптотика, сколько поведение в кэше. Аллокации, пропуски по памяти, ветвления — всё это может легко перебить разницу между O(N) и O(N^2).
И как правильно заметили в первом комментарии — сама триангуляция это лишь первый этап. Потом важно эффективно передать mesh на GPU.
Глянте мою предыдущую статью она об алгоритме Nlog(N)
Я даже не подумал, что может быть разночтение. В статье речь идет про один из алгоритмов компьютерной графики.
Спасибо. Не уверен, что все понял. У меня почти нет 3д опыта. Я понимаю задачу оптимизации меша, можно путем перекомпоновки индексов, можно чистить лишнии вершины например сгруппировав их по нормалям и с какой-то толерантностью провести union. Но я плохо понимаю где может понадобится триангуляция сложного контура.
Триангуляция в целом или Earcut? Триангуляция нужна потому, что видеокарта так рисует(рендерит). Earcut как оптимизация триангуляции на малых N.
iOverlay тоже очень стабилен. Я бы не стал разгонять шум вокруг неё, если бы не был в ней так уверен.
Rust — как раз тот язык, который поощряет писать тесты на код, и мне это прям сильно зашло.
Попробуйте запустить cargo test — там уже, наверное, ближе к двумстам тестам.
И часть из них — рандомные. Если честно, я думаю, что она более стабильна, чем Clipper.
Полгода назад iOverlay вошёл в состав GeoRust. Первое время, да, мне насыпали ошибок, но все они были ошибками имплементации, а не подхода как такового.
Так что пробуйте смело, а если найдете баг, тоже хорошо.
Это у вас какая прикладная область была? 3D-принтер?
Я хорошо погружён во все эти алгоритмы — iOverlay — не первый мой заход на эту территорию. Были и другие: например, я очень долго пытался реализовать рабочее решение, используя алгоритм Greiner-Hormann.
Clipper, как он сам пишет, использует алгоритм Vatti Clipping.
Проблема всех этих алгоритмов в том, что они дают лишь общее направление — там очень много подводных камней, о которые и разбиваются все эти решения.
И на продвинутом уровне интересен не сам базовый алгоритм, а то, как были решены все эти трудности.
И да читать 2000 строк очень сложно, я сам честно пробовал несколько раз, как раз на C#
Вы про iOverlay я полагаю. Clipper очень известная библиотека и для меня она больше как старший брат с которым ты себя сравниваешь и с которого берёшь пример. Но как она реализована я до конца так и не понял. Polybooljs вот кто открыл мне глаза. Если кто сможет объяснить принцип работы Clipper я с удовольствием послушаю.
Спасибо, да вы правы сейчас попробую добавить
Я тоже большой фанат фиксированных вычислений, они предсказуемы и детерминированы на всех платформах. Мне показалось что в моем случай точности pi/512 за глаза поэтому я использовал табличный подход. Для корня я использовал побитовый поиск, быстр и прост. Но потом понял что нативный способ все равно быстрее и оставил так:
Еще вопрос как вы храните дробную часть? У вас помножено на какую-то константу?
Хороший разбор, добавил себе в закладки. У меня на повестки алгоритм как собрать из точек кривую Безье и тоже надо будет думать о компромиссе количество точек/точность интерполяции
Все так, сам работал в одном их стартапе по разработки EDA, писал для них DRC правила. В первую очередь клиенты были их университеты где учат микросхемы проектировать. Интересно у нас есть такие университеты?
Все понятно, мой коммент был просто задуматься об этом. Это как с моделями солнечной системы, они не пропорциональны, а когда думаешь об этом масштаб тут же раскрывается
Рисунок с окружностями прикольный, но не передает масштаб. Отношение радиусов должно отличается в квадрат раз.
Проблему, экзотической арифметики, лучше оставить на уровне библиотек. Включение всех возможностей в стандартную библиотеку языка — это всегда компромисс между функциональностью и популярностью. Раздутый foundation может замедлить развитие других приоритетных частей.
Я пробовал данный алгоритм лет 5 назад, в нем гораздо сложнее победить дегенеративные случаи: общие вершины, ребра, элеменирующие ребра. Нет четкого подхода как их обрабатывать, остаешься с этим один на один. Мне так и не удалось довести результат до того, что бы он был корректен при любых входных данных. Из единственного плюса могу отметить его кажущуюся простоту.