← 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_edge.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_edge.erl
 
1
%%
 
2
%%  wings_edge.erl --
 
3
%%
 
4
%%     This module contains most edge command and edge utility functions.
 
5
%%
 
6
%%  Copyright (c) 2001-2008 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: wings_edge.erl,v 1.1 2009/01/25 18:55:33 kostis Exp $
 
12
%%
 
13
 
 
14
-module(wings_edge).
 
15
 
 
16
-export([dissolve_edges/2]).
 
17
 
 
18
-include("wings.hrl").
 
19
 
 
20
%%%
 
21
%%% Dissolve.
 
22
%%%
 
23
 
 
24
dissolve_edges(Edges0, We0) when is_list(Edges0) ->
 
25
    #we{es=Etab} = We1 = lists:foldl(fun internal_dissolve_edge/2, We0, Edges0),
 
26
    case [E || E <- Edges0, gb_trees:is_defined(E, Etab)] of
 
27
        Edges0 ->
 
28
            %% No edge was deleted in the last pass. We are done.
 
29
            We = wings_we:rebuild(We0#we{vc=undefined}),
 
30
            wings_we:validate_mirror(We);
 
31
        Edges ->
 
32
            dissolve_edges(Edges, We1)
 
33
    end;
 
34
dissolve_edges(Edges, We) ->
 
35
    dissolve_edges(gb_sets:to_list(Edges), We).
 
36
 
 
37
internal_dissolve_edge(Edge, #we{es=Etab}=We0) ->
 
38
    case gb_trees:lookup(Edge, Etab) of
 
39
        none -> We0;
 
40
        {value,#edge{ltpr=Same,ltsu=Same,rtpr=Same,rtsu=Same}} ->
 
41
            Empty = gb_trees:empty(),
 
42
            We0#we{vc=Empty,vp=Empty,es=Empty,fs=Empty,he=gb_sets:empty()};
 
43
        {value,#edge{rtpr=Back,ltsu=Back}=Rec} ->
 
44
            merge_edges(backward, Edge, Rec, We0);
 
45
        {value,#edge{rtsu=Forward,ltpr=Forward}=Rec} ->
 
46
            merge_edges(forward, Edge, Rec, We0);
 
47
        {value,Rec} ->
 
48
            try dissolve_edge_1(Edge, Rec, We0) of
 
49
                We -> We
 
50
            catch
 
51
                throw:hole -> We0
 
52
            end
 
53
    end.
 
54
 
 
55
%% dissolve_edge_1(Edge, EdgeRecord, We) -> We
 
56
%%  Remove an edge and a face. If one of the faces is degenerated
 
57
%%  (only consists of two edges), remove that one. Otherwise, it
 
58
%%  doesn't matter which face we remove.
 
59
dissolve_edge_1(Edge, #edge{lf=Remove,rf=Keep,ltpr=Same,ltsu=Same}=Rec, We) ->
 
60
    dissolve_edge_2(Edge, Remove, Keep, Rec, We);
 
61
dissolve_edge_1(Edge, #edge{lf=Keep,rf=Remove}=Rec, We) ->
 
62
    dissolve_edge_2(Edge, Remove, Keep, Rec, We).
 
63
 
 
64
dissolve_edge_2(Edge, FaceRemove, FaceKeep,
 
65
                #edge{ltpr=LP,ltsu=LS,rtpr=RP,rtsu=RS},
 
66
                #we{fs=Ftab0,es=Etab0,he=Htab0}=We0) ->
 
67
    %% First change face for all edges surrounding the face we will remove.
 
68
    Etab1 = wings_face:fold(
 
69
              fun (_, E, _, IntEtab) when E =:= Edge -> IntEtab;
 
70
                  (_, E, R, IntEtab) ->
 
71
                      case R of
 
72
                          #edge{lf=FaceRemove,rf=FaceKeep} ->
 
73
                              throw(hole);
 
74
                          #edge{rf=FaceRemove,lf=FaceKeep} ->
 
75
                              throw(hole);
 
76
                          #edge{lf=FaceRemove} ->
 
77
                              gb_trees:update(E, R#edge{lf=FaceKeep}, IntEtab);
 
78
                          #edge{rf=FaceRemove} ->
 
79
                              gb_trees:update(E, R#edge{rf=FaceKeep}, IntEtab)
 
80
                      end
 
81
              end, Etab0, FaceRemove, We0),
 
82
 
 
83
    %% Patch all predecessors and successor of the edge we will remove.
 
84
    Etab2 = patch_edge(LP, RS, Edge, Etab1),
 
85
    Etab3 = patch_edge(LS, RP, Edge, Etab2),
 
86
    Etab4 = patch_edge(RP, LS, Edge, Etab3),
 
87
    Etab5 = patch_edge(RS, LP, Edge, Etab4),
 
88
 
 
89
    %% Remove the edge.
 
90
    Etab = gb_trees:delete(Edge, Etab5),
 
91
    Htab = hardness(Edge, soft, Htab0),
 
92
 
 
93
    %% Remove the face. Patch the face entry for the remaining face.
 
94
    Ftab1 = gb_trees:delete(FaceRemove, Ftab0),
 
95
    We1 = wings_facemat:delete_face(FaceRemove, We0),
 
96
    Ftab = gb_trees:update(FaceKeep, LP, Ftab1),
 
97
 
 
98
    %% Return result.
 
99
    We = We1#we{es=Etab,fs=Ftab,vc=undefined,he=Htab},
 
100
    AnEdge = gb_trees:get(FaceKeep, Ftab),
 
101
    case gb_trees:get(AnEdge, Etab) of
 
102
        #edge{lf=FaceKeep,ltpr=Same,ltsu=Same} ->
 
103
            internal_dissolve_edge(AnEdge, We);
 
104
        #edge{rf=FaceKeep,rtpr=Same,rtsu=Same} ->
 
105
            internal_dissolve_edge(AnEdge, We);
 
106
        _Other ->
 
107
            case wings_we:is_face_consistent(FaceKeep, We) of
 
108
                true ->
 
109
                    We;
 
110
                false ->
 
111
                    io:format("Dissolving would cause a badly formed face.")
 
112
            end
 
113
    end.
 
114
 
 
115
%%
 
116
%% We like winged edges, but not winged vertices (a vertex with
 
117
%% only two edges connected to it). We will remove the winged vertex
 
118
%% by joining the two edges connected to it.
 
119
%%
 
120
 
 
121
merge_edges(Dir, Edge, Rec, #we{es=Etab}=We) ->
 
122
    {Va,Vb,_,_,_,_,To,To} = half_edge(Dir, Rec),
 
123
    case gb_trees:get(To, Etab) of
 
124
        #edge{vs=Va,ve=Vb} ->
 
125
            del_2edge_face(Dir, Edge, Rec, To, We);
 
126
        #edge{vs=Vb,ve=Va} ->
 
127
            del_2edge_face(Dir, Edge, Rec, To, We);
 
128
        _Other ->
 
129
            merge_1(Dir, Edge, Rec, To, We)
 
130
    end.
 
131
 
 
132
merge_1(Dir, Edge, Rec, To, #we{es=Etab0,fs=Ftab0,he=Htab0}=We) ->
 
133
    OtherDir = reverse_dir(Dir),
 
134
    {Vkeep,Vdelete,Lf,Rf,A,B,L,R} = half_edge(OtherDir, Rec),
 
135
    Etab1 = patch_edge(L, To, Edge, Etab0),
 
136
    Etab2 = patch_edge(R, To, Edge, Etab1),
 
137
    Etab3 = patch_half_edge(To, Vkeep, Lf, A, L, Rf, B, R, Vdelete, Etab2),
 
138
    Htab = hardness(Edge, soft, Htab0),
 
139
    Etab = gb_trees:delete(Edge, Etab3),
 
140
    #edge{lf=Lf,rf=Rf} = Rec,
 
141
    Ftab1 = update_face(Lf, To, Edge, Ftab0),
 
142
    Ftab = update_face(Rf, To, Edge, Ftab1),
 
143
    merge_2(To, We#we{es=Etab,fs=Ftab,he=Htab,vc=undefined}).
 
144
 
 
145
merge_2(Edge, #we{es=Etab}=We) ->
 
146
    %% If the merged edge is part of a two-edge face, we must
 
147
    %% remove that edge too.
 
148
    case gb_trees:get(Edge, Etab) of
 
149
        #edge{ltpr=Same,ltsu=Same} ->
 
150
            internal_dissolve_edge(Edge, We);
 
151
        #edge{rtpr=Same,rtsu=Same} ->
 
152
            internal_dissolve_edge(Edge, We);
 
153
        _Other -> We
 
154
    end.
 
155
 
 
156
update_face(Face, Edge, OldEdge, Ftab) ->
 
157
    case gb_trees:get(Face, Ftab) of
 
158
        OldEdge -> gb_trees:update(Face, Edge, Ftab);
 
159
        _Other -> Ftab
 
160
    end.
 
161
 
 
162
del_2edge_face(Dir, EdgeA, RecA, EdgeB,
 
163
               #we{es=Etab0,fs=Ftab0,he=Htab0}=We) ->
 
164
    {_,_,Lf,Rf,_,_,_,_} = half_edge(reverse_dir(Dir), RecA),
 
165
    RecB = gb_trees:get(EdgeB, Etab0),
 
166
    Del = gb_sets:from_list([EdgeA,EdgeB]),
 
167
    EdgeANear = stabile_neighbor(RecA, Del),
 
168
    EdgeBNear = stabile_neighbor(RecB, Del),
 
169
    Etab1 = patch_edge(EdgeANear, EdgeBNear, EdgeA, Etab0),
 
170
    Etab2 = patch_edge(EdgeBNear, EdgeANear, EdgeB, Etab1),
 
171
    Etab3 = gb_trees:delete(EdgeA, Etab2),
 
172
    Etab = gb_trees:delete(EdgeB, Etab3),
 
173
 
 
174
    %% Patch hardness table.
 
175
    Htab1 = hardness(EdgeA, soft, Htab0),
 
176
    Htab = hardness(EdgeB, soft, Htab1),
 
177
 
 
178
    %% Patch the face table.
 
179
    #edge{lf=Klf,rf=Krf} = gb_trees:get(EdgeANear, Etab),
 
180
    KeepFaces = ordsets:from_list([Klf,Krf]),
 
181
    EdgeAFaces = ordsets:from_list([Lf,Rf]),
 
182
    [DelFace] = ordsets:subtract(EdgeAFaces, KeepFaces),
 
183
    Ftab1 = gb_trees:delete(DelFace, Ftab0),
 
184
    [KeepFace] = ordsets:intersection(KeepFaces, EdgeAFaces),
 
185
    Ftab2 = update_face(KeepFace, EdgeANear, EdgeA, Ftab1),
 
186
    Ftab = update_face(KeepFace, EdgeBNear, EdgeB, Ftab2),
 
187
 
 
188
    %% Return result.
 
189
    We#we{vc=undefined,es=Etab,fs=Ftab,he=Htab}.
 
190
 
 
191
stabile_neighbor(#edge{ltpr=Ea,ltsu=Eb,rtpr=Ec,rtsu=Ed}, Del) ->
 
192
    [Edge] = lists:foldl(fun(E, A) ->
 
193
                                 case gb_sets:is_member(E, Del) of
 
194
                                     true -> A;
 
195
                                     false -> [E|A]
 
196
                           end
 
197
                         end, [], [Ea,Eb,Ec,Ed]),
 
198
    Edge.
 
199
 
 
200
%%%
 
201
%%% Setting hard/soft edges.
 
202
%%%
 
203
 
 
204
hardness(Edge, soft, Htab) -> gb_sets:delete_any(Edge, Htab);
 
205
hardness(Edge, hard, Htab) -> gb_sets:add(Edge, Htab).
 
206
 
 
207
%%%
 
208
%%% Utilities.
 
209
%%%
 
210
 
 
211
reverse_dir(forward) -> backward;
 
212
reverse_dir(backward) -> forward.
 
213
 
 
214
half_edge(backward, #edge{vs=Va,ve=Vb,lf=Lf,rf=Rf,a=A,b=B,ltsu=L,rtpr=R}) ->
 
215
    {Va,Vb,Lf,Rf,A,B,L,R};
 
216
half_edge(forward, #edge{ve=Va,vs=Vb,lf=Lf,rf=Rf,a=A,b=B,ltpr=L,rtsu=R}) ->
 
217
    {Va,Vb,Lf,Rf,A,B,L,R}.
 
218
 
 
219
patch_half_edge(Edge, V, FaceA, A, Ea, FaceB, B, Eb, OrigV, Etab) ->
 
220
    New = case gb_trees:get(Edge, Etab) of
 
221
              #edge{vs=OrigV,lf=FaceA,rf=FaceB}=Rec ->
 
222
                  Rec#edge{a=A,vs=V,ltsu=Ea,rtpr=Eb};
 
223
              #edge{vs=OrigV,lf=FaceB,rf=FaceA}=Rec ->
 
224
                  Rec#edge{a=B,vs=V,ltsu=Eb,rtpr=Ea};
 
225
              #edge{ve=OrigV,lf=FaceA,rf=FaceB}=Rec ->
 
226
                  Rec#edge{b=B,ve=V,ltpr=Ea,rtsu=Eb};
 
227
              #edge{ve=OrigV,lf=FaceB,rf=FaceA}=Rec ->
 
228
                  Rec#edge{b=A,ve=V,ltpr=Eb,rtsu=Ea}
 
229
          end,
 
230
    gb_trees:update(Edge, New, Etab).
 
231
 
 
232
patch_edge(Edge, ToEdge, OrigEdge, Etab) ->
 
233
    New = case gb_trees:get(Edge, Etab) of
 
234
              #edge{ltsu=OrigEdge}=R ->
 
235
                  R#edge{ltsu=ToEdge};
 
236
              #edge{ltpr=OrigEdge}=R ->
 
237
                  R#edge{ltpr=ToEdge};
 
238
              #edge{rtsu=OrigEdge}=R ->
 
239
                  R#edge{rtsu=ToEdge};
 
240
              #edge{rtpr=OrigEdge}=R ->
 
241
                  R#edge{rtpr=ToEdge}
 
242
          end,
 
243
    gb_trees:update(Edge, New, Etab).