вступление

Привет!

Несколько недель назад я сделал небольшую демонстрацию для JS-вызова. В этой демонстрации ландшафт отображался на основе процедурно сгенерированной карты высот. Чтобы отобразить его в виде 3D-поверхности, я оценивал интерполированную высоту случайных точек (рендеринг Монте-Карло), а затем проецировал их.

В то время я уже знал о некоторых сбоях в моем методе, но я ждал, когда вызов закончится, чтобы обратиться за помощью. Я рассчитываю на вас. :)

Проблема

Итак, основную ошибку, которую я получаю, можно увидеть на следующем снимке экрана:

http://code.aldream.net/img/interpolation-error.jpg

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

Текущий метод

Поверхностная интерполяция

Чтобы оценить высоту каждой точки поверхности, я использую триангуляцию + линейную интерполяцию с барицентрическими координатами, то есть:

1. Я нахожу, в каком квадрате ABCD находится моя точка (x, y), причем A = (X,Y), B = (X+1, Y) , C = (X, Y+1) и D = (X+1, Y+1), X и Y являются усеченным значением < эм>х, у. (каждая точка сопоставляется с моей картой высот)
2. Я оцениваю, в каком треугольнике — ABD или ACD — находится моя точка, используя условие: isInABD = dx > dy с dx, dy десятичным числом часть x, y.
3. I evaluate the height of my point using linear interpolation:
   • if in ABD, height = h(B) + [h(A) - h(B)] * (1-dx) + [h(D) - h(B)] * dy
   • если в ACD высота = h(C) + [h(A) - h(C)] * (1-dy) + [h(D) - h(C)] * dx, где h(X) высота от карта.

Отображение

Чтобы отобразить точку, я просто конвертирую (x, y, height) в мировые координаты, проецирую вершину (используя простую перспективную проекцию с углами рыскания и тангажа). Я использую zBuffer, который я постоянно обновляю, чтобы проверить, рисую ли я полученный пиксель или нет.

Попытки

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

Я использую проекцию в других демонстрациях, поэтому не думаю, что проблема здесь. Что касается zBuffering, я не понимаю, как это может быть связано...

Мне не повезло здесь ... Любые подсказки приветствуются!

Спасибо за внимание, и хорошего дня!

Приложение

JsFiddle — Демо

Вот jsFiddle http://jsfiddle.net/PWqDL/ всей слегка упрощенной демонстрации, для тех, кто хочет подкрутить...

JsFiddle — небольшой тест для интерполяции

Когда я записывал этот вопрос, мне пришла в голову мысль получше взглянуть на результаты моей интерполяции. Я реализовал простой тест, в котором использовал матрицу 2x2, содержащую некоторые значения оттенков, и интерполировал промежуточные цвета перед их отображением на холсте.

Вот jsFiddle: http://jsfiddle.net/y2K7n/

Увы, результаты, кажется, соответствуют ожидаемому поведению для "треугольной" интерполяции, которую я делаю, поэтому у меня определенно заканчиваются идеи.

Пример кода

А вот упрощенная, наиболее вероятно ошибочная часть моего JS-кода, описывающая мой метод рендеринга (но я думаю, что язык здесь не имеет большого значения), учитывая квадратную карту высот "displayHeightMap" размером < em>(dim x dim) для ландшафта размером (SIZE x SIZE):

    for (k = 0; k < nbMonteCarloPointsByFrame; k++) {
        // Random float indices:
        var i = Math.random() * (dim-1),
            j = Math.random() * (dim-1),
        // Integer part (troncated):
            iTronc = i|0,
            jTronc = j|0,
            indTronc = iTronc*dim + jTronc,
        // Decimal part:
            iDec = i%1,
            jDec = j%1,
        // Now we want to intrapolate the value of the float point from the surrounding points of our map. So we want to find in which triangle is our point to evaluate the weighted average of the 3 corresponding points.
        // We already know that our point is in the square defined by the map points (iTronc, jTronc), (iTronc+1, jTronc), (iTronc, jTronc+1), (iTronc+1, jTronc+1).
        // If we split this square into two rectangle using the diagonale [(iTronc, jTronc), (iTronc+1, jTronc+1)], we can deduce in which triangle is our point with the following condition:
            whichTriangle = iDec < jDec, // ie "are we above or under the line j = jTronc + distanceBetweenLandscapePoints - (i-iTronc)"
            indThirdPointOfTriangle = indTronc +dim*whichTriangle +1-whichTriangle, // Top-right point of the square or bottm left, depending on which triangle we are in.
        // Intrapolating the point's height:
            deltaHeight1 = (displayHeightMap[indTronc] - displayHeightMap[indThirdPointOfTriangle]),
            deltaHeight2 = (displayHeightMap[indTronc+dim+1] - displayHeightMap[indThirdPointOfTriangle]),
            height = displayHeightMap[indThirdPointOfTriangle] + deltaHeight1 * (1-(whichTriangle? jDec:iDec)) + deltaHeight2 * (!whichTriangle? jDec:iDec),

            posX = i*distanceBetweenLandscapePoints - SIZE/2,
            posY = j*distanceBetweenLandscapePoints - SIZE/2,
            posZ = height - WATER_LVL;

        // 3D Projection:
        var temp1 = cosYaw*(posY - camPosY) - sinYaw*(posX - camPosX),
            temp2 = posZ - camPosZ,
            dX = (sinYaw*(posY - camPosY) + cosYaw*(posX - camPosX)),
            dY = sinPitch*temp2 + cosPitch*temp1,
            dZ = cosPitch*temp2 - sinPitch*temp1,
            pixelY = dY / dZ * minDim + canvasHeight,
            pixelX = dX / dZ * minDim + canvasWidth,
            canvasInd = pixelY * canvasWidth*2 + pixelX;

        if (!zBuffer[canvasInd] || (dZ < zBuffer[canvasInd])) { // We check if what we want to draw will be visible or behind another element. If it will be visible (for now), we draw it and update the zBuffer:
            zBuffer[canvasInd] = dZ;

            // Color:
            a.fillStyle = a.strokeStyle = EvaluateColor(displayHeightMap, indTronc); // Personal tweaking.

            a.fillRect(pixelX, pixelY, 1, 1);
        }
    }