How can I concentrate points in areas of higher curvature?

How can I distribute points over an implicit surface, to concentrate them more densely in areas of higher curvature?

I've considered adding points randomly and rejecting points not required based on the curvature, but I'd like to know if there is a better approach giving a more even distribution over areas of similar curvature, while still giving the higher density required in high curvature regions.

I'm looking specifically at using these points for a triangulation of the surface, and I don't want to create more triangles than I need for relatively flat parts.

This will be applied to shapes with a known derivative so the curvature at a given point can be calculated.

This does not need to be a real-time approach.

• Are you looking for a more accurate way to sample from a distribution, without montecarlo test i mean? If you don't care much about the computational approach (i.e. you're looking for an accurate approach rather than the computational effort) i could have a solution, but it could be optimized of course. Aug 5 '15 at 11:33
• Do you know the analytical function or can you only sample it? Do you know its analytical derivative? Aug 5 '15 at 12:04
• @JulienGuertault Does my edit clarify? Aug 5 '15 at 14:07
• @Lukkio I'd like accuracy first, then optimisation can come later once the approach is working. Aug 5 '15 at 14:08
• You might want to take a look into finite-element methods, which also use triangulation (or more generally: simplices) and often face the problem of needing a higher sampling density in selected regions. They are bound to have developed algorithms for this. Aug 20 '15 at 6:56

The idea I would try to apply would be the following: I make the example for the curve, but it should be straightforward for the application for the surface.

Let's say we have a curve $\gamma$ uniformly parametrized. Let's say the parameter of the curve is $s$. Your goal is to sample point corresponding to value of $s$ such that the curvature is high.

If you get the magnitude of the curvature $c$, this will be function of $s$ too. So, if you normalize the function $|c|$, you will get a probability distribution. If you get the integral of such distribution, you will have the cumulative distribution. Let's call this cumulative function $C(s)$.

The sampling problem from a distribution given by the cumulative function is well known, so basically once you have sampled a set of value $s_0,s_1,\dots,s_n$, such value will be related to the points of interest.

The application of this method to the case of surface should be straight, since basically you have a two dimensional cumulative distribution function, but the sampling problem is exactly the same.

Just to give some detail, it is basically sampling from a distribution given the cumulative function involves two steps:

1. take a random value in the interval $[0,1]$, let's say $k$

2. solve the equation $C(s) = k$.

This approach is exact, of course it is expensive, but if you like such approach you can work on optimization.

• No latex support yet. Aug 5 '15 at 19:13
• I was looking for something that could be used with an implicit surface even if it doesn't have a parameterisation. Is it always possible to parameterise an implicit surface if the derivative is known? Aug 5 '15 at 21:10
• Any questions that would benefit from MathJax for formulae can be added to this meta answer to increase our chances of getting MathJax. (This one has already been added.) Aug 5 '15 at 21:12
• Remember that what you need is the distribution function derived from the curvature, you said you can derive everything (by the way what kind of surface have you got? i.e. the equation). Anyway... what do you mean with "derivative known"? do you know an explicit formula of the derivative? or it is implicit too? (i.e. described by means of differential equation)? Aug 5 '15 at 21:27
• By the way... if the curve/surface is algebric (i mean expressed by polynomial or rational staff) there are computational methods based on bspline/nurbs that explain how to perform parametrization of such curves. I had a glance here docs.lib.purdue.edu/cgi/…, further method (even advanced) could be found in one of my favourite book on Nurbs (The NURBS book by Tiller). Aug 5 '15 at 21:37

A good starting point is the classic paper Using particles to sample and control implicit surfaces, published in SIGGRAPH 1994.

A simple particle simulation described in the paper Sampling implicit objects with physically-based particle systems (Computers & Graphics, 1996) for curves works for surfaces as well; see Dynamic Texture for Implicit Surfaces for examples.

For a more recent example, see Shape and tone depiction for implicit surfaces (Computers & Graphics, 2011).

The following naïve approach will probably not yield as nicely distributed points as the ones given by Lhf, but it should be much easier to implement and computationally faster:

For two points $x$ and $y$ let $d(x,y)$ denote the average distance you want points with the average curvature of $x$ and $y$ to have, e.g., some constant multiplied with the inverse of the average curvature of $x$ and $y$.

Now build up your collection of points $A$ successively:

1. Select a random point $x$ and add two points, such that all three points form a equilateral triangle with edge length $d(x,x)$.

2. Add all points to $A$ and mark them as adjacent.

3. Repeatedly do the following until there are no adjacencies in $A$ anymore:

1. Select two adjacent points $x$ and $y$ from $A$. Mark them as non-adjacent.
2. Consider a point $z$ that has a distance of $d(x,y)$ from both these points. Of the two possible such points select the one pointing outwards of $A$ (this needs some work, but should be straightforward).
3. Check whether $z$ is closer than $d(x,y)$ to any point from $A$ that is still adjacent to another point.

• if no, mark $x$ and $z$ as well as $y$ and $z$ as adjacent and add $z$ to $A$.
At the end, $A$ should be a collection of points matching your criteria. You sort-of just created a triangulation but it may be pathological and thus you should probably triangulate the points afresh.