3

The issue that I'm having is working out how 3D Perlin Noise is used as a density function with the Dual Contouring Algorithm. I've found it difficult to find any Dual Contouring implementations or blogs/write ups that use or discuss the specifics of how they use 3D Perlin Noise with Dual Contouring to generate terrain.

I've managed to implement Dual Contouring with an implicit sphere so know its working correctly and have a basic idea of how density functions works (at least in a spheres case), have a basic knowledge of Perlin Noise (implemented the 3D version tested via texture output and basic cubic voxel terrain generation) and understand how to compute the gradient (analytical derivative in this case) for use with the QEF calculation.

I've experimented with a number of ways to try get relatively decent looking terrain with no success:

1) Generate the density values for the grid via Perlin noise (i.e. value < 1 is inside, > 1 is outside and 0 is on the contour) and then generate the intersection values (where the contour intersects the cube) for the cubes completely separately again using Perlin Noise, using the co-ordinate input as the index of the cube we're on with a minor offset. (Basically just generated a really cubic surface)

2) Use Perlin Noise in a similar way to the sphere function, generate the density grid via Perlin Noise and then for each intersection interpolate along the edge between the two nearby cubes density values until the Perlin Noise hits 0 (i.e. the exact point that the density function intersects the edge) then use the co-ordinate that triggered the 0 output from the Perlin Noise. (Again generates a cubic surface, think it might be because the interpolation usually triggers 0 when the co-ords hit an integer value i.e. on the Perlin latices edge.)

3) This is the one I've had most success with, similar to 2) except i keep the input values to the Perlin Noise within a 0.1 to 0.9 range i.e. kept within a single lattice. It feeds out ok values for some cubes but calculating the QEF (the averaged point for the cube) sends a fair amount of points well outside the range of a cube despite all the intersection points being well within the cube. I think its something to do with the way I use the Perlin Gradients, essentially I interpolate to find the co-ordinate that generates the 0 for the Perlin Noise return value, I then use the gradient(analytically derivative) from this co-ordinate and the culmination of all these sends the co-ordinate miles away.

Feel free to ask for more information to be posted up if its required I'll do my best, this is my first time posting so sorry if the post is sub-par.

tl;dr How is 3D Perlin Noise used as a density function to generate terrain in a Dual Contouring Algorithm? specifically in generating intersection points and normals for edges for the QEF calculation.

Edit: The new current method I'm trying (and failing) to use to integrate Perlin Noise using the perlin noise generator to fill up the initial density data, after this point for any edge intersection I do some simple linear maths to find the ratio on the line where the 0 crosses (so if a density value on one side was 0.5 and on the other side it was -0.5 the value given out would be that the 0 is 50% of the way between them so 0.5f). Once I have this value i simply add it on to the relevant co-ordinate to get the intersection point on that edge. After this point I use the intersection as input to calculate the Perlin Noises 3D Gradient (essentially just running the noise function with it as an input and calculating the analytically derivative using the method found here: 3D Perlin noise analytical derivative).

Once this is done the gradient and intersection values are fed into the QEF function, which uses SVD decomposition instead of the QR decomposition described as being more accurate within the original Dual Contouring Paper (found SVD to be simpler looking and it also sounded like it'd be less performance heavy from the paper).

A few screenshots to hopefully help a little by showing what it currently looks like. The first has the diagonal code commented out and the second has the Diagonal in place, the number immediately after all the prints of "vertex out of bounds" is the number of vertices outside of their cube.

https://i.stack.imgur.com/G0Wiv.jpg

The second with the diagonal division occurring:

https://i.stack.imgur.com/cLHyl.jpg

Community
  • 1
  • 1
user4568137
  • 31
  • 4
  • When solving QEF, are you subtracting the mass point (average of all intersections for a given grid cube) to the intersection point and add the same mass point back to the final QEF result ? This make sure your point will stick to your grid cube. –  Feb 26 '15 at 15:03
  • Hey, thanks for the reply. Yeah at the moment I'm averaging the intersections to create the mass point then negating it from the intersections before the dot product and the rest of the calculation is computed. After the calculation I add it back on. I've actually made a little progress on finding out what causes the most extreme vertex displacements, it appears to be dividing the calculated SVD diagonal from the data. If i comment this out it essentially removes the majority of displacements, however it leaves the mesh smooth and there is still some displaced vertices. – user4568137 Feb 26 '15 at 17:57
  • I've tested that my QEF function gives similar results to an QEF calculator I found online from http://www.sandboxie.com/misc/isosurf/isosurfaces.html and it gives the same results, so it seems more like its a misconception of how to form the perlin data into hermite data rather than an internal issue in the QEF function. – user4568137 Feb 26 '15 at 18:00
  • Good news. You stated that your mesh was smooth now with "still some displaced vertices". So you have what you expect in some areas, right ? Can you see some regularity / patterns in your artifacts ? I suppose you already triple-checked your noise data consistency but if not, have a check to your values and perhaps also at your Nyquist band-limits. You could also try to render or raymarch your noise and see if you grab clues / anomalies at the same locations. I believe your hermite storage is quite ok if you have at least some correct parts. Do you have a snapshot (easier to see what's up)? –  Feb 26 '15 at 19:13
  • Yeap I added a few images to the original post, one with the diagonal division and one without it, their is around 400 extra intersections placed incorrectly when the division is used (300 when not used, 700 when used). You can see from the images the main problem area is the bottom left area of the terrain and it extends up along a curve through the terrain from that point. The pattern always remains the same, the noise is set with a fixed seed value at the moment and their is no variation.I can locate the exact loop that the biggest anomaly occurs which is how I found out about the divisions – user4568137 Feb 26 '15 at 19:51
  • The edited part of the post also contains a little about how I'm using perlin noise at the moment. On top of that I'd like to add that at the moment the way I'm using the intersection point as input to the perlin noise to get the gradient may be a little iffy. I'm basically just offsetting the intersection points that would normally be integers (since each cube is a unit across, and 2 of the 3 values would be a whole number) by a small delta (0.0001) this is to avoid the Perlin Noise automatically setting the outputs to 0. – user4568137 Feb 26 '15 at 19:58
  • All input values to the Perlin Noise are also kept within the 0-1 range so as to stay within the same lattice. Thanks very much for the help by the way! And sorry if I'm spamming too much. I'll look into the Nyquist band-limits as I'm unfamiliar with this (relatively new to noise functions), however I'm relatively sure the noise function is alright, I've outputted 2D textures to check the output before as well as using an fbm version to generate minecraft esque cubic voxel terrain. – user4568137 Feb 26 '15 at 20:02
  • Ok, just saw your shots. You may solve the first shot before anything. One this one, DC looks like working as it should, but you are right, if this point is supposed to be that high (guess which one) your surrounding hermite edges intersection normals values are perhaps wrong. If the point is supposed to be here, I guess you must figure out what's going on with the intersected edges normals. –  Feb 26 '15 at 20:07
  • And you are not spamming at all. Keep going. Yes, check Nyquist limits for noise, not using them is so aliasing and other artifact-prone. –  Feb 26 '15 at 20:09
  • yeah it looks to be my normal calculations that are causing the problem, the minor issues (after diagonal division has been cancelled out) are being caused by the QEF functions final stage where it multiplies by the V portion of the SVD Decomposition (the SVD Decomposed matrix comprising only of normals) against the currently stored value and then adding it on. I'll have to triple check that I'm calculating the analytical derivative correctly, if its not that I'm unsure what I could do next, perhaps find an alternative method of deriving it. – user4568137 Feb 26 '15 at 22:02
  • The values are perhaps correct but the dirs look definitely weird. I am not sure but your DC command line output remind me Tao Ju's implementation. You can ask him for hints if you are stuck, he is cool / will answer. Good luck. –  Feb 27 '15 at 09:13

0 Answers0