Implement slope analysis on the mesh

[mariuszhermansdorfer]

There are Grasshopper plugins, which allow to perform landscape analyses on various meshes, Bison being one example.

Great as they are, their performance is not good enough for real-time interaction with the Sandbox, a slope analysis takes approx. 400ms on a typical mesh coming from SandWorm.

Implementing the algorithm directly in the C# code will be much faster. Current implementation of elevation banding takes 15ms, slope should be in the same ball park.

Use the logic described here.

[philipbelesky]

I assume that, in this case, the slope values would be fed to the colorising function in place of the elevation gradient?

I've implemented slope analysis before on a mesh, so I could have a go at implementing this. It might be worth evaluating an implementation that works directly on the point cloud rather than the mesh faces — this could potentially be the faster approach but would require the raw grid of pixels to be restructured in order to reliably determine neighbouring pixels.

It's probably worth bundling/implementing an aspect analysis at the same time — the logic is pretty similar. An occasionally-useful option that I've used before is also to have a combined measure of aspect and slope, e.g. where color hue measures aspect while color brightness measures slope.

[mariuszhermansdorfer]

It would be great if you could take care of this.
Yes, I was thinking of working directly on the point cloud rather than mesh faces. The current way of storing pixels in a one-dimensional array should work for this purpose. Consider the Core.CreateQuadMesh() function:

            for (int y = 1; y < yd - 1; y++)       // Iterate over y dimension
            {
                for (int x = 1; x < xd - 1; x++)       // Iterate over x dimension
                {
                    int i = y * xd + x;
                    int j = (y - 1) * xd + x;

                    mesh.Faces.AddFace(j - 1, j, i, i - 1);
                }
            }

it already addresses 4 neighboring pixels spread across two rows. The same logic could be easily extended to addressing 8 neighboring pixels for a slope analysis.

Given:
int i = y * xd + x; 
int j = (y - 1) * xd + x;
int k = (y + 1) * xd + x;

//Current pixel
i
//East pixel
i + 1
// West pixel
i - 1
//North pixel
j
//NW pixel
j - 1
//NE pixel
j + 1
//South pixel
k
//SW pixel
k -1
//SE pixel
k + 1

Given some additional boundary checks, this could be called directly from the main loop iterating over all the pixels in the SandWormComponent. Alternatively, we could just skip first and last rows as well as first and last columns to make sure we never run out of the array bounds. I'd be more than happy with that.

                for (int rows = topRows; rows < KinectController.depthHeight - bottomRows; rows++)

                {
                    for (int columns = rightColumns; columns < KinectController.depthWidth - leftColumns; columns++)
                    {

                        int i = rows * KinectController.depthWidth + columns;

[philipbelesky]

I've added a very quick prototype of this slope function on this branch but put out a few ideas/problems before integrating it:

• Because color is added for a vertex rather than a face, the slope (and aspect) values for each vertex are essentially the average slopes for the surrounding faces that each share the central node vertex. For performance reasons, I wonder if we need to use 8 neighbours or whether 4 would be good enough? When measuring 8 neighbours the diagonal nodes share vertices with the cardinal direction nodes so their slopes are somewhat related anyway
  • A more extreme optimisation might be for each node to only measure 2 neighbours (i.e. North + East) which would mean the slope for each point is nominally less accurate as each vertex then is measuring a particular neighbouring face rather than the average of its surrounding faces. However, as the number of points is very dense the resulting visualisations might still do the job of showing the overall slope ranges effectively
• The function sets out an array of points of uncertain size to check, which means that edge nodes do not need to be handled as a special case. That might make the method slower to call though and should be tested.
• As a slope measurement is always between two vertices the above function would end up performing the calculations for each pair multiple times over the course of the loop (i.e. A1 > B1 and B1 > A1). At that point it might be worth creating a data structure to calculate and store slope values along all of the mesh's edges and then have the per-vertex calculation lookup the values for the relevant edges.
  • Would need to test whether it is better to pre-calculate these values before the per-pixel loop, or whether this could be calculated while the per-pixel loop plays out. As we are iterating in row -> column order we would only need to store the edges from the current and preceding/proceeding rows.
  • An advantage of pre-calculation is that it could be done in parallel quite nicely whereas constructing the store within the per-pixel loop might cause problems if the per-pixel loop ever became parallelised.

[mariuszhermansdorfer]

Thanks for laying out these ideas, @philipbelesky. I'm all for making this whole thing as fast as possible. Like the idea of optimizing the heck out of it. While testing, please keep in mind, that the slope analysis should serve as a base for water flow visualization as mentioned in #14. We should make sure, that while optimizing one, we don't break the other.

Having said that, I think that ditching D8 in favor of D4 is definitely worth exploring. Also, I really like the idea of avoiding multiple checks of the same pairs of pixels and taking an edge-based approach instead.

Regarding your most recent doodles. Consider the following line:
double hypotenuse = center.DistanceTo(n);
I'm wondering whether this is correct. Slope is defined as run/rise. The DistanceTo() function measures the actual 3D distance between two points, which already includes rise. Shouldn't it be taking depthPixelSize.x and depthPixelSize.y as run parameter respectively? This would have an additional benefit of not having to call the DistanceTo() function each time we evaluate a pixel.

Also, how do you intend on creating the Point3f[] neighbourPixels arrays? I'd suggest going with a probably less elegant, but maybe more robust solution of hard-coding all the pixel addresses in the GetSlopeForPixels function as described in one of the above posts. Worst-case scenario, it's only 8 of them to work with.

[philipbelesky]

Noted RE: #14, although the different options sketched out there seem quite different in their approach which makes it a little hard to plan whether/how they can work within the per pixel-loop.

The inner workings of that slope calculation were very preliminary as I was mostly testing out what parameters would be compatible with the per-pixel loop. I had imagined the slope value being reported an angle rather than a ratio/or % which is kind of unnecessary when its only purpose is to produce a relative colour field and the sin() call is likely likely slower than a rise/run division.

Also, as a heads up I have a local branch with a few of the optimisations mentioned in #12 and some new ones that have been benchmarked as further improvements. I'll finish integrating/testing those and prepare a PR that should include the slope option also over the next few days.

[mariuszhermansdorfer]

Sounds great. Looking forward to seeing the results of your work!
Heads up from my side as well - my IT department changed some security policies last week and broke my Visual Studio in the process. As a result I’m unable to check out any branches other than master. Hopefully I’ll get that fixed in a couple of days and will be able to commit again.

[BarusXXX]

Hi Guys. Just catching up to your work.

My 2 cents on D4 vs D8;

While D8 gives more accurate movement per refresh and more local accuracy, comparing how D8 and D4 fair in accomplishing a diagonal cell flow in the water simulation; since the computational cost between D4 and D8 is linear, comparing for diagonal flow (it takes one step in D8 but two steps in D4) as Philip pointed out;

no_of_cells x 4 every 1st refresh vs no_of_cells x 8 to be calculated every 2nd refresh it should be in the same computational ball park but twice as fluid for D4(smooth animation).

So if the aim is to achieve smooth animation, simpler simulation models (like the D4) with lower computational cost per refresh are the winners.