Aldream Aldream - 20 days ago 7
Javascript Question

Glitches with Triangulation + Linear Interpolation + 3D projection

Intro






Hey!

Some weeks ago, I did a small demo for a JS challenge. This demo was displaying a landscape based on a procedurally-generated heightmap. To display it as a 3D surface, I was evaluating the interpolated height of random points (Monte-Carlo rendering) then projecting them.

At that time, I was already aware of some glitches in my method, but I was waiting for the challenge to be over to seek some help. I'm counting on you. :)

Problem






So the main error I get can be seen in the following screenshot:

Screenshot - Interpolation Error?

As you can see in the center, some points seem like floating above the peninsula, forming like a less-dense relief. It is especially obvious with the sea behind, because of the color difference, even though the problem seems global.

Current method






Surface interpolation



To evaluate the height of each point of the surface, I'm using triangulation + linear interpolation with barycentric coordinates, ie:


  1. I find in which square ABCD my point (x, y) is, with A = (X,Y), B = (X+1, Y), C = (X, Y+1) and D = (X+1, Y+1), X and Y being the truncated value of x, y. (each point is mapped to my heightmap)

  2. I estimate in which triangle - ABD or ACD - my point is, using the condition: isInABD = dx > dy with dx, dy the decimal part of 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

    • if in ACD, height = h(C) + [h(A) - h(C)] * (1-dy) + [h(D) - h(C)] * dx, with h(X) height from the map.




Displaying



To display the point, I just convert (x, y, height) into the world coordinates, project the vertex (using simple perspective projection with yaw and pitch angles). I use a zBuffer I keep updated to check if I draw or not the obtained pixel.

Attempts






My impression is that for some points, I get a wrong interpolated height. I thus tried to search for some errors or some non-covered boundaries cases, in my implementation of the triangulation + linear interpolation. But if there are, I can't spot them.

I use the projection in other demos, so I don't think the problem comes from here. As for the zBuffering, I can't see how it could be related...

I'm running out of luck here... Any hints are most welcome!

Thank for your attention, and have a nice day!







Annexe






JsFiddle - Demo



Here is a jsFiddle http://jsfiddle.net/PWqDL/ of the whole slightly simplified demo, for those who want to tweak around...

JsFiddle - Small test for the interpolation



As I was writing down this question, I got an idea to have a better look at the results of my interpolation. I implemented a simple test in which I use a 2x2 matrix containing some hue values, and I interpolate the intermediate colors before displaying them in the canvas.

Here is the jsFiddle: http://jsfiddle.net/y2K7n/

Alas, the results seem to match the expected behavior for the kind of "triangular" interpolation I'm doing, so I'm definitly running out of ideas.

Code sample



And here is the simplified most-probably-faulty part of my JS code describing my rendering method (but the language doesn't matter much here I think), given a square heightmap "displayHeightMap" of size (dim x dim) for a landscape of size (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);
}
}

Answer

Got it. And it was as stupid a mistake as expected: I was reinitializing my zBuffer each frame...

Usually it's what you should do, but in my case, each frame (ie call of my Painting() function) adds details to the same frame (ie drawed static scene from a constant given point of view).

If I reset my zBuffer at each call of Painting(), I lose the depth information of the points drawn during the previous calls. The corresponding pixels are thus considered as blank, and will be re-painted for any projected points, without any regard for their depth.

Note: Without reinitiliazation, the zBuffer gets quite big. Another fix I should have done earlier was thus to convert the pixel's positions of the projected point (and thus the indices of the zBuffer) into integer values:

pixelY = dY / dZ * minDim + canvasHeight +.5|0,
pixelX = dX / dZ * minDim + canvasWidth +.5|0,
canvasInd = pixelY * canvasWidth*2 + pixelX;
if (dZ > 0 && (!zBuffer[canvasInd]  || (dZ < zBuffer[canvasInd]))) {
    // We draw the point and update the zBuffer.
}

Fun fact

If the glitches appeared more obvious for relief with the sea behind, it wasn't only for the color difference, but because the hilly parts of the landscape need much more points to be rendered than flat areas (like the sea), given their stretched surface.

My simplistic Monte-Carlo sampling of points doesn't take this characteristic into account, which means that at each call of Painting(), the sea gains statistically more density than the lands.

Because of the reinitialization of the zBuffer each frame, the sea was thus "winning the fight" in the picture's areas where mountains should have covered it (explaining the "ghostly mountains" effect there).

Corrected JsFiddle

Corrected version for those interested: http://jsfiddle.net/W997s/1/

Comments