12 Replies - 1025 Views - Last Post: 19 March 2012 - 03:25 PM Rate Topic: -----

#1 lifeinbinary  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 158
  • Joined: 15-February 11

Anyone up for some linear algebra ;) OpenGL question

Posted 17 March 2012 - 03:58 PM

I'm in a graphics course that required linear algebra as a pre-requisite (that I didn't have!)... I'm making a simple animated grid mesh (where y=f(x,z)) but need to calculate normals for all my vertices so that the lighting works well. I've decided to use Goureaud's method which takes the normal of all adjoining polygons to calculate the normal of the vertex. The formula for the normal of a poly is in pseudo:

Begin Function CalculateSurfaceNormal (Input Triangle) Returns Vector

Set Vector U to (Triangle.p2 minus Triangle.p1)
Set Vector V to (Triangle.p3 minus Triangle.p1)

Set Normal.x to (multiply U.y by V.z) minus (multiply U.z by V.y)
Set Normal.y to (multiply U.z by V.x) minus (multiply U.x by V.z)
Set Normal.z to (multiply U.x by V.y) minus (multiply U.y by V.x)

Returning Normal

End Function

And the formula for finding the normal of a vertex is:

n= (n1+n2+n3+n4) / |n1 + n2 + n3 + n4| where there would be 4 adjoining polygons(triangles).

So I've coded it up but am getting strange normals on the interior vertices... here's the relevant code... sorry for the lengthy preamble but I just didn't want to have to reexplain what I mean :)


std::vector<GLushort> indices;

	for(int i = 0; i < m-1; i++)
	{
		for(int j = 0; j < n-1; j++)
		{
			indices.push_back((j*m)+i);
			indices.push_back((j*m)+i+1);
			indices.push_back((j*m)+i+m);

			Polygon p;
			p.P1 = vertices[(j*m)+i].vertex;
			p.P2 = vertices[(j*m)+i+1].vertex;
			p.P3 = vertices[(j*m)+i+m].vertex;

			p.calculateNormal();

			vertices[(j*m)+i].polygons.push_back(p);
			vertices[(j*m)+i+1].polygons.push_back(p);
			vertices[(j*m)+i+m].polygons.push_back(p);
		}
	}

	for(int i = 1; i < m; i++)
	{
		for(int j = 0; j < n-1; j++)
		{
			indices.push_back((j*m)+i);
			indices.push_back((j*m)+i+m-1);
			indices.push_back((j*m)+i+m);

			Polygon p;
			p.P1 = vertices[(j*m)+i].vertex;
			p.P2 = vertices[(j*m)+i+m-1].vertex;
			p.P3 = vertices[(j*m)+i+m].vertex;

			p.calculateNormal();

			vertices[(j*m)+i].polygons.push_back(p);
			vertices[(j*m)+i+m-1].polygons.push_back(p);
			vertices[(j*m)+i+m].polygons.push_back(p);


		}
	}



And...

struct Polygon
			{
				vec3 P1;
				vec3 P2;
				vec3 P3;

				vec3 normal;

				void calculateNormal()
				{
					vec3 U = P2 - P3;
					vec3 V = P3 - P1;

					normal = vec3((U[1]*V[2])-(U[2]*V[1]),
							(U[2]*V[0])-(U[0]*V[2]),
							(U[0]*V[1])-(U[1]*V[0]));
				}
			};


	struct Vertex
	{
		Vertex(vec3 v, vec3 n) {
			vertex = v;
			normal = n;
		}

		Vertex(vec3 v) {
			vertex = v;
		}

		void setNormal(std::vector<Polygon> p)
		{
			vec3 vecTot;
			for(int i = 0; i < p.size(); i++)
			{
				vecTot = vecTot + p[i].normal;
				//std::cout << p[i].normal;

			}

			GLfloat normalized = sqrt((vecTot[0]*vecTot[0])+(vecTot[1]*vecTot[1])+(vecTot[2]*vecTot[2]));
			//std::cout << vecTot << " " << normalized << "\n";
			normal = vecTot/normalized;
		}

		vec3 vertex;
		vec3 normal;
		//Material material;
		std::vector<Polygon> polygons;
	};



Thanks for anyone who has read this far! And thanks for any help I can get :) Oh and here is a screenshot of the output (white lines are the normals)...

Attached image(s)

  • Attached Image
  • Attached Image


Is This A Good Question/Topic? 0
  • +

Replies To: Anyone up for some linear algebra ;) OpenGL question

#2 CTphpnwb  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2911
  • View blog
  • Posts: 10,083
  • Joined: 08-August 08

Re: Anyone up for some linear algebra ;) OpenGL question

Posted 17 March 2012 - 06:45 PM

I haven't looked to closely so I could be wrong, but this doesn't look right to me:
			GLfloat normalized = sqrt((vecTot[0]*vecTot[0])+(vecTot[1]*vecTot[1])+(vecTot[2]*vecTot[2]));
			//std::cout << vecTot << " " << normalized << "\n";
			normal = vecTot/normalized;


Isn't this supposed to be this formula?
n= (n1+n2+n3+n4) / |n1 + n2 + n3 + n4|
Was This Post Helpful? 0
  • +
  • -

#3 lifeinbinary  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 158
  • Joined: 15-February 11

Re: Anyone up for some linear algebra ;) OpenGL question

Posted 17 March 2012 - 06:51 PM

Thanks for answering! Yes, my vecTot is the sum of n and my normalized is the square root of the vectors squared... So vecTot/normalized should be that formula...is this not right?
Was This Post Helpful? 0
  • +
  • -

#4 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1327
  • View blog
  • Posts: 4,552
  • Joined: 19-February 09

Re: Anyone up for some linear algebra ;) OpenGL question

Posted 17 March 2012 - 07:07 PM

Hi, it looks like you are trying this - Vectors Normalizing.
Was This Post Helpful? 0
  • +
  • -

#5 CTphpnwb  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2911
  • View blog
  • Posts: 10,083
  • Joined: 08-August 08

Re: Anyone up for some linear algebra ;) OpenGL question

Posted 17 March 2012 - 07:21 PM

The square root of the sum of the squares is not the same as the sum of the square root of the squares:

-3^2 + 4^2 = 9 + 16 = 25
sqrt(25) = 5

sqrt(-3^2) + sqrt(4^2) = 3+4 = 7

This post has been edited by CTphpnwb: 17 March 2012 - 07:22 PM

Was This Post Helpful? 0
  • +
  • -

#6 anonymous26  Icon User is offline

  • D.I.C Lover

Reputation: 0
  • View blog
  • Posts: 3,638
  • Joined: 26-November 10

Re: Anyone up for some linear algebra ;) OpenGL question

Posted 18 March 2012 - 03:58 PM

You have very bad naming conventions in your code, making a visual review difficult. Some of your normals are clearly inverted (appearing on the underside of the surface), so you need to check the ranges of your values to ensure they are being accurately computed.
Was This Post Helpful? 0
  • +
  • -

#7 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 449
  • View blog
  • Posts: 849
  • Joined: 17-March 11

Re: Anyone up for some linear algebra ;) OpenGL question

Posted 18 March 2012 - 04:21 PM

View PostCTphpnwb, on 18 March 2012 - 01:45 AM, said:

I haven't looked to closely so I could be wrong, but this doesn't look right to me:
			GLfloat normalized = sqrt((vecTot[0]*vecTot[0])+(vecTot[1]*vecTot[1])+(vecTot[2]*vecTot[2]));
			//std::cout << vecTot << " " << normalized << "\n";
			normal = vecTot/normalized;


Isn't this supposed to be this formula?
n= (n1+n2+n3+n4) / |n1 + n2 + n3 + n4|


I have no idea what you have just written here, you add the coefficients of a vector and you divide it by the absolute value of the sum of the coefficient. I can tell you right now the result will be either 1 or -1 or will give you a division by 0 error. Anyway the result will not be a normalized vector, nor will it be a length by any norm.

@lifeinbinary
The algorithm you've written in pseudo code is:

suppose the 3 points of your polygon are a, b, c

u = b-a
v = c-a

normal = u x v (x being the cross/vector product)

And then normalize the normal :)

Looking at

void calculateNormal()
{
	vec3 U = P2 - P3;
	vec3 V = P3 - P1;

normal = vec3((U[1]*V[2])-(U[2]*V[1]),
	(U[2]*V[0])-(U[0]*V[2]),
	(U[0]*V[1])-(U[1]*V[0]));
}



This looks a little strange:

vec3 U = P2 - P3;
vec3 V = P3 - P1;



It's not necessarily incorrect, it will just draw a normal using the left-hand-rule. Usually a right hand rule is used when deciding the order of the points in relation to which way the normal should face.

Basically if all your normals face in the opposite direction, use:

vec3 U = P2 - P1;
vec3 V = P3 - P1;



If not, you did it right :)

Secondly, you should normalize the individual normals. It's length is dependent on the sort of size and shape of the polygon. And the longer normals will have a much bigger impact on the sum.

Tell us if that fixes your vertex normals or should we keep looking.

EDIT: I just assumed the pseudo code was the entire algorithm and jumped to the code at that point. The goureaud shading part was actually just bellow that. Sorry about that. I edited the post to reflect that.

This post has been edited by Karel-Lodewijk: 18 March 2012 - 04:57 PM

Was This Post Helpful? 0
  • +
  • -

#8 CTphpnwb  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2911
  • View blog
  • Posts: 10,083
  • Joined: 08-August 08

Re: Anyone up for some linear algebra ;) OpenGL question

Posted 18 March 2012 - 08:00 PM

View PostKarel-Lodewijk, on 18 March 2012 - 07:21 PM, said:

View PostCTphpnwb, on 18 March 2012 - 01:45 AM, said:

I haven't looked to closely so I could be wrong, but this doesn't look right to me:
			GLfloat normalized = sqrt((vecTot[0]*vecTot[0])+(vecTot[1]*vecTot[1])+(vecTot[2]*vecTot[2]));
			//std::cout << vecTot << " " << normalized << "\n";
			normal = vecTot/normalized;


Isn't this supposed to be this formula?
n= (n1+n2+n3+n4) / |n1 + n2 + n3 + n4|


I have no idea what you have just written here, you add the coefficients of a vector and you divide it by the absolute value of the sum of the coefficient. I can tell you right now the result will be either 1 or -1 or will give you a division by 0 error. Anyway the result will not be a normalized vector, nor will it be a length by any norm.

Maybe you should read the code in post #1.
Was This Post Helpful? 0
  • +
  • -

#9 Aphex19  Icon User is offline

  • Born again Pastafarian.
  • member icon

Reputation: 614
  • View blog
  • Posts: 1,873
  • Joined: 02-August 09

Re: Anyone up for some linear algebra ;) OpenGL question

Posted 18 March 2012 - 10:38 PM

Quote

And the formula for finding the normal of a vertex is:

n= (n1+n2+n3+n4) / |n1 + n2 + n3 + n4| where there would be 4 adjoining polygons(triangles).


Gouraud's method is to average all of the face normals of each adjoining triangle. Is this what you were implementing?

This post has been edited by Aphex19: 18 March 2012 - 10:39 PM

Was This Post Helpful? 0
  • +
  • -

#10 mgcdrd  Icon User is offline

  • D.I.C Head

Reputation: 5
  • View blog
  • Posts: 83
  • Joined: 22-November 09

Re: Anyone up for some linear algebra ;) OpenGL question

Posted 19 March 2012 - 02:24 AM

View PostAphex19, on 18 March 2012 - 10:38 PM, said:

Quote

And the formula for finding the normal of a vertex is:

n= (n1+n2+n3+n4) / |n1 + n2 + n3 + n4| where there would be 4 adjoining polygons(triangles).


Gouraud's method is to average all of the face normals of each adjoining triangle. Is this what you were implementing?


As this equation stands, you will get either -1, 0 or 1. The only way to get 0 is if the sum of the normal is 0, otherwise Now see the lower and right hand sides' normals being down makes sense, if the graph is aligned right. In a 2d Cartesian plane, there are 4 quadrons (sorry for the spelling). 1 has positive numbers for both x, and y-so the product would be positive, 2 quad's have a positive and negative coordinate, so the product would be negative. And the last quad has 2 negative coordinate, which as math goes, the product would be positive. This is in a 2d cartesian plane.
In the 3d model, the idea is the same, only there are 8 areas about the center. Finding the normal would include this third dimension, and give you either the -1 or 1. This is where the normal issue might be. Having a negative normal will point the lines opposite to the positive. Maybe you can try to find the absolute value of all the normals, which should point them in the same direction.

vec3 U = P2 - P3;
vec3 V = P3 - P1;



Karel-Lodewijk looks to be right. You will get the negative (opposite from 0) value of your V answer this way. You should be "measuring" from the same vertex, in your case P3.

Just my 2 cents
Was This Post Helpful? 0
  • +
  • -

#11 Karel-Lodewijk  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 449
  • View blog
  • Posts: 849
  • Joined: 17-March 11

Re: Anyone up for some linear algebra ;) OpenGL question

Posted 19 March 2012 - 04:05 AM

Quote

n = (n1+n2+n3+n4) / |n1 + n2 + n3 + n4|


Well the original poster presented this as a formula to calculate the average of 4 for normal vectors n1, n2, n3, n4. Which will work. This is the same as taking the vector sum of these 4 vectors and then normalizing the resulting vector, which is how he implemented it. CTphpnwb threw me off guard by quoting a vector normalization code and then suggesting this formula. In that context I assumed n1-n4 to be vector coefficients of one vector. This is why people put vectors in bold or underline/overline them, to avoid this confusion.

Anyway, the code for setNormal seems ok to me. We don't really know where the std::vector of polygons comes from, but if it is somehow a vector of all polygons that share the vertex, then it should be ok. I stand by my original suggestions though, verify if the vectors in your original calculation of a polygons's normal are correct (normals point the right way) and normalize your polygon normals individually before taking the sum.

This post has been edited by Karel-Lodewijk: 19 March 2012 - 05:23 AM

Was This Post Helpful? 0
  • +
  • -

#12 anonymous26  Icon User is offline

  • D.I.C Lover

Reputation: 0
  • View blog
  • Posts: 3,638
  • Joined: 26-November 10

Re: Anyone up for some linear algebra ;) OpenGL question

Posted 19 March 2012 - 04:33 AM

I can see that I am going to have to explain this later properly. As I said earlier, please debug the existing code to ensure values are in range. If they aren't you will get incorrect results. Also, I am concerned about how the triangles are being formed to perform the calculations, as the code is not the best.

Anyway, will return to this later.
Was This Post Helpful? 0
  • +
  • -

#13 anonymous26  Icon User is offline

  • D.I.C Lover

Reputation: 0
  • View blog
  • Posts: 3,638
  • Joined: 26-November 10

Re: Anyone up for some linear algebra ;) OpenGL question

Posted 19 March 2012 - 03:25 PM

A little bit of background:

- 'Finding the normal of a surface' and 'normalizing a vector' are two different things.

Normalizing a vector

In this operation we are taking and arbitrary vector a and dividing each of its components ax, ay, and az by the vector's magnitude. See this link for a detailed explanation of the math.

Finding the normal of a surface

Finding the surface normal is simply finding the normalized unit vector from above that is perpendicular to the referenced surface. Again, here is the detailed math behind it.

there is one additional term that is often flying around and that is 'norm'. The vector norm is simply the absolute value of the vector.

Hopefully the differences between 'norm', normalization and finding the normal of a surface is clear.

a very important note about the Cross Product (finding the perpendicular vector on the cartesian 3D plane) is that it is only applicable to the 3D plane and does not apply to any other dimensions!

How would this look in code?

Clearly, you need to define a base type with associated overloaded functionality to perform the math provided above. Given that this is a class exercise it is the OP's responsibility to determine how to overload the vector operations. I would suggest, however, that they work from a struct that looks more like

struct Vector3D
{
    float x;
    float y;
    float z;
};



Which is the pretty standard format and also permits tidy dereferencing, for example:

    Vector3D vec[3];

    vec[0].x = ....



It makes things a whole lot easier.

Where has everyone else been going wrong?!

You appeared to be getting confused with the norm* words clarified above, as well as introducing other methods too early, and omitting important steps.

Gouraud Shading simply interpolates (algorithmically 'fills in the blanks') when shading a surface by referencing the surface normals in order to create a natural shading effect.

I hope that clears stuff up!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1