http://www.g-sharp.net/files/picture.PNG
Нужен алгоритм, определяющий прямоугольные области на каждой грани, внутри которых находятся заштрихованные части куба.
Кто может, подскажите, в какую сторону "копать", т.к. очень нужно
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Отсечение части куба |
| Автор: mr.DUDA 30.10.2005, 14:22 |
| Помогите найти способ, как определить области, заштрихованные на рисунке. Есть куб со стороной 1 и единичная окружность, пересекающая его. Окружность определяется через радиус, координаты центра и нормаль к плоскости. Центр куба совпадает с началом координат, стороны куба ориентированы вдоль декартовых осей (направление осей приведено на рисунке). http://www.g-sharp.net/files/picture.PNG Нужен алгоритм, определяющий прямоугольные области на каждой грани, внутри которых находятся заштрихованные части куба. Кто может, подскажите, в какую сторону "копать", т.к. очень нужно |
| Автор: maxim1000 30.10.2005, 20:41 |
| честно говоря, не очень понятно, что значит "отсечение окружностью"... (впрочем, может, это только мне) если я не ошибаюсь, об отсечении (в данном случае в 3d) можно говорить, когда какая-то поверхность разделяет какое-то тело на две несвязанные части в случае окружности такого не происходит - это даже не поверхность, с тем же успехом можно отсекать от куба что-нибудь с помощью прямой если даже заменить окружность на круг и предположить, что он достаточно большой, то это эквивалентно отсечению плоскостью однако, если окружность пересекает куб, значит, соответствующий круг недостаточно большой и он не делит куб на несвязанные части... P.S. может, описать исходную задачу, при решении которой понадобилось решать эту? Добавлено @ 20:43 вообще, если посмотреть на рисунок, создается впечатление, что речь идет о проекции круга на разные грани куба... в случае куба, да еще и ориентированного по осям, проекция - одно удовольствие - просто отбрасывать одну координату... |
| Автор: mr.DUDA 30.10.2005, 23:00 | ||
| maxim1000, спасибо за ответ. Переформулирую задачу: есть телесный угол, выходящий из центра куба. Телесный угол задан своим направлением и углом раствора. Надо для каждой грани куба определить, пересекается ли она с телесным углом, и если да - то определить прямоугольную область, охваченную телесным углом у этой грани. В итоге должна получиться фигура, аналогичная сферическому сегменту, но начерченная на гранях куба (поэтому говорится об отсечении). Вроде, правильно сформулировал... Можно ещё представить, будто куб со стороной 1/sqrt(2) вписан в сферу с радиусом 1, тогда задача будет сводиться к проекции краевой окружности сферического сегмента на вписанный куб.
Похоже на то, только просто отбрасывать координату не получается, т.к. круг лежит в плоскости, которая вертится вокруг начала координат на произвольные углы. У меня проблемы с проецированием круга на плоскость - никак не могу вывести формулы для эллипса, получающегося при проецировании. Хелп ! |
| Автор: fin 30.10.2005, 23:27 |
| В курсе начертательной геометрии были такие задачи. Правда я шас не упомню, как тогда мы делали. Рисовались проекции на три осных плоскости. И по этим проекциям делались уже разрезы. |
| Автор: maxim1000 31.10.2005, 03:59 |
| ага... что-то проясняется... т.е. из центра выходит конус найти часть, которую он отсекает от куба (точнее от его поверхности)... тут можно подумать так: введем такую проекцию (немного не та, какую обычно используют, нелинейная) у нас есть поверхность куба проекция точки - точка пересечения луча из центра в эту точку и поверхности куба как считается: 1. находим максимальную по модулю координату этой точки 2. делим все на модуль этой координаты у полученной точки все координаты не больше 1 по модулю и одна равна, значит, лежит на поверхности куба т.к. все координаты умножались на одно и то же число - лежит на нужном луче (конечно же, предполагается, что мы не захотим проектировать сам центр координат) так что это - то, что мы искали дальше берем окружность, которая описывает телесный угол, записываем ее в каком-нибудь параметрическом виде и применяем вышеописанное преобразование по идее, там будет три отрезка, на кажлом из которых ровно одна координата будет максимальной по модулю, так что надо будет рассмотреть эти три случая получим аналитическую формулу, а дальше с ней можно делать все, что душе угодно... возможно, возникнут проблемы с вариантом, когда охватывается больше трех граней... там уже надо смотреть P.S. а... да... тут предполагалось, что куб со стороной 2 (т.е. от центра до грани 1) ну потом все это можно поделить на 2... |
| Автор: mr.DUDA 31.10.2005, 08:33 | ||||
попробую... хотя не очень хорошо понял... я пока что лучшего решения, чем перебирать все точки окружности с определённым шагом, и проверять для каждой точки - куда она попала - не нашёл (по крайней мере, работающего решения не получается)...
я тоже помню такие задачки: пересечение двух плоскостей, рисуется 2 треугольника - и погнали; только это не катит, т.к. нужно программно это делать, да и задача отличается (нужно проецировать, а не пересекать 2 плоскости). |
| Автор: DENNN 31.10.2005, 09:24 |
| Я чего-то не понял. Если есть куб и конус, который "из него торчит", то мы просто имеем две пересекающиеся поверхности. Т.е. пишем уравнение для обоих поверхностей и считаем в каких точках они пересекаются. Я прав? |
| Автор: maxim1000 31.10.2005, 15:30 | ||||||
похоже на то...
да, это - более общий случай получится уравнение типа F(x,y,z)=0, которое надо будет решать предложенный мной вариант - один из способов решения этого уравнения... Добавлено @ 15:37
а как задано условие задачи? т.е. в каком виде есть окружность, параметры конуса принципиально от этого, конечно же ничего не зависит, но это влияет на простоту решения... |
| Автор: mr.DUDA 1.11.2005, 10:52 | ||||||
Полностью прав.
Дано: 1) есть куб со стороной 1, центр куба лежит в начале координат; 2) из начала координат выходит конус, описываемый двумя параметрами: направление прямой (kx,ky,kz) и углом конуса (alpha) 3) alpha может быть: 270, 180, 90, 45, 22.5 градусов, и т.д. 4) направление прямой (kx,ky,kz) может быть произвольным 5) высоту конуса (т.е. длину его направляющей прямой) можно считать бесконечной Найти: Для каждой грани куба нужно определить, пересекает ли её конус, и если да - найти область, лежащую внутри конуса. Как минимум, нужно вывести формулы, по которым находится такая область для грани куба, параллельной плоскости XY, т.к. это самый простой вариант. Потом можно будет использовать эти формулы для любой грани куба, просто поворачивая грань и конус к плоскости XY.
Да. У меня проблемы с аналитической геометрией, к сожалению  |
| Автор: DENNN 1.11.2005, 13:32 |
| Ну, определить какие грани конус не пересекает не сложно. Нужно брать угол между нормалью к грани и "вектором направления" конуса (та самая твоя прямая). Если грани ориентированны так, что нормали всегда направленны наружу, а угол не развернутый (меньше 180 градусов), то конус не будет пересекать грань(ни), угол с нормалью которой больше 90 градусов. для граней, которые рассекаются стороной конуса на ЭВМ определять линию пересечения можно итеративно. Скажем, для грани, параллельной пл. OXY, пересекаемой осью конуса под углом alfa, то мы получаем вектор, вершиной расположенный вточке пересечения оси и плоскосит и очерчивающий круг радиуса R. Тогда задача сводится к тому, что необходимо найти все проекции этого вектора на плоскость грани куба. Возбмем одно из положений ветора, когда он находится в плоскости грани за начальное и будем отсчитывать от него угол beta. Тогда спроектироанный на плоскость вектор можно получить как сумму двух векторов: проекция на саму ось пересечения, равная S*cos(beta) и перпендикулярная сосотавляющая в плоскости грани равная sin(beta)*cos(alfa), где S- длина вектора. Постараюсь к вечеру изобразить на рисунке и отсканировать. Только возникает вопрос: в каком виде нужно представить результат? В виде полигона, ввиде набора 3D точек, просто показать, что линия пересечения - это кривая второго порядка (в частном случае эллипс или круг)? |
| Автор: mr.DUDA 1.11.2005, 17:40 | ||||||
DENNN, спасибо за ответ.
Если угол не развёрнутый - тогда всё Ok, но если скажем угол в 270 градусов - как в таком случае определяется, пересекает ли конус грань куба ?
Без рисунка наверное не пойму 
Буду очень благодарен ! Результат нужен в виде прямоугольной области, полностью охватывающей линию пересечения, т.е. для грани OXY нужны координаты (x1;y1)-(x2;y2). Куб можно взять с любой стороной - важен лишь способ вычисления результата. |
| Автор: DENNN 1.11.2005, 18:14 | ||
Если ты представишь себе даный случай, то поймешь, что на самом деле конус просто направлен в противоположную сторону. Т.е. берешь обратное направление конуса и угол у него = 360-угол |
| Автор: cardinal 1.11.2005, 18:27 | ||
Мне тут мысль пришла в голову, что возможно будет полезно просто определить точки пересечение куба с конусом и соединить их векторами. Чем больше точек будет в общем, тем больше будет всяких разных векторов, которые и описывают плоскость, котороя заштрихована. То есть я бы предложил решить задачу не аналитическим а нумерическим образом (или как там по-русски  ). И массив векторов соединяющих точки пересечения и будет описывать твою плоскость. Потом с помощью массива можно наривать ее и повернуть так как тебе захочется.
А хотя если прочитать вот это, то похоже все таки нужно аналитическое решение.  Кстати помоему векторное произведение двух векторов соединяющих точки пересечения (то есть вектор) и описывает плоскость, которая отсекает часть куба... |
| Автор: mr.DUDA 1.11.2005, 20:00 | ||||||
В принципе, так и делаю. Смущает то, что приходится выбирать между кол-вом точек (чем больше вычислений, тем медленнее) и точностью результата, т.к. при малом кол-ве точек в выборке может получиться фигура, мало совпадающая с линией пересечения. Сейчас я проверяю точки с края конуса с шагом 2 градуса (та самая окружность, про которую в начале было сказано), и этого более-менее хватает.
Нужно получить линию, по которой конус пересекается с кубом. Разве бока у конуса являются плоскостью ? Очень всё-таки хочется докопаться до истины. Добавлено @ 20:04
Понял !  Получается как бы два конуса - один с углом 180 градусов (линия пересечения с кубом будет равна линии, по которой куб пересекается с плоскостью, нормаль которой = направляющей конуса), и другой конус - с углом меньше 180 градусов. Находим линию пересечения второго конуса с кубом, и инвертируем полученную область на кубе. Здорово ! Вот бы ещё научиться находить сабж... |
| Автор: DENNN 2.11.2005, 11:42 |
| Вот, типа мои скромные художества . Если получилось непонятно - спрашивайте. На первом рисунке сам конус, проходящий через грань куба. Я не стал усложнять рисуя нормали, линии пересечения и пр. На втором собственно сама суть: две плоскости. X-плоскость грани куба. Н- плоскость, образованная радиусом в точке пересечения оси конуса с кубом. r- радиус-вектор, численно равный радиусу конуса в данной плоскости. |
| Автор: DENNN 3.11.2005, 09:17 |
| Попробую сегодня закончить, а то вчера времени опять не хватило Итак. Косинус угола между векторами R1 и R2, если мне не изменяет мой склероз, будет cos = (x1*x2 + y1*y2) / sqrt ((x1*x1 + y1*y1) * (x2*x2 + y2*y2)) Т.е. если косинус задан направлением С, и требуется найти угол, между гранью куба Q и плоскостью сечения, перпендикулярного оси цилиндра и проходящего через точку пересечения этой оси с гранью, то угол между нормалью грани QN и этой плоскостью будет cos = (QNx*Сx + QNy*Сy) / sqrt ((QNx*QNx + QNy*QNy) * (Сx*Сx + Сy*Сy)) А угол между гранью и плосокстью alfa=PI/2 - arccos( (QNx*Сx + QNy*Сy) / sqrt ((QNx*QNx + QNy*QNy) * (Сx*Сx + Сy*Сy)) ) Необходимо найти радиус окружности, образованной сечением конуса. Если известно, что угол между осью цилиндра и его поверхностью равен w, а расстояние от вершины конуса до точки пересечения равно CS, то радиус будет равен r= tan(w)*CS Таким образом, как видно из второго рисунка, необходимо для всех положений радиуса r найти координаты проекции его вершины на грань куба. Удобно ввести еще одну систему координат, с центром в точке пересечения оси цилиндра с гранью. Пусть ось X' направленна по радиусу окружности, когда он совпадает с плоскостью грани куба, ось Y' лежит в плосксоти грани куба. Учитывая, что стороны куба палаллельны осям координат, при переходе от новой системы координат к исходной Z всегда будет постоянна. Итак, в новой введенной системе координат для положения вектора r, образующего с нашей осью X' угол beta координат спроектрованной вершины на плоскость грани вычисляются следующим образом : x'=- (r*cos(beta)); y'=r*sin(beta)*cos(alfa); У меня на рисунке "нулевой" угол бета направлен в противопложную от оси X' сторону, т.е. для beta=0 вектор r направлен в противопложную относительно OX' сторону. Поэтому я поставил знак минус в первой формуле. Для перехода от нашей локальной Ск к заданной в задаче необходимо прибывить поправки в координаты получаемых точек. К примеру, если координаты точки пересечения оси с гранью равны (Ox,Oy,Oz), то координаты искомых точек будут равны x=x'+Ox=- (r*cos(beta))+Ox; y=y'+Oy=r*sin(beta)*cos(alfa)+Oy; z=Oz; Таким образом, чтоб найти все точки, образованные сечением грани куба цилиндром необходимо последовательно перебрать все значения beta и найти координаты точек проекции вершины вектора r. При этом необходиом выполнять проверку, что точка лежит на грани кубы, а не на ее продолжении. Может чего перепутал - поправляйте. Главное, чтоб ход мысли был понятен. |
| Автор: mr.DUDA 4.11.2005, 10:09 |
| спасибо |