Started by May 18 2000 01:27 PM

,
90 replies to this topic

Posted 24 May 2000 - 09:37 AM

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.

--

Float like a butterfly, bite like a crocodile.

Posted 25 May 2000 - 04:05 AM

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

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

Posted 25 May 2000 - 05:18 AM

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

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

Posted 25 May 2000 - 06:13 AM

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

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

Posted 25 May 2000 - 07:19 AM

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

- WitchLord

Posted 25 May 2000 - 08:01 AM

This is really starting to get interresting. I'll look up your source in a few minutes Hans, it already seems promising.

Here's a few lines I use to calculate the force on my balls (the meta ones):

Edited by - baskuenen on May 25, 2000 3:03:17 PM

Here's a few lines I use to calculate the force on my balls (the meta ones):

ForceGrid[ index ] =

MB_SIZE*MB_SIZE/((x-bx1)*(x-bx1) + (y+by1)*(y+by1) + (z-bz1)*(z-bz1)) +

MB_SIZE*MB_SIZE/((x-bx2)*(x-bx2) + (y+by2)*(y+by2) + (z-bz2)*(z-bz2)) +

MB_SIZE*MB_SIZE/((x-bx3)*(x-bx3) + (y+by3)*(y+by3) + (z-bz3)*(z-bz3)) +

MB_SIZE*MB_SIZE/((x-bx4)*(x-bx4) + (y+by4)*(y+by4) + (z-bz4)*(z-bz4));

Edited by - baskuenen on May 25, 2000 3:03:17 PM

Posted 25 May 2000 - 08:54 AM

So all you''re balls are the same size?

If you want different sized balls, you must do this:

C = center of ball

S = size of ball

V = The vertex who''s normal is to be computed

M = magnitude(V-C)

N = (V-C0)*S0/M0^3 + (V-C1)*S1/M1^3 + (V-C2)*S2/M2^3 + ...

And I calculated my metaballs like:

sqr((x-bx1)*(x-bx1) + (y+by1)*(y+by1) + (z-bz1)*(z-bz1))

but you have only:

(x-bx1)*(x-bx1) + (y+by1)*(y+by1) + (z-bz1)*(z-bz1)

So you''ll need different power that ^3.. I''m not sure what but ^2 felt good when I tested it

Wild quess: maybe now ^1 normalizes the vector and the other ^1 is like (1/2)*2. In the old formula ^1 was normalize and ^2 was (1)*2..

I originally came up with the algo before I even knew what vector is, and I just tested things...

--

MB_SIZE*MB_SIZE

--

But why do you square your balls'' sizes? If you''re going to use that formula above, you shouldn''t sqare the sizes or else you''ll need square root in the formula:

N = (V-C0)*sqr(S0)/M0^2 + (V-C1)*sqr(S1)/M1^2 + (V-C2)*sqr(S2)/M2^2 + ...

-Hans

If you want different sized balls, you must do this:

C = center of ball

S = size of ball

V = The vertex who''s normal is to be computed

M = magnitude(V-C)

N = (V-C0)*S0/M0^3 + (V-C1)*S1/M1^3 + (V-C2)*S2/M2^3 + ...

And I calculated my metaballs like:

sqr((x-bx1)*(x-bx1) + (y+by1)*(y+by1) + (z-bz1)*(z-bz1))

but you have only:

(x-bx1)*(x-bx1) + (y+by1)*(y+by1) + (z-bz1)*(z-bz1)

So you''ll need different power that ^3.. I''m not sure what but ^2 felt good when I tested it

Wild quess: maybe now ^1 normalizes the vector and the other ^1 is like (1/2)*2. In the old formula ^1 was normalize and ^2 was (1)*2..

I originally came up with the algo before I even knew what vector is, and I just tested things...

--

MB_SIZE*MB_SIZE

--

But why do you square your balls'' sizes? If you''re going to use that formula above, you shouldn''t sqare the sizes or else you''ll need square root in the formula:

N = (V-C0)*sqr(S0)/M0^2 + (V-C1)*sqr(S1)/M1^2 + (V-C2)*sqr(S2)/M2^2 + ...

-Hans

Posted 25 May 2000 - 10:05 AM

I''m still looking through the overload of recent info.

Meanwhile I noticed the folowing:

Can''t Sqrt(x)^3 be described as x^2 ?

So after some radical algo optimizations:

N = 1/(V-C0) + 1/(V-C1) + 1/(V-C2) + ...

Am I getting this right?

If you want to use different sizes you get:

N = MB_SIZE/(V-C0) + MB_SIZE/(V-C1) + MB_SIZE/(V-C2) + ...

Please correct me if I''m wrong...

Meanwhile I noticed the folowing:

Can''t Sqrt(x)^3 be described as x^2 ?

So after some radical algo optimizations:

N = 1/(V-C0) + 1/(V-C1) + 1/(V-C2) + ...

Am I getting this right?

If you want to use different sizes you get:

N = MB_SIZE/(V-C0) + MB_SIZE/(V-C1) + MB_SIZE/(V-C2) + ...

Please correct me if I''m wrong...

Posted 25 May 2000 - 10:28 AM

>Can''t Sqrt(x)^3 be described as x^2 ?

No, sqrt(x)=x^(1/2)

And so x^(1/2)^3=x^(3/2)=x^1.5, not x^2

Sqrt(x)^4=x^2.

But since you should use:

N = (V-C0)*S0/M0^2 + (V-C1)*S1/M1^2 + (V-C2)*S2/M2^2 + ...

And M = sqr((x-x0)^2+(y-y0)^2)

M^2=(x-x0)^2+(y-y0)^2 , which is quite fast to calculate and you don''t need sqrt() at all.

(and we''re back at the form that WitchLord suggested earlier)

Whether it is M^2 or M^3 depends on how you calculate the metaballs. (but you, baskuenen, should use M^2 because you don''t use sqr to calculate metaballs'' forces, read my earlier posts)

-Hans

No, sqrt(x)=x^(1/2)

And so x^(1/2)^3=x^(3/2)=x^1.5, not x^2

Sqrt(x)^4=x^2.

But since you should use:

N = (V-C0)*S0/M0^2 + (V-C1)*S1/M1^2 + (V-C2)*S2/M2^2 + ...

And M = sqr((x-x0)^2+(y-y0)^2)

M^2=(x-x0)^2+(y-y0)^2 , which is quite fast to calculate and you don''t need sqrt() at all.

(and we''re back at the form that WitchLord suggested earlier)

Whether it is M^2 or M^3 depends on how you calculate the metaballs. (but you, baskuenen, should use M^2 because you don''t use sqr to calculate metaballs'' forces, read my earlier posts)

-Hans

Posted 25 May 2000 - 10:42 AM

Me = little bit stupid sometimes. You''re right! Optimized my amount of braincells a bit too much...

Good thing there are some sober people around!

*But we optimized it!*

Optimization is real important in my case, because I''m writing a software rendered runtime 3D animation of the metaballs. It''s still too slow (~20 FPS on PIII-450).

But you made a good point with metaball normal calculation.

- There is a better way -

(Although the "smooth surface normal calculation" topic was getting real interresting!)

I''m still implementing...hope it''ll work...

Thanks Hans and all of you guys!

Good thing there are some sober people around!

Optimization is real important in my case, because I''m writing a software rendered runtime 3D animation of the metaballs. It''s still too slow (~20 FPS on PIII-450).

But you made a good point with metaball normal calculation.

- There is a better way -

(Although the "smooth surface normal calculation" topic was getting real interresting!)

I''m still implementing...hope it''ll work...

Thanks Hans and all of you guys!

Posted 25 May 2000 - 11:50 AM

I see that I''m not needed here anymore.

I was inspired by this discussion so I sat down to make my own Metaballs, 2 hours later it was working (I stripped an old program I had for marching cubes). After some tweaking with the numbers I actually managed to get them to look good as well. As of yet the code is totally unoptimized though so the performance is truly poor: 8.7 fps on a Celeron 500 with GeForce. (Impressive isn''t it )

- WitchLord

I was inspired by this discussion so I sat down to make my own Metaballs, 2 hours later it was working (I stripped an old program I had for marching cubes). After some tweaking with the numbers I actually managed to get them to look good as well. As of yet the code is totally unoptimized though so the performance is truly poor: 8.7 fps on a Celeron 500 with GeForce. (Impressive isn''t it )

- WitchLord

Posted 25 May 2000 - 02:22 PM

Did you really think you could get away with it that easy?

We are not done yet! At the moment my surface is smooth, and the phong is shining brightly, but it''s still not right!

This thread is finished when I say so

and only when an image of perfect metaballs is posted!

...

We are not done yet! At the moment my surface is smooth, and the phong is shining brightly, but it''s still not right!

This thread is finished when I say so

and only when an image of perfect metaballs is posted!

...

Posted 25 May 2000 - 04:09 PM

Fine by me

Now that I have gotten my metaballs to run at a steady rate of 105fps with perfect smoothness (at least as perfect as it gets with low detail) I'm willing to give you a hand again.

You might wonder how I managed to optimize from 8.7 fps to 105 fps. Well the biggest change I did was that I no longer compute the field energy if there are no balls in close proximity. This got the fps up to a steady 32 fps (367% increase). The second optimization I made was that I switched to release build, and voila 105 fps (328% increase).

Here's a screenshot of my metaballs:

(Image no longer available)

For the sake of this screenshot I increased the density of the energy field to 64*64*64 from 32*32*32 (lowered fps to 14)

- WitchLord

Edited by - WitchLord on May 25, 2000 11:25:48 PM

Edited by - WitchLord on May 26, 2000 11:45:35 PM

Now that I have gotten my metaballs to run at a steady rate of 105fps with perfect smoothness (at least as perfect as it gets with low detail) I'm willing to give you a hand again.

You might wonder how I managed to optimize from 8.7 fps to 105 fps. Well the biggest change I did was that I no longer compute the field energy if there are no balls in close proximity. This got the fps up to a steady 32 fps (367% increase). The second optimization I made was that I switched to release build, and voila 105 fps (328% increase).

Here's a screenshot of my metaballs:

(Image no longer available)

For the sake of this screenshot I increased the density of the energy field to 64*64*64 from 32*32*32 (lowered fps to 14)

- WitchLord

Edited by - WitchLord on May 25, 2000 11:25:48 PM

Edited by - WitchLord on May 26, 2000 11:45:35 PM

Posted 25 May 2000 - 09:29 PM

DAMN! that looks good!

Can you post that program?

========================

Game project(s):

www.fiend.cjb.net

Can you post that program?

========================

Game project(s):

www.fiend.cjb.net

Posted 25 May 2000 - 10:22 PM

Pretty please?

Ok, im not gonna crawl... (not until ive seen what the program can do anyways =)

========================

Game project(s):

www.fiend.cjb.net

Ok, im not gonna crawl... (not until ive seen what the program can do anyways =)

========================

Game project(s):

www.fiend.cjb.net

Posted 26 May 2000 - 01:47 AM

Thanx!

========================

Game project(s):

www.fiend.cjb.net

========================

Game project(s):

www.fiend.cjb.net

Posted 26 May 2000 - 03:44 AM

Hey WitchLord or baskuenen, can you tell me where to find a tutorial on marching cubes? I tried to find one once, but all I found was blaahblaah and that it''s a patented algorithm (?).

-Hans

-Hans

Posted 26 May 2000 - 06:25 AM

We have given a few pointers in this thread: Metaballs - Where to start?

You may also check the source for my metaballs, it''s really well commented in my own humble opinion.

- WitchLord

You may also check the source for my metaballs, it''s really well commented in my own humble opinion.

- WitchLord