1%% 2%% wings_extrude_face.erl -- 3%% 4%% This module contains the Extrude command for faces and face regions. 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_extrude_face). 15-export([faces/2,regions/2]). 16 17-include("wings.hrl"). 18-import(lists, [foldl/3,foreach/2,last/1,reverse/2,sort/1,merge/1]). 19 20%%% 21%%% Extrusion of faces individually (used by Extrude, Inset, Bevel). 22%%% 23 24faces([], We) -> 25 We; 26faces(Faces, We) when is_list(Faces) -> 27 inner_extrude(Faces, We); 28faces(Faces, We) -> 29 faces(gb_sets:to_list(Faces), We). 30 31inner_extrude([Face|Faces], #we{next_id=AnEdge,fs=Ftab0}=We0) -> 32 Mat = wings_facemat:face(Face, We0), 33 Ftab = gb_trees:update(Face, AnEdge, Ftab0), 34 We1 = We0#we{fs=Ftab}, 35 Edges = inner_extrude_edges(Face, We0), 36 NumVs = length(Edges), 37 {Ids,We2} = wings_we:new_wrap_range(NumVs, 2, We1), 38 PrevEdge = last(Edges), 39 We3 = inner_extrude_1(Edges, PrevEdge, Face, Mat, Ids, We2), 40 We = case wings_va:any_attributes(We3) of 41 false -> We3; 42 true -> inner_extrude_attrs(Edges, PrevEdge, Face, Ids, We2, We3) 43 end, 44 inner_extrude(Faces, We); 45inner_extrude([], We) -> We. 46 47inner_extrude_edges(Face, We) -> 48 wings_face:fold(fun(_, E, _Rec, A) -> [E|A] end, [], Face, We). 49 50inner_extrude_1([Edge|Es], PrevEdge, Face, Mat, Ids0, We0) -> 51 PrevHor = wings_we:id(2-2, Ids0), 52 PrevFace = PrevHor, 53 54 HorEdge = wings_we:id(2, Ids0), 55 VertEdge = HorEdge + 1, 56 V = NewFace = HorEdge, 57 58 NextHor = wings_we:id(2+2, Ids0), 59 NextVert = NextHor + 1, 60 NextV = NextHor, 61 62 Ids = wings_we:bump_id(Ids0), 63 #we{fs=Ftab0,es=Etab0,vc=Vct0,vp=Vtab0} = We0, 64 65 Erec0 = array:get(Edge, Etab0), 66 Erec = case Erec0 of 67 #edge{lf=Face,vs=Va}=Erec0 -> 68 Erec0#edge{lf=NewFace,ltsu=VertEdge,ltpr=NextVert}; 69 #edge{rf=Face,ve=Va}=Erec0 -> 70 Erec0#edge{rf=NewFace,rtsu=VertEdge,rtpr=NextVert} 71 end, 72 Etab1 = array:set(Edge, Erec, Etab0), 73 74 VertEdgeRec = #edge{vs=Va,ve=V,lf=PrevFace,rf=NewFace, 75 ltsu=PrevEdge,ltpr=PrevHor, 76 rtsu=HorEdge,rtpr=Edge}, 77 Etab2 = array:set(VertEdge, VertEdgeRec, Etab1), 78 79 Etab = array:set(HorEdge, 80 #edge{vs=NextV,ve=V, 81 lf=NewFace,rf=Face, 82 ltsu=NextVert,ltpr=VertEdge, 83 rtsu=PrevHor,rtpr=NextHor}, Etab2), 84 85 Vct = array:set(V, HorEdge, Vct0), 86 Pos = array:get(Va, Vtab0), 87 Vtab = array:set(V, Pos, Vtab0), 88 89 Ftab = gb_trees:insert(NewFace, NewFace, Ftab0), 90 We1 = wings_facemat:assign(Mat, [NewFace], We0), 91 We = We1#we{fs=Ftab,es=Etab,vc=Vct,vp=Vtab}, 92 93 inner_extrude_1(Es, Edge, Face, Mat, Ids, We); 94inner_extrude_1([], _PrevEdge, _Face, _Mat, _Ids, We) -> We. 95 96inner_extrude_attrs([Edge|Es], PrevEdge, Face, Ids0, OrigWe, We0) -> 97 PrevHor = wings_we:id(2-2, Ids0), 98 HorEdge = wings_we:id(2, Ids0), 99 VertEdge = HorEdge + 1, 100 NewFace = HorEdge, 101 102 Ids = wings_we:bump_id(Ids0), 103 104 %% Set the vertex attributes. 105 InsideAttr = wings_va:edge_attrs(Edge, Face, OrigWe), 106 OtherFace = {other,Face}, 107 OutsideAttr = wings_va:edge_attrs(Edge, OtherFace, OrigWe), 108 OtherOutsideAttr = wings_va:edge_attrs(PrevEdge, OtherFace, OrigWe), 109 We1 = wings_va:set_edge_attrs(Edge, NewFace, OutsideAttr, We0), 110 We2 = wings_va:set_edge_attrs(HorEdge, right, InsideAttr, We1), 111 We3 = wings_va:set_edge_attrs(PrevHor, left, InsideAttr, We2), 112 We4 = wings_va:set_edge_attrs(VertEdge, right, InsideAttr, We3), 113 We = wings_va:set_edge_attrs(VertEdge, left, OtherOutsideAttr, We4), 114 115 inner_extrude_attrs(Es, Edge, Face, Ids, OrigWe, We); 116inner_extrude_attrs([], _PrevEdge, _Face, _Ids, _OrigWe, We) -> We. 117 118%%% 119%%% Extrude entire regions (does NOT work for single faces). 120%%% 121 122regions(Rs, We) -> 123 regions_1(Rs, [], We). 124 125regions_1([Faces|Rs], CollapseEs0, We0) -> 126 {We,CollapseEs} = region(Faces, CollapseEs0, We0), 127 regions_1(Rs, CollapseEs, We); 128regions_1([], CollapseEs, We) -> 129 wings_collapse:collapse_edges(CollapseEs, We). 130 131region(Faces, CollapseEs, #we{es=Etab}=We0) -> 132 ?ASSERT(gb_sets:size(Faces) > 1), 133 Edges0 = wings_face:outer_edges(Faces, We0), 134 G = digraph:new(), 135 foreach(fun(Edge) -> 136 digraph_edge(G, Faces, array:get(Edge, Etab)) 137 end, Edges0), 138 Vs0 = digraph:vertices(G), 139 Vs1 = sofs:relation(Vs0), 140 Vs = sofs:to_external(sofs:domain(Vs1)), 141 Edges = gb_sets:from_list(Edges0), 142 We = foldl(fun(V, A) -> 143 new_vertices(V, G, Edges, Faces, A) 144 end, We0, Vs), 145 WeEdges = connect(G, CollapseEs, We), 146 digraph:delete(G), 147 WeEdges. 148 149new_vertices(V, G, Edges, Faces, We0) -> 150 Pos = wings_vertex:pos(V, We0), 151 wings_vertex:fold( 152 fun(Edge, _, _, #we{es=Etab}=W0) -> 153 case gb_sets:is_member(Edge, Edges) of 154 true -> W0; 155 false -> 156 #edge{lf=Lf} = array:get(Edge, Etab), 157 case gb_sets:is_member(Lf, Faces) of 158 true -> 159 {We,NewV} = wings_edge:fast_cut(Edge, Pos, W0), 160 NewE = NewV, 161 Rec = get_edge_rec(V, NewV, Edge, NewE, We), 162 digraph_edge(G, Faces, Rec), 163 We; 164 false -> W0 165 end 166 end 167 end, We0, V, We0). 168 169get_edge_rec(Va, Vb, EdgeA, EdgeB, #we{es=Etab}) -> 170 case array:get(EdgeA, Etab) of 171 #edge{vs=Va,ve=Vb}=Rec -> Rec; 172 #edge{vs=Vb,ve=Va}=Rec -> Rec; 173 _Other -> array:get(EdgeB, Etab) 174 end. 175 176digraph_edge(G, Faces, #edge{lf=Lf,rf=Rf,vs=Va,ve=Vb}) -> 177 case gb_sets:is_member(Lf, Faces) of 178 true -> digraph_insert(G, Va, Vb, Lf); 179 false -> ok 180 end, 181 case gb_sets:is_member(Rf, Faces) of 182 true -> digraph_insert(G, Vb, Va, Rf); 183 false -> ok 184 end. 185 186digraph_insert(G, Va0, Vb0, Face) -> 187 Va = {Va0,Face}, 188 Vb = {Vb0,Face}, 189 digraph:add_vertex(G, Va), 190 digraph:add_vertex(G, Vb), 191 digraph:add_edge(G, Va, Vb). 192 193connect(G, CollapseEs, We0) -> 194 Cs = get_edge_chains(G), 195 foldl(fun(C, {W,A}) -> 196 connect_1(C, W, A) 197 end, {We0,CollapseEs}, Cs). 198 199connect_1(C, We0, Acc) -> 200 case C of 201 [Va,_,Vb] -> 202 Face = get_face(Va, Vb, We0), 203 {We,NewEdge} = wings_vertex:force_connect(Vb, Va, Face, We0), 204 {We,[NewEdge|Acc]}; 205 [Va|Path] -> 206 {connect_inner(Va, Path, We0),Acc} 207 end. 208 209get_edge_chains(G) -> 210 Vs = digraph:source_vertices(G), 211 get_edge_chains(G, Vs, []). 212 213get_edge_chains(G, [V|Vs], Acc) -> 214 Chain = collect_chain(G, V, []), 215 get_edge_chains(G, Vs, [Chain|Acc]); 216get_edge_chains(_, [], Acc) -> Acc. 217 218collect_chain(G, {V,_}=Va, Acc) -> 219 case digraph:out_neighbours(G, Va) of 220 [] -> reverse(Acc, [V]); 221 [Vb] -> collect_chain(G, Vb, [V|Acc]) 222 end. 223 224connect_inner(Current0, [_|[B,_,_|_]=Next], We0) -> 225 {We,Current} = connect_one_inner(Current0, B, We0), 226 connect_inner(Current, Next, We); 227connect_inner(Current, [_|[_,_]=Next], We) -> 228 connect_inner(Current, Next, We); 229connect_inner(Current, [_,Last], We0) -> 230 Face = get_face(Current, Last, We0), 231 {We,_} = wings_vertex:force_connect(Last, Current, Face, We0), 232 We. 233 234connect_one_inner(Current, B, We0) -> 235 Face = get_face(Current, B, We0), 236 {We1,Edge} = wings_vertex:force_connect(B, Current, Face, We0), 237 Pos = wings_vertex:pos(B, We1), 238 wings_edge:fast_cut(Edge, Pos, We1). 239 240get_face(Va, Vb, We) -> 241 Vs = [Va,Vb], 242 per_face(Vs, Vs, We, []). 243 244per_face([V|Vs], OrigVs, We, Acc) -> 245 Fs = wings_vertex:fold( 246 fun(_, Face, _, A) -> 247 [Face|A] 248 end, [], V, We), 249 per_face(Vs, OrigVs, We, [Fs|Acc]); 250per_face([], OrigVs, We, Acc) -> 251 R = sofs:from_term(Acc, [[face]]), 252 case sofs:to_external(sofs:intersection(R)) of 253 [Face] -> Face; 254 Faces -> choose_face(Faces, OrigVs, We) 255 end. 256 257choose_face([Face|Faces], [Va,Vb], We) -> 258 D = vertex_dist(Face, Va, Vb, We), 259 choose_face_1(Faces, Va, Vb, We, D, Face). 260 261choose_face_1([Face|Faces], Va, Vb, We, OldDist, OldFace) -> 262 case vertex_dist(Face, Va, Vb, We) of 263 Dist when Dist < OldDist -> 264 choose_face_1(Faces, Va, Vb, We, Dist, Face); 265 _Dist -> 266 choose_face_1(Faces, Va, Vb, We, OldDist, OldFace) 267 end; 268choose_face_1([], _, _, _, _, Face) -> Face. 269 270vertex_dist(Face, Va, Vb, We) -> 271 NumVerts = wings_face:vertices(Face, We), 272 Iter0 = wings_face:iterator(Face, We), 273 Iter = wings_face:skip_to_cw(Va, Iter0), 274 vertex_dist_1(Iter, Vb, NumVerts, 1). 275 276vertex_dist_1(Iter0, V, NumVerts, D) -> 277 case wings_face:next_cw(Iter0) of 278 {V,_,_,_} -> 279 if 280 D > NumVerts div 2 -> NumVerts-D; 281 true -> D 282 end; 283 {_,_,_,Iter} -> vertex_dist_1(Iter, V, NumVerts, D+1) 284 end. 285