← Back to branch summary

~ubuntu-branches/ubuntu/utopic/blender/utopic-proposed

« back to all changes in this revision

Viewing changes to source/blender/bmesh/operators/bmo_connect_nonplanar.c

  • Committer: Package Import Robot
  • Author(s): Matthias Klose
  • Date: 2014-02-19 11:24:23 UTC
  • mfrom: (14.2.23 sid)
  • Revision ID: package-import@ubuntu.com-20140219112423-rkmaz2m7ha06d4tk
Tags: 2.69-3ubuntu1
* Merge with Debian; remaining changes:
  - Configure without OpenImageIO on armhf, as it is not available on
    Ubuntu.

Show diffs side-by-side

added added

removed removed

Lines of Context:
source/blender/bmesh/operators/bmo_connect_nonplanar.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): Campbell Barton
 
19
 *
 
20
 * ***** END GPL LICENSE BLOCK *****
 
21
 */
 
22
 
 
23
/** \file blender/bmesh/operators/bmo_connect_nonplanar.c
 
24
 *  \ingroup bmesh
 
25
 *
 
26
 * Connect verts non-planer faces iteratively (splits faces).
 
27
 */
 
28
 
 
29
#include "MEM_guardedalloc.h"
 
30
 
 
31
#include "BLI_math.h"
 
32
#include "BLI_utildefines.h"
 
33
#include "BLI_alloca.h"
 
34
#include "BLI_linklist_stack.h"
 
35
 
 
36
#include "bmesh.h"
 
37
 
 
38
#include "intern/bmesh_operators_private.h" /* own include */
 
39
 
 
40
#define EDGE_OUT        (1 << 0)
 
41
#define FACE_OUT        (1 << 1)
 
42
 
 
43
/**
 
44
 * Calculates the face subset normal.
 
45
 */
 
46
static bool bm_face_subset_calc_normal(BMLoop *l_first, BMLoop *l_last, float r_no[3])
 
47
{
 
48
        float const *v_prev, *v_curr;
 
49
 
 
50
        /* Newell's Method */
 
51
        BMLoop *l_iter = l_first;
 
52
        BMLoop *l_term = l_last->next;
 
53
 
 
54
        zero_v3(r_no);
 
55
 
 
56
        v_prev = l_last->v->co;
 
57
        do {
 
58
                v_curr = l_iter->v->co;
 
59
                add_newell_cross_v3_v3v3(r_no, v_prev, v_curr);
 
60
                v_prev = v_curr;
 
61
        } while ((l_iter = l_iter->next) != l_term);
 
62
 
 
63
        return (normalize_v3(r_no) != 0.0f);
 
64
}
 
65
 
 
66
/**
 
67
 * Calculates how non-planar the face subset is.
 
68
 */
 
69
static float bm_face_subset_calc_planar(BMLoop *l_first, BMLoop *l_last, const float no[3])
 
70
{
 
71
        float axis_mat[3][3];
 
72
        float z_prev, z_curr;
 
73
        float delta_z = 0.0f;
 
74
 
 
75
        /* Newell's Method */
 
76
        BMLoop *l_iter = l_first;
 
77
        BMLoop *l_term = l_last->next;
 
78
 
 
79
        axis_dominant_v3_to_m3(axis_mat, no);
 
80
 
 
81
        z_prev = dot_m3_v3_row_z(axis_mat, l_last->v->co);
 
82
        do {
 
83
                z_curr = dot_m3_v3_row_z(axis_mat, l_iter->v->co);
 
84
                delta_z += fabsf(z_curr - z_prev);
 
85
                z_prev = z_curr;
 
86
        } while ((l_iter = l_iter->next) != l_term);
 
87
 
 
88
        return delta_z;
 
89
}
 
90
 
 
91
static bool bm_face_split_find(BMFace *f, BMVert *v_pair[2], float *r_angle)
 
92
{
 
93
        BMLoop *l_iter, *l_first;
 
94
        BMLoop **l_arr = BLI_array_alloca(l_arr, f->len);
 
95
        const unsigned int f_len = f->len;
 
96
        unsigned int i_a, i_b;
 
97
        bool found = false;
 
98
 
 
99
        /* angle finding */
 
100
        float err_best = FLT_MAX;
 
101
        float angle_best = FLT_MAX;
 
102
 
 
103
        l_iter = l_first = BM_FACE_FIRST_LOOP(f);
 
104
        i_a = 0;
 
105
        do {
 
106
                l_arr[i_a++] = l_iter;
 
107
        } while ((l_iter = l_iter->next) != l_first);
 
108
 
 
109
        /* now for the big search, O(N^2), however faces normally aren't so large */
 
110
        for (i_a = 0; i_a < f_len; i_a++) {
 
111
                BMLoop *l_a = l_arr[i_a];
 
112
                for (i_b = i_a + 2; i_b < f_len; i_b++) {
 
113
                        BMLoop *l_b = l_arr[i_b];
 
114
                        /* check these are not touching
 
115
                         * (we could be smarter here) */
 
116
                        if ((l_a->next != l_b) &&
 
117
                            (l_a->prev != l_b))
 
118
                        {
 
119
                                /* first calculate normals */
 
120
                                float no_a[3], no_b[3];
 
121
 
 
122
                                if (bm_face_subset_calc_normal(l_a, l_b, no_a) &&
 
123
                                    bm_face_subset_calc_normal(l_b, l_a, no_b))
 
124
                                {
 
125
                                        const float err_a = bm_face_subset_calc_planar(l_a, l_b, no_a);
 
126
                                        const float err_b = bm_face_subset_calc_planar(l_b, l_a, no_b);
 
127
                                        const float err_test = err_a + err_b;
 
128
 
 
129
                                        if (err_test < err_best) {
 
130
                                                /* check we're legal (we could batch this) */
 
131
                                                BMLoop *l_split[2] = {l_a, l_b};
 
132
                                                BM_face_legal_splits(f, &l_split, 1);
 
133
                                                if (l_split[0]) {
 
134
                                                        err_best = err_test;
 
135
                                                        v_pair[0] = l_a->v;
 
136
                                                        v_pair[1] = l_b->v;
 
137
 
 
138
                                                        angle_best = angle_normalized_v3v3(no_a, no_b);
 
139
                                                        found = true;
 
140
                                                }
 
141
                                        }
 
142
                                }
 
143
                        }
 
144
                }
 
145
        }
 
146
 
 
147
        *r_angle = angle_best;
 
148
 
 
149
        return found;
 
150
 
 
151
 
 
152
}
 
153
 
 
154
static bool bm_face_split_by_angle(BMesh *bm, BMFace *f, BMFace *r_f_pair[2], const float angle_limit)
 
155
{
 
156
        BMVert *v_pair[2];
 
157
        float angle;
 
158
 
 
159
        if (bm_face_split_find(f, v_pair, &angle) && (angle > angle_limit)) {
 
160
                BMFace *f_new;
 
161
                BMLoop *l_new;
 
162
                f_new = BM_face_split(bm, f, v_pair[0], v_pair[1], &l_new, NULL, false);
 
163
                if (f_new) {
 
164
                        r_f_pair[0] = f;
 
165
                        r_f_pair[1] = f_new;
 
166
 
 
167
                        BMO_elem_flag_enable(bm, f, FACE_OUT);
 
168
                        BMO_elem_flag_enable(bm, f_new, FACE_OUT);
 
169
                        BMO_elem_flag_enable(bm, l_new->e, EDGE_OUT);
 
170
                        return true;
 
171
                }
 
172
        }
 
173
 
 
174
        return false;
 
175
 
 
176
}
 
177
 
 
178
void bmo_connect_verts_nonplanar_exec(BMesh *bm, BMOperator *op)
 
179
{
 
180
        BMOIter siter;
 
181
        BMFace *f;
 
182
        int totface = 0, totloop = 0;
 
183
        BLI_LINKSTACK_DECLARE(fstack, BMFace *);
 
184
 
 
185
        const float angle_limit = BMO_slot_float_get(op->slots_in, "angle_limit");
 
186
 
 
187
 
 
188
        BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) {
 
189
                if (f->len > 3) {
 
190
                        totface += 1;
 
191
                        totloop += f->len;
 
192
                }
 
193
        }
 
194
 
 
195
        if (totface == 0) {
 
196
                return;
 
197
        }
 
198
 
 
199
        BLI_LINKSTACK_INIT(fstack);
 
200
 
 
201
        BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) {
 
202
                if (f->len > 3) {
 
203
                        BLI_LINKSTACK_PUSH(fstack, f);
 
204
                }
 
205
        }
 
206
 
 
207
        while ((f = BLI_LINKSTACK_POP(fstack))) {
 
208
                BMFace *f_pair[2];
 
209
                if (bm_face_split_by_angle(bm, f, f_pair, angle_limit)) {
 
210
                        int j;
 
211
                        for (j = 0; j < 2; j++) {
 
212
                                BM_face_normal_update(f_pair[j]);
 
213
                                if (f_pair[j]->len > 3) {
 
214
                                        BLI_LINKSTACK_PUSH(fstack, f_pair[j]);
 
215
                                }
 
216
                        }
 
217
                }
 
218
        }
 
219
 
 
220
        BLI_LINKSTACK_FREE(fstack);
 
221
 
 
222
        BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT);
 
223
        BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_OUT);
 
224
}