1/**************************************************************************/
2/* csg.cpp */
3/**************************************************************************/
4/* This file is part of: */
5/* GODOT ENGINE */
6/* https://godotengine.org */
7/**************************************************************************/
8/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
9/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
10/* */
11/* Permission is hereby granted, free of charge, to any person obtaining */
12/* a copy of this software and associated documentation files (the */
13/* "Software"), to deal in the Software without restriction, including */
14/* without limitation the rights to use, copy, modify, merge, publish, */
15/* distribute, sublicense, and/or sell copies of the Software, and to */
16/* permit persons to whom the Software is furnished to do so, subject to */
17/* the following conditions: */
18/* */
19/* The above copyright notice and this permission notice shall be */
20/* included in all copies or substantial portions of the Software. */
21/* */
22/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
23/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
24/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
25/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
26/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
27/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
28/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
29/**************************************************************************/
30
31#include "csg.h"
32
33#include "core/math/geometry_2d.h"
34#include "core/math/math_funcs.h"
35#include "core/templates/sort_array.h"
36
37// Static helper functions.
38
39inline static bool is_snapable(const Vector3 &p_point1, const Vector3 &p_point2, real_t p_distance) {
40 return p_point2.distance_squared_to(p_point1) < p_distance * p_distance;
41}
42
43inline static Vector2 interpolate_segment_uv(const Vector2 p_segment_points[2], const Vector2 p_uvs[2], const Vector2 &p_interpolation_point) {
44 if (p_segment_points[0].is_equal_approx(p_segment_points[1])) {
45 return p_uvs[0];
46 }
47
48 float segment_length = p_segment_points[0].distance_to(p_segment_points[1]);
49 float distance = p_segment_points[0].distance_to(p_interpolation_point);
50 float fraction = distance / segment_length;
51
52 return p_uvs[0].lerp(p_uvs[1], fraction);
53}
54
55inline static Vector2 interpolate_triangle_uv(const Vector2 p_vertices[3], const Vector2 p_uvs[3], const Vector2 &p_interpolation_point) {
56 if (p_interpolation_point.is_equal_approx(p_vertices[0])) {
57 return p_uvs[0];
58 }
59 if (p_interpolation_point.is_equal_approx(p_vertices[1])) {
60 return p_uvs[1];
61 }
62 if (p_interpolation_point.is_equal_approx(p_vertices[2])) {
63 return p_uvs[2];
64 }
65
66 Vector2 edge1 = p_vertices[1] - p_vertices[0];
67 Vector2 edge2 = p_vertices[2] - p_vertices[0];
68 Vector2 interpolation = p_interpolation_point - p_vertices[0];
69
70 float edge1_on_edge1 = edge1.dot(edge1);
71 float edge1_on_edge2 = edge1.dot(edge2);
72 float edge2_on_edge2 = edge2.dot(edge2);
73 float inter_on_edge1 = interpolation.dot(edge1);
74 float inter_on_edge2 = interpolation.dot(edge2);
75 float scale = (edge1_on_edge1 * edge2_on_edge2 - edge1_on_edge2 * edge1_on_edge2);
76 if (scale == 0) {
77 return p_uvs[0];
78 }
79
80 float v = (edge2_on_edge2 * inter_on_edge1 - edge1_on_edge2 * inter_on_edge2) / scale;
81 float w = (edge1_on_edge1 * inter_on_edge2 - edge1_on_edge2 * inter_on_edge1) / scale;
82 float u = 1.0f - v - w;
83
84 return p_uvs[0] * u + p_uvs[1] * v + p_uvs[2] * w;
85}
86
87static inline bool ray_intersects_triangle(const Vector3 &p_from, const Vector3 &p_dir, const Vector3 p_vertices[3], float p_tolerance, Vector3 &r_intersection_point) {
88 Vector3 edge1 = p_vertices[1] - p_vertices[0];
89 Vector3 edge2 = p_vertices[2] - p_vertices[0];
90 Vector3 h = p_dir.cross(edge2);
91 real_t a = edge1.dot(h);
92 // Check if ray is parallel to triangle.
93 if (Math::is_zero_approx(a)) {
94 return false;
95 }
96 real_t f = 1.0 / a;
97
98 Vector3 s = p_from - p_vertices[0];
99 real_t u = f * s.dot(h);
100 if (u < 0.0 - p_tolerance || u > 1.0 + p_tolerance) {
101 return false;
102 }
103
104 Vector3 q = s.cross(edge1);
105 real_t v = f * p_dir.dot(q);
106 if (v < 0.0 - p_tolerance || u + v > 1.0 + p_tolerance) {
107 return false;
108 }
109
110 // Ray intersects triangle.
111 // Calculate distance.
112 real_t t = f * edge2.dot(q);
113 // Confirm triangle is in front of ray.
114 if (t >= p_tolerance) {
115 r_intersection_point = p_from + p_dir * t;
116 return true;
117 } else {
118 return false;
119 }
120}
121
122inline bool is_point_in_triangle(const Vector3 &p_point, const Vector3 p_vertices[3], int p_shifted = 0) {
123 real_t det = p_vertices[0].dot(p_vertices[1].cross(p_vertices[2]));
124
125 // If determinant is, zero try shift the triangle and the point.
126 if (Math::is_zero_approx(det)) {
127 if (p_shifted > 2) {
128 // Triangle appears degenerate, so ignore it.
129 return false;
130 }
131 Vector3 shift_by;
132 shift_by[p_shifted] = 1;
133 Vector3 shifted_point = p_point + shift_by;
134 Vector3 shifted_vertices[3] = { p_vertices[0] + shift_by, p_vertices[1] + shift_by, p_vertices[2] + shift_by };
135 return is_point_in_triangle(shifted_point, shifted_vertices, p_shifted + 1);
136 }
137
138 // Find the barycentric coordinates of the point with respect to the vertices.
139 real_t lambda[3];
140 lambda[0] = p_vertices[1].cross(p_vertices[2]).dot(p_point) / det;
141 lambda[1] = p_vertices[2].cross(p_vertices[0]).dot(p_point) / det;
142 lambda[2] = p_vertices[0].cross(p_vertices[1]).dot(p_point) / det;
143
144 // Point is in the plane if all lambdas sum to 1.
145 if (!Math::is_equal_approx(lambda[0] + lambda[1] + lambda[2], 1)) {
146 return false;
147 }
148
149 // Point is inside the triangle if all lambdas are positive.
150 if (lambda[0] < 0 || lambda[1] < 0 || lambda[2] < 0) {
151 return false;
152 }
153
154 return true;
155}
156
157inline static bool is_triangle_degenerate(const Vector2 p_vertices[3], real_t p_vertex_snap2) {
158 real_t det = p_vertices[0].x * p_vertices[1].y - p_vertices[0].x * p_vertices[2].y +
159 p_vertices[0].y * p_vertices[2].x - p_vertices[0].y * p_vertices[1].x +
160 p_vertices[1].x * p_vertices[2].y - p_vertices[1].y * p_vertices[2].x;
161
162 return det < p_vertex_snap2;
163}
164
165inline static bool are_segments_parallel(const Vector2 p_segment1_points[2], const Vector2 p_segment2_points[2], float p_vertex_snap2) {
166 Vector2 segment1 = p_segment1_points[1] - p_segment1_points[0];
167 Vector2 segment2 = p_segment2_points[1] - p_segment2_points[0];
168 real_t segment1_length2 = segment1.dot(segment1);
169 real_t segment2_length2 = segment2.dot(segment2);
170 real_t segment_onto_segment = segment2.dot(segment1);
171
172 if (segment1_length2 < p_vertex_snap2 || segment2_length2 < p_vertex_snap2) {
173 return true;
174 }
175
176 real_t max_separation2;
177 if (segment1_length2 > segment2_length2) {
178 max_separation2 = segment2_length2 - segment_onto_segment * segment_onto_segment / segment1_length2;
179 } else {
180 max_separation2 = segment1_length2 - segment_onto_segment * segment_onto_segment / segment2_length2;
181 }
182
183 return max_separation2 < p_vertex_snap2;
184}
185
186// CSGBrush
187
188void CSGBrush::_regen_face_aabbs() {
189 for (int i = 0; i < faces.size(); i++) {
190 faces.write[i].aabb = AABB();
191 faces.write[i].aabb.position = faces[i].vertices[0];
192 faces.write[i].aabb.expand_to(faces[i].vertices[1]);
193 faces.write[i].aabb.expand_to(faces[i].vertices[2]);
194 }
195}
196
197void CSGBrush::build_from_faces(const Vector<Vector3> &p_vertices, const Vector<Vector2> &p_uvs, const Vector<bool> &p_smooth, const Vector<Ref<Material>> &p_materials, const Vector<bool> &p_flip_faces) {
198 faces.clear();
199
200 int vc = p_vertices.size();
201
202 ERR_FAIL_COND((vc % 3) != 0);
203
204 const Vector3 *rv = p_vertices.ptr();
205 int uvc = p_uvs.size();
206 const Vector2 *ruv = p_uvs.ptr();
207 int sc = p_smooth.size();
208 const bool *rs = p_smooth.ptr();
209 int mc = p_materials.size();
210 const Ref<Material> *rm = p_materials.ptr();
211 int ic = p_flip_faces.size();
212 const bool *ri = p_flip_faces.ptr();
213
214 HashMap<Ref<Material>, int> material_map;
215
216 faces.resize(p_vertices.size() / 3);
217
218 for (int i = 0; i < faces.size(); i++) {
219 Face &f = faces.write[i];
220 f.vertices[0] = rv[i * 3 + 0];
221 f.vertices[1] = rv[i * 3 + 1];
222 f.vertices[2] = rv[i * 3 + 2];
223
224 if (uvc == vc) {
225 f.uvs[0] = ruv[i * 3 + 0];
226 f.uvs[1] = ruv[i * 3 + 1];
227 f.uvs[2] = ruv[i * 3 + 2];
228 }
229
230 if (sc == vc / 3) {
231 f.smooth = rs[i];
232 } else {
233 f.smooth = false;
234 }
235
236 if (ic == vc / 3) {
237 f.invert = ri[i];
238 } else {
239 f.invert = false;
240 }
241
242 if (mc == vc / 3) {
243 Ref<Material> mat = rm[i];
244 if (mat.is_valid()) {
245 HashMap<Ref<Material>, int>::ConstIterator E = material_map.find(mat);
246
247 if (E) {
248 f.material = E->value;
249 } else {
250 f.material = material_map.size();
251 material_map[mat] = f.material;
252 }
253
254 } else {
255 f.material = -1;
256 }
257 }
258 }
259
260 materials.resize(material_map.size());
261 for (const KeyValue<Ref<Material>, int> &E : material_map) {
262 materials.write[E.value] = E.key;
263 }
264
265 _regen_face_aabbs();
266}
267
268void CSGBrush::copy_from(const CSGBrush &p_brush, const Transform3D &p_xform) {
269 faces = p_brush.faces;
270 materials = p_brush.materials;
271
272 for (int i = 0; i < faces.size(); i++) {
273 for (int j = 0; j < 3; j++) {
274 faces.write[i].vertices[j] = p_xform.xform(p_brush.faces[i].vertices[j]);
275 }
276 }
277
278 _regen_face_aabbs();
279}
280
281// CSGBrushOperation
282
283void CSGBrushOperation::merge_brushes(Operation p_operation, const CSGBrush &p_brush_a, const CSGBrush &p_brush_b, CSGBrush &r_merged_brush, float p_vertex_snap) {
284 // Check for face collisions and add necessary faces.
285 Build2DFaceCollection build2DFaceCollection;
286 for (int i = 0; i < p_brush_a.faces.size(); i++) {
287 for (int j = 0; j < p_brush_b.faces.size(); j++) {
288 if (p_brush_a.faces[i].aabb.intersects_inclusive(p_brush_b.faces[j].aabb)) {
289 update_faces(p_brush_a, i, p_brush_b, j, build2DFaceCollection, p_vertex_snap);
290 }
291 }
292 }
293
294 // Add faces to MeshMerge.
295 MeshMerge mesh_merge;
296 mesh_merge.vertex_snap = p_vertex_snap;
297
298 for (int i = 0; i < p_brush_a.faces.size(); i++) {
299 Ref<Material> material;
300 if (p_brush_a.faces[i].material != -1) {
301 material = p_brush_a.materials[p_brush_a.faces[i].material];
302 }
303
304 if (build2DFaceCollection.build2DFacesA.has(i)) {
305 build2DFaceCollection.build2DFacesA[i].addFacesToMesh(mesh_merge, p_brush_a.faces[i].smooth, p_brush_a.faces[i].invert, material, false);
306 } else {
307 Vector3 points[3];
308 Vector2 uvs[3];
309 for (int j = 0; j < 3; j++) {
310 points[j] = p_brush_a.faces[i].vertices[j];
311 uvs[j] = p_brush_a.faces[i].uvs[j];
312 }
313 mesh_merge.add_face(points, uvs, p_brush_a.faces[i].smooth, p_brush_a.faces[i].invert, material, false);
314 }
315 }
316
317 for (int i = 0; i < p_brush_b.faces.size(); i++) {
318 Ref<Material> material;
319 if (p_brush_b.faces[i].material != -1) {
320 material = p_brush_b.materials[p_brush_b.faces[i].material];
321 }
322
323 if (build2DFaceCollection.build2DFacesB.has(i)) {
324 build2DFaceCollection.build2DFacesB[i].addFacesToMesh(mesh_merge, p_brush_b.faces[i].smooth, p_brush_b.faces[i].invert, material, true);
325 } else {
326 Vector3 points[3];
327 Vector2 uvs[3];
328 for (int j = 0; j < 3; j++) {
329 points[j] = p_brush_b.faces[i].vertices[j];
330 uvs[j] = p_brush_b.faces[i].uvs[j];
331 }
332 mesh_merge.add_face(points, uvs, p_brush_b.faces[i].smooth, p_brush_b.faces[i].invert, material, true);
333 }
334 }
335
336 // Mark faces that ended up inside the intersection.
337 mesh_merge.mark_inside_faces();
338
339 // Create new brush and fill with new faces.
340 r_merged_brush.faces.clear();
341
342 switch (p_operation) {
343 case OPERATION_UNION: {
344 int outside_count = 0;
345
346 for (int i = 0; i < mesh_merge.faces.size(); i++) {
347 if (mesh_merge.faces[i].inside) {
348 continue;
349 }
350 outside_count++;
351 }
352
353 r_merged_brush.faces.resize(outside_count);
354
355 outside_count = 0;
356
357 for (int i = 0; i < mesh_merge.faces.size(); i++) {
358 if (mesh_merge.faces[i].inside) {
359 continue;
360 }
361
362 for (int j = 0; j < 3; j++) {
363 r_merged_brush.faces.write[outside_count].vertices[j] = mesh_merge.points[mesh_merge.faces[i].points[j]];
364 r_merged_brush.faces.write[outside_count].uvs[j] = mesh_merge.faces[i].uvs[j];
365 }
366
367 r_merged_brush.faces.write[outside_count].smooth = mesh_merge.faces[i].smooth;
368 r_merged_brush.faces.write[outside_count].invert = mesh_merge.faces[i].invert;
369 r_merged_brush.faces.write[outside_count].material = mesh_merge.faces[i].material_idx;
370 outside_count++;
371 }
372
373 r_merged_brush._regen_face_aabbs();
374
375 } break;
376
377 case OPERATION_INTERSECTION: {
378 int inside_count = 0;
379
380 for (int i = 0; i < mesh_merge.faces.size(); i++) {
381 if (!mesh_merge.faces[i].inside) {
382 continue;
383 }
384 inside_count++;
385 }
386
387 r_merged_brush.faces.resize(inside_count);
388
389 inside_count = 0;
390
391 for (int i = 0; i < mesh_merge.faces.size(); i++) {
392 if (!mesh_merge.faces[i].inside) {
393 continue;
394 }
395
396 for (int j = 0; j < 3; j++) {
397 r_merged_brush.faces.write[inside_count].vertices[j] = mesh_merge.points[mesh_merge.faces[i].points[j]];
398 r_merged_brush.faces.write[inside_count].uvs[j] = mesh_merge.faces[i].uvs[j];
399 }
400
401 r_merged_brush.faces.write[inside_count].smooth = mesh_merge.faces[i].smooth;
402 r_merged_brush.faces.write[inside_count].invert = mesh_merge.faces[i].invert;
403 r_merged_brush.faces.write[inside_count].material = mesh_merge.faces[i].material_idx;
404 inside_count++;
405 }
406
407 r_merged_brush._regen_face_aabbs();
408
409 } break;
410
411 case OPERATION_SUBTRACTION: {
412 int face_count = 0;
413
414 for (int i = 0; i < mesh_merge.faces.size(); i++) {
415 if (mesh_merge.faces[i].from_b && !mesh_merge.faces[i].inside) {
416 continue;
417 }
418 if (!mesh_merge.faces[i].from_b && mesh_merge.faces[i].inside) {
419 continue;
420 }
421 face_count++;
422 }
423
424 r_merged_brush.faces.resize(face_count);
425
426 face_count = 0;
427
428 for (int i = 0; i < mesh_merge.faces.size(); i++) {
429 if (mesh_merge.faces[i].from_b && !mesh_merge.faces[i].inside) {
430 continue;
431 }
432 if (!mesh_merge.faces[i].from_b && mesh_merge.faces[i].inside) {
433 continue;
434 }
435
436 for (int j = 0; j < 3; j++) {
437 r_merged_brush.faces.write[face_count].vertices[j] = mesh_merge.points[mesh_merge.faces[i].points[j]];
438 r_merged_brush.faces.write[face_count].uvs[j] = mesh_merge.faces[i].uvs[j];
439 }
440
441 if (mesh_merge.faces[i].from_b) {
442 //invert facing of insides of B
443 SWAP(r_merged_brush.faces.write[face_count].vertices[1], r_merged_brush.faces.write[face_count].vertices[2]);
444 SWAP(r_merged_brush.faces.write[face_count].uvs[1], r_merged_brush.faces.write[face_count].uvs[2]);
445 }
446
447 r_merged_brush.faces.write[face_count].smooth = mesh_merge.faces[i].smooth;
448 r_merged_brush.faces.write[face_count].invert = mesh_merge.faces[i].invert;
449 r_merged_brush.faces.write[face_count].material = mesh_merge.faces[i].material_idx;
450 face_count++;
451 }
452
453 r_merged_brush._regen_face_aabbs();
454
455 } break;
456 }
457
458 // Update the list of materials.
459 r_merged_brush.materials.resize(mesh_merge.materials.size());
460 for (const KeyValue<Ref<Material>, int> &E : mesh_merge.materials) {
461 r_merged_brush.materials.write[E.value] = E.key;
462 }
463}
464
465// CSGBrushOperation::MeshMerge
466
467// Use a limit to speed up bvh and limit the depth.
468#define BVH_LIMIT 8
469
470int CSGBrushOperation::MeshMerge::_create_bvh(FaceBVH *r_facebvhptr, FaceBVH **r_facebvhptrptr, int p_from, int p_size, int p_depth, int &r_max_depth, int &r_max_alloc) {
471 if (p_depth > r_max_depth) {
472 r_max_depth = p_depth;
473 }
474
475 if (p_size == 0) {
476 return -1;
477 }
478
479 if (p_size <= BVH_LIMIT) {
480 for (int i = 0; i < p_size - 1; i++) {
481 r_facebvhptrptr[p_from + i]->next = r_facebvhptrptr[p_from + i + 1] - r_facebvhptr;
482 }
483 return r_facebvhptrptr[p_from] - r_facebvhptr;
484 }
485
486 AABB aabb;
487 aabb = r_facebvhptrptr[p_from]->aabb;
488 for (int i = 1; i < p_size; i++) {
489 aabb.merge_with(r_facebvhptrptr[p_from + i]->aabb);
490 }
491
492 int li = aabb.get_longest_axis_index();
493
494 switch (li) {
495 case Vector3::AXIS_X: {
496 SortArray<FaceBVH *, FaceBVHCmpX> sort_x;
497 sort_x.nth_element(0, p_size, p_size / 2, &r_facebvhptrptr[p_from]);
498 //sort_x.sort(&p_bb[p_from],p_size);
499 } break;
500
501 case Vector3::AXIS_Y: {
502 SortArray<FaceBVH *, FaceBVHCmpY> sort_y;
503 sort_y.nth_element(0, p_size, p_size / 2, &r_facebvhptrptr[p_from]);
504 //sort_y.sort(&p_bb[p_from],p_size);
505 } break;
506
507 case Vector3::AXIS_Z: {
508 SortArray<FaceBVH *, FaceBVHCmpZ> sort_z;
509 sort_z.nth_element(0, p_size, p_size / 2, &r_facebvhptrptr[p_from]);
510 //sort_z.sort(&p_bb[p_from],p_size);
511 } break;
512 }
513
514 int left = _create_bvh(r_facebvhptr, r_facebvhptrptr, p_from, p_size / 2, p_depth + 1, r_max_depth, r_max_alloc);
515 int right = _create_bvh(r_facebvhptr, r_facebvhptrptr, p_from + p_size / 2, p_size - p_size / 2, p_depth + 1, r_max_depth, r_max_alloc);
516
517 int index = r_max_alloc++;
518 FaceBVH *_new = &r_facebvhptr[index];
519 _new->aabb = aabb;
520 _new->center = aabb.get_center();
521 _new->face = -1;
522 _new->left = left;
523 _new->right = right;
524 _new->next = -1;
525
526 return index;
527}
528
529void CSGBrushOperation::MeshMerge::_add_distance(List<IntersectionDistance> &r_intersectionsA, List<IntersectionDistance> &r_intersectionsB, bool p_from_B, real_t p_distance_squared, bool p_is_conormal) const {
530 List<IntersectionDistance> &intersections = p_from_B ? r_intersectionsB : r_intersectionsA;
531
532 // Check if distance exists.
533 for (const IntersectionDistance E : intersections) {
534 if (E.is_conormal == p_is_conormal && Math::is_equal_approx(E.distance_squared, p_distance_squared)) {
535 return;
536 }
537 }
538 IntersectionDistance distance;
539 distance.is_conormal = p_is_conormal;
540 distance.distance_squared = p_distance_squared;
541 intersections.push_back(distance);
542}
543
544bool CSGBrushOperation::MeshMerge::_bvh_inside(FaceBVH *r_facebvhptr, int p_max_depth, int p_bvh_first, int p_face_idx) const {
545 Face face = faces[p_face_idx];
546 Vector3 face_points[3] = {
547 points[face.points[0]],
548 points[face.points[1]],
549 points[face.points[2]]
550 };
551 Vector3 face_center = (face_points[0] + face_points[1] + face_points[2]) / 3.0;
552 Vector3 face_normal = Plane(face_points[0], face_points[1], face_points[2]).normal;
553
554 uint32_t *stack = (uint32_t *)alloca(sizeof(int) * p_max_depth);
555
556 enum {
557 TEST_AABB_BIT = 0,
558 VISIT_LEFT_BIT = 1,
559 VISIT_RIGHT_BIT = 2,
560 VISIT_DONE_BIT = 3,
561 VISITED_BIT_SHIFT = 29,
562 NODE_IDX_MASK = (1 << VISITED_BIT_SHIFT) - 1,
563 VISITED_BIT_MASK = ~NODE_IDX_MASK
564 };
565
566 List<IntersectionDistance> intersectionsA;
567 List<IntersectionDistance> intersectionsB;
568
569 Intersection closest_intersection;
570 closest_intersection.found = false;
571
572 int level = 0;
573 int pos = p_bvh_first;
574 stack[0] = pos;
575
576 while (true) {
577 uint32_t node = stack[level] & NODE_IDX_MASK;
578 const FaceBVH *current_facebvhptr = &(r_facebvhptr[node]);
579 bool done = false;
580
581 switch (stack[level] >> VISITED_BIT_SHIFT) {
582 case TEST_AABB_BIT: {
583 if (current_facebvhptr->face >= 0) {
584 while (current_facebvhptr) {
585 if (p_face_idx != current_facebvhptr->face &&
586 current_facebvhptr->aabb.intersects_ray(face_center, face_normal)) {
587 const Face &current_face = faces[current_facebvhptr->face];
588 Vector3 current_points[3] = {
589 points[current_face.points[0]],
590 points[current_face.points[1]],
591 points[current_face.points[2]]
592 };
593 Vector3 current_normal = Plane(current_points[0], current_points[1], current_points[2]).normal;
594 Vector3 intersection_point;
595 // Check if faces are co-planar.
596 if (current_normal.is_equal_approx(face_normal) &&
597 is_point_in_triangle(face_center, current_points)) {
598 // Only add an intersection if not a B face.
599 if (!face.from_b) {
600 _add_distance(intersectionsA, intersectionsB, current_face.from_b, 0, true);
601 }
602 } else if (ray_intersects_triangle(face_center, face_normal, current_points, CMP_EPSILON, intersection_point)) {
603 real_t distance_squared = face_center.distance_squared_to(intersection_point);
604 real_t inner = current_normal.dot(face_normal);
605 // If the faces are perpendicular, ignore this face.
606 // The triangles on the side should be intersected and result in the correct behavior.
607 if (!Math::is_zero_approx(inner)) {
608 _add_distance(intersectionsA, intersectionsB, current_face.from_b, distance_squared, inner > 0.0f);
609 }
610 }
611
612 if (face.from_b != current_face.from_b) {
613 if (current_normal.is_equal_approx(face_normal) &&
614 is_point_in_triangle(face_center, current_points)) {
615 // Only add an intersection if not a B face.
616 if (!face.from_b) {
617 closest_intersection.found = true;
618 closest_intersection.conormal = 1.0f;
619 closest_intersection.distance_squared = 0.0f;
620 closest_intersection.origin_angle = -FLT_MAX;
621 }
622 } else if (ray_intersects_triangle(face_center, face_normal, current_points, CMP_EPSILON, intersection_point)) {
623 Intersection potential_intersection;
624 potential_intersection.found = true;
625 potential_intersection.conormal = face_normal.dot(current_normal);
626 potential_intersection.distance_squared = face_center.distance_squared_to(intersection_point);
627 potential_intersection.origin_angle = Math::abs(potential_intersection.conormal);
628 real_t intersection_dist_from_face = face_normal.dot(intersection_point - face_center);
629 for (int i = 0; i < 3; i++) {
630 real_t point_dist_from_face = face_normal.dot(current_points[i] - face_center);
631 if (!Math::is_equal_approx(point_dist_from_face, intersection_dist_from_face) &&
632 point_dist_from_face < intersection_dist_from_face) {
633 potential_intersection.origin_angle = -potential_intersection.origin_angle;
634 break;
635 }
636 }
637 if (potential_intersection.conormal != 0.0f) {
638 if (!closest_intersection.found) {
639 closest_intersection = potential_intersection;
640 } else if (!Math::is_equal_approx(potential_intersection.distance_squared, closest_intersection.distance_squared) &&
641 potential_intersection.distance_squared < closest_intersection.distance_squared) {
642 closest_intersection = potential_intersection;
643 } else if (Math::is_equal_approx(potential_intersection.distance_squared, closest_intersection.distance_squared)) {
644 if (potential_intersection.origin_angle < closest_intersection.origin_angle) {
645 closest_intersection = potential_intersection;
646 }
647 }
648 }
649 }
650 }
651 }
652
653 if (current_facebvhptr->next != -1) {
654 current_facebvhptr = &r_facebvhptr[current_facebvhptr->next];
655 } else {
656 current_facebvhptr = nullptr;
657 }
658 }
659
660 stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
661
662 } else {
663 bool valid = current_facebvhptr->aabb.intersects_ray(face_center, face_normal);
664
665 if (!valid) {
666 stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
667 } else {
668 stack[level] = (VISIT_LEFT_BIT << VISITED_BIT_SHIFT) | node;
669 }
670 }
671 continue;
672 }
673
674 case VISIT_LEFT_BIT: {
675 stack[level] = (VISIT_RIGHT_BIT << VISITED_BIT_SHIFT) | node;
676 stack[level + 1] = current_facebvhptr->left | TEST_AABB_BIT;
677 level++;
678 continue;
679 }
680
681 case VISIT_RIGHT_BIT: {
682 stack[level] = (VISIT_DONE_BIT << VISITED_BIT_SHIFT) | node;
683 stack[level + 1] = current_facebvhptr->right | TEST_AABB_BIT;
684 level++;
685 continue;
686 }
687
688 case VISIT_DONE_BIT: {
689 if (level == 0) {
690 done = true;
691 break;
692 } else {
693 level--;
694 }
695 continue;
696 }
697 }
698
699 if (done) {
700 break;
701 }
702 }
703
704 if (!closest_intersection.found) {
705 return false;
706 } else {
707 return closest_intersection.conormal > 0.0f;
708 }
709}
710
711void CSGBrushOperation::MeshMerge::mark_inside_faces() {
712 // Mark faces that are inside. This helps later do the boolean ops when merging.
713 // This approach is very brute force with a bunch of optimizations,
714 // such as BVH and pre AABB intersection test.
715
716 Vector<FaceBVH> bvhvec;
717 bvhvec.resize(faces.size() * 3); // Will never be larger than this (TODO: Make better)
718 FaceBVH *facebvh = bvhvec.ptrw();
719
720 AABB aabb_a;
721 AABB aabb_b;
722
723 bool first_a = true;
724 bool first_b = true;
725
726 for (int i = 0; i < faces.size(); i++) {
727 facebvh[i].left = -1;
728 facebvh[i].right = -1;
729 facebvh[i].face = i;
730 facebvh[i].aabb.position = points[faces[i].points[0]];
731 facebvh[i].aabb.expand_to(points[faces[i].points[1]]);
732 facebvh[i].aabb.expand_to(points[faces[i].points[2]]);
733 facebvh[i].center = facebvh[i].aabb.get_center();
734 facebvh[i].aabb.grow_by(vertex_snap);
735 facebvh[i].next = -1;
736
737 if (faces[i].from_b) {
738 if (first_b) {
739 aabb_b = facebvh[i].aabb;
740 first_b = false;
741 } else {
742 aabb_b.merge_with(facebvh[i].aabb);
743 }
744 } else {
745 if (first_a) {
746 aabb_a = facebvh[i].aabb;
747 first_a = false;
748 } else {
749 aabb_a.merge_with(facebvh[i].aabb);
750 }
751 }
752 }
753
754 AABB intersection_aabb = aabb_a.intersection(aabb_b);
755
756 // Check if shape AABBs intersect.
757 if (intersection_aabb.size == Vector3()) {
758 return;
759 }
760
761 Vector<FaceBVH *> bvhtrvec;
762 bvhtrvec.resize(faces.size());
763 FaceBVH **bvhptr = bvhtrvec.ptrw();
764 for (int i = 0; i < faces.size(); i++) {
765 bvhptr[i] = &facebvh[i];
766 }
767
768 int max_depth = 0;
769 int max_alloc = faces.size();
770 _create_bvh(facebvh, bvhptr, 0, faces.size(), 1, max_depth, max_alloc);
771
772 for (int i = 0; i < faces.size(); i++) {
773 // Check if face AABB intersects the intersection AABB.
774 if (!intersection_aabb.intersects_inclusive(facebvh[i].aabb)) {
775 continue;
776 }
777
778 if (_bvh_inside(facebvh, max_depth, max_alloc - 1, i)) {
779 faces.write[i].inside = true;
780 }
781 }
782}
783
784void CSGBrushOperation::MeshMerge::add_face(const Vector3 p_points[3], const Vector2 p_uvs[3], bool p_smooth, bool p_invert, const Ref<Material> &p_material, bool p_from_b) {
785 int indices[3];
786 for (int i = 0; i < 3; i++) {
787 VertexKey vk;
788 vk.x = int((double(p_points[i].x) + double(vertex_snap) * 0.31234) / double(vertex_snap));
789 vk.y = int((double(p_points[i].y) + double(vertex_snap) * 0.31234) / double(vertex_snap));
790 vk.z = int((double(p_points[i].z) + double(vertex_snap) * 0.31234) / double(vertex_snap));
791
792 int res;
793 if (snap_cache.lookup(vk, res)) {
794 indices[i] = res;
795 } else {
796 indices[i] = points.size();
797 points.push_back(p_points[i]);
798 snap_cache.set(vk, indices[i]);
799 }
800 }
801
802 // Don't add degenerate faces.
803 if (indices[0] == indices[2] || indices[0] == indices[1] || indices[1] == indices[2]) {
804 return;
805 }
806
807 MeshMerge::Face face;
808 face.from_b = p_from_b;
809 face.inside = false;
810 face.smooth = p_smooth;
811 face.invert = p_invert;
812
813 if (p_material.is_valid()) {
814 if (!materials.has(p_material)) {
815 face.material_idx = materials.size();
816 materials[p_material] = face.material_idx;
817 } else {
818 face.material_idx = materials[p_material];
819 }
820 } else {
821 face.material_idx = -1;
822 }
823
824 for (int k = 0; k < 3; k++) {
825 face.points[k] = indices[k];
826 face.uvs[k] = p_uvs[k];
827 }
828
829 faces.push_back(face);
830}
831
832// CSGBrushOperation::Build2DFaces
833
834int CSGBrushOperation::Build2DFaces::_get_point_idx(const Vector2 &p_point) {
835 for (int vertex_idx = 0; vertex_idx < vertices.size(); ++vertex_idx) {
836 if (vertices[vertex_idx].point.distance_squared_to(p_point) < vertex_snap2) {
837 return vertex_idx;
838 }
839 }
840 return -1;
841}
842
843int CSGBrushOperation::Build2DFaces::_add_vertex(const Vertex2D &p_vertex) {
844 // Check if vertex exists.
845 int vertex_id = _get_point_idx(p_vertex.point);
846 if (vertex_id != -1) {
847 return vertex_id;
848 }
849
850 vertices.push_back(p_vertex);
851 return vertices.size() - 1;
852}
853
854void CSGBrushOperation::Build2DFaces::_add_vertex_idx_sorted(Vector<int> &r_vertex_indices, int p_new_vertex_index) {
855 if (p_new_vertex_index >= 0 && r_vertex_indices.find(p_new_vertex_index) == -1) {
856 ERR_FAIL_COND_MSG(p_new_vertex_index >= vertices.size(), "Invalid vertex index.");
857
858 // The first vertex.
859 if (r_vertex_indices.size() == 0) {
860 // Simply add it.
861 r_vertex_indices.push_back(p_new_vertex_index);
862 return;
863 }
864
865 // The second vertex.
866 if (r_vertex_indices.size() == 1) {
867 Vector2 first_point = vertices[r_vertex_indices[0]].point;
868 Vector2 new_point = vertices[p_new_vertex_index].point;
869
870 // Sort along the axis with the greatest difference.
871 int axis = 0;
872 if (Math::abs(new_point.x - first_point.x) < Math::abs(new_point.y - first_point.y)) {
873 axis = 1;
874 }
875
876 // Add it to the beginning or the end appropriately.
877 if (new_point[axis] < first_point[axis]) {
878 r_vertex_indices.insert(0, p_new_vertex_index);
879 } else {
880 r_vertex_indices.push_back(p_new_vertex_index);
881 }
882
883 return;
884 }
885
886 // Third or later vertices.
887 Vector2 first_point = vertices[r_vertex_indices[0]].point;
888 Vector2 last_point = vertices[r_vertex_indices[r_vertex_indices.size() - 1]].point;
889 Vector2 new_point = vertices[p_new_vertex_index].point;
890
891 // Determine axis being sorted against i.e. the axis with the greatest difference.
892 int axis = 0;
893 if (Math::abs(last_point.x - first_point.x) < Math::abs(last_point.y - first_point.y)) {
894 axis = 1;
895 }
896
897 // Insert the point at the appropriate index.
898 for (int insert_idx = 0; insert_idx < r_vertex_indices.size(); ++insert_idx) {
899 Vector2 insert_point = vertices[r_vertex_indices[insert_idx]].point;
900 if (new_point[axis] < insert_point[axis]) {
901 r_vertex_indices.insert(insert_idx, p_new_vertex_index);
902 return;
903 }
904 }
905
906 // New largest, add it to the end.
907 r_vertex_indices.push_back(p_new_vertex_index);
908 }
909}
910
911void CSGBrushOperation::Build2DFaces::_merge_faces(const Vector<int> &p_segment_indices) {
912 int segments = p_segment_indices.size() - 1;
913 if (segments < 2) {
914 return;
915 }
916
917 // Faces around an inner vertex are merged by moving the inner vertex to the first vertex.
918 for (int sorted_idx = 1; sorted_idx < segments; ++sorted_idx) {
919 int closest_idx = 0;
920 int inner_idx = p_segment_indices[sorted_idx];
921
922 if (sorted_idx > segments / 2) {
923 // Merge to other segment end.
924 closest_idx = segments;
925 // Reverse the merge order.
926 inner_idx = p_segment_indices[segments + segments / 2 - sorted_idx];
927 }
928
929 // Find the mergeable faces.
930 Vector<int> merge_faces_idx;
931 Vector<Face2D> merge_faces;
932 Vector<int> merge_faces_inner_vertex_idx;
933 for (int face_idx = 0; face_idx < faces.size(); ++face_idx) {
934 for (int face_vertex_idx = 0; face_vertex_idx < 3; ++face_vertex_idx) {
935 if (faces[face_idx].vertex_idx[face_vertex_idx] == inner_idx) {
936 merge_faces_idx.push_back(face_idx);
937 merge_faces.push_back(faces[face_idx]);
938 merge_faces_inner_vertex_idx.push_back(face_vertex_idx);
939 }
940 }
941 }
942
943 Vector<int> degenerate_points;
944
945 // Create the new faces.
946 for (int merge_idx = 0; merge_idx < merge_faces.size(); ++merge_idx) {
947 int outer_edge_idx[2];
948 outer_edge_idx[0] = merge_faces[merge_idx].vertex_idx[(merge_faces_inner_vertex_idx[merge_idx] + 1) % 3];
949 outer_edge_idx[1] = merge_faces[merge_idx].vertex_idx[(merge_faces_inner_vertex_idx[merge_idx] + 2) % 3];
950
951 // Skip flattened faces.
952 if (outer_edge_idx[0] == p_segment_indices[closest_idx] ||
953 outer_edge_idx[1] == p_segment_indices[closest_idx]) {
954 continue;
955 }
956
957 //Don't create degenerate triangles.
958 Vector2 edge1[2] = {
959 vertices[outer_edge_idx[0]].point,
960 vertices[p_segment_indices[closest_idx]].point
961 };
962 Vector2 edge2[2] = {
963 vertices[outer_edge_idx[1]].point,
964 vertices[p_segment_indices[closest_idx]].point
965 };
966 if (are_segments_parallel(edge1, edge2, vertex_snap2)) {
967 if (!degenerate_points.find(outer_edge_idx[0])) {
968 degenerate_points.push_back(outer_edge_idx[0]);
969 }
970 if (!degenerate_points.find(outer_edge_idx[1])) {
971 degenerate_points.push_back(outer_edge_idx[1]);
972 }
973 continue;
974 }
975
976 // Create new faces.
977 Face2D new_face;
978 new_face.vertex_idx[0] = p_segment_indices[closest_idx];
979 new_face.vertex_idx[1] = outer_edge_idx[0];
980 new_face.vertex_idx[2] = outer_edge_idx[1];
981 faces.push_back(new_face);
982 }
983
984 // Delete the old faces in reverse index order.
985 merge_faces_idx.sort();
986 merge_faces_idx.reverse();
987 for (int i = 0; i < merge_faces_idx.size(); ++i) {
988 faces.remove_at(merge_faces_idx[i]);
989 }
990
991 if (degenerate_points.size() == 0) {
992 continue;
993 }
994
995 // Split faces using degenerate points.
996 for (int face_idx = 0; face_idx < faces.size(); ++face_idx) {
997 Face2D face = faces[face_idx];
998 Vertex2D face_vertices[3] = {
999 vertices[face.vertex_idx[0]],
1000 vertices[face.vertex_idx[1]],
1001 vertices[face.vertex_idx[2]]
1002 };
1003 Vector2 face_points[3] = {
1004 face_vertices[0].point,
1005 face_vertices[1].point,
1006 face_vertices[2].point
1007 };
1008
1009 for (int point_idx = 0; point_idx < degenerate_points.size(); ++point_idx) {
1010 int degenerate_idx = degenerate_points[point_idx];
1011 Vector2 point_2D = vertices[degenerate_idx].point;
1012
1013 // Check if point is existing face vertex.
1014 bool existing = false;
1015 for (int i = 0; i < 3; ++i) {
1016 if (face_vertices[i].point.distance_squared_to(point_2D) < vertex_snap2) {
1017 existing = true;
1018 break;
1019 }
1020 }
1021 if (existing) {
1022 continue;
1023 }
1024
1025 // Check if point is on each edge.
1026 for (int face_edge_idx = 0; face_edge_idx < 3; ++face_edge_idx) {
1027 Vector2 edge_points[2] = {
1028 face_points[face_edge_idx],
1029 face_points[(face_edge_idx + 1) % 3]
1030 };
1031 Vector2 closest_point = Geometry2D::get_closest_point_to_segment(point_2D, edge_points);
1032
1033 if (point_2D.distance_squared_to(closest_point) < vertex_snap2) {
1034 int opposite_vertex_idx = face.vertex_idx[(face_edge_idx + 2) % 3];
1035
1036 // If new vertex snaps to degenerate vertex, just delete this face.
1037 if (degenerate_idx == opposite_vertex_idx) {
1038 faces.remove_at(face_idx);
1039 // Update index.
1040 --face_idx;
1041 break;
1042 }
1043
1044 // Create two new faces around the new edge and remove this face.
1045 // The new edge is the last edge.
1046 Face2D left_face;
1047 left_face.vertex_idx[0] = degenerate_idx;
1048 left_face.vertex_idx[1] = face.vertex_idx[(face_edge_idx + 1) % 3];
1049 left_face.vertex_idx[2] = opposite_vertex_idx;
1050 Face2D right_face;
1051 right_face.vertex_idx[0] = opposite_vertex_idx;
1052 right_face.vertex_idx[1] = face.vertex_idx[face_edge_idx];
1053 right_face.vertex_idx[2] = degenerate_idx;
1054 faces.remove_at(face_idx);
1055 faces.insert(face_idx, right_face);
1056 faces.insert(face_idx, left_face);
1057
1058 // Don't check against the new faces.
1059 ++face_idx;
1060
1061 // No need to check other edges.
1062 break;
1063 }
1064 }
1065 }
1066 }
1067 }
1068}
1069
1070void CSGBrushOperation::Build2DFaces::_find_edge_intersections(const Vector2 p_segment_points[2], Vector<int> &r_segment_indices) {
1071 LocalVector<Vector<Vector2>> processed_edges;
1072
1073 // For each face.
1074 for (int face_idx = 0; face_idx < faces.size(); ++face_idx) {
1075 Face2D face = faces[face_idx];
1076 Vertex2D face_vertices[3] = {
1077 vertices[face.vertex_idx[0]],
1078 vertices[face.vertex_idx[1]],
1079 vertices[face.vertex_idx[2]]
1080 };
1081
1082 // Check each edge.
1083 for (int face_edge_idx = 0; face_edge_idx < 3; ++face_edge_idx) {
1084 Vector<Vector2> edge_points_and_uvs = {
1085 face_vertices[face_edge_idx].point,
1086 face_vertices[(face_edge_idx + 1) % 3].point,
1087 face_vertices[face_edge_idx].uv,
1088 face_vertices[(face_edge_idx + 1) % 3].uv
1089 };
1090
1091 Vector2 edge_points[2] = {
1092 edge_points_and_uvs[0],
1093 edge_points_and_uvs[1],
1094 };
1095 Vector2 edge_uvs[2] = {
1096 edge_points_and_uvs[2],
1097 edge_points_and_uvs[3],
1098 };
1099
1100 // Check if edge has already been processed.
1101 if (processed_edges.find(edge_points_and_uvs) != -1) {
1102 continue;
1103 }
1104
1105 processed_edges.push_back(edge_points_and_uvs);
1106
1107 // First check if the ends of the segment are on the edge.
1108 Vector2 intersection_point;
1109
1110 bool on_edge = false;
1111 for (int edge_point_idx = 0; edge_point_idx < 2; ++edge_point_idx) {
1112 intersection_point = Geometry2D::get_closest_point_to_segment(p_segment_points[edge_point_idx], edge_points);
1113 if (p_segment_points[edge_point_idx].distance_squared_to(intersection_point) < vertex_snap2) {
1114 on_edge = true;
1115 break;
1116 }
1117 }
1118
1119 // Else check if the segment intersects the edge.
1120 if (on_edge || Geometry2D::segment_intersects_segment(p_segment_points[0], p_segment_points[1], edge_points[0], edge_points[1], &intersection_point)) {
1121 // Check if intersection point is an edge point.
1122 if ((edge_points[0].distance_squared_to(intersection_point) < vertex_snap2) ||
1123 (edge_points[1].distance_squared_to(intersection_point) < vertex_snap2)) {
1124 continue;
1125 }
1126
1127 // Check if edge exists, by checking if the intersecting segment is parallel to the edge.
1128 if (are_segments_parallel(p_segment_points, edge_points, vertex_snap2)) {
1129 continue;
1130 }
1131
1132 // Add the intersection point as a new vertex.
1133 Vertex2D new_vertex;
1134 new_vertex.point = intersection_point;
1135 new_vertex.uv = interpolate_segment_uv(edge_points, edge_uvs, intersection_point);
1136 int new_vertex_idx = _add_vertex(new_vertex);
1137 int opposite_vertex_idx = face.vertex_idx[(face_edge_idx + 2) % 3];
1138 _add_vertex_idx_sorted(r_segment_indices, new_vertex_idx);
1139
1140 // If new vertex snaps to opposite vertex, just delete this face.
1141 if (new_vertex_idx == opposite_vertex_idx) {
1142 faces.remove_at(face_idx);
1143 // Update index.
1144 --face_idx;
1145 break;
1146 }
1147
1148 // If opposite point is on the segment, add its index to segment indices too.
1149 Vector2 closest_point = Geometry2D::get_closest_point_to_segment(vertices[opposite_vertex_idx].point, p_segment_points);
1150 if (vertices[opposite_vertex_idx].point.distance_squared_to(closest_point) < vertex_snap2) {
1151 _add_vertex_idx_sorted(r_segment_indices, opposite_vertex_idx);
1152 }
1153
1154 // Create two new faces around the new edge and remove this face.
1155 // The new edge is the last edge.
1156 Face2D left_face;
1157 left_face.vertex_idx[0] = new_vertex_idx;
1158 left_face.vertex_idx[1] = face.vertex_idx[(face_edge_idx + 1) % 3];
1159 left_face.vertex_idx[2] = opposite_vertex_idx;
1160 Face2D right_face;
1161 right_face.vertex_idx[0] = opposite_vertex_idx;
1162 right_face.vertex_idx[1] = face.vertex_idx[face_edge_idx];
1163 right_face.vertex_idx[2] = new_vertex_idx;
1164 faces.remove_at(face_idx);
1165 faces.insert(face_idx, right_face);
1166 faces.insert(face_idx, left_face);
1167
1168 // Check against the new faces.
1169 --face_idx;
1170 break;
1171 }
1172 }
1173 }
1174}
1175
1176int CSGBrushOperation::Build2DFaces::_insert_point(const Vector2 &p_point) {
1177 int new_vertex_idx = -1;
1178
1179 for (int face_idx = 0; face_idx < faces.size(); ++face_idx) {
1180 Face2D face = faces[face_idx];
1181 Vertex2D face_vertices[3] = {
1182 vertices[face.vertex_idx[0]],
1183 vertices[face.vertex_idx[1]],
1184 vertices[face.vertex_idx[2]]
1185 };
1186 Vector2 points[3] = {
1187 face_vertices[0].point,
1188 face_vertices[1].point,
1189 face_vertices[2].point
1190 };
1191 Vector2 uvs[3] = {
1192 face_vertices[0].uv,
1193 face_vertices[1].uv,
1194 face_vertices[2].uv
1195 };
1196
1197 // Skip degenerate triangles.
1198 if (is_triangle_degenerate(points, vertex_snap2)) {
1199 continue;
1200 }
1201
1202 // Check if point is existing face vertex.
1203 for (int i = 0; i < 3; ++i) {
1204 if (face_vertices[i].point.distance_squared_to(p_point) < vertex_snap2) {
1205 return face.vertex_idx[i];
1206 }
1207 }
1208
1209 // Check if point is on each edge.
1210 bool on_edge = false;
1211 for (int face_edge_idx = 0; face_edge_idx < 3; ++face_edge_idx) {
1212 Vector2 edge_points[2] = {
1213 points[face_edge_idx],
1214 points[(face_edge_idx + 1) % 3]
1215 };
1216 Vector2 edge_uvs[2] = {
1217 uvs[face_edge_idx],
1218 uvs[(face_edge_idx + 1) % 3]
1219 };
1220
1221 Vector2 closest_point = Geometry2D::get_closest_point_to_segment(p_point, edge_points);
1222 if (p_point.distance_squared_to(closest_point) < vertex_snap2) {
1223 on_edge = true;
1224
1225 // Add the point as a new vertex.
1226 Vertex2D new_vertex;
1227 new_vertex.point = p_point;
1228 new_vertex.uv = interpolate_segment_uv(edge_points, edge_uvs, p_point);
1229 new_vertex_idx = _add_vertex(new_vertex);
1230 int opposite_vertex_idx = face.vertex_idx[(face_edge_idx + 2) % 3];
1231
1232 // If new vertex snaps to opposite vertex, just delete this face.
1233 if (new_vertex_idx == opposite_vertex_idx) {
1234 faces.remove_at(face_idx);
1235 // Update index.
1236 --face_idx;
1237 break;
1238 }
1239
1240 // Don't create degenerate triangles.
1241 Vector2 split_edge1[2] = { vertices[new_vertex_idx].point, edge_points[0] };
1242 Vector2 split_edge2[2] = { vertices[new_vertex_idx].point, edge_points[1] };
1243 Vector2 new_edge[2] = { vertices[new_vertex_idx].point, vertices[opposite_vertex_idx].point };
1244 if (are_segments_parallel(split_edge1, new_edge, vertex_snap2) &&
1245 are_segments_parallel(split_edge2, new_edge, vertex_snap2)) {
1246 break;
1247 }
1248
1249 // Create two new faces around the new edge and remove this face.
1250 // The new edge is the last edge.
1251 Face2D left_face;
1252 left_face.vertex_idx[0] = new_vertex_idx;
1253 left_face.vertex_idx[1] = face.vertex_idx[(face_edge_idx + 1) % 3];
1254 left_face.vertex_idx[2] = opposite_vertex_idx;
1255 Face2D right_face;
1256 right_face.vertex_idx[0] = opposite_vertex_idx;
1257 right_face.vertex_idx[1] = face.vertex_idx[face_edge_idx];
1258 right_face.vertex_idx[2] = new_vertex_idx;
1259 faces.remove_at(face_idx);
1260 faces.insert(face_idx, right_face);
1261 faces.insert(face_idx, left_face);
1262
1263 // Don't check against the new faces.
1264 ++face_idx;
1265
1266 // No need to check other edges.
1267 break;
1268 }
1269 }
1270
1271 // If not on an edge, check if the point is inside the face.
1272 if (!on_edge && Geometry2D::is_point_in_triangle(p_point, face_vertices[0].point, face_vertices[1].point, face_vertices[2].point)) {
1273 // Add the point as a new vertex.
1274 Vertex2D new_vertex;
1275 new_vertex.point = p_point;
1276 new_vertex.uv = interpolate_triangle_uv(points, uvs, p_point);
1277 new_vertex_idx = _add_vertex(new_vertex);
1278
1279 // Create three new faces around this point and remove this face.
1280 // The new vertex is the last vertex.
1281 for (int i = 0; i < 3; ++i) {
1282 // Don't create degenerate triangles.
1283 Vector2 new_points[3] = { points[i], points[(i + 1) % 3], vertices[new_vertex_idx].point };
1284 if (is_triangle_degenerate(new_points, vertex_snap2)) {
1285 continue;
1286 }
1287
1288 Face2D new_face;
1289 new_face.vertex_idx[0] = face.vertex_idx[i];
1290 new_face.vertex_idx[1] = face.vertex_idx[(i + 1) % 3];
1291 new_face.vertex_idx[2] = new_vertex_idx;
1292 faces.push_back(new_face);
1293 }
1294 faces.remove_at(face_idx);
1295
1296 // No need to check other faces.
1297 break;
1298 }
1299 }
1300
1301 return new_vertex_idx;
1302}
1303
1304void CSGBrushOperation::Build2DFaces::insert(const CSGBrush &p_brush, int p_face_idx) {
1305 // Find edge points that cross the plane and face points that are in the plane.
1306 // Map those points to 2D.
1307 // Create new faces from those points.
1308
1309 Vector2 points_2D[3];
1310 int points_count = 0;
1311
1312 for (int i = 0; i < 3; i++) {
1313 Vector3 point_3D = p_brush.faces[p_face_idx].vertices[i];
1314
1315 if (plane.has_point(point_3D)) {
1316 // Point is in the plane, add it.
1317 Vector3 point_2D = plane.project(point_3D);
1318 point_2D = to_2D.xform(point_2D);
1319 points_2D[points_count++] = Vector2(point_2D.x, point_2D.y);
1320
1321 } else {
1322 Vector3 next_point_3D = p_brush.faces[p_face_idx].vertices[(i + 1) % 3];
1323
1324 if (plane.has_point(next_point_3D)) {
1325 continue; // Next point is in plane, it will be added separately.
1326 }
1327 if (plane.is_point_over(point_3D) == plane.is_point_over(next_point_3D)) {
1328 continue; // Both points on the same side of the plane, ignore.
1329 }
1330
1331 // Edge crosses the plane, find and add the intersection point.
1332 Vector3 point_2D;
1333 if (plane.intersects_segment(point_3D, next_point_3D, &point_2D)) {
1334 point_2D = to_2D.xform(point_2D);
1335 points_2D[points_count++] = Vector2(point_2D.x, point_2D.y);
1336 }
1337 }
1338 }
1339
1340 Vector<int> segment_indices;
1341 Vector2 segment[2];
1342 int inserted_index[3] = { -1, -1, -1 };
1343
1344 // Insert points.
1345 for (int i = 0; i < points_count; ++i) {
1346 inserted_index[i] = _insert_point(points_2D[i]);
1347 }
1348
1349 if (points_count == 2) {
1350 // Insert a single segment.
1351 segment[0] = points_2D[0];
1352 segment[1] = points_2D[1];
1353 _find_edge_intersections(segment, segment_indices);
1354 for (int i = 0; i < 2; ++i) {
1355 _add_vertex_idx_sorted(segment_indices, inserted_index[i]);
1356 }
1357 _merge_faces(segment_indices);
1358 }
1359
1360 if (points_count == 3) {
1361 // Insert three segments.
1362 for (int edge_idx = 0; edge_idx < 3; ++edge_idx) {
1363 segment[0] = points_2D[edge_idx];
1364 segment[1] = points_2D[(edge_idx + 1) % 3];
1365 _find_edge_intersections(segment, segment_indices);
1366 for (int i = 0; i < 2; ++i) {
1367 _add_vertex_idx_sorted(segment_indices, inserted_index[(edge_idx + i) % 3]);
1368 }
1369 _merge_faces(segment_indices);
1370 segment_indices.clear();
1371 }
1372 }
1373}
1374
1375void CSGBrushOperation::Build2DFaces::addFacesToMesh(MeshMerge &r_mesh_merge, bool p_smooth, bool p_invert, const Ref<Material> &p_material, bool p_from_b) {
1376 for (int face_idx = 0; face_idx < faces.size(); ++face_idx) {
1377 Face2D face = faces[face_idx];
1378 Vertex2D fv[3] = {
1379 vertices[face.vertex_idx[0]],
1380 vertices[face.vertex_idx[1]],
1381 vertices[face.vertex_idx[2]]
1382 };
1383
1384 // Convert 2D vertex points to 3D.
1385 Vector3 points_3D[3];
1386 Vector2 uvs[3];
1387 for (int i = 0; i < 3; ++i) {
1388 Vector3 point_2D(fv[i].point.x, fv[i].point.y, 0);
1389 points_3D[i] = to_3D.xform(point_2D);
1390 uvs[i] = fv[i].uv;
1391 }
1392
1393 r_mesh_merge.add_face(points_3D, uvs, p_smooth, p_invert, p_material, p_from_b);
1394 }
1395}
1396
1397CSGBrushOperation::Build2DFaces::Build2DFaces(const CSGBrush &p_brush, int p_face_idx, float p_vertex_snap2) :
1398 vertex_snap2(p_vertex_snap2 * p_vertex_snap2) {
1399 // Convert 3D vertex points to 2D.
1400 Vector3 points_3D[3] = {
1401 p_brush.faces[p_face_idx].vertices[0],
1402 p_brush.faces[p_face_idx].vertices[1],
1403 p_brush.faces[p_face_idx].vertices[2],
1404 };
1405
1406 plane = Plane(points_3D[0], points_3D[1], points_3D[2]);
1407 to_3D.origin = points_3D[0];
1408 to_3D.basis.set_column(2, plane.normal);
1409 to_3D.basis.set_column(0, (points_3D[1] - points_3D[2]).normalized());
1410 to_3D.basis.set_column(1, to_3D.basis.get_column(0).cross(to_3D.basis.get_column(2)).normalized());
1411 to_2D = to_3D.affine_inverse();
1412
1413 Face2D face;
1414 for (int i = 0; i < 3; i++) {
1415 Vertex2D vertex;
1416 Vector3 point_2D = to_2D.xform(points_3D[i]);
1417 vertex.point.x = point_2D.x;
1418 vertex.point.y = point_2D.y;
1419 vertex.uv = p_brush.faces[p_face_idx].uvs[i];
1420 vertices.push_back(vertex);
1421 face.vertex_idx[i] = i;
1422 }
1423 faces.push_back(face);
1424}
1425
1426void CSGBrushOperation::update_faces(const CSGBrush &p_brush_a, const int p_face_idx_a, const CSGBrush &p_brush_b, const int p_face_idx_b, Build2DFaceCollection &p_collection, float p_vertex_snap) {
1427 Vector3 vertices_a[3] = {
1428 p_brush_a.faces[p_face_idx_a].vertices[0],
1429 p_brush_a.faces[p_face_idx_a].vertices[1],
1430 p_brush_a.faces[p_face_idx_a].vertices[2],
1431 };
1432
1433 Vector3 vertices_b[3] = {
1434 p_brush_b.faces[p_face_idx_b].vertices[0],
1435 p_brush_b.faces[p_face_idx_b].vertices[1],
1436 p_brush_b.faces[p_face_idx_b].vertices[2],
1437 };
1438
1439 // Don't use degenerate faces.
1440 bool has_degenerate = false;
1441 if (is_snapable(vertices_a[0], vertices_a[1], p_vertex_snap) ||
1442 is_snapable(vertices_a[0], vertices_a[2], p_vertex_snap) ||
1443 is_snapable(vertices_a[1], vertices_a[2], p_vertex_snap)) {
1444 p_collection.build2DFacesA[p_face_idx_a] = Build2DFaces();
1445 has_degenerate = true;
1446 }
1447
1448 if (is_snapable(vertices_b[0], vertices_b[1], p_vertex_snap) ||
1449 is_snapable(vertices_b[0], vertices_b[2], p_vertex_snap) ||
1450 is_snapable(vertices_b[1], vertices_b[2], p_vertex_snap)) {
1451 p_collection.build2DFacesB[p_face_idx_b] = Build2DFaces();
1452 has_degenerate = true;
1453 }
1454 if (has_degenerate) {
1455 return;
1456 }
1457
1458 // Ensure B has points either side of or in the plane of A.
1459 int over_count = 0, under_count = 0;
1460 Plane plane_a(vertices_a[0], vertices_a[1], vertices_a[2]);
1461 ERR_FAIL_COND_MSG(plane_a.normal == Vector3(), "Couldn't form plane from Brush A face.");
1462
1463 for (int i = 0; i < 3; i++) {
1464 if (plane_a.has_point(vertices_b[i])) {
1465 // In plane.
1466 } else if (plane_a.is_point_over(vertices_b[i])) {
1467 over_count++;
1468 } else {
1469 under_count++;
1470 }
1471 }
1472 // If all points under or over the plane, there is no intersection.
1473 if (over_count == 3 || under_count == 3) {
1474 return;
1475 }
1476
1477 // Ensure A has points either side of or in the plane of B.
1478 over_count = 0;
1479 under_count = 0;
1480 Plane plane_b(vertices_b[0], vertices_b[1], vertices_b[2]);
1481 ERR_FAIL_COND_MSG(plane_b.normal == Vector3(), "Couldn't form plane from Brush B face.");
1482
1483 for (int i = 0; i < 3; i++) {
1484 if (plane_b.has_point(vertices_a[i])) {
1485 // In plane.
1486 } else if (plane_b.is_point_over(vertices_a[i])) {
1487 over_count++;
1488 } else {
1489 under_count++;
1490 }
1491 }
1492 // If all points under or over the plane, there is no intersection.
1493 if (over_count == 3 || under_count == 3) {
1494 return;
1495 }
1496
1497 // Check for intersection using the SAT theorem.
1498 {
1499 // Edge pair cross product combinations.
1500 for (int i = 0; i < 3; i++) {
1501 Vector3 axis_a = (vertices_a[i] - vertices_a[(i + 1) % 3]).normalized();
1502
1503 for (int j = 0; j < 3; j++) {
1504 Vector3 axis_b = (vertices_b[j] - vertices_b[(j + 1) % 3]).normalized();
1505
1506 Vector3 sep_axis = axis_a.cross(axis_b);
1507 if (sep_axis == Vector3()) {
1508 continue; //colineal
1509 }
1510 sep_axis.normalize();
1511
1512 real_t min_a = 1e20, max_a = -1e20;
1513 real_t min_b = 1e20, max_b = -1e20;
1514
1515 for (int k = 0; k < 3; k++) {
1516 real_t d = sep_axis.dot(vertices_a[k]);
1517 min_a = MIN(min_a, d);
1518 max_a = MAX(max_a, d);
1519 d = sep_axis.dot(vertices_b[k]);
1520 min_b = MIN(min_b, d);
1521 max_b = MAX(max_b, d);
1522 }
1523
1524 min_b -= (max_a - min_a) * 0.5;
1525 max_b += (max_a - min_a) * 0.5;
1526
1527 real_t dmin = min_b - (min_a + max_a) * 0.5;
1528 real_t dmax = max_b - (min_a + max_a) * 0.5;
1529
1530 if (dmin > CMP_EPSILON || dmax < -CMP_EPSILON) {
1531 return; // Does not contain zero, so they don't overlap.
1532 }
1533 }
1534 }
1535 }
1536
1537 // If we're still here, the faces probably intersect, so add new faces.
1538 if (!p_collection.build2DFacesA.has(p_face_idx_a)) {
1539 p_collection.build2DFacesA[p_face_idx_a] = Build2DFaces(p_brush_a, p_face_idx_a, p_vertex_snap);
1540 }
1541 p_collection.build2DFacesA[p_face_idx_a].insert(p_brush_b, p_face_idx_b);
1542
1543 if (!p_collection.build2DFacesB.has(p_face_idx_b)) {
1544 p_collection.build2DFacesB[p_face_idx_b] = Build2DFaces(p_brush_b, p_face_idx_b, p_vertex_snap);
1545 }
1546 p_collection.build2DFacesB[p_face_idx_b].insert(p_brush_a, p_face_idx_a);
1547}
1548