## Re: [Algorithms] midpoint displacement problems

 Re: [Algorithms] midpoint displacement problems From: David Zaadstra - 2002-02-28 13:05:09 ```That's just about what my thoughts were about the algorithm. I just don't have the knowledge to tell you that it's sigma shaped ;-) I'll try two things: 1) your solution. If that doesn't look okay I'll try it like 2) http://www.people.nnov.ru/fractal/VRML/Terra/terra.htm with the difference that my triangles are 90°, not equal-sided. I would divide the terrain into 4 parts then, something like this: \----- /| | \ / | | \ / | | / \ | | / \ | /------\ and recurse on each part. Tried it on paper. Gave me a linear interpolation. Thanks for your help. I'll post another screenshot when it looks ok and tell you how I did it. David ----- Original Message ----- From: "Tom Forsyth" To: "David Zaadstra" ; Sent: Thursday, February 28, 2002 12:43 PM Subject: RE: [Algorithms] midpoint displacement problems > I dug out Gems1 and had a look at the algorithm. I would expect that with no > random displacements and a starting grid, it would produce a series of > bilinear patches. But the algorithm is not the one I was expecting. > > Given a grid: > > A-B-C > | | | > D-E-F > | | | > G-H-I > > For which we start with values A, C, G and I. We calculate the midpoint E > the way I would expect: > > E = (A+C+G+I)/4 > > To do a bilinear filter, you would then fine the edge midpoints this way: > > D = (A+G)/2 > B = (A+C)/2 > F = (C+I)/2 > H = (G+I)/2 > > ...but this is not what the book does. It requires use of an adjacent > square: > > A-B-C---+ > | | | | | > D-E-F-X-| > | | | | | > G-H-I---+ > > ...and F = (C+I+E+X)/4 > > > This seems wrong to me. I can't really say why, except that it feels wrong. > One odd feature is that with more tesselation (with no random > displacements), the line C-I is not a straight line, it is some odd > sigma-shaped thing. Which means the 2D midpoint displacement result (a > straight line) does not appear anywhere in the 3D version. Which seems > wrong. > > > I am by no means an expert on these things (and I would use a weighted > bicubic interpolation scheme rather than a linear one anyway), but is the > algorithm given in the book realy the standard algorithm? > > > Whether it is or not, it's obviously not giving you the results you expect, > which is what really matters. Try calculating using > > D = (A+G)/2 > B = (A+C)/2 > F = (C+I)/2 > H = (G+I)/2 > > instead - it may be more to your liking. And of course the real trick is to > fiddle with the algorithm until it gives you results you like - there's no > "right" or "wrong" way to do things. > > > Tom Forsyth - purely hypothetical Muckyfoot bloke. > > This email is the product of your deranged imagination, > and does not in any way imply existence of the author. > > > -----Original Message----- > > From: David Zaadstra [mailto:mythomania@...] > > Sent: 27 February 2002 21:35 > > To: gdalgorithms-list@... > > Subject: Re: [Algorithms] midpoint displacement problems > > > > > > hmm...I think I just found out that the algorithm as it is > > described in GPG1 > > doesn't really work. I can't explain why, but I calculated a small 8*8 > > heightmap on paper, and I get wrong results. The points get > > interpolated > > like an exponential function from the middle of the square to > > its edges. > > When I read how it works with a line I thought that the > > algorithm is ok. And > > it is, but only in 2D, with the line. > > I think the problem with the 3D version is that the 4 points which get > > interpolated don't lie in a plane. Or is it because the > > distance of the > > points is sqrt(2) in the diamond step and 1 in the square step? > > Can anybody else comment on this? Somebody how knows the > > algorithm, and is > > better at maths and explaining than me maybe? > > > > > > ----- Original Message ----- > > From: "Tom Forsyth" > > To: "David Zaadstra" ; > > > > Sent: Wednesday, February 27, 2002 9:24 PM > > Subject: RE: [Algorithms] midpoint displacement problems > > > > > > > That looks like your midpoint calculation isn't working > > right - the peaks > > > are the "coarse" divisions, but then the rest of the > > subdivisions don't > > > interpolate through them properly. Try turning off any > > random variation > > > after, say, three divisons - you should then get a nice > > smooth surface. > > But > > > I don't think you will, because the calculation of the new > > midpoint isn't > > > working right. > > > > > > Tom Forsyth - purely hypothetical Muckyfoot bloke. > > > > > > This email is the product of your deranged imagination, > > > and does not in any way imply existence of the author. > > > > > > > -----Original Message----- > > > > From: David Zaadstra [mailto:mythomania@...] > > > > Sent: 27 February 2002 20:12 > > > > To: gdalgorithms-list@... > > > > Subject: [Algorithms] midpoint displacement problems > > > > > > > > > > > > Hello everybody, > > > > > > > > I have a problem with the midpoint displacement algorithm > > (from GPG1). > > > > I get strange little peaks all around my landscape. I've been > > > > looking for > > > > the bug for hours now and starting to believe that I'm a > > > > complete idiot. > > > > Could it be that the peaks are normal? That would explain why > > > > an erosion > > > > filter was added to the example file in GPG... > > > > Please take a look at this screenshot to see what I mean: > > > > http://www.gameprogramming.de/screen.jpg (not a very good one, i know) > > > > > > > > Thanks for your help, > > > > David > > > > > > > > > > > > _______________________________________________ > > > > GDAlgorithms-list mailing list > > > > GDAlgorithms-list@... > > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > > Archives: > > > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > > > > > > > _______________________________________________ > > > GDAlgorithms-list mailing list > > > GDAlgorithms-list@... > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > Archives: > > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > > > > > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDAlgorithms-list@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > ```

 RE: [Algorithms] midpoint displacement problems From: Tom Forsyth - 2002-02-27 20:26:05 ```That looks like your midpoint calculation isn't working right - the peaks are the "coarse" divisions, but then the rest of the subdivisions don't interpolate through them properly. Try turning off any random variation after, say, three divisons - you should then get a nice smooth surface. But I don't think you will, because the calculation of the new midpoint isn't working right. Tom Forsyth - purely hypothetical Muckyfoot bloke. This email is the product of your deranged imagination, and does not in any way imply existence of the author. > -----Original Message----- > From: David Zaadstra [mailto:mythomania@...] > Sent: 27 February 2002 20:12 > To: gdalgorithms-list@... > Subject: [Algorithms] midpoint displacement problems > > > Hello everybody, > > I have a problem with the midpoint displacement algorithm (from GPG1). > I get strange little peaks all around my landscape. I've been > looking for > the bug for hours now and starting to believe that I'm a > complete idiot. > Could it be that the peaks are normal? That would explain why > an erosion > filter was added to the example file in GPG... > Please take a look at this screenshot to see what I mean: > http://www.gameprogramming.de/screen.jpg (not a very good one, i know) > > Thanks for your help, > David > > > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > ```
 RE: [Algorithms] midpoint displacement problems From: James Johnson - 2002-02-27 22:40:13 ```My guess is you're calculating your indices [into your map] incorrectly for some edge case(s). It's pretty easy to get a one off error, that will generate these types of anomalies. Combine Tom's approach (remove the random part), and seeding the four corners with known values. You should be able to produce a gradient. James -----Original Message----- From: David Zaadstra [mailto:mythomania@...] Sent: Wednesday, February 27, 2002 1:35 PM To: gdalgorithms-list@... Subject: Re: [Algorithms] midpoint displacement problems hmm...I think I just found out that the algorithm as it is described in GPG1 doesn't really work. I can't explain why, but I calculated a small 8*8 heightmap on paper, and I get wrong results. The points get interpolated like an exponential function from the middle of the square to its edges. When I read how it works with a line I thought that the algorithm is ok. And it is, but only in 2D, with the line. I think the problem with the 3D version is that the 4 points which get interpolated don't lie in a plane. Or is it because the distance of the points is sqrt(2) in the diamond step and 1 in the square step? Can anybody else comment on this? Somebody how knows the algorithm, and is better at maths and explaining than me maybe? ```
 RE: [Algorithms] midpoint displacement problems From: Tom Forsyth - 2002-02-28 11:45:21 ```I dug out Gems1 and had a look at the algorithm. I would expect that with no random displacements and a starting grid, it would produce a series of bilinear patches. But the algorithm is not the one I was expecting. Given a grid: A-B-C | | | D-E-F | | | G-H-I For which we start with values A, C, G and I. We calculate the midpoint E the way I would expect: E = (A+C+G+I)/4 To do a bilinear filter, you would then fine the edge midpoints this way: D = (A+G)/2 B = (A+C)/2 F = (C+I)/2 H = (G+I)/2 ...but this is not what the book does. It requires use of an adjacent square: A-B-C---+ | | | | | D-E-F-X-| | | | | | G-H-I---+ ...and F = (C+I+E+X)/4 This seems wrong to me. I can't really say why, except that it feels wrong. One odd feature is that with more tesselation (with no random displacements), the line C-I is not a straight line, it is some odd sigma-shaped thing. Which means the 2D midpoint displacement result (a straight line) does not appear anywhere in the 3D version. Which seems wrong. I am by no means an expert on these things (and I would use a weighted bicubic interpolation scheme rather than a linear one anyway), but is the algorithm given in the book realy the standard algorithm? Whether it is or not, it's obviously not giving you the results you expect, which is what really matters. Try calculating using D = (A+G)/2 B = (A+C)/2 F = (C+I)/2 H = (G+I)/2 instead - it may be more to your liking. And of course the real trick is to fiddle with the algorithm until it gives you results you like - there's no "right" or "wrong" way to do things. Tom Forsyth - purely hypothetical Muckyfoot bloke. This email is the product of your deranged imagination, and does not in any way imply existence of the author. > -----Original Message----- > From: David Zaadstra [mailto:mythomania@...] > Sent: 27 February 2002 21:35 > To: gdalgorithms-list@... > Subject: Re: [Algorithms] midpoint displacement problems > > > hmm...I think I just found out that the algorithm as it is > described in GPG1 > doesn't really work. I can't explain why, but I calculated a small 8*8 > heightmap on paper, and I get wrong results. The points get > interpolated > like an exponential function from the middle of the square to > its edges. > When I read how it works with a line I thought that the > algorithm is ok. And > it is, but only in 2D, with the line. > I think the problem with the 3D version is that the 4 points which get > interpolated don't lie in a plane. Or is it because the > distance of the > points is sqrt(2) in the diamond step and 1 in the square step? > Can anybody else comment on this? Somebody how knows the > algorithm, and is > better at maths and explaining than me maybe? > > > ----- Original Message ----- > From: "Tom Forsyth" > To: "David Zaadstra" ; > > Sent: Wednesday, February 27, 2002 9:24 PM > Subject: RE: [Algorithms] midpoint displacement problems > > > > That looks like your midpoint calculation isn't working > right - the peaks > > are the "coarse" divisions, but then the rest of the > subdivisions don't > > interpolate through them properly. Try turning off any > random variation > > after, say, three divisons - you should then get a nice > smooth surface. > But > > I don't think you will, because the calculation of the new > midpoint isn't > > working right. > > > > Tom Forsyth - purely hypothetical Muckyfoot bloke. > > > > This email is the product of your deranged imagination, > > and does not in any way imply existence of the author. > > > > > -----Original Message----- > > > From: David Zaadstra [mailto:mythomania@...] > > > Sent: 27 February 2002 20:12 > > > To: gdalgorithms-list@... > > > Subject: [Algorithms] midpoint displacement problems > > > > > > > > > Hello everybody, > > > > > > I have a problem with the midpoint displacement algorithm > (from GPG1). > > > I get strange little peaks all around my landscape. I've been > > > looking for > > > the bug for hours now and starting to believe that I'm a > > > complete idiot. > > > Could it be that the peaks are normal? That would explain why > > > an erosion > > > filter was added to the example file in GPG... > > > Please take a look at this screenshot to see what I mean: > > > http://www.gameprogramming.de/screen.jpg (not a very good one, i know) > > > > > > Thanks for your help, > > > David > > > > > > > > > _______________________________________________ > > > GDAlgorithms-list mailing list > > > GDAlgorithms-list@... > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > Archives: > > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > > > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDAlgorithms-list@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > ```
 Re: [Algorithms] midpoint displacement problems From: David Zaadstra - 2002-02-28 13:05:09 ```That's just about what my thoughts were about the algorithm. I just don't have the knowledge to tell you that it's sigma shaped ;-) I'll try two things: 1) your solution. If that doesn't look okay I'll try it like 2) http://www.people.nnov.ru/fractal/VRML/Terra/terra.htm with the difference that my triangles are 90°, not equal-sided. I would divide the terrain into 4 parts then, something like this: \----- /| | \ / | | \ / | | / \ | | / \ | /------\ and recurse on each part. Tried it on paper. Gave me a linear interpolation. Thanks for your help. I'll post another screenshot when it looks ok and tell you how I did it. David ----- Original Message ----- From: "Tom Forsyth" To: "David Zaadstra" ; Sent: Thursday, February 28, 2002 12:43 PM Subject: RE: [Algorithms] midpoint displacement problems > I dug out Gems1 and had a look at the algorithm. I would expect that with no > random displacements and a starting grid, it would produce a series of > bilinear patches. But the algorithm is not the one I was expecting. > > Given a grid: > > A-B-C > | | | > D-E-F > | | | > G-H-I > > For which we start with values A, C, G and I. We calculate the midpoint E > the way I would expect: > > E = (A+C+G+I)/4 > > To do a bilinear filter, you would then fine the edge midpoints this way: > > D = (A+G)/2 > B = (A+C)/2 > F = (C+I)/2 > H = (G+I)/2 > > ...but this is not what the book does. It requires use of an adjacent > square: > > A-B-C---+ > | | | | | > D-E-F-X-| > | | | | | > G-H-I---+ > > ...and F = (C+I+E+X)/4 > > > This seems wrong to me. I can't really say why, except that it feels wrong. > One odd feature is that with more tesselation (with no random > displacements), the line C-I is not a straight line, it is some odd > sigma-shaped thing. Which means the 2D midpoint displacement result (a > straight line) does not appear anywhere in the 3D version. Which seems > wrong. > > > I am by no means an expert on these things (and I would use a weighted > bicubic interpolation scheme rather than a linear one anyway), but is the > algorithm given in the book realy the standard algorithm? > > > Whether it is or not, it's obviously not giving you the results you expect, > which is what really matters. Try calculating using > > D = (A+G)/2 > B = (A+C)/2 > F = (C+I)/2 > H = (G+I)/2 > > instead - it may be more to your liking. And of course the real trick is to > fiddle with the algorithm until it gives you results you like - there's no > "right" or "wrong" way to do things. > > > Tom Forsyth - purely hypothetical Muckyfoot bloke. > > This email is the product of your deranged imagination, > and does not in any way imply existence of the author. > > > -----Original Message----- > > From: David Zaadstra [mailto:mythomania@...] > > Sent: 27 February 2002 21:35 > > To: gdalgorithms-list@... > > Subject: Re: [Algorithms] midpoint displacement problems > > > > > > hmm...I think I just found out that the algorithm as it is > > described in GPG1 > > doesn't really work. I can't explain why, but I calculated a small 8*8 > > heightmap on paper, and I get wrong results. The points get > > interpolated > > like an exponential function from the middle of the square to > > its edges. > > When I read how it works with a line I thought that the > > algorithm is ok. And > > it is, but only in 2D, with the line. > > I think the problem with the 3D version is that the 4 points which get > > interpolated don't lie in a plane. Or is it because the > > distance of the > > points is sqrt(2) in the diamond step and 1 in the square step? > > Can anybody else comment on this? Somebody how knows the > > algorithm, and is > > better at maths and explaining than me maybe? > > > > > > ----- Original Message ----- > > From: "Tom Forsyth" > > To: "David Zaadstra" ; > > > > Sent: Wednesday, February 27, 2002 9:24 PM > > Subject: RE: [Algorithms] midpoint displacement problems > > > > > > > That looks like your midpoint calculation isn't working > > right - the peaks > > > are the "coarse" divisions, but then the rest of the > > subdivisions don't > > > interpolate through them properly. Try turning off any > > random variation > > > after, say, three divisons - you should then get a nice > > smooth surface. > > But > > > I don't think you will, because the calculation of the new > > midpoint isn't > > > working right. > > > > > > Tom Forsyth - purely hypothetical Muckyfoot bloke. > > > > > > This email is the product of your deranged imagination, > > > and does not in any way imply existence of the author. > > > > > > > -----Original Message----- > > > > From: David Zaadstra [mailto:mythomania@...] > > > > Sent: 27 February 2002 20:12 > > > > To: gdalgorithms-list@... > > > > Subject: [Algorithms] midpoint displacement problems > > > > > > > > > > > > Hello everybody, > > > > > > > > I have a problem with the midpoint displacement algorithm > > (from GPG1). > > > > I get strange little peaks all around my landscape. I've been > > > > looking for > > > > the bug for hours now and starting to believe that I'm a > > > > complete idiot. > > > > Could it be that the peaks are normal? That would explain why > > > > an erosion > > > > filter was added to the example file in GPG... > > > > Please take a look at this screenshot to see what I mean: > > > > http://www.gameprogramming.de/screen.jpg (not a very good one, i know) > > > > > > > > Thanks for your help, > > > > David > > > > > > > > > > > > _______________________________________________ > > > > GDAlgorithms-list mailing list > > > > GDAlgorithms-list@... > > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > > Archives: > > > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > > > > > > > _______________________________________________ > > > GDAlgorithms-list mailing list > > > GDAlgorithms-list@... > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > > Archives: > > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > > > > > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDAlgorithms-list@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > ```
 RE: [Algorithms] midpoint displacement problems From: - 2002-02-28 12:57:55 ```I've done it similarly as Tom describes, and no strange peaks occur: http://manabove.org/terrain/images/tes26.jpg > A-B-C > | | | > D-E-F > | | | > G-H-I > For which we start with values A, C, G and I. We calculate the midpoint E > the way I would expect: > E = (A+C+G+I)/4 ```
 RE: [Algorithms] midpoint displacement problems From: Oscar Cooper - 2002-03-01 10:54:48 ```Hiya, I've just had an almost identical artefact, which seems to have been caused by subdividing the heightfield using a depth first traversal. When I switched to breadth first, the nasty peaks disappeared (kinda obvious when you think about it :-). Before working this out, I'd switched to using Tom's method for subdividing the edges, so maybe this is a factor too... Oscar Cooper. Creature Labs. -----Original Message----- From: David Zaadstra [mailto:mythomania@...] Sent: 27 February 2002 20:12 To: gdalgorithms-list@... Subject: [Algorithms] midpoint displacement problems Hello everybody, I have a problem with the midpoint displacement algorithm (from GPG1). I get strange little peaks all around my landscape. I've been looking for the bug for hours now and starting to believe that I'm a complete idiot. Could it be that the peaks are normal? That would explain why an erosion filter was added to the example file in GPG... Please take a look at this screenshot to see what I mean: http://www.gameprogramming.de/screen.jpg (not a very good one, i know) Thanks for your help, David ```
 Re: [Algorithms] midpoint displacement problems From: David Zaadstra - 2002-02-27 21:34:30 ```hmm...I think I just found out that the algorithm as it is described in GPG1 doesn't really work. I can't explain why, but I calculated a small 8*8 heightmap on paper, and I get wrong results. The points get interpolated like an exponential function from the middle of the square to its edges. When I read how it works with a line I thought that the algorithm is ok. And it is, but only in 2D, with the line. I think the problem with the 3D version is that the 4 points which get interpolated don't lie in a plane. Or is it because the distance of the points is sqrt(2) in the diamond step and 1 in the square step? Can anybody else comment on this? Somebody how knows the algorithm, and is better at maths and explaining than me maybe? ----- Original Message ----- From: "Tom Forsyth" To: "David Zaadstra" ; Sent: Wednesday, February 27, 2002 9:24 PM Subject: RE: [Algorithms] midpoint displacement problems > That looks like your midpoint calculation isn't working right - the peaks > are the "coarse" divisions, but then the rest of the subdivisions don't > interpolate through them properly. Try turning off any random variation > after, say, three divisons - you should then get a nice smooth surface. But > I don't think you will, because the calculation of the new midpoint isn't > working right. > > Tom Forsyth - purely hypothetical Muckyfoot bloke. > > This email is the product of your deranged imagination, > and does not in any way imply existence of the author. > > > -----Original Message----- > > From: David Zaadstra [mailto:mythomania@...] > > Sent: 27 February 2002 20:12 > > To: gdalgorithms-list@... > > Subject: [Algorithms] midpoint displacement problems > > > > > > Hello everybody, > > > > I have a problem with the midpoint displacement algorithm (from GPG1). > > I get strange little peaks all around my landscape. I've been > > looking for > > the bug for hours now and starting to believe that I'm a > > complete idiot. > > Could it be that the peaks are normal? That would explain why > > an erosion > > filter was added to the example file in GPG... > > Please take a look at this screenshot to see what I mean: > > http://www.gameprogramming.de/screen.jpg (not a very good one, i know) > > > > Thanks for your help, > > David > > > > > > _______________________________________________ > > GDAlgorithms-list mailing list > > GDAlgorithms-list@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > ```