javascript - Glitches with Triangulation + Linear Interpolation + 3D projection -

intro

---

hey!

some weeks ago, did small demo js challenge. demo displaying landscape based on procedurally-generated heightmap. display 3d surface, evaluating interpolated height of random points (monte-carlo rendering) projecting them.

at time, aware of glitches in method, waiting challenge on seek help. i'm counting on you. :)

problem

---

so main error can seen in following screenshot:

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

as can see in center, points seem floating above peninsula, forming less-dense relief. obvious sea behind, because of color difference, though problem seems global.

current method

---

surface interpolation

to evaluate height of each point of surface, i'm using triangulation + linear interpolation barycentric coordinates, ie:

1. i find in square abcd point (x, y) is, a = (x,y), b = (x+1, y), c = (x, y+1) , d = (x+1, y+1), x , y being truncated value of x, y. (each point mapped heightmap)
2. i estimate in triangle - abd or acd - point is, using condition: isinabd = dx > dy dx, dy decimal part of x, y.
3. i evaluate height of 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, h(x) height map.

displaying

to display point, convert (x, y, height) world coordinates, project vertex (using simple perspective projection yaw , pitch angles). use zbuffer keep updated check if draw or not obtained pixel.

attempts

---

my impression points, wrong interpolated height. tried search errors or non-covered boundaries cases, in implementation of triangulation + linear interpolation. if there are, can't spot them.

i use projection in other demos, don't think problem comes here. zbuffering, can't see how related...

i'm running out of luck here... hints welcome!

thank attention, , have nice day!

---

---

annexe

---

jsfiddle - demo

here jsfiddle http://jsfiddle.net/pwqdl/ of whole simplified demo, want tweak around...

jsfiddle - small test interpolation

as writing down question, got idea have better @ results of interpolation. implemented simple test in use 2x2 matrix containing hue values, , interpolate intermediate colors before displaying them in canvas.

here jsfiddle: http://jsfiddle.net/y2k7n/

alas, results seem match expected behavior kind of "triangular" interpolation i'm doing, i'm definitly running out of ideas.

code sample

and here simplified most-probably-faulty part of js code describing rendering method (but language doesn't matter here think), given square heightmap "displayheightmap" of size (dim x dim) landscape of size (size x size):

    (k = 0; k < nbmontecarlopointsbyframe; k++) {         // random float indices:         var = 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,         // want intrapolate value of float point surrounding points of our map. want find in triangle our point evaluate weighted average of 3 corresponding points.         // know our point in square defined map points (itronc, jtronc), (itronc+1, jtronc), (itronc, jtronc+1), (itronc+1, jtronc+1).         // if split square 2 rectangle using diagonale [(itronc, jtronc), (itronc+1, jtronc+1)], can deduce in triangle our point following condition:             whichtriangle = idec < jdec, // ie "are above or under line j = jtronc + distancebetweenlandscapepoints - (i-itronc)"             indthirdpointoftriangle = indtronc +dim*whichtriangle +1-whichtriangle, // top-right point of square or bottm left, depending on triangle in.         // intrapolating 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])) { // check if want draw visible or behind element. if visible (for now), draw , update zbuffer:             zbuffer[canvasind] = dz;              // color:             a.fillstyle = a.strokestyle = evaluatecolor(displayheightmap, indtronc); // personal tweaking.              a.fillrect(pixelx, pixely, 1, 1);         }     } 

got it. , stupid mistake expected: i reinitializing zbuffer each frame...

usually it's should do, in case, each frame (ie call of painting() function) adds details same frame (ie drawed static scene constant given point of view).

if reset zbuffer @ each call of painting(), lose depth information of points drawn during previous calls. corresponding pixels considered blank, , re-painted projected points, without regard depth.

note: without reinitiliazation, zbuffer gets quite big. fix should have done earlier convert pixel's positions of projected point (and indices of zbuffer) 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]))) {     // draw point , update zbuffer. } 

---

fun fact

if glitches appeared more obvious relief sea behind, wasn't color difference, because hilly parts of landscape need more points rendered flat areas (like sea), given stretched surface.

my simplistic monte-carlo sampling of points doesn't take characteristic account, means @ each call of painting(), the sea gains statistically more density lands.

because of reinitialization of zbuffer each frame, sea "winning fight" in picture's areas mountains should have covered (explaining "ghostly mountains" effect there).

corrected jsfiddle

corrected version interested: http://jsfiddle.net/w997s/1/