Имеется поверхность, заданная набором высот (взятых с определенным шагом по обоим осям); т.е. двухмерная матрица высот. Имеется аналитически заданная прямая: Y=a*X+b; Z=c*X+d. 

Надо найти точку, в которой вектор, сделанный из этой прямой, первый раз пересечет поверхность. В принципе, можно забыть о векторе и искать все пересечения прямой и поверхности - их не очень много.

Не хочется изобретать велосипед – наверняка имеются отработанные подходы. Посоветуйте.
Спасибо.

только высот на дискретной сетке недостаточно для задания поверхности на всей области, нужно ещё какое-то правило интерполяции, т.е. как себя ведёт поверхность не в координатах сетки. И уже от него будет зависеть, как искать пересечение...

А это входит в мой вопрос в неявном виде  Как интерполировать? Меня устроит, видимо, даже самый простой вариант. Лишь бы точку пересечения найти.

_Y_, абстрактная задача нуждается в абстрактном решении.   
-- интерполировать, "для простоты", можно треугольниками. треугольники будут строится для каждой 4-ки точек, координаты x,y которых расположены в пределах "взятых с определенным шагом по обоим осям". стоим 4 треугольника, с 2-мя вершинами в соседних вершинах прямоугольника и третьей - центральной - стреднее арифметическое по всем 4-м точкам.
-- для решения задачи пересечения с прямой можно "повернуть" оси координат так, чтобы ось Z смотрела в точности  по этой прямой. Тогда из всех наших "повернутых" треугольников останется выбрать тот, в который "втыкается ось Z", то есть в координатах вершин треугольника есть и отрицательные и полохительные элементы по обоим парам x,y...

Поверхность представить треугольниками. 
Алгоритм пересечения луча с треугольником известен.
Точки пересечения находить или перебором всех треугольников, что медленно.
Или 1) разбиением пространства или 2) c помощью ограничивающих фигур, оба гораздо быстрее.

ksnk, Ivanovich, спасибо. Но хотелось бы чуть больше разъяснений. Ваши ответы очень близки, поэтому спрашиваю вперемешку:

 Именно решения в общем виде и хочется   

 За ночь я именно до этого и додумался. Спасибо – вы подтвердили мой диагноз   А вот дальше у меня не пошло.

 Проблема в том, что он известен не мне.

 Что-то я здесь не понимаю. Вот пример после поворота координат (Z – нормаль в точке 0, 0). Вашему условию отвечают оба треугольника, а ось Z "втыкается" только в красный. 


 Про алгоритмы разбиения пространства и ограничивающих фигур я, честно говоря, ничего не знаю. Сам думал делать в два шага – сначала приблизительно оценивать область на основе здравого смысла, а потом делать перебор треугольников в этой области. Думаю, в этом случае просчитывать придется сотню-другую треугольников, не больше.

Спасибо!

Мда... Чего-то я треугольники с чем-то квадратным попутал :-( Тогда этот прием можно использовать для грубого отсечения заведомо ненужных треугольников. Впрочем, для абстрактной задачи - не важно.

Вообще-то задача "лежит ли точка внутри треугольника" - сводится к задаче "лежит ли точка с одной и той-же стороны, при обходе фигуры." В Гугле можно нарыть довольно много решений этой задачи... Векторная арифметика...

Для каждой пары точек(x0,y0) и (x1,y1) треугольника и для центра (x=0,y=0)считаем

Если F для всех пар разного знака и не 0 - точка не внутри.

Определение точки пересечения луча с поверхностью ( в т.ч. составной из треугольников и др. примитивов) является одним из основных моментов задачи трассировки лучей (ray tracing).
В источниках по этой теме всё подробно описано.

Проблему решил. Вот отчитываюсь - может кому понадобится.

1. Поверхность описывается набором треугольников, как посоветовал ksnk.
2. Каждый треугольник определяет бесконечную плоскость, описываемую уравнением aX+bY+cZ+d=0.
3. Прямая задана изначально уравнениями gX+hY+k=0 и pX+qZ+t=0.
4. Точка пересечения прямой и плоскости ищется совместным решением этих уравнений.
5. Проверка того, лежит ли точка пересечения в пределах треугольника производится сравнением площади треугольника с суммой площадей треугольников, образуемых этой точкой и каждой из сторон. Если наблюдается равенство - точка не снаружи. В этом шаге при сравнении надо учитывать машинную ошибку - к ней метод чувствителен.
6. Так находятся все треугольники, для у которых точка пересечения оказалась внутри, т.е. все пересечения прямой с поверхностью.
7. Если нужно найти только первое пересечение, для всех треугольников считается расстояние между точкой и началом исходной прямой. Выбирается тот треугольник, который ближе всего к этому началу.
8.  Если есть какие-то начальные соображения по приблизительному нахождению точки пересечения прямой и поверхности, число перебираемых треугольников можно ограничить, снизив количество  вычислений.


Это сообщение отредактировал(а) _Y_ - 7.5.2009, 08:56

Не очень понятен в готовом решении момент фильтрации. То есть имеется ли предварительная оценка участков поверхности на предмет самой возможности пересечения. Если такого вообще нет и перебираются все участки, то это не есть хорошо, как мне кажется.

Мне почему-то такая проверка представляется тривиальной.
Луч может пересекаться только с теми участками, проекция которых на плоскость XY пересекается с проекцией луча на эту же плоскость. Ну вот, идем вдоль прокции луча и выбираем только те участки, которые... Как-то так. мне кажется.


Это сообщение отредактировал(а) Sefko - 11.5.2009, 18:25

Проверки на пересекается/не пересекается в рамках данного алгоритма нет, в моей задаче прямая пересекается с поверхностью априори. Так что я этим и не загружался.

Оценка участка, в котором находится точка пересечения есть. Но она скорее эвристическая, чем алгоритмическая. Моя задача это позволяет. В результате сокращается количество перебираемых треугольников.


Именно проекции я и использовал, но только при оценке находится ли точка внутри треугльника. Однако это частный случай. Вместо этого можно разворачивать систему координат. ИМХО, проекция применима только если при проецировании точность теряется незначительно. В моем случае это это так. Угол между прямой и одной из осей не бывает близок к 90 градусам. Поэтому проецирование вдоль этой оси вполне "безопасно".


А вот это мне совершенно непонятно. Как можно осуществить "идем вдоль прокции луча"?

Спасибо. Это работает. Но столкнулся с таким вариантом. Высоты заданы для середин квадратов, на которые разбита поверхность. Соответственно, по краям у поверхности имеются "поля", в которых треугольники построить нужно, но вот "третья вершина" как среднеарифметическое рассчитана быть не может, т.к. четырьмя точками не окружена. Еще сложнее - с четырмя углами на такой поверхности. Есть ли какие-то разумные подходы к таким "полям" и углам? А то что-то у меня сплошные навороты получаются  
....................
Кстати, проход вдоль луча для поиска первого пересечения с поверхностью мне удалось описать. ИМХО эффективно. Если кого-то интересует - скажите - распишу алгоритм.