Archived

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

Normal to a descrete surface

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a mathematical problem, for which I think I have an answer, but since I have almost no math background, I thought to ask you for an advise. The problem is as follows: suppose a surface that consists of some final number (n) of discrete points. We have to calculate a normal to the surface at some point p[x] (0<=x[j]=crossProduct(p[i],p[j]); m[i][j]=magnitude(c); wp[i][j]= c[i][j]/m[i][j]; //weighted cross product } } normal = mean (wp)* mean (m); //END As I said, I''m not mathematician, so I''d like to hear some experts'' opinion on this issue Thanks a lot

Share this post


Link to post
Share on other sites
I took some time to asure myself that what you are doing is definitely wrong.

First of all there is not one "correct" set of normals for a set of points. How could there be one? Afterall we are talking about a disconnected set of points and normals usually only exist on planes. That said, let''s try and solve your problem anyway, in general terms.

First of all you need some knowledge of what those points are representing.

Are they a unconnected particle system - well forget about normals, at least you don''t need to calculate them as you may chose any one of your liking.

Are they parts of a geometry like a person or a heightfield? Well normals can be calculated in this case but they depend on what model of surfaces and normal interpolation you choose.

Give me some more informations before I launch into a full lecture on normals, surfaces, etc

Share this post


Link to post
Share on other sites
Sure the use case is important, but from the post I can imagine that the discrete set of point is representing a mesh (either a heightmap or a model).

Next comes the problem of the mathematical representation of the mesh (maybe it's some kind of curved surface that need special treatment) but I will assume it is not the case since some advanced math knowledge is required there and our guy clearly states that he dos not have this knowledge.

So I'll assume that the discrete points are representing a set of connected vertices.

The first thing to do is to triangulate the surface. If your surface is a height map then the tesselation is rather natural. If it is not then it should be explicit (or you are going to need some complex surface reconstruction algorithm). The code you posted do not tell anything about the spatial organisation of your surface - and therefore is very difficult to interpret.

With either explicit or implicit tessalation, the Complete Unoptimized But Readable Normal Calculation Algorithm looks like this :


for each (polygon) in (the model)
for each (vertex) in (the polygon)
add (a reference to the polygon) to (the vertex)
end for each
compute (polygon)->normal // using the method you want
end for each

for each (vertex) in (the vertice list)
N = (0, 0, 0)
for each (referenced polygon) in (the vertex)
N = N + (referenced polygon)->normal
end for each
(vertex)->normal = N / (referenced polygon count)
end for each


It looks like a hammer is used to kill a bee but it is simple as hell

Cordialement,

--
Emmanuel


[edited by - Emmanuel Deloget on October 10, 2003 12:59:34 PM]

Share this post


Link to post
Share on other sites
Your answer is exactly the reason why I asked for the use case. If we ignore for a moment that your normals are still in need of normalizing, which makes the
end for each
(vertex)->normal = N / (referenced polygon count)

redundant, there are still some open sores:
compute (polygon)->normal 

assumes there is one unique normal for the entire polygon, which in general is only true for triangles. Besides your average mesh has to be triangulated for rendering.

Back to "is it really what I want?" apply your algorithm to a cube, or to any other structure requiring sharp edges like any indoor level. If you assume a (axis aligned) cube of 6 sides, 6 polygons each with a unique normal your algorithm provides normals (+/-1, +/-1, +/-1) which require some normalizing. But even once normalized the normals not really satisfactory.

It gets worse once you take triangulation into account, because then a normal is added more then once, while others at the same point are taken only once. So there may be normals like (+2,-1,-2) or (+1,-1,+2) which is simply wrong, not even suboptimal.

You will have to figure out the unique normals of polygons adjacent to each vertex, in order to get at least remotely useful results. And dont't forget to normalize.

In my opinion, pretending there is a simple answer when there is not is worse then asking for more detail

[edited by - Dreamforger on October 15, 2003 5:04:10 AM]

Share this post


Link to post
Share on other sites
Forget my ridiculous english. I''m very tired.

quote:
Original post by Dreamforger
Back to "is it really what I want?" apply your algorithm to a cube, or to any other structure requiring sharp edges like any indoor level. If you assume a (axis aligned) cube of 6 sides, 6 polygons each with a unique normal your algorithm provides normals (+/-1, +/-1, +/-1) which require some normalizing. But even once normalized the normals not really satisfactory.



The same algorithm can be applied on such surfaces. Basically, the goal is to approximate a continuous, derivable surface. When the surface cannot be derivated at a particular point P then it is obvious that you need more than one vertex to represent this point P. Considering the example of a cube gives a good idea of the way it works : for each vertex of the cube, you really need 3 points - neither D3D nor OGL supports multiple normals per points. Each of these 24 points is a particular vertex of exactly one face (cube faces are squares. Of course, you can triangulate your faces and then a vertex can be associated to at most 2 faces which are coplanar - so the case is stricly equivalent). The given algorithm tells you that the normal to a particular vertex is the normal to the face it belongs.

quote:
Original post by Dreamforger
In my opinion, pretending there is a simple answer when there is not is worse then asking for more detail



Of course, there is no simple answer. If the surface is a NURBS then there is a lot of math in order to first compute the surface parameters then the vertice normals. And both of us can imagine even more complicated cases. In my previous post I assumed a number of things from which I derived the algorithm I gave. If bgbg''s case is not the one I described then for sure the post I made will not help him But since I described a classic case I had good chances to provide helpful informations.

Of course, I may be wrong

--
Emmanuel

Share this post


Link to post
Share on other sites