1%% 2%% wings_vertex.erl -- 3%% 4%% This module contains utility functions for vertices. 5%% 6%% Copyright (c) 2001-2011 Bjorn Gustavsson 7%% 8%% See the file "license.terms" for information on usage and redistribution 9%% of this file, and for a DISCLAIMER OF ALL WARRANTIES. 10%% 11%% $Id$ 12%% 13 14-module(wings_vertex). 15-export([from_edges/2,from_faces/2, 16 fold/4,other/2,other_pos/3, 17 until/4,until/5, 18 center/1,center/2, 19 bounding_box/1,bounding_box/2,bounding_box/3, 20 normal/2,per_face/2, 21 flatten/3,flatten/4, 22 dissolve_isolated/2, 23 connect/3,connect_cut/3,force_connect/4, 24 pos/2,outer_vertices_ccw/2,reachable/2, 25 isolated/1,edge_through/3,edge_through/4]). 26 27-export_type([vertex_num/0]). 28 29-include("wings.hrl"). 30-import(lists, [member/2,foldl/3,reverse/1,sort/1]). 31 32-type vertex_num() :: non_neg_integer(). 33-type edge_num() :: wings_edge:edge_num(). 34 35%% from_faces(FaceGbSet, We) -> VertexList 36%% Convert a set of faces to a list of vertices. 37from_faces(Fs, We) -> 38 wings_face:to_vertices(Fs, We). 39 40%% to_vertices(EdgeGbSet, We) -> VertexGbSet 41%% Convert a set of edges to a set of vertices. 42from_edges(Es, We) -> 43 wings_edge:to_vertices(Es, We). 44 45%% 46%% Fold over all edges/faces surrounding a vertex. 47%% 48 49fold(F, Acc, V, #we{vc=Vct}=We) -> 50 Edge = array:get(V, Vct), 51 fold(F, Acc, V, Edge, We). 52 53fold(F, Acc0, V, Edge, #we{es=Etab}) -> 54 Acc = case array:get(Edge, Etab) of 55 #edge{vs=V,lf=Face,rf=Other,rtpr=NextEdge}=E -> 56 F(Edge, Face, E, Acc0); 57 #edge{ve=V,lf=Face,rf=Other,rtsu=NextEdge}=E -> 58 F(Edge, Face, E, Acc0) 59 end, 60 fold(F, Acc, V, Other, NextEdge, Edge, Etab). 61 62fold(_F, Acc, _V, _Face, Last, Last, _Etab) -> Acc; 63fold(F, Acc0, V, Face, Edge, LastEdge, Etab) -> 64 Acc = case array:get(Edge, Etab) of 65 #edge{vs=V,lf=Face,rf=Other,rtpr=NextEdge}=E -> 66 F(Edge, Face, E, Acc0); 67 #edge{ve=V,lf=Face,rf=Other,rtsu=NextEdge}=E -> 68 F(Edge, Face, E, Acc0); 69 #edge{vs=V,rf=Face,lf=Other,ltsu=NextEdge}=E -> 70 F(Edge, Face, E, Acc0); 71 #edge{ve=V,rf=Face,lf=Other,ltpr=NextEdge}=E -> 72 F(Edge, Face, E, Acc0) 73 end, 74 fold(F, Acc, V, Other, NextEdge, LastEdge, Etab). 75 76%% 77%% Fold over all edges/faces surrounding a vertex until the 78%% accumulator changes. 79%% 80 81until(F, Acc, V, #we{vc=Vct}=We) -> 82 Edge = array:get(V, Vct), 83 until(F, Acc, V, Edge, We). 84 85until(F, Acc, V, Edge, #we{es=Etab}) -> 86 #edge{lf=Face} = array:get(Edge, Etab), 87 until(F, Acc, V, Face, Edge, Edge, Etab, not_done). 88 89until(_F, Acc, _V, _Face, Last, Last, _Etab, done) -> Acc; 90until(F, Acc0, V, Face, Edge, LastEdge, Etab, _) -> 91 Acc = case array:get(Edge, Etab) of 92 #edge{vs=V,lf=Face,rf=Other,rtpr=NextEdge}=E -> 93 F(Edge, Face, E, Acc0); 94 #edge{ve=V,lf=Face,rf=Other,rtsu=NextEdge}=E -> 95 F(Edge, Face, E, Acc0); 96 #edge{vs=V,rf=Face,lf=Other,ltsu=NextEdge}=E -> 97 F(Edge, Face, E, Acc0); 98 #edge{ve=V,rf=Face,lf=Other,ltpr=NextEdge}=E -> 99 F(Edge, Face, E, Acc0) 100 end, 101 if 102 Acc =:= Acc0 -> 103 until(F, Acc, V, Other, NextEdge, LastEdge, Etab, done); 104 true -> Acc 105 end. 106 107%% other(Vertex, EdgeRecord) -> OtherVertex 108%% Pick up the "other vertex" from an edge record. 109other(V, #edge{vs=V,ve=Other}) -> Other; 110other(V, #edge{ve=V,vs=Other}) -> Other. 111 112%% pos(Vertex, VtabOrWe) -> {X,Y,Z} 113%% Return the three coordinates for a vertex. 114pos(V, #we{vp=Vtab}) -> 115 array:get(V, Vtab); 116pos(V, Vtab) -> 117 array:get(V, Vtab). 118 119%% other_pos(Vertex, EdgeRecord, VtabOrWe) -> {X,Y,Z} 120%% Pick up the position for the "other vertex" from an edge record. 121other_pos(V, #edge{vs=V,ve=Other}, Tab) -> pos(Other, Tab); 122other_pos(V, #edge{ve=V,vs=Other}, Tab) -> pos(Other, Tab). 123 124%% center(We) -> {CenterX,CenterY,CenterZ} 125%% Find the geometric center of a body. 126center(#we{vp=Vtab}=We) -> 127 Center = e3d_vec:average(array:sparse_to_list(Vtab)), 128 Flatten = wings_we:mirror_projection(We), 129 e3d_mat:mul_point(Flatten, Center). 130 131%% center(VertexGbSet, We) -> {CenterX,CenterY,CenterZ} 132%% Find the geometric center of all vertices. 133center(Vs0, #we{vp=Vtab}) -> 134 Vs = if 135 is_list(Vs0) -> Vs0; 136 true -> gb_sets:to_list(Vs0) 137 end, 138 center(Vs, Vtab); 139center(Vlist, Vtab) -> 140 Positions = foldl(fun(V, A) -> 141 [pos(V, Vtab)|A] 142 end, [], Vlist), 143 e3d_vec:average(Positions). 144 145bounding_box(We) -> 146 bounding_box(We, none). 147 148bounding_box(#we{vp=Vtab}=We, BB) -> 149 do_bounding_box(array:sparse_to_list(Vtab), We, BB); 150bounding_box(Vs, We) -> 151 bounding_box(Vs, We, none). 152 153bounding_box(Vs, We, BB) when is_list(Vs) -> 154 bounding_box_1(ordsets:from_list(Vs), We, BB); 155bounding_box(Vs, We, BB) -> 156 bounding_box(gb_sets:to_list(Vs), We, BB). 157 158bounding_box_1(Vs0, #we{vp=Vtab}=We, BB) -> 159 Vs1 = sofs:from_external(Vs0, [vertex]), 160 R = sofs:from_external(array:sparse_to_orddict(Vtab), [{vertex,data}]), 161 I = sofs:image(R, Vs1), 162 Vs = sofs:to_external(I), 163 do_bounding_box(Vs, We, BB). 164 165do_bounding_box(Vs, #we{mirror=none}, BB) -> 166 do_bounding_box_1(Vs, BB); 167do_bounding_box(Vs0, #we{}=We, BB) -> 168 Mtx = wings_we:mirror_projection(We), 169 Vs = foldl(fun(P0, A) -> 170 P = e3d_mat:mul_point(Mtx, P0), 171 [P,P0|A] 172 end, [], Vs0), 173 do_bounding_box_1(Vs, BB). 174 175do_bounding_box_1(Vs, none) -> 176 e3d_vec:bounding_box(Vs); 177do_bounding_box_1(Vs, [Min,Max]) -> 178 e3d_vec:bounding_box([Min,Max|Vs]). 179 180%% normal(Vertex, We) -> Normal 181%% Calculate the normal for a vertex (based on the normals for all 182%% surrounding faces). 183normal(V, We) -> 184 Ns = fold(fun(_, Face, _, A) -> 185 [wings_face:normal(Face, We)|A] 186 end, [], V, We), 187 e3d_vec:norm(e3d_vec:add(Ns)). 188 189%% per_face(Vs, We) -> [{Face,[V]}] 190%% Group vertices according to face. 191per_face(Vs, We) when is_list(Vs) -> 192 per_face(Vs, We, []); 193per_face(Vs, We) -> 194 per_face(gb_sets:to_list(Vs), We, []). 195 196per_face([V|Vs], We, Acc0) -> 197 Acc = fold(fun(_, Face, _, A) -> 198 [{Face,V}|A] 199 end, Acc0, V, We), 200 per_face(Vs, We, Acc); 201per_face([], _We, Acc) -> 202 R = sofs:relation(Acc), 203 F = sofs:relation_to_family(R), 204 sofs:to_external(F). 205 206%% flatten(Vs, PlaneNormal, We) -> We' 207%% Flatten vertices by projecting them to the given plane. 208flatten(Vs, PlaneNormal, We) when is_list(Vs) -> 209 Center = wings_vertex:center(Vs, We), 210 flatten(Vs, PlaneNormal, Center, We); 211flatten(Vs, PlaneNormal, We) -> 212 flatten(gb_sets:to_list(Vs), PlaneNormal, We). 213 214flatten(Vs, PlaneNormal, Center, #we{vp=Vtab0}=We0) when is_list(Vs) -> 215 Flatten = flatten_matrix(Center, PlaneNormal), 216 Vtab = foldl(fun(V, Tab0) -> 217 flatten_move(V, Flatten, Tab0) 218 end, Vtab0, Vs), 219 We = We0#we{vp=Vtab}, 220 wings_we:mirror_flatten(We0, We); 221flatten(Vs, PlaneNormal, Center, We) -> 222 flatten(gb_sets:to_list(Vs), PlaneNormal, Center, We). 223 224flatten_matrix(Origin, PlaneNormal) -> 225 M0 = e3d_mat:translate(Origin), 226 M = e3d_mat:mul(M0, e3d_mat:project_to_plane(PlaneNormal)), 227 e3d_mat:mul(M, e3d_mat:translate(e3d_vec:neg(Origin))). 228 229flatten_move(V, Matrix, Vtab0) -> 230 Pos0 = array:get(V, Vtab0), 231 Pos = e3d_mat:mul_point(Matrix, Pos0), 232 array:set(V, Pos, Vtab0). 233 234%% dissolve_isolated_vs([Vertex], We) -> We' 235%% Remove all isolated vertices ("winged vertices", or vertices 236%% having exactly two edges). 237dissolve_isolated(Vs, We) -> 238 wings_edge:dissolve_isolated_vs(Vs, We). 239 240%% Connect vertices (which must share a face). 241connect(_Face, [_], We) -> We; 242connect(Face, Vs, #we{} = We0) -> 243 case polygon_pairs(Face, Vs, We0) of 244 no -> min_distance_pairs(Face, Vs, We0); 245 #we{} = We -> We 246 end. 247 248%% Connect Va to Vb, maybe through several faces. 249%% Return {#we{},gbset(Edges). 250 251-spec connect_cut(vertex_num(), vertex_num(), #we{}) -> 252 {#we{},gb_sets:set(edge_num())}. 253 254connect_cut(VS0, VE0, #we{}=We0) when is_integer(VS0), is_integer(VE0) -> 255 CutPlane = calc_planes(VS0,VE0,We0), 256 ETree = collect_edges(CutPlane, ordsets:from_list([VS0, VE0]), We0), 257 try 258 CutEs = select_cut_edges(VS0, VE0, ETree, We0), 259 Cut = fun({edge, Ei, Pos, Face}, {WeAcc,AccVs}) -> 260 {We1,Idx} = wings_edge:fast_cut(Ei, Pos, WeAcc), 261 {We1, [Idx,Face|AccVs]}; 262 ({vertex,_,V,Face}, {WeAcc, AccVs}) -> 263 {WeAcc, [V,Face|AccVs]} 264 end, 265 {We2,Vs1} = lists:foldl(Cut, {We0, []}, CutEs), 266 connect_vs(Vs1, We2, []) 267 catch _:_Reason:_ST -> 268 %% io:format("~p: ~p~n", [Reason, _ST]), 269 wings_u:error_msg(?__(1, "Could not connect vertices.")) 270 end. 271 272connect_vs([Va, Face|[Vb|_]=Vs], #we{next_id=Edge}=We0, Acc) -> 273 case edge_through(Va, Vb, Face, We0) of 274 none -> 275 {We,_} = force_connect(Va, Vb, Face, We0), 276 connect_vs(Vs, We, [Edge|Acc]); 277 Exist -> 278 connect_vs(Vs, We0, [Exist|Acc]) 279 end; 280connect_vs([_, undefined], We, Acc) -> 281 {We,gb_sets:from_list(Acc)}. 282 283path_length([V1|[V2|_]=Vs], We, Acc) -> 284 Dist = e3d_vec:dist(v(V1, We),v(V2, We)), 285 path_length(Vs, We, Dist + Acc); 286path_length([_], _, Acc) -> Acc. 287 288v({edge, _, Pos, _}, _We) -> Pos; 289v({vertex,_, V, _}, We) -> pos(V, We). 290 291select_cut_edges(VS0, VE0, Es, We) -> 292 FS0 = wings_face:from_vs([VS0], We), 293 Start00 = wings_face:fold_faces( 294 fun(Face, V, _Edge, _E, _Acc) when V =:= VE0 -> 295 [{stop, Face}]; 296 (Face, _V, EdgeId, E, Acc) -> 297 case collect_cut_edge(Face, Es, EdgeId, E, Acc) of 298 Acc -> Acc; 299 [{vertex, _, V,_},{vertex,_,V,_}|_] -> Acc; 300 [S1|Acc] -> [S1,Face|Acc] 301 end 302 end, [], FS0, We), 303 select_start_edges(filter_edges(Start00, []), VS0, VE0, Es, We). 304 305filter_edges([_,Face|[_,Face|_]=Start], Acc) -> 306 filter_edges(Start, Acc); 307filter_edges([EI,Face|Start], Acc) -> 308 filter_edges(Start, [Face,EI|Acc]); 309filter_edges([{stop,Face}|_], _) -> [{stop,Face}]; 310filter_edges([], Acc) -> Acc. 311 312select_start_edges([{stop,Face}], VS0, VE0, _Es, _We) -> 313 [{vertex, undefined, VE0, undefined}, {vertex, undefined, VS0, Face}]; 314select_start_edges([F1, S1], VS0, VE0, Es, We) when is_integer(F1) -> 315 case select_cut_edges_2(S1, VE0, Es, We, [{vertex,undefined,VS0, F1}]) of 316 fail -> throw(fail); 317 R1 -> [VE0|R1] 318 end; 319select_start_edges([F1, S1, F2, S2], VS0, VE0, Es, We) -> 320 R1 = select_cut_edges_2(S1, VE0, Es, We, [{vertex,undefined,VS0,F1}]), 321 R2 = select_cut_edges_2(S2, VE0, Es, We, [{vertex,undefined,VS0,F2}]), 322 case {R1, R2} of 323 {fail, fail} -> throw(fail); 324 {fail, R2} -> [{vertex,undefined,VE0,undefined}|R2]; 325 {R1, fail} -> [{vertex,undefined,VE0,undefined}|R1]; 326 _ -> 327 Path1 = [{vertex,undefined,VE0,undefined}|R2], 328 Path2 = [{vertex,undefined,VE0,undefined}|R1], 329 case path_length(Path1, We, 0.0) < path_length(Path2, We, 0.0) of 330 true -> Path1; 331 false -> Path2 332 end 333 end. 334 335select_cut_edges_2({stop,_Face}, _, _, _, CEs) -> 336 CEs; 337select_cut_edges_2({Type, Edge, VId, Face}=New, Stop, Es0, We, CEs) -> 338 Es = gb_trees:delete(Edge,Es0), 339 Next = wings_face:fold(fun(V, _EdgeId, _E, _Acc) when V =:= Stop -> 340 [{stop,Face}]; 341 (_V, _EdgeId, _E, [{stop,_}]=Acc) -> Acc; 342 (_V, EdgeId, E, Acc) -> 343 collect_cut_edge(Face, Es, EdgeId, E, Acc) 344 end, [fail], Face, We), 345 case {Type, CEs} of 346 {vertex, [{vertex, _, VId, _}|Acc]} -> %% Ignore already connect VId 347 select_cut_edges_2(hd(Next), Stop, Es, We, [New|Acc]); 348 _ -> 349 select_cut_edges_2(hd(Next), Stop, Es, We, [New|CEs]) 350 end; 351select_cut_edges_2(fail, _, _, _, _) -> fail. 352 353collect_cut_edge(_Face, _Es, _Edge, _E, [stop]=R) -> R; 354collect_cut_edge(Face, Es, Edge, E, Acc) -> 355 case gb_trees:lookup(Edge, Es) of 356 none -> Acc; 357 {value,{reuse_vertex, V}} -> 358 Next = wings_face:other(Face, E), 359 [{vertex, Edge, V, Next}|Acc]; 360 {value,Dist} -> 361 Next = wings_face:other(Face, E), 362 [{edge, Edge, Dist, Next}|Acc] 363 end. 364 365%% Collect all edges on the cut plane and calc edge cut distance 366collect_edges(Plane, Ignore, #we{es=Etab}=We) -> 367 Tol = 0.0001, 368 Filter = 369 fun(Ei, _Val, Acc) -> 370 #edge{vs=VS,ve=VE} = array:get(Ei,Etab), 371 Pt1 = wings_vertex:pos(VS,We), 372 Pt2 = wings_vertex:pos(VE,We), 373 S1 = e3d_vec:plane_side(Pt1, Plane), 374 S2 = e3d_vec:plane_side(Pt2, Plane), 375 D1 = abs(e3d_vec:plane_dist(Pt1, Plane)), 376 D2 = abs(e3d_vec:plane_dist(Pt2, Plane)), 377 if 378 D1 < Tol -> 379 Add = D2 >= Tol andalso 380 ordsets:is_disjoint(ordsets:from_list([VS,VE]),Ignore), 381 reuse_vertex(Add, VS, Ei, Acc); 382 D2 < Tol -> 383 Add = D1 >= Tol andalso 384 ordsets:is_disjoint(ordsets:from_list([VS,VE]),Ignore), 385 reuse_vertex(Add, VE, Ei, Acc); 386 S1 =/= S2 -> 387 Dir = e3d_vec:norm(e3d_vec:sub(Pt2,Pt1)), 388 Percent = D1/(D1+D2), 389 PtX = e3d_vec:add(Pt1, e3d_vec:mul(Dir, Percent*wings_edge:length(Ei,We))), 390 gb_trees:enter(Ei,PtX,Acc); 391 true -> 392 Acc 393 end 394 end, 395 array:sparse_foldl(Filter, gb_trees:empty(), Etab). 396 397reuse_vertex(false, _, _Ei, Acc) -> 398 Acc; 399reuse_vertex(true, VS, Ei, Acc) -> 400 gb_trees:enter(Ei,{reuse_vertex, VS}, Acc). 401 402calc_planes(VS0, VE0, We) -> 403 P1 = wings_vertex:pos(VS0,We), 404 P2 = wings_vertex:pos(VE0,We), 405 Vec = e3d_vec:norm(e3d_vec:sub(P2, P1)), 406 Mid = e3d_vec:average(P1, P2), 407 N1 = wings_vertex:normal(VS0,We), 408 N2 = wings_vertex:normal(VE0, We), 409 AverN = e3d_vec:average(N1, N2), 410 Wanted = [N || N <- [AverN, N1, N2], 411 e3d_vec:len(N) > 0.0001, 412 abs(e3d_vec:dot(Vec, N)) < 0.9999], 413 Normal = case Wanted of 414 [N|_] -> N; 415 [] -> 416 {X,Y,Z} = Vec, 417 if abs(X) < abs(Z), abs(Y) < abs(Z) -> {1.0, 0.0, 0.0}; 418 abs(Z) < abs(X), abs(Y) < abs(X) -> {0.0, 0.0, 1.0}; 419 true -> {1.0, 0.0, 0.0} 420 end 421 end, 422 e3d_vec:plane(Mid, e3d_vec:cross(Vec,Normal)). 423 424 425%% Create pairs by walking the edge of the face. If we can connect 426%% all selected vertices for the face we are done. The result will 427%% be a polygon. 428%% 429%% +----*----+ 430%% | / \ | 431%% | / \ | * = Selected vertices 432%% | / \ | + = Unselected vertices 433%% |/ \| 434%% * * 435%% |\ /| 436%% | \ / | 437%% | \ / | 438%% | \ / | 439%% +----*----+ 440 441polygon_pairs(Face, Vs, We0) -> 442 ?ASSERT(length(Vs) > 1), 443 Iter = wings_face:iterator(Face, We0), 444 {Vstart,_,_,_} = wings_face:next_cw(Iter), 445 case pp_make_pairs(Iter, Vs, Vstart, []) of 446 [Va,Vb] -> 447 case try_connect({Va,Vb}, Face, We0) of 448 no -> We0; 449 {We,_} -> We 450 end; 451 Pairs -> polygon_pairs_1(Pairs, Face, Pairs, We0) 452 end. 453 454polygon_pairs_1([Va|[Vb|_]=T], Face, Pairs, We0) -> 455 case try_connect({Va,Vb}, Face, We0) of 456 no -> no; 457 {We,_} -> polygon_pairs_1(T, Face, Pairs, We) 458 end; 459polygon_pairs_1([Va], Face, [Vb|_], We) -> 460 polygon_pairs_1([Va,Vb], Face, [], We); 461polygon_pairs_1([_], _, [], We) -> We. 462 463pp_make_pairs(Iter0, Vs, Vstart, Acc) -> 464 case wings_face:next_cw(Iter0) of 465 {Vstart,_,_,_} when Acc =/= [] -> 466 reverse(Acc); 467 {V,_,_,Iter} -> 468 case member(V, Vs) of 469 false -> pp_make_pairs(Iter, Vs, Vstart, Acc); 470 true -> pp_make_pairs(Iter, Vs, Vstart, [V|Acc]) 471 end 472 end. 473 474%% If polygon_pairs/3 failed, we search for the two 475%% vertices which are nearest each other. We try to connect, 476%% then repeat the search in both the original face and the 477%% the newly created face. We continue until no more connections 478%% are possible. Two vertices that have been connected cannot be 479%% connected again (in the same face). 480%% 481%% +-----+ 482%% | | * = Selected vertices 483%% *-----* + = Non-selected vertices 484%% | | 485%% | | 486%% *-----* 487%% | | 488%% | | 489%% *-----* 490%% | | 491%% +-----+ 492%% 493 494min_distance_pairs(Face, Vs, We) -> 495 min_distance_pairs_1(gb_sets:singleton(Face), ordsets:from_list(Vs), We). 496 497min_distance_pairs_1(Faces0, Vs0, We0) -> 498 case gb_sets:is_empty(Faces0) of 499 true -> We0; 500 false -> 501 {Face,Faces1} = gb_sets:take_smallest(Faces0), 502 case nearest_pair_smart(Face, Vs0, We0) of % dgud 503 no -> 504 case nearest_pair(Face, Vs0, We0) of 505 no -> 506 min_distance_pairs_1(Faces1, Vs0, We0); 507 {{Va,Vb},{We,NewFace}} -> 508 Faces = gb_sets:insert(NewFace, Faces0), 509 Vs = ordsets:subtract(Vs0, ordsets:from_list([Va,Vb])), 510 min_distance_pairs_1(Faces, Vs, We) 511 end; 512 {{Va,Vb},{We,NewFace}} -> 513 Faces = gb_sets:insert(NewFace, Faces0), 514 Vs = ordsets:subtract(Vs0, ordsets:from_list([Va,Vb])), 515 min_distance_pairs_1(Faces, Vs, We) 516 end 517 end. 518 519%% Don't go for position distance - use the topological distance instead. 520%% Hopefully fixes this problem: 521%% A B C 522%% +__*_ *__*_+ 523%% \ | \ 524%% \ | \ 525%% \ | \ 526%% \ | \ 527%% \ | \ 528%% \ | \ 529%% +--*--*--*-+ 530%% D E F 531%% What we do is to try connecting each selected vertex to the 532%% next selected vertex near it. For instance, we might try the following 533%% connections: A-B, B-C, C-D... The first two connections will be 534%% discarded because the resulting new faces do not have defined 535%% normals. The connection C-D will succeed. 536 537nearest_pair_smart(Face, AllVs, We) -> 538 FaceVs = wings_face:vertices_ccw(Face, We), 539 Vs0 = ordsets:from_list(FaceVs), 540 Vs = ordsets:intersection(Vs0, AllVs), 541 nearest_pair_smart_1(FaceVs, Vs, Face, We, []). 542 543%% If we knew that the intersection was stable this step wouldn't be needed. 544nearest_pair_smart_1([V|Vs], Sel, Face, We, Acc) -> 545 case ordsets:is_element(V, Sel) of 546 true -> 547 nearest_pair_smart_1(Vs, Sel, Face, We, [V|Acc]); 548 false -> 549 nearest_pair_smart_1(Vs, Sel, Face, We, Acc) 550 end; 551nearest_pair_smart_1([], _, Face, We, Acc=[Last|_]) when length(Acc) > 1 -> 552 connect_pairs([Last|reverse(Acc)],Face,We); 553nearest_pair_smart_1([], _, _, _, _) -> 554 no. 555 556nearest_pair(Face, AllVs, #we{vp=Vtab}=We) -> 557 Vs0 = ordsets:from_list(wings_face:vertices_ccw(Face, We)), 558 Vs = ordsets:intersection(Vs0, AllVs), 559 VsPos = [{V,array:get(V, Vtab)} || V <- Vs], 560 nearest_pair(VsPos, Face, We, []). 561 562nearest_pair([{V,Pos}|VsPos], Face, We, Acc0) -> 563 Acc = nearest_pair_1(VsPos, V, Pos, Acc0), 564 nearest_pair(VsPos, Face, We, Acc); 565nearest_pair([], Face, We, Acc) -> 566 connect_pairs(sort(Acc), Face, We). 567 568nearest_pair_1([{Vb,PosB}|VsPos], Va, PosA, Acc) -> 569 Dist = e3d_vec:dist(PosA, PosB), 570 nearest_pair_1(VsPos, Va, PosA, [{Dist,{Va,Vb}}|Acc]); 571nearest_pair_1([], _, _, Acc) -> Acc. 572 573connect_pairs([{_,Pair}|Pairs], Face, We0) -> 574 case try_connect(Pair, Face, We0) of 575 no -> connect_pairs(Pairs, Face, We0); 576 {_,_}=Res -> {Pair,Res} 577 end; 578%% <dgud 579connect_pairs([Va,Vb|Pairs], Face, We0) -> 580 Pair = {Va,Vb}, 581 case try_connect(Pair, Face, We0) of 582 no -> connect_pairs([Vb|Pairs], Face, We0); 583 {_,_}=Res -> {Pair,Res} 584 end; 585connect_pairs([_], _, _) -> no; 586%% dgud> 587connect_pairs([], _, _) -> no. 588 589try_connect({Va,Vb}, Face, We) -> 590 %% Do not try to connect if there is an edge from Va to Vb in this face. 591 case edge_through(Va, Vb, Face, We) of 592 none -> try_connect_1(Va, Vb, Face, We); 593 _ -> no 594 end. 595 596try_connect_1(Va, Vb, Face, We0) -> 597 {We,NewFace} = Res = force_connect(Va, Vb, Face, We0), 598 599 %% It is crucial that we reject long thin faces, such as 600 %% 601 %% A 602 %% | 603 %% | 604 %% C 605 %% | 606 %% | 607 %% B 608 %% 609 %% (where the edges are A-C, C-B, and B-A), since the 610 %% Connect command for vertices will try many combinations 611 %% of pair of vertices if the user has selected more than two 612 %% vertices. 613 case wings_face:is_thin(Face, We) orelse 614 wings_face:is_thin(NewFace, We) of 615 true -> no; 616 false -> Res 617 end. 618 619%% force_connect(Vstart, Vend, Face, We0) -> We 620%% Create a new edge between the vertices Vstart and Vend 621%% in face Face, also creating a new face. 622%% 623%% The edges between Vstart and Vend (in the clockwise direction) 624%% and the left side of the new edge will belong to the new face. 625%% 626force_connect(Vstart, Vend, Face, #we{es=Etab0,fs=Ftab0}=We0) -> 627 All = wings_face:vertices_ccw(Face, We0), 628 true = lists:member(Vstart, All) andalso lists:member(Vend, All), 629 {NewFace,We1} = wings_we:new_ids(1, We0), 630 NewEdge = NewFace, 631 NeRec0 = #edge{vs=Vstart,ve=Vend,lf=NewFace,rf=Face}, 632 633 Iter0 = wings_face:iterator(Face, We1), 634 Iter1 = wings_face:skip_to_cw(Vstart, Iter0), 635 {_,_,_,Iter2} = wings_face:next_ccw(Iter1), 636 {Etab1,NeRec1,Iter3} = connect_1(Iter2, Vstart, NewEdge, NeRec0, Etab0), 637 {Etab2,NeRec2} = connect_2(Iter3, Vstart, NewEdge, NeRec1, Etab1), 638 {Etab3,Iter} = connect_3(Iter3, Face, Vend, NewFace, Etab2), 639 Etab = connect_4(Iter, Vend, NewEdge, NeRec2, Etab3), 640 641 Ftab1 = gb_trees:insert(NewFace, NewEdge, Ftab0), 642 Ftab = gb_trees:update(Face, NewEdge, Ftab1), 643 Mat = wings_facemat:face(Face, We1), 644 We2 = We1#we{es=Etab,fs=Ftab}, 645 646 LeftAttr = wings_va:vtx_attrs(Vstart, Face, We0), 647 RightAttr = wings_va:vtx_attrs(Vend, Face, We0), 648 We = wings_va:set_both_edge_attrs(NewEdge, LeftAttr, RightAttr, We2), 649 650 {wings_facemat:assign(Mat, [NewFace], We),NewFace}. 651 652%% connect_1(Iter0, Vstart, NewEdge, NeRec0, Etab0) -> {Etab,NeRec,Iter} 653%% Connect the edge immediately before Vstart. 654connect_1(Iter0, Vstart, NewEdge, NeRec0, Etab) -> 655 case wings_face:next_cw(Iter0) of 656 {_,Edge,#edge{ve=Vstart}=Rec0,Iter} -> 657 NeRec = NeRec0#edge{rtpr=Edge}, 658 Rec = Rec0#edge{rtsu=NewEdge}; 659 {_,Edge,#edge{vs=Vstart}=Rec0,Iter} -> 660 NeRec = NeRec0#edge{rtpr=Edge}, 661 Rec = Rec0#edge{ltsu=NewEdge} 662 end, 663 {array:set(Edge, Rec, Etab),NeRec,Iter}. 664 665%% connect_2(Iter0, Vstart, NewEdge, NeRec0, Etab) -> {Etab,NeRec} 666%% Connect the edge immediately after Vstart. 667connect_2(Iter, Vstart, NewEdge, NeRec0, Etab) -> 668 case wings_face:next_cw(Iter) of 669 {_,Edge,#edge{vs=Vstart}=Rec0,_} -> 670 NeRec = NeRec0#edge{ltsu=Edge}, 671 Rec = Rec0#edge{rtpr=NewEdge}; 672 {_,Edge,#edge{ve=Vstart}=Rec0,_} -> 673 NeRec = NeRec0#edge{ltsu=Edge}, 674 Rec = Rec0#edge{ltpr=NewEdge} 675 end, 676 {array:set(Edge, Rec, Etab),NeRec}. 677 678%% connect_3(Iter, Face, Vend, NewFace, Etab0) -> {Etab,Iter} 679%% Replace the face for all edges between Vstart and Vend. 680%% The returned iterator points to the edge immediately before Vend. 681connect_3(Iter0, Face, Vend, NewFace, Etab0) -> 682 {_,Edge,_,Iter} = wings_face:next_cw(Iter0), 683 684 %% Ignore the record returned by the iterator, because it 685 %% is stale for the edge that was updated by connect_2/5. 686 Rec = case array:get(Edge, Etab0) of 687 #edge{lf=Face}=Rec0 -> Rec0#edge{lf=NewFace}; 688 #edge{rf=Face}=Rec0 -> Rec0#edge{rf=NewFace} 689 end, 690 Etab = array:set(Edge, Rec, Etab0), 691 case Rec of 692 #edge{vs=Vend} -> {Etab,Iter0}; 693 #edge{ve=Vend} -> {Etab,Iter0}; 694 _Other -> connect_3(Iter, Face, Vend, NewFace, Etab) 695 end. 696 697%% connect_4(Iter, Vend, NewEdge, NeRec, Etab0) -> Etab 698%% Patches the final two edges. 699connect_4(Iter0, Vend, NewEdge, NeRec0, Etab0) -> 700 {_,Edge,_,Iter} = wings_face:next_cw(Iter0), 701 Rec = case array:get(Edge, Etab0) of 702 #edge{ve=Vend}=Rec0 -> 703 NeRec1 = NeRec0#edge{ltpr=Edge}, 704 Rec0#edge{rtsu=NewEdge}; 705 #edge{vs=Vend}=Rec0 -> 706 NeRec1 = NeRec0#edge{ltpr=Edge}, 707 Rec0#edge{ltsu=NewEdge} 708 end, 709 Etab1 = array:set(Edge, Rec, Etab0), 710 711 %% Now for the final edge. 712 FinalRec = case wings_face:next_cw(Iter) of 713 {_,Final,#edge{vs=Vend}=FinalRec0,_} -> 714 NeRec = NeRec1#edge{rtsu=Final}, 715 FinalRec0#edge{rtpr=NewEdge}; 716 {_,Final,#edge{ve=Vend}=FinalRec0,_} -> 717 NeRec = NeRec1#edge{rtsu=Final}, 718 FinalRec0#edge{ltpr=NewEdge} 719 end, 720 Etab = array:set(Final, FinalRec, Etab1), 721 array:set(NewEdge, NeRec, Etab). 722 723%% outer_vertices_ccw(Faces, We) -> [V] | error 724%% Faces (non-empty list or gb_set) must comprise a single face region 725%% (each face must share at least one edge with another face in the 726%% region). This functions returns a list of the outer vertices, 727%% ordered in CCW order. (Useful for calculating the normal for 728%% an edge loop, for instance.) The return value is 'error' if 729%% the faces don't comprise a single region. 730 731outer_vertices_ccw(Faces, We) when is_list(Faces) -> 732 collect_outer_edges(Faces, gb_sets:from_list(Faces), We, []); 733outer_vertices_ccw(Faces, We) -> 734 collect_outer_edges(gb_sets:to_list(Faces), Faces, We, []). 735 736collect_outer_edges([Face|Fs], Faces, We, Acc0) -> 737 Acc = wings_face:fold( 738 fun(_, _, Erec, A) -> 739 outer_edge(Erec, Face, Faces, A) 740 end, Acc0, Face, We), 741 collect_outer_edges(Fs, Faces, We, Acc); 742 743collect_outer_edges([], _Faces, _We, []) -> 744 error; 745 746collect_outer_edges([], _Faces, _We, Acc) -> 747 R = sofs:relation(Acc), 748 F0 = sofs:relation_to_family(R), 749 [{Va,Info}|F] = sofs:to_external(F0), 750 order_edges(Va, Info, gb_trees:from_orddict(F), []). 751 752outer_edge(Erec, Face, Faces, Acc) -> 753 {V,OtherV,OtherFace} = 754 case Erec of 755 #edge{vs=Vs,ve=Ve,lf=Face,rf=Other0} -> 756 {Vs,Ve,Other0}; 757 #edge{vs=Vs,ve=Ve,rf=Face,lf=Other0} -> 758 {Ve,Vs,Other0} 759 end, 760 case gb_sets:is_member(OtherFace, Faces) of 761 true -> Acc; %Not an outer edge. 762 false -> [{V,{V,OtherV}}|Acc] 763 end. 764 765order_edges(Va, [{Va,Vb}], Es0, Acc0) -> 766 Acc = [Va|Acc0], 767 case gb_trees:lookup(Vb, Es0) of 768 none -> 769 %% We have collected all outer vertices for one 770 %% face region. We are done unless more edges remain 771 %% (which is an error). 772 case gb_trees:is_empty(Es0) of 773 true -> Acc; 774 false -> error 775 end; 776 {value,Val} -> 777 Es = gb_trees:delete(Vb, Es0), 778 order_edges(Vb, Val, Es, Acc) 779 end; 780order_edges(_, [_,_|_], _, _) -> 781 %% Two face regions are connected by a single vertex. 782 error. 783 784%% reachable([Vertex], We) -> [ReachableVertex] 785%% Returns a list of the vertices that can be reached by following 786%% edges from the given list of vertices. 787reachable(Vs0, #we{es=Etab,vc=Vct}) when is_list(Vs0) -> 788 Es0 = foldl(fun(V, A) -> 789 [array:get(V, Vct)|A] 790 end, [], Vs0), 791 Es1 = gb_sets:from_list(Es0), 792 Es = reachable_edges(Es1, Etab, gb_trees:empty()), 793 Vs = foldl(fun(#edge{vs=Va,ve=Vb}, A) -> 794 [Va,Vb|A] 795 end, [], gb_trees:values(Es)), 796 ordsets:from_list(Vs). 797 798reachable_edges(Ws0, Etab, Reachable0) -> 799 case gb_sets:is_empty(Ws0) of 800 true -> Reachable0; 801 false -> 802 {Edge,Ws1} = gb_sets:take_smallest(Ws0), 803 Rec = array:get(Edge, Etab), 804 Reachable = gb_trees:insert(Edge, Rec, Reachable0), 805 #edge{ltpr=LP,ltsu=LS,rtpr=RP,rtsu=RS} = Rec, 806 reachable_edges_1([LP,LS,RP,RS], Etab, Ws1, Reachable) 807 end. 808 809reachable_edges_1([E|Es], Etab, Ws, Reachable) -> 810 case gb_trees:is_defined(E, Reachable) of 811 true -> 812 reachable_edges_1(Es, Etab, Ws, Reachable); 813 false -> 814 reachable_edges_1(Es, Etab, gb_sets:add(E, Ws), Reachable) 815 end; 816reachable_edges_1([], Etab, Ws, Reachable) -> 817 reachable_edges(Ws, Etab, Reachable). 818 819%% isolated(We) -> GbSet 820%% Returns a list containing all isolated vertices in We. 821 822isolated(#we{vp=Vtab}=We) -> 823 Vs0 = foldl(fun(V, A) -> 824 isolated_1(V, We, A) 825 end, [], wings_util:array_keys(Vtab)), 826 Vs1 = sofs:relation(Vs0), 827 Fs0 = sofs:domain(Vs1), 828 Fs = sofs:to_external(Fs0), 829 StableFaces = sofs:set(stable_faces(Fs, We)), 830 Vs = sofs:image(Vs1, StableFaces), 831 sofs:to_external(Vs). 832 833isolated_1(V, We, Acc) -> 834 Fs = fold(fun(_, Face, _, A) -> 835 [Face|A] 836 end, [], V, We), 837 case Fs of 838 [A,B] -> [{A,V},{B,V}|Acc]; 839 [_|_] -> Acc 840 end. 841 842%% stable_faces(Faces, We) -> StableFaces 843%% Returns a list of the stable faces. Stable faces have at least 844%% three corner vertices (vertices with 3 or more neighboring edges), 845%% meaning that the face will not collapse if any vertices with only 846%% two edges are removed from it. 847 848stable_faces(Fs, We) -> 849 stable_faces(Fs, We, []). 850 851stable_faces([F|Fs], We, Acc) -> 852 case is_face_stable(F, We) of 853 true -> stable_faces(Fs, We, [F|Acc]); 854 false -> stable_faces(Fs, We, Acc) 855 end; 856stable_faces([], _, Acc) -> Acc. 857 858is_face_stable(Face, We) -> 859 Vs = wings_face:vertices_ccw(Face, We), 860 is_face_stable_1(Vs, We, 0). 861 862is_face_stable_1([V|Vs], We, N) -> 863 case is_corner(V, We) of 864 true -> is_face_stable_1(Vs, We, N+1); 865 false -> is_face_stable_1(Vs, We, N) 866 end; 867is_face_stable_1([], _, N) -> N >= 3. 868 869is_corner(V, We) -> 870 N = fold(fun(_, _, _, A) -> A+1 end, 0, V, We), 871 N >= 3. 872 873%% edge_through(Vertex1, Vertex1, Face, We) -> Edge|none 874%% Returns the edge number of the edge between Vertex1 and Vertex2 875%% in the given face (if there is one). 876edge_through(Va, Vb, Face, We) -> 877 foldl(fun({Edge,Lf,Rf}, A) -> 878 case Face of 879 Lf -> Edge; 880 Rf -> Edge; 881 _ -> A 882 end 883 end, none, edge_through(Va, Vb, We)). 884 885%% edge_through(Vertex1, Vertex1, We) -> [{Edge,LeftFace,RightFace}] 886%% Returns edge number and faces number for all edges between 887%% Vertex1 and Vertex2. 888edge_through(Va, Vb, We) -> 889 fold(fun(Edge, _, #edge{lf=Lf,rf=Rf}=Rec, A) -> 890 case other(Va, Rec) of 891 Vb -> [{Edge,Lf,Rf}|A]; 892 _ -> A 893 end 894 end, [], Va, We). 895