source: OGRE/trunk/ogrenew/Tools/Wings3DExporter/pgon.py @ 657

Revision 657, 4.6 KB checked in by mattausch, 19 years ago (diff)

added ogre dependencies and patched ogre sources

Line 
1# ear-clipping polygon triangulation
2#
3# written in 2003 by Attila Tajti
4
5from vector import Vector
6
7def sum(a, b):
8        return a + b
9
10# get the average normal of a 3d polygon
11def pgon_normal(verts):
12        normal = Vector(0,0,0)
13        for i in range(len(verts)):
14                x1, y1, z1 = verts[i - 1]
15                x2, y2, z2 = verts[i]
16                nx = (y1 - y2) * (z1 + z2)
17                ny = (z1 - z2) * (x1 + x2)
18                nz = (x1 - x2) * (y1 + y2)
19                normal += Vector(nx, ny, nz)
20        return normal.unit()
21
22class Triangulator:
23
24        def dump(self, what):
25                if __name__ == "__main__":
26                        print what
27
28        def __init__(self, pgon):
29                self.pgon = pgon
30
31                self.dump("pgon: %s" % repr(self.pgon))
32
33                # normal used for direction calculation
34                self.normal = pgon_normal(pgon)
35                self.dump("normal: %s" % repr(self.normal))
36
37                # original indices
38                self.indices = range(len(self.pgon))
39
40                # result triangles
41                self.tris = []
42       
43        def process(self):
44
45                while len(self.indices) > 3:
46                        self.find_and_clip_ear()
47               
48                self.tris.append(self.indices)
49
50                self.dump("triangles: %s\n" % repr(self.tris))
51
52                return self.tris
53
54        def this_v(self, vert):
55                "return position of given vertex"
56                return self.pgon[vert]
57
58        def pred_i(self, vert):
59                cur = self.indices.index(vert)
60                return self.indices[cur - 1]
61
62        def pred_v(self, vert):
63                "return position of predecessor vertex"
64                pred = self.pred_i(vert)
65                return self.pgon[pred]
66
67        def succ_i(self, vert):
68                cur = self.indices.index(vert)
69                return self.indices[cur + 1 - len(self.indices)]
70
71        def succ_v(self, vert):
72                "return position of successor vertex"
73                succ = self.succ_i(vert)
74                return self.pgon[succ]
75
76        def tri_i_at(self, vert):
77                Ai = self.pred_i(vert)
78                Bi = vert
79                Ci = self.succ_i(vert)
80                #self.dump("   tri %d,%d,%d" % (Ai,Bi,Ci))
81                return Ai, Bi, Ci
82
83        def tri_at(self, vert):
84                Ai, Bi, Ci = self.tri_i_at(vert)
85                A = self.pgon[Ai]
86                B = self.pgon[Bi]
87                C = self.pgon[Ci]
88                return A, B, C
89
90        def reflex_factor(self, eartip):
91                A, B, C = self.tri_at(eartip)
92                AB = B - A
93                BC = C - B
94                # vector pointing outside
95                AB_out = Vector.cross(AB, self.normal).unit()
96                return Vector.dot(AB_out, BC.unit())
97
98        def is_convex(self, eartip):
99                return self.reflex_factor(eartip) < 0
100
101        def all_outside(self, eartip, verts):
102                tri = self.tri_at(eartip)
103                A, B, C = tri
104                sides = B - A, C - B, A - C
105                # vector pointing outside
106                normals = map(lambda x: Vector.cross(x, self.normal), sides)
107                for vert in map(lambda x: self.pgon[x], verts):
108                        out = 0
109                        for i in range(3):
110                                outside_edge = Vector.dot(vert - tri[i], normals[i])
111                                if outside_edge:
112                                        out = 1
113                        # vertex inside triangle
114                        if not out: return 0
115                return 1
116
117        def is_ear(self, eartip):
118
119                # create array of other vertices
120                others = self.indices[:]
121
122                # remove current triangle
123                A, B, C = self.tri_i_at(eartip)
124                others.remove(A)
125                others.remove(B)
126                others.remove(C)
127
128                # check if all is outside
129                return self.all_outside(eartip, others)
130
131        def clip_ear(self, vert):
132                self.tris.append(list(self.tri_i_at(vert)))
133                self.indices.remove(vert)
134
135        def find_and_clip_ear(self):
136                "find clip one ear"
137
138                # try to cut at the tightest angles first
139                # TODO: check if this is good for us
140
141                # vertices we are working with
142                work = self.indices[:]
143
144                # factors for all vertices
145                factors = map(self.reflex_factor, work)
146
147                while len(factors):
148                        f = min(factors)
149                        eartip = work[factors.index(f)]
150
151                        if self.is_ear(eartip):
152
153                                self.clip_ear(eartip)
154                                return
155                        else:
156                                # remove this from our work list
157                                factors.remove(f)
158                                work.remove(eartip)
159
160                print self.pgon
161                print self.indices
162                raise ValueError("failed!")
163
164        def find_and_clip_earx(self):
165                "find clip one ear"
166
167                print self.indices
168                for vert in self.indices:
169                        # check if point is convex
170                        if self.is_convex(vert):
171                                self.dump("%s is convex" % repr(vert))
172
173                                # check if this vertex is an ear
174                                if self.is_ear(vert):
175
176                                        self.dump("%s is an ear" % repr(vert))
177
178                                        # found an eartip, remove it
179                                        self.clip_ear(vert)
180                                        return
181                        else:
182                                self.dump("%s is reflex" % repr(vert))
183                raise ValueError("failed!")
184
185
186def triangulate(pgon):
187        "triangulate a polygon defined by its vertices"
188
189        t = Triangulator(pgon)
190
191        return t.process()
192
193if __name__ == "__main__":
194
195        print "* normal polygon"
196        pgon = []
197        pgon.append(Vector(0,0,0))
198        pgon.append(Vector(1,0,0))
199        pgon.append(Vector(1,1,0))
200        pgon.append(Vector(0,1,0))
201        triangulate(pgon)
202       
203        print "* concave polygon"
204        pgon = []
205        pgon.append(Vector(0,0,0))
206        pgon.append(Vector(1,1,0))
207        pgon.append(Vector(3,0,0))
208        pgon.append(Vector(3,1,0))
209        pgon.append(Vector(0,1,0))
210        triangulate(pgon)
211       
212        print "* poly with straight edges"
213        pgon = []
214        pgon.append(Vector(0,0,0))
215        pgon.append(Vector(0.5,0,0))
216        pgon.append(Vector(1,0,0))
217        pgon.append(Vector(2,0,0))
218        pgon.append(Vector(2,2,0))
219        pgon.append(Vector(0,2,0))
220        triangulate(pgon)
221
Note: See TracBrowser for help on using the repository browser.