1%%%------------------------------------------------------------------- 2%%% File : auv_placement.erl 3%%% Author : Dan Gudmundsson <dgud@erix.ericsson.se> 4%%% Description : Algotrihms for placing charts on texture. 5%%% 6%%% Created : 7 Oct 2002 by Dan Gudmundsson <dgud@erix.ericsson.se> 7%%%------------------------------------------------------------------- 8%% Copyright (c) 2001-2011 Dan Gudmundsson 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_placement). 15 16-include_lib("src/wings.hrl"). 17-include("auv.hrl"). 18 19-export([place_areas/1,rotate_area/2,group_edge_loops/2]). 20 21-import(lists, [max/1,sort/1,map/2,reverse/1]). 22 23%% Returns a gb_tree with areas... 24place_areas(Areas0) -> 25 Rotate = fun(#we{id=Id,name=Ch0}=We0, BBs) -> 26 {{Dx,Dy}=Size,Vs} = center(We0), 27 Ch = Ch0#ch{size=Size}, 28 We = We0#we{vp=array:from_orddict(Vs),name=Ch}, 29 {We,[{Dx,Dy,Id}|BBs]} 30 end, 31 {Areas1,Sizes0} = lists:mapfoldl(Rotate, [], Areas0), 32% ?DBG("~p~n",[Sizes0]), 33 {Positions0, Max} = fill(Sizes0, [0,0]), 34% ?DBG("~p~n",[Positions0]), 35 Scale = 1 / max(Max), 36 move_and_scale_charts(Areas1, lists:sort(Positions0), Scale, []). 37 38center(#we{vp=VTab}) -> 39 VL = array:sparse_to_orddict(VTab), 40 {{_,Xmin},{_,Xmax},{_,Ymin},{_,Ymax}} = auv_util:maxmin(VL), 41 Dx = Xmax - Xmin, 42 Dy = Ymax - Ymin, 43 CX = Xmin + Dx / 2, 44 CY = Ymin + Dy / 2, 45 Vs = auv_util:moveAndScale(VL, -CX, -CY, 1, []), 46 {{Dx,Dy}, Vs}. 47 48fill(Areas, [0,0]) -> %% First time 49 Map = fun({W,H,Id}) when W > H -> 50 {{W,width}, H, Id}; 51 ({W,H,Id}) -> 52 {{H,height}, W, Id} 53 end, 54 SL0 = sort(map(Map, Areas)), 55 [First|SL] = reverse(SL0), 56 {Res,PX,PY} = insert(First, 0,0), 57 fill(SL, PX,PY, [Res]); 58fill(Areas, [PX,PY]) -> 59 Map = fun({W,H,Id}) when W > H -> 60 {{W,width}, H, Id}; 61 ({W,H,Id}) -> 62 {{H,height}, W, Id} 63 end, 64 SL0 = sort(map(Map, Areas)), 65 SL = reverse(SL0), 66 fill(SL, PX,PY, []). 67 68fill([], MaxX, MaxY, Res) -> 69 {Res, [MaxX,MaxY]}; 70fill([Biggest|SL], MX0, MY0, Res0) -> 71 {W0,H0} = case Biggest of {{W,width},H,_} -> {W,H}; {{H,height},W,_} -> {W,H} end, 72 %% Calc possible places 73 A1 = max([(W0 + MX0), max([H0,MY0])]), %% Build Element to the right 74 A2 = max([max([W0, MX0]), (MY0 + H0)]), %% Build Element on the top 75 if 76 A1 < A2 -> 77 {New, MX1, MY1} = insert(Biggest, MX0, 0), 78 if MY0 >= MY1 -> 79 {SL2, Res1} = fill_area(SL, W0,MY0-H0, MX0,MY1, [], [New|Res0]), 80 fill(SL2, MX1, MY0, Res1); 81 MY1 > MY0 -> 82 {SL2, Res1} = fill_area(SL, MX0,MY1-MY0, 0,MY0, [], [New|Res0]), 83 fill(SL2, MX1, MY1, Res1) 84 end; 85 true -> 86 {New, MX1, MY1} = insert(Biggest, 0, MY0), 87 if MX0 >= MX1 -> 88 {SL2, Res1} = fill_area(SL, MX0-W0,H0, MX1,MY0, [], [New|Res0]), 89 fill(SL2, MX0, MY1, Res1); 90 MX1 > MX0 -> 91 {SL2, Res1} = fill_area(SL, MX1-MX0,MY0, MX0,0, [], [New|Res0]), 92 fill(SL2, MX1, MY1, Res1) 93 end 94 end. 95 96insert({{X,width}, Y, I},XP,YP) -> 97 New = {I, {XP+X/2, YP+Y/2}}, 98 {New, XP+X, YP+Y}; 99insert({{Y,height}, X, I},XP,YP) -> 100 New = {I, {XP+X/2, YP+Y/2}}, 101 {New, XP+X, YP+Y}. 102 103fill_area([Sel = {{X0,width},Y0,_}|SL], MX, MY, XP,YP, UU, Res0) 104 when X0 =< MX, Y0 =< MY -> 105 {New,_,_} = insert(Sel,XP,YP), 106 {SL2, Res1}= fill_area(SL, MX-X0, MY, XP+X0, YP, [], Res0), 107 fill_area(SL2, X0, MY-Y0, XP, YP+Y0, UU, [New|Res1]); 108fill_area([Sel={{Y0,height},X0,_}|SL], MX, MY, XP,YP,UU, Res0) 109 when X0 =< MX, Y0 =< MY -> 110 {New,_,_} = insert(Sel,XP,YP), 111 {SL2, Res1} = fill_area(SL, MX,MY-Y0, XP, YP+Y0,[], Res0), 112 fill_area(SL2, MX-X0, Y0, XP+X0, YP, UU, [New|Res1]); 113fill_area([Nouse|SL], MaxX, MaxY, XP,YP, Unused, Res) -> 114 fill_area(SL,MaxX,MaxY, XP,YP, [Nouse|Unused], Res); 115fill_area([], _,_, _,_, Unused,Res) -> 116 {reverse(Unused), Res}. 117 118%%%%%%%%%%%%%%%% 119move_and_scale_charts([We0|RA], [{C,{Cx,Cy}}|RP], S, Acc) -> 120 Transform0 = e3d_mat:scale(S, S, 0.0), 121 Transform = e3d_mat:mul(e3d_mat:translate(S*Cx, S*Cy, 0.0), Transform0), 122 We = wings_we:transform_vs(Transform, We0), 123 move_and_scale_charts(RA, RP, S, [{C,We}|Acc]); 124move_and_scale_charts([], [], _, Acc) -> Acc. 125 126rotate_area(Vs, #we{vp=Orig}=We) -> 127 VTab = array:from_orddict(lists:sort(Vs)), 128 Fs = wings_we:visible(We), 129 [{_,Eds3}|_] = group_edge_loops(Fs,We), 130 Eds4 = make_convex(reverse(Eds3), [], VTab), 131 [#be{vs=LV1,ve=LV2,dist=_Dist}|_] = lists:reverse(lists:keysort(5, Eds4)), 132 LV1P = array:get(LV1, VTab), 133 LV2P = array:get(LV2, VTab), 134 O1 = array:get(LV1, Orig), 135 O2 = array:get(LV2, Orig), 136 Normal = {NX,NY,NZ} = 137 try auv_mapping:chart_normal(Fs,We) catch throw:_ -> {0.0,0.0,1.0} end, 138 ANX = abs(NX), ANY = abs(NY), ANZ = abs(NZ), 139 Csys = if ANX > ANY, ANX > ANZ -> csys(NX, Normal, {0.0,0.0,-1.0}); 140 ANZ > ANY -> csys(NZ, Normal, {1.0,0.0,0.0}); 141 true -> csys(NY, Normal, {1.0,0.0,0.0}) 142 end, 143 O11 = mul_point(O1, Csys), 144 O12 = mul_point(O2, Csys), 145 RealAngle = math:atan2(element(2,O12)-element(2,O11), 146 element(1,O12)-element(1,O11)), 147 Angle = math:atan2(element(2,LV2P)-element(2,LV1P), 148 element(1,LV2P)-element(1,LV1P)), 149 Rotate = Angle - RealAngle, 150 ?DBG("Angle ~p~n P1 ~p~n P2 ~p~n", 151 [Angle*180/math:pi(), 152 {auv_segment:map_vertex(LV1, (We#we.name)#ch.vmap), LV1P}, 153 {auv_segment:map_vertex(LV2, (We#we.name)#ch.vmap), LV2P}]), 154 ?DBG("Real ~p ~p~n ~p~n RAngle ~p => ~p~n", 155 [O1,O2,{O11,O12},RealAngle*180/math:pi(),Rotate*180/math:pi()]), 156 Rot = e3d_mat:rotate(-(Rotate*180/math:pi()), {0.0,0.0,1.0}), 157 Res = [{Id,e3d_mat:mul_point(Rot, Vtx)} || {Id,Vtx} <- Vs], 158 %% ?DBG("Rot angle ~p ~p~n", [Angle*180/math:pi(), Res]), 159 Res. 160 161mul_point(P, {X,Y,Z}) -> 162 {e3d_vec:dot(P,X), e3d_vec:dot(P,Y),e3d_vec:dot(P,Z)}. 163 164csys(Dir0,Z,X0) -> 165 X1 = if Dir0 > 0.0 -> X0; 166 true ->e3d_vec:neg(X0) 167 end, 168 Y = e3d_vec:cross(Z,X1), 169 X = e3d_vec:cross(Y,Z), 170 {e3d_vec:norm(X),e3d_vec:norm(Y),Z}. 171 172-define(PI, 3.141592). 173-define(ALMOSTPI, (?PI-(0.5/180*?PI))). %% cluster together straight lines 174 175make_convex([This, Next|Rest], Acc, Vs) -> 176 case calc_dir(This,Next,Vs) >= ?ALMOSTPI of 177 true -> 178 New = #be{vs=This#be.vs, ve=Next#be.ve, 179 edge=[This#be.edge,Next#be.edge], 180 dist=dist(This#be.vs,Next#be.ve,Vs)}, 181 if Acc == [] -> 182 make_convex([New|Rest], Acc, Vs); 183 true -> 184 make_convex([hd(Acc),New|Rest], tl(Acc), Vs) 185 end; 186 false -> 187 make_convex([Next|Rest], [This|Acc], Vs) 188 end; 189make_convex([This],Acc, Vs) -> 190 [Next|Acc2] = lists:reverse(Acc), 191 case calc_dir(This,Next,Vs) >= ?ALMOSTPI of 192 true -> 193 New = #be{vs=This#be.vs, ve=Next#be.ve, 194 edge=[This#be.edge,Next#be.edge], 195 dist=dist(This#be.vs,Next#be.ve,Vs)}, 196 Acc3 = reverse(Acc2), 197 make_convex([hd(Acc3),New], tl(Acc3), Vs); 198 false -> 199 [This|Acc] 200 end. 201 202%% Group edgeloops and return a list sorted by total dist. 203%% [{TotDist, [{V1,V2,Edge,Dist},...]}, ...] 204group_edge_loops(Fs, We = #we{name=#ch{emap=Emap}}) -> 205 case auv_util:outer_edges(Fs, We, false) of 206 [] -> []; 207 Eds1 -> 208 Info = fun({Edge,Face},Tree) -> 209 Cut = gb_trees:is_defined(Edge,Emap), 210 case array:get(Edge, We#we.es) of 211 #edge{vs=V1,ve=V2,lf=Face} -> 212 Dist = dist(V1,V2,We#we.vp), 213 Be = #be{vs=V1,ve=V2,edge=Edge,face=Face, 214 cut=Cut,dist=Dist}, 215 gb_trees:insert(V1,Be,Tree); 216 #edge{vs=V2,ve=V1,rf=Face} -> 217 Dist = dist(V1,V2,We#we.vp), 218 Be = #be{vs=V1,ve=V2,edge=Edge,face=Face, 219 cut=Cut,dist=Dist}, 220 gb_trees:insert(V1,Be,Tree) 221 end 222 end, 223 Eds = lists:foldl(Info, gb_trees:empty(), Eds1), 224 Loops = sort_edges(Eds), 225%% io:format("Cuts ~p ~n",[Loops]), 226 Add = fun(#be{dist=Dist}, Acc) -> Acc + Dist end, 227 SumLoops = [{lists:foldl(Add, 0, Loop), Loop} 228 || Loop <- Loops], 229 lists:reverse(lists:sort(SumLoops)) 230 end. 231 232calc_dir(#be{vs=V11,ve=V12},#be{vs=V12,ve=V22}, Vs) -> 233 C = array:get(V12, Vs), 234 V1 = array:get(V11, Vs), 235 V2 = array:get(V22, Vs), 236 {X1,Y1,_} = e3d_vec:sub(V1, C), 237 {X2,Y2,_} = e3d_vec:sub(V2, C), 238 Angle = case (math:atan2(Y1,X1) - math:atan2(Y2,X2)) of 239 A when A >= 0.0 -> 240 A; 241 A -> 242 2 * math:pi() + A 243 end, 244% ?DBG("Angle Vertex ~p Edges ~w : ~p-~p = ~p ~n", 245% [V12,{_E1,_E2},math:atan2(Y1,X1), math:atan2(Y2,X2),Angle]), 246 Angle. 247 248dist(V1, V2, Vs) -> 249 e3d_vec:dist(array:get(V1, Vs), array:get(V2, Vs)). 250 251%% Returns a list of loops 252sort_edges(Eds) -> 253 {_V1, BE=#be{ve=V2}, EdsT0} = gb_trees:take_smallest(Eds), 254 sort_edges(V2, EdsT0, [[BE]]). 255 256sort_edges(V21, EdsT0, All = [Current|Acc]) -> 257 case gb_trees:lookup(V21, EdsT0) of 258 {value, BE = #be{ve=V22}} -> 259 sort_edges(V22, gb_trees:delete(V21,EdsT0), 260 [[BE|Current]|Acc]); 261 none -> 262 case catch gb_trees:take_smallest(EdsT0) of 263 {_, BE = #be{ve=V2}, EdsT1} -> 264 sort_edges(V2, EdsT1, [[BE]|All]); 265 {'EXIT', _} -> %% Stop 266 All 267 end 268 end. 269