Aldream - 2 months ago 12

Javascript Question

Hey!

Some weeks ago, I did a small demo for a JS challenge. This demo was displaying a landscape based on a procedurally-generated

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. :)

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

As you can see in the center, some points seem like floating above the peninsula, forming like a

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

**I find in which square ABCD my point**, with*(x, y)*is*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)**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*.**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.

To display the point, I just convert

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

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

Thank for your attention, and have a nice day!

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

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/

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 "

`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.
}
```

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 version for those interested: http://jsfiddle.net/W997s/1/