1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  */
16 
17 #pragma once
18 
19 /** \file
20  * \ingroup bli
21  */
22 
23 /* Axis-aligned bounding box */
24 typedef struct {
25   float bmin[3], bmax[3];
26 } BB;
27 
28 /* Axis-aligned bounding box with centroid */
29 typedef struct {
30   float bmin[3], bmax[3], bcentroid[3];
31 } BBC;
32 
33 /* Note: this structure is getting large, might want to split it into
34  * union'd structs */
35 struct PBVHNode {
36   /* Opaque handle for drawing code */
37   struct GPU_PBVH_Buffers *draw_buffers;
38 
39   /* Voxel bounds */
40   BB vb;
41   BB orig_vb;
42 
43   /* For internal nodes, the offset of the children in the PBVH
44    * 'nodes' array. */
45   int children_offset;
46 
47   /* Pointer into the PBVH prim_indices array and the number of
48    * primitives used by this leaf node.
49    *
50    * Used for leaf nodes in both mesh- and multires-based PBVHs.
51    */
52   int *prim_indices;
53   unsigned int totprim;
54 
55   /* Array of indices into the mesh's MVert array. Contains the
56    * indices of all vertices used by faces that are within this
57    * node's bounding box.
58    *
59    * Note that a vertex might be used by a multiple faces, and
60    * these faces might be in different leaf nodes. Such a vertex
61    * will appear in the vert_indices array of each of those leaf
62    * nodes.
63    *
64    * In order to support cases where you want access to multiple
65    * nodes' vertices without duplication, the vert_indices array
66    * is ordered such that the first part of the array, up to
67    * index 'uniq_verts', contains "unique" vertex indices. These
68    * vertices might not be truly unique to this node, but if
69    * they appear in another node's vert_indices array, they will
70    * be above that node's 'uniq_verts' value.
71    *
72    * Used for leaf nodes in a mesh-based PBVH (not multires.)
73    */
74   const int *vert_indices;
75   unsigned int uniq_verts, face_verts;
76 
77   /* An array mapping face corners into the vert_indices
78    * array. The array is sized to match 'totprim', and each of
79    * the face's corners gets an index into the vert_indices
80    * array, in the same order as the corners in the original
81    * MLoopTri.
82    *
83    * Used for leaf nodes in a mesh-based PBVH (not multires.)
84    */
85   const int (*face_vert_indices)[3];
86 
87   /* Indicates whether this node is a leaf or not; also used for
88    * marking various updates that need to be applied. */
89   PBVHNodeFlags flag : 16;
90 
91   /* Used for raycasting: how close bb is to the ray point. */
92   float tmin;
93 
94   /* Scalar displacements for sculpt mode's layer brush. */
95   float *layer_disp;
96 
97   int proxy_count;
98   PBVHProxyNode *proxies;
99 
100   /* Dyntopo */
101   GSet *bm_faces;
102   GSet *bm_unique_verts;
103   GSet *bm_other_verts;
104   float (*bm_orco)[3];
105   int (*bm_ortri)[3];
106   int bm_tot_ortri;
107 
108   /* Used to store the brush color during a stroke and composite it over the original color */
109   PBVHColorBufferNode color_buffer;
110 };
111 
112 typedef enum {
113   PBVH_DYNTOPO_SMOOTH_SHADING = 1,
114 } PBVHFlags;
115 
116 typedef struct PBVHBMeshLog PBVHBMeshLog;
117 
118 struct PBVH {
119   PBVHType type;
120   PBVHFlags flags;
121 
122   PBVHNode *nodes;
123   int node_mem_count, totnode;
124 
125   int *prim_indices;
126   int totprim;
127   int totvert;
128 
129   int leaf_limit;
130 
131   /* Mesh data */
132   const struct Mesh *mesh;
133   MVert *verts;
134   const MPoly *mpoly;
135   const MLoop *mloop;
136   const MLoopTri *looptri;
137   CustomData *vdata;
138   CustomData *ldata;
139   CustomData *pdata;
140 
141   int face_sets_color_seed;
142   int face_sets_color_default;
143   int *face_sets;
144 
145   /* Grid Data */
146   CCGKey gridkey;
147   CCGElem **grids;
148   void **gridfaces;
149   const DMFlagMat *grid_flag_mats;
150   int totgrid;
151   BLI_bitmap **grid_hidden;
152 
153   /* Only used during BVH build and update,
154    * don't need to remain valid after */
155   BLI_bitmap *vert_bitmap;
156 
157 #ifdef PERFCNTRS
158   int perf_modified;
159 #endif
160 
161   /* flag are verts/faces deformed */
162   bool deformed;
163   bool show_mask;
164   bool show_face_sets;
165   bool respect_hide;
166 
167   /* Dynamic topology */
168   BMesh *bm;
169   float bm_max_edge_len;
170   float bm_min_edge_len;
171   int cd_vert_node_offset;
172   int cd_face_node_offset;
173 
174   float planes[6][4];
175   int num_planes;
176 
177   struct BMLog *bm_log;
178   struct SubdivCCG *subdiv_ccg;
179 };
180 
181 /* pbvh.c */
182 void BB_reset(BB *bb);
183 void BB_expand(BB *bb, const float co[3]);
184 void BB_expand_with_bb(BB *bb, BB *bb2);
185 void BBC_update_centroid(BBC *bbc);
186 int BB_widest_axis(const BB *bb);
187 void pbvh_grow_nodes(PBVH *bvh, int totnode);
188 bool ray_face_intersection_quad(const float ray_start[3],
189                                 struct IsectRayPrecalc *isect_precalc,
190                                 const float *t0,
191                                 const float *t1,
192                                 const float *t2,
193                                 const float *t3,
194                                 float *depth);
195 bool ray_face_intersection_tri(const float ray_start[3],
196                                struct IsectRayPrecalc *isect_precalc,
197                                const float *t0,
198                                const float *t1,
199                                const float *t2,
200                                float *depth);
201 
202 bool ray_face_nearest_quad(const float ray_start[3],
203                            const float ray_normal[3],
204                            const float *t0,
205                            const float *t1,
206                            const float *t2,
207                            const float *t3,
208                            float *r_depth,
209                            float *r_dist_sq);
210 bool ray_face_nearest_tri(const float ray_start[3],
211                           const float ray_normal[3],
212                           const float *t0,
213                           const float *t1,
214                           const float *t2,
215                           float *r_depth,
216                           float *r_dist_sq);
217 
218 void pbvh_update_BB_redraw(PBVH *bvh, PBVHNode **nodes, int totnode, int flag);
219 
220 /* pbvh_bmesh.c */
221 bool pbvh_bmesh_node_raycast(PBVHNode *node,
222                              const float ray_start[3],
223                              const float ray_normal[3],
224                              struct IsectRayPrecalc *isect_precalc,
225                              float *dist,
226                              bool use_original,
227                              int *r_active_vertex_index,
228                              float *r_face_normal);
229 bool pbvh_bmesh_node_nearest_to_ray(PBVHNode *node,
230                                     const float ray_start[3],
231                                     const float ray_normal[3],
232                                     float *depth,
233                                     float *dist_sq,
234                                     bool use_original);
235 
236 void pbvh_bmesh_normals_update(PBVHNode **nodes, int totnode);
237