# Metaballs - Normals

###
#3
Moderators - Reputation: **4408**

Posted 19 May 2000 - 02:48 AM

You of course need some way of storing the vertices and vertex normals so that they can be shared among the triangles. To figure out the correct way of storing the vertices you should think of that the cubes has 12 edges that are all shared among four cubes.

- WitchLord

###
#4
Members - Reputation: **123**

Posted 19 May 2000 - 09:00 AM

It almost looked like no one had an answer.

To take this further...

I''m not using OpenGL or DirectX, but I''m coding an oldfashioned software rendered engine, but that''s ok. I''ve got the principle of normal calculation under control.

When I use x triangle normals I just calculate the average normal. (Add the normals, and normalize again)

Here''s the problem (You don''t need to know metaballs to solve this!):

Most polygons are on one side:

*top view*

When I calculate the "average normal" I get the red normal:

*side view*

**I need the blue normal...**

###
#6
Moderators - Reputation:

The solution to that particular problem is that you add a fraction of the triangle normal depending on the angle that the two edges sharing the vertex make.

Let's say you want to compute the normal for vertex V0 in a triangle V0,V1,V2

You can compute the normal like this:

E1 = V1-V0

E2 = V2-V0

Normal = CrossProduct(E1,E2);

The length of this normal is dependant on the angle between the two edges E1 and E2. And also the length of the edges like this:

LengthOf(Normal) = LengthOf(E1)*LengthOf(E2)*sin(SmallestAngleBetween(E1,E2))

If you add this normal to the vertex directly without normalizing it first you'll almost have what you want. The larger triangles have more influence than than smaller. I suggest that you try this way as I believe it gives an acceptable approximation.

If you want it to be perfect then you need to compute the actual angle between the edges. Which is done with either

angle = asin(LengthOf(Normal)/LengthOf(E1)/LengthOf(E2))

or

angle = acos(DotProduct(E1,E2)/LengthOf(E1)/LenghtOf(E2))

The second is derived from the formula for the dot product:

DotProduct(E1,E2) = LengthOf(E1)*LengthOf(E2)*cos(SmallestAngleBetween(E1,E2))

In either case the determination of the angle requires a lot of computations (as you can see).

Then the normals should be summed together like this:

V0Normal += angle/2/pi*Normalize(Normal);

Does this make me a marching-cube-guru?

- WitchLord

Edited by - WitchLord on May 19, 2000 8:39:44 PM

###
#7
Members - Reputation:

whoa whoa wait.. cant you just use the first derivative? i havent looked into metaballs a whole lot, but as far as i understand, they're implicit surfaces and as such can be differentiated..

--

Float like a butterfly, bite like a crocodile.

Edited by - goltrpoat on May 21, 2000 10:42:00 AM

###
#8
Moderators - Reputation:

The metaballs can be described mathematically with implicit surfaces, but it is my belief that it would require a lot more computations to find the normal from the first derivative than the method I describe. At least if you are using marching cubes to produce the surfaces.

But then again I haven''t worked with metaballs myself either so I could be completely wrong.

- WitchLord

###
#9
Members - Reputation:

Brilliant, WitchLord!!!!!!!!!!

That I didn''t think of it...use the angle to multiply with the normal, add em all and normalize...perfect!

> Does this make me a marching-cube-guru?

Well, If you as me - not a marching-cube-guru -

The solution is to a more trivial problem. (So it''s even better)

You can use this in a lot more of normal calculations!

Never thought anyone could answer this, thanks!

###
#12
Members - Reputation:

This is starting to look like a tutorial on "how to calc your normals on smooth surfaces".

Implementation of above angle calculation solution is completed but -

Here''s the next and hopefully last question on perfect normal calculation:

Hope to explain more with the following pictures:

"2D images of an metaballs animation"

Watch the green normals: if the polygon gets smaller -> the normals come closer together and in the end

So, the question is (forget about the angle calculation explained above):

Am I right?

Can you just calc the polygon normal (as always) and divide it by the average size of the polygons edges. Then add up all the normals that are attached to a vertex, and normalize?

###
#13
Moderators - Reputation:

Let's use a generalized function for averaging the normals at the vertices

NV = w1*N1 + w2*N2 + w3*N3 + ...

Here NV is the vertex normal. N1, N2, and N3 is the normalized triangle normals. w1, w2, and w3 is the weights that are used to average the normals together.

1. If you ignore the size of the triangle and the angle it makes at the vertex, all weights are 1.

2. You can use the angles as weights. This ensure that the vertex normal stays the same if one of the triangles are divided in two at the vertex. Yet it ignore the size of the triangle which is also good if you for example tesselate your triangles so that a triangle is divided into four parts.

3. If you use the size of the triangle as weight, you'll of course get that larger triangles have more influence on the vertex normal. This is not too good if any triangle is divided into parts as the size will then change and the vertex normal will move away from the triangles normal. But then again this may be what you want.

4. Then there is the possibility to use the reciprocity of the triangles area as weight. Then the smaller the triangle is the more influence it will have. This has similar effects as the above.

For your problem I would say that number 4 is what you want. Here you can compute the weight like this:

E1 = V1-V0

E2 = V2-V0

Normal = CrossProduct(E1,E2);

w = Normal.x*Normal.x + Normal.y*Normal.y + Normal.z*Normal.z;

VertexNormal += Normal/w;

You'll of course have to be careful so you don't get divide by zero due to the low precision of floats or doubles.

Give this a try and see if it works better

(Hmm, I think I'll have to make my own little demo with Metaballs )

- WitchLord

Edited by - WitchLord on May 22, 2000 6:40:26 PM

###
#14
Members - Reputation:

WitchLord, good to hear from you again! Who else could respond so such a topic (maybe goltrpoat?).

I first said:

> Can you just calc the polygon normal (as always) and divide it by the average size of the polygons edges. Then add up all the normals that are attached to a vertex, and normalize?

Your version: (see if I''m getting this right)

> Calc the polygon (un-normalized-)normal and divide it by it''s own (un-normalized-)normal length^2. Then add up all the normals that are attached to a vertex, and normalize!

This way small polys weigh more. If a polygon size is nearing zero the weight is nearing infinity...

If the above doesn''t turn out to be the solution, should we be thinking in a sort of interpolation technique between polygons?

Looks like you know what I meant, and it seems right!

Also, your formula is a nice and fast implementation, thanks. In a few minutes/hours I''ll be needing some sleep, but I''ll test it tomorrow.

> (Hmm, I think I''ll have to make my own little demo with Metaballs )

If you ask me: metaballs is a different topic. Maybe the solution to this normal problem lies elsewhere, but then again - maybe not!

Hey, why don''t you write a GameDev tutorial on "Smooth surface normal calculation"? Seems like you know your stuff!

It''s hightech to me.

You have my permission to use the superb images on this page!

Anyway, hope to hear from you again...I''ll be back with more...

###
#16
Moderators - Reputation:

There are plenty of guys smarter than me. They are just too smart to hang around here when they could be working on their own game.

Maybe I will write a tutorial on smooth surface normal computations, but I think there are more important ones to be written first. Read my thread "A Direct3D tutorial by WitchLord" and give your suggestions for future tutorials.

- WitchLord

###
#17
Members - Reputation:

I''m sorry but I''ve only done OpenGL and currently my own software rendering. But it looks great - good use of colours - nice links to ms!

How about adding a screenshot of the object you''re creating...?

If you write your future tutorials in a more independant style, you''ve got a 100% of my attention!

By the road, checked out my tutorials? (getting a little old though)

- Backface culling & optimization

- General 3D optimization techniques

- 3D Matrix calculations

- Fullscreen Windows application (Win32 or DirectDraw)

###
#18
Moderators - Reputation:

Screenshot, probably a good idea. I will add this in the future. As these are my first tutorials there are room for alot of improvement and I''m grateful for any tip I can get.

What do you mean with independant style?

PS. I like you homepage, very pleasant design. The tutorials look good as well, even though there wasn''t anything I didn''t already know.

- WitchLord

###
#19
Members - Reputation:

Thanks, and you''re right: it needs some new stuff.

I see we have the same idea''s, when it''s about tutorials.

> "independant style"

I can see this could see said more clearly. How can I say this...I mean platform independant, OpenGL/Direct3D independant. Everybody has it''s own interrest and opinion, but if it''s "independant" everybody will have something from it!

Do I make any sense? Sometimes my English leaves me!

I also saw your new thread

Has anyone seen the tutorial Metaball stuff on Gamasutra?

Maybe I''ll do some more research before restarting metaballs...but will be back...

###
#20
Moderators - Reputation:

My tutorials will be as independant as they can be without talking about anything else than Direct3D. I don''t know enough about OpenGL to really say anything about it. But the 3D theory that I''m planning on writing about for my coming tutorials can be applied to both OpenGL and Direct3D. As I speak about the theory I will show how it is done in Direct3D, but if the reader knows OpenGL he/she should be able to implement it from the theory.

And yes I saw the article on Gamasutra. I haven''t had time to read it though. At a quick glance it looked as if he used ''marching tetraeders'' instead of cubes, which I think is a stupid choice. But it is perhaps easier write about them.

- WitchLord

###
#6
Moderators - Reputation: **4408**

Posted 19 May 2000 - 01:33 PM

Let's say you want to compute the normal for vertex V0 in a triangle V0,V1,V2

You can compute the normal like this:

E1 = V1-V0

E2 = V2-V0

Normal = CrossProduct(E1,E2);

The length of this normal is dependant on the angle between the two edges E1 and E2. And also the length of the edges like this:

LengthOf(Normal) = LengthOf(E1)*LengthOf(E2)*sin(SmallestAngleBetween(E1,E2))

If you add this normal to the vertex directly without normalizing it first you'll almost have what you want. The larger triangles have more influence than than smaller. I suggest that you try this way as I believe it gives an acceptable approximation.

If you want it to be perfect then you need to compute the actual angle between the edges. Which is done with either

angle = asin(LengthOf(Normal)/LengthOf(E1)/LengthOf(E2))

or

angle = acos(DotProduct(E1,E2)/LengthOf(E1)/LenghtOf(E2))

The second is derived from the formula for the dot product:

DotProduct(E1,E2) = LengthOf(E1)*LengthOf(E2)*cos(SmallestAngleBetween(E1,E2))

In either case the determination of the angle requires a lot of computations (as you can see).

Then the normals should be summed together like this:

V0Normal += angle/2/pi*Normalize(Normal);

Does this make me a marching-cube-guru?

- WitchLord

Edited by - WitchLord on May 19, 2000 8:39:44 PM

###
#7
Members - Reputation: **122**

Posted 21 May 2000 - 03:39 AM

--

Float like a butterfly, bite like a crocodile.

Edited by - goltrpoat on May 21, 2000 10:42:00 AM

###
#8
Moderators - Reputation: **4408**

Posted 21 May 2000 - 01:00 PM

But then again I haven''t worked with metaballs myself either so I could be completely wrong.

- WitchLord

###
#9
Members - Reputation: **123**

Posted 21 May 2000 - 01:22 PM

That I didn''t think of it...use the angle to multiply with the normal, add em all and normalize...perfect!

> Does this make me a marching-cube-guru?

Well, If you as me - not a marching-cube-guru -

The solution is to a more trivial problem. (So it''s even better)

You can use this in a lot more of normal calculations!

Never thought anyone could answer this, thanks!

**...Brilliant perfect superb...!!!**

###
#12
Members - Reputation: **123**

Posted 22 May 2000 - 11:05 AM

Implementation of above angle calculation solution is completed but -

*normals are still wrong!!!*

Here''s the next and hopefully last question on perfect normal calculation:

**The size of each poly does also matter!**

Hope to explain more with the following pictures:

"2D images of an metaballs animation"

*the animation starts with a uge red polygon (line in this case)*

*during animation, the red poly shrinks to almost none existing*

Watch the green normals: if the polygon gets smaller -> the normals come closer together and in the end

*are*the same!!!

So, the question is (forget about the angle calculation explained above):

**Is there a formula to calculate the correct normal of a vertex using it''s attached polygon normals, while polygons differ in size?**

Am I right?

Can you just calc the polygon normal (as always) and divide it by the average size of the polygons edges. Then add up all the normals that are attached to a vertex, and normalize?

###
#13
Moderators - Reputation: **4408**

Posted 22 May 2000 - 11:39 AM

NV = w1*N1 + w2*N2 + w3*N3 + ...

Here NV is the vertex normal. N1, N2, and N3 is the normalized triangle normals. w1, w2, and w3 is the weights that are used to average the normals together.

1. If you ignore the size of the triangle and the angle it makes at the vertex, all weights are 1.

2. You can use the angles as weights. This ensure that the vertex normal stays the same if one of the triangles are divided in two at the vertex. Yet it ignore the size of the triangle which is also good if you for example tesselate your triangles so that a triangle is divided into four parts.

3. If you use the size of the triangle as weight, you'll of course get that larger triangles have more influence on the vertex normal. This is not too good if any triangle is divided into parts as the size will then change and the vertex normal will move away from the triangles normal. But then again this may be what you want.

4. Then there is the possibility to use the reciprocity of the triangles area as weight. Then the smaller the triangle is the more influence it will have. This has similar effects as the above.

For your problem I would say that number 4 is what you want. Here you can compute the weight like this:

E1 = V1-V0

E2 = V2-V0

Normal = CrossProduct(E1,E2);

w = Normal.x*Normal.x + Normal.y*Normal.y + Normal.z*Normal.z;

VertexNormal += Normal/w;

You'll of course have to be careful so you don't get divide by zero due to the low precision of floats or doubles.

Give this a try and see if it works better

(Hmm, I think I'll have to make my own little demo with Metaballs )

- WitchLord

Edited by - WitchLord on May 22, 2000 6:40:26 PM

###
#14
Members - Reputation: **123**

Posted 22 May 2000 - 12:25 PM

I first said:

> Can you just calc the polygon normal (as always) and divide it by the average size of the polygons edges. Then add up all the normals that are attached to a vertex, and normalize?

Your version: (see if I''m getting this right)

> Calc the polygon (un-normalized-)normal and divide it by it''s own (un-normalized-)normal length^2. Then add up all the normals that are attached to a vertex, and normalize!

This way small polys weigh more. If a polygon size is nearing zero the weight is nearing infinity...

If the above doesn''t turn out to be the solution, should we be thinking in a sort of interpolation technique between polygons?

Looks like you know what I meant, and it seems right!

Also, your formula is a nice and fast implementation, thanks. In a few minutes/hours I''ll be needing some sleep, but I''ll test it tomorrow.

> (Hmm, I think I''ll have to make my own little demo with Metaballs )

If you ask me: metaballs is a different topic. Maybe the solution to this normal problem lies elsewhere, but then again - maybe not!

Hey, why don''t you write a GameDev tutorial on "Smooth surface normal calculation"? Seems like you know your stuff!

It''s hightech to me.

You have my permission to use the superb images on this page!

Anyway, hope to hear from you again...I''ll be back with more...

###
#16
Moderators - Reputation: **4408**

Posted 22 May 2000 - 09:22 PM

Maybe I will write a tutorial on smooth surface normal computations, but I think there are more important ones to be written first. Read my thread "A Direct3D tutorial by WitchLord" and give your suggestions for future tutorials.

- WitchLord

###
#17
Members - Reputation: **123**

Posted 23 May 2000 - 10:47 AM

How about adding a screenshot of the object you''re creating...?

If you write your future tutorials in a more independant style, you''ve got a 100% of my attention!

By the road, checked out my tutorials? (getting a little old though)

- Backface culling & optimization

- General 3D optimization techniques

- 3D Matrix calculations

- Fullscreen Windows application (Win32 or DirectDraw)

###
#18
Moderators - Reputation: **4408**

Posted 23 May 2000 - 11:06 AM

What do you mean with independant style?

PS. I like you homepage, very pleasant design. The tutorials look good as well, even though there wasn''t anything I didn''t already know.

- WitchLord

###
#19
Members - Reputation: **123**

Posted 24 May 2000 - 08:48 AM

I see we have the same idea''s, when it''s about tutorials.

> "independant style"

I can see this could see said more clearly. How can I say this...I mean platform independant, OpenGL/Direct3D independant. Everybody has it''s own interrest and opinion, but if it''s "independant" everybody will have something from it!

Do I make any sense? Sometimes my English leaves me!

I also saw your new thread

*"A Direct3D Tutorial from WitchLord"*and will be posting tutorial stuff to this thread from now on.

Has anyone seen the tutorial Metaball stuff on Gamasutra?

Maybe I''ll do some more research before restarting metaballs...but will be back...

###
#20
Moderators - Reputation: **4408**

Posted 24 May 2000 - 09:32 AM

And yes I saw the article on Gamasutra. I haven''t had time to read it though. At a quick glance it looked as if he used ''marching tetraeders'' instead of cubes, which I think is a stupid choice. But it is perhaps easier write about them.

- WitchLord