| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Найти точку пересечения прямой и 3D повехности |
| Автор: _Y_ 28.4.2009, 16:51 |
| Имеется поверхность, заданная набором высот (взятых с определенным шагом по обоим осям); т.е. двухмерная матрица высот. Имеется аналитически заданная прямая: Y=a*X+b; Z=c*X+d. Надо найти точку, в которой вектор, сделанный из этой прямой, первый раз пересечет поверхность. В принципе, можно забыть о векторе и искать все пересечения прямой и поверхности - их не очень много. Не хочется изобретать велосипед – наверняка имеются отработанные подходы. Посоветуйте. Спасибо. |
| Автор: maxim1000 28.4.2009, 18:35 |
| только высот на дискретной сетке недостаточно для задания поверхности на всей области, нужно ещё какое-то правило интерполяции, т.е. как себя ведёт поверхность не в координатах сетки. И уже от него будет зависеть, как искать пересечение... |
| Автор: _Y_ 29.4.2009, 08:30 | ||
А это входит в мой вопрос в неявном виде  Как интерполировать? Меня устроит, видимо, даже самый простой вариант. Лишь бы точку пересечения найти. |
| Автор: ksnk 29.4.2009, 08:56 |
_Y_, абстрактная задача нуждается в абстрактном решении.  -- интерполировать, "для простоты", можно треугольниками. треугольники будут строится для каждой 4-ки точек, координаты x,y которых расположены в пределах "взятых с определенным шагом по обоим осям". стоим 4 треугольника, с 2-мя вершинами в соседних вершинах прямоугольника и третьей - центральной - стреднее арифметическое по всем 4-м точкам. -- для решения задачи пересечения с прямой можно "повернуть" оси координат так, чтобы ось Z смотрела в точности по этой прямой. Тогда из всех наших "повернутых" треугольников останется выбрать тот, в который "втыкается ось Z", то есть в координатах вершин треугольника есть и отрицательные и полохительные элементы по обоим парам x,y... |
| Автор: Ivanovich 29.4.2009, 09:49 |
| Поверхность представить треугольниками. Алгоритм пересечения луча с треугольником известен. Точки пересечения находить или перебором всех треугольников, что медленно. Или 1) разбиением пространства или 2) c помощью ограничивающих фигур, оба гораздо быстрее. |
| Автор: _Y_ 29.4.2009, 11:30 | ||||||||||
ksnk, Ivanovich, спасибо. Но хотелось бы чуть больше разъяснений. Ваши ответы очень близки, поэтому спрашиваю вперемешку:
А вот дальше у меня не пошло.
Спасибо! |
| Автор: ksnk 29.4.2009, 11:56 | ||
Мда... Чего-то я треугольники с чем-то квадратным попутал :-( Тогда этот прием можно использовать для грубого отсечения заведомо ненужных треугольников. Впрочем, для абстрактной задачи - не важно. Вообще-то задача "лежит ли точка внутри треугольника" - сводится к задаче "лежит ли точка с одной и той-же стороны, при обходе фигуры." В Гугле можно нарыть довольно много решений этой задачи... Векторная арифметика... |
| Автор: ksnk 29.4.2009, 12:16 | ||
Для каждой пары точек(x0,y0) и (x1,y1) треугольника и для центра (x=0,y=0)считаем
Если F для всех пар разного знака и не 0 - точка не внутри. |
| Автор: Ivanovich 29.4.2009, 12:28 |
| Определение точки пересечения луча с поверхностью ( в т.ч. составной из треугольников и др. примитивов) является одним из основных моментов задачи трассировки лучей (ray tracing). В источниках по этой теме всё подробно описано. |
| Автор: _Y_ 7.5.2009, 08:55 |
| Проблему решил. Вот отчитываюсь - может кому понадобится. 1. Поверхность описывается набором треугольников, как http://forum.vingrad.ru/index.php?showtopic=257336&view=findpost&p=1855681. 2. Каждый треугольник определяет бесконечную плоскость, описываемую уравнением aX+bY+cZ+d=0. 3. Прямая задана изначально уравнениями gX+hY+k=0 и pX+qZ+t=0. 4. Точка пересечения прямой и плоскости ищется совместным решением этих уравнений. 5. Проверка того, лежит ли точка пересечения в пределах треугольника производится сравнением площади треугольника с суммой площадей треугольников, образуемых этой точкой и каждой из сторон. Если наблюдается равенство - точка не снаружи. В этом шаге при сравнении надо учитывать машинную ошибку - к ней метод чувствителен. 6. Так находятся все треугольники, для у которых точка пересечения оказалась внутри, т.е. все пересечения прямой с поверхностью. 7. Если нужно найти только первое пересечение, для всех треугольников считается расстояние между точкой и началом исходной прямой. Выбирается тот треугольник, который ближе всего к этому началу. 8. Если есть какие-то начальные соображения по приблизительному нахождению точки пересечения прямой и поверхности, число перебираемых треугольников можно ограничить, снизив количество вычислений. |
| Автор: Sefko 11.5.2009, 18:24 |
| Не очень понятен в готовом решении момент фильтрации. То есть имеется ли предварительная оценка участков поверхности на предмет самой возможности пересечения. Если такого вообще нет и перебираются все участки, то это не есть хорошо, как мне кажется. Мне почему-то такая проверка представляется тривиальной. Луч может пересекаться только с теми участками, проекция которых на плоскость XY пересекается с проекцией луча на эту же плоскость. Ну вот, идем вдоль прокции луча и выбираем только те участки, которые... Как-то так. мне кажется. |
| Автор: _Y_ 13.5.2009, 08:53 | ||||||
Проверки на пересекается/не пересекается в рамках данного алгоритма нет, в моей задаче прямая пересекается с поверхностью априори. Так что я этим и не загружался. Оценка участка, в котором находится точка пересечения есть. Но она скорее эвристическая, чем алгоритмическая. Моя задача это позволяет. В результате сокращается количество перебираемых треугольников.
Именно проекции я и использовал, но только при оценке находится ли точка внутри треугльника. Однако это частный случай. Вместо этого можно разворачивать систему координат. ИМХО, проекция применима только если при проецировании точность теряется незначительно. В моем случае это это так. Угол между прямой и одной из осей не бывает близок к 90 градусам. Поэтому проецирование вдоль этой оси вполне "безопасно".
А вот это мне совершенно непонятно. Как можно осуществить "идем вдоль прокции луча"? |
| Автор: _Y_ 3.6.2009, 18:01 | ||
Спасибо. Это работает. Но столкнулся с таким вариантом. Высоты заданы для середин квадратов, на которые разбита поверхность. Соответственно, по краям у поверхности имеются "поля", в которых треугольники построить нужно, но вот "третья вершина" как среднеарифметическое рассчитана быть не может, т.к. четырьмя точками не окружена. Еще сложнее - с четырмя углами на такой поверхности. Есть ли какие-то разумные подходы к таким "полям" и углам? А то что-то у меня сплошные навороты получаются  .................... Кстати, проход вдоль луча для поиска первого пересечения с поверхностью мне удалось описать. ИМХО эффективно. Если кого-то интересует - скажите - распишу алгоритм. |