Задача вот в чем: У нас есть трехмерное пространство, в котором находится множество треугольников. Где-то в нем установлена камера, вектор направления которой известен. Так же известна предельная видимость камеры.
Вопрос: Как узнать какие треугольники попали в видимую облать камеры, а какие нет? Разумеется, требуется алгоритм, с наименьшей затратой ресурсов. Но главное понятный)

Вообщем вопрос давно решенный многими умными людьми, хотелось бы получить описание приемлемого алгоритма или ссылку на таковое)

Типо на форуме программистов никто об этих алгоритмах незнает? 
Или тему перекиньте плиз в более подходящий раздел, раз тут 0..

мне кажется, здесь могут подойти методы обнаружения столкновений объектов
по сути, и там, и там выделяются объекты, расстояние до которых меньше какого-то порога

Добавлено @ 16:56 
вот в этой теме обсуждали:
http://forum.vingrad.ru/topic-128962.html

Как мне подсказывают мои очень скромные познания в области компьютерной графики, здесь нужны алгоритмы отсечения:
http://algolist.manual.ru/graphics/clip_seg.php - отсечение отрезков
http://algolist.manual.ru/graphics/clip_poly.php - отсечение многоугольников

DragonFire, У NeHe в уроках(урок №10) рассмотренна эта проблема.

Bikutoru, Смотрел уже... можно конечно на этой основе придумать свой алгоритм, но не думаю что он будет быстр и надежен...

maxim1000, Сылка рульная на деревья, но теперь бы по русски норм описание достать...

En_t_end, я там не нашел)) 

Там берется массив треугольником и весь отрисовывается, предварительно перемещается СК, а не камера...

ну с деревьями я сам особо не разбирался (да и ссылку кинул не я)
но можно упростить всё (в качестве первого шага по построению алгоритма):
1. разделяем всё пространство на слои (например, делим на отрезки ось x), каждому слою сопоставляем массив
2. когда нужно найти множество близких элементов, просто смотрим, в каких слоях они могут лежать (влево и вправо на расстояние радиуса), из них и перебираем
это уже даст некоторое увеличение скорости

ну а дальше уже можно и внутри каждого слоя делить, но это, ИМХО, желательно делать, когда первый шаг сделан, понят и отлажен...

Область "видимости камеры" - четырехгранная пирамида. Решаем геометрическую задачу по поиску пересечения пирамиды и наших треугольников в сцене. К тем, что оказались внутри пирамиды применяем алгоритм, аналогичный Z-Buffer чтоб исключить треугольники, закрываемые более близкими к камере.

а если два треугольника закрывают друг друга не полностью, а ты смотришь перекрываются ли их центры или нет?

DENNN, В точку. А теперь этот самый алгоритм - решение геометрической задачи, с максимальными отсечениями, дающий высокую скорость я и пытаюсь тут у вас выспросить 

maxim1000, На словах вроде все понятно... просто неохото "изобретать велосипед, когда  все уже изобрели до вас".

Я смотрю не "центры", я использую Z-Buffer, в этом случае есть лишь пиксельная погрешность по линии пересечения двух граней 



Задача пересечения плоскости и прямой. После нахождения координат точки пересечения проверяешь, лежит ли она между двумя вершинами отрезка или находится на продолжении. Повторяешь для остальных двух линий, образующих треугольную грань.  Если точка есть только для одной линии  - треугольник касается плоскости, если две и более (и они не совпадают с вершиной) - грань отсекается.  Последнее действие, когда пересечений нет - проверить по какую сторону грани находится треугольник. Для этого достаточно взять любую вершину и сравнить с нормалью к грани.

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

P.S. проблемы точности вычислений никто не отменял   

Понял.

DENNN, Может нубский вопрос, но плоскость, это плоскость грани видимой области, а прямая это сторона треугольника? И как построить плоскость грани камеры? Но это моя я сам выведу, а вот как оптимизировать? Все чтоли треугольники тупо перебирать?

Да. Фактически треугольную грань можно описать либо координатами ее вершин, либо коэффициентами ур-ия прямых, ее образующих. Что лучше - это всегда диллема. В ряде алгоритмов удобнее хранить такие грани в виде прямых, в ряде удобнее как координаты вершин (матричные преобразования уже давно отлажены    ).


А что ее строить? У тебя же есть такая информация, как видимый угол обзора камеры (ну или фокусное растояние, или аппертура - одна суть)? Вектор камеры тебе известен, значит и сможешь найти и все четыре(а вернее пять) грани, образующих конус видимости.

Надо подумать. У меня в выходной день голова совсем не варит   

Ну и последний нубский вопрос  
Как узнать угол обзора, я предполагаю что это будет что-то вроде tg(width/height) видимой области, или что-то вроде этого. Или не так?)