Все это важно, но иногда из-за стресса экзамен, собеседование, дедлайн не дают выспаться. И вот я нашел по истине простой и работающий метод. Вечером выходим гулять и в идеале быстрым шагом ходим не менее 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 назад, в нем гораздо сложнее победить дегенеративные случаи: общие вершины, ребра, элеменирующие ребра. Нет четкого подхода как их обрабатывать, остаешься с этим один на один. Мне так и не удалось довести результат до того, что бы он был корректен при любых входных данных. Из единственного плюса могу отметить его кажущуюся простоту.
Да вы правы, задача имеет не мало подводных камней, в основном связанных с точностью вычислений. Например, такая казалось бы тривиальная проблема, как определение принадлежности точки прямой, становится не однозначной при работе с числами с плавающей точкой. В случае целочисленных вычислений возникают свои трудности, например, в вопросе: определения точки пересечения отрезков (0, 0)-(4, 0) и (1, -2)-(2, 2)? Это (1, 0) или (2, 0)? Оба этих решения не лежат на обоих отрезках, что приводит к искажению изначальной картины.
Однако, несмотря на сложности, эти проблемы можно решить, если принять ряд условностей. В этой статье я сознательно опустил ряд сложных деталий, чтобы сфокусироваться на основной концепции. Но, судя по вашему интересу и комментариям, тема действительно заслуживает продолжения.
Все это важно, но иногда из-за стресса экзамен, собеседование, дедлайн не дают выспаться. И вот я нашел по истине простой и работающий метод. Вечером выходим гулять и в идеале быстрым шагом ходим не менее 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 назад, в нем гораздо сложнее победить дегенеративные случаи: общие вершины, ребра, элеменирующие ребра. Нет четкого подхода как их обрабатывать, остаешься с этим один на один. Мне так и не удалось довести результат до того, что бы он был корректен при любых входных данных. Из единственного плюса могу отметить его кажущуюся простоту.
Да вы правы, задача имеет не мало подводных камней, в основном связанных с точностью вычислений. Например, такая казалось бы тривиальная проблема, как определение принадлежности точки прямой, становится не однозначной при работе с числами с плавающей точкой. В случае целочисленных вычислений возникают свои трудности, например, в вопросе: определения точки пересечения отрезков (0, 0)-(4, 0) и (1, -2)-(2, 2)? Это (1, 0) или (2, 0)? Оба этих решения не лежат на обоих отрезках, что приводит к искажению изначальной картины.
Однако, несмотря на сложности, эти проблемы можно решить, если принять ряд условностей. В этой статье я сознательно опустил ряд сложных деталий, чтобы сфокусироваться на основной концепции. Но, судя по вашему интересу и комментариям, тема действительно заслуживает продолжения.