1%%
2%%  wpc_rib.erl --
3%%
4%%     Renderman exporter.
5%%
6%%  Copyright (c) 2002 Bjorn Gustavsson, Danni Coy (KayosIII).
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$
12
13-module(wpc_rib).
14-include_lib("e3d.hrl").
15-include_lib("e3d_image.hrl").
16
17-export([init/0,menu/2,command/2]).
18
19-import(lists, [foldl/3,map/2,foreach/2,reverse/1,seq/2,
20		flat_length/1,append/1,append/2]).
21
22init() ->
23    %% Disabled.
24    false.
25
26menu({file,export}, Menu) ->
27    menu_entry(Menu);
28menu({file,export_selected}, Menu) ->
29    menu_entry(Menu);
30menu({file,render}, Menu0) ->
31    Menu1 = case os:find_executable("rendrib") of
32		false -> Menu0;
33		_Path -> Menu0 ++ [{"BMRT 2.6",rendrib,[option]}]
34	    end,
35    Menu2 = case os:find_executable("air") of
36		false -> Menu1;
37		_Path2 -> Menu1 ++ [{"Air",air,[option]}]
38	   end,
39    Menu3 = case os:find_executable("entropy") of
40		false -> Menu2;
41		_Path3 -> Menu2 ++  [{"Entropy",entropy,[option]}]
42	    end,
43    Menu3;
44menu(_, Menu) -> Menu.
45
46command({file,{export,{rib,Ask}}}, St) ->
47    Exporter = fun(Ps, Fun) -> wpa:export(Ps, Fun, St) end,
48    do_export(Ask, export, Exporter, St);
49command({file,{export_selected,{rib,Ask}}}, St) ->
50    Exporter = fun(Ps, Fun) -> wpa:export_selected(Ps, Fun, St) end,
51    do_export(Ask, export_selected, Exporter, St);
52command({file,{render,{rendrib,Ask}}}, St) ->
53    do_render(Ask, rendrib, St);
54command({file,{render,{air, Ask}}}, St) ->
55    do_render(Ask, air, St);
56command({file, {render, {entropy, Ask}}}, St) ->
57    do_render(Ask, entropy, St);
58command(_, _) -> next.
59
60menu_entry(Menu) ->
61    Menu ++ [{"RenderMan (.rib)...",rib,[option]}].
62
63props() ->
64    [{ext,".rib"},{ext_desc,"RenderMan File"}].
65
66render_props() ->
67    [{ext,".tif"},{ext_desc,"Tiff Bitmap"}].
68
69dialog_qs(export)->
70    MeshVar = {mesh_type,get_pref(mesh_type, poly)},
71    [{vframe,
72      [{key_alt,MeshVar,"Polygon Mesh (older renderer)",poly},
73       {key_alt,MeshVar,"Subdivision Mesh (smoother)",subdiv}],
74      [{title,"Mesh Type"}]},
75     {"Triangulate Faces (needed for BMRT)",get_pref(triangulate, true),
76      [{key,triangulate}]},
77     {"Expand Faces (BMRT)",get_pref(expand_faces, true),
78      [{key,expand_faces}]},
79     {"Export UV Coordinates",get_pref(export_uv, true),[{key,export_uv}]}|
80     common_dialog()].
81dialog_qs(render, Engine)->
82    DefVar = {render_type,get_pref(render_type, preview)},
83    [{hframe,
84      [{vframe,
85	[{key_alt,DefVar,"Preview Window",preview},
86	 {key_alt,DefVar,"File",file}],
87	[{title,"Output"}]},
88       {vframe,
89	[{label_column,
90	  [{"Width",{text,get_pref(width, 320),[{key,width}]}},
91	   {"Height",{text,get_pref(height, 240),[{key,height}]}}]}],
92	[{title,"Resolution"}]}]}|render_dialog(Engine)].
93
94render_dialog(rendrib) ->
95    MeshVar = {mesh_type,get_pref(mesh_type, poly)},
96    [{vframe,
97      [{key_alt,MeshVar,"Polygon Mesh (older renderer)",poly},
98       {"Export UV Coordinates",get_pref(export_uv, false),[{key,export_uv}]},
99       {key_alt,MeshVar,"Subdivision Mesh (smoother)",subdiv}],
100      [{title,"Mesh Type"}]}| common_dialog()];
101render_dialog(air) ->
102    MeshVar = {mesh_type,get_pref(mesh_type, subdiv)},
103    [{vframe,
104      [{key_alt,MeshVar,"Polygon Mesh (older renderer)",poly},
105       {key_alt,MeshVar,"Subdivision Mesh (smoother)",subdiv}],
106      [{title,"Mesh Type"}]},
107     {"Export UV Coordinates",get_pref(export_uv, true),[{key,export_uv}]} | common_dialog()];
108render_dialog(entropy) ->
109    MeshVar = {mesh_type,get_pref(mesh_type, subdiv)},
110    [{vframe,
111      [{key_alt,MeshVar,"Polygon Mesh (older renderer)",poly},
112       {key_alt,MeshVar,"Subdivision Mesh (smoother)",subdiv}],
113      [{title,"Mesh Type"}]},
114     {"Export UV Coordinates",get_pref(export_uv, true),[{key,export_uv}]} | common_dialog()].
115
116common_dialog() ->
117    [{"Export Normals",get_pref(export_normals, true),[{key,export_normals}]}].
118
119get_pref(Key, Def) ->
120    wpa:pref_get(?MODULE, Key, Def).
121
122set_pref(KeyVals) ->
123    wpa:pref_set(?MODULE, KeyVals).
124
125%%%
126%%% Rendering.
127%%%
128
129do_render(Ask, Engine, _St) when is_atom(Ask) ->
130    wpa:dialog(Ask, "RIB Rendering Options", dialog_qs(render, Engine),
131	       fun(Res) ->
132		       {file,{render,{Engine,Res}}}
133	       end);
134do_render(Attr0, Engine, St) ->
135    set_pref(Attr0),
136    Attr1 = case proplists:get_value(render_type, Attr0) of
137		file ->
138		    RendFile = wpa:export_filename(render_props(), St),
139		    [{render_file,RendFile}|Attr0];
140		preview -> Attr0
141	    end,
142    Ls = wpa:lights(St),
143    Attr2 = [{lights,Ls},{tmp_render,Engine}|Attr1],
144    Attr = add_attr(Engine, Attr2),
145    wpa:export(none, render_fun(Attr), St).
146
147add_attr(rendrib, Attr) ->
148    case proplists:get_value(mesh_type, Attr) of
149	poly ->
150	    TriFs = true, ExpandFs = true;
151	_ ->
152	    TriFs = false, ExpandFs = false
153    end,
154    [{triangulate,TriFs},{expand_faces,ExpandFs}|Attr];
155add_attr(air, Attr) ->
156    [{triangulate,false},{expand_faces,false}|Attr];
157add_attr(entropy, Attr) ->
158    [{triangulate,false},{expand_faces,false}|Attr].
159
160render_fun(Attr) ->
161    fun(Filename, Contents) ->
162	    case render(Filename, Contents, Attr) of
163		ok -> ok;
164		{error,Error} -> {error,Error}
165	    end
166    end.
167
168render(none, Contents, Attr) ->
169    TmpName = "wpc_rib_temp" ++ random_string() ++ ".rib",
170    TxList = export_1(TmpName, Contents, Attr),
171    Width = proplists:get_value(width, Attr),
172    Height = proplists:get_value(height, Attr),
173    Renderer0 = proplists:get_value(tmp_render, Attr),
174    Options1 = case Renderer0 of
175		   rendrib ->
176		       " -silent -res " ++ integer_to_list(Width) ++ " " ++
177			   integer_to_list(Height) ++ " -d 16 ";
178		   air ->
179		       " ";
180		   entropy ->
181		       " -silent -res " ++ integer_to_list(Width) ++ " " ++
182			   integer_to_list(Height) ++ " -d 16 "
183	       end,
184    Options2 = case Renderer0 of
185		   rendrib ->
186		       " -silent -res " ++ integer_to_list(Width) ++ " " ++
187			   integer_to_list(Height) ++ " ";
188		   air ->
189		       " ";
190		   entropy ->
191		       " -silent -res " ++ integer_to_list(Width) ++ " " ++
192			   integer_to_list(Height) ++ " "
193	       end,
194    Renderer = atom_to_list(Renderer0),
195    F = fun() ->
196		case proplists:get_value(render_file, Attr) of
197		    undefined ->
198			os:cmd(Renderer ++ Options1 ++ TmpName);
199		    RendFile ->
200			os:cmd(Renderer ++ Options2 ++ TmpName),
201			case os:find_executable("iv") of
202			    false -> true;
203			    _Path ->  os:cmd("iv " ++ RendFile)
204			end
205		end,
206		ok = file:delete(TmpName),
207		foreach(fun(TmpImg) ->
208				ok = file:delete(TmpImg)
209			end, TxList)
210	end,
211    spawn(F),
212    ok.
213
214random_string() ->
215    {A,B,C} = now(),
216    foldl(fun(I, Acc) ->
217		  integer_to_list(I) ++ [$_|Acc]
218	  end, [$_|os:getpid()], [A,B,C]).
219
220
221
222
223%%%
224%%% Export functions.
225%%%
226
227do_export(Ask, Op, _Exporter, _St) when is_atom(Ask) ->
228    wpa:dialog(Ask, "RIB Export Options", dialog_qs(export),
229	       fun(Res) ->
230		       {file,{Op,{rib,Res}}}
231	       end);
232do_export(Attr0, _Op, Exporter, St) when is_list(Attr0) ->
233    set_pref(Attr0),
234    Ls = wpa:lights(St),
235    Attr = [{lights,Ls},{tmp_render,none}|Attr0],
236    Exporter(props(), export_fun(Attr)).
237
238export_fun(Attr) ->
239    fun(Filename, Contents) ->
240	    export_1(Filename, Contents, Attr)
241    end.
242
243export_1(Name, #e3d_file{objs=Objs,mat=Mat,creator=Creator}, Attr) ->
244    {ok,F} = file:open(Name, [write]),
245    Base = filename:basename(filename:rootname(Name, ".rib")),
246    io:format(F, "# Exported from ~s\n", [Creator]),
247    case proplists:get_value(render_file, Attr) of
248    	undefined -> ok;
249	RenderFile0 ->
250	    RenderFile = filename:basename(RenderFile0),
251	    io:format(F, "Display ~p \"file\" \"rgba\"\n", [RenderFile])
252    end,
253    export_camera(F),
254    io:put_chars(F, "WorldBegin\n"),
255    io:put_chars(F, "Identity\n"),
256    export_lights(F, Attr),
257    TmpImgs = export_materials_one(Mat, Base, Attr),
258    foreach(fun(Obj) -> export_object(F, Obj, Mat, Base, Attr) end, Objs),
259    io:put_chars(F, "WorldEnd\n"),
260    ok = file:close(F),
261    case proplists:get_value(tmp_render, Attr) of
262  	none -> true;
263  	_ -> TmpImgs
264    end,
265    ok.
266
267export_object(F, #e3d_object{name=Name,obj=Mesh0}, Mat, Base, Attr) ->
268    Mesh1 = case proplists:get_bool(triangulate, Attr) of
269		true -> e3d_mesh:triangulate(Mesh0);
270		false -> Mesh0
271	    end,
272    Mesh = e3d_mesh:vertex_normals(Mesh1),
273
274    io:format(F, "# Object: ~s\n", [Name]),
275    io:put_chars(F, "AttributeBegin\n"),
276    #e3d_mesh{fs=Fs0} = Mesh,
277    Fs1 = [{M,FaceRec} || #e3d_face{mat=M}=FaceRec <- Fs0],
278    Fs = sofs:to_external(sofs:relation_to_family(sofs:relation(Fs1))),
279    export_all(F, Fs, Mesh, Base, Mat, Attr),
280    io:put_chars(F, "AttributeEnd\n").
281
282export_all(F, [{[MatName],Faces}|T], OrigMesh, Base, Mat, Attr) ->
283    write_shader(F, MatName, Mat, Base, Attr),
284    Mesh = OrigMesh#e3d_mesh{fs=Faces},
285    MeshType = proplists:get_value(mesh_type, Attr),
286    export_mesh(F, MeshType, Mesh, Attr),
287    export_all(F, T, OrigMesh, Base, Mat, Attr);
288export_all(_F, [], _, _, _, _) -> ok.
289
290export_mesh(F, _, Mesh, Attr) ->
291    #e3d_mesh{fs=Fs,vs=Vs0,ns=Ns0,tx=Tx0,he=He} = e3d_mesh:renumber(Mesh),
292    {FsV,FsN,FsUV} = separate_faces(Fs),
293    Vs = list_to_tuple(Vs0),
294    Ns = list_to_tuple(Ns0),
295    Tx = list_to_tuple(Tx0),
296    export_mesh(F, Fs, FsV, FsN, FsUV, Vs, Ns, Tx, He, Attr).
297
298export_mesh(F, Fs, FsV, FsN, FsUV, Vs, Ns, Tx, He0, Attr) ->
299    MeshType = proplists:get_value(mesh_type, Attr),
300    ExpandFaces = proplists:get_bool(expand_faces, Attr),
301    case MeshType of
302    	subdiv ->
303	    io:put_chars(F, "SubdivisionMesh \"catmull-clark\"\n");
304    	poly ->
305	    io:put_chars(F, "PointsPolygons\n")
306    end,
307
308    io:put_chars(F, "[ "),
309    foreach(fun(#e3d_face{vs=FaceVs}) ->
310		    io:format(F, " ~p", [length(FaceVs)])
311	    end, Fs),
312    io:put_chars(F, "]\n"),
313
314    io:put_chars(F, "[ "),
315    FsVI = case ExpandFaces of
316	       true ->
317		   NumVs0 = [length(FaceVs) || #e3d_face{vs=FaceVs} <- Fs],
318		   NumVs = lists:sum(NumVs0),
319		   seq(0, NumVs-1);
320	       false -> FsV
321	   end,
322    foreach(fun(V) ->
323		    io:format(F, "~p ", [V])
324	    end, FsVI),
325    io:put_chars(F, "]\n"),
326
327    %% Attributes (i.e. creases)
328    case MeshType of
329	subdiv ->
330	    He = create_loops(He0),
331	    io:put_chars(F, "[\"interpolateboundary\""),
332	    foreach(fun(_) -> io:put_chars(F, " \"crease\"") end, He),
333	    io:put_chars(F, "] [0 0"),
334	    foreach(fun(H) -> io:format(F, " ~p 1", [length(H)]) end, He),
335	    io:put_chars(F, "]\n["),
336	    foreach(fun(H) ->
337			    foreach(fun(V) ->
338					    io:format(F, " ~p", [V])
339				    end, H)
340		    end, He),
341	    io:put_chars(F, "]\n["),
342	    foreach(fun(_) -> io:put_chars(F, " 2") end, He),
343	    io:put_chars(F, "]\n");
344	poly -> ok
345    end,
346
347    %% Vertex coords
348    io:put_chars(F, "\"P\"\n[\n"),
349    case ExpandFaces  of
350	true ->
351	    foreach(fun(V) ->
352			    {X,Y,Z} = element(V+1, Vs),
353			    io:format(F, "~p ~p ~p\n", [X,Y,Z])
354		    end, FsV);
355	false ->
356	    foreach(fun({X,Y,Z}) ->
357			    io:format(F, "~p ~p ~p\n", [X,Y,Z])
358		    end, tuple_to_list(Vs))
359    end,
360    io:put_chars(F, "]\n"),
361
362    %% Normals
363    case proplists:get_bool(export_normals, Attr) of
364	true ->
365	    case ExpandFaces of
366		true ->
367		    io:put_chars(F, "\"N\" \n[\n");
368		false ->
369		    io:put_chars(F, "\"facevarying float[3] N\" \n[\n")
370	    end,
371	    foreach(fun(N) ->
372			    {X,Y,Z} = element(N+1, Ns),
373			    io:format(F, "~p ~p ~p\n", [X,Y,Z])
374		    end, FsN),
375	    io:put_chars(F, "]\n");
376	false -> ok
377    end,
378
379    %% UV coordinates
380    case proplists:get_bool(export_uv, Attr) andalso FsUV =/= [] of
381	true ->
382	    case ExpandFaces of
383		true ->
384		    io:put_chars(F, "\"st\" \n[\n");
385		false ->
386		    io:put_chars(F, "\"facevarying float[2] st\" \n[\n")
387	    end,
388	    foreach(fun(UV) ->
389			    {S0,T0} = element(UV+1, Tx),
390			    %%wings measures textures from bottom left;
391			    %% Renderman from top left - must invert T0
392			    io:format(F, "~p ~p\n", [S0,1-T0])
393		    end, FsUV),
394	    io:put_chars(F, "]\n");
395	false -> ok
396    end.
397
398export_camera(F) ->
399    [{OX,OY,OZ},Dist,Az,El,{TrackX,TrackY},Fov] =
400	wpa:camera_info([aim,distance_to_aim,azimuth,elevation,tracking,fov]),
401    io:format(F, "Projection \"perspective\" \"fov\" ~p\n", [Fov]),
402    io:format(F, "Scale ~p ~p ~p\n", [1,1,-1]),
403    io:format(F, "Translate ~p ~p ~p\n", [TrackX,TrackY,-Dist]),
404    io:format(F, "Rotate ~p ~p ~p ~p\n", [El,1,0,0]),
405    io:format(F, "Rotate ~p ~p ~p ~p\n", [Az,0,1,0]),
406    io:format(F, "Translate ~p ~p ~p\n", [OX,OY,OZ]).
407
408export_materials_one(Mats, Base, Attr) ->
409    export_materials_one(Mats, Base, Attr, []).
410
411export_materials_one([{Name,Mat}|T], Base, Attr, Acc) ->
412    case proplists:get_value(diffuse_map, Mat, none) of
413	none ->
414	    export_materials_one(T,Base, Attr, Acc);
415	{W,H,DiffMap} ->
416	    case proplists:get_value(tmp_render, Attr) of
417		none ->
418		    MapFile = Base ++ "_" ++ atom_to_list(Name) ++
419			"_diffmap.tif",
420		    Image = #e3d_image{image=DiffMap,width=W,height=H},
421		    ok = e3d_image:save(Image, MapFile),
422		    export_materials_one(T,Base, Attr, Acc);
423		_ ->
424		    MapFile = "wpc_tif_temp_" ++ atom_to_list(Name) ++
425			os:getpid() ++ ".tif",
426		    Image = #e3d_image{image=DiffMap,width=W,height=H},
427		    ok = e3d_image:save(Image, MapFile),
428		    export_materials_one(T,Base, Attr, [MapFile|Acc])
429	    end
430    end;
431export_materials_one([], _Base, _Attr, Acc) -> Acc.
432
433write_shader(F, Name, [{Name,Mat}|_], Base, Attr) ->
434    export_material(F, Name, Mat, Base, Attr);
435write_shader(F, Name, [_|T], Base, Attr) ->
436    write_shader(F, Name, T, Base, Attr).
437
438export_material(F, Name, Mat, Base, Attr) ->
439    OpenGL = proplists:get_value(opengl, Mat),
440    Maps = proplists:get_value(maps, Mat),
441    {Dr,Dg,Db,Opacity} = proplists:get_value(diffuse, OpenGL),
442    io:format(F, "Color ~p ~p ~p\n", [Dr,Dg,Db]),
443    io:format(F, "Opacity ~p ~p ~p\n", [Opacity,Opacity,Opacity]),
444    {Ar,Ag,Ab,_} = proplists:get_value(ambient, OpenGL),
445    {Sr,Sg,Sb,_} = proplists:get_value(specular, OpenGL),
446    Shine = proplists:get_value(shininess, OpenGL),
447    Ka = (Ar+Ag+Ab)/3,
448    Kd = (Dr+Dg+Db)/3,
449    %%%Ks = (Sr+Sg+Sb)/3,
450    case proplists:get_value(diffuse, Maps, none) of
451	none ->
452	    io:format(F, "Surface \"plastic\"\n"
453		      " \"float Ka\" [~p]\n"
454		      " \"float Kd\" [~p]\n"
455		      " \"float Ks\" [~p]\n"
456		      " \"float roughness\" [~p]\n"
457		      " \"color specularcolor\" [~p ~p ~p]\n",
458		      [Ka,Kd,Shine,0.1,Sr,Sg,Sb]);
459	{_,_,_DiffMap} ->
460	    MapFile  = case proplists:get_value(tmp_render, Attr) of
461			   none -> Base ++ "_" ++ atom_to_list(Name) ++ "_diffmap.tif";
462			   _ -> "wpc_tif_temp_" ++ atom_to_list(Name) ++ os:getpid() ++ ".tif"
463		       end,
464	    io:format(F, "Surface \"paintedplastic\"\n"
465		      " \"float Ka\" [~p]\n"
466		      " \"float Kd\" [~p]\n"
467		      " \"float Ks\" [~p]\n"
468		      " \"float roughness\" [~p]\n"
469		      " \"color specularcolor\" [~p ~p ~p]\n"
470		      " \"string texturename\" [~p]\n",
471		      [Ka,Kd,Shine,0.1,Sr,Sg,Sb,MapFile])
472    end.
473
474export_lights(F, Attr) ->
475    declare(F, "from", "point"),
476    declare(F, "to", "point"),
477    declare(F, "lightcolor", "color"),
478    Ls = proplists:get_value(lights, Attr),
479    foldl(fun(L, I) -> export_light(F, I, L), I+1 end, 0, Ls).
480
481export_light(F, I, {_,Ps}) ->
482    OpenGL = proplists:get_value(opengl, Ps, []),
483    Type = proplists:get_value(type, OpenGL, point),
484    export_light(F, Type, I, OpenGL).
485
486export_light(F, point, I, OpenGL) ->
487    io:format(F, "LightSource ~p ~p", ["pointlight",I]),
488    export_light_common(F, OpenGL),
489    io:nl(F);
490export_light(F, infinite, I, OpenGL) ->
491    To = proplists:get_value(aim_point, OpenGL, {0,0,1}),
492    io:format(F, "LightSource ~p ~p", ["distantlight",I]),
493    export_light_common(F, OpenGL),
494    show_point(F, "to", To),
495    io:nl(F);
496export_light(F, spot, I, OpenGL) ->
497    To = proplists:get_value(aim_point, OpenGL, {0,0,1}),
498    Angle0 = proplists:get_value(cone_angle, OpenGL, 30),
499    Angle = Angle0*math:pi()/180,
500    io:format(F, "LightSource ~p ~p", ["spotlight",I]),
501    export_light_common(F, OpenGL),
502    show_point(F, "to", To),
503    io:format(F, " ~p ~p ", ["coneangle",Angle]),
504    io:nl(F);
505export_light(F, ambient, I, OpenGL) ->
506    io:format(F, "LightSource ~p ~p", ["ambientlight",I]),
507    {R,G,B,_} = proplists:get_value(ambient, OpenGL, {0.0,0.0,0.0,1.0}),
508    io:format(F, " ~p ~p ", ["intensity",1.0]),
509    show_point(F, "lightcolor", {R,G,B}),
510    io:nl(F);
511export_light(_, Type, _, _) ->
512    io:format("Ignoring unknown light type: ~p\n", [Type]).
513
514export_light_common(F, OpenGL) ->
515    From = proplists:get_value(position, OpenGL, {0,0,0}),
516    {R,G,B,_} = proplists:get_value(diffuse, OpenGL, {1,1,1,1}),
517    io:format(F, " ~p ~p ", ["intensity",1.0]),
518    show_point(F, "lightcolor", {R,G,B}),
519    show_point(F, "from", From).
520
521show_point(F, Label, {X,Y,Z}) ->
522    io:format(F, "~p [~p ~p ~p] ", [Label,X,Y,Z]).
523
524declare(F, N, V) ->
525    io:format(F, "Declare ~p ~p\n", [N,V]).
526
527%%%
528%%% Utilities.
529%%%
530
531separate_faces(L) -> separate_faces(L, [], [], []).
532
533separate_faces([#e3d_face{vs=Vs,tx=Tx,ns=Ns}|T], VAcc, NAcc, UVAcc) ->
534    separate_faces(T, [Vs|VAcc], [Ns|NAcc], [Tx|UVAcc]);
535separate_faces([], VAcc, NAcc, UVAcc) ->
536    {append(reverse(VAcc)),append(reverse(NAcc)),append(reverse(UVAcc))}.
537
538create_loops([]) -> [];
539create_loops(L) -> create_loops(L, []).
540
541create_loops(Vl, Acc) ->
542    if
543	length(Vl) >0 ->
544	    Vh = hd(Vl),
545	    Vt = tl(Vl),
546	    {V0,V1} = Vh,
547	    {Acc0,Nl} = create_loops0(V1,V0,Vt, [V0,V1]),
548	    Acc1 = lists:append(Acc, [Acc0]),
549	    create_loops(Nl,Acc1);
550	length(Vl) =< 0 ->
551	    Acc
552    end.
553
554create_loops0( V,V0,Vl,Acc) ->
555    {Nxt,Nl} = get_next(V, Vl, []),
556    case Nxt of
557	V0 ->
558	    Acc0 = lists:append(Acc,[V0]),
559	    {Acc0,Nl};
560	Nxt when Nxt >= 0 ->
561	    Acc0 = lists:append(Acc,[Nxt]),
562	    create_loops0(Nxt,V0,Nl,Acc0);
563	Nxt when Nxt < 0 ->
564	    {Acc,Nl}
565    end.
566
567%% Find first edge with shared vertex,
568%% return other vertex in that edge, remove edge from list.
569
570get_next(X, [{X,Z}|T], Acc) ->
571    Nl = lists:append(Acc,T),
572    {Z,Nl};
573get_next(X,[{Z,X}|T],Acc)->
574    Nl = lists:append(Acc,T),
575    {Z,Nl};
576get_next(X, [H|T],Acc) ->
577    Nl = lists:append(Acc,[H]),
578    get_next(X, T, Nl);
579get_next(_, [], Acc) -> {-1,Acc}.
580