1

I got a problem where I have an object in 3D of which I can only take samples by using small linear lines. For a given point of this object, I want to find the respective normal vector.

Therefore, by using lines in 3D, I search for some more sampled points in the neighborhood. With those neighbors found by the sampling, I want to approximate the normal in the way that I create a triangulation where each triangle uses the center point. The mean normal will be the output.

This is the way how some sampling lines can be put around the studied point: enter image description here

Another example with some more sampled lines.

3

Does anyone know how to find a stable triangulation or has a promising idea?

RBarryYoung
  • 55,398
  • 14
  • 96
  • 137
Dastelt
  • 19
  • 3
  • I am not sure I understand this. Can you show us an example of the data that you have as input? – RBarryYoung Jul 24 '21 at 12:47
  • It would be too complicated to explain the exact problem or what this surface ist. But I got a vector field an search for a special feature. As an example you could imagine that the surface I search is just a square in the 3D space. The red dot in the middle is a point which I found with an approach which samples the space with a kind of raytracing. Now I want to approximate the normal for this one point. This point and and the vector field (from which I can take samples with lines) are the only inputs for the problem. – Dastelt Jul 24 '21 at 14:36
  • Did you consider Newell's algorithm? – JohanC Jul 24 '21 at 16:39
  • Actually not. I will try this, thanks. – Dastelt Jul 24 '21 at 17:31

1 Answers1

1

If you do not care about speed too much you can sort the neighboring points by ang = atan2(a,b,n) angle:

n   - view direction
ang - CW? angle

sin(ang) = ((n x a).b)/(|a|*|b|)
cos(ang) = (a.b)      /(|a|*|b|)

if (sin(ang)>=0) ang=       acos(cos(ang))
if (sin(ang)< 0) ang=2*Pi - acos(cos(ang))
ang = <0,2*Pi)

So if you got point p0 and its neighbors p1,p2,p3,... then for example set view vector as:

n = (p1-p0) x (p2-p1)
n = n / |n|

and then compute angle for each point

a1 = 0
a2 = atan2(p1-p0,p2-p0,n)
a3 = atan2(p1-p0,p3-p0,n)
...

then simply sort the points p1,p2,... by their angles and then you can simply triangulate (as triangle fan using p0 as base point of the fan)...

triangle(q0,q1,q2)
triangle(q0,q2,q3)
triangle(q0,q3,q4)
...

where q0,q1,q2,q3... are the points p0,p1,p2,p3,... in sorted order

From this you simply can apply your normal computation ... Also check this:

In case you want to weight the normals by triangle size then simply do not normalize the partial normals and simply normalize the resulting sum normal instead of dividing it by cnt ...

btw this can be done also without any goniometrics ... you can use bubble sort and simply sort they points so the comply selected winding rule so for example:

if (dot(n,cross(p(i)-p0,p(j)-p0)) > 0) swap(p(i),p(j))

However this will prevent the use of faster sorting algorithms so unless some spatial subdivision of points is used it will be slow for too many points... with spatial subdivision or small amount of point this should be fast. Also this approach does not require any additional memory space as no angle is required and sorting can be done in-place.

Spektre
  • 49,595
  • 11
  • 110
  • 380