1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
|
/*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software Foundation,
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/
/** \file
* \ingroup bmesh
*
* Main functions for boolean on a BMesh (used by the tool and modifier)
*/
#include "MEM_guardedalloc.h"
#include "BLI_boolean.h"
#include "BLI_math.h"
#include "bmesh.h"
#include "bmesh_boolean.h"
/* Make a a triangle mesh for input to the Boolean function.
* We take only take triangles from faces f for which test_fn(f, user_data) returns 'side'.
* Caller must call free_trimesh_input when done with the returned value. */
static Boolean_trimesh_input *trimesh_input_from_bm(BMesh *bm,
struct BMLoop *(*looptris)[3],
const int looptris_tot,
int (*(test_fn))(BMFace *f, void *user_data),
void *user_data,
int side)
{
int i, in_v_index, in_t_index, bmv_index, looptri_index, tot_in_vert, tot_in_tri;
Boolean_trimesh_input *trimesh;
int *bmv_to_v, *v_to_bmv, *t_to_looptri;
BMFace *f;
BM_mesh_elem_index_ensure(bm, BM_VERT | BM_FACE);
BM_mesh_elem_table_ensure(bm, BM_VERT | BM_FACE);
trimesh = MEM_mallocN(sizeof(*trimesh), __func__);
bmv_to_v = MEM_malloc_arrayN(bm->totvert, sizeof(int), __func__);
v_to_bmv = MEM_malloc_arrayN(bm->totvert, sizeof(int), __func__);
t_to_looptri = MEM_malloc_arrayN(looptris_tot, sizeof(int), __func__);
for (i = 0; i < bm->totvert; i++) {
bmv_to_v[i] = -1;
v_to_bmv[i] = -1;
}
in_v_index = 0;
tot_in_tri = 0;
for (looptri_index = 0; looptri_index < looptris_tot; looptri_index++) {
f = looptris[looptri_index][0]->f;
if (test_fn(f, user_data) == side) {
t_to_looptri[tot_in_tri++] = looptri_index;
for (i = 0; i < 3; i++) {
bmv_index = BM_elem_index_get(looptris[looptri_index][i]->v);
if (bmv_to_v[bmv_index] == -1) {
v_to_bmv[in_v_index] = bmv_index;
bmv_to_v[bmv_index] = in_v_index;
in_v_index++;
}
}
}
}
tot_in_vert = in_v_index;
trimesh->vert_len = tot_in_vert;
trimesh->tri_len = tot_in_tri;
trimesh->vert_coord = MEM_malloc_arrayN(tot_in_vert, sizeof(trimesh->vert_coord[0]), __func__);
trimesh->tri = MEM_malloc_arrayN(tot_in_tri, sizeof(trimesh->tri[0]), __func__);
for (in_v_index = 0; in_v_index < tot_in_vert; in_v_index++) {
bmv_index = v_to_bmv[in_v_index];
BMVert *bmv = BM_vert_at_index(bm, bmv_index);
copy_v3_v3(trimesh->vert_coord[in_v_index], bmv->co);
}
for (in_t_index = 0; in_t_index < tot_in_tri; in_t_index++) {
looptri_index = t_to_looptri[in_t_index];
for (i = 0; i < 3; i++) {
bmv_index = BM_elem_index_get(looptris[looptri_index][i]->v);
BLI_assert(bmv_to_v[bmv_index] != -1);
trimesh->tri[in_t_index][i] = bmv_to_v[bmv_index];
}
}
MEM_freeN(bmv_to_v);
MEM_freeN(v_to_bmv);
MEM_freeN(t_to_looptri);
return trimesh;
}
static void free_trimesh_input(Boolean_trimesh_input *in)
{
MEM_freeN(in->vert_coord);
MEM_freeN(in->tri);
MEM_freeN(in);
}
static void apply_trimesh_output_to_bmesh(BMesh *bm, Boolean_trimesh_output *out)
{
/* For now, for testing, just create new BMesh elements for returned subdivided mesh and kill old
* mesh. */
int v, t;
BMIter iter;
BMVert *bmv, *bmv_next;
BM_ITER_MESH_MUTABLE (bmv, bmv_next, &iter, bm, BM_VERTS_OF_MESH) {
BM_vert_kill(bm, bmv);
}
if (out->vert_len > 0 && out->tri_len > 0) {
BMVert **new_bmv = MEM_malloc_arrayN(out->vert_len, sizeof(BMVert *), __func__);
for (v = 0; v < out->vert_len; v++) {
new_bmv[v] = BM_vert_create(bm, out->vert_coord[v], NULL, BM_CREATE_NOP);
}
for (t = 0; t < out->tri_len; t++) {
BMVert *v0 = new_bmv[out->tri[t][0]];
BMVert *v1 = new_bmv[out->tri[t][1]];
BMVert *v2 = new_bmv[out->tri[t][2]];
BM_face_create_quad_tri(bm, v0, v1, v2, NULL, NULL, BM_CREATE_NOP);
}
MEM_freeN(new_bmv);
}
}
/*
* Perform the boolean operation specified by boolean_mode on the mesh bm.
* The inputs to the boolean operation are either one submesh (if use_self is true),
* or two submeshes. The submeshes are specified by providing a test_fn which takes
* a face and the supplied user_data and says with 'side' of the boolean operation
* that face is for: 0 for the first side (side A), 1 for the second side (side B),
* and -1 if the face is to be ignored completely in the boolean operation.
*
* If use_self is true, all operations do the same: the submesh is self-intersected
* and all pieces inside that result are removed.
* Otherwise, the operations can be one of BMESH_ISECT_BOOLEAN_ISECT, BMESH_ISECT_BOOLEAN_UNION,
* or BMESH_ISECT_BOOLEAN_DIFFERENCE.
*
* (The actual library function called to do the boolean is internally capable of handling
* n-ary operands, so maybe in the future we can expose that functionality to users.)
*/
bool BM_mesh_boolean(BMesh *bm,
struct BMLoop *(*looptris)[3],
const int looptris_tot,
int (*test_fn)(BMFace *f, void *user_data),
void *user_data,
const bool use_self,
const int boolean_mode)
{
Boolean_trimesh_input *in_a = trimesh_input_from_bm(
bm, looptris, looptris_tot, test_fn, user_data, 0);
Boolean_trimesh_input *in_b = NULL;
if (!use_self) {
in_b = trimesh_input_from_bm(bm, looptris, looptris_tot, test_fn, user_data, 1);
/* The old boolean code does DIFFERENCE as b - a, which is weird, so adapt here
* so the rest of the code is sensible.
*/
SWAP(Boolean_trimesh_input *, in_a, in_b);
}
Boolean_trimesh_output *out = BLI_boolean_trimesh(in_a, in_b, boolean_mode);
BLI_assert(out != NULL);
bool intersections_found = out->tri_len != in_a->tri_len + (in_b ? in_b->tri_len : 0) ||
out->vert_len != in_a->vert_len + (in_b ? in_b->vert_len : 0);
apply_trimesh_output_to_bmesh(bm, out);
free_trimesh_input(in_a);
if (in_b) {
free_trimesh_input(in_b);
}
BLI_boolean_trimesh_free(out);
return intersections_found;
}
/*
* Perform a Knife Intersection operation on the mesh bm.
* There are either one or two operands, the same as described above for BM_mesh_boolean().
* If use_separate_all is true, each edge that is created from the intersection should
* be used to separate all its incident faces. TODO: implement that.
* TODO: need to ensure that "selected/non-selected" flag of original faces gets propagated
* to the intersection result faces.
*/
bool BM_mesh_boolean_knife(BMesh *bm,
struct BMLoop *(*looptris)[3],
const int looptris_tot,
int (*test_fn)(BMFace *f, void *user_data),
void *user_data,
const bool use_self,
const bool UNUSED(use_separate_all))
{
Boolean_trimesh_input *in_a = trimesh_input_from_bm(
bm, looptris, looptris_tot, test_fn, user_data, 0);
Boolean_trimesh_input *in_b = NULL;
if (!use_self) {
in_b = trimesh_input_from_bm(bm, looptris, looptris_tot, test_fn, user_data, 1);
}
Boolean_trimesh_output *out = BLI_boolean_trimesh(in_a, in_b, BOOLEAN_NONE);
BLI_assert(out != NULL);
bool intersections_found = out->tri_len != in_a->tri_len + (in_b ? in_b->tri_len : 0) ||
out->vert_len != in_a->vert_len + (in_b ? in_b->vert_len : 0);
apply_trimesh_output_to_bmesh(bm, out);
free_trimesh_input(in_a);
if (in_b) {
free_trimesh_input(in_b);
}
BLI_boolean_trimesh_free(out);
return intersections_found;
}
|
