Started by May 18 2000 01:27 PM

,
90 replies to this topic

Posted 26 May 2000 - 07:10 AM

Yes, I've done it!

If you look up the previous piece of code I posted, you'll see - with x&z's and + with the y's.

I also saw it: very late . This was my problem with the implementation of the new metaball normals!!!

So I've done it, but still running 20FPS (100% software rendered).

Here's the screenshot:

Here's the demo: 3ddemo_metaballs.zip

(ps: Also improved my homepage a little)

Edited by - baskuenen on May 26, 2000 2:12:07 PM

If you look up the previous piece of code I posted, you'll see - with x&z's and + with the y's.

I also saw it: very late . This was my problem with the implementation of the new metaball normals!!!

So I've done it, but still running 20FPS (100% software rendered).

Here's the screenshot:

Here's the demo: 3ddemo_metaballs.zip

(ps: Also improved my homepage a little)

Edited by - baskuenen on May 26, 2000 2:12:07 PM

Posted 26 May 2000 - 07:15 AM

Here''s another metaball tutorial: http://www.exaflop.org/docs/marchcubes/ind.html

Posted 26 May 2000 - 07:37 AM

Your metaballs are a whole lot more impressive than mine.

20fps in software mode, I think you should be proud of that. Have you tried the optimizations that I did?

What size do you use for you energy field? In my current version I use 48*48*48.

Could the smooth specular highlights be the result of Phong lighting? I had to turn off specular lighting on my balls because they looked horrible.

- WitchLord

20fps in software mode, I think you should be proud of that. Have you tried the optimizations that I did?

What size do you use for you energy field? In my current version I use 48*48*48.

Could the smooth specular highlights be the result of Phong lighting? I had to turn off specular lighting on my balls because they looked horrible.

- WitchLord

Posted 26 May 2000 - 10:42 AM

Thanks,

I haven''t optimized the force grid yet. I was thinking about it, but have not come up a solid algo for this...I''m really interrested in your optimizations!

I must admit I''m using a 32*32*32 grid only.

And yes, I managed to implement a fast phong mapping algo. (It''s no OpenGL or DirectX - so you can cheat a little with this)

I like - you like it! You answering all my questions, and I never could answer yours, was starting to bug me.

I always said to myself: If you can do metaballs, you''re really good! Now I can do metaballs, and I feel good. If you can do metaballs like WitchLord or Hans: You''re also a superb programmer! Guru is the name here!

I''m just home - back from the cafe (burph) - Need some liquid now...

I haven''t optimized the force grid yet. I was thinking about it, but have not come up a solid algo for this...I''m really interrested in your optimizations!

I must admit I''m using a 32*32*32 grid only.

And yes, I managed to implement a fast phong mapping algo. (It''s no OpenGL or DirectX - so you can cheat a little with this)

I like - you like it! You answering all my questions, and I never could answer yours, was starting to bug me.

I always said to myself: If you can do metaballs, you''re really good! Now I can do metaballs, and I feel good. If you can do metaballs like WitchLord or Hans: You''re also a superb programmer! Guru is the name here!

I''m just home - back from the cafe (burph) - Need some liquid now...

Posted 26 May 2000 - 11:33 AM

Well, I only made a simple optimization, yet the performance was increased by 367%.

What we must recognize here is that the only energy values that are needed are those that are really close to the surface of the balls. In my optimization I don''t compute the values that are too far away from any of the balls. It can maybe be optimized further by not computing the values that are inside the balls as well.

Anyway you can see my optimization in the source code, it is really simple so you shouldn''t have any trouble implementing it in your own code.

- WitchLord

What we must recognize here is that the only energy values that are needed are those that are really close to the surface of the balls. In my optimization I don''t compute the values that are too far away from any of the balls. It can maybe be optimized further by not computing the values that are inside the balls as well.

Anyway you can see my optimization in the source code, it is really simple so you shouldn''t have any trouble implementing it in your own code.

- WitchLord

Posted 26 May 2000 - 01:43 PM

WitchLord:

While looking through your code I noticed it looks simple and clean. Mine still is a bit messy with lots a pointers and stuff.

I''m not re-normalizing the added normals. Is this really needed? It will improve performance a bit.

Is there a precise threshold value for the energy field optimization?

While looking through your code I noticed it looks simple and clean. Mine still is a bit messy with lots a pointers and stuff.

I''m not re-normalizing the added normals. Is this really needed? It will improve performance a bit.

Is there a precise threshold value for the energy field optimization?

Posted 26 May 2000 - 01:48 PM

Just for the record: Here''s my metaball vertex normal calculation source:

void __fastcall CalcVertexNormal(PVERTEX pVertex)

{

float x = pVertex->x;

float y = pVertex->y;

float z = pVertex->z;

float dx1 = (x-tx1);

float dx2 = (x-tx2);

float dx3 = (x-tx3);

float dx4 = (x-tx4);

float dy1 = (y-ty1);

float dy2 = (y-ty2);

float dy3 = (y-ty3);

float dy4 = (y-ty4);

float dz1 = (z-tz1);

float dz2 = (z-tz2);

float dz3 = (z-tz3);

float dz4 = (z-tz4);

float n1 = dx1*dx1 + dy1*dy1 + dz1*dz1;

float n2 = dx2*dx2 + dy2*dy2 + dz2*dz2;

float n3 = dx3*dx3 + dy3*dy3 + dz3*dz3;

float n4 = dx4*dx4 + dy4*dy4 + dz4*dz4;

n1 = MB_SIZE*MB_SIZE / (sqrt(n1) * n1);

n2 = MB_SIZE*MB_SIZE / (sqrt(n2) * n2);

n3 = MB_SIZE*MB_SIZE / (sqrt(n3) * n3);

n4 = MB_SIZE*MB_SIZE / (sqrt(n4) * n4);

pVertex->nx = dx1*n1 + dx2*n2 + dx3*n3 + dx4*n4;

pVertex->ny = dy1*n1 + dy2*n2 + dy3*n3 + dy4*n4;

pVertex->nz = dz1*n1 + dz2*n2 + dz3*n3 + dz4*n4;

}

Posted 26 May 2000 - 02:10 PM

Normalization of the normals are only needed if your lighting code requires it. For both OpenGL and Direct3D the

normals must be unit length, otherwise you''ll get strange lightvalues. If you try normalizing the normals, you''ll see that it doesn''t make a lot of difference to the performance.

I noticed that you have an extra step when computing your normals:

n1 = MB_SIZE*MB_SIZE / (sqrt(n1) * n1);

Is this necessary? Does it give you better appearance of the lighting?

The threshold I use in my optimizations is the distance from the center to the surface if all balls was on the same spot.

- WitchLord

normals must be unit length, otherwise you''ll get strange lightvalues. If you try normalizing the normals, you''ll see that it doesn''t make a lot of difference to the performance.

I noticed that you have an extra step when computing your normals:

n1 = MB_SIZE*MB_SIZE / (sqrt(n1) * n1);

Is this necessary? Does it give you better appearance of the lighting?

The threshold I use in my optimizations is the distance from the center to the surface if all balls was on the same spot.

- WitchLord

Posted 26 May 2000 - 02:26 PM

Well I tried adding that step in the normal computations myself and it does look better. I also tried with this:

n1 = MB_SIZE*MB_SIZE / (n1 * n1);

And that does also look right. So which is it? I''ll have to do some testing, I''ll add some user interactivity to my program so that I can do some tests.

- WitchLord

n1 = MB_SIZE*MB_SIZE / (n1 * n1);

And that does also look right. So which is it? I''ll have to do some testing, I''ll add some user interactivity to my program so that I can do some tests.

- WitchLord

Posted 26 May 2000 - 02:35 PM

I''m using this extra step for some optimization.

I''m using floating point:

- FDIV costs 17 instructions

- FMUL costs 3 instructions

This is not entirely right, because floating point functions can be interleaved with integer functions, but thats not the case in this function.

If you are going to divide multiple numbers by the same value, it''s better to divide once, and then multiply the rest! If optimized in assembly the FMUL''s clock count could be reduced to 1, and can interleave each other! (the FDIV''s cannot) But that''s all another topic, and you probably knew most of it.

So the extra step is for optimization only.

> The threshold I use in my optimizations is the distance from the center to the surface if all balls was on the same spot.

Good point, that''s the threshold!

Then: If you want the minimal value for a metaball optimization:*use the distance from the center to the surface if just one ball.*

I''m using floating point:

- FDIV costs 17 instructions

- FMUL costs 3 instructions

This is not entirely right, because floating point functions can be interleaved with integer functions, but thats not the case in this function.

If you are going to divide multiple numbers by the same value, it''s better to divide once, and then multiply the rest! If optimized in assembly the FMUL''s clock count could be reduced to 1, and can interleave each other! (the FDIV''s cannot) But that''s all another topic, and you probably knew most of it.

So the extra step is for optimization only.

> The threshold I use in my optimizations is the distance from the center to the surface if all balls was on the same spot.

Good point, that''s the threshold!

Then: If you want the minimal value for a metaball optimization:

Posted 26 May 2000 - 03:42 PM

That would probably work.

The problem comes when you introduce anti-metaballs that subtract energy. But my guess is that there would be a whole lot other issues to solve as well if such where to be added.

The extra step I referred to was not that you pre-divided the normal magnitude. It was that you used a higher power than I did, which looks better. I''m now trying to figure out the exact power to use when computing the normals.

- WitchLord

The problem comes when you introduce anti-metaballs that subtract energy. But my guess is that there would be a whole lot other issues to solve as well if such where to be added.

The extra step I referred to was not that you pre-divided the normal magnitude. It was that you used a higher power than I did, which looks better. I''m now trying to figure out the exact power to use when computing the normals.

- WitchLord

Posted 26 May 2000 - 04:55 PM

To calc the energy from 1 ball I use: (And add forces for more balls)

To calc the normal I use: (Add normals for more balls)

Hope I''ve got it correct, and hope it helps,

Bas.

(ps: Can''t run your demo! Get an error about "DDRAW.DLL: DirectDrawCreateEx". I have no 3D card. Do I need to upgrade my DirectX 6.1 version first?)

rr = (x-tx1)*(x-tx1) + (y-ty1)*(y-ty1) + (z-tz1)*(z-tz1);

Force = MB_SIZE*MB_SIZE/rr;

To calc the normal I use: (Add normals for more balls)

n = MB_SIZE*MB_SIZE / (sqrt(rr) * rr);

pVertex->nx = (x-ballx)*n;

pVertex->ny = (y-bally)*n;

pVertex->nz = (z-ballz)*n;

Hope I''ve got it correct, and hope it helps,

Bas.

(ps: Can''t run your demo! Get an error about "DDRAW.DLL: DirectDrawCreateEx". I have no 3D card. Do I need to upgrade my DirectX 6.1 version first?)

Posted 26 May 2000 - 04:59 PM

I''ve been tweaking my program a little, here''s a new screenshot:

I have changed the normal computation for my program so that it is now done like this:

I couldn''t see much difference between using

m = SQRADIUS / (m*m);

and

m = SQRADIUS / (sqrt(m)*m);

so I decided to use the one that was faster. Though no performance difference was visible.

I''ll be uploading the new program to my site later today.

- WitchLord

I have changed the normal computation for my program so that it is now done like this:

inline D3DVECTOR CMetaBallApp::Normal(D3DVECTOR &Pos)

{

D3DVECTOR N = D3DVECTOR(0,0,0);

for( int i = 0; i < m_nNumBalls; i ++ )

{

D3DVECTOR v = Pos - m_Balls;

float m = SquareMagnitude(v);

m = SQRADIUS / (m*m);

N += v*m;

}

return Normalize(N);

}

I couldn''t see much difference between using

m = SQRADIUS / (m*m);

and

m = SQRADIUS / (sqrt(m)*m);

so I decided to use the one that was faster. Though no performance difference was visible.

I''ll be uploading the new program to my site later today.

- WitchLord

Posted 26 May 2000 - 05:15 PM

You''re almost making the same mistake I made (page 2, post 3), but I must say: Looks great! Can''t see the difference!

But after lozing the sqrt from this part you probably have to normalize, and the sqrt is back.

I think the sqrt() is there to make the vector (CenterBall to CurrentVertex) of unit length 1.

What do you get if you use the sqrt() and drop normalization?

Your metaballs look great, all 5! of them.

But after lozing the sqrt from this part you probably have to normalize, and the sqrt is back.

I think the sqrt() is there to make the vector (CenterBall to CurrentVertex) of unit length 1.

What do you get if you use the sqrt() and drop normalization?

Your metaballs look great, all 5! of them.

Posted 26 May 2000 - 05:33 PM

If you want Phong mapping:

- Use a phong map (texture)

- Do environment mapping (use the x & y part of the vertex normals as texture coords)

Here's a PhongMap/Texture:

You can also add a picture-texture by:

- Use the PhongMap as a lightmap orso??? I have never done this with OpenGL or Direct3D, is this possible?

- Mixing it with the phong map. (But then you will not be able to rotate around it) (this would increase the speed of my software engine greatly, but the total engine isn't based on this, and after optimizing this will not support other models...but good idea for you!)

The disadvantage you have with phongmapping is: Your light must come out of the camera, in the Z direction.

Well, you don't have to, but then there's also a light spot on the other side (real ugly).

(ps: We're now in the 25 hottest topics of all time)

Edited by - baskuenen on May 26, 2000 12:35:17 AM

- Use a phong map (texture)

- Do environment mapping (use the x & y part of the vertex normals as texture coords)

Here's a PhongMap/Texture:

You can also add a picture-texture by:

- Use the PhongMap as a lightmap orso??? I have never done this with OpenGL or Direct3D, is this possible?

- Mixing it with the phong map. (But then you will not be able to rotate around it) (this would increase the speed of my software engine greatly, but the total engine isn't based on this, and after optimizing this will not support other models...but good idea for you!)

The disadvantage you have with phongmapping is: Your light must come out of the camera, in the Z direction.

Well, you don't have to, but then there's also a light spot on the other side (real ugly).

(ps: We're now in the 25 hottest topics of all time)

Edited by - baskuenen on May 26, 2000 12:35:17 AM

Posted 26 May 2000 - 06:48 PM

You're right, I did some refurnishing in my functions and now everything looks much logical. Here's what they look like:

Can you see the similarities?

And I tried to drop the normalization of the normal after the summation but that doesn't work, the lighting gets all screwed. It's actually quite easy to see that it must be normalized. Think about what happens when you have two balls and you take a point exactly between them, then the normal will have zero length. If you move just a little bit away from this spot the normal will be small but it can be normalized to give a unitlength direction.

During this testing I also tested to change the energy function so that it has linear falloff. It still produces metaballs, but they have slightly different properties; They grow a lot more when they are close to each other.

nVidia has some cool demos and papers on how to go about to create phong mapping with specular highlights with OGL and D3D. I had initially planned to implement that and cub environmentmapping on my metaballs, but now I think that I should go back to writing my game instead. Maybe I'll dig up my metaballs again later and add some cool effects to them.

It's been fun.

- WitchLord

Edited by - WitchLord on May 27, 2000 1:50:04 AM

inline float CMetaBallApp::Energy(D3DVECTOR &Pos)

{

float e = 0;

for( int i = 0; i < m_nNumBalls; i++ )

{

float SqDistance = SquareMagnitude(Pos - m_Balls[ i ]);

e += SQRADIUS / SqDistance;

}

return e;

}

inline D3DVECTOR CMetaBallApp::Normal(D3DVECTOR &Pos)

{

D3DVECTOR N = D3DVECTOR(0,0,0);

for( int i = 0; i < m_nNumBalls; i ++ )

{

D3DVECTOR v = Pos - m_Balls[ i ];

float SqDistance = SquareMagnitude(v);

v /= (float)sqrt(SqDistance); // Normalize the vector

// We should scale this vector so that the contribution from this

// metaball is inversely proportional to the square distance, because

// the energy from it is also inversely proportional to the square

// distance.

N += (SQRADIUS / SqDistance)*v;

}

return Normalize(N);

}

Can you see the similarities?

And I tried to drop the normalization of the normal after the summation but that doesn't work, the lighting gets all screwed. It's actually quite easy to see that it must be normalized. Think about what happens when you have two balls and you take a point exactly between them, then the normal will have zero length. If you move just a little bit away from this spot the normal will be small but it can be normalized to give a unitlength direction.

During this testing I also tested to change the energy function so that it has linear falloff. It still produces metaballs, but they have slightly different properties; They grow a lot more when they are close to each other.

nVidia has some cool demos and papers on how to go about to create phong mapping with specular highlights with OGL and D3D. I had initially planned to implement that and cub environmentmapping on my metaballs, but now I think that I should go back to writing my game instead. Maybe I'll dig up my metaballs again later and add some cool effects to them.

It's been fun.

- WitchLord

Edited by - WitchLord on May 27, 2000 1:50:04 AM

Posted 26 May 2000 - 08:00 PM

--quote baskuenen--

n = MB_SIZE*MB_SIZE / (sqrt(rr) * rr);

--

This:

n = MB_SIZE*MB_SIZE / (sqrt(rr) * rr);

Should be:

n = MB_SIZE*MB_SIZE / (rr * rr);

If you're using "force+=radius/distance;" (not square distance), then the "n = MB_SIZE / (sqrt(rr) * rr);" is correct.

I still don't get why you have MB_SIZE*MB_SIZE and not only MB_SIZE...

Howeved I downloaded your metaballs demo and it looks good!

-Hans

Edited by - Hans on May 27, 2000 3:07:51 AM

n = MB_SIZE*MB_SIZE / (sqrt(rr) * rr);

--

This:

n = MB_SIZE*MB_SIZE / (sqrt(rr) * rr);

Should be:

n = MB_SIZE*MB_SIZE / (rr * rr);

If you're using "force+=radius/distance;" (not square distance), then the "n = MB_SIZE / (sqrt(rr) * rr);" is correct.

I still don't get why you have MB_SIZE*MB_SIZE and not only MB_SIZE...

Howeved I downloaded your metaballs demo and it looks good!

-Hans

Edited by - Hans on May 27, 2000 3:07:51 AM

Posted 27 May 2000 - 06:26 AM

Even though I haven''t had the energy to sit down and prove my theory with maths, I believe you are wrong, Hans. Both the normal and force computations should be the same:

P: Point to be computed

C: Center of metaball

v = P - C;

r = Magnitude(v);

n = radius/r;

force += n;

normal += n*v/r;

or

v = P - C;

rr = SquareMagnitude(v);

n = sqradius/rr;

force += n;

normal += n*v/sqrt(rr);

---

baskuenen, when I tried your program it desided to use 16 bit mode because my GeForce 256 don''t support 24 bit mode. Perhaps you should implement you engine to support 32 bit also.

- WitchLord

P: Point to be computed

C: Center of metaball

v = P - C;

r = Magnitude(v);

n = radius/r;

force += n;

normal += n*v/r;

or

v = P - C;

rr = SquareMagnitude(v);

n = sqradius/rr;

force += n;

normal += n*v/sqrt(rr);

---

baskuenen, when I tried your program it desided to use 16 bit mode because my GeForce 256 don''t support 24 bit mode. Perhaps you should implement you engine to support 32 bit also.

- WitchLord

Posted 27 May 2000 - 09:01 AM

I''ve now tried it without the sqrt(), and it looks a bit sharper. Also it''s faster (not noticeable though).

The phong spot looks a bit better this way, but the sharp edges between the balls are a bit too sharp.

Here''s a new screenshot:

Download of new version: 3ddemo_metaballs2.zip

The use of sqrt() or not is getting a bit confusing to me. I can understand the math using sqrt(), but it makes no sense to me if I lose the sqrt().

Hans: why lose the sqrt? It''s used to make the normal in the calculation of unit length 1, before dividing it with the force from that single ball. (But in practice it almost seems right to lose the sqrt!)

Good idea, the 32bit color depth support...will do that.

The phong spot looks a bit better this way, but the sharp edges between the balls are a bit too sharp.

Here''s a new screenshot:

Download of new version: 3ddemo_metaballs2.zip

The use of sqrt() or not is getting a bit confusing to me. I can understand the math using sqrt(), but it makes no sense to me if I lose the sqrt().

Hans: why lose the sqrt? It''s used to make the normal in the calculation of unit length 1, before dividing it with the force from that single ball. (But in practice it almost seems right to lose the sqrt!)

Good idea, the 32bit color depth support...will do that.

Posted 27 May 2000 - 09:11 AM

What would be a good idea for implementing metaballs into a game? Another remake of tetris, but this time with blobby objects, seems a little boring!

It could be a nice way to have an animated man running around. Although texturing this would be quite hard.

Maybe this question is a little of the topic: Imagine a running man; How do I calculate the anim paths for this? (the metaball coords in this case). Can a few simple sin & cos be enough, or is human movement more complex?

I can imagine setting up a tree...

Edited by - baskuenen on May 27, 2000 4:12:37 PM

It could be a nice way to have an animated man running around. Although texturing this would be quite hard.

Maybe this question is a little of the topic: Imagine a running man; How do I calculate the anim paths for this? (the metaball coords in this case). Can a few simple sin & cos be enough, or is human movement more complex?

I can imagine setting up a tree...

Edited by - baskuenen on May 27, 2000 4:12:37 PM