StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Someone answered this question on another forum. I am going to post the revised getSurfaceNormal function. This implements the second algorithm as described by Nathan Reed</p> <p>-(CGPoint)getSurfaceNormalAt:(CGPoint)pt withSquareWidth:(int)area { // This method only looks at surface pixels</p> <pre><code>int avgX = 0; int avgY = 0; CGPoint normal; float len; ccColor4B color = ccc4(0, 0, 0, 0); for (int w = area; w >= -area; w--) { int h = area; do { if ([self pixelAt:ccp(w + pt.x, h + pt.y) colorCache:&color]) { if (color.a != 0) { if (w < 0) { avgX -= w; avgY -= h; } else { avgX += w; avgY += h; } break; } // end inner if } // end outer if h--; } while (h >= -area); } // end for int perpX = -avgY; int perpY = avgX; len = sqrtf(perpX * perpX + perpY * perpY); normal = ccp(perpX/len, perpY/len); return normal; } </code></pre> <p>Also here is the person's original post: Credit to Nathan Reed for the answer</p> <p>I think your basic idea is sound. I'll summarize what your current code is doing. To get the average normal within an area around a point, you're gathering all the pixels in a rectangle centered on that point. For all the pixels in the rectangle that are solid ground, you're averaging the vector from the pixel to the query point. Effectively you're calculating the vector from the center of mass of the nearby solid pixels, to the query point.</p> <p>I have two general suggestions to speed this up. The first is that you don't need to look at <em>every single</em> pixel in the search area. You can probably get a pretty good approximation by using a sparse sampling: only look at a few isolated pixels, evenly distributed over the search area. For instance, you could step by units of 2 to 5 pixels instead of 1 pixel in your loop; that would give you a sparse grid sampling and that might well be good enough to get away with. <a href="http://devmag.org.za/2009/05/03/poisson-disk-sampling/" rel="nofollow">Poisson disk sampling</a> is also a common sparse sampling method, especially in pixel shaders for soft shadows, SSAO, etc. You precompute a Poisson disk pattern (just store the points in a static array in your code) and scale the pattern to the size of the desired search area at runtime.</p> <p>The second suggestion is that you could probably replace the 2D search with a series of 1D searches. You don't really care what's under the ground, you just care what the orientation of the ground <em>surface</em> is, if I understand correctly. So you could pick a few points along the top of the search area, then just do a 1D search down from each starting point until you find a solid pixel. In ASCII art,</p> <pre><code>X X X X | | | | | | | ..* | ..*...*.... *............ </code></pre> <p>The X's are the starting points, the vertical bars are the 1D searches, the dots are the ground, and the stars are the ground points found by the searches. Once you have these points, you calculate the average vector from each of them to the center point, but negate the vector for the points to the left of the center, and leave it alone for the points to the right. That should prevent the average from coming out zero, and will give you a vector that points tangent to the terrain, to the right. Calculate the vector perpendicular to this one and you'll have your normal.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload