Предыдущая страница реферата | 1  2  3  4 | Следующая страница реферата

Рис. 5. Во время Update() для NE квадранта мы принимаем решение включить черную вершину. Так как эта вершина общая с SE квадрантов (помеченным серым), то мы должны включить этот квадрант тоже. Включение SE вкадранта в свою очередь заставит нас включить помеченные серым вершины.

После того как мы закончим с Update() мы можем вызвать Render(). Рендер очень прост - все вычисления по сохранению целостности меша уже были выполнены в Update(). Идея, на которой основан Render() - это рекурсивный вызов Render для включенных подквадратов и затем отрисовка всех треугольников квадрата, которые не были покрыты включенными подквадратами.

Рис 6. Пример меша. Включенные вершины помечены черным. Серые треугольники отрисованы во время рекурсивного вызова Render() для сопоставленных им подквадратов. Белые треугольники отрисоввываются во время изначального вызова Render() для этого квадрата.

Алгоритм: Обработка вершин и квадратов

Перейдем к самому вычислению - должна ли вершина быть включена. Для этого существует несколько методов. Все, которые я принял во внимание, называются "vertex interpolation error" (ошибка интерполяции вершины), или, короче, vertex error. Это разница между высотой вершины и высотой ребра в треугольнике, который апроксимирует вершину, когда та выключена (Рис. 7). Вершины с большей ошибкой должны быть предпочтительнее вершин с маленькой ошибкой. Другой вариант основан на растоянии вершины от точки зрения. Интуитивно, имея 2 вершины с одинаковой ошибкой мы должны выбрать более ближнюю. 

Рис. 7. Vertex interpolation error. Когда вершина включена или выключена, меш меняяет форму. Максимальное изменение, получающееся при включении вершины показано пунктирной линией. Величина изменения есть разница между реальной высотой вершины (черная точка) и высотой ребра под ним (белая точка). Белая точка - это просто середина между 2 серыми точками. (Wolverene: Середина - так как мы рассматриваем измельчающиеся квадраты в quadtree и точка деления лежит ровно посередине).

Также есть другие влияющие факторы. К примеру, в [1] принимается во внимание направление между вершиной и точкой зрения. Идея заключается в screen space error (экранной ошибке) - интуитивно vertex error менее видима чем более вертикально данное направление. В [1] описана вся эта математика в деталях.

Но я не думаю что screen space error является хорошей метрикой по двум причинам: во-первых, он игнорирует текстурную перспективу и depth buffering errors - даже если вершина не движется на экране, т.к. она сдвигается строго пенпердикулярно к/от точки зрения, Z значение влияет на коррекцию перспективы так же как и depth-buffering. Во-вторых, точка зрения прямо вниз является как легким случаем для LOD ландшафтов, так и не типичным случаем. 

На мой взгляд, нет смысла оптимизировать для нетипичного легкого случая. Случай, когда ось зрения более горизонтальна и большая часть ландшафта видима определяет наименьший framerate, и, следовательно, эффективность алгоритма.

Вместо screen-space geometric error я предлагаю делать подобный тест в трехмерном пространстве с ошибкой пропорциональной дистанции. Он включает только 3 величины: L1 норму вектора между вершиной и точкой зрения, vertex error и константный "порог детализации"(Threshold). 

Vertex test:

L1 = max(abs(vertx - viewx), abs(verty - viewy), abs(vertz - viewz)); 

enabled = error * Threshold < L1;

На практике использование L1 нормы означает большую глубину делений вдоль диагоналей горизонтальной плоскости ландшафта. Я не смог заметить данный эффект глазом, так что я не думаю что об этом стоит беспокоиться. [4] и другие используют view-space-z вместо L1 нормы, что теоретически является даже более правильным чем истинная дистанция между вершиной и точкой зрения. Несмотря на это, L1 по-моему работает наилучшим образом и в [3] она тоже используется.

Можно использовать Threshold как регулятор подстройки скорость/качество, но он не имеет четкой геометричесой интерпретации. Грубо говоря, он означает: для данного растояния z, худшей ошибкой с которой я буду мирится будет z / Threshold. Конечно, вы можете произвести некоторые вычисления угла зрения и связать Threshold с максимальной пиксельной ошибкой, но я никогда не рассматривал его более чем значение для подстройки отношения качество/скорость.

Вот так работает включение вершин. Но что является более важным, как работает включение подквадратов во время Update()? Ответом является box test. Он задает следующий вопрос: рассматриваем выровненный по осям 3D Box, содержащий участок ландшафта (т.е. элемент quadtree), и знаем соответвующую ему максимальную vertex error всех вершин внутри. Может ли vertex enable test вернуть истину для какой-либо вершины из этого квадрата? Если да, то делим.

Прелесть этого метода в том, что делая BoxTest мы можем одним махом отсечь тысячи вершин. Это делает Update() полностью масштабируемым: стоимость его не зависит от размера всего набора данных, а лишь от размера данных, включенных в текущий LOD меш. И, как побочное явление, предпросчитанный вертикальный размер Bounding Box может использоватся для frustim culling. (примечание wolverene - координаты x и z мы уже знаем из выбора квадрата как элемента quadtree, т.е. для построения BoundBox нам надо знать лишь вертикальный его размер).

Box Test консервативен в том смысле что вершина, из-за которой Box Test вернул "Да" (т.е. необходимость деления) может находится на другой стороне bound box от ближней к точке зрения стороны bound box, и, таким образом, сама вершина может этот тест провалить. Но на деле это не влечет больших накладных расходов - несколько box test и vertex test.

Box test имеет следующий вид, очень похожий на VertexTest:

Box test:

bc[x,y,z] == coordinates of box center

ex[x,y,z] == extent of box from the center (i.e. 1/2 the box dimensions)

L1 = max(abs(bcx - viewx) - exx, abs(bcy - viewy) - exy, abs(bcz - viewz) - exz)

enabled = maxerror * Threshold < L1

Рекомендуем скачать другие рефераты по теме: сочинение почему, доклад по информатике.





Предыдущая страница реферата | 1  2  3  4 | Следующая страница реферата