Подскажите пожалуйста, методику, либо алгоритм, разрезание произвольной объемной невыпуклой фигуры плоскостью.
Например, у нас есть трехмерное тело (в идеале куб) описанное 8 точками x,y,z. Нам необходимо отсечь от него часть произвольной плоскостью ( и так несколько раз ).
После этого, посчитать объем получившейся фигуры.
Здравствуйте, Ev., Вы писали:
Ev.>Подскажите пожалуйста, методику, либо алгоритм, разрезание произвольной объемной невыпуклой фигуры плоскостью.
Ev.>Например, у нас есть трехмерное тело (в идеале куб) описанное 8 точками x,y,z. Нам необходимо отсечь от него часть произвольной плоскостью ( и так несколько раз ). Ev.>После этого, посчитать объем получившейся фигуры. Ev.>
Можно попробовать применить метод Монте-Карло. Для этого потребуется решить задачу принадлежности точки телу.
Навскидку, предлагаю решать задачу принадлежности точки телу так:
выпустить луч из точки (например, перпендикуляр к Ox). Пробежав по всем плоскостям граней определить пересекает ли луч эту плоскость.
Если пересекает, то спроектировать грань и луч на Ox — свели задачу к принадлежности точке фигуре. Посчитать таким образом количество пересекаемых граней — если это количество нечетное, то точка внутри тела, если четное, то вне тела.
Учтем, что тело рассекали плоскостями. Для этого для каждой точки попавшей внутрь тела вычислим с какой стороны она находиться от каждой плоскости (подставить координаты в каноническое уравнение) — это однозначно задает какому "куску" тела она принадлежит.
Здравствуйте, akochnev, Вы писали:
A>Здравствуйте, Ev., Вы писали:
Ev.>>Подскажите пожалуйста, методику, либо алгоритм, разрезание произвольной объемной невыпуклой фигуры плоскостью.
Ev.>>Например, у нас есть трехмерное тело (в идеале куб) описанное 8 точками x,y,z. Нам необходимо отсечь от него часть произвольной плоскостью ( и так несколько раз ). Ev.>>После этого, посчитать объем получившейся фигуры. Ev.>>
A>Можно попробовать применить метод Монте-Карло. Для этого потребуется решить задачу принадлежности точки телу. A>Навскидку, предлагаю решать задачу принадлежности точки телу так: A>выпустить луч из точки (например, перпендикуляр к Ox). Пробежав по всем плоскостям граней определить пересекает ли луч эту плоскость. A>Если пересекает, то спроектировать грань и луч на Ox — свели задачу к принадлежности точке фигуре. Посчитать таким образом количество пересекаемых граней — если это количество нечетное, то точка внутри тела, если четное, то вне тела. A>Учтем, что тело рассекали плоскостями. Для этого для каждой точки попавшей внутрь тела вычислим с какой стороны она находиться от каждой плоскости (подставить координаты в каноническое уравнение) — это однозначно задает какому "куску" тела она принадлежит.
Если коротко, то выбираем случайным образом n точек из некоторого куба, который содержит тело. Считаем количество точек k, которое попало в нужный кусок тела. Объем куска тела будет относиться к объему куба как k/n. Соответственно, нужно уметь определять принадлежит ли данная точка телу. Примерный алгоритм я и привел выше.
Здравствуйте, akochnev, Вы писали:
A>http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%9C%D0%BE%D0%BD%D1%82%D0%B5-%D0%9A%D0%B0%D1%80%D0%BB%D0%BE
A>Если коротко, то выбираем случайным образом n точек из некоторого куба, который содержит тело. Считаем количество точек k, которое попало в нужный кусок тела. Объем куска тела будет относиться к объему куба как k/n. Соответственно, нужно уметь определять принадлежит ли данная точка телу. Примерный алгоритм я и привел выше.
Вы видимо не внимательно прочитали условие задачи.
У нас есть тело, описанное 8-ю точками (кубом оно может являться только в очень редких случаях). Нужно это тело отсечь тремя произвольными плоскостями.
В итоге, у нас получится какое-то новое тело, описанное уже другим набором точек. Дак вот, нужно посчитать точный объем этого тела.
Сложность данной задачи состоит в том, что даже если представить, что мы не отсекаем первоначальное тело, подсчитать его объем также проблематично.
Сейчас, для подсчета объема тела описанного 8 точками, я использую 2 алгоритма.
1. Если тело — куб, то объем = высота * ширина * глубина
2. Если тело — искаженный куб, то разбиваем тело на 6 тетраэдров и считаем в них объем по формуле 1/3*S*h, где S — площадь грани тетраэдра, h — высота, опущенная на эту грань. Затем суммируем объемы 6-ти тетраэдров
Если тело вывернуто, то тут пока проблемы.
Соответственно, если тело после отсечения принимает новую неизвестную форму, совершенно не ясно как подсчитать его объем.
Мне часто говорят, что не умею понятно объяснять
Я специально кинул ссылку на метод, посмотрите, там есть пример расчета площади.
A>>Если коротко, то выбираем случайным образом n точек из некоторого куба, который содержит тело.
Здесь я имел ввиду, что берем любой куб, содержащий тело.
Ev.>В итоге, у нас получится какое-то новое тело, описанное уже другим набором точек. Дак вот, нужно посчитать точный объем этого тела.
Метод Монте-Карло не точный. Он всегда дает приближенный результат с некоторой надежностью, которая зависит от количества выбираемых точек.
Но в Вашей задаче он позволяет избежать явного нахождения результата отсечения. А так как в первом сообщении было:
Ev.>Подскажите пожалуйста, методику, либо алгоритм, разрезание произвольной объемной невыпуклой фигуры плоскостью.
то данный метод мне кажется наиболее подходящим.
Если же самый сложный случай — это искаженный куб, то можно найти результат отсечения "в лоб", а как у Вас написано разбивать на тетраэдры.
Здравствуйте, Ev., Вы писали:
Ev.>Подскажите пожалуйста, методику, либо алгоритм, разрезание произвольной объемной невыпуклой фигуры плоскостью.
Ev.>Например, у нас есть трехмерное тело (в идеале куб) описанное 8 точками x,y,z. Нам необходимо отсечь от него часть произвольной плоскостью ( и так несколько раз ). Ev.>После этого, посчитать объем получившейся фигуры. Ev.>
Напрашивается вопрос при сечении плоскостью какую часть фигуры считать отсеченной а какую оставшейся?
Здравствуйте, Ev., Вы писали:
Ev.>Например, у нас есть трехмерное тело (в идеале куб) описанное 8 точками x,y,z. Нам необходимо отсечь от него часть произвольной плоскостью ( и так несколько раз ). Ev.>После этого, посчитать объем получившейся фигуры.
А что, если пойти таким простым путём:
1) представить тело в виде композиции примитивных тел (например, тетраэдров)
2) выполнить сечение всех этих примитивов, получая всё новые и новые примитивы
3) и посчитать, наконец, сумму объёмов
Куб (и любая его деформаця) раскладывается на 4 тетраэдра.
При сечении тетраэдра получается тетраэдр + тетраэдр либо тетраэдр + треугольная призма, которая раскладывается на два тетраэдра.
Можно, конечно, попробовать всё время работать с телом, заданным поверхностью из многоугольников...
Это выбор — либо много простой однотипной возни с тетраэдрами, либо чуть меньше, но весьма затейливой возни с сечением произвольного тела и подсчётом его объёма.
Я за тетраэдры
Перекуём баги на фичи!
Re[2]: сечение трехмерной фигуры плоскостью
От:
Аноним
Дата:
25.08.10 09:27
Оценка:
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Ev., Вы писали:
Ev.>>Например, у нас есть трехмерное тело (в идеале куб) описанное 8 точками x,y,z. Нам необходимо отсечь от него часть произвольной плоскостью ( и так несколько раз ). Ev.>>После этого, посчитать объем получившейся фигуры.
К>А что, если пойти таким простым путём: К>1) представить тело в виде композиции примитивных тел (например, тетраэдров) К>2) выполнить сечение всех этих примитивов, получая всё новые и новые примитивы К>3) и посчитать, наконец, сумму объёмов
К>Куб (и любая его деформаця) раскладывается на 4 тетраэдра. К>При сечении тетраэдра получается тетраэдр + тетраэдр либо тетраэдр + треугольная призма, которая раскладывается на два тетраэдра.
К>Можно, конечно, попробовать всё время работать с телом, заданным поверхностью из многоугольников...
К>Это выбор — либо много простой однотипной возни с тетраэдрами, либо чуть меньше, но весьма затейливой возни с сечением произвольного тела и подсчётом его объёма. К>Я за тетраэдры
Проблема в том, что расчет объема через тетраэдры не всегда дает точный объем тела, т.к. все зависит от того, как именно делить тело на тетраэдры.
Здравствуйте, Аноним (Ev. ?), Вы писали:
А>Проблема в том, что расчет объема через тетраэдры не всегда дает точный объем тела, т.к. все зависит от того, как именно делить тело на тетраэдры.
Ну, с какой-то потерей точности всё равно мы столкнёмся, получая точки пересечения рёбер плоскостями.
Или мы реализуем точную рациональную арифметику — и тогда погрешности устранятся сами по себе.
Или нужно указать, какие погрешности для нас приемлемы, а какие уже нет.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Аноним (Ev. ?), Вы писали:
А>>Проблема в том, что расчет объема через тетраэдры не всегда дает точный объем тела, т.к. все зависит от того, как именно делить тело на тетраэдры.
К>Ну, с какой-то потерей точности всё равно мы столкнёмся, получая точки пересечения рёбер плоскостями.
К>Или мы реализуем точную рациональную арифметику — и тогда погрешности устранятся сами по себе. К>Или нужно указать, какие погрешности для нас приемлемы, а какие уже нет.
Тут не совсем о погрешности идет речь, дело в том, что деление тела на тетраэдры должно быть каким-то умным, т.к. в разных случаях получается разный объем.
Вот например тело с координатами:
X,Y,Z
0,0,0
0,100,10
100,0,10
100,100,0
0,0,20
0,100,10
100,0,10
100,100,20
В зависимости от того, как разбивать на тетраэдры, объем будет варьироваться от 66000 до 133000, хотя объем тела равен 100000
Здравствуйте, Ev., Вы писали:
Ev.>Тут не совсем о погрешности идет речь, дело в том, что деление тела на тетраэдры должно быть каким-то умным, т.к. в разных случаях получается разный объем. Ev.>Вот например тело с координатами: Ev.>X,Y,Z Ev.>A 0,0,0 Ev.>B 0,100,10 Ev.>C 100,0,10 Ev.>D 100,100,0 Ev.>E 0,0,20 Ev.>F 0,100,10 Ev.>G 100,0,10 Ev.>H 100,100,20
(добавил имена вершин)
Ev.>В зависимости от того, как разбивать на тетраэдры, объем будет варьироваться от 66000 до 133000, хотя объем тела равен 100000
Начнём с того, что это не перекошенный куб, а октаэдр: вершины B=F, C=G.
ACBD — это не одна сторона, а две, с линией перелома по AD или по BC (внезапно, вогнутый октаэдр).
То же самое и с EFHG.
По шести точкам можно построить один выпуклый и кучу разных невыпуклых октаэдров, в том числе вырождающихся до пары тетраэдров.
Вот и расхождения в объёме. Так что "хотя объём тела равен 100000" — это тоже один частный случай. Могло быть и 50000.
Здравствуйте, Ev., Вы писали:
Ev.>Вот например тело с координатами:
<>
Это, кстати, иллюстрация того факта, что тело, "заданное 8 точками" — задано неполно.
Надо задавать не только точки, но и рёбра.
Даже на картинке
неочевидно, являются ли 1243 и 5687 плоскостями, или там есть ненарисованная линия перегиба по одной или другой диагонали.
Стандарты инженерной графики предполагают, что если ничего не нарисовано, значит, перегиба там нет.
Ну, тогда нужно за этим следить, и давать по пальцам за ввод несогласованных данных.
Здравствуйте, Ev., Вы писали:
Ev.>Тут не совсем о погрешности идет речь, дело в том, что деление тела на тетраэдры должно быть каким-то умным, т.к. в разных случаях получается разный объем. Ev.>Вот например тело с координатами: Ev.>X,Y,Z Ev.>0,0,0 Ev.>0,100,10 Ev.>100,0,10 Ev.>100,100,0 Ev.>0,0,20 Ev.>0,100,10 Ev.>100,0,10 Ev.>100,100,20
Ev.>В зависимости от того, как разбивать на тетраэдры, объем будет варьироваться от 66000 до 133000, хотя объем тела равен 100000
о_О
из приведенных цифр следует что у вас там ошибка...
и скорее всего в алгоритме разбиения на тетраэдры
а если попробуете разбить не на 6, а на 5 тетраэдров, это уже на цикл пересчета меньше)
при сечении тетраэдра плоскостью может получиться либо тетраэдр либо выпуклая 5 гранная фигура, которую в свою очередь можно разделить на 6 тетраэдров. Соответственно при увеличении количества сечений будет происходить увеличение пересчета количествава тетраэдров, образующих вашу исходную фигуру после сечения плоскостями.
объем тетраэда думаю проще считать по этой формуле
осталось только это все запрограммировать, удачи
Здравствуйте, Ev., Вы писали:
Ev.>Подскажите пожалуйста, методику, либо алгоритм, разрезание произвольной объемной невыпуклой фигуры плоскостью.
Ev.>Например, у нас есть трехмерное тело (в идеале куб) описанное 8 точками x,y,z. Нам необходимо отсечь от него часть произвольной плоскостью ( и так несколько раз ). Ev.>После этого, посчитать объем получившейся фигуры. Ev.>
Могу предложить такой метод расчета объема многогранника: триангулировать все нетреугольные грани
в цикле по всем граням посчитать
V = sum((p1^p2)*p3))/6
, где p1..p3 — координаты вершин (векторы), ^ — векторное произведение, * — скалярное произведение
Важно соблюдать одинаковый порядок обхода вершин в гранях (скажем, нормаль наружу).
Точность метода тем лучше, чем ближе центр масс многогранника к началу координат (если нет — есть смысл его туда переместить).
Сечение плоскостями при таком количестве граней вроде бы трудностей не представляет.
Здравствуйте, Ev., Вы писали:
Ev.>Подскажите пожалуйста, методику, либо алгоритм, разрезание произвольной объемной невыпуклой фигуры плоскостью.
Ev.>Например, у нас есть трехмерное тело (в идеале куб) описанное 8 точками x,y,z. Нам необходимо отсечь от него часть произвольной плоскостью ( и так несколько раз ). Ev.>После этого, посчитать объем получившейся фигуры. Ev.>
Чтобы посчитать объем выпуклого многогранника, полученного отсечением плоскостью части куба, нужно сначала определить какие вершины из начального набора остались (плюс точки пересечения ребер с рёбрами новых граней). Это просто: из знака результата подстановки координат вершины в уравнение плоскости (у одних "+", у других "-" — по разные стороны). Т.е. задача сводится к вычислению объема выпуклого многогранника. Кажется, самое оно — про группы можно пропустить в конце как раз формулы (даже для более сложного случая).
).
Перекуём баги на фичи!
