1%%%------------------------------------------------------------------- 2%%% File : auv_segment.erl 3%%% Author : Dan Gudmundsson <dgud@erix.ericsson.se> 4%%% Description : Different segmentation algorithms. 5%%% Segments Model into set of charts containing faces. 6%%% Created : 3 Oct 2002 by Dan Gudmundsson <dgud@erix.ericsson.se> 7%%%------------------------------------------------------------------- 8%% Copyright (c) 2001-2011 Dan Gudmundsson, Bjorn Gustavsson 9%% 10%% See the file "license.terms" for information on usage and redistribution 11%% of this file, and for a DISCLAIMER OF ALL WARRANTIES. 12%% $Id$ 13 14-module(auv_segment). 15 16-export([create/2,segment_by_material/1,cut_model/3, 17 normalize_charts/3,map_vertex/2,map_edge/2, 18 fv_to_uv_map/2,uv_to_charts/3]). 19 20-ifdef(DEBUG). 21-export([degrees/0, find_features/3, build_seeds/2]). %% Debugging 22-endif. 23 24-include_lib("src/wings.hrl"). 25-include("auv.hrl"). 26 27-import(lists, [reverse/1,mapfoldl/3,sort/1,foldl/3]). 28 29%% Returns segments=[Charts={Id,[Faces]}] and Bounds=gb_sets([Edges]) 30create(Mode, We0) -> 31 case Mode of 32 feature -> 33 Tot = wings_util:array_entries(We0#we.es), 34 {_Distances,Charts0,Cuts0,_Feats} = 35 segment_by_feature(We0, edge_sharpness(), Tot div 50), 36 {Charts0, Cuts0}; 37 autouvmap -> 38 Charts0 = segment_by_direction(We0), 39 {Charts0, gb_sets:empty()} 40 end. 41 42edge_sharpness() -> 43 %% Fool dialyzer to think this is not hard coded 44 case is_process_alive(self()) of 45 true -> 60; 46 false -> rand:uniform(100) 47 end. 48 49%%%%%% Feature detection Algorithm %%%%%%%%%%%% 50%% Algorithms based on the paper, now probably totally ruined by me... 51%% 'Least Square Conformal Maps for Automatic Texture Generation Atlas' 52%% by Bruno Levy, Sylvain Petitjean, Nicolas Ray, Jerome Mailot. 53%% Presented on Siggraph 2002. 54 55-define(MAX_STRING_LENGTH, 5). 56-define(MIN_SHARPNESS(MAX), (1 - MAX) * (?MAX_STRING_LENGTH -1)). 57 58-record(restr, {sharp, featl}). 59 60%% Debug func %% 61-ifdef(DEBUG). 62degrees() -> 63 Test = fun(D) -> 64 X = (math:cos(D * math:pi() / 180) + 1) / 2, 65 Y = math:sin(D * math:pi() / 180) /2, 66 Dir = math:sqrt(X*X+Y*Y), 67 io:format("~.3w "++?__(1,"deg")++" -> ~w ~w~n", [D, Dir, 1 - Dir]) 68 end, 69 lists:foreach(Test, lists:seq(0,360,15)). 70-endif. 71 72degrees(Deg) -> 73 X = (math:cos(Deg * math:pi() / 180) + 1) / 2, 74 Y = math:sin(Deg * math:pi() / 180) /2, 75 math:sqrt(X*X+Y*Y). 76 77segment_by_feature(We, SharpEdgeDeg, MinFeatureLen) -> 78 {Features,VEG,EWs} = find_features(We, SharpEdgeDeg, MinFeatureLen), 79 {LocalMaxs,Extra} = build_seeds(Features, We), 80 {Distances,Charts0,Cuts} = build_charts(LocalMaxs, Extra, VEG, EWs, We), 81 Charts = solve_map_problem(Charts0, We), 82 {Distances,Charts,Cuts,Features}. 83 84 85solve_map_problem(Charts0, _We) when length(Charts0) =< 9 -> 86 Charts0; 87 88solve_map_problem(Charts0, We) -> 89 Charts = auv_util:number(Charts0), 90 FamC2F = sofs:family(Charts), 91 RelC2F = sofs:family_to_relation(FamC2F), 92 FaceChart0 = sofs:to_external(sofs:converse(RelC2F)), 93 Face2Chart = gb_trees:from_orddict(lists:sort(FaceChart0)), 94 EdgesInCharts = 95 lists:foldl(fun({Id, Faces}, Acc) -> 96 [{Id, wings_face:outer_edges(Faces, We)} | Acc] 97 end, [], Charts), 98 Neighbours0 = neighbour_charts(EdgesInCharts, Face2Chart, We#we.es, []), 99 Map = color_map(Neighbours0, gb_trees:empty(), gb_sets:empty(), 0), 100 MapC2Col = sofs:relation(Map), 101 T0 = sofs:range(sofs:relative_product([MapC2Col, FamC2F])), 102 T1 = sofs:range(sofs:family_union(sofs:relation_to_family(T0))), 103 T2 = sofs:to_external(T1), 104 ?DBG("Map painting solved from ~p to ~p colors~n", [length(Charts0), length(T2)]), 105 T2. 106 107 108color_map([{_, Id, NBeds}|Rest], Map0, Cols, NextCol) -> 109 NBcols = lists:foldl(fun(Neigh, Acc) -> 110 case gb_trees:lookup(Neigh, Map0) of 111 none -> Acc; 112 {value, Col} -> 113 gb_sets:add(Col, Acc) 114 end 115 end, gb_sets:empty(), NBeds), 116 Avail = gb_sets:difference(Cols, NBcols), 117 case gb_sets:is_empty(Avail) of 118 true -> 119 color_map(Rest, gb_trees:insert(Id, NextCol, Map0), 120 gb_sets:insert(NextCol,Cols), NextCol +1); 121 false -> 122 {First,_} = gb_sets:take_smallest(Avail), 123 color_map(Rest, gb_trees:insert(Id, First, Map0), Cols, NextCol) 124 end; 125color_map([], Map, _, _) -> 126 gb_trees:to_list(Map). 127 128neighbour_charts([{Id, Edges}|Rest], Face2Chart, Etab, Acc) -> 129 Neighb0 = foldl(fun(Edge, Acc0) -> 130 #edge{lf=LF, rf=RF} = array:get(Edge, Etab), 131 case gb_trees:get(RF, Face2Chart) of 132 Id -> 133 [gb_trees:get(LF, Face2Chart)|Acc0]; 134 Chart -> 135 [Chart|Acc0] 136 end 137 end, [], Edges), 138 Neighb = lists:usort(Neighb0), 139 neighbour_charts(Rest, Face2Chart, Etab, [{length(Neighb), Id, Neighb}|Acc]); 140neighbour_charts([], _, _, Acc) -> 141 reverse(sort(Acc)). 142 143%%% SharpEdge should be degrees value is: (180 +/- SharpEdge) 144%%% MinFeatureLen is the number of edges a feature must contain 145find_features(We, SharpEdge, MinFeatureLen) when MinFeatureLen > 20 -> 146 find_features(We, SharpEdge, 20); 147find_features(We, SharpEdge, MinFeatureLen) when MinFeatureLen < 2 -> 148 find_features(We, SharpEdge, 2); 149find_features(We, SharpEdge, MinFeatureLen) when SharpEdge > 90 -> 150 find_features(We, 90, MinFeatureLen); 151find_features(We, SharpEdge, MinFeatureLen) when SharpEdge < 2 -> 152 find_features(We, 10, MinFeatureLen); 153find_features(We0, SharpEdgeDeg, MinFeatureLen) -> 154 Restrs = #restr{sharp = ?MIN_SHARPNESS(degrees(SharpEdgeDeg)), 155 featl=MinFeatureLen}, 156 {Sorted, N, _FNormals} = sort_edges_by_weight(We0), 157 %% split list normals may diff with +-60 deg and 20% of the edges 158 {Best, _Rest} = pick_features(Sorted, 0, degrees(SharpEdgeDeg), N, []), 159%% ?DBG("Best ~p ~p ~n", [Best, _Rest]), 160 EVGraph = build_vertex_graph(Sorted, We0, gb_trees:empty()), 161 EWs = gb_trees:from_orddict(lists:sort(Sorted)), 162 163 Features0 = expand_features(Best, EVGraph, EWs, We0, Restrs), 164 {Features0, EVGraph, EWs}. 165 166sort_edges_by_weight(We0 = #we{fs = Ftab, es = Etab}) -> 167 Faces = gb_trees:keys(Ftab), 168 FaceNormals0 = lists:map(fun(Face) -> 169 {Face,wings_face:normal(Face, We0)} 170 end, Faces), 171 FaceNormals = gb_trees:from_orddict(FaceNormals0), 172 Edges = wings_util:array_keys(Etab), 173 WEdges = lists:map(fun(Edge) -> 174 Val = calc_normal_value(Edge, FaceNormals, We0), 175 {Edge, Val} 176 end, Edges), 177 {lists:keysort(2,WEdges), length(WEdges), FaceNormals}. 178 179calc_normal_value(Edge, FaceData, We) -> 180 #edge{lf = LF, rf = RF} = array:get(Edge, We#we.es), 181 calc_dir_vector(gb_trees:get(LF,FaceData), gb_trees:get(RF,FaceData)). 182 183pick_features([Edge = {_,Value}|Rest], N, Constraint, Max, Acc) 184 when Value < Constraint, N < Max -> 185 pick_features(Rest, N+1, Constraint, Max, [Edge|Acc]); 186pick_features(Rest, _,_,_, Acc) -> 187 {lists:reverse(Acc), Rest}. 188 189-record(fd, {graph, vals, neigh, feat}). 190-define(fdcreate(VerG,Vals), #fd{graph=VerG, vals=Vals, neigh=gb_sets:empty(), feat=[]}). 191-define(fdmember(Edge,Fd), gb_sets:is_member(Edge, Fd#fd.neigh)). 192-define(fdisneigh(Edge,Fd), gb_sets:is_member(Edge, Fd#fd.neigh)). 193-define(fdgetfeat(Fd), Fd#fd.feat). 194-define(fdgetsurrneigh(EdgVer, Fd), gb_trees:get(EdgVer,Fd#fd.graph)). 195-define(fdgetvalue(Edge, Fd), gb_trees:get(Edge,Fd#fd.vals)). 196-define(fdmarkused(Edge, Fd), Fd#fd{neigh=gb_sets:add(Edge, Fd#fd.neigh)}). 197fdaddneighandfeat(Feat, We, FdXX) -> 198 FindXX = fun(EdgeXX, AccXX) -> 199 #edge{vs=Vs,ve=Ve} = array:get(EdgeXX, We#we.es), 200 Neigh1 = ?fdgetsurrneigh({EdgeXX,Vs}, FdXX), 201 Neigh2 = ?fdgetsurrneigh({EdgeXX,Ve}, FdXX), 202 (Neigh1 ++ Neigh2) ++ AccXX 203 end, 204 PossNeighXX = gb_sets:from_list(lists:foldl(FindXX,[], Feat)), 205 NewNBXX = gb_sets:union(PossNeighXX, FdXX#fd.neigh), 206 FdXX#fd{neigh = NewNBXX, feat = Feat ++ FdXX#fd.feat}. 207 208expand_features(Possible, EVGr, EdgeCost, We, Restrs) -> 209 expand_features(Possible, ?fdcreate(EVGr, EdgeCost), We, Restrs). 210 211expand_features([First = {Edge, _}|Rest], Fd = #fd{}, We, Restrs) -> 212 case ?fdmember(Edge,Fd) of 213 true -> %% Already used ignore 214 expand_features(Rest, Fd, We, Restrs); 215 false -> 216 {Feature, Fd1} = expand_feature_curve(First, Fd, We, Restrs), 217%% ?DBG("Expand ~p ~p ~p ~p~n", [First, Restrs#restr.featl, length(Feature), Feature]), 218 if 219 length(Feature) < Restrs#restr.featl -> 220 expand_features(Rest, Fd, We,Restrs); 221 true -> %% Accepted feature 222 %% Add neighbors 223 Fd2 = fdaddneighandfeat(Feature,We,Fd1), 224 expand_features(Rest, Fd2, We, Restrs) 225 end 226 end; 227expand_features([], Fd, _We, _Restrs) -> 228% ?DBG("Expand done~n"), 229 ?fdgetfeat(Fd). 230 231expand_feature_curve({Edge, _Sharpness}, Fd0, We, Rs) -> 232 #edge{vs = Vs, ve = Ve} = array:get(Edge, We#we.es), 233 Dir1 = get_vector(Vs,Ve,We), 234 {Edges1,_} = get_edges(Vs, Edge, Dir1, We, Fd0), 235 {Feat0, Fd2}=depth_traverse_tree([Edges1],0,0,Dir1,Fd0,We,Rs,[Edge]), 236 Dir2 = get_vector(Ve,Vs,We), 237 {Edges2,_} = get_edges(Ve, Edge, Dir2, We, Fd2), 238 depth_traverse_tree([Edges2],0,0,Dir2,Fd2,We,Rs,Feat0). 239 240depth_traverse_tree(Tree=[[{Val,_,_}|_]|_],Sharp,Depth,_Dir1,Fd0,We,Rs,Feat) 241 when Sharp + Val > Rs#restr.sharp -> 242 %% Found suitable edge -> add to feat 243 [[{Val0,{Edge,#edge{vs=VaN,ve=VbN}},V0}|_]|Found] = lists:reverse(Tree), 244%% ?DBG("Found suitable edge ~p ~p ~p ~n", [Edge,Sharp,Depth]), 245 Fd1 = ?fdmarkused(Edge, Fd0), 246 case Found of 247 [] -> %% Oops first level hit, restart (special case) 248% ?DBG("Special case ~p ~n", [Tree]), 249 NextV = if V0 == VaN -> VbN; V0 == VbN -> VaN end, 250 Dir2 = get_vector(VaN,VbN,V0,We), 251 {Edges1,_} = get_edges(NextV, Edge, Dir2, We, Fd1), 252 depth_traverse_tree([Edges1], 0, 0, Dir2, Fd1, We, Rs, 253 [Edge|Feat]); 254 [[{_,{_,#edge{vs=Va,ve=Vb}},V}|_]|_] -> 255 Dir2 = get_vector(Va,Vb,V,We), 256 depth_traverse_tree(lists:reverse(Found), Sharp - Val0, 257 Depth -1,Dir2,Fd1,We,Rs,[Edge|Feat]) 258 end; 259 260depth_traverse_tree([[]|[[{Value,_,_}|Alt]|Tree]],Sharp, 261 Depth,Dir,Fd0,We,Rs,Feat) -> 262 %% Last tested in that branch -> search other branches 263% ?DBG("Last tested in that branch -> search other branches ~p~n", [Depth]), 264 depth_traverse_tree([Alt|Tree], Sharp -Value, 265 Depth -1,Dir,Fd0, We,Rs,Feat); 266 267depth_traverse_tree([_Miss|[[Root|Alt]|Tree]], Sharp, Depth, 268 Dir,Fd0, We,Rs,Feat) 269 when Depth >= ?MAX_STRING_LENGTH -> 270 %% To deep -> look in other branch 271% ?DBG("To deep -> look in other branch ~n",[]), 272 {Value, _, _} = Root, 273 depth_traverse_tree([Alt|Tree], Sharp - Value, Depth -1, 274 Dir,Fd0, We,Rs, Feat); 275depth_traverse_tree([[]], _Sharp, _Depth, _Dir,Fd0,_We,_Rs,Feat) -> 276 %% done -> tree search complete 277% ?DBG("done[[]]~n",[]), 278 {Feat, Fd0}; 279depth_traverse_tree(Tree=[[{Val,Leaf,Vertex}|_]|_],Sharp,Depth, 280 Dir,Fd0,We,Rs,Feat) -> 281 %% No success yet -> search deeper 282%% ?DBG("No success yet -> search deeper ~p (~p) ~p ~n",[Sharp+Val, ?MIN_SHARPNESS, Depth]), 283 Next = case Leaf of 284 {Id, #edge{vs = Vertex, ve = NextV}} -> 285 NextV; 286 {Id, #edge{ve = Vertex, vs = NextV}} -> 287 NextV 288 end, 289 case get_edges(Next, Id, Dir, We, Fd0) of 290 {[],Poss} -> %% Fixing last edge in edgeloop 291 {NewSharp,NewTree, NewFeat} = 292 patch_tree(Poss, Sharp+Val, Tree, Rs,Feat), 293 depth_traverse_tree(NewTree,NewSharp,Depth+1,Dir,Fd0, 294 We,Rs,NewFeat); 295 {Edges,_} -> 296 depth_traverse_tree([Edges|Tree],Sharp+Val,Depth+1,Dir,Fd0, 297 We,Rs,Feat) 298 end. 299 300patch_tree([{Val,{Edge,_ER},_Vs}|_],Sharp,Tree,Rs,Feat) -> 301 case lists:member(Edge, Feat) of 302 true when (Val + Sharp) > Rs#restr.sharp -> 303%%% ?DBG("Patched OK ~p ~n",[Edge]), 304 NewFeats = lists:map(fun([{_,{Element,_},_}|_]) -> Element end, 305 Tree), 306 {Val + Sharp, [[]], NewFeats ++ Feat}; 307 _Mem -> 308%%% ?DBG("patch miss ~p ~p ~p ~p ~n",[Edge, _Mem, Val, Sharp]), 309 {Sharp, [[]|Tree], Feat} 310 end; 311patch_tree([],Sharp,Tree, _,Feat) -> 312 {Sharp, [[]|Tree], Feat}. 313 314get_edges(V, Current, CurrVect, We, Fd) -> 315 Surr = ?fdgetsurrneigh({Current,V}, Fd), 316 Add = fun(Edge, Acc = {Acc1,Acc2}) -> 317 case ?fdisneigh(Edge, Fd) of 318 true -> 319 ER = array:get(Edge, We#we.es), 320 Val = ?fdgetvalue(Edge,Fd), 321 {Acc1,[{1-Val,{Edge,ER},V}|Acc2]}; 322 false -> 323 ER = #edge{vs = Va,ve = Vb} = array:get(Edge, We#we.es), 324 ThisVect = get_vector(Va,Vb,V,We), 325 Dir = calc_dir_vector(CurrVect, ThisVect), 326 if Dir < 0.707106 -> %% 90deg 327 Acc; 328 true -> 329 Val = ?fdgetvalue(Edge,Fd), 330 {[{1 - Val, {Edge, ER}, V}|Acc1],Acc2} 331 end 332 end 333 end, 334 {New,Bup} = lists:foldl(Add, {[],[]}, Surr), 335 {lists:reverse(lists:sort(New)), lists:reverse(lists:sort(Bup))}. 336 337 338calc_dir_vector(Vec1, Vec2) -> 339 Vec = e3d_vec:add(Vec1,Vec2), 340 e3d_vec:len(e3d_vec:divide(Vec, 2.0)). 341 342get_vector(A,B,A,We) -> 343 get_vector(B,A,We); 344get_vector(A,B,B,We) -> 345 get_vector(A,B,We). 346 347get_vector(A, B, #we{vp=Vs}) -> 348 e3d_vec:norm(e3d_vec:sub(array:get(A, Vs), array:get(B, Vs))). 349 350find_extremities(#we{vc=Vct,vp=Vs0,es=Es}) -> 351 Center = e3d_vec:average(array:sparse_to_list(Vs0)), 352 Vs = array:sparse_to_orddict(Vs0), 353 AllC = lists:map(fun({Id,Pos}) -> 354 Dist = e3d_vec:dist(Pos, Center), 355 {Dist,Id,Pos} 356 end, Vs), 357 [{_,V1,V1Pos}|_] = lists:reverse(lists:sort(AllC)), 358 AllV1 = lists:map(fun({Id,Pos}) -> 359 Dist = e3d_vec:dist(Pos, V1Pos), 360 {Dist,Id,Pos} 361 end, Vs), 362 [{_,V2,_}|_] = lists:reverse(lists:sort(AllV1)), 363 E1 = array:get(V1, Vct), 364 E2 = array:get(V2, Vct), 365 F1 = (array:get(E1,Es))#edge.lf, 366 case (array:get(E2,Es))#edge.lf of 367 F1 -> 368 [F1, (array:get(E2,Es))#edge.rf]; 369 F2 -> 370 [F1, F2] 371 end. 372 373build_extreme([], _, _, Acc0) -> 374 ReNumber = fun({_Group, Fs}, {No, Acc}) -> 375 {No+1,[{No, Fs}|Acc]} 376 end, 377 {_,Acc} = lists:foldl(ReNumber, {0,[]}, Acc0), 378 F = sofs:family(Acc), 379 Rel = sofs:family_to_relation(F), 380 lists:reverse(sofs:to_external(Rel)); 381build_extreme(Fs,Max,FaceG,Acc) -> 382 Find = fun(Face, {FG, New0, Fs0}) -> 383 case gb_trees:lookup(Face,FG) of 384 {value, New1} -> 385 FG1 = gb_trees:delete(Face,FG), 386 {FG1, New1 ++ New0, [Face|Fs0]}; 387 none -> 388 {FG, New0, Fs0} 389 end 390 end, 391 {FG1,New, Fs1} = lists:foldl(Find, {FaceG, [], []}, Fs), 392 build_extreme(New, Max-1, FG1, [{Max,Fs1}|Acc]). 393 394build_seeds(Features0, #we{fs=Ftab}=We) -> 395 FaceGraph = build_face_graph(gb_trees:keys(Ftab), We, 396 gb_trees:empty()), 397 case Features0 of 398 [] -> 399 Fs = [F1,F2] = find_extremities(We), 400 StartNo = gb_trees:size(Ftab), 401 Dists = [{Max, _}|_] = build_extreme(Fs,StartNo,FaceGraph,[]), 402 LMaxs = [{Max, F1}, {Max, F2}], 403 DTree = lists:foldl(fun({Dist, Face}, Tree) -> 404 gb_trees:insert(Face, Dist, Tree) 405 end, gb_trees:empty(), Dists), 406 {LMaxs,{DTree,Max,Dists}}; 407 _ -> 408 Distances = [{Max, _}|_] = 409 calc_distance(Features0, FaceGraph, We), 410 DTree = lists:foldl(fun({Dist, Face}, Tree) -> 411 gb_trees:insert(Face, Dist, Tree) 412 end, gb_trees:empty(), Distances), 413 LocalMaxs = find_local_max(Distances, DTree,Features0, 414 FaceGraph, We), 415 {LocalMaxs,{DTree,Max,Distances}} 416 end. 417 418build_charts(LocalMaxs, {DistTree,Max,Distances}, VEG, EWs, We) -> 419 {Charts0,Bounds} = expand_charts(LocalMaxs, Max + 1, DistTree, VEG,EWs, We), 420 Charts1 = sofs:from_external(gb_trees:to_list(Charts0), [{atom,atom}]), 421 Charts2 = sofs:converse(Charts1), 422 Charts3 = sofs:relation_to_family(Charts2), 423 Charts4 = sofs:to_external(sofs:range(Charts3)), 424 {Charts,Cuts} = normalize_charts(Charts4, Bounds, We), 425 {Distances,Charts,Cuts}. 426 427add_face_edges_to_heap(Face, FaceDist, ChartBds, Heap, EWs, We) -> 428 Find = fun(_, Edge, #edge{lf=LF,rf=RF}, Heap0) -> 429 case gb_sets:is_member(Edge, ChartBds) of 430 true -> 431 Fopp = if LF == Face -> RF; RF == Face ->LF end, 432 EdgeW = 1 - gb_trees:get(Edge, EWs), 433 gb_trees:enter({FaceDist,EdgeW,Edge},{Face,Fopp}, Heap0); 434 false -> 435 Heap0 436 end 437 end, 438 wings_face:fold(Find, Heap, Face, We). 439 440delete_inner_edges(Face, VEG, We, Boundaries) -> 441 wings_face:fold(fun(_, Edge, _, A) -> 442 case is_extremity(Edge, Boundaries, VEG, We) of 443 false -> A; 444 true -> gb_sets:delete_any(Edge, A) 445 end 446 end, Boundaries, Face, We). 447 448expand_charts(LocalMaxs, Max, Dt, VEG,EWs, We0) -> 449 ChartsE = gb_trees:empty(), 450 HeapE = gb_trees:empty(), 451 ChartBds = gb_sets:from_ordset(wings_util:array_keys(We0#we.es)), 452 Init = fun({LMax, Face}, {Chart0, Heap0}) -> 453 Chart1 = gb_trees:insert(Face, Face, Chart0), 454 Heap1 = add_face_edges_to_heap(Face,Max-LMax,ChartBds,Heap0,EWs,We0), 455 {Chart1, Heap1} 456 end, 457 {ChartI, HeapI} = lists:foldl(Init, {ChartsE, HeapE}, LocalMaxs), 458 expand_charts(HeapI, ChartI, ChartBds, Max, Dt, VEG,EWs, We0). 459 460expand_charts(Heap0, Charts0, ChartBds0, Max, Dt, VEG,EWs, We) -> 461 case gb_trees:is_empty(Heap0) of 462 true -> 463 {Charts0,ChartBds0}; 464 false -> 465 {{_Dist,_,Edge},{Face,Fopp},Heap1} = gb_trees:take_smallest(Heap0), 466 ChartNum = gb_trees:get(Face, Charts0), 467 case gb_trees:lookup(Fopp, Charts0) of 468 none -> 469 Charts = gb_trees:insert(Fopp, ChartNum, Charts0), 470 ChartBds1 = gb_sets:delete(Edge, ChartBds0), 471 ChartBds = delete_inner_edges(Fopp, VEG, We, ChartBds1), 472 DistFopp = gb_trees:get(Fopp, Dt), 473 Heap = add_face_edges_to_heap(Fopp, Max-DistFopp, 474 ChartBds, Heap1, EWs, We), 475 expand_charts(Heap, Charts, ChartBds, Max, Dt, VEG,EWs, We); 476 {value,ChartNum} -> %% Fopp and Face are in same chart 477 ChartBds = case is_extremity(Edge, ChartBds0, VEG, We) of 478 false -> ChartBds0; 479 true -> gb_sets:delete_any(Edge, ChartBds0) 480 end, 481 expand_charts(Heap1, Charts0, ChartBds, Max, Dt, VEG,EWs, We); 482 {value,OtherChartNum} -> 483 MaxDistChartFace = gb_trees:get(ChartNum, Dt), 484 MaxDistChartFopp = gb_trees:get(OtherChartNum, Dt), 485 DistFace = gb_trees:get(Face, Dt), 486 DistFopp = gb_trees:get(Fopp, Dt), 487 Const = Max/4, 488 if ((MaxDistChartFace - DistFace) < Const) and 489 ((MaxDistChartFopp - DistFopp) < Const) -> 490 {Charts,ChartBds} = 491 merge_charts(ChartNum, OtherChartNum, 492 Charts0, Dt, VEG, ChartBds0, We), 493 expand_charts(Heap1, Charts, ChartBds, Max, 494 Dt, VEG,EWs, We); 495 true -> 496 expand_charts(Heap1, Charts0, ChartBds0, Max, Dt, VEG,EWs, We) 497 end 498 end 499 end. 500 501is_extremity(Edge, ChartBds, VEG, #we{es=Etab}) -> 502 #edge{vs=Va,ve=Vb} = array:get(Edge, Etab), 503 not (is_connected(gb_trees:get({Edge,Va}, VEG), ChartBds) andalso 504 is_connected(gb_trees:get({Edge,Vb}, VEG), ChartBds)). 505 506is_connected([E|Es], ChartBds) -> 507 gb_sets:is_member(E, ChartBds) orelse is_connected(Es, ChartBds); 508is_connected([], _) -> false. 509 510merge_charts(Ch1,Ch2, Charts0, Dt, VEG,ChartBds0,We) -> 511 {C1,C2} = 512 case gb_trees:get(Ch1, Dt) > gb_trees:get(Ch2, Dt) of 513 true -> 514 {Ch1, Ch2}; 515 false-> 516 {Ch2, Ch1} 517 end, 518 List = gb_trees:to_list(Charts0), 519 {Merged, ChartBds1} = 520 mapfoldl(fun({Face, Chart}, ChB) when Chart == C2 -> 521 %% Removed Merged Charts borders from 522 %% BorderEdges. 523 DelCommonEdge = 524 fun(_V,Edge,#edge{lf=LF,rf=RF},Acc) -> 525 Test = if LF==Face -> RF; true -> LF end, 526 case gb_trees:lookup(Test, Charts0) of 527 {value, C1} -> 528 case is_extremity(Edge, Acc, VEG, We) of 529 true -> 530 gb_sets:delete_any(Edge,Acc); 531 false -> 532 Acc 533 end; 534 _ -> 535 Acc 536 end 537 end, 538 {{Face, C1}, wings_face:fold(DelCommonEdge, ChB, Face, We)}; 539 (Else,ChB) -> 540 {Else,ChB} end, 541 ChartBds0, List), 542 {gb_trees:from_orddict(Merged), ChartBds1}. 543 544find_local_max(Distances, DTree, Features, FaceGraph, #we{es = Es}) -> 545 %% Remove the features from FaceGraph, edges which are a feature 546 %% shouldn't connect to opposite faces 547 FG1 = lists:foldl(fun(Edge, Tree0) -> 548 #edge{lf=LF,rf=RF} = array:get(Edge, Es), 549 LFL = gb_trees:get(LF, Tree0), 550 LFL1 = lists:delete(RF, LFL), 551 Tree1 = gb_trees:update(LF, LFL1, Tree0), 552 RFL = gb_trees:get(RF, Tree1), 553 RFL1 = lists:delete(LF, RFL), 554 gb_trees:update(RF, RFL1, Tree1) 555 end, FaceGraph, Features), 556 find_local_maximum(Distances, DTree, FG1, []). 557 558find_local_maximum([This = {Dist, Face}|Dists], Dtree0, FG, Maxs) -> 559 case gb_trees:delete_any(Face, Dtree0) of 560 Dtree0 -> 561 find_local_maximum(Dists, Dtree0, FG, Maxs); 562 Dtree1 -> 563 Dtree2 = delete_less([{gb_trees:get(Face, FG), Dist}], Dtree1, FG), 564 find_local_maximum(Dists, Dtree2, FG, [This|Maxs]) 565 end; 566find_local_maximum([], _, _FG, Maxs) -> 567 lists:reverse(Maxs). 568 569delete_less([{[Face|Rest1], Dist}|Rest2], Dtree0, FG) -> 570 case gb_trees:lookup(Face, Dtree0) of 571 none -> 572 delete_less([{Rest1, Dist}|Rest2], Dtree0, FG); 573 {value, Val} when Val > Dist -> 574 delete_less([{Rest1, Dist}|Rest2], Dtree0, FG); 575 {value, Val} -> 576 Dtree1 = gb_trees:delete(Face, Dtree0), 577 New = {gb_trees:get(Face, FG), Val}, 578 delete_less([{Rest1,Dist},New|Rest2], Dtree1, FG) 579 end; 580delete_less([{[],_}|Rest], Dt, Fg) -> 581 delete_less(Rest, Dt,Fg); 582delete_less([],Dt,_Fg) -> 583 Dt. 584 585build_face_graph([Face|Faces], We, Tree0) -> 586 Find = fun(_V, _Edge, #edge{lf=LF,rf=RF}, Acc) -> 587 New = if LF == Face -> RF; RF == Face ->LF end, 588 [New|Acc] 589 end, 590 Surround = wings_face:fold(Find, [], Face, We), 591 build_face_graph(Faces, We, gb_trees:insert(Face, Surround, Tree0)); 592build_face_graph([],_, Tree) -> 593 Tree. 594 595build_vertex_graph([{Edge, _Value}|R], We, Tree0) -> 596 #edge{vs = Vs, ve = Ve} = array:get(Edge,We#we.es), 597 Find = fun(Id, _Face, _, Acc) when Id == Edge -> 598 Acc; 599 (Id, _Face, _, Acc) -> 600 [Id|Acc] 601 end, 602 Surround0 = wings_vertex:fold(Find, [], Vs, We), 603 Tree1 = gb_trees:insert({Edge,Vs}, Surround0, Tree0), 604 Surround1 = wings_vertex:fold(Find, [], Ve, We), 605 build_vertex_graph(R, We, gb_trees:insert({Edge,Ve}, Surround1, Tree1)); 606build_vertex_graph([],_, Tree) -> 607 Tree. 608 609calc_distance(Features, FG, We = #we{fs = FsOrig}) -> 610 Faces = fun(Edge, {Dist0,Next0,Fs0}) -> 611 #edge{lf = LF, rf = RF} = array:get(Edge, We#we.es), 612 {Dist1,Next1,Fs1} = find_delete(LF,0,Dist0,Next0,Fs0,FG), 613 find_delete(RF,0,Dist1,Next1,Fs1,FG) 614 end, 615 {Dist2,Next2,Fs2} = lists:foldl(Faces, {[],[],FsOrig}, Features), 616 calc_distance(Next2, 1, Dist2, [], Fs2,FG). 617 618calc_distance([Head|Rest], Level, Dist0, Next0, Fs0,Fg) -> 619 {Dist2, Next2, Fs2} = find_delete(Head, Level, Dist0, Next0, Fs0,Fg), 620 calc_distance(Rest, Level, Dist2, Next2, Fs2,Fg); 621calc_distance([], _Level, Dist, [], _Fs, _) -> 622 lists:reverse(lists:sort(Dist)); 623calc_distance([], Level, Dist, Next, Fs, Fg) -> 624 calc_distance(Next, Level+1, Dist, [], Fs, Fg). 625 626find_delete(Face,Level,Dist0,Next0,Fs0,Fg) -> 627 case gb_trees:delete_any(Face, Fs0) of 628 Fs0 -> {Dist0,Next0,Fs0}; 629 Fs1 -> 630 Next = gb_trees:get(Face,Fg), 631 {[{Level,Face}|Dist0],Next ++ Next0,Fs1} 632 end. 633%%%%%%%%%%% End Feature detection 634 635%% 636%% The original autouv algorithm... 637%% 638 639segment_by_direction(We) -> 640 Rel = [begin 641 N = wings_face:normal(Face, We), 642 {seg_dir(N),Face} 643 end || Face <- wings_we:visible(We)], 644 segment_by_cluster(Rel, We). 645 646seg_dir({X,Y,Z}) -> 647 Max = lists:max([abs(X),abs(Y),abs(Z)]), 648 if 649 X =:= Max -> x; 650 Y =:= Max -> y; 651 Z =:= Max -> z; 652 -X =:= Max -> '-x'; 653 -Y =:= Max -> '-y'; 654 -Z =:= Max -> '-z' 655 end. 656 657segment_by_material(We) -> 658 Rel = [{Name,Face} || {Face,Name} <- wings_facemat:all(We)], 659 segment_by_cluster(Rel, We). 660 661%% segment_by_cluster([{Key,Face}], We) 662%% Group all faces by Key. 663segment_by_cluster(Rel0, #we{mirror=Mirror}=We) -> 664 Rel1 = lists:keydelete(Mirror, 2, Rel0), 665 Rel = sofs:relation(Rel1), 666 Clustered = sofs:relation_to_family(Rel), 667 Groups0 = sofs:range(Clustered), 668 Groups = sofs:to_external(Groups0), 669 Neigh = [wings_sel:face_regions(Group, We) || Group <- Groups], 670 foldl(fun(List, Acc) -> 671 [gb_sets:to_list(L) || L <- List]++Acc 672 end, [], Neigh). 673 674%%% 675%%% Map back to the original vertex. 676%%% 677 678map_vertex(V0, Vmap) -> 679 case gb_trees:lookup(V0, Vmap) of 680 none -> V0; 681 {value,V} -> V 682 end. 683 684%%% 685%%% Map back to the original edge. 686%%% 687 688map_edge(E0, Emap) -> 689 case gb_trees:lookup(E0, Emap) of 690 none -> E0; 691 {value,E} -> E 692 end. 693 694%%% 695%%% Cutting along hard edges. 696%%% 697 698cut_model(Charts, Cuts0, We0) -> 699 We = wings_va:remove(all, We0), 700 Cuts = gb_sets:to_list(Cuts0), 701 cut_model_1(Charts, Cuts, We#we{mirror=none}, length(Charts), []). 702 703cut_model_1([Fs|Cs], Cuts, OrigWe, Id, Acc) -> 704 We = cut_one_chart(Fs, Cuts, OrigWe#we{id=Id}), 705 cut_model_1(Cs, Cuts, OrigWe, Id-1, [We|Acc]); 706cut_model_1([], _, _, _, Acc) -> Acc. 707 708cut_one_chart(Keep0, Cuts, We0) -> 709 {InnerEdges,OuterEdges} = wings_face:inner_outer_edges(Keep0, We0), 710 Keep = gb_sets:from_list(Keep0), 711 Map0 = gb_trees:empty(), 712 {We1,Map1} = cut_shared_vertices(Keep, OuterEdges, We0, Map0), 713 {We2,Vmap} = cut_edges(Keep0, InnerEdges, Cuts, We1, Map1), 714 %% Dissolve unneeded faces and also hide them. 715 #we{fs=Ftab} = We3 = wpa:face_dissolve_complement(Keep0, We2), 716 Hidden = ordsets:subtract(gb_trees:keys(Ftab), Keep0), 717 We4 = wings_we:hide_faces(Hidden, We3), 718 %% Create edge map and finish We. 719 Me = wings_we:new_items_as_ordset(edge, We1, We4), 720 Emap = make_emap(Me, Vmap, We0, We4, []), 721 We4#we{name=#ch{vmap=Vmap,me=Me,emap=Emap}}. 722 723make_emap([ME|T], Vmap, We0, #we{es=Etab}=We, Acc) -> 724 case array:get(ME, Etab) of 725 undefined -> 726 make_emap(T, Vmap, We0, We, Acc); 727 #edge{vs=Va0,ve=Vb0} -> 728 Va = map_vertex(Va0, Vmap), 729 case map_vertex(Vb0, Vmap) of 730 Va -> 731 make_emap(T, Vmap, We0, We, Acc); 732 Vb -> 733 E = wings_vertex:until( 734 fun(E, _, Rec, A) -> 735 case Rec of 736 #edge{vs=Va,ve=Vb} -> E; 737 #edge{vs=Vb,ve=Va} -> E; 738 _ -> A 739 end 740 end, none, Va, We0), 741 case E of 742 none -> make_emap(T, Vmap, We0, We, Acc); 743 _ -> make_emap(T, Vmap, We0, We, [{ME,E}|Acc]) 744 end 745 end 746 end; 747make_emap([], _, _, _, Acc) -> gb_trees:from_orddict(sort(Acc)). 748 749cut_shared_vertices(Faces, Es, #we{es=Etab}=We0, InvVmap0) -> 750 VsEs0 = foldl(fun(E, A) -> 751 #edge{vs=Va,ve=Vb} = array:get(E, Etab), 752 [{Va,E},{Vb,E}|A] 753 end, [], Es), 754 VsEs = sofs:relation(VsEs0), 755 F = sofs:relation_to_family(VsEs), 756 Shared0 = sofs:specification({external,fun({_,L}) -> 757 length(L) > 2 758 end}, F), 759 Shared = sofs:to_external(sofs:domain(Shared0)), 760 foldl(fun(V, A) -> 761 do_cut_shared(V, Faces, A) 762 end, {We0,InvVmap0}, Shared). 763 764do_cut_shared(V, Faces, {#we{next_id=Wid}=We0,Ivmap}) -> 765 Fs = wings_vertex:fold( 766 fun(_, Face, _, A) -> 767 case gb_sets:is_member(Face, Faces) of 768 false -> A; 769 true -> [Face|A] 770 end 771 end, [], V, We0), 772 We = wings_vertex_cmd:bevel_vertex(V, We0), 773 do_cut_shared_1(Fs, V, Wid, We, Ivmap). 774 775do_cut_shared_1([F|Fs], V, Wid, We0, Map0) -> 776 {We,Map} = wings_face:fold( 777 fun(_, E, #edge{vs=Va}, {W0,M}) when E >= Wid -> 778 W = wings_collapse:collapse_edge(E, Va, W0), 779 {W,add_new_vs(V, [Va], M)}; 780 (_, _, _, A) -> A 781 end, {We0,Map0}, F, We0), 782 do_cut_shared_1(Fs, V, Wid, We, Map); 783do_cut_shared_1([], _, _, We, Map) -> {We,Map}. 784 785cut_edges(Faces, Inner, Cuts0, We, Map) -> 786 case ordsets:intersection(Inner, Cuts0) of 787 [] -> {We,Map}; 788 Cuts -> cut_edges_1(Faces, Cuts, We, Map) 789 end. 790 791cut_edges_1(Faces, Cuts, We0, Map0) -> 792 Vs = wings_edge:to_vertices(Cuts, We0), 793 {We1,Map1} = bevel_cut_vs(Vs, We0, Map0), 794 CutEdges = edges_to_cut(Cuts, We1), 795 {We2,Map} = cut_new_edges(CutEdges, We1, Map1), 796 MaybeRem = wings_we:new_items_as_ordset(edge, We0, We2), 797 We3 = connect_edges(Cuts, We2), 798 We = cut_cleanup(Faces, MaybeRem, We3), 799 {We,Map}. 800 801bevel_cut_vs([V|Vs], We0, Map0) -> 802 We = wings_vertex_cmd:bevel_vertex(V, We0), 803 NewVs = wings_we:new_items_as_ordset(vertex, We0, We), 804 Map = add_new_vs(V, NewVs, Map0), 805 bevel_cut_vs(Vs, We, Map); 806bevel_cut_vs([], We, Map) -> {We,Map}. 807 808edges_to_cut(Es, #we{es=Etab}) -> 809 edges_to_cut_1(Es, Etab, []). 810 811edges_to_cut_1([E|Es], Etab, Acc) -> 812 #edge{ltpr=Lp,ltsu=Lu,rtpr=Rp,rtsu=Ru} = array:get(E, Etab), 813 edges_to_cut_1(Es, Etab, [Lp,Lu,Rp,Ru|Acc]); 814edges_to_cut_1([], _, Es) -> 815 edges_to_cut_2(sort(Es), []). 816 817edges_to_cut_2([E,E|Es], Acc) -> 818 edges_to_cut_2(Es, [E|Acc]); 819edges_to_cut_2([_|Es], Acc) -> 820 edges_to_cut_2(Es, Acc); 821edges_to_cut_2([], Acc) -> 822 ordsets:from_list(Acc). 823 824cut_new_edges([Edge|Es], #we{es=Etab}=We0, Map0) -> 825 #edge{vs=Va,ve=Vb} = array:get(Edge, Etab), 826 Pos = wpa:vertex_pos(Va, We0), 827 {We,NewV} = wings_edge:screaming_cut(Edge, Pos, We0), 828 Map = add_new_vs(Vb, [NewV], add_new_vs(Va, [NewV], Map0)), 829 cut_new_edges(Es, We, Map); 830cut_new_edges([], We, Map) -> {We,Map}. 831 832connect_edges([E|Es], #we{es=Etab}=We0) -> 833 #edge{vs=Va,ve=Vb,lf=Lf,ltpr=Lp,ltsu=Lu, 834 rf=Rf,rtpr=Rp,rtsu=Ru} = array:get(E, Etab), 835 LpV = other_vertex(Vb, Lp, Etab), 836 LuV = other_vertex(Va, Lu, Etab), 837 RpV = other_vertex(Va, Rp, Etab), 838 RuV = other_vertex(Vb, Ru, Etab), 839 {We1,_} = wings_vertex:force_connect(LpV, LuV, Lf, We0), 840 {We,_} = wings_vertex:force_connect(RpV, RuV, Rf, We1), 841 connect_edges(Es, We); 842connect_edges([], We) -> We. 843 844other_vertex(V, Edge, Etab) -> 845 wings_vertex:other(V, array:get(Edge, Etab)). 846 847cut_cleanup(Faces, MaybeRemove, We) -> 848 Es = ordsets:intersection(MaybeRemove, 849 wings_face:to_edges(Faces, We)), 850 foldl(fun(E, W) -> 851 wings_collapse:fast_collapse_edge(E, W) 852 end, We, Es). 853 854add_new_vs(OldV, NewVs, Map) -> 855 foldl(fun(NewV, M) -> add_new_vs_1(OldV, NewV, M) end, Map, NewVs). 856 857add_new_vs_1(To, From, Map) -> 858 case gb_trees:lookup(To, Map) of 859 none -> gb_trees:enter(From, To, Map); 860 {value,NewTo} -> add_new_vs_1(NewTo, From, Map) 861 end. 862 863%% normalize_charts(Charts, Cuts, We) -> {Charts',Cuts'} 864%% Possibly split charts that are divided into several non-connected 865%% components by edges in Cuts. Remove any edges in Cuts that goes 866%% along the boundary between two charts. 867normalize_charts(Charts, Cuts, We) -> 868 normalize_charts(Charts, Cuts, We, []). 869 870normalize_charts([C0|Cs], Cuts, We, Acc0) -> 871 C = gb_sets:from_list(C0), 872 Acc = normalize_chart(C, Cuts, We, Acc0), 873 normalize_charts(Cs, Cuts, We, Acc); 874normalize_charts([], Cuts0, We, Charts) -> 875 AllInner0 = lists:concat([wings_face:inner_edges(C, We) || C <- Charts]), 876 AllInner = gb_sets:from_list(AllInner0), 877 Cuts = gb_sets:intersection(Cuts0, AllInner), 878 {Charts,Cuts}. 879 880normalize_chart(Faces, Cuts, We, Acc) -> 881 find_reachable(Faces, We, collect_fun(Cuts), Acc). 882 883find_reachable(Faces0, We, Coll, Acc) -> 884 case gb_sets:is_empty(Faces0) of 885 true -> Acc; 886 false -> 887 {Face,Faces1} = gb_sets:take_smallest(Faces0), 888 Ws = [Face], 889 {Reg,Faces} = collect_reachable(Ws, We, Coll, [], Faces1), 890 find_reachable(Faces, We, Coll, [Reg|Acc]) 891 end. 892 893collect_reachable([_|_]=Ws0, We, Coll, Reg0, Faces0) -> 894 Reg = Ws0++Reg0, 895 {Ws,Faces} = wings_face:fold_faces(Coll, {[],Faces0}, Ws0, We), 896 collect_reachable(Ws, We, Coll, Reg, Faces); 897collect_reachable([], _, _, Reg, Faces) -> 898 {sort(Reg),Faces}. 899 900collect_fun(Cuts) -> 901 fun(Face, _, Edge, Rec, {Ws,Faces}=A) -> 902 Of = case Rec of 903 #edge{lf=Face,rf=Of0} -> Of0; 904 #edge{rf=Face,lf=Of0} -> Of0 905 end, 906 case gb_sets:is_member(Of, Faces) andalso 907 not gb_sets:is_member(Edge, Cuts) of 908 true -> {[Of|Ws],gb_sets:delete(Of, Faces)}; 909 false -> A 910 end 911 end. 912 913%%% 914%%% Build a map [F|V] => UV. 915%%% 916 917fv_to_uv_map(object,#we{fs=Ftab,holes=Holes0}=We) -> 918 AllFsEs = sofs:relation(gb_trees:to_list(Ftab)), 919 Holes = sofs:set(Holes0), 920 FsEs = sofs:drestriction(AllFsEs, Holes), 921 fvuvmap_1(sofs:to_external(FsEs), We, [], []); 922fv_to_uv_map(Faces0,#we{fs=Ftab}=We) -> 923 AllFsEs = sofs:relation(gb_trees:to_list(Ftab)), 924 Fs = sofs:set(gb_sets:to_list(Faces0)), 925 FsEs = sofs:restriction(AllFsEs,Fs), 926 fvuvmap_1(sofs:to_external(FsEs), We, [], []). 927 928fvuvmap_1([{F,E}|FsEs], We, FaceAcc, Acc) -> 929 case uv_info(F, E, We) of 930 error -> fvuvmap_1(FsEs, We, FaceAcc, Acc); 931 Info -> fvuvmap_1(FsEs, We, [F|FaceAcc], Info++Acc) 932 end; 933fvuvmap_1([], _, FaceAcc, Acc) -> 934 {FaceAcc,gb_trees:from_orddict(sort(Acc))}. 935 936uv_info(F, E, We) -> 937 uv_info_1(wings_va:face_attr([vertex|uv], F, E, We), F, []). 938 939uv_info_1([[V|{_,_}=UV]|T], F, Acc) -> 940 uv_info_1(T, F, [{[F|V],UV}|Acc]); 941uv_info_1([[V|_]|T], F, Acc) -> 942 %% No UV coordinates for this vertex. 943 uv_info_1(T, F, [{[F|V],none}|Acc]); 944uv_info_1([_|_], _, _) -> error; 945uv_info_1([], _, Acc) -> Acc. 946 947%%% 948%%% Given a model having UV coordinates, partition it into charts. 949%%% 950 951uv_to_charts(Faces0, Dict, We) -> 952 Faces = gb_sets:from_list(Faces0), 953 Coll = collect_chart_fun(Dict), 954 Cs = uv_to_charts_1(Faces, We, Coll, []), 955 Cuts = chart_cuts(Cs, We, Dict, []), 956 {Cs,Cuts}. 957 958uv_to_charts_1(Faces0, We, Coll, Acc) -> 959 case gb_sets:is_empty(Faces0) of 960 true -> Acc; 961 false -> 962 {Face,Faces1} = gb_sets:take_smallest(Faces0), 963 Ws = [Face], 964 {Reg,Faces} = collect_chart(Ws, We, Coll, [], Faces1), 965 uv_to_charts_1(Faces, We, Coll, [Reg|Acc]) 966 end. 967 968collect_chart([_|_]=Ws0, We, Coll, Reg0, Faces0) -> 969 Reg = Ws0++Reg0, 970 {Ws,Faces} = wings_face:fold_faces(Coll, {[],Faces0}, Ws0, We), 971 collect_chart(Ws, We, Coll, Reg, Faces); 972collect_chart([], _, _, Reg, Faces) -> 973 {sort(Reg),Faces}. 974 975collect_chart_fun(Dict) -> 976 fun(Face, _, _, Rec, {Ws,Faces}=A) -> 977 Of = case Rec of 978 #edge{lf=Face,rf=Of0} -> Of0; 979 #edge{rf=Face,lf=Of0} -> Of0 980 end, 981 case gb_sets:is_member(Of, Faces) andalso 982 not is_cutting_edge(Rec, Dict) of 983 true -> {[Of|Ws],gb_sets:delete(Of, Faces)}; 984 false -> A 985 end 986 end. 987 988chart_cuts([C|Cs], #we{es=Etab}=We, D, Acc0) -> 989 Inner = wings_face:inner_edges(C, We), 990 Acc = chart_cuts_1(Inner, Etab, D, Acc0), 991 chart_cuts(Cs, We, D, Acc); 992chart_cuts([], _, _, Acc) -> gb_sets:from_list(Acc). 993 994chart_cuts_1([E|Es], Etab, D, Acc) -> 995 case is_cutting_edge(array:get(E, Etab), D) of 996 false -> chart_cuts_1(Es, Etab, D, Acc); 997 true -> chart_cuts_1(Es, Etab, D, [E|Acc]) 998 end; 999chart_cuts_1([], _, _, Acc) -> Acc. 1000 1001is_cutting_edge(#edge{vs=Va,ve=Vb,lf=Lf,rf=Rf}, D) -> 1002 gb_trees:get([Lf|Va], D) =/= gb_trees:get([Rf|Va], D) orelse 1003 gb_trees:get([Lf|Vb], D) =/= gb_trees:get([Rf|Vb], D). 1004