Errors are stored per midpoint coordinate instead of per Triangle

I noticed that the errors are stored for each coordinate in the grid instead of per triangle.

Line 60 in f0d6dca

this.errors = new Float32Array(terrain.length);

Lines 80 to 90 in f0d6dca

    
           // calculate error in the middle of the long edge of the triangle 
        
           const interpolatedHeight = (terrain[ay * size + ax] + terrain[by * size + bx]) / 2; 
        
           const middleIndex = my * size + mx; 
        
           const middleError = Math.abs(interpolatedHeight - terrain[middleIndex]); 
        
           errors[middleIndex] = Math.max(errors[middleIndex], middleError); 
        
           if (i < numParentTriangles) { // bigger triangles; accumulate error with children 
        
               const leftChildIndex = ((ay + cy) >> 1) * size + ((ax + cx) >> 1); 
        
               const rightChildIndex = ((by + cy) >> 1) * size + ((bx + cx) >> 1); 
        
               errors[middleIndex] = Math.max(errors[middleIndex], errors[leftChildIndex], errors[rightChildIndex]);

The paper suggests to calculate per triangle (Section 6: "... An initial preprocessing phase allocates to each triangle a measure of how accurately it approximates the surface - the triangles error"). I believe the reason is that storing per point creates an issue where triangle A and B may share a midpoint, but triangle A has a child with a greater error than any of triangle B's children.

If you are storing the maximum error of the children of triangle A at triangle A's midpoint, triangle B will also use that error value, even though they are in separate branches of the tree and do not share that maximum error child. Maybe this depends on the order of the iteration.

It may also be ok to store the midpoint errors on each point if they are true midpoint errors (not maximized based on the children), and then descend the tree to override with children in the getMesh call.

Apologies if I'm missing something, but I noticed because I'm trying to implement in rust and that caused a discrepancy when calculating error starting from a triangle and only checking its children vs starting from that same triangle's parent.

I believe the reason is that storing per point creates an issue where triangle A and B may share a midpoint, but triangle A has a child with a greater error than any of triangle B's children.

If the error is big enough to "split" triangle A into two triangles, then triangle B has to be split as well, otherwise there will be a discontinuity in the mesh with a vertical "gap" between the two halves. The algorithm is specifically designed to produce a conformal mesh — without gaps and t-junctions.

It may also be ok to store the midpoint errors on each point if they are true midpoint errors (not maximized based on the children), and then descend the tree to override with children in the getMesh call.

Aside from the gaps issue, this also defeats the purpose of the algorithm because you won't know when to "stop" descending and won't be able to get the mesh fast in linear time, without complex backtracking.

Totally make sense, thank you for getting back to me!

	// calculate error in the middle of the long edge of the triangle
	const interpolatedHeight = (terrain[ay * size + ax] + terrain[by * size + bx]) / 2;
	const middleIndex = my * size + mx;
	const middleError = Math.abs(interpolatedHeight - terrain[middleIndex]);

	errors[middleIndex] = Math.max(errors[middleIndex], middleError);

	if (i < numParentTriangles) { // bigger triangles; accumulate error with children
	const leftChildIndex = ((ay + cy) >> 1) * size + ((ax + cx) >> 1);
	const rightChildIndex = ((by + cy) >> 1) * size + ((bx + cx) >> 1);
	errors[middleIndex] = Math.max(errors[middleIndex], errors[leftChildIndex], errors[rightChildIndex]);