From: <kemen@po...>  20020228 12:57:55

I've done it similarly as Tom describes, and no strange peaks occur: http://manabove.org/terrain/images/tes26.jpg > ABC >    > DEF >    > GHI > 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 
From: Tom Forsyth <tomf@mu...>  20020227 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: gdalgorithmslist@... > 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 > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > 
From: James Johnson <James.J<ohnson@si...>  20020227 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: gdalgorithmslist@... 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? 
From: Tom Forsyth <tomf@mu...>  20020228 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: ABC    DEF    GHI 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: ABC+      DEFX      GHI+ ...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 CI is not a straight line, it is some odd sigmashaped 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: gdalgorithmslist@... > 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" <tomf@...> > To: "David Zaadstra" <mythomania@...>; > <gdalgorithmslist@...> > 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: gdalgorithmslist@... > > > 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 > > > > > > > > > _______________________________________________ > > > GDAlgorithmslist mailing list > > > GDAlgorithmslist@... > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > > Archives: > > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > > > > _______________________________________________ > > GDAlgorithmslist mailing list > > GDAlgorithmslist@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > 
From: David Zaadstra <mythomania@gm...>  20020228 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 equalsided. 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" <tomf@...> To: "David Zaadstra" <mythomania@...>; <gdalgorithmslist@...> 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: > > ABC >    > DEF >    > GHI > > 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: > > ABC+ >      > DEFX >      > GHI+ > > ...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 CI is not a straight line, it is some odd > sigmashaped 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: gdalgorithmslist@... > > 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" <tomf@...> > > To: "David Zaadstra" <mythomania@...>; > > <gdalgorithmslist@...> > > 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: gdalgorithmslist@... > > > > 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 > > > > > > > > > > > > _______________________________________________ > > > > GDAlgorithmslist mailing list > > > > GDAlgorithmslist@... > > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > > > Archives: > > > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > > > > > > > _______________________________________________ > > > GDAlgorithmslist mailing list > > > GDAlgorithmslist@... > > > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > > Archives: > > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > > > > > > _______________________________________________ > > GDAlgorithmslist mailing list > > GDAlgorithmslist@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > 
From: <kemen@po...>  20020228 12:57:55

I've done it similarly as Tom describes, and no strange peaks occur: http://manabove.org/terrain/images/tes26.jpg > ABC >    > DEF >    > GHI > 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 
From: Oscar Cooper <oscar.cooper@cr...>  20020301 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: gdalgorithmslist@... 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 
From: David Zaadstra <mythomania@gm...>  20020227 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" <tomf@...> To: "David Zaadstra" <mythomania@...>; <gdalgorithmslist@...> 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: gdalgorithmslist@... > > 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 > > > > > > _______________________________________________ > > GDAlgorithmslist mailing list > > GDAlgorithmslist@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > Archives: > > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > 