1

Context: trying to draw a 3d geometry using points only.

Looking for ways (efficiency vs precision) to evenly distribute N amount of 3d points over a 3D plane made of 3 vertices - see image below: enter image description here

So, with given three 3D points (A.xyz, B.xyz, C.xyz), how to generate an array of N 3D points that evenly spread/distribute over the surface.

Put another way, if I had N points to paint a triangle surface, where should I place these points on the plane so that the surface appears fully painted.

Your help would be much appreciated!

mika
  • 1,003
  • What does "evenly spread" mean? – NoChance Aug 26 '16 at 18:42
  • Sorry I don't know the right vocabulary for this. I guess I meant the output points ideally should be distributed over the full surface, without concentrations toward corners or center. Which is also what I referred to when comparing efficiency versus precision. – mika Aug 26 '16 at 18:54
  • 1
    Maybe you mean that the minimal distance between pairs of points should be maximised. Maybe you mean that the average density in some sense should be minimal. There are probably many different ways to formulate this which gives different answers. – mathreadler Aug 26 '16 at 19:34
  • From which angle? – mathreadler Aug 26 '16 at 20:01
  • Why not just use a random number generator to generate 3 values for x,y,z and repeat the process 3 times, then test if what you get is a triangle or not. – NoChance Aug 26 '16 at 20:01
  • Any three random points will almost always give a triangle. The question is about finding points which in some sense fills a given triangle the best. – mathreadler Aug 26 '16 at 20:02
  • Correct, finding points which fills a given triangle best, in a 3d space. – mika Aug 26 '16 at 20:08
  • The angle would be defined by xyz coordinates of ABC @mathreadler – mika Aug 26 '16 at 20:11
  • So we are looking at the triangle from some sort of camera placed in origo $(0,0,0)$? – mathreadler Aug 26 '16 at 20:13
  • Correct, however the camera position should not have an impact on the algorithm , only the the 3 vertices of the triangle (ABC) should be needed. – mika Aug 26 '16 at 20:20
  • See Lloyd's algorithm. – WimC Aug 26 '16 at 20:24
  • Would that work for 3d? – mika Aug 26 '16 at 20:28

1 Answers1

0

For an even spreading, I advocate a barycentrical approch. It suffices to use the set of points:

$$\begin{pmatrix}x\\y\\z\end{pmatrix}=\frac{u}{20}\begin{pmatrix}x_a\\y_a\\z_a\end{pmatrix}+\frac{v}{20}\begin{pmatrix}x_b\\y_b\\z_b\end{pmatrix}+\frac{20-u-v}{20}\begin{pmatrix}x_c\\y_c\\z_c\end{pmatrix}$$

with a double loop "for $u=0..20$, for v=$0..(20-u)$" (take care of this limit $20-u$).

Explanation: points such as the ones described in (1) are of the symbolic form $M=\alpha a+\beta b+\gamma c$ with $\alpha + \beta + \gamma = 1$ (check it...) ; they are inside the triangle defined by points $a,b,c$, and, in a reciprocal way, any point in this triangle is such that it can be written in this way ($\alpha, \beta, \gamma$ are called the "barycentrical coordinates" of $M$).

If you don't want the sides of the triangle to be "painted", use loops beginning at 1 and ending at $19.$

Of course, $20$ is just there as an example ; it can be replaced by any other integer constant.

Jean Marie
  • 81,803
  • This is close to what I'm looking for, but it's renders a 4 sides polygon, not 3 sided - see: http://i.imgur.com/wdwzWwy.png – mika Aug 26 '16 at 23:41
  • here is an example render of a sphere geometry using your algorithm: http://i.imgur.com/r4DZgGP.png It looks kind of nice :) But how could i remove the extra triangles? – mika Aug 27 '16 at 00:31
  • Adding if ( v>uLength-u ) continue; did the trick, thanks! – mika Aug 27 '16 at 03:49
  • Sorry for having forgot this restriction... – Jean Marie Aug 27 '16 at 06:46