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