%%
%%  wings_edge.erl --
%%
%%     This module contains most edge command and edge utility functions.
%%
%%  Copyright (c) 2001-2004 Bjorn Gustavsson.
%%
%%  See the file "license.terms" for information on usage and redistribution
%%  of this file, and for a DISCLAIMER OF ALL WARRANTIES.
%%
%%     $Id: wings_edge.erl,v 1.105 2004/11/16 12:19:21 bjorng Exp $
%%

-module(wings_edge).

%% Commands.
-export([menu/3,command/2]).

%% Utilities.
-export([convert_selection/1,
	 select_more/1,select_less/1,
	 from_vs/2,
	 select_region/1,
	 select_edge_ring/1,select_edge_ring_incr/1,select_edge_ring_decr/1,
	 cut/3,fast_cut/3,
	 dissolve_edges/2,dissolve_edge/2,
	 hardness/2,hardness/3,
	 adjacent_edges/2,
	 to_vertices/2,from_faces/2,extend_sel/2,
	 set_color/2,
	 patch_edge/4,patch_edge/5]).

-export([dissolve_isolated_vs/2]).

-define(NEED_ESDL, 1).
-define(NEED_OPENGL, 1).
-include("wings.hrl").
-import(lists, [foldl/3,last/1,member/2,reverse/1,reverse/2,
		seq/2,sort/1]).
-import(e3d_vec, [add/1,add/2,sub/2,neg/1,norm/1,len/1,
		  average/1,average/2,
		  dot/2,cross/2]).

menu(X, Y, St) ->
    Dir = wings_menu_util:directions(St),
    Menu = [{basic,{?STR(menu,1,"Edge operations"),ignore}},
	    {basic,separator},
	    {?STR(menu,2,"Move"),{move,Dir},[],[magnet]},
	    wings_menu_util:rotate(St),
	    wings_menu_util:scale(St),
	    {?STR(menu,3,"Slide"), slide, ?STR(menu,4,"Slide edges along neighbor edges")},
	    separator,
	    {?STR(menu,5,"Extrude"),{extrude,Dir}},
	    separator,
	    cut_line(St),
	    {?STR(menu,6,"Connect"),connect,
	     ?STR(menu,7,"Create a new edge by connecting midpoints of selected edges")},
	    {?STR(menu,8,"Bevel"),bevel,?STR(menu,9,"Round off selected edges")},
	    separator,
	    {?STR(menu,10,"Dissolve"),dissolve,?STR(menu,11,"Eliminate selected edges")},
	    {?STR(menu,12,"Collapse"),collapse,?STR(menu,13,"Delete edges, replacing them with vertices")},
	    separator,
	    {?STR(menu,14,"Hardness"),{hardness,[{?STR(menu,15,"Soft"),soft},
				   {?STR(menu,16,"Hard"),hard}]}},
	    separator,
	    {?STR(menu,17,"Loop Cut"),loop_cut,?STR(menu,18,"Cut into two objects along edge loop")},
	    separator,
	    {?STR(menu,19,"Vertex Color"),vertex_color,
	     ?STR(menu,20,"Apply vertex colors to selected edges")}],
    wings_menu:popup_menu(X, Y, edge, Menu).

cut_line(#st{sel=[{_,Es}]}) ->
    case gb_sets:size(Es) of
	1 -> cut_fun();
	_ -> plain_cut_menu()
    end;
cut_line(_) -> plain_cut_menu().

plain_cut_menu() ->
    {?STR(plain_cut_menu,1,"Cut"),{cut,cut_entries()},?STR(plain_cut_menu,2,"Cut into edges of equal length")}.

cut_fun() ->
    F = fun(help, _Ns) ->
		{?STR(cut_fun,1,"Cut into edges of equal length"),[],?STR(cut_fun,2,"Cut at arbitrary position")};
	   (1, _Ns) -> cut_entries();
	   (2, _) -> ignore;
	   (3, _) -> {edge,cut_pick}
	end,
    {?STR(cut_fun,3,"Cut"),{cut,F}}.

cut_entries() ->
    [cut_entry(2),
     cut_entry(3),
     cut_entry(4),
     cut_entry(5),
     separator,
     cut_entry(10)].

cut_entry(N) ->
    Str = integer_to_list(N),
    {Str,N,?STR(cut_entry,1,"Cut into ") ++ Str ++ ?STR(cut_entry,2," edges of equal length")}.

%% Edge commands.
command(bevel, St) ->
    ?SLOW(wings_extrude_edge:bevel(St));
command({extrude,Type}, St) ->
    ?SLOW(wings_extrude_edge:extrude(Type, St));
command(slide, St) ->
    slide(St);
command(cut_pick, St) ->
    cut_pick(St);
command({cut,Num}, St) ->
    {save_state,cut(Num, St)};
command(connect, St) ->
    {save_state,connect(St)};
command(dissolve, St) ->
    {save_state,dissolve(St)};
command(collapse, St) ->
    {save_state,wings_collapse:collapse(St)};
command({hardness,Type}, St) ->
    {save_state,hardness(Type, St)};
command(loop_cut, St) ->
    ?SLOW({save_state,loop_cut(St)});
command(auto_smooth, St) ->
    wings_body:auto_smooth(St);
command({move,Type}, St) ->
    wings_move:setup(Type, St);
command({rotate,Type}, St) ->
    wings_rotate:setup(Type, St);
command({scale,Type}, St) ->
    wings_scale:setup(Type, St);
command(vertex_color, St) ->
    wings_color:choose(fun(Color) ->
			       set_color(Color, St)
		       end).

%%
%% Convert the current selection to an edge selection.
%%
convert_selection(#st{selmode=body}=St) ->
    wings_sel:convert_shape(
      fun(_, #we{es=Etab}) ->
	      gb_sets:from_list(gb_trees:keys(Etab))
      end, edge, St);
convert_selection(#st{selmode=face}=St) ->
    wings_sel:convert_shape(
      fun(Faces, We) ->
	      from_faces(Faces, We)
      end, edge, St);
convert_selection(#st{selmode=edge}=St) ->
    wings_sel:convert_shape(
      fun(Edges, We) ->
	      extend_sel(Edges, We)
      end, edge, St);
convert_selection(#st{selmode=vertex}=St) ->
    wings_sel:convert_shape(fun(Vs, We) -> from_vs(Vs, We) end, edge, St).

from_vs(Vs, We) when is_list(Vs) ->
    from_vs(Vs, We, []);
from_vs(Vs, We) ->
    gb_sets:from_list(from_vs(gb_sets:to_list(Vs), We, [])).

from_vs([V|Vs], We, Acc0) ->
    Acc = wings_vertex:fold(fun(E, _, _, A) -> [E|A] end, Acc0, V, We),
    from_vs(Vs, We, Acc);
from_vs([], _, Acc) -> Acc.

%%% Select more or less.

select_more(St) ->
    wings_sel:convert_shape(fun select_more/2, edge, St).

select_more(Edges, We) ->
    Vs = to_vertices(Edges, We),
    adjacent_edges(Vs, We, Edges).

select_less(St) ->
    wings_sel:convert_shape(
      fun(Edges, #we{es=Etab}=We) ->
	      Vs0 = select_less_1(Edges, Etab),
	      Vs = ordsets:from_list(Vs0),
	      AdjEdges = adjacent_edges(Vs, We),
	      gb_sets:subtract(Edges, AdjEdges)
      end, edge, St).

select_less_1(Edges, Etab) ->
    foldl(fun(Edge, A0) ->
		  Rec = gb_trees:get(Edge, Etab),
		  #edge{vs=Va,ve=Vb,
			ltpr=LP,ltsu=LS,
			rtpr=RP,rtsu=RS} = Rec,
		  A = case gb_sets:is_member(LS, Edges) andalso
			  gb_sets:is_member(RP, Edges) of
			  true -> A0;
			  false -> [Va|A0]
		      end,
		  case gb_sets:is_member(LP, Edges) andalso
		      gb_sets:is_member(RS, Edges) of
		      true -> A;
		      false -> [Vb|A]
		  end
	  end, [], gb_sets:to_list(Edges)).

adjacent_edges(Vs, We) ->
    adjacent_edges(Vs, We, gb_sets:empty()).

adjacent_edges(Vs, We, Acc) ->
    foldl(fun(V, A) ->
		  wings_vertex:fold(
		    fun(Edge, _, _, AA) ->
			    gb_sets:add(Edge, AA)
		    end, A, V, We)
	  end, Acc, Vs).

%% to_vertices(EdgeGbSet, We) -> VertexGbSet
%%  Convert a set of edges to a set of vertices.

to_vertices(Edges, #we{es=Etab}) when is_list(Edges) ->
    to_vertices(Edges, Etab, []);
to_vertices(Edges, #we{es=Etab}) ->
    to_vertices(gb_sets:to_list(Edges), Etab, []).

to_vertices([E|Es], Etab, Acc) ->
    #edge{vs=Va,ve=Vb} = gb_trees:get(E, Etab),
    to_vertices(Es, Etab, [Va,Vb|Acc]);
to_vertices([], _Etab, Acc) -> ordsets:from_list(Acc).

%% from_faces(FaceSet, We) -> EdgeSet
%%  Convert faces to edges.
from_faces(Faces, We) ->
    gb_sets:from_ordset(wings_face:to_edges(Faces, We)).

%% from_faces(Edges, We) -> EdgeSet
%%  Extend Edges with all neighboring edges.
extend_sel(Edges, We) when is_list(Edges) ->
    extend_sel(Edges, gb_sets:from_list(Edges), We);
extend_sel(EdgeSet, We) ->
    extend_sel(gb_sets:to_list(EdgeSet), EdgeSet, We).

extend_sel(Edges, EdgeSet, #we{es=Etab}) ->
    foldl(fun(Edge, S0) ->
		  Rec = gb_trees:get(Edge, Etab),
		  #edge{ltpr=LP,ltsu=LS,rtpr=RP,rtsu=RS} = Rec,
		  gb_sets:union(S0, gb_sets:from_list([LP,LS,RP,RS]))
	  end, EdgeSet, Edges).

%%%
%%% The Cut command.
%%%

cut(N, #st{selmode=edge}=St0) when N > 1 ->
    {St,Sel} = wings_sel:mapfold(
		 fun(Edges, #we{id=Id}=We0, Acc) ->
			 We = cut_edges(Edges, N, We0),
			 S = wings_we:new_items(vertex, We0, We),
			 {We,[{Id,S}|Acc]}
		 end, [], St0),
    wings_sel:set(vertex, Sel, St);
cut(_, St) -> St.

cut_edges(Edges, N, We0) ->
    foldl(fun(Edge, W0) ->
		  {We,_} = cut(Edge, N, W0),
		  We
	  end, We0, gb_sets:to_list(Edges)).

%% cut(Edge, Parts, We0) -> {We,NewVertex,NewEdge}
%%  Cut an edge into Parts parts.
cut(Edge, 2, We) ->
    fast_cut(Edge, default, We);
cut(Edge, N, #we{es=Etab}=We) ->
    #edge{vs=Va,ve=Vb} = gb_trees:get(Edge, Etab),
    PosA = wings_vertex:pos(Va, We),
    PosB = wings_vertex:pos(Vb, We),
    Vec = e3d_vec:mul(e3d_vec:sub(PosB, PosA), 1/N),
    cut_1(N, Edge, PosA, Vec, We).

cut_1(2, Edge, _, _, We) ->
    fast_cut(Edge, default, We);
cut_1(N, Edge, Pos0, Vec, We0) ->
    Pos = e3d_vec:add(Pos0, Vec),
    {We,NewE} = fast_cut(Edge, Pos, We0),
    cut_1(N-1, NewE, Pos, Vec, We).

%% fast_cut(Edge, Position, We0) -> {We,NewVertex,NewEdge}
%%  Cut an edge in two parts. Position can be given as
%%  the atom `default', in which case the position will
%%  be set to the midpoint of the edge.

fast_cut(Edge, Pos0, We0) ->
    {NewEdge=NewV,We} = wings_we:new_ids(1, We0),
    #we{es=Etab0,vc=Vct0,vp=Vtab0,he=Htab0} = We,
    Template = gb_trees:get(Edge, Etab0),
    #edge{vs=Vstart,ve=Vend,a=ACol,b=BCol,lf=Lf,rf=Rf,
	  ltpr=EdgeA,rtsu=EdgeB,rtpr=NextBCol} = Template,
    VendPos = gb_trees:get(Vend, Vtab0),
    Vct1 = gb_trees:update(Vend, NewEdge, Vct0),
    VstartPos = wings_vertex:pos(Vstart, Vtab0),
    if
	Pos0 =:= default ->
	    NewVPos0 = e3d_vec:average([VstartPos,VendPos]);
	true ->
	    NewVPos0 = Pos0
    end,
    NewVPos = wings_util:share(NewVPos0),
    Vct = gb_trees:insert(NewV, NewEdge, Vct1),
    Vtab = gb_trees:insert(NewV, NewVPos, Vtab0),

    %% Here we handle vertex colors/UV coordinates.
    Weight = if
		 Pos0 == default -> 0.5;
		 true ->
		     ADist = e3d_vec:dist(Pos0, VstartPos),
		     BDist = e3d_vec:dist(Pos0, VendPos),
		     case catch ADist/(ADist+BDist) of
			 {'EXIT',_} -> 0.5;
			 Weight0 -> Weight0
		     end
	     end,
    AColOther = get_vtx_color(EdgeA, Lf, Etab0),
    NewColA = wings_color:mix(Weight, AColOther, ACol),
    BColOther = get_vtx_color(NextBCol, Rf, Etab0),
    NewColB = wings_color:mix(Weight, BCol, BColOther),

    NewEdgeRec = Template#edge{vs=NewV,a=NewColA,ltsu=Edge,rtpr=Edge},
    Etab1 = gb_trees:insert(NewEdge, NewEdgeRec, Etab0),
    Etab2 = patch_edge(EdgeA, NewEdge, Edge, Etab1),
    Etab3 = patch_edge(EdgeB, NewEdge, Edge, Etab2),
    EdgeRec = Template#edge{ve=NewV,b=NewColB,rtsu=NewEdge,ltpr=NewEdge},
    Etab = gb_trees:update(Edge, EdgeRec, Etab3),

    Htab = case gb_sets:is_member(Edge, Htab0) of
	       false -> Htab0;
	       true -> gb_sets:insert(NewEdge, Htab0)
	   end,
    {We#we{es=Etab,vc=Vct,vp=Vtab,he=Htab},NewV}.

get_vtx_color(Edge, Face, Etab) ->
    case gb_trees:get(Edge, Etab) of
	#edge{lf=Face,a=Col} -> Col;
	#edge{rf=Face,b=Col} -> Col
    end.

%%%
%%% Cut at an arbitrary position.
%%%

cut_pick(St) ->
    {Tvs,Sel} = wings_sel:fold(
		  fun(Es, We, []) ->
			  case gb_sets:to_list(Es) of
			      [E] -> cut_pick_make_tvs(E, We);
			      _ -> cut_pick_error()
			  end;
		     (_, _, _) ->
			  cut_pick_error()
		  end, [], St),
    Units = [{percent,{0.0,1.0}}],
    Flags = [{initial,[0]}],
    wings_drag:setup(Tvs, Units, Flags, wings_sel:set(vertex, Sel, St)).

cut_pick_error() ->
    wings_util:error(?STR(cut_pick_error,1,"Only one edge can be cut at an arbitrary position.")).

cut_pick_make_tvs(Edge, #we{id=Id,es=Etab,vp=Vtab,next_id=NewV}=We) ->
    #edge{vs=Va,ve=Vb} = gb_trees:get(Edge, Etab),
    Start = gb_trees:get(Va, Vtab),
    End = gb_trees:get(Vb, Vtab),
    Dir = e3d_vec:sub(End, Start),
    Char = {7,7,3,3,7,0,
	    <<2#01111100,
	     2#10000010,
	     2#10000010,
	     2#10000010,
	     2#10000010,
	     2#10000010,
	     2#01111100>>},
    Fun = fun(I, D) -> cut_pick_marker(I, D, Edge, We, Start, Dir, Char) end,
    Sel = [{Id,gb_sets:singleton(NewV)}],
    {{general,[{Id,Fun}]},Sel}.

cut_pick_marker([I], D, Edge, We0, Start, Dir, Char) ->
    {X,Y,Z} = Pos = e3d_vec:add_prod(Start, Dir, I),
    {MM,PM,ViewPort} = wings_util:get_matrices(0, original),
    {Sx,Sy,_} = glu:project(X, Y, Z, MM, PM, ViewPort),
    Dl = gl:genLists(1),
    gl:newList(Dl, ?GL_COMPILE),
    gl:pushAttrib(?GL_ALL_ATTRIB_BITS),
    gl:color3f(1, 0, 0),
    gl:shadeModel(?GL_FLAT),
    gl:disable(?GL_DEPTH_TEST),
    gl:matrixMode(?GL_PROJECTION),
    gl:pushMatrix(),
    gl:loadIdentity(),
    {W,H} = wings_wm:win_size(),
    glu:ortho2D(0, W, 0, H),
    gl:matrixMode(?GL_MODELVIEW),
    gl:pushMatrix(),
    gl:loadIdentity(),
    gl:rasterPos2f(Sx, Sy),
    wings_io:draw_char(Char),
    gl:popMatrix(),
    gl:matrixMode(?GL_PROJECTION),
    gl:popMatrix(),
    gl:popAttrib(),
    gl:endList(),
    {We,_} = fast_cut(Edge, Pos, We0),
    D#dlo{hilite={call_in_this_win,wings_wm:this(),Dl},src_we=We};
cut_pick_marker({finish,[I]}, D0, Edge, We, Start, Dir, Char) ->
    D = cut_pick_marker([I], D0, Edge, We, Start, Dir, Char),
    D#dlo{vs=none,hilite=none}.

%%%
%%% The Slide command.
%%%

slide(St) ->
    Mode = wings_pref:get_value(slide_mode, relative),
    Stop = wings_pref:get_value(slide_stop, false),
    State = {Mode,none,Stop},
    SUp = SDown = SN = SBi = {0.0,0.0,0.0},
    {Tvs,_,_,_,_,MinUp,MinDw} = 
	wings_sel:fold(
	  fun(EsSet, #we{id=Id} = We, {Acc,Up0,Dw0,N0,Bi0,MinUp,MinDw}) ->
		  LofEs0 = wings_edge_loop:partition_edges(EsSet, We),
		  LofEs = reverse(sort([{length(Es),Es} || Es <- LofEs0])),
		  {{Slides,MUp,MDw},Up,Dw,N,Bi} = 
		      slide_setup_edges(LofEs,Up0,Dw0,N0,Bi0,We,
					{gb_trees:empty(),MinUp,MinDw}),
		  {[{Id,make_slide_tv(Slides, State)}|Acc],Up,Dw,N,Bi,MUp,MDw}
	  end, {[], SUp, SDown, SN, SBi, unknown,unknown}, St),
    Units = slide_units(State,MinUp,MinDw),
    Flags = [{mode,{slide_mode(MinUp,MinDw),State}},{initial,[0]}],
    wings_drag:setup(Tvs, Units, Flags, St).

slide_mode(MinUp,MinDw) ->
    fun(help, State)              ->    slide_help(State);
       ({key,$1}, {relative,F,S}) ->    {absolute,F,S};
       ({key,$1}, {absolute,F,S}) ->    {relative,F,S};
       ({key,$2}, {Mode,none,S})  ->
	    case get(wings_slide) of
		undefined -> 
		    {Mode,none,S};
		Dx when Dx >= 0 -> 
		    {Mode,positive,S};
		_ -> 
		    {Mode,negative,S}
	    end;
       ({key,$2}, {Mode,_,S})     ->    {Mode,none,S};
       ({key,$3}, {Mode,F,false}) ->    {Mode,F,true};
       ({key,$3}, {Mode,F,true})  ->    {Mode,F,false};

       (units, NewState) ->
	    slide_units(NewState,MinUp,MinDw);
       
       (done, {NewMode,_,NewStop})->
	    wings_pref:set_value(slide_mode, NewMode),
	    wings_pref:set_value(slide_stop, NewStop),
	    erase(wings_slide);

       (_, _) -> none
    end.

slide_units({absolute,_,false},_,_) -> [distance];
slide_units({absolute,_Freeze,true},MinUp,MinDw) ->
    [{distance, {-MinUp, MinDw}}];
slide_units({relative,_,false},_,_) -> [percent];
slide_units({relative,_,true},_,_) -> [{percent,{-1.0,1.0}}].

slide_help({Mode,Freeze,Stop}) ->
    ["[1] ",slide_help_mode(Mode),
     "  [2] ",slide_help_freeze(Freeze),
     "  [3] ",slide_help_stop(Stop)].

slide_help_mode(relative) -> ?STR(slide_help_mode,1,"Absolute");
slide_help_mode(absolute) -> ?STR(slide_help_mode,2,"Relative").
slide_help_freeze(none)   -> ?STR(slide_help_mode,3,"Freeze direction");
slide_help_freeze(_)      -> ?STR(slide_help_mode,4,"Thaw direction").
slide_help_stop(false)    -> ?STR(slide_help_mode,5,"Stop at other edges");
slide_help_stop(true)     -> ?STR(slide_help_mode,6,"Continue past other edges").

make_slide_tv(Slides, State) ->
    Vs = gb_trees:keys(Slides),
    {Vs,make_slide_fun(Vs, Slides, State)}.

%% The calculating fun
slide_fun(Dx0,{Mode,Freeze,_Stop}, Slides) ->
    {Dx,I} = 
	case Freeze of   %% 3 = UP, 2 = Down
	    none when Dx0 >= 0 -> {Dx0, 3};
	    none ->               {-Dx0,2};
	    positive -> 	  {Dx0, 3};
	    negative ->           {-Dx0,2}
	end,
    case Mode of 
	relative ->
	    fun(V,A) ->
		    Slide = gb_trees:get(V, Slides),
		    {Dir, Len, Count} = element(I, Slide),
		    ScaleDir = e3d_vec:mul(e3d_vec:norm(Dir), Dx*(Len/Count)),
		    [{V,e3d_vec:add(element(1,Slide), ScaleDir)}|A]
	    end;
	absolute ->
	    fun(V,A) ->
		    Slide = gb_trees:get(V, Slides),
		    {Dir, _Len, _C} = element(I, Slide),
		    ScaleDir = e3d_vec:mul(e3d_vec:norm(Dir), Dx),
		    [{V,e3d_vec:add(element(1,Slide), ScaleDir)}|A]
	    end
    end.

make_slide_fun(Vs, Slides, State) ->
    fun([Dx|_],Acc) ->
	    put(wings_slide, Dx),
	    Fun = slide_fun(Dx,State,Slides),
	    foldl(Fun, Acc, Vs);
       (new_mode_data, {NewState,_}) ->
	    make_slide_fun(Vs,Slides,NewState);
       (_,_) ->
	    make_slide_fun(Vs,Slides,State)
    end.

slide_setup_edges([{_Sz,Es0}|LofEs],GUp0,GDw0,GN0,GBi0,We,Acc0) ->
    Parts = slide_part_loop(Es0,We),
    {GUp,GDw,GN,GBi,Acc} = slide_add_edges(Parts,GUp0,GDw0,GN0,GBi0,Acc0),
    slide_setup_edges(LofEs,GUp,GDw,GN,GBi,We,Acc);
slide_setup_edges([], Up,Dw,N,Bi,_,Slides) ->
    {Slides,Up,Dw,N,Bi}.

slide_add_edges([{LUp,LDw,LN,Es}|Parts],GUp,GDw,GN,GBi,Acc0) ->
    %%    io:format("UDN ~p ~p ~p ~p~n", [len(LUp), len(LDw), len(LN), length(Es)]),
    Count  = length(Es)/2,    
    Vec1   = norm(LUp), LenUp = len(LUp),
    Vec2   = norm(LDw), LenDw = len(LDw),
    Vec3   = norm(LN),  LenN  = len(LN),
    Bi     = norm(cross(Vec1,Vec3)),
    Rotation = dot(Bi, norm(GBi)),
%    io:format("BIs ~p ~p ~p ~p ~n", [Bi, norm(GBi), Rotation, Count]),
    case (LenUp/Count > 0.707) and (LenN/Count > 0.707) and
	(abs(Rotation) > 0.707) of
	true ->  %% Edge rings
	    Acc  = slide_dirs(Es,Rotation,Acc0),
	    slide_add_edges(Parts,GUp,GDw,GN,GBi,Acc);
	false ->
	    case (LenUp >= 1) or (LenDw >= 1)
		or (LenN =< 1) or (Count < 4) of
		true -> %% Make sure up is up..
		    DotUp1 = dot(Vec1,norm(GUp)), 
		    %%DotDw1 = dot(Vec1,norm(GDw)),
		    %%DotUp2 = dot(Vec2,norm(GUp)), 
		    DotDw2 = dot(Vec2,norm(GDw)),
		    if (DotUp1 >= 0) and (DotDw2 >= 0) ->
			    Acc  = slide_dirs(Es,1.0,Acc0),
			    slide_add_edges(Parts,add(Vec1, GUp),add(Vec2,GDw),
					    GN,add(GBi,Bi), Acc);
		       (DotUp1 =< 0) and (DotDw2 =< 0) ->
			    Acc  = slide_dirs(Es,-1.0,Acc0),
			    slide_add_edges(Parts,add(neg(Vec1),GUp),
					    add(neg(Vec2),GDw),
					    GN,add(GBi,neg(Bi)),Acc);
		       true ->
			    Acc  = slide_dirs(Es,-1.0,Acc0),
			    slide_add_edges(Parts,add(Vec2,GUp),
					    add(Vec1,GDw),GN,add(GBi,Bi),Acc)
		    end;
		false -> 
		    %% Probably a loop, make sure it goes in/out and not out/in.
		    %% BUGBUG this isn't good enough..
		    Norm0 = Vec3,
		    Dot = dot(Norm0,norm(GUp)),
		    Norm = if Dot < 0.0 -> neg(Norm0); true -> Norm0 end,
		    Acc = slide_dirs(Es,Dot,Acc0),
		    slide_add_edges(Parts,GUp,add(Norm, GDw),GN,GBi,Acc)
	    end
    end;
slide_add_edges([],GUp,GDw,GN,GBi,Acc) ->
    {GUp,GDw,GN,GBi,Acc}.

slide_dirs([{V1,V1dir},{V2,V2dir}|Es],Up,{Acc0,MinU0,MinD0}) ->
    {_,{_,V1M1},{_,V1M2}} = V1dir,
    {_,{_,V2M1},{_,V2M2}} = V2dir,
    case Up < 0 of
	true ->
	    MinU = lists:min([MinU0,V1M2,V2M2]),
	    MinD = lists:min([MinD0,V1M1,V2M1]),
	    Acc1 = add_slide_vertex(V1,swap(V1dir), Acc0),
	    Acc  = add_slide_vertex(V2,swap(V2dir), Acc1),
	    slide_dirs(Es,Up,{Acc,MinU,MinD});
	false ->
	    MinU = lists:min([MinU0,V1M1,V2M1]),
	    MinD = lists:min([MinD0,V1M2,V2M2]),
	    Acc1 = add_slide_vertex(V1,V1dir,Acc0),
	    Acc  = add_slide_vertex(V2,V2dir,Acc1),
	    slide_dirs(Es,Up,{Acc,MinU,MinD})
    end;
slide_dirs([],_,Acc) -> Acc.

slide_part_loop(Es,We) ->
    Def   = {0.0,0.0,0.0},
    Eis   = slide_gather_info(Es,We,[]),
    Parts = wings_edge_loop:edge_links(Es,We),
    [slide_dir(P,Eis,Def,Def,Def,[]) || P <- Parts].

slide_gather_info([Edge|Es],We=#we{es=Etab,vp=Vtab},Acc) ->
    #edge{vs=V1,ve=V2,ltpr=LP,ltsu=LS,lf=LF,rtpr=RP,rtsu=RS,rf=RF} = 
	gb_trees:get(Edge, Etab),
    A1 = other(V1,gb_trees:get(RP, Etab)),
    B1 = other(V1,gb_trees:get(LS, Etab)),
    A2 = other(V2,gb_trees:get(RS, Etab)),
    B2 = other(V2,gb_trees:get(LP, Etab)),
    N1 = wings_face:normal(LF,We), N2 = wings_face:normal(RF,We),
    N = norm(average(N2,N1)),
    V1pos = gb_trees:get(V1, Vtab),V2pos = gb_trees:get(V2, Vtab),
    A1pos = gb_trees:get(A1, Vtab),A2pos = gb_trees:get(A2, Vtab),
    B1pos = gb_trees:get(B1, Vtab),B2pos = gb_trees:get(B2, Vtab),
    E1v1  = sub(A1pos,V1pos), E2v1 = sub(B1pos,V1pos),
    E1v2  = sub(A2pos,V2pos), E2v2 = sub(B2pos,V2pos), 
    NE1v1 = norm(E1v1), NE2v1 = norm(E2v1),
    NE1v2 = norm(E1v2), NE2v2 = norm(E2v2),

    E1 = norm(average(NE1v1,NE1v2)), E2 = norm(average(NE2v1,NE2v2)),
    New = {V1, {V1pos,{NE1v1,len(E1v1)},{NE2v1,len(E2v1)}},
	   V2, {V2pos,{NE1v2,len(E1v2)},{NE2v2,len(E2v2)}},
	   E1, E2, N},
    slide_gather_info(Es, We, [{Edge,New}|Acc]);
slide_gather_info([],_,Acc) ->
    gb_trees:from_orddict(sort(Acc)).

slide_dir([Edge|R],Es,Up0,Dw0,N0,Acc) ->
    {V1id,V1E,V2id,V2E,E1,E2,MyN} = find_edge(Edge,Es),
    Up = add(Up0, E1),
    Dw = add(Dw0, E2),
    N  = add(N0, MyN),
    slide_dir(R,Es,Up,Dw,N,[{V1id,V1E},{V2id,V2E}|Acc]);
slide_dir([],_,Up,Dw,N,Acc) ->
    {Up,Dw,N,Acc}.

find_edge({Edge,V1,V2},Es) ->
    case gb_trees:get(Edge, Es) of
	{V1,_,V2,_,_,_,_} = R -> R;
	{V2,V2E,V1,V1E,E2,E1,N} ->
	    {V1,swap(V1E),V2,swap(V2E),E1,E2,N}
    end.

other(Vertex, #edge{vs=Vertex,ve=Other}) -> Other;
other(Vertex, #edge{vs=Other,ve=Vertex}) -> Other.

swap({Vpos,Ndir,Pdir}) -> 
    {Vpos,Pdir,Ndir}.

add_slide_vertex(V,{Vpos,{Ndir,NL},{Pdir,PL}},Acc) ->
    case gb_trees:lookup(V,Acc) of
	none ->
	    gb_trees:insert(V, {Vpos,{Ndir,NL,1},{Pdir,PL,1}},Acc);
	{value, {_, {Ndir0,NL0,NC0},{Pdir0,PL0,PC0}}} ->
	    New = {Vpos, {add(Ndir,Ndir0),NL+NL0,NC0+1},
		   {add(Pdir,Pdir0),PL+PL0,PC0+1}},
	    gb_trees:update(V, New, Acc)
    end.

%%%
%%% The Connect command.
%%%

connect(St0) ->
    {St,Sel} = wings_sel:mapfold(fun connect/3, [], St0),
    wings_sel:set(Sel, St).

connect(Es, #we{id=Id}=We0, Acc) ->
    {We1,Vs} = cut_edges(Es, We0),
    We2 = wings_vertex_cmd:connect(Vs, We1),
    Sel = wings_we:new_items(edge, We1, We2),
    We = dissolve_isolated_vs(Vs, We2),
    {We,[{Id,Sel}|Acc]}.

cut_edges(Es, We) ->
    gb_sets:fold(fun(Edge, {W0,Vs0}) ->
			 {W,V} = cut(Edge, 2, W0),
			 {W,[V|Vs0]}
		 end, {We,[]}, Es).

%%%
%%% The Dissolve command.
%%%

dissolve(St0) ->
    St = wings_sel:map(fun dissolve_edges/2, St0),
    wings_sel:clear(St).

dissolve_edge(Edge, We) ->
    dissolve_edges([Edge], We).

dissolve_edges(Edges0, We0) when is_list(Edges0) ->
    #we{es=Etab} = We = foldl(fun internal_dissolve_edge/2, We0, Edges0),
    case [E || E <- Edges0, gb_trees:is_defined(E, Etab)] of
	Edges0 ->
	    %% No edge was deleted in the last pass. We are done.
	    wings_util:validate_mirror(wings_we:vertex_gc(We));
	Edges ->
	    dissolve_edges(Edges, We)
    end;
dissolve_edges(Edges, We) ->
    dissolve_edges(gb_sets:to_list(Edges), We).

internal_dissolve_edge(Edge, #we{es=Etab}=We0) ->
    case gb_trees:lookup(Edge, Etab) of
	none -> We0;
	{value,#edge{ltpr=Same,ltsu=Same,rtpr=Same,rtsu=Same}} ->
	    Empty = gb_trees:empty(),
	    We0#we{vc=Empty,vp=Empty,es=Empty,fs=Empty,he=gb_sets:empty()};
	{value,#edge{rtpr=Back,ltsu=Back}=Rec} ->
	    merge_edges(backward, Edge, Rec, We0);
	{value,#edge{rtsu=Forward,ltpr=Forward}=Rec} ->
	    merge_edges(forward, Edge, Rec, We0);
	{value,Rec} ->
	    try dissolve_edge_1(Edge, Rec, We0) of
		We -> We
	    catch
		throw:hole -> We0
	    end
    end.

%% dissolve_edge_1(Edge, EdgeRecord, We) -> We
%%  Remove an edge and a face. If one of the faces is degenerated
%%  (only consists of two edges), remove that one. Otherwise, it
%%  doesn't matter which face we remove.
dissolve_edge_1(Edge, #edge{lf=Remove,rf=Keep,ltpr=Same,ltsu=Same}=Rec, We) ->
    dissolve_edge_2(Edge, Remove, Keep, Rec, We);
dissolve_edge_1(Edge, #edge{lf=Keep,rf=Remove}=Rec, We) ->
    dissolve_edge_2(Edge, Remove, Keep, Rec, We).

dissolve_edge_2(Edge, FaceRemove, FaceKeep,
		#edge{ltpr=LP,ltsu=LS,rtpr=RP,rtsu=RS},
		#we{fs=Ftab0,es=Etab0,he=Htab0}=We0) ->
    %% First change face for all edges surrounding the face we will remove.
    Etab1 = wings_face:fold(
	      fun (_, E, _, IntEtab) when E =:= Edge -> IntEtab;
		  (_, E, R, IntEtab) ->
		      case R of
			  #edge{lf=FaceRemove,rf=FaceKeep} ->
			      throw(hole);
			  #edge{rf=FaceRemove,lf=FaceKeep} ->
			      throw(hole);
			  #edge{lf=FaceRemove} ->
			      gb_trees:update(E, R#edge{lf=FaceKeep}, IntEtab);
			  #edge{rf=FaceRemove} ->
			      gb_trees:update(E, R#edge{rf=FaceKeep}, IntEtab)
		      end
	      end, Etab0, FaceRemove, We0),

    %% Patch all predecessors and successor of the edge we will remove.
    Etab2 = patch_edge(LP, RS, Edge, Etab1),
    Etab3 = patch_edge(LS, RP, Edge, Etab2),
    Etab4 = patch_edge(RP, LS, Edge, Etab3),
    Etab5 = patch_edge(RS, LP, Edge, Etab4),

    %% Remove the edge.
    Etab = gb_trees:delete(Edge, Etab5),
    Htab = hardness(Edge, soft, Htab0),

    %% Remove the face. Patch the face entry for the remaining face.
    Ftab1 = gb_trees:delete(FaceRemove, Ftab0),
    We1 = wings_material:delete_face(FaceRemove, We0),
    Ftab = gb_trees:update(FaceKeep, LP, Ftab1),

    %% Return result.
    We = We1#we{es=Etab,fs=Ftab,vc=undefined,he=Htab},
    AnEdge = gb_trees:get(FaceKeep, Ftab),
    case gb_trees:get(AnEdge, Etab) of
	#edge{lf=FaceKeep,ltpr=Same,ltsu=Same} ->
	    internal_dissolve_edge(AnEdge, We);
	#edge{rf=FaceKeep,rtpr=Same,rtsu=Same} ->
	    internal_dissolve_edge(AnEdge, We);
	_Other ->
	    case wings_we:is_face_consistent(FaceKeep, We) of
		true ->
		    We;
		false ->
		    wings_util:error(?STR(dissolve_edge_2,1,"Dissolving would cause a badly formed face."))
	    end
    end.

%% dissolve_isolated_vs([Vertex], We) -> We'
%%  Remove all isolated vertices ("winged vertices", or vertices
%%  having exactly two edges).
dissolve_isolated_vs([_|_]=Vs, We) ->
    dissolve_isolated_vs_1(Vs, We, []);
dissolve_isolated_vs([], We) -> We.

%% Since the dissolve operation will not keep the incident
%% edge table for vertices updated, we'll need to lookup
%% all incident edges now before we have started to dissolve.
dissolve_isolated_vs_1([V|Vs], #we{vc=Vct}=We, Acc) ->
    case gb_trees:lookup(V, Vct) of
	none ->
	    %% A previous pass has already removed this vertex.
	    dissolve_isolated_vs_1(Vs, We, Acc);
	{value,Edge} ->
	    dissolve_isolated_vs_1(Vs, We, [{V,Edge}|Acc])
    end;
dissolve_isolated_vs_1([], We, Vc) ->
    dissolve_isolated_vs_2(Vc, We, []).

%% Now do all dissolving.
dissolve_isolated_vs_2([{V,Edge}|T], We0, Acc) ->
    case dissolve_vertex(V, Edge, We0) of
	done -> dissolve_isolated_vs_2(T, We0, Acc);
	We -> dissolve_isolated_vs_2(T, We, [V|Acc])
    end;
dissolve_isolated_vs_2([], We0, Vs) ->
    We = wings_we:vertex_gc(We0),

    %% Now do another pass over the vertices still in our list.
    %% Reason:
    %%
    %% 1. An incident edge may have become wrong by a previous
    %%    dissolve (on another vertex). Do another try now that
    %%    the incident table has been rebuilt.
    %%
    %% 2. A vertex may have be connected to two faces that
    %%    have no edge in common. In that case, all edges
    %%    are not reachable from the incident edge.
    dissolve_isolated_vs(Vs, We).

%% dissolve(V, Edge, We0) -> We|done
%%  Dissolve the given vertex. The 'done' return value means
%%  that the vertex is already non-existing (or is not isolated).
%%  If a We is returned, the caller must call this function again
%%  (after rebuilding the incident table) since there might be more
%%  work to do. 
dissolve_vertex(V, Edge, #we{es=Etab}=We0) ->
    case gb_trees:lookup(Edge, Etab) of
	{value,#edge{vs=V,ltsu=AnEdge,rtpr=AnEdge}=Rec} ->
	    merge_edges(backward, Edge, Rec, We0);
	{value,#edge{ve=V,rtsu=AnEdge,ltpr=AnEdge}=Rec} ->
	    merge_edges(forward, Edge, Rec, We0);

	%% Handle the case that the incident edge is correct for
	%% the given vertex, but the vertex is NOT isolated.
	{value,#edge{vs=V}} -> done;
	{value,#edge{ve=V}} -> done;

	%% The incident edge is either non-existing or no longer
	%% references the given edge. In this case, we'll need
	%% to try dissolving the vertex again in the next
	%% pass after the incident table has been rebuilt.
	none -> We0;
	{value,_} -> We0
    end.

%%
%% We like winged edges, but not winged vertices (a vertex with
%% only two edges connected to it). We will remove the winged vertex
%% by joining the two edges connected to it.
%%

merge_edges(Dir, Edge, Rec, #we{es=Etab}=We) ->
    {Va,Vb,_,_,_,_,To,To} = half_edge(Dir, Rec),
    case gb_trees:get(To, Etab) of
	#edge{vs=Va,ve=Vb} ->
	    del_2edge_face(Dir, Edge, Rec, To, We);
	#edge{vs=Vb,ve=Va} ->
	    del_2edge_face(Dir, Edge, Rec, To, We);
	_Other ->
	    merge_1(Dir, Edge, Rec, To, We)
    end.

merge_1(Dir, Edge, Rec, To, #we{es=Etab0,fs=Ftab0,he=Htab0}=We) ->
    OtherDir = reverse_dir(Dir),
    {Vkeep,Vdelete,Lf,Rf,A,B,L,R} = half_edge(OtherDir, Rec),
    Etab1 = patch_edge(L, To, Edge, Etab0),
    Etab2 = patch_edge(R, To, Edge, Etab1),
    Etab3 = patch_half_edge(To, Vkeep, Lf, A, L, Rf, B, R, Vdelete, Etab2),
    Htab = hardness(Edge, soft, Htab0),
    Etab = gb_trees:delete(Edge, Etab3),
    #edge{lf=Lf,rf=Rf} = Rec,
    Ftab1 = update_face(Lf, To, Edge, Ftab0),
    Ftab = update_face(Rf, To, Edge, Ftab1),
    merge_2(To, We#we{es=Etab,fs=Ftab,he=Htab,vc=undefined}).

merge_2(Edge, #we{es=Etab}=We) ->
    %% If the merged edge is part of a two-edge face, we must
    %% remove that edge too.
    case gb_trees:get(Edge, Etab) of
	#edge{ltpr=Same,ltsu=Same} ->
	    internal_dissolve_edge(Edge, We);
	#edge{rtpr=Same,rtsu=Same} ->
	    internal_dissolve_edge(Edge, We);
	_Other -> We
    end.

update_face(Face, Edge, OldEdge, Ftab) ->
    case gb_trees:get(Face, Ftab) of
	OldEdge -> gb_trees:update(Face, Edge, Ftab);
	_Other -> Ftab
    end.

del_2edge_face(Dir, EdgeA, RecA, EdgeB,
	       #we{es=Etab0,fs=Ftab0,he=Htab0}=We) ->
    {_,_,Lf,Rf,_,_,_,_} = half_edge(reverse_dir(Dir), RecA),
    RecB = gb_trees:get(EdgeB, Etab0),
    Del = gb_sets:from_list([EdgeA,EdgeB]),
    EdgeANear = stabile_neighbor(RecA, Del),
    EdgeBNear = stabile_neighbor(RecB, Del),
    Etab1 = patch_edge(EdgeANear, EdgeBNear, EdgeA, Etab0),
    Etab2 = patch_edge(EdgeBNear, EdgeANear, EdgeB, Etab1),
    Etab3 = gb_trees:delete(EdgeA, Etab2),
    Etab = gb_trees:delete(EdgeB, Etab3),

    %% Patch hardness table.
    Htab1 = hardness(EdgeA, soft, Htab0),
    Htab = hardness(EdgeB, soft, Htab1),

    %% Patch the face table.
    #edge{lf=Klf,rf=Krf} = gb_trees:get(EdgeANear, Etab),
    KeepFaces = ordsets:from_list([Klf,Krf]),
    EdgeAFaces = ordsets:from_list([Lf,Rf]),
    [DelFace] = ordsets:subtract(EdgeAFaces, KeepFaces),
    Ftab1 = gb_trees:delete(DelFace, Ftab0),
    [KeepFace] = ordsets:intersection(KeepFaces, EdgeAFaces),
    Ftab2 = update_face(KeepFace, EdgeANear, EdgeA, Ftab1),
    Ftab = update_face(KeepFace, EdgeBNear, EdgeB, Ftab2),

    %% Return result.
    We#we{vc=undefined,es=Etab,fs=Ftab,he=Htab}.

stabile_neighbor(#edge{ltpr=Ea,ltsu=Eb,rtpr=Ec,rtsu=Ed}, Del) ->
    [Edge] = foldl(fun(E, A) ->
			   case gb_sets:is_member(E, Del) of
			       true -> A;
			       false -> [E|A]
			   end
		   end, [], [Ea,Eb,Ec,Ed]),
    Edge.

%%%
%%% The Hardness command.
%%%

hardness(soft, St) ->
    wings_sel:map(fun(Edges, #we{he=Htab0}=We) ->
			  Htab = gb_sets:difference(Htab0, Edges),
			  We#we{he=Htab}
		  end, St);
hardness(hard, St) ->
    wings_sel:map(fun(Edges, #we{he=Htab0}=We) ->
			  Htab = gb_sets:union(Htab0, Edges),
			  We#we{he=Htab}
		  end, St).

hardness(Edge, soft, Htab) ->
    case gb_sets:is_member(Edge, Htab) of
	true -> gb_sets:delete(Edge, Htab);
	false -> Htab
    end;
hardness(Edge, hard, Htab) -> gb_sets:add(Edge, Htab).

%%%
%%% "Select faces on one side of an edge loop."
%%%
%%% This description is pretty ambigous. If there are
%%% multiple edge loops, it is not clear what to select.
%%%
%%% What we do for each object is to collect all faces
%%% sandwhiched between one or more edge loops. We then
%%% partition all those face collection into one partition
%%% for each sub-object (if there are any). For each
%%% sub-object, we arbitrarily pick the face collection
%%% having the smallest number of faces.
%%%

select_region(#st{selmode=edge}=St) ->
    Sel = wings_sel:fold(fun select_region/3, [], St),
    wings_sel:set(face, Sel, St);
select_region(St) -> St.

select_region(Edges, #we{id=Id}=We, Acc) ->
    Part = wings_edge_loop:partition_edges(Edges, We),
    FaceSel0 = select_region_1(Part, Edges, We, []),
    FaceSel = wings_sel:subtract_mirror_face(FaceSel0, We),
    [{Id,FaceSel}|Acc].

select_region_1([[AnEdge|_]|Ps], Edges, #we{es=Etab}=We, Acc) ->
    #edge{lf=Lf,rf=Rf} = gb_trees:get(AnEdge, Etab),
    Left = collect_faces(Lf, Edges, We),
    Right = collect_faces(Rf, Edges, We),

    %% We'll let AnEdge identify the edge loop that each
    %% face collection borders to.
    select_region_1(Ps, Edges, We, [{Left,AnEdge},{Right,AnEdge}|Acc]);
select_region_1([], _Edges, _We, Acc) ->
    %% Now we have all collections of faces sandwhiched between
    %% one or more edge loops. Using the face collections as keys,
    %% we will partition the edge loop identifiers into groups.

    Rel0 = [{gb_sets:to_list(Set),Edge} || {Set,Edge} <- Acc],
    Rel = sofs:relation(Rel0),
    Fam = sofs:relation_to_family(Rel),
    DirectCs = sofs:to_external(sofs:range(Fam)),

    %% DirectCs now contains lists of edge loop identifiers that
    %% can reach each other through a collection of face.
    %% Using a digraph, partition edge loop into components
    %% (each edge loop in a component can reach any other edge loop
    %% directly or indirectly).

    G = digraph:new(),
    make_digraph(G, DirectCs),
    Cs = digraph_utils:components(G),
    digraph:delete(G),

    %% Now having the components, consisting of edge identifiers
    %% identifying the original edge loop, we now need to partition
    %% the actual collection of faces.

    PartKey0 = [[{K,sofs:from_term(F)} || K <- Ks] || [F|_]=Ks <- Cs],
    PartKey = gb_trees:from_orddict(sort(lists:append(PartKey0))),
    SetFun = fun(S) ->
		     {_,[E|_]} = sofs:to_external(S),
		     gb_trees:get(E, PartKey)
	     end,
    Part = sofs:to_external(sofs:partition(SetFun, Fam)),

    %% We finally have one partition for each sub-object.

    Sel0 = [select_region_2(P) || P <- Part],
    Sel = lists:merge(Sel0),
    gb_sets:from_ordset(Sel).

select_region_2(P) ->
    case [Fs || {Fs,[_]} <- P] of
	[_|_]=Fss when length(Fss) < length(P) ->
	    lists:merge(Fss);
	_ ->
	    [{_,Fs}|_] = sort([{length(Fs),Fs} || {Fs,_} <- P]),
	    Fs
    end.

make_digraph(G, [Es|T]) ->
    make_digraph_1(G, Es),
    make_digraph(G, T);
make_digraph(_, []) -> ok.

make_digraph_1(G, [E]) ->
    digraph:add_vertex(G, E);
make_digraph_1(G, [E1|[E2|_]=Es]) ->
    digraph:add_vertex(G, E1),
    digraph:add_vertex(G, E2),
    digraph:add_edge(G, E1, E2),
    make_digraph_1(G, Es).

%%%
%%% The Loop Cut command.
%%%

loop_cut(#st{onext=NextId}=St0) ->
    St1 = wings_sel:map(fun(_, #we{mirror=none}=We) -> We;
			   (_, We) ->We#we{mirror=none}
			end, St0),
    {Sel0,St2} = wings_sel:fold(fun loop_cut/3, {[],St1}, St1),
    St3 = wings_sel:set(face, Sel0, St2),
    #st{sel=Sel1} = St = wings_face_cmd:dissolve(St3),
    Sel = [S || {Id,_}=S <- Sel1, Id >= NextId],
    wings_body:convert_selection(wings_sel:set(body, Sel, St)).

loop_cut(Edges, #we{name=Name,id=Id,es=Etab}=We, {Sel0,St}) ->
    AdjFaces = loop_cut_adj_faces(gb_sets:to_list(Edges), Etab, []),
    case loop_cut_1(AdjFaces, Edges, We, []) of
	[_] ->
	    wings_util:error(?STR(loop_cut,1,"Edge loop doesn't divide ~p  into two (or more) parts."), [Name]);
	Parts0 ->
	    Parts1 = [{gb_trees:size(P),P} || P <- Parts0],
	    Parts2 = reverse(sort(Parts1)),
	    [_|Parts] = [P || {_,P} <- Parts2],
	    NotInvolved = wings_sel:inverse_items(face, gb_sets:union(Parts), We),
	    Orig = wings_sel:inverse_items(face, NotInvolved, We),
	    Sel = [{Id,Orig}|Sel0],
	    loop_cut_make_copies(Parts, We, Sel, St)
    end.

loop_cut_make_copies([P|Parts], We, Sel0, #st{onext=Id}=St0) ->
    Sel = [{Id,wings_sel:inverse_items(face, P, We)}|Sel0],
    St = wings_shape:insert(We, cut, St0),
    loop_cut_make_copies(Parts, We, Sel, St);
loop_cut_make_copies([], _, Sel, St) -> {Sel,St}.

loop_cut_1(Faces0, Edges, We, Acc) ->
    case gb_trees:is_empty(Faces0) of
	true -> Acc;
	false ->
	    {AFace,Faces1} = gb_sets:take_smallest(Faces0),
	    Reachable = collect_faces(AFace, Edges, We),
	    Faces = gb_sets:difference(Faces1, Reachable),
	    loop_cut_1(Faces, Edges, We, [Reachable|Acc])
    end.

loop_cut_adj_faces([E|Es], Etab, Acc) ->
    #edge{lf=Lf,rf=Rf} = gb_trees:get(E, Etab),
    loop_cut_adj_faces(Es, Etab, [Lf,Rf|Acc]);
loop_cut_adj_faces([], _, Acc) ->
    gb_sets:from_list(Acc).

collect_faces(Face, Edges, We) ->
    collect_faces(gb_sets:singleton(Face), We, Edges, gb_sets:empty()).

collect_faces(Work0, We, Edges, Acc0) ->
    case gb_sets:is_empty(Work0) of
	true -> Acc0;
	false ->
	    {Face,Work1} = gb_sets:take_smallest(Work0),
	    Acc = gb_sets:insert(Face, Acc0),
	    Work = collect_maybe_add(Work1, Face, Edges, We, Acc),
	    collect_faces(Work, We, Edges, Acc)
    end.

collect_maybe_add(Work, Face, Edges, We, Res) ->
    wings_face:fold(
      fun(_, Edge, Rec, A) ->
	      case gb_sets:is_member(Edge, Edges) of
		  true -> A;
		  false ->
		      Of = wings_face:other(Face, Rec),
		      case gb_sets:is_member(Of, Res) of
			  true -> A;
			  false -> gb_sets:add(Of, A)
		      end
	      end
      end, Work, Face, We).

%%%
%%% Edge Ring. (Based on Anders Conradi's plug-in.)
%%%

select_edge_ring(#st{selmode=edge}=St) ->
    Sel = wings_sel:fold(fun build_selection/3, [], St),
    wings_sel:set(Sel, St);
select_edge_ring(St) -> St.

select_edge_ring_incr(#st{selmode=edge}=St) ->
    Sel = wings_sel:fold(fun incr_ring_selection/3, [], St),
    wings_sel:set(Sel, St);
select_edge_ring_incr(St) -> St.

select_edge_ring_decr(#st{selmode=edge}=St) ->
    Sel = wings_sel:fold(fun decr_ring_selection/3, [], St),
    wings_sel:set(Sel, St);
select_edge_ring_decr(St) -> St.

build_selection(Edges, #we{id=Id} = We, ObjAcc) ->
    [{Id,foldl(fun(Edge, EdgeAcc) ->
		       grow_from_edge(Edge, We, EdgeAcc)
	       end, gb_sets:empty(), gb_sets:to_list(Edges))}|ObjAcc].

grow_from_edge(unknown, _We, Selected) -> Selected;
grow_from_edge(Edge, We, Selected0) ->
    case gb_sets:is_member(Edge, Selected0) of
        true ->
	    Selected0;
        false ->
	    Selected = gb_sets:add(Edge, Selected0),
	    LeftSet = grow_from_edge(opposing_edge(Edge, We, left), We, Selected),
	    grow_from_edge(opposing_edge(Edge, We, right), We, LeftSet)
    end.

opposing_edge(Edge, #we{es=Es}=We, Side) ->
    #edge{lf=Left,rf=Right} = gb_trees:get(Edge, Es),
    Face = case Side of
               left -> Left;
               right -> Right
           end,
    %% Get opposing edge or fail.
    case wings_face:vertices(Face, We) of
        4 -> next_edge(next_edge(Edge, Face, We), Face, We);
        _ -> unknown
    end.

next_edge(Edge, Face, #we{es=Etab})->
    case gb_trees:get(Edge, Etab) of
        #edge{lf=Face,ltsu=NextEdge} -> NextEdge;
        #edge{rf=Face,rtsu=NextEdge} -> NextEdge
    end.

incr_ring_selection(Edges, #we{id=Id} = We, ObjAcc) ->
    [{Id,foldl(fun(Edge, EdgeAcc) ->
		       incr_from_edge(Edge, We, EdgeAcc)
	       end, gb_sets:empty(), gb_sets:to_list(Edges))}|ObjAcc].

incr_from_edge(Edge, We, Acc) ->
    Selected = gb_sets:add(Edge, Acc),
    LeftSet =
	case opposing_edge(Edge, We, left) of
	    unknown -> Selected;
	    Left -> gb_sets:add(Left, Selected)
	end,
    case opposing_edge(Edge, We, right) of
	unknown -> LeftSet;
	Right -> gb_sets:add(Right, LeftSet)
    end.

decr_ring_selection(Edges, #we{id=Id} = We, ObjAcc) ->
    [{Id,foldl(fun(Edge, EdgeAcc) ->
		       decr_from_edge(Edge, We, Edges, EdgeAcc)
	       end, Edges, gb_sets:to_list(Edges))}|ObjAcc].

decr_from_edge(Edge, We, Orig, Acc) ->
    Left = opposing_edge(Edge, We, left),
    Right =  opposing_edge(Edge, We, right),
    case (Left == unknown) or (Right == unknown) of
	true ->
	    gb_sets:delete(Edge,Acc);
	false ->
	    case gb_sets:is_member(Left, Orig) and
		gb_sets:is_member(Right, Orig) of
		true ->
		    Acc;
		false ->
		    gb_sets:delete(Edge,Acc)
	    end
    end.

%%%
%%% Set vertex color for selected edges.
%%%

set_color(Color, St) ->
    wings_sel:map(fun(Es, We) ->
			  set_color_1(gb_sets:to_list(Es), Color,
				      We#we{mode=vertex})
		  end, St).

set_color_1([E|Es], Color, #we{es=Etab0}=We) ->
    Rec0 = #edge{vs=Va,ve=Vb,rtpr=Rp,ltpr=Lp} = gb_trees:get(E, Etab0),
    Rec = Rec0#edge{a=Color,b=Color},
    Etab1 = gb_trees:update(E, Rec, Etab0),
    Etab2 = set_color_2(Rp, Va, Color, Etab1),
    Etab = set_color_2(Lp, Vb, Color, Etab2),
    set_color_1(Es, Color, We#we{es=Etab});
set_color_1([], _, We) -> We.

set_color_2(E, V, Color, Etab) ->
    Rec = case gb_trees:get(E, Etab) of
	      #edge{vs=V}=Rec0 -> Rec0#edge{a=Color};
	      #edge{ve=V}=Rec0 -> Rec0#edge{b=Color}
	  end,
    gb_trees:update(E, Rec, Etab).

%%%
%%% Utilities.
%%%

reverse_dir(forward) -> backward;
reverse_dir(backward) -> forward.

half_edge(backward, #edge{vs=Va,ve=Vb,lf=Lf,rf=Rf,a=A,b=B,ltsu=L,rtpr=R}) ->
    {Va,Vb,Lf,Rf,A,B,L,R};
half_edge(forward, #edge{ve=Va,vs=Vb,lf=Lf,rf=Rf,a=A,b=B,ltpr=L,rtsu=R}) ->
    {Va,Vb,Lf,Rf,A,B,L,R}.

patch_half_edge(Edge, V, FaceA, A, Ea, FaceB, B, Eb, OrigV, Etab) ->
    New = case gb_trees:get(Edge, Etab) of
	      #edge{vs=OrigV,lf=FaceA,rf=FaceB}=Rec ->
		  Rec#edge{a=A,vs=V,ltsu=Ea,rtpr=Eb};
	      #edge{vs=OrigV,lf=FaceB,rf=FaceA}=Rec ->
		  Rec#edge{a=B,vs=V,ltsu=Eb,rtpr=Ea};
	      #edge{ve=OrigV,lf=FaceA,rf=FaceB}=Rec ->
		  Rec#edge{b=B,ve=V,ltpr=Ea,rtsu=Eb};
	      #edge{ve=OrigV,lf=FaceB,rf=FaceA}=Rec ->
		  Rec#edge{b=A,ve=V,ltpr=Eb,rtsu=Ea}
	  end,
    gb_trees:update(Edge, New, Etab).

patch_edge(Edge, ToEdge, OrigEdge, Etab) ->
    New = case gb_trees:get(Edge, Etab) of
	      #edge{ltsu=OrigEdge}=R ->
		  R#edge{ltsu=ToEdge};
	      #edge{ltpr=OrigEdge}=R ->
		  R#edge{ltpr=ToEdge};
	      #edge{rtsu=OrigEdge}=R ->
		  R#edge{rtsu=ToEdge};
	      #edge{rtpr=OrigEdge}=R ->
		  R#edge{rtpr=ToEdge}
	  end,
    gb_trees:update(Edge, New, Etab).

patch_edge(Edge, ToEdge, Face, OrigEdge, Etab) ->
    New = case gb_trees:get(Edge, Etab) of
	      #edge{lf=Face,ltsu=OrigEdge}=R ->
		  R#edge{ltsu=ToEdge};
	      #edge{lf=Face,ltpr=OrigEdge}=R ->
		  R#edge{ltpr=ToEdge};
	      #edge{rf=Face,rtsu=OrigEdge}=R ->
		  R#edge{rtsu=ToEdge};
	      #edge{rf=Face,rtpr=OrigEdge}=R ->
		  R#edge{rtpr=ToEdge}
	  end,
    gb_trees:update(Edge, New, Etab).
