9 replies to this topic

[JoryRFerrell]

<p>How do I determine if a the normal for a vertex has been created by ccw ordered verts or cw wound verts? I assign each vert's neighbors to a list in the order they wind around, but it doesn't assign them in a secific clockwise/ccw order consistently. I have just decided to calculate the normal then determine whether the verts are cw, or ccw, and then change the signs of the normal vector components accordingly.</p>
<p>&nbsp;</p>
<p>Some suggested using a secondary vector to compare the angle between the secondary and the generated normal. If greater than 90, or less than, that would tell me if the normal vector is facing the direction I need. But I don't think this works for concave (NOTE: I originally wrote &quot;CONVEX&quot;. I meant &quot;CONCAVE&quot;. :\) shapes (normals can face toward origin, allowing for angles less than 90 degrees when compared with a vector drawn from the origin of object.</p>

Edited by JoryRFerrell, 07 March 2013 - 08:53 PM.

[Megahertz]

Is the object guaranteed to be closed? Convex or not.

[JoryRFerrell]

Is the object guaranteed to be closed? Convex or not.

Yes. Objects are guaranteed to be closed (for now) and must account for both convex and concave geometry. Is their an algorithm which will do this for both with a single equation? Or would it require different equations/logic-branches for each?

 

Also, I want it to handle weird geometry with verts forming concave shapes which bow in past the objects local origin. Say you take a unit cube a split two opposite faces, along the z axis, into four faces each. then you take the center vertices of those four faces and translate them both -1.5 along the z axis. You'd have one vert which went inwards (forming a concave surface) past its own origin, so I can't rely on a vector from the origin to each vert, that compares with the generated normal to check the total angle between the two or something.

Edited by JoryRFerrell, 07 March 2013 - 06:16 PM.

[cr88192]

note:
usually figuring out the vertex normals is done (in the simple case) via a cross product.

say, we have 3 points (A, B, C) along the edge of a polygon, and want to find the normal for point B:
X=B-A
Y=C-B
Z=normalize(X % Y)

then basically, similar is done for each vertex, to generate starting normals.

note that depending on the winding of the vertices, the normals will either point into or out-of the object.


while this works, the normals generated tend to point directly out of the face, and ignore adjacent faces. for some tasks, we might want weighted normals.

the trick is basically for each vertex, finding any other vertices at the same coordinates.
then, one can do a "weighted average" of all the normals, with the weight being the dot-product between the normals.
this will smooth out soft curves while also preserving sharp edges.


dunno if this helps...

[Megahertz]

I've been giving this problem some thought over the past day or so and here's what has been on my mind.

 

Let's take the simplest example, a cube.

 

First you need to determine a point that is outside the object. You need to have some sort of reference/view point.The easiest way would be to pick a point that is some large distance away from the object so that it pretty much guarantees the point is outside.

 

Next calculate the normal for a triangle/face of the cube and calculate the dot product of this normal vector with the one formed by the view point and a point on the face of the cube to determine which way the triangle/face is facing.

 

The problem is that the winding order matters in that you could be comparing a back face of the cube and the dot product result would indicate that its a front facing surface.

 

I guess you would need to calculate the closest intersection point between the way-off-in-the-distance point and the faces of the cube. The closest intersection point would indicate that you have found a surface that is facing "outward" towards the view point. (You could only do this for objects that are closed)

 

From here you could use the result of the dot product to make a determination as to the winding order of the verts.

 

Thoughts?

[JoryRFerrell]

note:
usually figuring out the vertex normals is done (in the simple case) via a cross product.

say, we have 3 points (A, B, C) along the edge of a polygon, and want to find the normal for point B:
X=B-A
Y=C-B
Z=normalize(X % Y)

then basically, similar is done for each vertex, to generate starting normals.

note that depending on the winding of the vertices, the normals will either point into or out-of the object.


while this works, the normals generated tend to point directly out of the face, and ignore adjacent faces. for some tasks, we might want weighted normals.

the trick is basically for each vertex, finding any other vertices at the same coordinates.
then, one can do a "weighted average" of all the normals, with the weight being the dot-product between the normals.
this will smooth out soft curves while also preserving sharp edges.


dunno if this helps...

Yea, I already know about cross-product method. I have made one, but Newell's Method is more accurate.

 

Like I was saying, my method grabs all neighboring verts, and forms a projected face from them on each axis. For each created face, I find the normal of the face via the cross product method. Then with all those calculated face normals, I take the average and I end up with the more accurate per-vertex normal.

My problem was correctly finding the neighbor vertices in a consistent clockwise/counter-clockwise order. They often get reversed with my current algorithm. But, if I could find a way to correctly determine the order of the verts after finding them, I could simply reverse the per-vertex normal whenever it was facing the wrong direction. However I found a way to ensure the normal is facing the correct direction no matter what, and I don't need to determine the handedness of the neighbor verts order to do it. Look at explanation below.

[wintertime]

the trick is basically for each vertex, finding any other vertices at the same coordinates.
then, one can do a "weighted average" of all the normals, with the weight being the dot-product between the normals.
this will smooth out soft curves while also preserving sharp edges.

Wouldnt it be better if the dot product is just used to divide those vertices at the same coordinate into groups with not too high angle in between the surface normals and then use weights that get higher for wider angles between adjacent edges of each vertex?

[LorenzoGatti]

Given a possibly concave (or even self-intersecting) polygon as a vertex list, you can compute whether it's sorted clockwise or counterclockwise by looking at the sign of its area, which you can compute as the sum of the signed area of each triangle formed by two consecutive vertices of the polygon and a chosen point outside it. You need neither normals nor angles.

[cr88192]

the trick is basically for each vertex, finding any other vertices at the same coordinates.
then, one can do a "weighted average" of all the normals, with the weight being the dot-product between the normals.
this will smooth out soft curves while also preserving sharp edges.

Wouldnt it be better if the dot product is just used to divide those vertices at the same coordinate into groups with not too high angle in between the surface normals and then use weights that get higher for wider angles between adjacent edges of each vertex?

well, typically there will only be 3 or 4 faces sharing each vertex, so grouping wouldn't seem to make much sense.

a weighted average for each vertex seems to work pretty well, since the only times the different normals will effect each other is when they are already similar.

say, if it is at the corner of a box, for each vertex, the dot-products of the other vertices' normals will be 0, so they have no real effect (each vertex will retain its own normal), and on a pointy corner they will be negative (which is clamped to 0).

whereas, on a curve, the faces may have much closer normals, so this will tend to average them out a lot more.

[JoryRFerrell]

I figured out a method and posted a vid on it:

 

http://youtu.be/wwMD2UX0rQ4