← Back to branch summary

~clint-fewbar/ubuntu/precise/erlang/merge-15b

« back to all changes in this revision

Viewing changes to lib/dialyzer/test/opaque_SUITE_data/src/wings/wings_we.erl

  • Committer: Package Import Robot
  • Author(s): Sergei Golovan
  • Date: 2011-12-15 19:20:10 UTC
  • mfrom: (1.1.18) (3.5.15 sid)
  • mto: (3.5.16 sid)
  • mto: This revision was merged to the branch mainline in revision 33.
  • Revision ID: package-import@ubuntu.com-20111215192010-jnxcfe3tbrpp0big
Tags: 1:15.b-dfsg-1
* New upstream release.
* Upload to experimental because this release breaks external drivers
  API along with ABI, so several applications are to be fixed.
* Removed SSL patch because the old SSL implementation is removed from
  the upstream distribution.
* Removed never used patch which added native code to erlang beam files.
* Removed the erlang-docbuilder binary package because the docbuilder
  application was dropped by upstream.
* Documented dropping ${erlang-docbuilder:Depends} substvar in
  erlang-depends(1) manpage.
* Made erlang-base and erlang-base-hipe provide virtual package
  erlang-abi-15.b (the number means the first erlang version, which
  provides current ABI).

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/dialyzer/test/opaque_SUITE_data/src/wings/wings_we.erl
 
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
 
 
19
validate_mirror(#we{mirror=none}=We) -> We;
 
20
validate_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.
 
31
rebuild(#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);
 
37
rebuild(#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)});
 
40
rebuild(#we{fs=undefined,es=Etab}=We) ->
 
41
    Ftab = rebuild_ftab(gb_trees:to_list(Etab)),
 
42
    rebuild(We#we{fs=Ftab});
 
43
rebuild(We) -> update_id_bounds(We).
 
44
 
 
45
%%% Utilities for allocating IDs.
 
46
 
 
47
new_id(#we{next_id=Id}=We) ->
 
48
    {Id,We#we{next_id=Id+1}}.
 
49
 
 
50
%%% Returns sets of newly created items.
 
51
 
 
52
new_items_as_ordset(vertex, #we{next_id=Wid}, #we{next_id=NewWid,vp=Tab}) ->
 
53
    new_items_as_ordset_1(Tab, Wid, NewWid);
 
54
new_items_as_ordset(edge, #we{next_id=Wid}, #we{next_id=NewWid,es=Tab}) ->
 
55
    new_items_as_ordset_1(Tab, Wid, NewWid);
 
56
new_items_as_ordset(face, #we{next_id=Wid}, #we{next_id=NewWid,fs=Tab}) ->
 
57
    new_items_as_ordset_1(Tab, Wid, NewWid).
 
58
 
 
59
any_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
 
 
67
rebuild_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
 
 
75
rebuild_vct(Es) ->
 
76
    rebuild_vct(Es, []).
 
77
 
 
78
rebuild_vct([{Edge,#edge{vs=Va,ve=Vb}}|Es], Acc0) ->
 
79
    Acc = rebuild_maybe_add(Va, Vb, Edge, Acc0),
 
80
    rebuild_vct(Es, Acc);
 
81
rebuild_vct([], VtoE) ->
 
82
    build_incident_tab(VtoE).
 
83
 
 
84
rebuild_ftab(Es) ->
 
85
    rebuild_ftab_1(Es, []).
 
86
 
 
87
rebuild_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);
 
90
rebuild_ftab_1([], FtoE) ->
 
91
    gb_trees:from_orddict(build_incident_tab(FtoE)).
 
92
 
 
93
rebuild_maybe_add(Ka, Kb, E, [_,{Ka,_}|_]=Acc) ->
 
94
    [{Kb,E}|Acc];
 
95
rebuild_maybe_add(Ka, Kb, E, [_,{Kb,_}|_]=Acc) ->
 
96
    [{Ka,E}|Acc];
 
97
rebuild_maybe_add(Ka, Kb, E, [{Ka,_}|_]=Acc) ->
 
98
    [{Kb,E}|Acc];
 
99
rebuild_maybe_add(Ka, Kb, E, [{Kb,_}|_]=Acc) ->
 
100
    [{Ka,E}|Acc];
 
101
rebuild_maybe_add(Ka, Kb, E, Acc) ->
 
102
    [{Ka,E},{Kb,E}|Acc].
 
103
 
 
104
vertex_gc_1([{V,_}|Vct], [{V,_}=Vtx|Vpos], Acc) ->
 
105
    vertex_gc_1(Vct, Vpos, [Vtx|Acc]);
 
106
vertex_gc_1([_|_]=Vct, [_|Vpos], Acc) ->
 
107
    vertex_gc_1(Vct, Vpos, Acc);
 
108
vertex_gc_1([], _, Acc) ->
 
109
    gb_trees:from_orddict(lists:reverse(Acc)).
 
110
 
 
111
%%%
 
112
%%% Handling of hidden faces.
 
113
%%%
 
114
 
 
115
visible(#we{mirror=none,fs=Ftab}) ->
 
116
    visible_2(gb_trees:keys(Ftab));
 
117
visible(#we{mirror=Face,fs=Ftab}) ->
 
118
    visible_2(gb_trees:keys(gb_trees:delete(Face, Ftab))).
 
119
 
 
120
visible_2([F|Fs]) when F < 0 -> visible_2(Fs);
 
121
visible_2(Fs) -> Fs.
 
122
 
 
123
visible_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
 
 
129
visible_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;
 
148
visible_es_1([], _, Acc) -> ordsets:from_list(Acc).
 
149
 
 
150
update_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
 
 
165
build_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
 
 
176
new_items_as_ordset_1(Tab, Wid, NewWid) when NewWid-Wid < 32 ->
 
177
    new_items_as_ordset_2(Wid, NewWid, Tab, []);
 
178
new_items_as_ordset_1(Tab, Wid, _NewWid) ->
 
179
    [Item || Item <- gb_trees:keys(Tab), Item >= Wid].
 
180
 
 
181
new_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;
 
186
new_items_as_ordset_2(_Wid, _NewWid, _Tab, Acc) -> lists:reverse(Acc).
 
187
 
 
188
%%%
 
189
%%% Test the consistency of a #we{}.
 
190
%%%
 
191
 
 
192
is_consistent(#we{}=We) ->
 
193
    try
 
194
        validate_vertex_tab(We),
 
195
        validate_faces(We)
 
196
    catch error:_ -> false
 
197
    end.
 
198
 
 
199
is_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
 
 
205
validate_faces(#we{fs=Ftab,es=Etab}) ->
 
206
    validate_faces_1(gb_trees:to_list(Ftab), Etab).
 
207
 
 
208
validate_faces_1([{Face,Edge}|Fs], Etab) ->
 
209
    validate_face(Face, Edge, Etab),
 
210
    validate_faces_1(Fs, Etab);
 
211
validate_faces_1([], _) -> true.
 
212
 
 
213
validate_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
 
 
219
validate_face_vertices([V|_], V) ->
 
220
    erlang:error(repeated_vertex);
 
221
validate_face_vertices([_], _) ->
 
222
    true;
 
223
validate_face_vertices([V|Vs], _) ->
 
224
    validate_face_vertices(Vs, V).
 
225
 
 
226
walk_face_ccw(LastEdge, _, _, LastEdge, [_|_]=Acc) -> Acc;
 
227
walk_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
 
 
235
walk_face_cw(Edge, _, _, []) -> Edge;
 
236
walk_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
 
 
244
validate_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)).