Jump to content

  • Log In with Google      Sign In   
  • Create Account

Determining which order to add vert neighbors in prep for Newells Method/Normal Calculation.


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
No replies to this topic

#1 JoryRFerrell   Members   -  Reputation: 143

Like
0Likes
Like

Posted 10 February 2013 - 02:33 PM

I am attempting to find the neighbors for each vert in an object. By finding all the neighbors, adding them to a index in a consistent clockwise/counter-clockwise order, I can then calculate the normals via Newell's Method. But, I have a problem. When I run this with a cube as a test object, I get Half the normals moving in the correct direction (normals facing out of object), and the other half facing inwards. The problem is the order in which the verts are added. I can't figure out how to consistently find which verts to  add to the list of neighbors according to the neighbors position.

 

    for face in faces:

        if vert_ID+1 in face:

            if total_Neighbors == 3:

                if face.index(vert_ID+1) == 0:

                    # print "Located: 0"
                    if vertices[face[1]-1] not in neighbors:
                        neighbors[1] = vertices[face[1]-1]
                    if vertices[face[3]-1] not in neighbors:
                        neighbors[2] = vertices[face[3]-1]

                elif face.index(vert_ID+1) == 1:

                    # print "Located: 1"
                    if vertices[face[0]-1] not in neighbors:
                        neighbors[0] = vertices[face[0]-1]
                    if vertices[face[2]-1] not in neighbors:
                        neighbors[1] = vertices[face[2]-1]

                elif face.index(vert_ID+1) == 2:

                    # print "Located: 2"
                    if vertices[face[1]-1] not in neighbors:
                        neighbors[0] = vertices[face[1]-1]
                    if vertices[face[3]-1] not in neighbors:
                        neighbors[2] = vertices[face[3]-1]

                elif face.index(vert_ID+1) == 3:
                    # print "Located: 3"
                    if vertices[face[0]-1] not in neighbors:
                        neighbors[0] = vertices[face[0]-1]
                    if vertices[face[2]-1] not in neighbors:
                        neighbors[1] = vertices[face[2]-1]

For every vert in an object, I iterate through all the faces, checking to see if the vert is contained in the face. If so, I grab the address/index value of the verts position in the face. For every possible position the vert can be in (in a cube, there are obviously 4 possible places it can be...), I add the two verts, which would logically be connected to it, after checking to make sure each is not going to be written over a value already in the list of neighbors (If a value besides zero already occupies the spot, my algor. doesn't overwrite it. I ran into some issues when I did.).

 

I create the neighbors list and initialize it with values (so I can assign rather than append, which created problems with my partic. algorithm).

If the vert is in position 1 (or index value "0") I assign the two neighbors to specific spots in the neighbors list. The order and spot they occupy is important since newells method is non-commutative (the two possible results being complete opposite vectors), meaning I need to ensure all neighbors are added as either clockwise, or counter-clockwise.

 

The following is a line for each vertice, followed by the list of neighbors.

 Neighbors:
(-1.0, -1.0, 1.0)   [(-1.0, -1.0, -1.0), (1.0, -1.0, 1.0), (-1.0, 1.0, 1.0)]

(-1.0, -1.0, -1.0)   [(-1.0, -1.0, 1.0), (1.0, -1.0, -1.0), (-1.0, 1.0, -1.0)]

(1.0, -1.0, -1.0)   [(1.0, 1.0, -1.0), (1.0, -1.0, 1.0), (-1.0, -1.0, -1.0)]

(1.0, -1.0, 1.0)   [(-1.0, -1.0, 1.0), (1.0, 1.0, 1.0), (1.0, -1.0, -1.0)]

(-1.0, 1.0, 1.0)   [(-1.0, -1.0, 1.0), (1.0, 1.0, 1.0), (-1.0, 1.0, -1.0)]

(-1.0, 1.0, -1.0)   [(-1.0, -1.0, -1.0), (1.0, 1.0, -1.0), (-1.0, 1.0, 1.0)]

(1.0, 1.0, -1.0)   [(-1.0, 1.0, -1.0), (1.0, 1.0, 1.0), (1.0, -1.0, -1.0)]

(1.0, 1.0, 1.0)   [(1.0, 1.0, -1.0), (1.0, -1.0, 1.0), (-1.0, 1.0, 1.0)]


 



 

Then the output:

    Normals: 
(-2.0, -2.0,  2.0)
( 2.0,  2.0,  2.0)#<- reversed. Should be (-2.0, -2.0, -2.0)
( 2.0, -2.0, -2.0)
(-2.0,  2.0, -2.0)#<- reversed. Should be (2.0, -2.0, 2.0)
(-2.0,  2.0,  2.0)
( 2.0, -2.0,  2.0)#<- reversed. Should be (-2.0, 2.0, -2.0)
( 2.0,  2.0, -2.0)
(-2.0, -2.0, -2.0)#<- reversed. Should be (2.0, 2.0, 2.0)

And yes...I have not normalized these, so they are a length of 2. I already have a func for normalizing the values, I just didn't use it. tongue.png

Anyway's, has anyone seen examples of this problem or see any solutions for dealing with it? I have the bulk of this written, but it's useless if every other normal is pointing INTO the object.... tongue.png

 

I don't need the algorithm in any particular language or anything, you can even help with pseudocode. I'm not picky.

Thanks in advance. smile.png


Edited by JoryRFerrell, 10 February 2013 - 02:37 PM.


Sponsor:



Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS