Hi,

I need to create a smooth terrain. To do this I intend to use the Marching Cubes geometry extractor and to smooth out the densities using my own algorithms (I'll devise them when I get to that ).

The thing is, I don't understand exactly what changing the density of a voxel actually does. Say you have a corner case, with one voxel and a single triangle covering that corner. Does adjusting the density "slide" that polygon in and out? This is really hard to describe in words... ok here's a picture I drew in Paint that attempts to illustrate what I'm describing, but in 2D:



The other problem I had trying to visualise all this in my head: Does geometry form around a voxel or next to it? Here's another picture:



I realise both of those drawing are probably confusing to anyone who understands PolyVox properly (you're probably thinking, "What on earth is he going on about??") because the drawings are probably nothing like how it actually works, but I really have no idea how PolyVox works.

Any information you can give me to help me understand this (more is better) would be much appreciated

EDIT: I forgot that the main reason I posted this was because I was confused as to how to use densities if you need the voxel to contain more than just an integer. What if I need a voxel to contain a struct with several other variables in it? What controls the density in that case?

Clonkex

Those are some beautiful diagrams :-)

Ok, so the most important point to realise is that the Marching Cubes algorithm does not actually opaerate on individual voxels, but rather it processes groups of eight voxels at at time. A group of eight voxels is called a 'cell' (or at least that is what I call it).

When processing a cell the algoithm generates a number of vertices which make up the triangles. Each vertex lies exactly on an edge of the cell, and so is between exactly two voxels. Here's the image from Wikipedia:



In that image each box is a cell, and the eight corners are the eight voxels. A voxel can be solid or empty (indicated by the presence or absence of the yellow dot) and a vertex always lies between two voxels.

So, given two voxels with a vertex between them, how do we decide exactly where the vertex should go? The easiest thing is to place it in the middle (as shown in that figure) but to get smooth terrain is is often useful to place it nearer to one of the voxels than the other.

If your two voxels have densities of 0 and 255, and your 'threshold' value is 128 then the vertex will be placed in the middle. On the other hand, if the voxel values are 0 and 130 the the vertex will be placed very close to to voxel with a value of 130. In other words, the algorithm takes the two voxel values and determines where the threshold value would fall between them.



It's quite advanced (needs some C++ template knowledge) but you can provide a custom marching cubes controller. The default version contains some documentation and is here: https://bitbucket.org/volumesoffun/poly ... ?at=master

Hope that helps :-)

Looking at the code, it seems it does this as a linear interpolation. I can see how this improves smoothness but is there any benefit to using a non-linear function to make things even smoother? Or is linear interpolation + some smooth lighting enough?

_________________
Matt Williams
Linux/CMake guy

I think if you used a higher-order interpolation (such as cubic) then it would be possible to obtain smoother meshes, though you might also lose some high frequency (small) details. There would also be the additional cost of sampling the extra voxels to perform the interpolation.

Something like GLSL's smoothstep() function might be interesting as it allows you to get a smooth curve from only two end points (I think?) and it's pretty cheap. Hmmm... I think that's probably worth testing.

Why thankyou



Ah, so it's effectively a "weight" system. The higher the value of each voxel, the more "pull" towards it there is. It's closer to my "forms next to" idea.



I understand the concepts of templates, but not exactly how to implement them. I'll have to do a bit of experimenting on this front. Just had quick look at the code; should be fairly simple to achieve what I need



It does indeed, thanks

Cool, my question spawned a new Issue on BitBucket Also, just out of curiosity, are you and Matt related at all?

Clonkex

Kind of, the details of the way in which linear interpolation is used to position the vertex between two voxels are also discussed here (this is the article which the marching cubes surface extractor was originally based on): http://paulbourke.net/geometry/polygonise/

It's a useful article in general for understanding how the system works.



Yep, we're brothers :-)

Ah, well I can see where you got edgeTable and triTable from then



I thought so but I couldn't tell because Matt's pulling a face in his BitBucket picture

Clonkex

Yeah, my face does that a lot We've also got bios at http://www.volumesoffun.com/about-us/

_________________
Matt Williams
Linux/CMake guy

Lol

Actually I hadn't noticed the About Us page. I can see the family resemblance there

Clonkex