Archived

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

Xeno

Normals for Metaballs

Recommended Posts

hi , im implemting a metaballs demo using the marching cubes algorithm, anyway , im wondering how to calculate the normal at each vertex on the polygonized scalar filed... im creating the scalar filed using the function 1/(R^2), while as you guess:

R^2 = x^2 + y^2 + z^2 what i thought about is to find the gradient function of the above one , so what i did is:

f(x,y,z) = 1/(x^2 + y^2 + z^2) (u/v)'' = (uv'' - u''v)/(v^2) for X: f(x,y,z)'' = [-(x^2)'' - (y^2)'' - (z^2)'']/[(x^2 + y^2 + z^2)^2] Y and Z are constants so: f(x,y,z)'' = (-2x)/[(x^2 + y^2 + z^2)^2] = -2x / (R^4) we will get the same for Y and Z: for y: -2y / (R^4) for z: -2z / (R^4) so from that i can say the the tangent vector of f(x,y,z) = 1/(x^2 + y^2 + z^2) is: (-2x / (R^4),-2y / (R^4),-2z / (R^4))

the problem is... how do i get the normal vector from the tangent vector at each vertex? Thanks in advance.

Share this post


Link to post
Share on other sites
If you have two non-coincident tangent lines at a point then their cross product is your normal. Those tangent lines need not be expressed as constant vectors but can instead be vector equations. The vector equation for the normal is then the cross product of those vector equations.

Share this post


Link to post
Share on other sites
>so from that i can say the the tangent vector of
>f(x,y,z) = 1/(x^2 + y^2 + z^2) is:
>(-2x / (R^4),-2y / (R^4),-2z / (R^4))
>the problem is... how do i get the normal vector from the >tangent vector at each vertex?

You seem to have a misconception.

The thing you call "tangent vector" is actually the normal vector. It is not a tangent vector. In a scalar field, the gradient vector is equal to the normal vector (or its direction is). Just normalize it and plug it into your 3d engine...

>If you have two non-coincident tangent lines at a point then >their cross product is your normal. Those tangent lines need >not be expressed as constant vectors but can instead be vector >equations. The vector equation for the normal is then the cross >product of those vector equations.

This is true, but sounds more like an answer to the problem of finding normals of a parametric surface instead of an implicit surface.

- Mikko Kauppila

Share this post


Link to post
Share on other sites
ok thanks for the replay... it seems to be actually the normals coz it works.

but i still dont understand what make me get the normal vector instead of the tnagent vector for the first derivative in an implicit surface... i would be greatful if someone can expline me that.

Share this post


Link to post
Share on other sites
You might want to take a look at my reply on your same question in another section but to repeat it here:

What you want to draw is an isolevel of f(x); the surface on which f(x) has a certain constant value c. The gradient gives you the direction in which the slope of f(x) is maximum. This direction is perpendicular to the direction that has a slope of zero.

Share this post


Link to post
Share on other sites
Atheist: thanks for the replays... i read wha you write in the other forum too... although i still prefer to calculate the normals in that way... coz i still have to do some optimization which is more important.

and if we talking about optimizations... my metaballs are very slow. im using the marching cubes with tetrahedrons algorithm to render them. my algorithm runs in O(n^3) which is very slow... coz i have to scan the whole scalar filed each frame to polygonize my filed... is there any way to make it faster? some known optimizations?

Share this post


Link to post
Share on other sites
1)
A friend of mine was trying this (we are both using square cubes):

he added a boolean to each cube (or maybe even each gridpoint; not sure about that now) to check if that cube has already been calculated. Then he starts in the middle going outwards until he hits a cube that is cut by your surface. From there on he starts calculating the neighbouring cubes (if they haven´t already been calculated). This way you only calculate those cubes that are cut by the surface.

The problem with this method is that you will miss parts if your surface isn´t successoinal (<- found this word in a dictionary spo it might not be the right one) i.e. if you have two seperate balls. To solve this you might want to start from the origin of every single ball and do the above thing.

Doing this he had quite an increase of speed. I preferred not doing this since i like the generality of the marching cubes. You can display the isolevel of ANY scalar funcion (in physics this will be potentials in most cases) not just the field of balls (which would be the potential of a system of masses or the potential of a system of charges).

2)
As for another speedup you should at least try to calculate the normals after having calculated the points. It´s even easier than interpolating to implement and it raises quality surprisingly good so you can switch to a lower gridsize still getting results that are equal in quality (from my experiences I´d say halving the gridsize ( 1/8 times the number of gridpoints) this way still gives better results than going full gridsize with interpolation.

3)
Third speedup you can consider chosing powers of two for the gridsize thus you can acces positions in your grid by shifts rather than by multiplications. I´m not sure if that´s possible for tetrahedrons (whatever this might be). But I wouldn´t reccomend this. I got a small increase in speed but for the cost of a lot of flexibility.

Share this post


Link to post
Share on other sites
Atheist:
first of all, thanks for your time to answer my questions, i really appreciate it.

about the first optimization , i dont think i can use it coz my demo includes a state where the balls are rendered separately, so by what you said , i will have a problem in this state.

about the second one , i think its nice one , but i thought about another one... some triangles share 2 vertiecs , so whats happening is that sometimes i calcuate the normal for the same vertex twise instead of once... what i can do is to check whether i already calculated the normal in this vertex or not... it would save some CPU time.

as for the third one... i prefer to be flexible with the grid size and let the user chose any grid size he wishes.

fourth thing i would like to note is that polygonizing a scalar filed with tetrahedrons generates number of triangles that is approximately twise as that number of triangles that generated using regular marching cubes algorithm.

another question i would like to add is , how can i check whether my generated triangle in the marching cubes algorithm is a fornt face triangle or not without using cross product to check the sign of its normal... is there any other way?

Share this post


Link to post
Share on other sites
>another question i would like to add is , how can i check
>whether my generated triangle in the marching cubes algorithm
>is a fornt face triangle or not without using cross product to
>check the sign of its normal... is there any other way?

This depends completely on the way you''re computing the triangles!

I suggest using some precalculated triangle table for this purpose, for example the tables on Paul Bourke''s site

>about the second one , i think its nice one , but i thought
>about another one... some triangles share 2 vertiecs , so whats
>happening is that sometimes i calcuate the normal for the same
>vertex twise instead of once... what i can do is to check
>whether i already calculated the normal in this vertex or
>not... it would save some CPU time.

Here''s a good trick from "the good ol'' days":

The problem with checking is that you first need to reinitialize the test array per frame. To overcome N^3 iterations, initialize an array that tells on which frame a cell has been checked for the last time. If you ever encounter "the current frame" in some particulal cell, you can assume that it has been already checked on the current frame.

You might use values of -1 for initializing this table, and use the largest possible datatype in hand. Even int is good because you probably won''t compute more than 2,000,000,000 frames of animation...

- Mikko Kauppila

Share this post


Link to post
Share on other sites
What's the tangent vector of a surface Xeno ? How would you define it ? This is meaningless unless you define a plane that cuts the surface in two halves. The gradient IS parallel to your normal vector.

As you wrote (that's called the partial derivative in x)
d/dx(1/R^2) = -(d/dx(R^2))/R^4 that is -2x/R^4.

Can't you see that if (x,y,z) is a point of your sphere (you supposed center is {0,0,0} ) then the normal is parallel to {x,y,z}. Damn the normal to a point of the sphere is parallel to the radius that joins the center to the point ! lol

Gradient(1/R^2) = -2/R^4 * {x,y,z } that is -2/R^3 * N where N is the normal.

and this -2/R^3 represents a kind of inverse volume related to the "curve" at the point.


Now your implicit surface looks like : k1*f(d1) + k2*f(d2) + ... + kn*f(dn) = k0

f(d) being 1/d^2 and d1, d2, ...., dn being the respective distances of the ball centers to the point {x,y,z} : di^2 = (x-xi)^2 + (y-yi)^2 + (z-zi)^2

So you just have to sum the gradients for each ball and you'll get the gradient of your metaball since derivation is a linear application. ( (u+v)'=u'+v' )

Just normalize and change sign. There is no real problem I can see.


[edited by - Charles B on July 11, 2003 7:31:13 PM]

Share this post


Link to post
Share on other sites