Alternative to angle_between?
-
I've been working on this problem quite alot lately, and I've realised the code I posted is wildly incorrect, as you say ThomThom:
@thomthom said:it seem to be 50/50 chance that the cross vector points in opposite directions.
so we should probably compare the cross vector against something relatively static, like one of the model axes?
@unknownuser said:
Note that if you work in the horizontal plane, the you can take Z_AXIS as your reference rotation vector (and then Bill'sformula works).
could this work if we reverse the cross vector based on its angle to the Z_AXIS (ie. greater than 90 degrees then reverse cross vector).
-
@bentleykfrog said:
I've been working on this problem quite alot lately
I've finally got my 2d manifold detection working (albeit quite slowly as I have to calculate an infinite line [planar normal of an edge] intersecting a complex polygon [face] for each edge to determine the side of the edge its associated face is on). Anyway I thought I'd post the code here for some feedback and optimization advice. Here's the code snippet: feel free to chop/change/reuse if you like.def intersect_line_line_segment_2d(line,segment) x1 = line[0].x y1 = line[0].y x2 = line[1].x y2 = line[1].y x3 = segment[0].x y3 = segment[0].y x4 = segment[1].x y4 = segment[1].y u_line_n = ((x4 - x3)*(y1 - y3)) - ((y4 - y3)*(x1 - x3)) #line equation numerator denom = ((y4 - y3)*(x2 - x1)) - ((x4 - x3)*(y2 - y1)) #line & segment equation denominator u_segment_n = ((x2 - x1)*(y1 - y3)) - ((y2 - y1)*(x1 - x3)) #segmnet equation numerator if denom == 0 #line and segment are parallel return false end #if u_segment = u_segment_n.quo(denom) if u_segment >= 0 || u_segment <=1 #return [x1 + (u_segment*(x2-x1)),y1 + (u_segment*(y2-y1)),1] #use to return the point of intersection u_line = u_line_n.quo(denom) #use to return a relative distance value for ordering return u_line #intersections on a complex polygon else #intersection is outside the line segment return false end end #def def find_manifold_face(origin_face_id,fold_edge_id,possible_face_ids,check_orientation=false,correct_orientation=false) origin_face = @@face_objects[origin_face_id] origin_edges = @@faces_to_edges[origin_face_id] manifold_face = false # PT1; ORIGIN FACE->FOLD EDGE ORIENTATION # we need to find on which side of the edge the face is, and then # determine the direction of rotation. This is more difficult than # it appears. The most error-free way to do it is to create a line # that represents the planar normal for the edge (ie perpendicular # to the fold edge and on the plane of the origin face) and find the # line segments that intersect with the face using an Intersect Segment # with Polygon algorithm. [see; http://softsurfer.com/Archive/algorithm_0111/algorithm_0111.htm] # A COUPLE OF NOTES FIRST; # 1;We only need a 2d coordinate system for this so we can use the UVHelper # to generate this and hopefully make the code more efficient # 2;We only need to find the first intersected line segment that shares # one of its points with the fold edge fold_verts = @@edges_to_verts[fold_edge_id] #construct points on the fold edge that will help with fold_arr = fold_verts.values #orientation; pt1; start, pt2; middle, pt3; end fold_pt1 = fold_arr[0].position fold_pt3 = fold_arr[1].position fold_pt2 = fold_pt1 + Geom;;Vector3d.new((fold_pt3.x-fold_pt1.x).quo(2),(fold_pt3.y-fold_pt1.y).quo(2),(fold_pt3.z-fold_pt1.z).quo(2)) fold_vec = fold_pt1.vector_to fold_pt3 trans = Geom;;Transformation.rotation fold_pt2, origin_face.normal, -90.degrees o_vec1 = fold_vec.transform trans origin_uvhelp = origin_face.get_UVHelper true, false, @@tw #UVHelper can give us 2d coordinates for a 3d face ;) fold_uv_pt1 = origin_uvhelp.get_front_UVQ(fold_pt1) #construct the corresponding uv points that are uv fold_uv_pt2 = origin_uvhelp.get_front_UVQ(fold_pt2) #representations of the 3d coordinates fold_uv_pt3 = origin_uvhelp.get_front_UVQ(fold_pt3) fold_uv_vec = fold_uv_pt1.vector_to fold_uv_pt3 trans_uv_vec = Geom;;Vector3d.new(fold_uv_vec[1],-fold_uv_vec[0],1) #construct a fold edge normal line to trans_uv_pt = fold_uv_pt2 + trans_uv_vec #calculate the line segments of intersection trans_uv_line = [fold_uv_pt2, trans_uv_pt] intersection_array = Array[0] origin_edges.each {|edgeID| next if fold_edge_id == edgeID edge_uv_pt1 = origin_uvhelp.get_front_UVQ(@@edge_objects[edgeID].start.position) edge_uv_pt2 = origin_uvhelp.get_front_UVQ(@@edge_objects[edgeID].end.position) edge_uv_segment = [edge_uv_pt1, edge_uv_pt2] intersection_u = self.intersect_line_line_segment_2d(trans_uv_line,edge_uv_segment) next if !intersection_u intersection_array << intersection_u } if intersection_array.length <= 1 msg = "Critical Error; Normalize Toolkit encountered an illegal face (a face with only two vertices).\nYour model probably has errors?" msg += "To check, select the menu item 'Window' -> Model Info, then select 'Statictics' and click on 'Fix Problems'." self.alert_error(msg,true) Sketchup.send_action CMD_SELECT return false end #if intersection_array.sort! #ok lets find if the vector is pointing the right way reverse = (intersection_array.index(0) % 2) ? 1 ; -1 o_vec1.reverse! if reverse == -1 o_pt1 = fold_pt2 + o_vec1 o_vec2 = origin_face.normal #make the origin face's normal an orientation vector #we need two vectors at right angles to get around the #angle_between not greater than 180 degrees problem. smallest_angle = 360.degrees possible_face_ids.each {|faceID| next if !@@faces_to_verts.has_key?(faceID) next if faceID == origin_face_id #logically, the p_vec1 should be found by rotating the fold_vec in the opposite direction #as o_vec1 was. The only issue here is that if the normal is reversed, we wont get a correctly #facing vector. Fortunately, we can determine this by comparing the clockwise angle from o_vec1 #to p_vec1 and from o_vec1 to @@face_objects[faceID].normal. #If o_vec1 to p_vec1 is smaller than o_vec1 to @@face_objects[faceID].normal, we've got a reversed #normal!! cool trans = Geom;;Transformation.rotation fold_pt2, @@face_objects[faceID].normal, reverse * 90.degrees p_vec1 = fold_vec.transform trans t_ang1a = o_vec1.angle_between @@face_objects[faceID].normal t_ang1b = o_vec2.angle_between @@face_objects[faceID].normal t_ang2a = o_vec1.angle_between p_vec1 t_ang2b = o_vec2.angle_between p_vec1 t_ang1 = (t_ang1b <= 90.degrees) ? t_ang1a ; 180.degrees + (180.degrees - t_ang1a) t_ang2 = (t_ang2b <= 90.degrees) ? t_ang2a ; 180.degrees + (180.degrees - t_ang2a) #another problem here is that the difference between t_ang1 & t_ang2 should be roughly plus or minus 90 degrees #if its greater, then the possible face is on such an obtuse angle and reversed that its normal is closer to #o_vec1 than p_vec1 is p_vec1.reverse! if ((t_ang1 > t_ang2) || ((t_ang2 - t_ang1) > 180.degrees)) o_ang1 = o_vec1.angle_between p_vec1 o_ang2 = o_vec2.angle_between p_vec1 manifold_angle = (o_ang2 <= 90.degrees) ? o_ang1 ; 180.degrees + (180.degrees - o_ang1) if manifold_angle < smallest_angle smallest_angle = manifold_angle manifold_face = @@face_objects[faceID] end } if !manifold_face return false end if check_orientation direction = self.get_rotation_direction(fold_vec,fold_pt2,origin_face.normal,o_pt1) #work out whether the vector is pointing in the right direction trans = Geom;;Transformation.rotation fold_pt2, fold_vec, (smallest_angle * direction) #rotate the origin normal so its aligned with m_normal = o_vec2.transform trans #the manifold's normal. This should give a vector m_ang1 = m_normal.angle_between manifold_face.normal #that angles 180 degrees from the manifold's normal oriented = (m_ang1 > 90.degrees) ? true ; false #if its less than 90 degrees, reverse the face. return Hash[ "manifold_face" => manifold_face, "oriented" => oriented ] end #if return manifold_face end #def -
just for context, attached is the wip with a few modifications to the previous post to reduce the load significantly if we're dealing with convex polygons.
-
See if any ideas here help. Tried to find arctan2 for three 3d. More search probably required
http://www.euclideanspace.com/maths/algebra/vectors/angleBetween/index.htm -
atan2()is one of the methods in the standard RubyMathmodule.Somewhere TIG posted an example method of using it with Sketchup API units.
-
wow, major oversight! I should probably be using edge.reversed_in? to reliably find the edge normal direction relative to the face.
Just to double-check my logic: on outer loops edge.reversed_in? will return true if the start and end vertex of the edge is running clockwise (if your looking against the normal of the face [the negative face normal vector is the vector for determining clockwise or anti-clockwise]). On inner loops (face.loops - face.outer_loop) edge.reversed_in will return true if the start and end vertex of the edge is running counter-clockwise?
-
Once one determines the angle value the inverse trig functions calculate the principal value. Therefore to determine the actual angle logic must be use either in the method or in the program its self to determine the correct quadrant. Give one can get the cos from the dot product, sine from the cross and even tangent from tan( theta) = |V1xV2|/ (V1 dot V2) then it is possible to establish the quadrant??
-
@bentleykfrog said:
wow, major oversight! I should probably be using edge.reversed_in? to reliably find the edge normal direction relative to the face.
Just to double-check my logic: on outer loops edge.reversed_in? will return true if the start and end vertex of the edge is running clockwise (if your looking against the normal of the face [the negative face normal vector is the vector for determining clockwise or anti-clockwise]). On inner loops (face.loops - face.outer_loop) edge.reversed_in will return true if the start and end vertex of the edge is running counter-clockwise?
Aye.
LoopandEdgeUseobjects can be very useful. -
@bentleykfrog said:
Just to double-check my logic: on outer loops edge.reversed_in? will return true if the start and end vertex of the edge is running clockwise (if your looking against the normal of the face [the negative face normal vector is the vector for determining clockwise or anti-clockwise]). On inner loops (face.loops - face.outer_loop) edge.reversed_in will return true if the start and end vertex of the edge is running counter-clockwise?
I'm probably getting a bit off topic here, so to sum up, when you're looking against the normal of the face
edge.reversed_in? returns true when the face is on the left hand side of the edge, and false when on the right hand side of the face (irrespective of inner and outer loops, so disregard my previous assumption).@mac1 said:
Once one determines the angle value the inverse trig functions calculate the principal value. Therefore to determine the actual angle logic must be use either in the method or in the program its self to determine the correct quadrant. Give one can get the cos from the dot product, sine from the cross and even tangent from tan( theta) = |V1xV2|/ (V1 dot V2) then it is possible to establish the quadrant??
I agree, the problem I had in Sketchup (I think) is determining a consistent cross and dot product vectors. Once you've established consistent methods for determining these, you should be good to go.
In my case I'm trying to define a 2d manifold. What's important in a 2d manifold is the angle between two faces (complex polygons) at a common edge. Given this angle, we can establish 2d manifold errors (like an edge sharing 3 or more faces).
To establish this angle we need three vectors: 'the edge vector normal on the first face', 'the face normal' & the 'the edge vector normal on the second face'.
edge.reversed_in?seems to be a very consistent way to get the right edge vector normals. Also, to eliminate errors with faces that are reversed, we need to define a 'dominant' face. This dominant face is the origin of the 2d manifold, so all other connected faces should be oriented in the same direction as the dominant face (ie. all looking into the 2d manifold, or all looking out of the 2d manifold), if not, their normal vector is reversed (not the face itself) so the angle between two faces remains consistent. In my code, the dominant face is the face the user hovers over with their cursor.@thomthom said:
Aye.
LoopandEdgeUseobjects can be very useful.
-
Not ruby programmer so leave that up to you, but for 3d vectors and using the general approach the angle is the shortest great circle path between the two. The angle is atan2( Norm( cross(a,b)), dot( a,b)). This means the angle is 0 to pi()
FYI http://www.euclideanspace.com/maths/algebra/vectors/angleBetween/index.htm and http://www.mathworks.com/matlabcentral/newsreader/view_thread/151925
Advertisement