• Create Account

# Marching Cube Holes

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

6 replies to this topic

### #1Tapped  Members   -  Reputation: 384

Like
0Likes
Like

Posted 14 September 2012 - 06:38 AM

I have problem generating terrain in marching cubes. My marching cube implementation is in OpenCL. I have 16 * 16 * 16 voxels per block. It works fine when generating a sphere, the only problem is that you can see some small holes between some parts of the sphere. My theory is floating precision, but i dont know.

http://imageshack.us/photo/my-images/833/failsphere.png/

Another problem occur when i tries to generate terrain, with noise:

http://imageshack.us...failterrain.png

As you can see, it does not look well. This was rendered with isolevel 0.9f.

I create the terrain like:
[source lang="cpp"]sampler_t randomVolumeSampler = CLK_NORMALIZED_COORDS_TRUE | CLK_ADDRESS_REPEAT | CLK_FILTER_LINEAR;density.x = wPos.y; density.x += read_imagef(randomVolume, randomVolumeSampler, realGridPos).x * 0.25f;[/source]

So i was wondering, if i have implemented marching cube wrong, or if it behaves right,

Edited by Tapped, 14 September 2012 - 06:42 AM.

### #2Bacterius  Crossbones+   -  Reputation: 8177

Like
4Likes
Like

Posted 14 September 2012 - 09:03 AM

I believe your problem is because you are sampling a random volume of finite size, which is not tileable. The crack patterns suggest you are having a discontinuity in your noise volume at regular UV intervals. Do the cracks appear at the edge of each block only? How do you generate randomVolume? Is it done on the CPU? Can we see the noise generation code?

The marching cubes triangulation looks fine - if you screw that up it usually ends up looking like nothing, so your code seems to work in that regard.

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

- Pessimal Algorithms and Simplexity Analysis

### #3Kaptein  Prime Members   -  Reputation: 1844

Like
1Likes
Like

Posted 14 September 2012 - 10:32 AM

it depends on how you build your sphere.. with voxels the best test would be a n^3 for loop over the diameter, ie. dx is iterated (x-radius+1 to x+radius-1) etc.
that way you can be sure the sphere is complete
the terrain is unmistakably as the poster above me said, the noise doesn't use world-space coordinates.. or it's just an array you draw 4 times which is even more wrong

Edited by Kaptein, 14 September 2012 - 10:33 AM.

### #4Tapped  Members   -  Reputation: 384

Like
0Likes
Like

Posted 15 September 2012 - 07:21 AM

Thanks, i generate the noise with glm::perlin. First I create a random 3D vector, which is then being multiplied with the position in the random volume, then i use that as the seed for perlin.

The thing is that my blocks are 2.0 * 2.0 * 2.0 in opengl size. And 32 * 32 * 32 voxels per block, therefore 16 * 16 * 16 voxels per cubic meter(opengl). What you see on the picture is one block, so 4 cracks appear per block. So yeah, i believe it is some problem with the tiling of the random volume. However, how can i create a tileable noise volume. I have tried different techniques which did not fix the cracks, like using the same noise on all edges...

#define RANDOM_VOLUME_EXTENT 16

glm::vec3 randVec(glm::signedRand1<float>(), glm::signedRand1<float>(), glm::signedRand1<float>());
for(int i = 0;i < RANDOM_VOLUME_EXTENT;++i)
{
for(int j = 0;j < RANDOM_VOLUME_EXTENT;++j)
{
for(int k = 0;k < RANDOM_VOLUME_EXTENT;++k)
{
glm::vec3 p(i * randVec.x, j * randVec.y, k * randVec.z);
randBuffer[(i*RANDOM_VOLUME_EXTENT*RANDOM_VOLUME_EXTENT)+(j*RANDOM_VOLUME_EXTENT) + k] = glm::perlin(p);
}
}


Edited by Tapped, 15 September 2012 - 07:23 AM.

### #5Tapped  Members   -  Reputation: 384

Like
0Likes
Like

Posted 15 September 2012 - 07:32 AM

Never mind, found enough information on how to create tileable perlin noise.

Edited by Tapped, 15 September 2012 - 07:32 AM.

### #6Bacterius  Crossbones+   -  Reputation: 8177

Like
0Likes
Like

Posted 15 September 2012 - 07:41 AM

Nice that you've fixed it (can you give some information or perhaps links for people of the future - hello guys!). I don't know but I'm pretty sure you only need a single seed for perlin noise, and that you then use the world position in the density function to sample the perlin noise directly (with a single seed, it can be sampled from -infinity to +infinity and will never have discontinuities, so you won't have that crack problem).

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

- Pessimal Algorithms and Simplexity Analysis

### #7Tapped  Members   -  Reputation: 384

Like
2Likes
Like

Posted 15 September 2012 - 12:19 PM

Now i have implemented the information i got from: http://gamedev.stack...le-perlin-noise
Even if i did that, i still had cracks, but then after a lot of testing of different sample types, i finally got it work. It worked when i used this sampler:
__constant sampler_t randomVolumeSampler = CLK_NORMALIZED_COORDS_TRUE | CLK_ADDRESS_MIRRORED_REPEAT | CLK_FILTER_LINEAR;

float4 realGridPos;
realGridPos.x = gridPos.x * voxelSize;
realGridPos.y = gridPos.y * voxelSize;
realGridPos.z = gridPos.z * voxelSize;

density.x += read_imagef(randomVolume, randomVolumeSampler, realGridPos).x * 0.8f;


realGridPos is the same as the local position in terms of a block, which in this case range from [0.0, 2.0] for each block.
Here is the result:

http://imageshack.us...383/itworks.png
Thanks for the help!

Edited by Tapped, 15 September 2012 - 12:19 PM.

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS