   Terrain geometry patching with fractal generator
  Hi, I am working on my 3d editor again. I have a nxm controlpoint matrix for a terrain patch.I use fractals(midpoint displacement) to subdivide the terrain patch. Now since I don t have one global terrain patch I wonder how would you achive proper patching of neighbouring terrain patches in order to avoid gaps between the bordering triangles.One thing I thought of, which would be the easiest way, is to subdivide the whole mesh, but keep the border vertices fixed.What do you think about this?Another solution would be to average the border vertices of neighbouring patches. This however can lead to some odd shaps like strong elevations that shouldn t be there at all.Any suggestions?thx in advance   
  You could do the midpoint displacement in one dimension rather than two along the borders, and it should generate identical borders for neighboring patches as long as their shared corners are the same. All you would need to modify in the code is to have the border vertices use only their two neighbors that are also on the border and not include the third inside neighbor.   ;  Ok this is an excerpt from an articleQuote: The diamond step: Taking a square of four points, generate a random value at the square midpoint, where the two diagonals meet. The midpoint value is calculated by averaging the four corner values, plus a random amount. This gives you diamonds when you have multiple squares arranged in a grid. The square step: Taking each diamond of four points, generate a random value at the center of the diamond. Calculate the midpoint value by averaging the corner values, plus a random amount generated in the same range as used for the diamond step. This gives you squares again.I have a patch with NxN squares 1. The diamond step: I have a quad and calculate the midpoint2. The midpoint generation results in several diamond which again can be used to calculate a midpoint, so in the end i get squares againHm thinking about this, the border edges should never be split at all, since there are no diamonds.thx you, I think the algorithm should work pretty well with geometry patching   ;Quote:Original post by BasirorHm thinking about this, the border edges should never be split at all, since there are no diamonds.thx you, I think the algorithm should work pretty well with geometry patchingWhile you don't have a full diamond on the edges, you do have half of one. Every implementation I've seen splits the edges. If you are on the left edge, you use the vertices that are above, to the right of, and below the vertex that you are creating. For example:*0   **where "0" is the new vertex and asterisks are vertices used in its calculation. (I had to get rid of slashes for it to display properly.)Now to avoid gaps in neighboring patches, we just leave out the the inside vertex in the calculation of new vertices in the square step. So, you are essentially doing one-dimensional midpoint displacement on the edges. I haven't looked at the results of doing this, but it should definitely be better than not splitting the edges at all.Edit: Now that I think about it, you can't go past the first diamond step without splitting the edges... The following square step will always place one new vertex on each edge.[Edited by - Hexus on May 30, 2006 2:03:10 PM];  I could apply the random() seed on the non edge vertices only   ;  For determinism, you could use the heights of the original geometry for an edge as the random seed, so that if you are doing cell-based loading/unloading, both cells will generate the same random height along that edge.   ;  Hm I think there s an even better solution, I could take the x,y coordinates as a base for the random see, so touching edges will ever generate the same seed. I just get rid of the random part of the perlin noise .   ;Quote:Original post by BasirorHm I think there s an even better solution, I could take the x,y coordinates as a base for the random see, so touching edges will ever generate the same seed. I just get rid of the random part of the perlin noise .You should just be using a basic 2d noise function for performing all displacements in the diamond-square method. All random values are then seeded by their x and y coordinates and some global seed value. Here is an example function that creates noise values from -1.0 to 1.0:double noise(int x, int y, int seed){int n = (x + 31337 * y + 1013 * seed) & 0x7fffffff;n = (n >> 13) ^ n;return 1.0 - ((double)((n * (n * n * 60493 + 19990303) + 1376312589) & 0x7fffffff) / 1073741824.0);}So you are right that the same random value will be generated at the same locations, but these are just displacement values, so you need to be displacing from the same height. That is why you only do one-dimensional midpoint displacement on the edges.   ;  yes thats the perlin noise function I am using.Yes I may not do midpoint displacement and use the midpoint on the edges since the midpoint height is different for each terrain quad.thx   ;  Watch it, SoE has a patent on this type of stuff.