#### Archived

This topic is now archived and is closed to further replies.

# Metaballs - Normals

This topic is 5273 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

At the moment I''m using the polygon normals to calc the vertex normals. If you look close enough you''ll notice the mapping isn''t perfect. Does anyone know how to calculate the vertex normals on these metaballs?

##### Share on other sites
Maybe this''ll help:
I''m using the marching cubes algorithm...

Any comment links or whatever is respected...

##### Share on other sites
During the calculations of the triangles with marching cubes, you should add the normal of each triangle to the used vertex normals. When all triangles has been defined the normals are normalized. (If you use OpenGL or Direct3D the API can do the normalization for you, probably faster than you yourself can do it.)

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

##### Share on other sites
First of all, thanks for your response WitchLord!

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...

##### Share on other sites
Any marching-cube-guru''s around?

##### Share on other sites
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

##### Share on other sites
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

##### Share on other sites
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

##### Share on other sites
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! ...Brilliant perfect superb...!!!

##### Share on other sites
Why, thank you!

I can''t take credit for the solution though as I read it somewhere. I just can''t remember where.

- WitchLord

##### Share on other sites
Before I forget my thanks also go out to you goltrpoat!

But goltrpoat, this may look like a stupid question, but because of my bad English - can you explain what you mean in more simple words?

##### Share on other sites
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 - 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?

##### Share on other sites
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

##### Share on other sites
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...

##### Share on other sites
After you stopped laughing from the previous joke (I know: wasn''t that good),

Is there a Smooth-Surface-Normal-Calculation-Guru around?

(Maybe nobody is smarter than WitchLord?)

##### Share on other sites
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

##### Share on other sites
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!

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)

##### Share on other sites
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

##### Share on other sites
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 "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...

##### Share on other sites
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

##### Share on other sites
bas: what i meant is this.. if you remember your calculus, the first derivative of a function defines the vector tangent to the function at a given point. in other words, if a surface is defined as A(s,t) then the partial derivatives of A, A''s and A''t define the plane tangent to the surface at (s,t). taking the cross product of the partial derivatives results in the normal vector at (s,t), i.e. nA(s,t) = A''s x A''t. this is pretty standard in parametric surfaces such as bezier surfaces, NURBS, etc.

--
Float like a butterfly, bite like a crocodile.

##### Share on other sites
I'm not sure if any real metaball-angle-calculation-formula has been here yet.

I once made a program that calculates the real angle in a metaball system for single point. It's only 2d but it's very easy to implement to 3d also.

And this is the only _real_ way to calculate vertex normals (the original question).

If you're intrested in how it works, check out my mighty qbasic (!!) demonstratin program (& source of course)

http://www.kolumbus.fi/hannes.k/TESMI.BAS

I don't want to explain it here but it's quite basic vector calculus though. And the program is quite old so don't ask if it looks odd

-Hans

Edited by - Hans on May 25, 2000 11:13:16 AM

##### Share on other sites
Hi Hans!

How much computations does it require to compute the normal the way you do it? I could figure it out myself but if you already know the answer...

The way I do it above requires about four (educated guess) crossproducts per normal. Is it faster to do it your way?

After a quick glance at the source for your program it seems that you compute the normals like this:

V : The vertex who's normal is to be computed
C : The center of a metaball
Sq = SquareMagnitude(V-C)

N = (V-C0)/Sq0 + (V-C1)/Sq1 + (V-C2)/Sq2 + ...

That seems to be logical. Baskuenen you should probably try this. If it works it will improve your performance alot

- WitchLord

Edited by - WitchLord on May 25, 2000 12:26:51 PM

##### Share on other sites
Of course it works

But

N = (V-C0)/Sq0 + (V-C1)/Sq1 + (V-C2)/Sq2 + ...

needs to be

M = magnitude(V-C)
N = (V-C0)/M0^3 + (V-C1)/M1^3 + (V-C2)/M2^3 + ...

I don't know why it must be power 3 but I was trying different powers and noticed that power 3 is the correct one (whoops the BAS code has ^2.5.. well it should be ^3). So I haven't proven the formula mathematically, but if someone can, I'll be happy to hear.

-Hans

Edited by - Hans on May 25, 2000 1:17:34 PM

##### Share on other sites
Well, the first power is to normalize the vector to unit length. The two other powers is to compensate for the metaballs'' dropoff in energy with distance. As I have never made any metaballs I assumed that the dropoff was linear but it might be better if it is proportional to the square distance.

- WitchLord