<p>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.</p>

<p>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.</p>

<p>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)$.</p>

<p>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.</p>

<p>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.</p>

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

<ol>
<li><p>take a random value in the interval $[0,1]$, let's say $k$ </p></li>
<li><p>solve the equation $C(s) = k$.</p></li>
</ol>

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

CC BY-SA 3.0
2015-08-05T19:13:27.257Z
No latex support yet.
joojaa
CC BY-SA 3.0
2015-08-05T21:10:49.550Z
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?
trichoplax is on Codidact now
CC BY-SA 3.0
2015-08-05T21:12:23.440Z
Any questions that would benefit from MathJax for formulae can be added to [this meta answer](http://meta.computergraphics.stackexchange.com/a/34/231) to increase our chances of getting MathJax. (This one has already been added.)
trichoplax is on Codidact now
CC BY-SA 3.0
2015-08-05T21:27:45.793Z
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)?
user8469759
CC BY-SA 3.0
2015-08-05T21:37:28.987Z
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 http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1827&context=cstech, further method (even advanced) could be found in one of my favourite book on Nurbs (The NURBS book by Tiller).
user8469759
CC BY-SA 3.0
2015-08-05T18:15:47.057Z
2017-05-19T08:22:56.183Z
2017-05-19T08:22:56.183Z
user8469759
<p>A good starting point is the classic paper <a href="http://dl.acm.org/citation.cfm?id=192227" rel="nofollow">Using particles to sample and control implicit surfaces</a>, published in SIGGRAPH 1994.</p>

<p>A simple particle simulation described in the paper <a href="http://dx.doi.org/10.1016/0097-8493(96)00005-2" rel="nofollow">Sampling implicit objects with physically-based particle systems
</a> (<em>Computers &amp; Graphics</em>, 1996) for curves works for surfaces as well; see <a href="http://www.visgraf.impa.br/Projects/dtexture/" rel="nofollow">Dynamic Texture for Implicit Surfaces</a> for examples.</p>

<p>For a more recent example, see <a href="http://dx.doi.org/10.1016/j.cag.2010.09.017" rel="nofollow">Shape and tone depiction for implicit surfaces</a> (<em>Computers &amp; Graphics</em>, 2011). </p>

CC BY-SA 3.0
2015-08-15T00:14:29.170Z
2015-08-18T18:26:56.627Z
2015-08-18T18:26:56.627Z
lhf
<p>The following naïve approach will probably not yield as nicely distributed points as the <a href="https://computergraphics.stackexchange.com/a/251/394">ones given by Lhf</a>, but it should be much easier to implement and computationally faster:</p>

<p>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$.</p>

<p>Now build up your collection of points $A$ successively:</p>

<ol>
<li><p>Select a random point $x$ and add two points, such that all three points form a equilateral triangle with edge length $d(x,x)$.</p></li>
<li><p>Add all points to $A$ and mark them as adjacent.</p></li>
<li><p>Repeatedly do the following until there are no adjacencies in $A$ anymore:</p>

<ol>
<li>Select two adjacent points $x$ and $y$ from $A$. Mark them as non-adjacent.</li>
<li>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).</li>
<li><p>Check whether $z$ is closer than $d(x,y)$ to any point from $A$ that is still adjacent to another point.</p>

<ul>
<li>if yes, discard it.</li>
<li>if no, mark $x$ and $z$ as well as $y$ and $z$ as adjacent and add $z$ to $A$.</li>
</ul></li>
</ol></li>
</ol>

<p>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.</p>

CC BY-SA 3.0
2015-08-20T07:48:41.177Z
2015-11-03T17:35:30.317Z
2017-04-13T13:00:43.660Z
Wrzlprmft
<p>How can I distribute points over an implicit surface, to concentrate them more densely in areas of higher curvature?</p>

<p>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.</p>

<p>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.</p>

<hr>

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

<p>This does not need to be a real-time approach.</p>

CC BY-SA 3.0
2017-05-19T09:14:24.353Z
I do not quite see the difficulty: Couldn't you just start with any coarse initial mesh, and refine each triangle where e.g. the product of $curvature\times area$ (or e.g. the sum of the absolute angles to the neighbour triangles, or any other heuristic) exceeds some constant? In bthe basic adaptive FEM you basically try to estimate the error on each element (i.e. triangle) and refine it if the error is above some threshhold.
flawr
CC BY-SA 3.0
2015-08-05T11:33:16.990Z
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.
user8469759
CC BY-SA 3.0
2015-08-05T12:04:10.887Z
Do you know the analytical function or can you only sample it? Do you know its analytical derivative?
Julien Guertault
CC BY-SA 3.0
2015-08-05T14:07:56.533Z
@JulienGuertault Does my edit clarify?
trichoplax is on Codidact now
CC BY-SA 3.0
2015-08-05T14:08:44.487Z
@Lukkio I'd like accuracy first, then optimisation can come later once the approach is working.
trichoplax is on Codidact now
CC BY-SA 3.0
2015-08-06T05:01:17.340Z
@trichoplax: yes. Now thinking about how it can be used.
Julien Guertault
CC BY-SA 3.0
2015-08-20T06:56:31.913Z
You might want to take a look into [finite-element methods](https://en.wikipedia.org/wiki/Finite_element_method), 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.
Wrzlprmft
<algorithm><triangulation>
How can I concentrate points in areas of higher curvature?
trichoplax is on Codidact now
# How can I concentrate points in areas of higher curvature?

(Asked by: username_0 on 2015-08-05)

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.

**Tags:** algorithm, triangulation

> **Comments:**
> **username_2**: 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.  
> **username_3**: Do you know the analytical function or can you only sample it? Do you know its analytical derivative?  
> **username_0**: @username_3 Does my edit clarify?  
> **username_0**: @Lukkio I'd like accuracy first, then optimisation can come later once the approach is working.  
> **username_3**: @username_0: yes. Now thinking about how it can be used.  
> **username_4**: You might want to take a look into [finite-element methods](https://en.wikipedia.org/wiki/Finite_element_method), 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.  
> **username_1**: I do not quite see the difficulty: Couldn't you just start with any coarse initial mesh, and refine each triangle where e.g. the product of $curvature\times area$ (or e.g. the sum of the absolute angles to the neighbour triangles, or any other heuristic) exceeds some constant? In bthe basic adaptive FEM you basically try to estimate the error on each element (i.e. triangle) and refine it if the error is above some threshhold.  

---

## 3 answers

### Answer by username_2 on 2015-08-05. Score: 12

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.

> **Comments:**
> **username_5**: No latex support yet.  
> **username_0**: 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?  
> **username_0**: Any questions that would benefit from MathJax for formulae can be added to [this meta answer](http://meta.computergraphics.stackexchange.com/a/34/231) to increase our chances of getting MathJax. (This one has already been added.)  
> **username_2**: 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)?  
> **username_2**: 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 http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1827&context=cstech, further method (even advanced) could be found in one of my favourite book on Nurbs (The NURBS book by Tiller).  

---

### Answer by username_6 on 2015-08-15. Score: 2

A good starting point is the classic paper [Using particles to sample and control implicit surfaces](http://dl.acm.org/citation.cfm?id=192227), published in SIGGRAPH 1994.

A simple particle simulation described in the paper [Sampling implicit objects with physically-based particle systems](http://dx.doi.org/10.1016/0097-8493(96)00005-2) (*Computers & Graphics*, 1996) for curves works for surfaces as well; see [Dynamic Texture for Implicit Surfaces](http://www.visgraf.impa.br/Projects/dtexture/) for examples.

For a more recent example, see [Shape and tone depiction for implicit surfaces](http://dx.doi.org/10.1016/j.cag.2010.09.017) (*Computers & Graphics*, 2011).


---

### Answer by username_4 on 2015-08-20. Score: 2

The following naïve approach will probably not yield as nicely distributed points as the [ones given by Lhf](https://computergraphics.stackexchange.com/a/251/394), 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.


---

