How can I concentrate points in areas of higher curvature?

Question

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.

Answer 1

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.

Answer 2

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).

Answer 3

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 yes, discard it.
      • 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.