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