Code Cleanup: spelling
[blender.git] / source / blender / bmesh / intern / bmesh_polygon.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Joseph Eagar, Geoffrey Bantle, Campbell Barton
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/intern/bmesh_polygon.c
24  *  \ingroup bmesh
25  *
26  * This file contains code for dealing
27  * with polygons (normal/area calculation,
28  * tessellation, etc)
29  */
30
31 #include "DNA_listBase.h"
32 #include "DNA_modifier_types.h"
33
34 #include "MEM_guardedalloc.h"
35
36 #include "BLI_alloca.h"
37 #include "BLI_math.h"
38 #include "BLI_memarena.h"
39 #include "BLI_polyfill2d.h"
40 #include "BLI_listbase.h"
41
42 #include "bmesh.h"
43 #include "bmesh_tools.h"
44
45 #include "intern/bmesh_private.h"
46
47 /**
48  * \brief TEST EDGE SIDE and POINT IN TRIANGLE
49  *
50  * Point in triangle tests stolen from scanfill.c.
51  * Used for tessellator
52  */
53
54 static bool testedgesidef(const float v1[2], const float v2[2], const float v3[2])
55 {
56         /* is v3 to the right of v1 - v2 ? With exception: v3 == v1 || v3 == v2 */
57         double inp;
58
59         //inp = (v2[cox] - v1[cox]) * (v1[coy] - v3[coy]) + (v1[coy] - v2[coy]) * (v1[cox] - v3[cox]);
60         inp = (v2[0] - v1[0]) * (v1[1] - v3[1]) + (v1[1] - v2[1]) * (v1[0] - v3[0]);
61
62         if (inp < 0.0) {
63                 return false;
64         }
65         else if (inp == 0) {
66                 if (v1[0] == v3[0] && v1[1] == v3[1]) return false;
67                 if (v2[0] == v3[0] && v2[1] == v3[1]) return false;
68         }
69         return true;
70 }
71
72 /**
73  * \brief COMPUTE POLY NORMAL
74  *
75  * Computes the normal of a planar
76  * polygon See Graphics Gems for
77  * computing newell normal.
78  */
79 static void calc_poly_normal(float normal[3], float verts[][3], int nverts)
80 {
81         float const *v_prev = verts[nverts - 1];
82         float const *v_curr = verts[0];
83         float n[3] = {0.0f};
84         int i;
85
86         /* Newell's Method */
87         for (i = 0; i < nverts; v_prev = v_curr, v_curr = verts[++i]) {
88                 add_newell_cross_v3_v3v3(n, v_prev, v_curr);
89         }
90
91         if (UNLIKELY(normalize_v3_v3(normal, n) == 0.0f)) {
92                 normal[2] = 1.0f; /* other axis set to 0.0 */
93         }
94 }
95
96 /**
97  * \brief COMPUTE POLY NORMAL (BMFace)
98  *
99  * Same as #calc_poly_normal but operates directly on a bmesh face.
100  */
101 static void bm_face_calc_poly_normal(const BMFace *f, float n[3])
102 {
103         BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
104         BMLoop *l_iter  = l_first;
105         float const *v_prev = l_first->prev->v->co;
106         float const *v_curr = l_first->v->co;
107
108         zero_v3(n);
109
110         /* Newell's Method */
111         do {
112                 add_newell_cross_v3_v3v3(n, v_prev, v_curr);
113
114                 l_iter = l_iter->next;
115                 v_prev = v_curr;
116                 v_curr = l_iter->v->co;
117
118         } while (l_iter != l_first);
119
120         if (UNLIKELY(normalize_v3(n) == 0.0f)) {
121                 n[2] = 1.0f;
122         }
123 }
124
125 /**
126  * \brief COMPUTE POLY NORMAL (BMFace)
127  *
128  * Same as #calc_poly_normal and #bm_face_calc_poly_normal
129  * but takes an array of vertex locations.
130  */
131 static void bm_face_calc_poly_normal_vertex_cos(BMFace *f, float r_no[3],
132                                                 float const (*vertexCos)[3])
133 {
134         BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
135         BMLoop *l_iter  = l_first;
136         float const *v_prev = vertexCos[BM_elem_index_get(l_first->prev->v)];
137         float const *v_curr = vertexCos[BM_elem_index_get(l_first->v)];
138
139         zero_v3(r_no);
140
141         /* Newell's Method */
142         do {
143                 add_newell_cross_v3_v3v3(r_no, v_prev, v_curr);
144
145                 l_iter = l_iter->next;
146                 v_prev = v_curr;
147                 v_curr = vertexCos[BM_elem_index_get(l_iter->v)];
148         } while (l_iter != l_first);
149
150         if (UNLIKELY(normalize_v3(r_no) == 0.0f)) {
151                 r_no[2] = 1.0f; /* other axis set to 0.0 */
152         }
153 }
154
155 /**
156  * \brief COMPUTE POLY CENTER (BMFace)
157  */
158 static void bm_face_calc_poly_center_mean_vertex_cos(BMFace *f, float r_cent[3],
159                                                      float const (*vertexCos)[3])
160 {
161         BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
162         BMLoop *l_iter  = l_first;
163
164         zero_v3(r_cent);
165
166         /* Newell's Method */
167         do {
168                 add_v3_v3(r_cent, vertexCos[BM_elem_index_get(l_iter->v)]);
169         } while ((l_iter = l_iter->next) != l_first);
170         mul_v3_fl(r_cent, 1.0f / f->len);
171 }
172
173 /**
174  * For tools that insist on using triangles, ideally we would cache this data.
175  *
176  * \param r_loops  Store face loop pointers, (f->len)
177  * \param r_index  Store triangle triples, indices into \a r_loops,  ((f->len - 2) * 3)
178  */
179 void BM_face_calc_tessellation(const BMFace *f, BMLoop **r_loops, unsigned int (*r_index)[3])
180 {
181         BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
182         BMLoop *l_iter;
183
184         if (f->len == 3) {
185                 *r_loops++ = (l_iter = l_first);
186                 *r_loops++ = (l_iter = l_iter->next);
187                 *r_loops++ = (         l_iter->next);
188
189                 r_index[0][0] = 0;
190                 r_index[0][1] = 1;
191                 r_index[0][2] = 2;
192         }
193         else if (f->len == 4) {
194                 *r_loops++ = (l_iter = l_first);
195                 *r_loops++ = (l_iter = l_iter->next);
196                 *r_loops++ = (l_iter = l_iter->next);
197                 *r_loops++ = (         l_iter->next);
198
199                 r_index[0][0] = 0;
200                 r_index[0][1] = 1;
201                 r_index[0][2] = 2;
202
203                 r_index[1][0] = 0;
204                 r_index[1][1] = 2;
205                 r_index[1][2] = 3;
206         }
207         else {
208                 float axis_mat[3][3];
209                 float (*projverts)[2] = BLI_array_alloca(projverts, f->len);
210                 int j;
211
212                 axis_dominant_v3_to_m3(axis_mat, f->no);
213
214                 j = 0;
215                 l_iter = l_first;
216                 do {
217                         mul_v2_m3v3(projverts[j], axis_mat, l_iter->v->co);
218                         r_loops[j] = l_iter;
219                         j++;
220                 } while ((l_iter = l_iter->next) != l_first);
221
222                 /* complete the loop */
223                 BLI_polyfill_calc((const float (*)[2])projverts, f->len, r_index);
224         }
225 }
226
227 /**
228  * get the area of the face
229  */
230 float BM_face_calc_area(BMFace *f)
231 {
232         BMLoop *l;
233         BMIter iter;
234         float (*verts)[3] = BLI_array_alloca(verts, f->len);
235         float area;
236         int i;
237
238         BM_ITER_ELEM_INDEX (l, &iter, f, BM_LOOPS_OF_FACE, i) {
239                 copy_v3_v3(verts[i], l->v->co);
240         }
241
242         if (f->len == 3) {
243                 area = area_tri_v3(verts[0], verts[1], verts[2]);
244         }
245         else if (f->len == 4) {
246                 area = area_quad_v3(verts[0], verts[1], verts[2], verts[3]);
247         }
248         else {
249                 float normal[3];
250                 calc_poly_normal(normal, verts, f->len);
251                 area = area_poly_v3(f->len, verts, normal);
252         }
253
254         return area;
255 }
256
257 /**
258  * compute the perimeter of an ngon
259  */
260 float BM_face_calc_perimeter(BMFace *f)
261 {
262         BMLoop *l_iter, *l_first;
263         float perimeter = 0.0f;
264
265         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
266         do {
267                 perimeter += len_v3v3(l_iter->v->co, l_iter->next->v->co);
268         } while ((l_iter = l_iter->next) != l_first);
269
270         return perimeter;
271 }
272
273 /**
274  * Compute a meaningful direction along the face (use for manipulator axis).
275  * \note result isnt normalized.
276  */
277 void BM_face_calc_plane(BMFace *f, float r_plane[3])
278 {
279         if (f->len == 3) {
280                 BMVert *verts[3];
281                 float lens[3];
282                 float difs[3];
283                 int  order[3] = {0, 1, 2};
284
285                 BM_face_as_array_vert_tri(f, verts);
286
287                 lens[0] = len_v3v3(verts[0]->co, verts[1]->co);
288                 lens[1] = len_v3v3(verts[1]->co, verts[2]->co);
289                 lens[2] = len_v3v3(verts[2]->co, verts[0]->co);
290
291                 /* find the shortest or the longest loop */
292                 difs[0] = fabsf(lens[1] - lens[2]);
293                 difs[1] = fabsf(lens[2] - lens[0]);
294                 difs[2] = fabsf(lens[0] - lens[1]);
295
296                 axis_sort_v3(difs, order);
297                 sub_v3_v3v3(r_plane, verts[order[0]]->co, verts[(order[0] + 1) % 3]->co);
298         }
299         else if (f->len == 4) {
300                 BMVert *verts[4];
301                 float vec[3], vec_a[3], vec_b[3];
302
303                 // BM_iter_as_array(NULL, BM_VERTS_OF_FACE, efa, (void **)verts, 4);
304                 BM_face_as_array_vert_quad(f, verts);
305
306                 sub_v3_v3v3(vec_a, verts[3]->co, verts[2]->co);
307                 sub_v3_v3v3(vec_b, verts[0]->co, verts[1]->co);
308                 add_v3_v3v3(r_plane, vec_a, vec_b);
309
310                 sub_v3_v3v3(vec_a, verts[0]->co, verts[3]->co);
311                 sub_v3_v3v3(vec_b, verts[1]->co, verts[2]->co);
312                 add_v3_v3v3(vec, vec_a, vec_b);
313                 /* use the biggest edge length */
314                 if (dot_v3v3(r_plane, r_plane) < dot_v3v3(vec, vec)) {
315                         copy_v3_v3(r_plane, vec);
316                 }
317         }
318         else {
319                 BMLoop *l_long  = BM_face_find_longest_loop(f);
320
321                 sub_v3_v3v3(r_plane, l_long->v->co, l_long->next->v->co);
322         }
323
324         normalize_v3(r_plane);
325 }
326
327 /**
328  * computes center of face in 3d.  uses center of bounding box.
329  */
330 void BM_face_calc_center_bounds(BMFace *f, float r_cent[3])
331 {
332         BMLoop *l_iter;
333         BMLoop *l_first;
334         float min[3], max[3];
335
336         INIT_MINMAX(min, max);
337
338         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
339         do {
340                 minmax_v3v3_v3(min, max, l_iter->v->co);
341         } while ((l_iter = l_iter->next) != l_first);
342
343         mid_v3_v3v3(r_cent, min, max);
344 }
345
346 /**
347  * computes the center of a face, using the mean average
348  */
349 void BM_face_calc_center_mean(BMFace *f, float r_cent[3])
350 {
351         BMLoop *l_iter, *l_first;
352
353         zero_v3(r_cent);
354
355         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
356         do {
357                 add_v3_v3(r_cent, l_iter->v->co);
358         } while ((l_iter = l_iter->next) != l_first);
359         mul_v3_fl(r_cent, 1.0f / (float) f->len);
360 }
361
362 /**
363  * computes the center of a face, using the mean average
364  * weighted by edge length
365  */
366 void BM_face_calc_center_mean_weighted(BMFace *f, float r_cent[3])
367 {
368         BMLoop *l_iter;
369         BMLoop *l_first;
370         float totw = 0.0f;
371         float w_prev;
372
373         zero_v3(r_cent);
374
375
376         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
377         w_prev = BM_edge_calc_length(l_iter->prev->e);
378         do {
379                 const float w_curr = BM_edge_calc_length(l_iter->e);
380                 const float w = (w_curr + w_prev);
381                 madd_v3_v3fl(r_cent, l_iter->v->co, w);
382                 totw += w;
383                 w_prev = w_curr;
384         } while ((l_iter = l_iter->next) != l_first);
385
386         if (totw != 0.0f)
387                 mul_v3_fl(r_cent, 1.0f / (float) totw);
388 }
389
390 /**
391  * COMPUTE POLY PLANE
392  *
393  * Projects a set polygon's vertices to
394  * a plane defined by the average
395  * of its edges cross products
396  */
397 void calc_poly_plane(float (*verts)[3], const int nverts)
398 {
399         
400         float avgc[3], norm[3], mag, avgn[3];
401         float *v1, *v2, *v3;
402         int i;
403         
404         if (nverts < 3)
405                 return;
406
407         zero_v3(avgn);
408         zero_v3(avgc);
409
410         for (i = 0; i < nverts; i++) {
411                 v1 = verts[i];
412                 v2 = verts[(i + 1) % nverts];
413                 v3 = verts[(i + 2) % nverts];
414                 normal_tri_v3(norm, v1, v2, v3);
415
416                 add_v3_v3(avgn, norm);
417         }
418
419         if (UNLIKELY(normalize_v3(avgn) == 0.0f)) {
420                 avgn[2] = 1.0f;
421         }
422         
423         for (i = 0; i < nverts; i++) {
424                 v1 = verts[i];
425                 mag = dot_v3v3(v1, avgn);
426                 madd_v3_v3fl(v1, avgn, -mag);
427         }
428 }
429
430 /**
431  * \brief BM LEGAL EDGES
432  *
433  * takes in a face and a list of edges, and sets to NULL any edge in
434  * the list that bridges a concave region of the face or intersects
435  * any of the faces's edges.
436  */
437 static void scale_edge_v2f(float v1[2], float v2[2], const float fac)
438 {
439         float mid[2];
440
441         mid_v2_v2v2(mid, v1, v2);
442
443         sub_v2_v2v2(v1, v1, mid);
444         sub_v2_v2v2(v2, v2, mid);
445
446         mul_v2_fl(v1, fac);
447         mul_v2_fl(v2, fac);
448
449         add_v2_v2v2(v1, v1, mid);
450         add_v2_v2v2(v2, v2, mid);
451 }
452
453 /**
454  * \brief POLY ROTATE PLANE
455  *
456  * Rotates a polygon so that it's
457  * normal is pointing towards the mesh Z axis
458  */
459 void poly_rotate_plane(const float normal[3], float (*verts)[3], const int nverts)
460 {
461         float mat[3][3];
462
463         if (axis_dominant_v3_to_m3(mat, normal)) {
464                 int i;
465                 for (i = 0; i < nverts; i++) {
466                         mul_m3_v3(mat, verts[i]);
467                 }
468         }
469 }
470
471 /**
472  * updates face and vertex normals incident on an edge
473  */
474 void BM_edge_normals_update(BMEdge *e)
475 {
476         BMIter iter;
477         BMFace *f;
478         
479         BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
480                 BM_face_normal_update(f);
481         }
482
483         BM_vert_normal_update(e->v1);
484         BM_vert_normal_update(e->v2);
485 }
486
487 /**
488  * update a vert normal (but not the faces incident on it)
489  */
490 void BM_vert_normal_update(BMVert *v)
491 {
492         /* TODO, we can normalize each edge only once, then compare with previous edge */
493
494         BMIter liter;
495         BMLoop *l;
496         float vec1[3], vec2[3], fac;
497         int len = 0;
498
499         zero_v3(v->no);
500
501         BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) {
502                 /* Same calculation used in BM_mesh_normals_update */
503                 sub_v3_v3v3(vec1, l->v->co, l->prev->v->co);
504                 sub_v3_v3v3(vec2, l->next->v->co, l->v->co);
505                 normalize_v3(vec1);
506                 normalize_v3(vec2);
507
508                 fac = saacos(-dot_v3v3(vec1, vec2));
509
510                 madd_v3_v3fl(v->no, l->f->no, fac);
511
512                 len++;
513         }
514
515         if (len) {
516                 normalize_v3(v->no);
517         }
518 }
519
520 void BM_vert_normal_update_all(BMVert *v)
521 {
522         BMIter iter;
523         BMFace *f;
524
525         BM_ITER_ELEM (f, &iter, v, BM_FACES_OF_VERT) {
526                 BM_face_normal_update(f);
527         }
528
529         BM_vert_normal_update(v);
530 }
531
532 /**
533  * \brief BMESH UPDATE FACE NORMAL
534  *
535  * Updates the stored normal for the
536  * given face. Requires that a buffer
537  * of sufficient length to store projected
538  * coordinates for all of the face's vertices
539  * is passed in as well.
540  */
541
542 void BM_face_calc_normal(const BMFace *f, float r_no[3])
543 {
544         BMLoop *l;
545
546         /* common cases first */
547         switch (f->len) {
548                 case 4:
549                 {
550                         const float *co1 = (l = BM_FACE_FIRST_LOOP(f))->v->co;
551                         const float *co2 = (l = l->next)->v->co;
552                         const float *co3 = (l = l->next)->v->co;
553                         const float *co4 = (l->next)->v->co;
554
555                         normal_quad_v3(r_no, co1, co2, co3, co4);
556                         break;
557                 }
558                 case 3:
559                 {
560                         const float *co1 = (l = BM_FACE_FIRST_LOOP(f))->v->co;
561                         const float *co2 = (l = l->next)->v->co;
562                         const float *co3 = (l->next)->v->co;
563
564                         normal_tri_v3(r_no, co1, co2, co3);
565                         break;
566                 }
567                 default:
568                 {
569                         bm_face_calc_poly_normal(f, r_no);
570                         break;
571                 }
572         }
573 }
574 void BM_face_normal_update(BMFace *f)
575 {
576         BM_face_calc_normal(f, f->no);
577 }
578
579 /* exact same as 'BM_face_calc_normal' but accepts vertex coords */
580 void BM_face_calc_normal_vcos(BMesh *bm, BMFace *f, float r_no[3],
581                               float const (*vertexCos)[3])
582 {
583         BMLoop *l;
584
585         /* must have valid index data */
586         BLI_assert((bm->elem_index_dirty & BM_VERT) == 0);
587         (void)bm;
588
589         /* common cases first */
590         switch (f->len) {
591                 case 4:
592                 {
593                         const float *co1 = vertexCos[BM_elem_index_get((l = BM_FACE_FIRST_LOOP(f))->v)];
594                         const float *co2 = vertexCos[BM_elem_index_get((l = l->next)->v)];
595                         const float *co3 = vertexCos[BM_elem_index_get((l = l->next)->v)];
596                         const float *co4 = vertexCos[BM_elem_index_get((l->next)->v)];
597
598                         normal_quad_v3(r_no, co1, co2, co3, co4);
599                         break;
600                 }
601                 case 3:
602                 {
603                         const float *co1 = vertexCos[BM_elem_index_get((l = BM_FACE_FIRST_LOOP(f))->v)];
604                         const float *co2 = vertexCos[BM_elem_index_get((l = l->next)->v)];
605                         const float *co3 = vertexCos[BM_elem_index_get((l->next)->v)];
606
607                         normal_tri_v3(r_no, co1, co2, co3);
608                         break;
609                 }
610                 case 0:
611                 {
612                         zero_v3(r_no);
613                         break;
614                 }
615                 default:
616                 {
617                         bm_face_calc_poly_normal_vertex_cos(f, r_no, vertexCos);
618                         break;
619                 }
620         }
621 }
622
623 /* exact same as 'BM_face_calc_normal' but accepts vertex coords */
624 void BM_face_calc_center_mean_vcos(BMesh *bm, BMFace *f, float r_cent[3],
625                                    float const (*vertexCos)[3])
626 {
627         /* must have valid index data */
628         BLI_assert((bm->elem_index_dirty & BM_VERT) == 0);
629         (void)bm;
630
631         bm_face_calc_poly_center_mean_vertex_cos(f, r_cent, vertexCos);
632 }
633
634 /**
635  * \brief Face Flip Normal
636  *
637  * Reverses the winding of a face.
638  * \note This updates the calculated normal.
639  */
640 void BM_face_normal_flip(BMesh *bm, BMFace *f)
641 {
642         bmesh_loop_reverse(bm, f);
643         negate_v3(f->no);
644 }
645
646 /* detects if two line segments cross each other (intersects).
647  * note, there could be more winding cases then there needs to be. */
648 static bool line_crosses_v2f(const float v1[2], const float v2[2], const float v3[2], const float v4[2])
649 {
650
651 #define GETMIN2_AXIS(a, b, ma, mb, axis)   \
652         {                                      \
653                 ma[axis] = min_ff(a[axis], b[axis]); \
654                 mb[axis] = max_ff(a[axis], b[axis]); \
655         } (void)0
656
657 #define GETMIN2(a, b, ma, mb)          \
658         {                                  \
659                 GETMIN2_AXIS(a, b, ma, mb, 0); \
660                 GETMIN2_AXIS(a, b, ma, mb, 1); \
661         } (void)0
662
663 #define EPS (FLT_EPSILON * 15)
664
665         int w1, w2, w3, w4, w5 /*, re */;
666         float mv1[2], mv2[2], mv3[2], mv4[2];
667         
668         /* now test winding */
669         w1 = testedgesidef(v1, v3, v2);
670         w2 = testedgesidef(v2, v4, v1);
671         w3 = !testedgesidef(v1, v2, v3);
672         w4 = testedgesidef(v3, v2, v4);
673         w5 = !testedgesidef(v3, v1, v4);
674         
675         if (w1 == w2 && w2 == w3 && w3 == w4 && w4 == w5) {
676                 return true;
677         }
678         
679         GETMIN2(v1, v2, mv1, mv2);
680         GETMIN2(v3, v4, mv3, mv4);
681         
682         /* do an interval test on the x and y axes */
683         /* first do x axis */
684         if (fabsf(v1[1] - v2[1]) < EPS &&
685             fabsf(v3[1] - v4[1]) < EPS &&
686             fabsf(v1[1] - v3[1]) < EPS)
687         {
688                 return (mv4[0] >= mv1[0] && mv3[0] <= mv2[0]);
689         }
690
691         /* now do y axis */
692         if (fabsf(v1[0] - v2[0]) < EPS &&
693             fabsf(v3[0] - v4[0]) < EPS &&
694             fabsf(v1[0] - v3[0]) < EPS)
695         {
696                 return (mv4[1] >= mv1[1] && mv3[1] <= mv2[1]);
697         }
698
699         return false;
700
701 #undef GETMIN2_AXIS
702 #undef GETMIN2
703 #undef EPS
704
705 }
706
707 /**
708  *  BM POINT IN FACE
709  *
710  * Projects co onto face f, and returns true if it is inside
711  * the face bounds.
712  *
713  * \note this uses a best-axis projection test,
714  * instead of projecting co directly into f's orientation space,
715  * so there might be accuracy issues.
716  */
717 bool BM_face_point_inside_test(BMFace *f, const float co[3])
718 {
719         int ax, ay;
720         float co2[2], cent[2] = {0.0f, 0.0f}, out[2] = {FLT_MAX * 0.5f, FLT_MAX * 0.5f};
721         BMLoop *l_iter;
722         BMLoop *l_first;
723         int crosses = 0;
724         float onepluseps = 1.0f + (float)FLT_EPSILON * 150.0f;
725         
726         if (dot_v3v3(f->no, f->no) <= FLT_EPSILON * 10)
727                 BM_face_normal_update(f);
728         
729         /* find best projection of face XY, XZ or YZ: barycentric weights of
730          * the 2d projected coords are the same and faster to compute
731          *
732          * this probably isn't all that accurate, but it has the advantage of
733          * being fast (especially compared to projecting into the face orientation)
734          */
735         axis_dominant_v3(&ax, &ay, f->no);
736
737         co2[0] = co[ax];
738         co2[1] = co[ay];
739         
740         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
741         do {
742                 cent[0] += l_iter->v->co[ax];
743                 cent[1] += l_iter->v->co[ay];
744         } while ((l_iter = l_iter->next) != l_first);
745         
746         mul_v2_fl(cent, 1.0f / (float)f->len);
747         
748         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
749         do {
750                 float v1[2], v2[2];
751                 
752                 v1[0] = (l_iter->prev->v->co[ax] - cent[0]) * onepluseps + cent[0];
753                 v1[1] = (l_iter->prev->v->co[ay] - cent[1]) * onepluseps + cent[1];
754                 
755                 v2[0] = (l_iter->v->co[ax] - cent[0]) * onepluseps + cent[0];
756                 v2[1] = (l_iter->v->co[ay] - cent[1]) * onepluseps + cent[1];
757                 
758                 crosses += line_crosses_v2f(v1, v2, co2, out) != 0;
759         } while ((l_iter = l_iter->next) != l_first);
760         
761         return crosses % 2 != 0;
762 }
763
764 /**
765  * \brief BMESH TRIANGULATE FACE
766  *
767  * Breaks all quads and ngons down to triangles.
768  * It uses polyfill for the ngons splitting, and
769  * the beautify operator when use_beauty is true.
770  *
771  * \param r_faces_new if non-null, must be an array of BMFace pointers,
772  * with a length equal to (f->len - 3). It will be filled with the new
773  * triangles (not including the original triangle).
774  *
775  * \note The number of faces is _almost_ always (f->len - 3),
776  *       However there may be faces that already occupying the
777  *       triangles we would make, so the caller must check \a r_faces_new_tot.
778  *
779  * \note use_tag tags new flags and edges.
780  */
781 void BM_face_triangulate(BMesh *bm, BMFace *f,
782                          BMFace **r_faces_new,
783                          int *r_faces_new_tot,
784                          MemArena *sf_arena,
785                          const int quad_method,
786                          const int ngon_method,
787                          const bool use_tag)
788 {
789         BMLoop *l_iter, *l_first, *l_new;
790         BMFace *f_new;
791         int orig_f_len = f->len;
792         int nf_i = 0;
793         BMEdge **edge_array;
794         int edge_array_len;
795         bool use_beauty = (ngon_method == MOD_TRIANGULATE_NGON_BEAUTY);
796
797         BLI_assert(BM_face_is_normal_valid(f));
798
799         /* ensure both are valid or NULL */
800         BLI_assert((r_faces_new == NULL) == (r_faces_new_tot == NULL));
801
802         if (f->len == 4) {
803                 BMLoop *l_v1, *l_v2;
804                 l_first = BM_FACE_FIRST_LOOP(f);
805
806                 switch (quad_method) {
807                         case MOD_TRIANGULATE_QUAD_FIXED:
808                         {
809                                 l_v1 = l_first;
810                                 l_v2 = l_first->next->next;
811                                 break;
812                         }
813                         case MOD_TRIANGULATE_QUAD_ALTERNATE:
814                         {
815                                 l_v1 = l_first->next;
816                                 l_v2 = l_first->prev;
817                                 break;
818                         }
819                         case MOD_TRIANGULATE_QUAD_SHORTEDGE:
820                         {
821                                 BMLoop *l_v3, *l_v4;
822                                 float d1, d2;
823
824                                 l_v1 = l_first;
825                                 l_v2 = l_first->next->next;
826                                 l_v3 = l_first->next;
827                                 l_v4 = l_first->prev;
828
829                                 d1 = len_squared_v3v3(l_v1->v->co, l_v2->v->co);
830                                 d2 = len_squared_v3v3(l_v3->v->co, l_v4->v->co);
831
832                                 if (d2 < d1) {
833                                         l_v1 = l_v3;
834                                         l_v2 = l_v4;
835                                 }
836                                 break;
837                         }
838                         case MOD_TRIANGULATE_QUAD_BEAUTY:
839                         default:
840                         {
841                                 BMLoop *l_v3, *l_v4;
842                                 float cost;
843
844                                 l_v1 = l_first->next;
845                                 l_v2 = l_first->next->next;
846                                 l_v3 = l_first->prev;
847                                 l_v4 = l_first;
848
849                                 cost = BM_verts_calc_rotate_beauty(l_v1->v, l_v2->v, l_v3->v, l_v4->v, 0, 0);
850
851                                 if (cost < 0.0f) {
852                                         l_v1 = l_v4;
853                                         //l_v2 = l_v2;
854                                 }
855                                 else {
856                                         //l_v1 = l_v1;
857                                         l_v2 = l_v3;
858                                 }
859                                 break;
860                         }
861                 }
862
863                 f_new = BM_face_split(bm, f, l_v1, l_v2, &l_new, NULL, false);
864                 copy_v3_v3(f_new->no, f->no);
865
866                 if (use_tag) {
867                         BM_elem_flag_enable(l_new->e, BM_ELEM_TAG);
868                         BM_elem_flag_enable(f_new, BM_ELEM_TAG);
869                 }
870
871                 if (r_faces_new) {
872                         r_faces_new[nf_i++] = f_new;
873                 }
874         }
875         else if (f->len > 4) {
876
877                 float axis_mat[3][3];
878                 float (*projverts)[2] = BLI_array_alloca(projverts, f->len);
879                 BMLoop **loops = BLI_array_alloca(loops, f->len);
880                 unsigned int (*tris)[3] = BLI_array_alloca(tris, f->len);
881                 const int totfilltri = f->len - 2;
882                 const int last_tri = f->len - 3;
883                 int i;
884
885                 axis_dominant_v3_to_m3(axis_mat, f->no);
886
887                 for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f); i < f->len; i++, l_iter = l_iter->next) {
888                         loops[i] = l_iter;
889                         mul_v2_m3v3(projverts[i], axis_mat, l_iter->v->co);
890                 }
891
892                 BLI_polyfill_calc_arena((const float (*)[2])projverts, f->len, tris,
893                                         sf_arena);
894
895                 if (use_beauty) {
896                         edge_array = BLI_array_alloca(edge_array, orig_f_len - 3);
897                         edge_array_len = 0;
898                 }
899
900                 /* loop over calculated triangles and create new geometry */
901                 for (i = 0; i < totfilltri; i++) {
902                         /* the order is reverse, otherwise the normal is flipped */
903                         BMLoop *l_tri[3] = {
904                             loops[tris[i][2]],
905                             loops[tris[i][1]],
906                             loops[tris[i][0]]};
907
908                         BMVert *v_tri[3] = {
909                             l_tri[0]->v,
910                             l_tri[1]->v,
911                             l_tri[2]->v};
912
913                         f_new = BM_face_create_verts(bm, v_tri, 3, f, false, true);
914                         l_new = BM_FACE_FIRST_LOOP(f_new);
915
916                         BLI_assert(v_tri[0] == l_new->v);
917
918                         /* copy CD data */
919                         BM_elem_attrs_copy(bm, bm, l_tri[0], l_new);
920                         BM_elem_attrs_copy(bm, bm, l_tri[1], l_new->next);
921                         BM_elem_attrs_copy(bm, bm, l_tri[2], l_new->prev);
922
923                         /* add all but the last face which is swapped and removed (below) */
924                         if (i != last_tri) {
925                                 if (use_tag) {
926                                         BM_elem_flag_enable(f_new, BM_ELEM_TAG);
927                                 }
928                                 if (r_faces_new) {
929                                         r_faces_new[nf_i++] = f_new;
930                                 }
931                         }
932
933                         /* we know any edge that we create and _isnt_ */
934                         if (use_beauty || use_tag) {
935                                 /* new faces loops */
936                                 l_iter = l_first = l_new;
937                                 do {
938                                         BMEdge *e = l_iter->e;
939                                         /* confusing! if its not a boundary now, we know it will be later
940                                          * since this will be an edge of one of the new faces which we're in the middle of creating */
941                                         bool is_new_edge = (l_iter == l_iter->radial_next);
942
943                                         if (is_new_edge) {
944                                                 if (use_beauty) {
945                                                         edge_array[edge_array_len] = e;
946                                                         edge_array_len++;
947                                                 }
948
949                                                 if (use_tag) {
950                                                         BM_elem_flag_enable(e, BM_ELEM_TAG);
951
952                                                 }
953                                         }
954                                         /* note, never disable tag's */
955                                 } while ((l_iter = l_iter->next) != l_first);
956                         }
957                 }
958
959                 if ((!use_beauty) || (!r_faces_new)) {
960                         /* we can't delete the real face, because some of the callers expect it to remain valid.
961                          * so swap data and delete the last created tri */
962                         bmesh_face_swap_data(f, f_new);
963                         BM_face_kill(bm, f_new);
964                 }
965
966                 if (use_beauty) {
967                         BLI_assert(edge_array_len <= orig_f_len - 3);
968
969                         BM_mesh_beautify_fill(bm, edge_array, edge_array_len, 0, 0, 0, 0);
970
971                         if (r_faces_new) {
972                                 /* beautify deletes and creates new faces
973                                  * we need to re-populate the r_faces_new array
974                                  * with the new faces
975                                  */
976                                 int i;
977
978
979 #define FACE_USED_TEST(f) (BM_elem_index_get(f) == -2)
980 #define FACE_USED_SET(f)   BM_elem_index_set(f,    -2)
981
982                                 nf_i = 0;
983                                 for (i = 0; i < edge_array_len; i++) {
984                                         BMFace *f_a, *f_b;
985                                         BMEdge *e = edge_array[i];
986 #ifndef NDEBUG
987                                         const bool ok = BM_edge_face_pair(e, &f_a, &f_b);
988                                         BLI_assert(ok);
989 #else
990                                         BM_edge_face_pair(e, &f_a, &f_b);
991 #endif
992
993                                         if (FACE_USED_TEST(f_a) == false) {
994                                                 FACE_USED_SET(f_a);
995
996                                                 if (nf_i < edge_array_len) {
997                                                         r_faces_new[nf_i++] = f_a;
998                                                 }
999                                                 else {
1000                                                         f_new = f_a;
1001                                                         break;
1002                                                 }
1003                                         }
1004
1005                                         if (FACE_USED_TEST(f_b) == false) {
1006                                                 FACE_USED_SET(f_b);
1007
1008                                                 if (nf_i < edge_array_len) {
1009                                                         r_faces_new[nf_i++] = f_b;
1010                                                 }
1011                                                 else {
1012                                                         f_new = f_b;
1013                                                         break;
1014                                                 }
1015                                         }
1016                                 }
1017
1018 #undef FACE_USED_TEST
1019 #undef FACE_USED_SET
1020
1021                                 /* nf_i doesn't include the last face */
1022                                 BLI_assert(nf_i <= orig_f_len - 3);
1023
1024                                 /* we can't delete the real face, because some of the callers expect it to remain valid.
1025                                  * so swap data and delete the last created tri */
1026                                 bmesh_face_swap_data(f, f_new);
1027                                 BM_face_kill(bm, f_new);
1028                         }
1029                 }
1030         }
1031
1032         if (r_faces_new_tot) {
1033                 *r_faces_new_tot = nf_i;
1034         }
1035 }
1036
1037 /**
1038  * each pair of loops defines a new edge, a split.  this function goes
1039  * through and sets pairs that are geometrically invalid to null.  a
1040  * split is invalid, if it forms a concave angle or it intersects other
1041  * edges in the face, or it intersects another split.  in the case of
1042  * intersecting splits, only the first of the set of intersecting
1043  * splits survives
1044  */
1045 void BM_face_legal_splits(BMFace *f, BMLoop *(*loops)[2], int len)
1046 {
1047         const int len2 = len * 2;
1048         BMLoop *l;
1049         float v1[2], v2[2], v3[2], mid[2], *p1, *p2, *p3, *p4;
1050         float out[2] = {-FLT_MAX, -FLT_MAX};
1051         float axis_mat[3][3];
1052         float (*projverts)[2] = BLI_array_alloca(projverts, f->len);
1053         float (*edgeverts)[2] = BLI_array_alloca(edgeverts, len2);
1054         float fac1 = 1.0000001f, fac2 = 0.9f; //9999f; //0.999f;
1055         int i, j, a = 0, clen;
1056
1057         BLI_assert(BM_face_is_normal_valid(f));
1058
1059         axis_dominant_v3_to_m3(axis_mat, f->no);
1060
1061         for (i = 0, l = BM_FACE_FIRST_LOOP(f); i < f->len; i++, l = l->next) {
1062                 BM_elem_index_set(l, i); /* set_loop */
1063                 mul_v2_m3v3(projverts[i], axis_mat, l->v->co);
1064
1065                 out[0] = max_ff(out[0], projverts[i][0]);
1066                 out[1] = max_ff(out[1], projverts[i][1]);
1067         }
1068         
1069         /* ensure we are well outside the face bounds (value is arbitrary) */
1070         add_v2_fl(out, 1.0f);
1071
1072         for (i = 0; i < len; i++) {
1073                 copy_v2_v2(edgeverts[a + 0], projverts[BM_elem_index_get(loops[i][0])]);
1074                 copy_v2_v2(edgeverts[a + 1], projverts[BM_elem_index_get(loops[i][1])]);
1075                 scale_edge_v2f(edgeverts[a + 0], edgeverts[a + 1], fac2);
1076                 a += 2;
1077         }
1078
1079         /* do convexity test */
1080         for (i = 0; i < len; i++) {
1081                 copy_v2_v2(v2, edgeverts[i * 2 + 0]);
1082                 copy_v2_v2(v3, edgeverts[i * 2 + 1]);
1083
1084                 mid_v2_v2v2(mid, v2, v3);
1085                 
1086                 clen = 0;
1087                 for (j = 0; j < f->len; j++) {
1088                         p1 = projverts[j];
1089                         p2 = projverts[(j + 1) % f->len];
1090                         
1091 #if 0
1092                         copy_v2_v2(v1, p1);
1093                         copy_v2_v2(v2, p2);
1094
1095                         scale_edge_v2f(v1, v2, fac1);
1096                         if (line_crosses_v2f(v1, v2, mid, out)) {
1097                                 clen++;
1098                         }
1099 #else
1100                         if (line_crosses_v2f(p1, p2, mid, out)) {
1101                                 clen++;
1102                         }
1103 #endif
1104                 }
1105
1106                 if (clen % 2 == 0) {
1107                         loops[i][0] = NULL;
1108                 }
1109         }
1110
1111         /* do line crossing tests */
1112         for (i = 0; i < f->len; i++) {
1113                 p1 = projverts[i];
1114                 p2 = projverts[(i + 1) % f->len];
1115                 
1116                 copy_v2_v2(v1, p1);
1117                 copy_v2_v2(v2, p2);
1118
1119                 scale_edge_v2f(v1, v2, fac1);
1120
1121                 for (j = 0; j < len; j++) {
1122                         if (!loops[j][0]) {
1123                                 continue;
1124                         }
1125
1126                         p3 = edgeverts[j * 2];
1127                         p4 = edgeverts[j * 2 + 1];
1128
1129                         if (line_crosses_v2f(v1, v2, p3, p4)) {
1130                                 loops[j][0] = NULL;
1131                         }
1132                 }
1133         }
1134
1135         for (i = 0; i < len; i++) {
1136                 for (j = 0; j < len; j++) {
1137                         if (j != i && loops[i][0] && loops[j][0]) {
1138                                 p1 = edgeverts[i * 2];
1139                                 p2 = edgeverts[i * 2 + 1];
1140                                 p3 = edgeverts[j * 2];
1141                                 p4 = edgeverts[j * 2 + 1];
1142
1143                                 copy_v2_v2(v1, p1);
1144                                 copy_v2_v2(v2, p2);
1145
1146                                 scale_edge_v2f(v1, v2, fac1);
1147
1148                                 if (line_crosses_v2f(v1, v2, p3, p4)) {
1149                                         loops[i][0] = NULL;
1150                                 }
1151                         }
1152                 }
1153         }
1154 }
1155
1156
1157 /**
1158  * Small utility functions for fast access
1159  *
1160  * faster alternative to:
1161  *  BM_iter_as_array(bm, BM_VERTS_OF_FACE, f, (void **)v, 3);
1162  */
1163 void BM_face_as_array_vert_tri(BMFace *f, BMVert *r_verts[3])
1164 {
1165         BMLoop *l = BM_FACE_FIRST_LOOP(f);
1166
1167         BLI_assert(f->len == 3);
1168
1169         r_verts[0] = l->v; l = l->next;
1170         r_verts[1] = l->v; l = l->next;
1171         r_verts[2] = l->v;
1172 }
1173
1174 /**
1175  * faster alternative to:
1176  *  BM_iter_as_array(bm, BM_VERTS_OF_FACE, f, (void **)v, 4);
1177  */
1178 void BM_face_as_array_vert_quad(BMFace *f, BMVert *r_verts[4])
1179 {
1180         BMLoop *l = BM_FACE_FIRST_LOOP(f);
1181
1182         BLI_assert(f->len == 4);
1183
1184         r_verts[0] = l->v; l = l->next;
1185         r_verts[1] = l->v; l = l->next;
1186         r_verts[2] = l->v; l = l->next;
1187         r_verts[3] = l->v;
1188 }
1189
1190
1191 /**
1192  * Small utility functions for fast access
1193  *
1194  * faster alternative to:
1195  *  BM_iter_as_array(bm, BM_LOOPS_OF_FACE, f, (void **)l, 3);
1196  */
1197 void BM_face_as_array_loop_tri(BMFace *f, BMLoop *r_loops[3])
1198 {
1199         BMLoop *l = BM_FACE_FIRST_LOOP(f);
1200
1201         BLI_assert(f->len == 3);
1202
1203         r_loops[0] = l; l = l->next;
1204         r_loops[1] = l; l = l->next;
1205         r_loops[2] = l;
1206 }
1207
1208 /**
1209  * faster alternative to:
1210  *  BM_iter_as_array(bm, BM_LOOPS_OF_FACE, f, (void **)l, 4);
1211  */
1212 void BM_face_as_array_loop_quad(BMFace *f, BMLoop *r_loops[4])
1213 {
1214         BMLoop *l = BM_FACE_FIRST_LOOP(f);
1215
1216         BLI_assert(f->len == 4);
1217
1218         r_loops[0] = l; l = l->next;
1219         r_loops[1] = l; l = l->next;
1220         r_loops[2] = l; l = l->next;
1221         r_loops[3] = l;
1222 }
1223
1224
1225 /**
1226  * \brief BM_bmesh_calc_tessellation get the looptris and its number from a certain bmesh
1227  * \param looptris
1228  *
1229  * \note \a looptris  Must be pre-allocated to at least the size of given by: poly_to_tri_count
1230  */
1231 void BM_bmesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptris_tot)
1232 {
1233         /* use this to avoid locking pthread for _every_ polygon
1234          * and calling the fill function */
1235 #define USE_TESSFACE_SPEEDUP
1236
1237         /* this assumes all faces can be scan-filled, which isn't always true,
1238          * worst case we over alloc a little which is acceptable */
1239 #ifndef NDEBUG
1240         const int looptris_tot = poly_to_tri_count(bm->totface, bm->totloop);
1241 #endif
1242
1243         BMIter iter;
1244         BMFace *efa;
1245         int i = 0;
1246
1247         MemArena *arena = NULL;
1248
1249         BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) {
1250                 /* don't consider two-edged faces */
1251                 if (UNLIKELY(efa->len < 3)) {
1252                         /* do nothing */
1253                 }
1254
1255 #ifdef USE_TESSFACE_SPEEDUP
1256
1257                 /* no need to ensure the loop order, we know its ok */
1258
1259                 else if (efa->len == 3) {
1260 #if 0
1261                         int j;
1262                         BM_ITER_ELEM_INDEX (l, &liter, efa, BM_LOOPS_OF_FACE, j) {
1263                                 looptris[i][j] = l;
1264                         }
1265                         i += 1;
1266 #else
1267                         /* more cryptic but faster */
1268                         BMLoop *l;
1269                         BMLoop **l_ptr = looptris[i++];
1270                         l_ptr[0] = l = BM_FACE_FIRST_LOOP(efa);
1271                         l_ptr[1] = l = l->next;
1272                         l_ptr[2] = l->next;
1273 #endif
1274                 }
1275                 else if (efa->len == 4) {
1276 #if 0
1277                         BMLoop *ltmp[4];
1278                         int j;
1279                         BLI_array_grow_items(looptris, 2);
1280                         BM_ITER_ELEM_INDEX (l, &liter, efa, BM_LOOPS_OF_FACE, j) {
1281                                 ltmp[j] = l;
1282                         }
1283
1284                         looptris[i][0] = ltmp[0];
1285                         looptris[i][1] = ltmp[1];
1286                         looptris[i][2] = ltmp[2];
1287                         i += 1;
1288
1289                         looptris[i][0] = ltmp[0];
1290                         looptris[i][1] = ltmp[2];
1291                         looptris[i][2] = ltmp[3];
1292                         i += 1;
1293 #else
1294                         /* more cryptic but faster */
1295                         BMLoop *l;
1296                         BMLoop **l_ptr_a = looptris[i++];
1297                         BMLoop **l_ptr_b = looptris[i++];
1298                         (l_ptr_a[0] = l_ptr_b[0] = l = BM_FACE_FIRST_LOOP(efa));
1299                         (l_ptr_a[1]              = l = l->next);
1300                         (l_ptr_a[2] = l_ptr_b[1] = l = l->next);
1301                         (             l_ptr_b[2] = l->next);
1302 #endif
1303                 }
1304
1305 #endif /* USE_TESSFACE_SPEEDUP */
1306
1307                 else {
1308                         int j;
1309
1310                         BMLoop *l_iter;
1311                         BMLoop *l_first;
1312                         BMLoop **l_arr;
1313
1314                         float axis_mat[3][3];
1315                         float (*projverts)[2];
1316                         unsigned int (*tris)[3];
1317
1318                         const int totfilltri = efa->len - 2;
1319
1320                         if (UNLIKELY(arena == NULL)) {
1321                                 arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
1322                         }
1323
1324                         tris = BLI_memarena_alloc(arena, sizeof(*tris) * totfilltri);
1325                         l_arr = BLI_memarena_alloc(arena, sizeof(*l_arr) * efa->len);
1326                         projverts = BLI_memarena_alloc(arena, sizeof(*projverts) * efa->len);
1327
1328                         axis_dominant_v3_to_m3(axis_mat, efa->no);
1329
1330                         j = 0;
1331                         l_iter = l_first = BM_FACE_FIRST_LOOP(efa);
1332                         do {
1333                                 l_arr[j] = l_iter;
1334                                 mul_v2_m3v3(projverts[j], axis_mat, l_iter->v->co);
1335                                 j++;
1336                         } while ((l_iter = l_iter->next) != l_first);
1337
1338                         BLI_polyfill_calc_arena((const float (*)[2])projverts, efa->len, tris, arena);
1339
1340                         for (j = 0; j < totfilltri; j++) {
1341                                 BMLoop **l_ptr = looptris[i++];
1342                                 unsigned int *tri = tris[j];
1343
1344                                 l_ptr[0] = l_arr[tri[2]];
1345                                 l_ptr[1] = l_arr[tri[1]];
1346                                 l_ptr[2] = l_arr[tri[0]];
1347                         }
1348
1349                         BLI_memarena_clear(arena);
1350                 }
1351         }
1352
1353         if (arena) {
1354                 BLI_memarena_free(arena);
1355                 arena = NULL;
1356         }
1357
1358         *r_looptris_tot = i;
1359
1360         BLI_assert(i <= looptris_tot);
1361
1362 #undef USE_TESSFACE_SPEEDUP
1363
1364 }