1%% 2%% wings_we.erl -- 3%% 4%% This module contains functions to build and manipulate 5%% we records (winged-edged records, the central data structure 6%% in Wings 3D). 7 8-module(wings_we). 9 10-export([rebuild/1, is_consistent/1, is_face_consistent/2, new_id/1, 11 new_items_as_ordset/3, validate_mirror/1, visible/1, visible_edges/1]). 12 13-include("wings.hrl"). 14 15%%% 16%%% API. 17%%% 18 19validate_mirror(#we{mirror=none}=We) -> We; 20validate_mirror(#we{fs=Ftab,mirror=Face}=We) -> 21 case gb_trees:is_defined(Face, Ftab) of 22 false -> We#we{mirror=none}; 23 true -> We 24 end. 25 26%% rebuild(We) -> We' 27%% Rebuild any missing 'vc' and 'fs' tables. If there are 28%% fewer elements in the 'vc' table than in the 'vp' table, 29%% remove redundant entries in the 'vp' table. Updated id 30%% bounds. 31rebuild(#we{vc=undefined,fs=undefined,es=Etab0}=We0) -> 32 Etab = gb_trees:to_list(Etab0), 33 Ftab = rebuild_ftab(Etab), 34 VctList = rebuild_vct(Etab), 35 We = We0#we{vc=gb_trees:from_orddict(VctList),fs=Ftab}, 36 rebuild_1(VctList, We); 37rebuild(#we{vc=undefined,es=Etab}=We) -> 38 VctList = rebuild_vct(gb_trees:to_list(Etab), []), 39 rebuild_1(VctList, We#we{vc=gb_trees:from_orddict(VctList)}); 40rebuild(#we{fs=undefined,es=Etab}=We) -> 41 Ftab = rebuild_ftab(gb_trees:to_list(Etab)), 42 rebuild(We#we{fs=Ftab}); 43rebuild(We) -> update_id_bounds(We). 44 45%%% Utilities for allocating IDs. 46 47new_id(#we{next_id=Id}=We) -> 48 {Id,We#we{next_id=Id+1}}. 49 50%%% Returns sets of newly created items. 51 52new_items_as_ordset(vertex, #we{next_id=Wid}, #we{next_id=NewWid,vp=Tab}) -> 53 new_items_as_ordset_1(Tab, Wid, NewWid); 54new_items_as_ordset(edge, #we{next_id=Wid}, #we{next_id=NewWid,es=Tab}) -> 55 new_items_as_ordset_1(Tab, Wid, NewWid); 56new_items_as_ordset(face, #we{next_id=Wid}, #we{next_id=NewWid,fs=Tab}) -> 57 new_items_as_ordset_1(Tab, Wid, NewWid). 58 59any_hidden(#we{fs=Ftab}) -> 60 not gb_trees:is_empty(Ftab) andalso 61 wings_util:gb_trees_smallest_key(Ftab) < 0. 62 63%%% 64%%% Local functions. 65%%% 66 67rebuild_1(VctList, #we{vc=Vct,vp=Vtab0}=We) -> 68 case {gb_trees:size(Vct),gb_trees:size(Vtab0)} of 69 {Same,Same} -> rebuild(We); 70 {Sz1,Sz2} when Sz1 < Sz2 -> 71 Vtab = vertex_gc_1(VctList, gb_trees:to_list(Vtab0), []), 72 rebuild(We#we{vp=Vtab}) 73 end. 74 75rebuild_vct(Es) -> 76 rebuild_vct(Es, []). 77 78rebuild_vct([{Edge,#edge{vs=Va,ve=Vb}}|Es], Acc0) -> 79 Acc = rebuild_maybe_add(Va, Vb, Edge, Acc0), 80 rebuild_vct(Es, Acc); 81rebuild_vct([], VtoE) -> 82 build_incident_tab(VtoE). 83 84rebuild_ftab(Es) -> 85 rebuild_ftab_1(Es, []). 86 87rebuild_ftab_1([{Edge,#edge{lf=Lf,rf=Rf}}|Es], Acc0) -> 88 Acc = rebuild_maybe_add(Lf, Rf, Edge, Acc0), 89 rebuild_ftab_1(Es, Acc); 90rebuild_ftab_1([], FtoE) -> 91 gb_trees:from_orddict(build_incident_tab(FtoE)). 92 93rebuild_maybe_add(Ka, Kb, E, [_,{Ka,_}|_]=Acc) -> 94 [{Kb,E}|Acc]; 95rebuild_maybe_add(Ka, Kb, E, [_,{Kb,_}|_]=Acc) -> 96 [{Ka,E}|Acc]; 97rebuild_maybe_add(Ka, Kb, E, [{Ka,_}|_]=Acc) -> 98 [{Kb,E}|Acc]; 99rebuild_maybe_add(Ka, Kb, E, [{Kb,_}|_]=Acc) -> 100 [{Ka,E}|Acc]; 101rebuild_maybe_add(Ka, Kb, E, Acc) -> 102 [{Ka,E},{Kb,E}|Acc]. 103 104vertex_gc_1([{V,_}|Vct], [{V,_}=Vtx|Vpos], Acc) -> 105 vertex_gc_1(Vct, Vpos, [Vtx|Acc]); 106vertex_gc_1([_|_]=Vct, [_|Vpos], Acc) -> 107 vertex_gc_1(Vct, Vpos, Acc); 108vertex_gc_1([], _, Acc) -> 109 gb_trees:from_orddict(lists:reverse(Acc)). 110 111%%% 112%%% Handling of hidden faces. 113%%% 114 115visible(#we{mirror=none,fs=Ftab}) -> 116 visible_2(gb_trees:keys(Ftab)); 117visible(#we{mirror=Face,fs=Ftab}) -> 118 visible_2(gb_trees:keys(gb_trees:delete(Face, Ftab))). 119 120visible_2([F|Fs]) when F < 0 -> visible_2(Fs); 121visible_2(Fs) -> Fs. 122 123visible_edges(#we{es=Etab,mirror=Face}=We) -> 124 case any_hidden(We) of 125 false -> gb_trees:keys(Etab); 126 true -> visible_es_1(gb_trees:to_list(Etab), Face, []) 127 end. 128 129visible_es_1([{E,#edge{lf=Lf,rf=Rf}}|Es], Face, Acc) -> 130 if 131 Lf < 0 -> 132 %% Left face hidden. 133 if 134 Rf < 0; Rf =:= Face -> 135 %% Both faces invisible (in some way). 136 visible_es_1(Es, Face, Acc); 137 true -> 138 %% Right face is visible. 139 visible_es_1(Es, Face, [E|Acc]) 140 end; 141 Lf =:= Face, Rf < 0 -> 142 %% Left face mirror, right face hidden. 143 visible_es_1(Es, Face, Acc); 144 true -> 145 %% At least one face visible. 146 visible_es_1(Es, Face, [E|Acc]) 147 end; 148visible_es_1([], _, Acc) -> ordsets:from_list(Acc). 149 150update_id_bounds(#we{vp=Vtab,es=Etab,fs=Ftab}=We) -> 151 case gb_trees:is_empty(Etab) of 152 true -> We#we{next_id=0}; 153 false -> 154 LastId = lists:max([wings_util:gb_trees_largest_key(Vtab), 155 wings_util:gb_trees_largest_key(Etab), 156 wings_util:gb_trees_largest_key(Ftab)]), 157 We#we{next_id=LastId+1} 158 end. 159 160%% build_incident_tab([{Elem,Edge}]) -> [{Elem,Edge}] 161%% Elem = Face or Vertex 162%% Build the table of incident edges for either faces or vertices. 163%% Returns an ordered list where each Elem is unique. 164 165build_incident_tab(ElemToEdgeRel) -> 166 T = ets:new(?MODULE, [ordered_set]), 167 ets:insert(T, ElemToEdgeRel), 168 R = ets:tab2list(T), 169 ets:delete(T), 170 R. 171 172%%% 173%%% Calculate normals. 174%%% 175 176new_items_as_ordset_1(Tab, Wid, NewWid) when NewWid-Wid < 32 -> 177 new_items_as_ordset_2(Wid, NewWid, Tab, []); 178new_items_as_ordset_1(Tab, Wid, _NewWid) -> 179 [Item || Item <- gb_trees:keys(Tab), Item >= Wid]. 180 181new_items_as_ordset_2(Wid, NewWid, Tab, Acc) when Wid < NewWid -> 182 case gb_trees:is_defined(Wid, Tab) of 183 true -> new_items_as_ordset_2(Wid+1, NewWid, Tab, [Wid|Acc]); 184 false -> new_items_as_ordset_2(Wid+1, NewWid, Tab, Acc) 185 end; 186new_items_as_ordset_2(_Wid, _NewWid, _Tab, Acc) -> lists:reverse(Acc). 187 188%%% 189%%% Test the consistency of a #we{}. 190%%% 191 192is_consistent(#we{}=We) -> 193 try 194 validate_vertex_tab(We), 195 validate_faces(We) 196 catch error:_ -> false 197 end. 198 199is_face_consistent(Face, #we{fs=Ftab,es=Etab}) -> 200 Edge = gb_trees:get(Face, Ftab), 201 try validate_face(Face, Edge, Etab) 202 catch error:_ -> false 203 end. 204 205validate_faces(#we{fs=Ftab,es=Etab}) -> 206 validate_faces_1(gb_trees:to_list(Ftab), Etab). 207 208validate_faces_1([{Face,Edge}|Fs], Etab) -> 209 validate_face(Face, Edge, Etab), 210 validate_faces_1(Fs, Etab); 211validate_faces_1([], _) -> true. 212 213validate_face(Face, Edge, Etab) -> 214 Ccw = walk_face_ccw(Edge, Etab, Face, Edge, []), 215 Edge = walk_face_cw(Edge, Etab, Face, Ccw), 216 [V|Vs] = lists:sort(Ccw), 217 validate_face_vertices(Vs, V). 218 219validate_face_vertices([V|_], V) -> 220 erlang:error(repeated_vertex); 221validate_face_vertices([_], _) -> 222 true; 223validate_face_vertices([V|Vs], _) -> 224 validate_face_vertices(Vs, V). 225 226walk_face_ccw(LastEdge, _, _, LastEdge, [_|_]=Acc) -> Acc; 227walk_face_ccw(Edge, Etab, Face, LastEdge, Acc) -> 228 case gb_trees:get(Edge, Etab) of 229 #edge{ve=V,lf=Face,ltpr=Next} -> 230 walk_face_ccw(Next, Etab, Face, LastEdge, [V|Acc]); 231 #edge{vs=V,rf=Face,rtpr=Next} -> 232 walk_face_ccw(Next, Etab, Face, LastEdge, [V|Acc]) 233 end. 234 235walk_face_cw(Edge, _, _, []) -> Edge; 236walk_face_cw(Edge, Etab, Face, [V|Vs]) -> 237 case gb_trees:get(Edge, Etab) of 238 #edge{vs=V,lf=Face,ltsu=Next} -> 239 walk_face_cw(Next, Etab, Face, Vs); 240 #edge{ve=V,rf=Face,rtsu=Next} -> 241 walk_face_cw(Next, Etab, Face, Vs) 242 end. 243 244validate_vertex_tab(#we{es=Etab,vc=Vct}) -> 245 lists:foreach(fun({V,Edge}) -> 246 case gb_trees:get(Edge, Etab) of 247 #edge{vs=V} -> ok; 248 #edge{ve=V} -> ok 249 end 250 end, gb_trees:to_list(Vct)). 251