How Will I Compute The Normals at Vertices using 2D Object?

[kindgnice]

Hello Professionals,

Good day. I would like to ask if how will I compute the surface normals (BLUE) and the normal constraints (GREEN) from any 2D object using the boundary constraints (RED)?
As an example, I have drawn my own 2D object sample using Paint, (sorry for the bad quality because I cannot find a good example in internet).

Given:
RED - boundary constraints
GREEN - normal constraints
BLUE - surface normal
d = distance between boundary constraints and normal constraints

Image: https://i.imgur.com/Nl2D7su.jpg

As shown in my given picture, my goal is to get the GREEN normal constraints.
1. How will I compute the surface normals (BLUE)?
2. How can I use value I computed from #1 to get the normal constraints (GREEN) with respect to the boundary constraints (RED), considering the distance of normal constraints (GREEN) and boundary constraints (RED) is d=0.01?

Thank you very much for your response in advance and God bless :)

[lastchance]

For the surface normals in TWO DIMENSIONS:
- find the local tangent vector (e.g. from difference of two position vectors either side)
- rotate this vector by 90 degrees (sense depends on which direction is outward)
- normalise this normal vector by its length to get a unit vector n

For the constraints:
- start at the boundary and offset by vector -dn (i.e. distance d in the opposed direction to unit normal n)



In THREE DIMENSIONS it's probably easier: take the cross product of two sides of a triangle to get a vector normal to that triangle.

[lastchance]

This should work.

Input file (boundary.txt): two columns containing boundary x and y coordinates.

Output file (output.txt): six columns - one and two are boundary x,y; three and four are unit normal vectors; five and six are your "normal constraints".

Sample output (sorry, just a quick plot with gnuplot):
https://imgur.com/a/Z01T8

#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;

//======================================================================

struct Pt2d { double x, y; };

Pt2d operator +( Pt2d p, Pt2d q )     { return { p.x + q.x, p.y + q.y }; }
Pt2d operator -( Pt2d p, Pt2d q )     { return { p.x - q.x, p.y - q.y }; }
Pt2d operator -( Pt2d p )             { return { -p.x     , -p.y      }; }
Pt2d operator *( double r, Pt2d p )   { return { r * p.x  , r * p.y   }; }
Pt2d operator /( Pt2d p, double r )   { return { p.x / r  , p.y / r   }; }
double dot( Pt2d p, Pt2d q ) { return p.x * q.x + p.y * q.y; }
double abs( Pt2d p ) { return sqrt( dot( p, p ) ); }

ostream &operator <<( ostream &strm, Pt2d p )
{
   const int w = 12;
   strm << fixed;
   return strm << setw( w ) << p.x << "  " << setw( w ) << p.y;
}

//======================================================================

vector<Pt2d> readData( string filename )
{
   vector<Pt2d> result;
   double x, y;
   ifstream fin( filename );
   while ( fin >> x >> y ) result.push_back( { x, y } );
   fin.close();
   return result;
}

//======================================================================

vector<Pt2d> setNormal( const vector<Pt2d> &boundary, bool anticlockwise )
{
   int N = boundary.size();
   vector<Pt2d> normal( N );

   for ( int i = 0; i < N; i++ )
   {
      int im = i - 1, ip = i + 1;                // Points behind and in front
      if ( i == 0     ) im = N - 1;              // Special cases at ends (assumes closed curve)
      if ( i == N - 1 ) ip = 0;

      // Get tangent (weighted on distances to nearby points)
      Pt2d t1 = boundary[ip]-boundary[i ];
      Pt2d t2 = boundary[i ]-boundary[im];
      double abst1 = abs( t1 );
      double abst2 = abs( t2 );
      Pt2d tangent = ( abst2 * t1 + abst1 * t2 ) / ( abst1 + abst2 ); 

      // Get normal vector by rotating 90 degrees
      Pt2d nvec = { tangent.y, -tangent.x };
      if ( !anticlockwise ) nvec = -nvec;
      normal[i] = nvec / abs( nvec );            // normalise
   }

   return normal;
}

//======================================================================

vector<Pt2d> setNormalConstraint( const vector<Pt2d> &boundary, const vector<Pt2d> &normal, double d )
{
   int N = boundary.size();
   vector<Pt2d> constraint( N );

   for ( int i = 0; i < N; i++ ) constraint[i] = boundary[i] - d * normal[i];
   return constraint;
}

//======================================================================

int main()
{
   bool anticlockwise = true;
   double d = 0.25;

   vector<Pt2d> boundary   = readData( "boundary.txt" );
   vector<Pt2d> normal     = setNormal( boundary, anticlockwise );
   vector<Pt2d> constraint = setNormalConstraint( boundary, normal, d );


   // Output
   #define SPACE << "      " <<
   ofstream fout( "output.txt" );
   for ( int i = 0; i < boundary.size(); i++ ) fout << boundary[i] SPACE normal[i] SPACE constraint[i] << '\n';
   fout.close();
}

boundary.txt

8  0
7.82518  1.03956
7.30836  2.03368
6.47214  2.93892
5.35305  3.71572
4.00001  4.33012
2.47214  4.75528
0.836238  4.97261
-0.836216  4.97261
-2.47212  4.75529
-3.99999  4.33013
-5.35303  3.71573
-6.47213  2.93893
-7.30836  2.03369
-7.82518  1.03957
-8  1.32679e-005
-7.82519  -1.03954
-7.30837  -2.03367
-6.47215  -2.93891
-5.35306  -3.71571
-4.00002  -4.33012
-2.47216  -4.75528
-0.836259  -4.97261
0.836195  -4.97261
2.4721  -4.75529
3.99997  -4.33014
5.35302  -3.71574
6.47211  -2.93895
7.30835  -2.03371
7.82517  -1.03958

    8.000000      0.000000          1.000000     -0.000003          7.750000      0.000001
    7.825180      1.039560          0.948283      0.317427          7.588109      0.960203
    7.308360      2.033680          0.818154      0.575000          7.103822      1.889930
    6.472140      2.938920          0.656293      0.754506          6.308067      2.750293
    5.353050      3.715720          0.493852      0.869546          5.229587      3.498333
    4.000010      4.330120          0.341795      0.939775          3.914561      4.095176
    2.472140      4.755280          0.200375      0.979719          2.422046      4.510350
    0.836238      4.972610          0.065990      0.997820          0.819740      4.723155
   -0.836216      4.972610         -0.065987      0.997820         -0.819719      4.723155
   -2.472120      4.755290         -0.200372      0.979720         -2.422027      4.510360
   -3.999990      4.330130         -0.341795      0.939775         -3.914541      4.095186
   -5.353030      3.715730         -0.493850      0.869547         -5.229567      3.498343
   -6.472130      2.938930         -0.656289      0.754509         -6.308058      2.750303
   -7.308360      2.033690         -0.818152      0.575002         -7.103822      1.889939
   -7.825180      1.039570         -0.948282      0.317428         -7.588109      0.960213
   -8.000000      0.000013         -1.000000      0.000004         -7.750000      0.000012
   -7.825190     -1.039540         -0.948285     -0.317422         -7.588119     -0.960185
   -7.308370     -2.033670         -0.818155     -0.574998         -7.103831     -1.889920
   -6.472150     -2.938910         -0.656293     -0.754506         -6.308077     -2.750283
   -5.353060     -3.715710         -0.493855     -0.869545         -5.229596     -3.498324
   -4.000020     -4.330120         -0.341799     -0.939773         -3.914570     -4.095177
   -2.472160     -4.755280         -0.200375     -0.979719         -2.422066     -4.510350
   -0.836259     -4.972610         -0.065990     -0.997820         -0.819761     -4.723155
    0.836195     -4.972610          0.065987     -0.997820          0.819698     -4.723155
    2.472100     -4.755290          0.200368     -0.979721          2.422008     -4.510360
    3.999970     -4.330140          0.341791     -0.939776          3.914522     -4.095196
    5.353020     -3.715740          0.493848     -0.869548          5.229558     -3.498353
    6.472110     -2.938950          0.656286     -0.754512          6.308038     -2.750322
    7.308350     -2.033710          0.818151     -0.575003          7.103812     -1.889959
    7.825170     -1.039580          0.948282     -0.317428          7.588099     -0.960223

[kindgnice]

Thank you very much @lastchance. I am so sorry but I have not understood the concept of taking the surface normals at each boundary constraint of a certain object. :(

1. Does computing the vertex normals at each boundary constraint has something to do with respect to the center of object (or any object)?
2. If the answer to question #1 is yes, how will I find the exact center of an object by using the coordinate values of boundary constraints?

Sorry if I cannot grasp the concept as of the moment. :'(

[lastchance]

The answer to your first question is no: nowhere is the centre needed. (Sorry, @kindgnice, but I can't work out why you are asking that: there is nothing about it either in my description or in my code). Your second question is then redundant.

A flat surface would still have a normal vector at each point, but any concept of "centre" would be meaningless.

"Normal" just means perpendicular: i.e., 90 degrees to the local surface. In 2d one can get this by first finding the local tangent, then rotating it 90 degrees.

My picture example was for an ellipse simply because it was easy to generate the vertices for that. The normal vectors are unit vectors (i.e. have length 1). Depending on the size of the object you might want to rescale these before drawing them. Similarly, I have set distance d = 0.25 because of the size of my object. You can change this to 0.01 or anything else that you want.

[kindgnice]

@lastchance I have tried to use the output points you have shared, and thank God, it worked to my program. It showed like this:

Image: https://i.imgur.com/gTSpppu.png

I am so sorry if I did not understand easily your concept of how you computed the normal vectors until now (that's why I cannot try to incorporate the codes to my program because I cannot understand[ my bad :'( ]), especially the meaning of rotation of 90 degrees. Hmm, let me try if I understood it, I tried to print your image...

My sketch: https://i.imgur.com/ZzCPvyQ.jpg

If we are going to take the coordinates A & B with the coordinates as follows:
A(8,0) and B(7.8215,1.039560). Then you take the distance between them?
D = sqrt((8-7.8125)^2+(0-1.039560)^2) = 1.0563

Then you mentioned I will rotate by 90 degrees to get the new rotated vector?
If my assumption is correct, how will I compute or rotate the old vector to the new vector?
How will I compute the normal constraints using the new rotated vector?
Thank you for your response and God bless.

P.S. Super sorry for my silly questions, and sorry for my poor math foundation. :(

[lastchance]

I only use the "distance" to get a weighted average of two possible tangents at a particular vertex.

The first approximation is vector t1, the vector from one point to the following one.
The second approximation is vector t2, the vector from the preceding point to the current one.

Both approximations are biased to one or other side, so I simply interpolate to get a better approximation. This interpolation uses the distances: that is the only reason for finding distance. At the end of the day, Pt2d tangent is a reasonably good tangent vector at that vertex.

I then rotate the tangent vector (i.e. find a perpendicular vector). If you have vector (X,Y) then (Y,-X) is a perpendicular vector. In this instance I produce a normal vector:
Pt2d nvec = { tangent.y, -tangent.x };


Finally I normalise the normal vector so that it is a unit vector (has length 1.0).
normal[i] = nvec / abs( nvec );


To find what you call the "normal constraints" I have simply gone back a distance d along the negative normal:
constraint[i] = boundary[i] - d * normal[i];


I have written a lot of operators for Pt2d just to (a) simplify my manipulations with them; (b) make it more like I would write down on paper.


For a simple introduction to vectors:
https://www.mathsisfun.com/algebra/vectors.html

[kindgnice]

Hello @lastchance, thank you for the link about the vectors. Since last week, I tried to review a lot of times your code because maybe it will help me understand how did you compute the tangent vectors and normal vectors. Honestly, I had a hard time to figure it out, but I will try to summarize what I have understood so far:

1. I thought at first abs() is taking the absolute value of certain value, until I realized that what you are doing in the program is taking the squared values of x and y values and taking its square root, like the typical computation of distance formula? Am I right?

2. Though I don't know how did you come up with your formula, at some point, it worked to my program, I think for any 2D object it will work... I observed that you use this kind of formula?

tangent = [(length_t2)(x_t1,y_t1)+(length_t1)(x_t2,y_t2)] / (length_t2+length_t1) ???

This formula of yours really worked, however, I am wondering how did you come up with this formulation? Or this is a common formula? It just so happened that I don't know it??

3. I tried to manually compute using your formula and luckily, my computations are also the same with the output.txt especially for normal[1] (which means index 1). However, I found that your output.txt is different to mine? I don't know why? :(
Here's the link of my screenshot:

Link: https://i.imgur.com/11xlE0W.jpg

So far, my brain is totally drained now. I will try to ask questions later... :)

[lastchance]

1. This is how you find the length of a vector.

2. This is just standard interpolation ( factor * T1 + (1-factor) * T2 ). Here I use relative distances of nearby points to find the factor:
factor = (length of t2) / (sum of lengths)
This will give a bigger weighting to T1 if the point related to T2 is further away.

I wouldn't spend too long on this. If the points were approximately equally spaced then simple averaging:
0.5 * (T1+T2)
would probably work perfectly well for what you are trying to do. There are fancier things like spline fits if you want more accurate tangents: they aren't worth it here.

3. Looks like my output.txt file corresponded to an earlier run of the code whilst I was still developing it and looking for the best approach to find the tangent. There are very small differences in the numerical output - my apologies for that. I have edited the output file now. I think it corresponds to your hand calculations as well.

If you supply the vertices for your "bunny" picture then I will run it for those. Note that, depending on the size of the object one may want to scale the normal vectors when plotting them (as otherwise they may either be much larger than the object concerned, or too small to see). Similarly, you may need to modify the distance to your constraints.

[kindgnice]

Thank you @lastchance for expounding further the formula that you have used in your program. I guess your explanation about interpolation has a relationship to this link?

Link: https://www.scratchapixel.com/lessons/mathematics-physics-for-computer-graphics/interpolation

I am still flabbergasted how this interpolation formula can be used and incorporated to this kind of problem. How I wish I can learn these things too... :D

On the flip side, I am also amazed how this formula can compute the tangent exactly placed at the desired coordinate point between its "in front" and "behind" points. I am also thinking how did you effectively plot them beautifully using gnuplot? It seems like the gnuplot you used has shown and presented perfectly the drawing in terms of points and unit vectors. I don't know how to show those in my program, but I am happy that it is working... :)

I also tried your program to my "customized" bunny coordinates, and luckily it worked as well perfectly. Though there is a tiny excess in the ears of the bunny, it still worked effectively. :D

Link: https://i.imgur.com/eVS2HCr.png

I am also glad to know that even I cannot see visually the vectors' direction in my program, these computations really work well. And I am also amazed how the coordinates of the vector can be used and easily multiplied directly to the distance d=0.25 and after that it will be used to subtract from boundary coordinates. It's really awesome and honestly I don't know this. :) All these program calculations worked like a miracle to my program even though I cannot see the vectors in my program.

Link: https://i.imgur.com/08TIdO0.png

"Note that, depending on the size of the object one may want to scale the normal vectors when plotting them (as otherwise they may either be much larger than the object concerned, or too small to see)."

Will finding the unit vectors (as also included in your program) not solve this issue so as to avoid scalings of normal vectors?

Thank you very much for your swift response always and God bless. :)

P.S. Here's the list of coordinate points I manually inputted one by one.....

Link: https://drive.google.com/file/d/1HvXBLPqoLqL5I536zm2pjN2phFFjimx4/view?usp=sharing

P.S.2. My clipping planes are x: (0.0 to 1.0), y: (0.0 to 1.0)

[lastchance]

how did you effectively plot them beautifully using gnuplot?

The only command I had to put into gnuplot was

p "output.txt" u 1:2 w p, "output.txt" u 5:6 w p, "output.txt" u 1:2:3:4 w vec

It's a marvellously effective and versatile graph-plotting package.

Will finding the unit vectors (as also included in your program) not solve this issue so as to avoid scalings of normal vectors?

A "unit vector" is just one with "unit" length - i.e. has length 1.0. It is better to keep the normals like that so that they can be used to precisely place points at a given distance from the surface. It would be the task of your plotting package to change them if necessary.

[kindgnice]

Hello @lastchance, I downloaded now the gnuplot. When I tried to type the same pattern that you mentioned above, I also saw the same pattern that you shared:

Image: https://i.imgur.com/mBbLomE.png

However, when I tried to use the output.txt from bunny data, this is what I saw...

Image: https://i.imgur.com/XZMxdPo.png

Is there any reason why it displays that way? Is it because my clipping area is "too" small? That even the vectors are "normalized", they happen to appear "bigger"?

[lastchance]

As I said, the normals have length 1, so they are quite big compared with the rest of your drawing. You can scale the length of the arrows inside gnuplot. For example, with a scale factor of 0.05 (see below for a comment about the negative sign):

p "output.txt" u 1:2 w p, "output.txt" u 1:2:(-0.05*$3):(-0.05*$4) w vec

You will have to play around with that scaling factor - here, I guessed at 0.05, but you can change it to anything appropriate to the overall size of your drawing.

NOTE: I have just discovered that you traverse your boundary clockwise rather than anticlockwise. You can either set anticlockwise = false; or, as I have done here, scale the plotted normal vectors by -0.05, rather than +0.05. One of your vertices also appears to be wrong. You can see this by plotting the boundary with lines rather than points:

p "output.txt" u 1:2 w l, "output.txt" u 1:2:(-0.05*$3):(-0.05*$4) w vec

(I have removed your inner constraints from the plot - you would have to change the distance within the code to move those).

Note also that the "normals" won't look perpendicular to the surface unless the gnuplot window uses the same scales in both directions (and your bunny will get quite "flattened" as well!).


If I remove the incorrect vertex, and do the appropriate rescaling of normals, your bunny lokks like a, well, hairy bunny! https://imgur.com/a/6JfGs

[kindgnice]

Wow! Thank you @lastchance for this wonderful explanation. I must admit I am still flabbergasted of gnuplot's ability to plot things like this... I think I still need more time to absord gnuplot. :D

Thank you @lastchance for your splendid guidance and help. You're an angel. (Well, you're always an angel to all of us). :D God bless you and thanks a bunch Sir! :)

P.S. I hope I can ask questions to you Sir again in the future about these things regarding vectors... probably in 3D.. from which I am afraid of looking forward... (>_<)

[zaphraud]

Re: "In three dimensions its probably easier"

No, not really. The exact same technique works, you just assume all z values are always equal to zero. It's never easier in 3D than in 2D. Ever. Using the 3D method will also be somewhat slower (not like that matters much in most cases these days).

[lastchance]

The exact same technique works

Err, no.
A line segment and a triangle are rather different things!

[kindgnice]

Hello Professionals,

Thank you again to all of you (especially to @lastchance), for the inputs about my query before. I have created a new thread for 3D scenario.

http://www.cplusplus.com/forum/general/235547/

Thank you for your insights in advance and God bless. :)