Cleanup Newell's algorithm implementation
[vrm.git] / vrm.py
1 #!BPY
2 """
3 Name: 'VRM'
4 Blender: 242
5 Group: 'Render'
6 Tooltip: 'Vector Rendering Method script'
7 """
8
9 __author__ = "Antonio Ospite"
10 __url__ = ["http://projects.blender.org/projects/vrm"]
11 __version__ = "0.3.beta"
12
13 __bpydoc__ = """\
14     Render the scene and save the result in vector format.
15 """
16
17 # ---------------------------------------------------------------------
18 #    Copyright (c) 2006 Antonio Ospite
19 #
20 #    This program is free software; you can redistribute it and/or modify
21 #    it under the terms of the GNU General Public License as published by
22 #    the Free Software Foundation; either version 2 of the License, or
23 #    (at your option) any later version.
24 #
25 #    This program is distributed in the hope that it will be useful,
26 #    but WITHOUT ANY WARRANTY; without even the implied warranty of
27 #    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
28 #    GNU General Public License for more details.
29 #
30 #    You should have received a copy of the GNU General Public License
31 #    along with this program; if not, write to the Free Software
32 #    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
33 #
34 # ---------------------------------------------------------------------
35 #
36 # Additional credits:
37 #   Thanks to Emilio Aguirre for S2flender from which I took inspirations :)
38 #   Thanks to Nikola Radovanovic, the author of the original VRM script,
39 #       the code you read here has been rewritten _almost_ entirely
40 #       from scratch but Nikola gave me the idea, so I thank him publicly.
41 #
42 # ---------------------------------------------------------------------
43
44 # Things TODO for a next release:
45 #   - FIX the issue with negative scales in object tranformations!
46 #   - Use a better depth sorting algorithm
47 #   - Implement clipping of primitives and do handle object intersections.
48 #     (for now only clipping away whole objects is supported).
49 #   - Review how selections are made (this script uses selection states of
50 #     primitives to represent visibility infos)
51 #   - Use a data structure other than Mesh to represent the 2D image? 
52 #     Think to a way to merge (adjacent) polygons that have the same color.
53 #     Or a way to use paths for silhouettes and contours.
54 #   - Consider SMIL for animation handling instead of ECMA Script? (Firefox do
55 #     not support SMIL for animations)
56 #   - Switch to the Mesh structure, should be considerably faster
57 #     (partially done, but with Mesh we cannot sort faces, yet)
58 #   - Implement Edge Styles (silhouettes, contours, etc.) (partially done).
59 #   - Implement Shading Styles? (partially done, to make more flexible).
60 #   - Add Vector Writers other than SVG.
61 #   - Check memory use!!
62 #   - Support Indexed palettes!! (Useful for ILDA FILES, for example,
63 #     see http://www.linux-laser.org/download/autotrace/ilda-output.patch)
64 #
65 # ---------------------------------------------------------------------
66 #
67 # Changelog:
68 #
69 #   vrm-0.3.py  - ...
70 #     * First release after code restucturing.
71 #       Now the script offers a useful set of functionalities
72 #       and it can render animations, too.
73 #     * Optimization in Renderer.doEdgeStyle(), build a topology cache
74 #       so to speed up the lookup of adjacent faces of an edge.
75 #       Thanks ideasman42.
76 #     * The SVG output is now SVG 1.0 valid.
77 #       Checked with: http://jiggles.w3.org/svgvalidator/ValidatorURI.html
78 #     * Progress indicator during HSR.
79 #
80 # ---------------------------------------------------------------------
81
82 import Blender
83 from Blender import Scene, Object, Mesh, NMesh, Material, Lamp, Camera, Window
84 from Blender.Mathutils import *
85 from math import *
86 import sys, time
87
88 # Constants
89 EPS = 10e-5
90
91
92 # Some global settings
93
94 class config:
95     polygons = dict()
96     polygons['SHOW'] = True
97     polygons['SHADING'] = 'TOON'
98     #polygons['HSR'] = 'PAINTER' # 'PAINTER' or 'NEWELL'
99     polygons['HSR'] = 'NEWELL'
100     # Hidden to the user for now
101     polygons['EXPANSION_TRICK'] = True
102
103     polygons['TOON_LEVELS'] = 2
104
105     edges = dict()
106     edges['SHOW'] = False
107     edges['SHOW_HIDDEN'] = False
108     edges['STYLE'] = 'MESH' # or SILHOUETTE
109     edges['WIDTH'] = 2
110     edges['COLOR'] = [0, 0, 0]
111
112     output = dict()
113     output['FORMAT'] = 'SVG'
114     output['ANIMATION'] = False
115     output['JOIN_OBJECTS'] = True
116
117
118
119 # Utility functions
120 def sign(x):
121
122     if x < 0:
123         return -1
124     elif x > 0:
125         return 1
126     #else:
127     #    return 0
128
129
130 # ---------------------------------------------------------------------
131 #
132 ## Mesh Utility class
133 #
134 # ---------------------------------------------------------------------
135 class MeshUtils:
136
137     def buildEdgeFaceUsersCache(me):
138         ''' 
139         Takes a mesh and returns a list aligned with the meshes edges.
140         Each item is a list of the faces that use the edge
141         would be the equiv for having ed.face_users as a property
142
143         Taken from .blender/scripts/bpymodules/BPyMesh.py,
144         thanks to ideasman_42.
145         '''
146
147         def sorted_edge_indicies(ed):
148             i1= ed.v1.index
149             i2= ed.v2.index
150             if i1>i2:
151                 i1,i2= i2,i1
152             return i1, i2
153
154         
155         face_edges_dict= dict([(sorted_edge_indicies(ed), (ed.index, [])) for ed in me.edges])
156         for f in me.faces:
157             fvi= [v.index for v in f.v]# face vert idx's
158             for i in xrange(len(f)):
159                 i1= fvi[i]
160                 i2= fvi[i-1]
161                 
162                 if i1>i2:
163                     i1,i2= i2,i1
164                 
165                 face_edges_dict[i1,i2][1].append(f)
166         
167         face_edges= [None] * len(me.edges)
168         for ed_index, ed_faces in face_edges_dict.itervalues():
169             face_edges[ed_index]= ed_faces
170         
171         return face_edges
172
173     def isMeshEdge(adjacent_faces):
174         """Mesh edge rule.
175
176         A mesh edge is visible if _at_least_one_ of its adjacent faces is selected.
177         Note: if the edge has no adjacent faces we want to show it as well,
178         useful for "edge only" portion of objects.
179         """
180
181         if len(adjacent_faces) == 0:
182             return True
183
184         selected_faces = [f for f in adjacent_faces if f.sel]
185
186         if len(selected_faces) != 0:
187             return True
188         else:
189             return False
190
191     def isSilhouetteEdge(adjacent_faces):
192         """Silhuette selection rule.
193
194         An edge is a silhuette edge if it is shared by two faces with
195         different selection status or if it is a boundary edge of a selected
196         face.
197         """
198
199         if ((len(adjacent_faces) == 1 and adjacent_faces[0].sel == 1) or
200             (len(adjacent_faces) == 2 and
201                 adjacent_faces[0].sel != adjacent_faces[1].sel)
202             ):
203             return True
204         else:
205             return False
206
207     buildEdgeFaceUsersCache = staticmethod(buildEdgeFaceUsersCache)
208     isMeshEdge = staticmethod(isMeshEdge)
209     isSilhouetteEdge = staticmethod(isSilhouetteEdge)
210
211
212 # ---------------------------------------------------------------------
213 #
214 ## Shading Utility class
215 #
216 # ---------------------------------------------------------------------
217 class ShadingUtils:
218
219     shademap = None
220
221     def toonShadingMapSetup():
222         levels = config.polygons['TOON_LEVELS']
223
224         texels = 2*levels - 1
225         tmp_shademap = [0.0] + [(i)/float(texels-1) for i in xrange(1, texels-1) ] + [1.0]
226
227         return tmp_shademap
228
229     def toonShading(u):
230
231         shademap = ShadingUtils.shademap
232
233         if not shademap:
234             shademap = ShadingUtils.toonShadingMapSetup()
235
236         v = 1.0
237         for i in xrange(0, len(shademap)-1):
238             pivot = (shademap[i]+shademap[i+1])/2.0
239             j = int(u>pivot)
240
241             v = shademap[i+j]
242
243             if v < shademap[i+1]:
244                 return v
245
246         return v
247
248     toonShadingMapSetup = staticmethod(toonShadingMapSetup)
249     toonShading = staticmethod(toonShading)
250
251
252 # ---------------------------------------------------------------------
253 #
254 ## Projections classes
255 #
256 # ---------------------------------------------------------------------
257
258 class Projector:
259     """Calculate the projection of an object given the camera.
260     
261     A projector is useful to so some per-object transformation to obtain the
262     projection of an object given the camera.
263     
264     The main method is #doProjection# see the method description for the
265     parameter list.
266     """
267
268     def __init__(self, cameraObj, canvasRatio):
269         """Calculate the projection matrix.
270
271         The projection matrix depends, in this case, on the camera settings.
272         TAKE CARE: This projector expects vertices in World Coordinates!
273         """
274
275         camera = cameraObj.getData()
276
277         aspect = float(canvasRatio[0])/float(canvasRatio[1])
278         near = camera.clipStart
279         far = camera.clipEnd
280
281         scale = float(camera.scale)
282
283         fovy = atan(0.5/aspect/(camera.lens/32))
284         fovy = fovy * 360.0/pi
285         
286         # What projection do we want?
287         if camera.type == 0:
288             mP = self._calcPerspectiveMatrix(fovy, aspect, near, far) 
289         elif camera.type == 1:
290             mP = self._calcOrthoMatrix(fovy, aspect, near, far, scale) 
291         
292         # View transformation
293         cam = Matrix(cameraObj.getInverseMatrix())
294         cam.transpose() 
295         
296         mP = mP * cam
297
298         self.projectionMatrix = mP
299
300     ##
301     # Public methods
302     #
303
304     def doProjection(self, v):
305         """Project the point on the view plane.
306
307         Given a vertex calculate the projection using the current projection
308         matrix.
309         """
310         
311         # Note that we have to work on the vertex using homogeneous coordinates
312         # From blender 2.42+ we don't need to resize the vector to be 4d
313         # when applying a 4x4 matrix, but we do that anyway since we need the
314         # 4th coordinate later
315         p = self.projectionMatrix * Vector(v).resize4D()
316         
317         # Perspective division
318         if p[3] != 0:
319             p[0] = p[0]/p[3]
320             p[1] = p[1]/p[3]
321             p[2] = p[2]/p[3]
322
323         # restore the size
324         p[3] = 1.0
325         p.resize3D()
326
327         return p
328
329
330     ##
331     # Private methods
332     #
333     
334     def _calcPerspectiveMatrix(self, fovy, aspect, near, far):
335         """Return a perspective projection matrix.
336         """
337         
338         top = near * tan(fovy * pi / 360.0)
339         bottom = -top
340         left = bottom*aspect
341         right= top*aspect
342         x = (2.0 * near) / (right-left)
343         y = (2.0 * near) / (top-bottom)
344         a = (right+left) / (right-left)
345         b = (top+bottom) / (top - bottom)
346         c = - ((far+near) / (far-near))
347         d = - ((2*far*near)/(far-near))
348         
349         m = Matrix(
350                 [x,   0.0,    a,    0.0],
351                 [0.0,   y,    b,    0.0],
352                 [0.0, 0.0,    c,      d],
353                 [0.0, 0.0, -1.0,    0.0])
354
355         return m
356
357     def _calcOrthoMatrix(self, fovy, aspect , near, far, scale):
358         """Return an orthogonal projection matrix.
359         """
360         
361         # The 11 in the formula was found emiprically
362         top = near * tan(fovy * pi / 360.0) * (scale * 11)
363         bottom = -top 
364         left = bottom * aspect
365         right= top * aspect
366         rl = right-left
367         tb = top-bottom
368         fn = near-far 
369         tx = -((right+left)/rl)
370         ty = -((top+bottom)/tb)
371         tz = ((far+near)/fn)
372
373         m = Matrix(
374                 [2.0/rl, 0.0,    0.0,     tx],
375                 [0.0,    2.0/tb, 0.0,     ty],
376                 [0.0,    0.0,    2.0/fn,  tz],
377                 [0.0,    0.0,    0.0,    1.0])
378         
379         return m
380
381
382 # ---------------------------------------------------------------------
383 #
384 ## Progress Indicator
385 #
386 # ---------------------------------------------------------------------
387
388 class Progress:
389     """A model for a progress indicator.
390     
391     Do the progress calculation calculation and
392     the view independent stuff of a progress indicator.
393     """
394     def __init__(self, steps=0):
395         self.name = ""
396         self.steps = steps
397         self.completed = 0
398         self.progress = 0
399
400     def setSteps(self, steps):
401         """Set the number of steps of the activity wich we want to track.
402         """
403         self.steps = steps
404
405     def getSteps(self):
406         return self.steps
407
408     def setName(self, name):
409         """Set the name of the activity wich we want to track.
410         """
411         self.name = name
412
413     def getName(self):
414         return self.name
415
416     def getProgress(self):
417         return self.progress
418
419     def reset(self):
420         self.completed = 0
421         self.progress = 0
422
423     def update(self):
424         """Update the model, call this method when one step is completed.
425         """
426         if self.progress == 100:
427             return False
428
429         self.completed += 1
430         self.progress = ( float(self.completed) / float(self.steps) ) * 100
431         self.progress = int(self.progress)
432
433         return True
434
435
436 class ProgressIndicator:
437     """An abstraction of a View for the Progress Model
438     """
439     def __init__(self):
440
441         # Use a refresh rate so we do not show the progress at
442         # every update, but every 'self.refresh_rate' times.
443         self.refresh_rate = 10
444         self.shows_counter = 0
445
446         self.quiet = False
447
448         self.progressModel = None
449
450     def setQuiet(self, value):
451         self.quiet = value
452
453     def setActivity(self, name, steps):
454         """Initialize the Model.
455
456         In a future version (with subactivities-progress support) this method
457         could only set the current activity.
458         """
459         self.progressModel = Progress()
460         self.progressModel.setName(name)
461         self.progressModel.setSteps(steps)
462
463     def getActivity(self):
464         return self.progressModel
465
466     def update(self):
467         """Update the model and show the actual progress.
468         """
469         assert(self.progressModel)
470
471         if self.progressModel.update():
472             if self.quiet:
473                 return
474
475             self.show(self.progressModel.getProgress(),
476                     self.progressModel.getName())
477
478         # We return always True here so we can call the update() method also
479         # from lambda funcs (putting the call in logical AND with other ops)
480         return True
481
482     def show(self, progress, name=""):
483         self.shows_counter = (self.shows_counter + 1) % self.refresh_rate
484         if self.shows_counter != 0:
485             return
486
487         if progress == 100:
488             self.shows_counter = -1
489
490
491 class ConsoleProgressIndicator(ProgressIndicator):
492     """Show a progress bar on stderr, a la wget.
493     """
494     def __init__(self):
495         ProgressIndicator.__init__(self)
496
497         self.swirl_chars = ["-", "\\", "|", "/"]
498         self.swirl_count = -1
499
500     def show(self, progress, name):
501         ProgressIndicator.show(self, progress, name)
502         
503         bar_length = 70
504         bar_progress = int( (progress/100.0) * bar_length )
505         bar = ("=" * bar_progress).ljust(bar_length)
506
507         self.swirl_count = (self.swirl_count+1)%len(self.swirl_chars)
508         swirl_char = self.swirl_chars[self.swirl_count]
509
510         progress_bar = "%s |%s| %c %3d%%" % (name, bar, swirl_char, progress)
511
512         sys.stderr.write(progress_bar+"\r")
513         if progress == 100:
514             sys.stderr.write("\n")
515
516
517 class GraphicalProgressIndicator(ProgressIndicator):
518     """Interface to the Blender.Window.DrawProgressBar() method.
519     """
520     def __init__(self):
521         ProgressIndicator.__init__(self)
522
523         #self.swirl_chars = ["-", "\\", "|", "/"]
524         # We have to use letters with the same width, for now!
525         # Blender progress bar considers the font widths when
526         # calculating the progress bar width.
527         self.swirl_chars = ["\\", "/"]
528         self.swirl_count = -1
529
530     def show(self, progress, name):
531         ProgressIndicator.show(self, progress)
532
533         self.swirl_count = (self.swirl_count+1)%len(self.swirl_chars)
534         swirl_char = self.swirl_chars[self.swirl_count]
535
536         progress_text = "%s - %c %3d%%" % (name, swirl_char, progress)
537
538         # Finally draw  the Progress Bar
539         Window.WaitCursor(1) # Maybe we can move that call in the constructor?
540         Window.DrawProgressBar(progress/100.0, progress_text)
541
542         if progress == 100:
543             Window.DrawProgressBar(1, progress_text)
544             Window.WaitCursor(0)
545
546
547
548 # ---------------------------------------------------------------------
549 #
550 ## 2D Object representation class
551 #
552 # ---------------------------------------------------------------------
553
554 # TODO: a class to represent the needed properties of a 2D vector image
555 # For now just using a [N]Mesh structure.
556
557
558 # ---------------------------------------------------------------------
559 #
560 ## Vector Drawing Classes
561 #
562 # ---------------------------------------------------------------------
563
564 ## A generic Writer
565
566 class VectorWriter:
567     """
568     A class for printing output in a vectorial format.
569
570     Given a 2D representation of the 3D scene the class is responsible to
571     write it is a vector format.
572
573     Every subclasses of VectorWriter must have at last the following public
574     methods:
575         - open(self)
576         - close(self)
577         - printCanvas(self, scene,
578             doPrintPolygons=True, doPrintEdges=False, showHiddenEdges=False):
579     """
580     
581     def __init__(self, fileName):
582         """Set the output file name and other properties"""
583
584         self.outputFileName = fileName
585         self.file = None
586         
587         context = Scene.GetCurrent().getRenderingContext()
588         self.canvasSize = ( context.imageSizeX(), context.imageSizeY() )
589
590         self.startFrame = 1
591         self.endFrame = 1
592         self.animation = False
593
594
595     ##
596     # Public Methods
597     #
598     
599     def open(self, startFrame=1, endFrame=1):
600         if startFrame != endFrame:
601             self.startFrame = startFrame
602             self.endFrame = endFrame
603             self.animation = True
604
605         self.file = open(self.outputFileName, "w")
606         print "Outputting to: ", self.outputFileName
607
608         return
609
610     def close(self):
611         self.file.close()
612         return
613
614     def printCanvas(self, scene, doPrintPolygons=True, doPrintEdges=False,
615             showHiddenEdges=False):
616         """This is the interface for the needed printing routine.
617         """
618         return
619         
620
621 ## SVG Writer
622
623 class SVGVectorWriter(VectorWriter):
624     """A concrete class for writing SVG output.
625     """
626
627     def __init__(self, fileName):
628         """Simply call the parent Contructor.
629         """
630         VectorWriter.__init__(self, fileName)
631
632
633     ##
634     # Public Methods
635     #
636
637     def open(self, startFrame=1, endFrame=1):
638         """Do some initialization operations.
639         """
640         VectorWriter.open(self, startFrame, endFrame)
641         self._printHeader()
642
643     def close(self):
644         """Do some finalization operation.
645         """
646         self._printFooter()
647
648         # remember to call the close method of the parent
649         VectorWriter.close(self)
650
651         
652     def printCanvas(self, scene, doPrintPolygons=True, doPrintEdges=False,
653             showHiddenEdges=False):
654         """Convert the scene representation to SVG.
655         """
656
657         Objects = scene.getChildren()
658
659         context = scene.getRenderingContext()
660         framenumber = context.currentFrame()
661
662         if self.animation:
663             framestyle = "display:none"
664         else:
665             framestyle = "display:block"
666         
667         # Assign an id to this group so we can set properties on it using DOM
668         self.file.write("<g id=\"frame%d\" style=\"%s\">\n" %
669                 (framenumber, framestyle) )
670
671
672         for obj in Objects:
673
674             if(obj.getType() != 'Mesh'):
675                 continue
676
677             self.file.write("<g id=\"%s\">\n" % obj.getName())
678
679             mesh = obj.getData(mesh=1)
680
681             if doPrintPolygons:
682                 self._printPolygons(mesh)
683
684             if doPrintEdges:
685                 self._printEdges(mesh, showHiddenEdges)
686             
687             self.file.write("</g>\n")
688
689         self.file.write("</g>\n")
690
691     
692     ##  
693     # Private Methods
694     #
695     
696     def _calcCanvasCoord(self, v):
697         """Convert vertex in scene coordinates to canvas coordinates.
698         """
699
700         pt = Vector([0, 0, 0])
701         
702         mW = float(self.canvasSize[0])/2.0
703         mH = float(self.canvasSize[1])/2.0
704
705         # rescale to canvas size
706         pt[0] = v.co[0]*mW + mW
707         pt[1] = v.co[1]*mH + mH
708         pt[2] = v.co[2]
709          
710         # For now we want (0,0) in the top-left corner of the canvas.
711         # Mirror and translate along y
712         pt[1] *= -1
713         pt[1] += self.canvasSize[1]
714         
715         return pt
716
717     def _printHeader(self):
718         """Print SVG header."""
719
720         self.file.write("<?xml version=\"1.0\"?>\n")
721         self.file.write("<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.0//EN\"\n")
722         self.file.write("\t\"http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd\">\n")
723         self.file.write("<svg version=\"1.0\"\n")
724         self.file.write("\txmlns=\"http://www.w3.org/2000/svg\"\n")
725         self.file.write("\twidth=\"%d\" height=\"%d\">\n\n" %
726                 self.canvasSize)
727
728         if self.animation:
729
730             self.file.write("""\n<script type="text/javascript"><![CDATA[
731             globalStartFrame=%d;
732             globalEndFrame=%d;
733
734             /* FIXME: Use 1000 as interval as lower values gives problems */
735             timerID = setInterval("NextFrame()", 1000);
736             globalFrameCounter=%d;
737
738             function NextFrame()
739             {
740               currentElement  = document.getElementById('frame'+globalFrameCounter)
741               previousElement = document.getElementById('frame'+(globalFrameCounter-1))
742
743               if (!currentElement)
744               {
745                 return;
746               }
747
748               if (globalFrameCounter > globalEndFrame)
749               {
750                 clearInterval(timerID)
751               }
752               else
753               {
754                 if(previousElement)
755                 {
756                     previousElement.style.display="none";
757                 }
758                 currentElement.style.display="block";
759                 globalFrameCounter++;
760               }
761             }
762             \n]]></script>\n
763             \n""" % (self.startFrame, self.endFrame, self.startFrame) )
764                 
765     def _printFooter(self):
766         """Print the SVG footer."""
767
768         self.file.write("\n</svg>\n")
769
770     def _printPolygons(self, mesh): 
771         """Print the selected (visible) polygons.
772         """
773
774         if len(mesh.faces) == 0:
775             return
776
777         self.file.write("<g>\n")
778
779         for face in mesh.faces:
780             if not face.sel:
781                continue
782
783             self.file.write("<path d=\"")
784
785             p = self._calcCanvasCoord(face.verts[0])
786             self.file.write("M %g,%g L " % (p[0], p[1]))
787
788             for v in face.verts[1:]:
789                 p = self._calcCanvasCoord(v)
790                 self.file.write("%g,%g " % (p[0], p[1]))
791             
792             # get rid of the last blank space, just cosmetics here.
793             self.file.seek(-1, 1) 
794             self.file.write(" z\"\n")
795             
796             # take as face color the first vertex color
797             if face.col:
798                 fcol = face.col[0]
799                 color = [fcol.r, fcol.g, fcol.b, fcol.a]
800             else:
801                 color = [255, 255, 255, 255]
802
803             # Convert the color to the #RRGGBB form
804             str_col = "#%02X%02X%02X" % (color[0], color[1], color[2])
805
806             # Handle transparent polygons
807             opacity_string = ""
808             if color[3] != 255:
809                 opacity = float(color[3])/255.0
810                 opacity_string = " fill-opacity: %g; stroke-opacity: %g; opacity: 1;" % (opacity, opacity)
811                 #opacity_string = "opacity: %g;" % (opacity)
812
813             self.file.write("\tstyle=\"fill:" + str_col + ";")
814             self.file.write(opacity_string)
815
816             # use the stroke property to alleviate the "adjacent edges" problem,
817             # we simulate polygon expansion using borders,
818             # see http://www.antigrain.com/svg/index.html for more info
819             stroke_width = 1.0
820
821             # EXPANSION TRICK is not that useful where there is transparency
822             if config.polygons['EXPANSION_TRICK'] and color[3] == 255:
823                 # str_col = "#000000" # For debug
824                 self.file.write(" stroke:%s;\n" % str_col)
825                 self.file.write(" stroke-width:" + str(stroke_width) + ";\n")
826                 self.file.write(" stroke-linecap:round;stroke-linejoin:round")
827
828             self.file.write("\"/>\n")
829
830         self.file.write("</g>\n")
831
832     def _printEdges(self, mesh, showHiddenEdges=False):
833         """Print the wireframe using mesh edges.
834         """
835
836         stroke_width = config.edges['WIDTH']
837         stroke_col = config.edges['COLOR']
838         
839         self.file.write("<g>\n")
840
841         for e in mesh.edges:
842             
843             hidden_stroke_style = ""
844             
845             if e.sel == 0:
846                 if showHiddenEdges == False:
847                     continue
848                 else:
849                     hidden_stroke_style = ";\n stroke-dasharray:3, 3"
850
851             p1 = self._calcCanvasCoord(e.v1)
852             p2 = self._calcCanvasCoord(e.v2)
853             
854             self.file.write("<line x1=\"%g\" y1=\"%g\" x2=\"%g\" y2=\"%g\"\n"
855                     % ( p1[0], p1[1], p2[0], p2[1] ) )
856             self.file.write(" style=\"stroke:rgb("+str(stroke_col[0])+","+str(stroke_col[1])+","+str(stroke_col[2])+");")
857             self.file.write(" stroke-width:"+str(stroke_width)+";\n")
858             self.file.write(" stroke-linecap:round;stroke-linejoin:round")
859             self.file.write(hidden_stroke_style)
860             self.file.write("\"/>\n")
861
862         self.file.write("</g>\n")
863
864
865 # ---------------------------------------------------------------------
866 #
867 ## Rendering Classes
868 #
869 # ---------------------------------------------------------------------
870
871 # A dictionary to collect different shading style methods
872 shadingStyles = dict()
873 shadingStyles['FLAT'] = None
874 shadingStyles['TOON'] = None
875
876 # A dictionary to collect different edge style methods
877 edgeStyles = dict()
878 edgeStyles['MESH'] = MeshUtils.isMeshEdge
879 edgeStyles['SILHOUETTE'] = MeshUtils.isSilhouetteEdge
880
881 # A dictionary to collect the supported output formats
882 outputWriters = dict()
883 outputWriters['SVG'] = SVGVectorWriter
884
885
886 class Renderer:
887     """Render a scene viewed from the active camera.
888     
889     This class is responsible of the rendering process, transformation and
890     projection of the objects in the scene are invoked by the renderer.
891
892     The rendering is done using the active camera for the current scene.
893     """
894
895     def __init__(self):
896         """Make the rendering process only for the current scene by default.
897
898         We will work on a copy of the scene, to be sure that the current scene do
899         not get modified in any way.
900         """
901
902         # Render the current Scene, this should be a READ-ONLY property
903         self._SCENE = Scene.GetCurrent()
904         
905         # Use the aspect ratio of the scene rendering context
906         context = self._SCENE.getRenderingContext()
907
908         aspect_ratio = float(context.imageSizeX())/float(context.imageSizeY())
909         self.canvasRatio = (float(context.aspectRatioX())*aspect_ratio,
910                             float(context.aspectRatioY())
911                             )
912
913         # Render from the currently active camera 
914         self.cameraObj = self._SCENE.getCurrentCamera()
915
916         # Get a projector for this camera.
917         # NOTE: the projector wants object in world coordinates,
918         # so we should remember to apply modelview transformations
919         # _before_ we do projection transformations.
920         self.proj = Projector(self.cameraObj, self.canvasRatio)
921
922         # Get the list of lighting sources
923         obj_lst = self._SCENE.getChildren()
924         self.lights = [ o for o in obj_lst if o.getType() == 'Lamp']
925
926         # When there are no lights we use a default lighting source
927         # that have the same position of the camera
928         if len(self.lights) == 0:
929             l = Lamp.New('Lamp')
930             lobj = Object.New('Lamp')
931             lobj.loc = self.cameraObj.loc
932             lobj.link(l) 
933             self.lights.append(lobj)
934
935
936     ##
937     # Public Methods
938     #
939
940     def doRendering(self, outputWriter, animation=False):
941         """Render picture or animation and write it out.
942         
943         The parameters are:
944             - a Vector writer object that will be used to output the result.
945             - a flag to tell if we want to render an animation or only the
946               current frame.
947         """
948         
949         context = self._SCENE.getRenderingContext()
950         origCurrentFrame = context.currentFrame()
951
952         # Handle the animation case
953         if not animation:
954             startFrame = origCurrentFrame
955             endFrame = startFrame
956             outputWriter.open()
957         else:
958             startFrame = context.startFrame()
959             endFrame = context.endFrame()
960             outputWriter.open(startFrame, endFrame)
961         
962         # Do the rendering process frame by frame
963         print "Start Rendering of %d frames" % (endFrame-startFrame)
964         for f in xrange(startFrame, endFrame+1):
965             print "\n\nFrame: %d" % f
966             context.currentFrame(f)
967
968             # Use some temporary workspace, a full copy of the scene
969             inputScene = self._SCENE.copy(2)
970             # And Set our camera accordingly
971             self.cameraObj = inputScene.getCurrentCamera()
972
973             try:
974                 renderedScene = self.doRenderScene(inputScene)
975             except :
976                 print "There was an error! Aborting."
977                 import traceback
978                 print traceback.print_exc()
979
980                 self._SCENE.makeCurrent()
981                 Scene.unlink(inputScene)
982                 del inputScene
983                 return
984
985             outputWriter.printCanvas(renderedScene,
986                     doPrintPolygons = config.polygons['SHOW'],
987                     doPrintEdges    = config.edges['SHOW'],
988                     showHiddenEdges = config.edges['SHOW_HIDDEN'])
989             
990             # delete the rendered scene
991             self._SCENE.makeCurrent()
992             Scene.unlink(renderedScene)
993             del renderedScene
994
995         outputWriter.close()
996         print "Done!"
997         context.currentFrame(origCurrentFrame)
998
999
1000     def doRenderScene(self, workScene):
1001         """Control the rendering process.
1002         
1003         Here we control the entire rendering process invoking the operation
1004         needed to transform and project the 3D scene in two dimensions.
1005         """
1006         
1007         # global processing of the scene
1008
1009         self._doSceneClipping(workScene)
1010
1011         self._doConvertGeometricObjsToMesh(workScene)
1012
1013         if config.output['JOIN_OBJECTS']:
1014             self._joinMeshObjectsInScene(workScene)
1015
1016         self._doSceneDepthSorting(workScene)
1017         
1018         # Per object activities
1019
1020         Objects = workScene.getChildren()
1021         print "Total Objects: %d" % len(Objects)
1022         for i,obj in enumerate(Objects):
1023             print "\n\n-------"
1024             print "Rendering Object: %d" % i
1025
1026             if obj.getType() != 'Mesh':
1027                 print "Only Mesh supported! - Skipping type:", obj.getType()
1028                 continue
1029
1030             print "Rendering: ", obj.getName()
1031
1032             mesh = obj.getData(mesh=1)
1033
1034             # Triangolarize the mesh??
1035             for f in mesh.faces: f.sel = 1
1036             mesh.quadToTriangle()
1037
1038             self._doModelingTransformation(mesh, obj.matrix)
1039
1040             self._doBackFaceCulling(mesh)
1041
1042             # When doing HSR with NEWELL we may want to flip all normals
1043             # toward the viewer
1044             if config.polygons['HSR'] == "NEWELL":
1045                 for f in mesh.faces:
1046                     f.sel = 1-f.sel
1047                 mesh.flipNormals()
1048                 for f in mesh.faces:
1049                     f.sel = 1
1050
1051             self._doLighting(mesh)
1052
1053
1054             # Do "projection" now so we perform further processing
1055             # in Normalized View Coordinates
1056             self._doProjection(mesh, self.proj)
1057
1058             self._doViewFrustumClipping(mesh)
1059
1060             self._doHiddenSurfaceRemoval(mesh)
1061
1062             self._doEdgesStyle(mesh, edgeStyles[config.edges['STYLE']])
1063
1064             
1065             # Update the object data, important! :)
1066             mesh.update()
1067
1068         return workScene
1069
1070
1071     ##
1072     # Private Methods
1073     #
1074
1075     # Utility methods
1076
1077     def _getObjPosition(self, obj):
1078         """Return the obj position in World coordinates.
1079         """
1080         return obj.matrix.translationPart()
1081
1082     def _cameraViewVector(self):
1083         """Get the View Direction form the camera matrix.
1084         """
1085         return Vector(self.cameraObj.matrix[2]).resize3D()
1086
1087
1088     # Faces methods
1089
1090     def _isFaceVisible(self, face):
1091         """Determine if a face of an object is visible from the current camera.
1092         
1093         The view vector is calculated from the camera location and one of the
1094         vertices of the face (expressed in World coordinates, after applying
1095         modelview transformations).
1096
1097         After those transformations we determine if a face is visible by
1098         computing the angle between the face normal and the view vector, this
1099         angle has to be between -90 and 90 degrees for the face to be visible.
1100         This corresponds somehow to the dot product between the two, if it
1101         results > 0 then the face is visible.
1102
1103         There is no need to normalize those vectors since we are only interested in
1104         the sign of the cross product and not in the product value.
1105
1106         NOTE: here we assume the face vertices are in WorldCoordinates, so
1107         please transform the object _before_ doing the test.
1108         """
1109
1110         normal = Vector(face.no)
1111         camPos = self._getObjPosition(self.cameraObj)
1112         view_vect = None
1113
1114         # View Vector in orthographics projections is the view Direction of
1115         # the camera
1116         if self.cameraObj.data.getType() == 1:
1117             view_vect = self._cameraViewVector()
1118
1119         # View vector in perspective projections can be considered as
1120         # the difference between the camera position and one point of
1121         # the face, we choose the farthest point from the camera.
1122         if self.cameraObj.data.getType() == 0:
1123             vv = max( [ ((camPos - Vector(v.co)).length, (camPos - Vector(v.co))) for v in face] )
1124             view_vect = vv[1]
1125
1126
1127         # if d > 0 the face is visible from the camera
1128         d = view_vect * normal
1129         
1130         if d > 0:
1131             return True
1132         else:
1133             return False
1134
1135
1136     # Scene methods
1137
1138     def _doSceneClipping(self, scene):
1139         """Clip whole objects against the View Frustum.
1140
1141         For now clip away only objects according to their center position.
1142         """
1143
1144         cpos = self._getObjPosition(self.cameraObj)
1145         view_vect = self._cameraViewVector()
1146
1147         near = self.cameraObj.data.clipStart
1148         far  = self.cameraObj.data.clipEnd
1149
1150         aspect = float(self.canvasRatio[0])/float(self.canvasRatio[1])
1151         fovy = atan(0.5/aspect/(self.cameraObj.data.lens/32))
1152         fovy = fovy * 360.0/pi
1153
1154         Objects = scene.getChildren()
1155         for o in Objects:
1156             if o.getType() != 'Mesh': continue;
1157
1158             obj_vect = Vector(cpos) - self._getObjPosition(o)
1159
1160             d = obj_vect*view_vect
1161             theta = AngleBetweenVecs(obj_vect, view_vect)
1162             
1163             # if the object is outside the view frustum, clip it away
1164             if (d < near) or (d > far) or (theta > fovy):
1165                 scene.unlink(o)
1166
1167     def _doConvertGeometricObjsToMesh(self, scene):
1168         """Convert all "geometric" objects to mesh ones.
1169         """
1170         geometricObjTypes = ['Mesh', 'Surf', 'Curve', 'Text']
1171         #geometricObjTypes = ['Mesh', 'Surf', 'Curve']
1172
1173         Objects = scene.getChildren()
1174         objList = [ o for o in Objects if o.getType() in geometricObjTypes ]
1175         for obj in objList:
1176             old_obj = obj
1177             obj = self._convertToRawMeshObj(obj)
1178             scene.link(obj)
1179             scene.unlink(old_obj)
1180
1181
1182             # XXX Workaround for Text and Curve which have some normals
1183             # inverted when they are converted to Mesh, REMOVE that when
1184             # blender will fix that!!
1185             if old_obj.getType() in ['Curve', 'Text']:
1186                 me = obj.getData(mesh=1)
1187                 for f in me.faces: f.sel = 1;
1188                 for v in me.verts: v.sel = 1;
1189                 me.remDoubles(0)
1190                 me.triangleToQuad()
1191                 me.recalcNormals()
1192                 me.update()
1193
1194
1195     def _doSceneDepthSorting(self, scene):
1196         """Sort objects in the scene.
1197
1198         The object sorting is done accordingly to the object centers.
1199         """
1200
1201         c = self._getObjPosition(self.cameraObj)
1202
1203         by_center_pos = (lambda o1, o2:
1204                 (o1.getType() == 'Mesh' and o2.getType() == 'Mesh') and
1205                 cmp((self._getObjPosition(o1) - Vector(c)).length,
1206                     (self._getObjPosition(o2) - Vector(c)).length)
1207             )
1208
1209         # TODO: implement sorting by bounding box, if obj1.bb is inside obj2.bb,
1210         # then ob1 goes farther than obj2, useful when obj2 has holes
1211         by_bbox = None
1212         
1213         Objects = scene.getChildren()
1214         Objects.sort(by_center_pos)
1215         
1216         # update the scene
1217         for o in Objects:
1218             scene.unlink(o)
1219             scene.link(o)
1220
1221     def _joinMeshObjectsInScene(self, scene):
1222         """Merge all the Mesh Objects in a scene into a single Mesh Object.
1223         """
1224
1225         oList = [o for o in scene.getChildren() if o.getType()=='Mesh']
1226
1227         # FIXME: Object.join() do not work if the list contains 1 object
1228         if len(oList) == 1:
1229             return
1230
1231         mesh = Mesh.New('BigOne')
1232         bigObj = Object.New('Mesh', 'BigOne')
1233         bigObj.link(mesh)
1234
1235         scene.link(bigObj)
1236
1237         try:
1238             bigObj.join(oList)
1239         except RuntimeError:
1240             print "\nWarning! - Can't Join Objects\n"
1241             scene.unlink(bigObj)
1242             return
1243         except TypeError:
1244             print "Objects Type error?"
1245         
1246         for o in oList:
1247             scene.unlink(o)
1248
1249         scene.update()
1250
1251  
1252     # Per object/mesh methods
1253
1254     def _convertToRawMeshObj(self, object):
1255         """Convert geometry based object to a mesh object.
1256         """
1257         me = Mesh.New('RawMesh_'+object.name)
1258         me.getFromObject(object.name)
1259
1260         newObject = Object.New('Mesh', 'RawMesh_'+object.name)
1261         newObject.link(me)
1262
1263         # If the object has no materials set a default material
1264         if not me.materials:
1265             me.materials = [Material.New()]
1266             #for f in me.faces: f.mat = 0
1267
1268         newObject.setMatrix(object.getMatrix())
1269
1270         return newObject
1271
1272     def _doModelingTransformation(self, mesh, matrix):
1273         """Transform object coordinates to world coordinates.
1274
1275         This step is done simply applying to the object its tranformation
1276         matrix and recalculating its normals.
1277         """
1278         # XXX FIXME: blender do not transform normals in the right way when
1279         # there are negative scale values
1280         if matrix[0][0] < 0 or matrix[1][1] < 0 or matrix[2][2] < 0:
1281             print "WARNING: Negative scales, expect incorrect results!"
1282
1283         mesh.transform(matrix, True)
1284
1285     def _doBackFaceCulling(self, mesh):
1286         """Simple Backface Culling routine.
1287         
1288         At this level we simply do a visibility test face by face and then
1289         select the vertices belonging to visible faces.
1290         """
1291         
1292         # Select all vertices, so edges can be displayed even if there are no
1293         # faces
1294         for v in mesh.verts:
1295             v.sel = 1
1296         
1297         Mesh.Mode(Mesh.SelectModes['FACE'])
1298         # Loop on faces
1299         for f in mesh.faces:
1300             f.sel = 0
1301             if self._isFaceVisible(f):
1302                 f.sel = 1
1303
1304     def _doLighting(self, mesh):
1305         """Apply an Illumination and shading model to the object.
1306
1307         The model used is the Phong one, it may be inefficient,
1308         but I'm just learning about rendering and starting from Phong seemed
1309         the most natural way.
1310         """
1311
1312         # If the mesh has vertex colors already, use them,
1313         # otherwise turn them on and do some calculations
1314         if mesh.vertexColors:
1315             return
1316         mesh.vertexColors = 1
1317
1318         materials = mesh.materials
1319
1320         camPos = self._getObjPosition(self.cameraObj)
1321
1322         # We do per-face color calculation (FLAT Shading), we can easily turn
1323         # to a per-vertex calculation if we want to implement some shading
1324         # technique. For an example see:
1325         # http://www.miralab.unige.ch/papers/368.pdf
1326         for f in mesh.faces:
1327             if not f.sel:
1328                 continue
1329
1330             mat = None
1331             if materials:
1332                 mat = materials[f.mat]
1333
1334             # A new default material
1335             if mat == None:
1336                 mat = Material.New('defMat')
1337
1338             # Check if it is a shadeless material
1339             elif mat.getMode() & Material.Modes['SHADELESS']:
1340                 I = mat.getRGBCol()
1341                 # Convert to a value between 0 and 255
1342                 tmp_col = [ int(c * 255.0) for c in I]
1343
1344                 for c in f.col:
1345                     c.r = tmp_col[0]
1346                     c.g = tmp_col[1]
1347                     c.b = tmp_col[2]
1348                     #c.a = tmp_col[3]
1349
1350                 continue
1351
1352
1353             # do vertex color calculation
1354
1355             TotDiffSpec = Vector([0.0, 0.0, 0.0])
1356
1357             for l in self.lights:
1358                 light_obj = l
1359                 light_pos = self._getObjPosition(l)
1360                 light = light_obj.getData()
1361             
1362                 L = Vector(light_pos).normalize()
1363
1364                 V = (Vector(camPos) - Vector(f.cent)).normalize()
1365
1366                 N = Vector(f.no).normalize()
1367
1368                 if config.polygons['SHADING'] == 'TOON':
1369                     NL = ShadingUtils.toonShading(N*L)
1370                 else:
1371                     NL = (N*L)
1372
1373                 # Should we use NL instead of (N*L) here?
1374                 R = 2 * (N*L) * N - L
1375
1376                 Ip = light.getEnergy()
1377
1378                 # Diffuse co-efficient
1379                 kd = mat.getRef() * Vector(mat.getRGBCol())
1380                 for i in [0, 1, 2]:
1381                     kd[i] *= light.col[i]
1382
1383                 Idiff = Ip * kd * max(0, NL)
1384
1385
1386                 # Specular component
1387                 ks = mat.getSpec() * Vector(mat.getSpecCol())
1388                 ns = mat.getHardness()
1389                 Ispec = Ip * ks * pow(max(0, (V*R)), ns)
1390
1391                 TotDiffSpec += (Idiff+Ispec)
1392
1393
1394             # Ambient component
1395             Iamb = Vector(Blender.World.Get()[0].getAmb())
1396             ka = mat.getAmb()
1397
1398             # Emissive component (convert to a triplet)
1399             ki = Vector([mat.getEmit()]*3)
1400
1401             #I = ki + Iamb + (Idiff + Ispec)
1402             I = ki + (ka * Iamb) + TotDiffSpec
1403
1404
1405             # Set Alpha component
1406             I = list(I)
1407             I.append(mat.getAlpha())
1408
1409             # Clamp I values between 0 and 1
1410             I = [ min(c, 1) for c in I]
1411             I = [ max(0, c) for c in I]
1412
1413             # Convert to a value between 0 and 255
1414             tmp_col = [ int(c * 255.0) for c in I]
1415
1416             for c in f.col:
1417                 c.r = tmp_col[0]
1418                 c.g = tmp_col[1]
1419                 c.b = tmp_col[2]
1420                 c.a = tmp_col[3]
1421
1422     def _doProjection(self, mesh, projector):
1423         """Apply Viewing and Projection tranformations.
1424         """
1425
1426         for v in mesh.verts:
1427             p = projector.doProjection(v.co[:])
1428             v.co[0] = p[0]
1429             v.co[1] = p[1]
1430             v.co[2] = p[2]
1431
1432         #mesh.recalcNormals()
1433         #mesh.update()
1434
1435         # We could reeset Camera matrix, since now
1436         # we are in Normalized Viewing Coordinates,
1437         # but doung that would affect World Coordinate
1438         # processing for other objects
1439
1440         #self.cameraObj.data.type = 1
1441         #self.cameraObj.data.scale = 2.0
1442         #m = Matrix().identity()
1443         #self.cameraObj.setMatrix(m)
1444
1445     def _doViewFrustumClipping(self, mesh):
1446         """Clip faces against the View Frustum.
1447         """
1448
1449     # HSR routines
1450     def __simpleDepthSort(self, mesh):
1451         """Sort faces by the furthest vertex.
1452
1453         This simple mesthod is known also as the painter algorithm, and it
1454         solves HSR correctly only for convex meshes.
1455         """
1456
1457         global progress
1458         # The sorting requires circa n*log(n) steps
1459         n = len(mesh.faces)
1460         progress.setActivity("HSR: Painter", n*log(n))
1461
1462         by_furthest_z = (lambda f1, f2: progress.update() and
1463                 cmp(max([v.co[2] for v in f1]), max([v.co[2] for v in f2])+EPS)
1464                 )
1465
1466         # FIXME: using NMesh to sort faces. We should avoid that!
1467         nmesh = NMesh.GetRaw(mesh.name)
1468
1469         # remember that _higher_ z values mean further points
1470         nmesh.faces.sort(by_furthest_z)
1471         nmesh.faces.reverse()
1472
1473         nmesh.update()
1474
1475     def __newellDepthSort(self, mesh):
1476         """Newell's depth sorting.
1477
1478         """
1479
1480         from hsrtk import *
1481
1482         # Find non planar quads and convert them to triangle
1483         #for f in mesh.faces:
1484         #    f.sel = 0
1485         #    if is_nonplanar_quad(f.v):
1486         #        print "NON QUAD??"
1487         #        f.sel = 1
1488
1489
1490         # Now reselect all faces
1491         for f in mesh.faces:
1492             f.sel = 1
1493
1494         # FIXME: using NMesh to sort faces. We should avoid that!
1495         nmesh = NMesh.GetRaw(mesh.name)
1496
1497         # remember that _higher_ z values mean further points
1498         nmesh.faces.sort(by_furthest_z)
1499         nmesh.faces.reverse()
1500
1501         
1502         # Begin depth sort tests
1503
1504         # use the smooth flag to set marked faces
1505         for f in nmesh.faces:
1506             f.smooth = 0
1507
1508         facelist = nmesh.faces[:]
1509         maplist = []
1510
1511
1512         # The steps are _at_least_ equal to len(facelist), we do not count the
1513         # feces coming out from splitting!!
1514         global progress
1515         progress.setActivity("HSR: Newell", len(facelist))
1516         #progress.setQuiet(True)
1517
1518         
1519         while len(facelist):
1520             debug("\n----------------------\n")
1521             debug("len(facelits): %d\n" % len(facelist))
1522             P = facelist[0]
1523
1524             pSign = sign(P.normal[2])
1525
1526             # We can discard faces parallel to the view vector
1527             if P.normal[2] == 0:
1528                 facelist.remove(P)
1529                 continue
1530
1531             split_done = 0
1532             face_marked = 0
1533
1534             for Q in facelist[1:]:
1535
1536                 debug("P.smooth: " + str(P.smooth) + "\n")
1537                 debug("Q.smooth: " + str(Q.smooth) + "\n")
1538                 debug("\n")
1539
1540                 qSign = sign(Q.normal[2])
1541                 # TODO: check also if Q is parallel??
1542  
1543                 # Test 0: We need to test only those Qs whose furthest vertex
1544                 # is closer to the observer than the closest vertex of P.
1545
1546                 zP = [v.co[2] for v in P.v]
1547                 zQ = [v.co[2] for v in Q.v]
1548                 notZOverlap = min(zP) > max(zQ)+EPS
1549
1550                 if notZOverlap:
1551                     debug("\nTest 0\n")
1552                     debug("NOT Z OVERLAP!\n")
1553                     if Q.smooth == 0:
1554                         # If Q is not marked then we can safely print P
1555                         break
1556                     else:
1557                         debug("met a marked face\n")
1558                         continue
1559
1560                 
1561                 # Test 1: X extent overlapping
1562                 xP = [v.co[0] for v in P.v]
1563                 xQ = [v.co[0] for v in Q.v]
1564                 #notXOverlap = (max(xP) <= min(xQ)) or (max(xQ) <= min(xP))
1565                 notXOverlap = (min(xQ) >= max(xP)-EPS) or (min(xP) >= max(xQ)-EPS)
1566
1567                 if notXOverlap:
1568                     debug("\nTest 1\n")
1569                     debug("NOT X OVERLAP!\n")
1570                     continue
1571
1572
1573                 # Test 2: Y extent Overlapping
1574                 yP = [v.co[1] for v in P.v]
1575                 yQ = [v.co[1] for v in Q.v]
1576                 #notYOverlap = (max(yP) <= min(yQ)) or (max(yQ) <= min(yP))
1577                 notYOverlap = (min(yQ) >= max(yP)-EPS) or (min(yP) >= max(yQ)-EPS)
1578
1579                 if notYOverlap:
1580                     debug("\nTest 2\n")
1581                     debug("NOT Y OVERLAP!\n")
1582                     continue
1583                 
1584
1585                 # Test 3: P vertices are all behind the plane of Q
1586                 n = 0
1587                 for Pi in P:
1588                     d = qSign * Distance(Vector(Pi), Q)
1589                     if d <= EPS:
1590                         n += 1
1591                 pVerticesBehindPlaneQ = (n == len(P))
1592
1593                 if pVerticesBehindPlaneQ:
1594                     debug("\nTest 3\n")
1595                     debug("P BEHIND Q!\n")
1596                     continue
1597
1598
1599                 # Test 4: Q vertices in front of the plane of P
1600                 n = 0
1601                 for Qi in Q:
1602                     d = pSign * Distance(Vector(Qi), P)
1603                     if d >= -EPS:
1604                         n += 1
1605                 qVerticesInFrontPlaneP = (n == len(Q))
1606
1607                 if qVerticesInFrontPlaneP:
1608                     debug("\nTest 4\n")
1609                     debug("Q IN FRONT OF P!\n")
1610                     continue
1611
1612
1613                 # Test 5: Check if projections of polygons effectively overlap,
1614                 # in previous tests we checked only bounding boxes.
1615
1616                 if not projectionsOverlap(P, Q):
1617                     debug("\nTest 5\n")
1618                     debug("Projections do not overlap!\n")
1619                     continue
1620
1621                 # We still can't say if P obscures Q.
1622
1623                 # But if Q is marked we do a face-split trying to resolve a
1624                 # difficulty (maybe a visibility cycle).
1625                 if Q.smooth == 1:
1626                     # Split P or Q
1627                     debug("Possibly a cycle detected!\n")
1628                     debug("Split here!!\n")
1629
1630                     facelist = facesplit(P, Q, facelist, nmesh)
1631                     split_done = 1
1632                     break 
1633
1634                 # The question now is: Does Q obscure P?
1635
1636
1637                 # Test 3bis: Q vertices are all behind the plane of P
1638                 n = 0
1639                 for Qi in Q:
1640                     d = pSign * Distance(Vector(Qi), P)
1641                     if d <= EPS:
1642                         n += 1
1643                 qVerticesBehindPlaneP = (n == len(Q))
1644
1645                 if qVerticesBehindPlaneP:
1646                     debug("\nTest 3bis\n")
1647                     debug("Q BEHIND P!\n")
1648
1649
1650                 # Test 4bis: P vertices in front of the plane of Q
1651                 n = 0
1652                 for Pi in P:
1653                     d = qSign * Distance(Vector(Pi), Q)
1654                     if d >= -EPS:
1655                         n += 1
1656                 pVerticesInFrontPlaneQ = (n == len(P))
1657
1658                 if pVerticesInFrontPlaneQ:
1659                     debug("\nTest 4bis\n")
1660                     debug("P IN FRONT OF Q!\n")
1661
1662                 
1663                 # We don't even know if Q does obscure P, so they should
1664                 # intersect each other, split one of them in two parts.
1665                 if not qVerticesBehindPlaneP and not pVerticesInFrontPlaneQ:
1666                     debug("\nSimple Intersection?\n")
1667                     debug("Test 3bis or 4bis failed\n")
1668                     debug("Split here!!2\n")
1669
1670                     facelist = facesplit(P, Q, facelist, nmesh)
1671                     split_done = 1
1672                     break 
1673                     
1674                 facelist.remove(Q)
1675                 facelist.insert(0, Q)
1676                 Q.smooth = 1
1677                 face_marked = 1
1678                 debug("Q marked!\n")
1679                 break
1680            
1681             # Write P!                     
1682             if split_done == 0 and face_marked == 0:
1683                 facelist.remove(P)
1684                 maplist.append(P)
1685
1686                 progress.update()
1687
1688             if facelist == None:
1689                 maplist = [P, Q]
1690                 print [v.co for v in P]
1691                 print [v.co for v in Q]
1692                 break
1693
1694             # end of while len(facelist)
1695          
1696
1697         nmesh.faces = maplist
1698
1699         nmesh.update()
1700
1701
1702     def _doHiddenSurfaceRemoval(self, mesh):
1703         """Do HSR for the given mesh.
1704         """
1705         if len(mesh.faces) == 0:
1706             return
1707
1708         if config.polygons['HSR'] == 'PAINTER':
1709             print "\nUsing the Painter algorithm for HSR."
1710             self.__simpleDepthSort(mesh)
1711
1712         elif config.polygons['HSR'] == 'NEWELL':
1713             print "\nUsing the Newell's algorithm for HSR."
1714             self.__newellDepthSort(mesh)
1715
1716
1717     def _doEdgesStyle(self, mesh, edgestyleSelect):
1718         """Process Mesh Edges accroding to a given selection style.
1719
1720         Examples of algorithms:
1721
1722         Contours:
1723             given an edge if its adjacent faces have the same normal (that is
1724             they are complanar), than deselect it.
1725
1726         Silhouettes:
1727             given an edge if one its adjacent faces is frontfacing and the
1728             other is backfacing, than select it, else deselect.
1729         """
1730
1731         Mesh.Mode(Mesh.SelectModes['EDGE'])
1732
1733         edge_cache = MeshUtils.buildEdgeFaceUsersCache(mesh)
1734
1735         for i,edge_faces in enumerate(edge_cache):
1736             mesh.edges[i].sel = 0
1737             if edgestyleSelect(edge_faces):
1738                 mesh.edges[i].sel = 1
1739
1740         """
1741         for e in mesh.edges:
1742
1743             e.sel = 0
1744             if edgestyleSelect(e, mesh):
1745                 e.sel = 1
1746         """
1747                 
1748
1749
1750 # ---------------------------------------------------------------------
1751 #
1752 ## GUI Class and Main Program
1753 #
1754 # ---------------------------------------------------------------------
1755
1756
1757 from Blender import BGL, Draw
1758 from Blender.BGL import *
1759
1760 class GUI:
1761     
1762     def _init():
1763
1764         # Output Format menu 
1765         output_format = config.output['FORMAT']
1766         default_value = outputWriters.keys().index(output_format)+1
1767         GUI.outFormatMenu = Draw.Create(default_value)
1768         GUI.evtOutFormatMenu = 0
1769
1770         # Animation toggle button
1771         GUI.animToggle = Draw.Create(config.output['ANIMATION'])
1772         GUI.evtAnimToggle = 1
1773
1774         # Join Objects toggle button
1775         GUI.joinObjsToggle = Draw.Create(config.output['JOIN_OBJECTS'])
1776         GUI.evtJoinObjsToggle = 2
1777
1778         # Render filled polygons
1779         GUI.polygonsToggle = Draw.Create(config.polygons['SHOW'])
1780
1781         # Shading Style menu 
1782         shading_style = config.polygons['SHADING']
1783         default_value = shadingStyles.keys().index(shading_style)+1
1784         GUI.shadingStyleMenu = Draw.Create(default_value)
1785         GUI.evtShadingStyleMenu = 21
1786
1787         GUI.evtPolygonsToggle = 3
1788         # We hide the config.polygons['EXPANSION_TRICK'], for now
1789
1790         # Render polygon edges
1791         GUI.showEdgesToggle = Draw.Create(config.edges['SHOW'])
1792         GUI.evtShowEdgesToggle = 4
1793
1794         # Render hidden edges
1795         GUI.showHiddenEdgesToggle = Draw.Create(config.edges['SHOW_HIDDEN'])
1796         GUI.evtShowHiddenEdgesToggle = 5
1797
1798         # Edge Style menu 
1799         edge_style = config.edges['STYLE']
1800         default_value = edgeStyles.keys().index(edge_style)+1
1801         GUI.edgeStyleMenu = Draw.Create(default_value)
1802         GUI.evtEdgeStyleMenu = 6
1803
1804         # Edge Width slider
1805         GUI.edgeWidthSlider = Draw.Create(config.edges['WIDTH'])
1806         GUI.evtEdgeWidthSlider = 7
1807
1808         # Edge Color Picker
1809         c = config.edges['COLOR']
1810         GUI.edgeColorPicker = Draw.Create(c[0]/255.0, c[1]/255.0, c[2]/255.0)
1811         GUI.evtEdgeColorPicker = 71
1812
1813         # Render Button
1814         GUI.evtRenderButton = 8
1815
1816         # Exit Button
1817         GUI.evtExitButton = 9
1818
1819     def draw():
1820
1821         # initialize static members
1822         GUI._init()
1823
1824         glClear(GL_COLOR_BUFFER_BIT)
1825         glColor3f(0.0, 0.0, 0.0)
1826         glRasterPos2i(10, 350)
1827         Draw.Text("VRM: Vector Rendering Method script. Version %s." %
1828                 __version__)
1829         glRasterPos2i(10, 335)
1830         Draw.Text("Press Q or ESC to quit.")
1831
1832         # Build the output format menu
1833         glRasterPos2i(10, 310)
1834         Draw.Text("Select the output Format:")
1835         outMenuStruct = "Output Format %t"
1836         for t in outputWriters.keys():
1837            outMenuStruct = outMenuStruct + "|%s" % t
1838         GUI.outFormatMenu = Draw.Menu(outMenuStruct, GUI.evtOutFormatMenu,
1839                 10, 285, 160, 18, GUI.outFormatMenu.val, "Choose the Output Format")
1840
1841         # Animation toggle
1842         GUI.animToggle = Draw.Toggle("Animation", GUI.evtAnimToggle,
1843                 10, 260, 160, 18, GUI.animToggle.val,
1844                 "Toggle rendering of animations")
1845
1846         # Join Objects toggle
1847         GUI.joinObjsToggle = Draw.Toggle("Join objects", GUI.evtJoinObjsToggle,
1848                 10, 235, 160, 18, GUI.joinObjsToggle.val,
1849                 "Join objects in the rendered file")
1850
1851         # Render Button
1852         Draw.Button("Render", GUI.evtRenderButton, 10, 210-25, 75, 25+18,
1853                 "Start Rendering")
1854         Draw.Button("Exit", GUI.evtExitButton, 95, 210-25, 75, 25+18, "Exit!")
1855
1856         # Rendering Styles
1857         glRasterPos2i(200, 310)
1858         Draw.Text("Rendering Style:")
1859
1860         # Render Polygons
1861         GUI.polygonsToggle = Draw.Toggle("Filled Polygons", GUI.evtPolygonsToggle,
1862                 200, 285, 160, 18, GUI.polygonsToggle.val,
1863                 "Render filled polygons")
1864
1865         if GUI.polygonsToggle.val == 1:
1866
1867             # Polygon Shading Style
1868             shadingStyleMenuStruct = "Shading Style %t"
1869             for t in shadingStyles.keys():
1870                 shadingStyleMenuStruct = shadingStyleMenuStruct + "|%s" % t.lower()
1871             GUI.shadingStyleMenu = Draw.Menu(shadingStyleMenuStruct, GUI.evtShadingStyleMenu,
1872                     200, 260, 160, 18, GUI.shadingStyleMenu.val,
1873                     "Choose the shading style")
1874
1875
1876         # Render Edges
1877         GUI.showEdgesToggle = Draw.Toggle("Show Edges", GUI.evtShowEdgesToggle,
1878                 200, 235, 160, 18, GUI.showEdgesToggle.val,
1879                 "Render polygon edges")
1880
1881         if GUI.showEdgesToggle.val == 1:
1882             
1883             # Edge Style
1884             edgeStyleMenuStruct = "Edge Style %t"
1885             for t in edgeStyles.keys():
1886                 edgeStyleMenuStruct = edgeStyleMenuStruct + "|%s" % t.lower()
1887             GUI.edgeStyleMenu = Draw.Menu(edgeStyleMenuStruct, GUI.evtEdgeStyleMenu,
1888                     200, 210, 160, 18, GUI.edgeStyleMenu.val,
1889                     "Choose the edge style")
1890
1891             # Edge size
1892             GUI.edgeWidthSlider = Draw.Slider("Width: ", GUI.evtEdgeWidthSlider,
1893                     200, 185, 140, 18, GUI.edgeWidthSlider.val,
1894                     0.0, 10.0, 0, "Change Edge Width")
1895
1896             # Edge Color
1897             GUI.edgeColorPicker = Draw.ColorPicker(GUI.evtEdgeColorPicker,
1898                     342, 185, 18, 18, GUI.edgeColorPicker.val, "Choose Edge Color")
1899
1900             # Show Hidden Edges
1901             GUI.showHiddenEdgesToggle = Draw.Toggle("Show Hidden Edges",
1902                     GUI.evtShowHiddenEdgesToggle,
1903                     200, 160, 160, 18, GUI.showHiddenEdgesToggle.val,
1904                     "Render hidden edges as dashed lines")
1905
1906         glRasterPos2i(10, 160)
1907         Draw.Text("%s (c) 2006" % __author__)
1908
1909     def event(evt, val):
1910
1911         if evt == Draw.ESCKEY or evt == Draw.QKEY:
1912             Draw.Exit()
1913         else:
1914             return
1915
1916         Draw.Redraw(1)
1917
1918     def button_event(evt):
1919
1920         if evt == GUI.evtExitButton:
1921             Draw.Exit()
1922
1923         elif evt == GUI.evtOutFormatMenu:
1924             i = GUI.outFormatMenu.val - 1
1925             config.output['FORMAT']= outputWriters.keys()[i]
1926
1927         elif evt == GUI.evtAnimToggle:
1928             config.output['ANIMATION'] = bool(GUI.animToggle.val)
1929
1930         elif evt == GUI.evtJoinObjsToggle:
1931             config.output['JOIN_OBJECTS'] = bool(GUI.joinObjsToggle.val)
1932
1933         elif evt == GUI.evtPolygonsToggle:
1934             config.polygons['SHOW'] = bool(GUI.polygonsToggle.val)
1935
1936         elif evt == GUI.evtShadingStyleMenu:
1937             i = GUI.shadingStyleMenu.val - 1
1938             config.polygons['SHADING'] = shadingStyles.keys()[i]
1939
1940         elif evt == GUI.evtShowEdgesToggle:
1941             config.edges['SHOW'] = bool(GUI.showEdgesToggle.val)
1942
1943         elif evt == GUI.evtShowHiddenEdgesToggle:
1944             config.edges['SHOW_HIDDEN'] = bool(GUI.showHiddenEdgesToggle.val)
1945
1946         elif evt == GUI.evtEdgeStyleMenu:
1947             i = GUI.edgeStyleMenu.val - 1
1948             config.edges['STYLE'] = edgeStyles.keys()[i]
1949
1950         elif evt == GUI.evtEdgeWidthSlider:
1951             config.edges['WIDTH'] = float(GUI.edgeWidthSlider.val)
1952
1953         elif evt == GUI.evtEdgeColorPicker:
1954             config.edges['COLOR'] = [int(c*255.0) for c in GUI.edgeColorPicker.val]
1955
1956         elif evt == GUI.evtRenderButton:
1957             label = "Save %s" % config.output['FORMAT']
1958             # Show the File Selector
1959             global outputfile
1960             Blender.Window.FileSelector(vectorize, label, outputfile)
1961
1962         else:
1963             print "Event: %d not handled!" % evt
1964
1965         if evt:
1966             Draw.Redraw(1)
1967             #GUI.conf_debug()
1968
1969     def conf_debug():
1970         from pprint import pprint
1971         print "\nConfig"
1972         pprint(config.output)
1973         pprint(config.polygons)
1974         pprint(config.edges)
1975
1976     _init = staticmethod(_init)
1977     draw = staticmethod(draw)
1978     event = staticmethod(event)
1979     button_event = staticmethod(button_event)
1980     conf_debug = staticmethod(conf_debug)
1981
1982 # A wrapper function for the vectorizing process
1983 def vectorize(filename):
1984     """The vectorizing process is as follows:
1985      
1986      - Instanciate the writer and the renderer
1987      - Render!
1988      """
1989
1990     if filename == "":
1991         print "\nERROR: invalid file name!"
1992         return
1993
1994     from Blender import Window
1995     editmode = Window.EditMode()
1996     if editmode: Window.EditMode(0)
1997
1998     actualWriter = outputWriters[config.output['FORMAT']]
1999     writer = actualWriter(filename)
2000     
2001     renderer = Renderer()
2002     renderer.doRendering(writer, config.output['ANIMATION'])
2003
2004     if editmode: Window.EditMode(1) 
2005
2006 # We use a global progress Indicator Object
2007 progress = None
2008
2009 # Here the main
2010 if __name__ == "__main__":
2011
2012     global progress
2013
2014     outputfile = ""
2015     basename = Blender.sys.basename(Blender.Get('filename'))
2016     if basename != "":
2017         outputfile = Blender.sys.splitext(basename)[0] + "." + str(config.output['FORMAT']).lower()
2018
2019     if Blender.mode == 'background':
2020         progress = ConsoleProgressIndicator()
2021         vectorize(outputfile)
2022     else:
2023         progress = GraphicalProgressIndicator()
2024         Draw.Register(GUI.draw, GUI.event, GUI.button_event)