1/**************************************************************************/
2/* csg.h */
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#ifndef CSG_H
32#define CSG_H
33
34#include "core/math/aabb.h"
35#include "core/math/plane.h"
36#include "core/math/transform_3d.h"
37#include "core/math/vector2.h"
38#include "core/math/vector3.h"
39#include "core/object/ref_counted.h"
40#include "core/templates/list.h"
41#include "core/templates/oa_hash_map.h"
42#include "core/templates/vector.h"
43#include "scene/resources/material.h"
44
45struct CSGBrush {
46 struct Face {
47 Vector3 vertices[3];
48 Vector2 uvs[3];
49 AABB aabb;
50 bool smooth = false;
51 bool invert = false;
52 int material = 0;
53 };
54
55 Vector<Face> faces;
56 Vector<Ref<Material>> materials;
57
58 inline void _regen_face_aabbs();
59
60 // Create a brush from faces.
61 void 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_invert_faces);
62 void copy_from(const CSGBrush &p_brush, const Transform3D &p_xform);
63};
64
65struct CSGBrushOperation {
66 enum Operation {
67 OPERATION_UNION,
68 OPERATION_INTERSECTION,
69 OPERATION_SUBTRACTION,
70 };
71
72 void merge_brushes(Operation p_operation, const CSGBrush &p_brush_a, const CSGBrush &p_brush_b, CSGBrush &r_merged_brush, float p_vertex_snap);
73
74 struct MeshMerge {
75 struct Face {
76 bool from_b = false;
77 bool inside = false;
78 int points[3] = {};
79 Vector2 uvs[3];
80 bool smooth = false;
81 bool invert = false;
82 int material_idx = 0;
83 };
84
85 struct FaceBVH {
86 int face = 0;
87 int left = 0;
88 int right = 0;
89 int next = 0;
90 Vector3 center;
91 AABB aabb;
92 };
93
94 struct FaceBVHCmpX {
95 _FORCE_INLINE_ bool operator()(const FaceBVH *p_left, const FaceBVH *p_right) const {
96 return p_left->center.x < p_right->center.x;
97 }
98 };
99
100 struct FaceBVHCmpY {
101 _FORCE_INLINE_ bool operator()(const FaceBVH *p_left, const FaceBVH *p_right) const {
102 return p_left->center.y < p_right->center.y;
103 }
104 };
105 struct FaceBVHCmpZ {
106 _FORCE_INLINE_ bool operator()(const FaceBVH *p_left, const FaceBVH *p_right) const {
107 return p_left->center.z < p_right->center.z;
108 }
109 };
110
111 struct VertexKey {
112 int32_t x, y, z;
113 _FORCE_INLINE_ bool operator<(const VertexKey &p_key) const {
114 if (x == p_key.x) {
115 if (y == p_key.y) {
116 return z < p_key.z;
117 } else {
118 return y < p_key.y;
119 }
120 } else {
121 return x < p_key.x;
122 }
123 }
124
125 _FORCE_INLINE_ bool operator==(const VertexKey &p_key) const {
126 return (x == p_key.x && y == p_key.y && z == p_key.z);
127 }
128 };
129
130 struct VertexKeyHash {
131 static _FORCE_INLINE_ uint32_t hash(const VertexKey &p_vk) {
132 uint32_t h = hash_murmur3_one_32(p_vk.x);
133 h = hash_murmur3_one_32(p_vk.y, h);
134 h = hash_murmur3_one_32(p_vk.z, h);
135 return h;
136 }
137 };
138 struct Intersection {
139 bool found = false;
140 real_t conormal = FLT_MAX;
141 real_t distance_squared = FLT_MAX;
142 real_t origin_angle = FLT_MAX;
143 };
144
145 struct IntersectionDistance {
146 bool is_conormal;
147 real_t distance_squared;
148 };
149
150 Vector<Vector3> points;
151 Vector<Face> faces;
152 HashMap<Ref<Material>, int> materials;
153 HashMap<Vector3, int> vertex_map;
154 OAHashMap<VertexKey, int, VertexKeyHash> snap_cache;
155 float vertex_snap = 0.0;
156
157 inline void _add_distance(List<IntersectionDistance> &r_intersectionsA, List<IntersectionDistance> &r_intersectionsB, bool p_from_B, real_t p_distance, bool p_is_conormal) const;
158 inline bool _bvh_inside(FaceBVH *r_facebvhptr, int p_max_depth, int p_bvh_first, int p_face_idx) const;
159 inline int _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);
160
161 void 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);
162 void mark_inside_faces();
163 };
164
165 struct Build2DFaces {
166 struct Vertex2D {
167 Vector2 point;
168 Vector2 uv;
169 };
170
171 struct Face2D {
172 int vertex_idx[3] = {};
173 };
174
175 Vector<Vertex2D> vertices;
176 Vector<Face2D> faces;
177 Plane plane;
178 Transform3D to_2D;
179 Transform3D to_3D;
180 float vertex_snap2 = 0.0;
181
182 inline int _get_point_idx(const Vector2 &p_point);
183 inline int _add_vertex(const Vertex2D &p_vertex);
184 inline void _add_vertex_idx_sorted(Vector<int> &r_vertex_indices, int p_new_vertex_index);
185 inline void _merge_faces(const Vector<int> &p_segment_indices);
186 inline void _find_edge_intersections(const Vector2 p_segment_points[2], Vector<int> &r_segment_indices);
187 inline int _insert_point(const Vector2 &p_point);
188
189 void insert(const CSGBrush &p_brush, int p_brush_face);
190 void addFacesToMesh(MeshMerge &r_mesh_merge, bool p_smooth, bool p_invert, const Ref<Material> &p_material, bool p_from_b);
191
192 Build2DFaces() {}
193 Build2DFaces(const CSGBrush &p_brush, int p_brush_face, float p_vertex_snap2);
194 };
195
196 struct Build2DFaceCollection {
197 HashMap<int, Build2DFaces> build2DFacesA;
198 HashMap<int, Build2DFaces> build2DFacesB;
199 };
200
201 void 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);
202};
203
204#endif // CSG_H
205