Найти узлы решётки, принадлежащие телу.
off-lattice вершинамиможешь пояснить, что это значит?
точное решение можно получать с помощью библиотеки ISL (гуглить "integer set library") или, возможно, polylib и PPL (Parma polyhedra library)
в ISL можно задать выпуклое тело как пересечение полупространств и спросить все целые точки, попавшие в него
Это наверное не в тему, но самый быстрый способ определить принадлежность точки двумерному полигону (неважно, выпуклому или нет) - провести отрезок из этой точки в точку, заведомо не принадлежащую телу, и посчитать количество пересечений с границей тела. Если нечетное - то точка внутри, если четное - то снаружи.
Можно попробовать экстраполировать на трехмерное тело.
Можно попробовать экстраполировать на трехмерное тело.
Тут тело выпуклое, так что ситуация вообще шикарная.
посчитать количество пересечений с границей тела. Если нечетное - то точка внутри, если четное - то снаружи.Только нужно ещё учитывать, что этот отрезок может пересечь границу тела в вершине. При этом точка пересечения одна, но интересующая нас точка может быть как снаружи тела, так и внутри него.
Тут тело выпуклое, так что ситуация вообще шикарная.Да ещё и многогранник!
В общем, если тело — выпуклый многогранник, то каждый треугольник, который задаёт часть его поверхности, задаёт плоскость. Нормаль к этой плоскости мы можем найти.
Задача сильно упрощается, если известно ещё и по какую сторону от каждой плоскости лежит тело. (Это также легко можно вычислить: взять вершину многогранника, которая не лежит на плоскости, и посчитать с какой стороны от плоскости она располагается — см. ниже.)
Так вот. Считаем, что у нас есть для каждого треугольника набор трёх чисел — координаты вектора нормали, направленной внутрь тела.
Берём произвольную точку (про которую хотим понять где она лежит) — набор трёх её координат (x, y, z).
Для каждой нормали (nx, ny, nz) считаем h = x * nx + y * ny + z * nz. Если h < 0, то точка точно снаружи. Если h = 0, то точка лежит на плоскости.
Таким образом, если есть хотя бы одно отрицательное h для какой-либо нормали, то точка лежит вне тела. Если все h положительные, то точка лежит внутри тела. Если все h неотрицательные и при этом есть хотя бы одно h равное нулю, то точка лежит на поверхности тела.
Если тело не меняется во времени или довольно редко меняется (по сравнению с частотой подсчётов положения точек относительно данного тела то следует все нормали посчитать заранее и пользоваться расчётами, которые я привёл. Это быстро и довольно точно (погрешность только из-за неточных представлений чисел с плавающей точкой).
ЗЫ
h, получаемое по приведённой выше формуле, — расстояние от точки до плоскости умноженное на длину вектора нормали.
Не, это круто, но тут не учитывается, что нам надо не принадлежность произвольных точек считать, а именно точек сетки. Например, если (0, 0, x) и (0, 0, y) принадлежат этому многограннику (выпуклому то все промежуточные заведомо тоже. Поэтому полный перебор не особо может сгодиться, хотя зависит от чисел в задаче.
Можно для каждой пары целых x,y находить минимальное и максимальное целое z такое, что точка (x,y,z) лежит внутри. Из-за выпуклости точки с промежуточными z тоже внутри.
Для этого для каждой пары целых x,y нужно найти 2 треугольника (верхний и нижний проекции которых на плоскость XY содержат точку (x,y). Короче задача сводится к нахождению точек решетки внутри треугольника на плоскости.
Для этого для каждой пары целых x,y нужно найти 2 треугольника (верхний и нижний проекции которых на плоскость XY содержат точку (x,y). Короче задача сводится к нахождению точек решетки внутри треугольника на плоскости.
ну да, в принципе, если знать ограничивающий параллелепипед всей фигурки, то можно довольно эффективно реализовать.
Не, это круто, но тут не учитывается, что нам надо не принадлежность произвольных точек считать, а именно точек сетки.Да, это в описанном мной методе никак не учитывается.
полный переборГде ты увидел полный перебор?
Там для каждого треугольника считается число (три умножения и два сложения). Но нам, в принципе, не обязательно вычислять все эти числа, если хотя бы одно будет отрицательным.
Где ты увидел полный перебор?ну а как ты от метода определения принадлежности точки телу перейдешь к подсчету количества этих точек?
Чиорт, повёлся за ежом... 
Подумал, что надо быстро определять принадлежит ли точка телу или нет.
Подумал, что надо быстро определять принадлежит ли точка телу или нет.
Спасибо. Я примерно так и делаю, только, помимо определения, по какую сторону от граней лежит точка, я зачем-то проверяю, есть ли пересечение вектора из условного "центра" тела в данную точку с данной гранью (а не только с её плоскостью). Действительно, эта проверка, похоже, нафиг не нужна, она делается потому, что в другом месте программы я ищу именно пересечение с гранью, и использую ту же функцию. Попробую сделать отдельную функцию для проверки принадлежности точки тела без проверки: сейчас это самое жрущее место в программе, поглощает 80% всего времени, и любая оптимизация будет полезна. Огромное спасибо.
Хотя я сейчас подумал, не факт, что это оптимизация. У меня проверка с каждой гранью идёт дольше, но зато если есть пересечение, дальнейшая проверка других граней не нужна.
Так что я просто попробую ваш метод и сравню. В любом случае, спасибо.
Так что я просто попробую ваш метод и сравню. В любом случае, спасибо.
По-моему лучше определить алгоритм по уменьшению количества узлов проверяемого объема. А уж способ проверки принадлежности точки не сильно важен. Так например, точки-узлы, расположенные сравнительно недалеко от центра тела по сравнению с размерами тела, проверять смысла нет.
При выпуклом теле, кстати, можно воспользоваться OpenGL, отрисовав объект с нескольких сторон и проанализировав, какие узлы нарисовались.
При выпуклом теле, кстати, можно воспользоваться OpenGL, отрисовав объект с нескольких сторон и проанализировав, какие узлы нарисовались.
Эта проверка не нужна, так как если многогранник выпуклый и отрезок, соединяющий интересующую нас точку и известную внутреннюю точку, пересекает плоскость грани, то эта точка находится снаружи многогранника независимо от того, пересекает ли отрезок саму грань. Условие пересечения плоскости в моём случае: h < 0.
Вот, кстати, идейка, которую можно попробовать развить.
Если у нас вершины выпуклого многогранника задаются координатами (xi, yi, zi i = 1, ..., n, то любая внутренняя его точка задаётся координатами \sum_i ki (xi, yi, zi причём k_i >= 0 и \sum_i ki = 1.
Вот, кстати, идейка, которую можно попробовать развить.
Если у нас вершины выпуклого многогранника задаются координатами (xi, yi, zi i = 1, ..., n, то любая внутренняя его точка задаётся координатами \sum_i ki (xi, yi, zi причём k_i >= 0 и \sum_i ki = 1.
а ISL чем-то не устроил?
Как вариант еще:
1. Выбирается несколько плоскостей объекта, образующих замкнутый объект. От 4-х до 6.
2. Вычисляется узлы внутри полученного объекта.
3. Поток к этому набору применяются по одной остальные плоскости. По ходу удаляя из начального набора узлы, которые не прошли проверку.
1. Выбирается несколько плоскостей объекта, образующих замкнутый объект. От 4-х до 6.
2. Вычисляется узлы внутри полученного объекта.
3. Поток к этому набору применяются по одной остальные плоскости. По ходу удаляя из начального набора узлы, которые не прошли проверку.
Тут тело выпуклое, так что ситуация вообще шикарная.а шо, бывает вогнутое тело?
Оставить комментарий
Inflict84
Тело (условно говоря, односвязное выпуклое - например, смахивающее на немного смятый шар, хотя в идеале любое) живет в дискретной трехмерной решётке. Поверхность тела задана треугольниками с off-lattice вершинами. Надо узнать, какие узлы решётки находятся внутри тела, и сделать это как можно более быстрыми вычислениями. В принципе, 100%-ная точность определения принадлежности точки телу не требуется, но желательна.Буду признателен за советы,
Заранее спасибо.