Или тему перекиньте плиз в более подходящий раздел, раз тут 0..
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Видимая область в пространстве |
| Автор: DragonFire 25.1.2007, 19:22 |
| Задача вот в чем: У нас есть трехмерное пространство, в котором находится множество треугольников. Где-то в нем установлена камера, вектор направления которой известен. Так же известна предельная видимость камеры. Вопрос: Как узнать какие треугольники попали в видимую облать камеры, а какие нет? Разумеется, требуется алгоритм, с наименьшей затратой ресурсов. Но главное понятный) Вообщем вопрос давно решенный многими умными людьми, хотелось бы получить описание приемлемого алгоритма или ссылку на таковое) |
| Автор: DragonFire 26.1.2007, 15:26 |
| Типо на форуме программистов никто об этих алгоритмах незнает? Или тему перекиньте плиз в более подходящий раздел, раз тут 0.. |
| Автор: maxim1000 26.1.2007, 16:52 |
| мне кажется, здесь могут подойти методы обнаружения столкновений объектов по сути, и там, и там выделяются объекты, расстояние до которых меньше какого-то порога Добавлено @ 16:56 вот в этой теме обсуждали: http://forum.vingrad.ru/topic-128962.html |
| Автор: Bikutoru 26.1.2007, 17:50 |
| Как мне подсказывают мои очень скромные познания в области компьютерной графики, здесь нужны алгоритмы отсечения: http://algolist.manual.ru/graphics/clip_seg.php - отсечение отрезков http://algolist.manual.ru/graphics/clip_poly.php - отсечение многоугольников |
| Автор: En_t_end 26.1.2007, 17:58 |
| DragonFire, У NeHe в уроках(урок №10) рассмотренна эта проблема. |
| Автор: DragonFire 27.1.2007, 12:59 | ||
| Bikutoru, Смотрел уже... можно конечно на этой основе придумать свой алгоритм, но не думаю что он будет быстр и надежен... maxim1000, Сылка рульная на деревья, но теперь бы по русски норм описание достать... En_t_end, я там не нашел))
Там берется массив треугольником и весь отрисовывается, предварительно перемещается СК, а не камера... |
| Автор: maxim1000 27.1.2007, 15:01 |
| ну с деревьями я сам особо не разбирался (да и ссылку кинул не я) но можно упростить всё (в качестве первого шага по построению алгоритма): 1. разделяем всё пространство на слои (например, делим на отрезки ось x), каждому слою сопоставляем массив 2. когда нужно найти множество близких элементов, просто смотрим, в каких слоях они могут лежать (влево и вправо на расстояние радиуса), из них и перебираем это уже даст некоторое увеличение скорости ну а дальше уже можно и внутри каждого слоя делить, но это, ИМХО, желательно делать, когда первый шаг сделан, понят и отлажен... |
| Автор: DENNN 27.1.2007, 15:55 |
| Область "видимости камеры" - четырехгранная пирамида. Решаем геометрическую задачу по поиску пересечения пирамиды и наших треугольников в сцене. К тем, что оказались внутри пирамиды применяем алгоритм, аналогичный Z-Buffer чтоб исключить треугольники, закрываемые более близкими к камере. |
| Автор: cardinal 27.1.2007, 18:02 | ||
а если два треугольника закрывают друг друга не полностью, а ты смотришь перекрываются ли их центры или нет? |
| Автор: DragonFire 27.1.2007, 19:58 | ||
DENNN, В точку. А теперь этот самый алгоритм - решение геометрической задачи, с максимальными отсечениями, дающий высокую скорость я и пытаюсь тут у вас выспросить maxim1000, На словах вроде все понятно... просто неохото "изобретать велосипед, когда все уже изобрели до вас". |
| Автор: DENNN 27.1.2007, 21:15 | ||||
Я смотрю не "центры", я использую Z-Buffer, в этом случае есть лишь пиксельная погрешность по линии пересечения двух граней
Задача пересечения плоскости и прямой. После нахождения координат точки пересечения проверяешь, лежит ли она между двумя вершинами отрезка или находится на продолжении. Повторяешь для остальных двух линий, образующих треугольную грань. Если точка есть только для одной линии - треугольник касается плоскости, если две и более (и они не совпадают с вершиной) - грань отсекается. Последнее действие, когда пересечений нет - проверить по какую сторону грани находится треугольник. Для этого достаточно взять любую вершину и сравнить с нормалью к грани. Если поскрипеть мозгами, то реализацию можно оптимизировать в пользу скорости. Например, если есть граничные условия, перейти от вещественных чисел, к числам с фиксированной запятой, хранящимся как целые. P.S. проблемы точности вычислений никто не отменял  |
| Автор: cardinal 27.1.2007, 23:23 | ||
Понял. |
| Автор: DragonFire 28.1.2007, 00:47 |
| DENNN, Может нубский вопрос, но плоскость, это плоскость грани видимой области, а прямая это сторона треугольника? И как построить плоскость грани камеры? Но это моя я сам выведу, а вот как оптимизировать? Все чтоли треугольники тупо перебирать? |
| Автор: DENNN 28.1.2007, 14:14 | ||||||
Да. Фактически треугольную грань можно описать либо координатами ее вершин, либо коэффициентами ур-ия прямых, ее образующих. Что лучше - это всегда диллема. В ряде алгоритмов удобнее хранить такие грани в виде прямых, в ряде удобнее как координаты вершин (матричные преобразования уже давно отлажены ).
А что ее строить? У тебя же есть такая информация, как видимый угол обзора камеры (ну или фокусное растояние, или аппертура - одна суть)? Вектор камеры тебе известен, значит и сможешь найти и все четыре(а вернее пять) грани, образующих конус видимости.
Надо подумать. У меня в выходной день голова совсем не варит  |
| Автор: DragonFire 28.1.2007, 21:41 | ||
Ну и последний нубский вопрос Как узнать угол обзора, я предполагаю что это будет что-то вроде tg(width/height) видимой области, или что-то вроде этого. Или не так?) |
| Автор: DENNN 29.1.2007, 11:26 | ||
Это будет откуда? Ты мне и расскажи. У тебя как камера задана? Фокусным расстоянием или граничными плоскостями, задающими область видимости?Если врыжать в углах, то, по уму, должно быть два угла: в горизонтальной и вертикальной плоскости, но иногда для упрощения их берут равными. |
| Автор: DragonFire 29.1.2007, 17:54 |
| DENNN, У меня камера задана положением в простанстве (вектор {x;y;z}), направлением (еденичный вектор {x;y;z}) и дальностью обзора (натуральное число). Также мне известна видимая область - предположим это весь экран, т.е. 1024*768. |
| Автор: DENNN 29.1.2007, 18:27 |
| В прикрепленном рисунке: точка O - точка экрана, через которую проходит ось камеры (иначе т.н. "главная точка"). O' - точка фокуса. Сотвественно отрезок OO' - фокусное расстояние камеры, равное f. O" - расположена на "дальней плоскости видимости". Отрезок OO", равный S дальности обзора камеры. В целом получаем т.н. пирамиду видимости. Сорри, но рисовать все в пространстве в глупом паинте мне в лом Габариты экрана в пространстве сцены ты знаешь, значит сможешь посчитать и все интересующие тебя стороны и углы (помня, что треуголники подобны, коэффициент подобия равен отношению f к (f+S) |
| Автор: DragonFire 29.1.2007, 21:20 |
| Ясно, буду мутить... |
