Blender  V3.3
Projections.cpp
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #ifdef WITH_CXX_GUARDEDALLOC
4 # include "MEM_guardedalloc.h"
5 #endif
6 
7 #include "Projections.h"
8 #include <math.h>
9 
10 const int vertmap[8][3] = {
11  {0, 0, 0},
12  {0, 0, 1},
13  {0, 1, 0},
14  {0, 1, 1},
15  {1, 0, 0},
16  {1, 0, 1},
17  {1, 1, 0},
18  {1, 1, 1},
19 };
20 
21 const int centmap[3][3][3][2] = {
22  {{{0, 0}, {0, 1}, {1, 1}}, {{0, 2}, {0, 3}, {1, 3}}, {{2, 2}, {2, 3}, {3, 3}}},
23 
24  {{{0, 4}, {0, 5}, {1, 5}}, {{0, 6}, {0, 7}, {1, 7}}, {{2, 6}, {2, 7}, {3, 7}}},
25 
26  {{{4, 4}, {4, 5}, {5, 5}}, {{4, 6}, {4, 7}, {5, 7}}, {{6, 6}, {6, 7}, {7, 7}}}};
27 
28 const int edgemap[12][2] = {
29  {0, 4},
30  {1, 5},
31  {2, 6},
32  {3, 7},
33  {0, 2},
34  {1, 3},
35  {4, 6},
36  {5, 7},
37  {0, 1},
38  {2, 3},
39  {4, 5},
40  {6, 7},
41 };
42 
43 const int facemap[6][4] = {
44  {0, 1, 2, 3},
45  {4, 5, 6, 7},
46  {0, 1, 4, 5},
47  {2, 3, 6, 7},
48  {0, 2, 4, 6},
49  {1, 3, 5, 7},
50 };
51 
55 static void crossProduct(int64_t res[3], const int64_t a[3], const int64_t b[3])
56 {
57  res[0] = a[1] * b[2] - a[2] * b[1];
58  res[1] = a[2] * b[0] - a[0] * b[2];
59  res[2] = a[0] * b[1] - a[1] * b[0];
60 }
61 
62 static void crossProduct(double res[3], const double a[3], const double b[3])
63 {
64  res[0] = a[1] * b[2] - a[2] * b[1];
65  res[1] = a[2] * b[0] - a[0] * b[2];
66  res[2] = a[0] * b[1] - a[1] * b[0];
67 }
68 
72 static int64_t dotProduct(const int64_t a[3], const int64_t b[3])
73 {
74  return a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
75 }
76 
77 static void normalize(double a[3])
78 {
79  double mag = a[0] * a[0] + a[1] * a[1] + a[2] * a[2];
80  if (mag > 0) {
81  mag = sqrt(mag);
82  a[0] /= mag;
83  a[1] /= mag;
84  a[2] /= mag;
85  }
86 }
87 
88 /* Create projection axes for cube+triangle intersection testing.
89  * 0, 1, 2: cube face normals
90  *
91  * 3: triangle normal
92  *
93  * 4, 5, 6,
94  * 7, 8, 9,
95  * 10, 11, 12: cross of each triangle edge vector with each cube
96  * face normal
97  */
98 static void create_projection_axes(int64_t axes[NUM_AXES][3], const int64_t tri[3][3])
99 {
100  /* Cube face normals */
101  axes[0][0] = 1;
102  axes[0][1] = 0;
103  axes[0][2] = 0;
104  axes[1][0] = 0;
105  axes[1][1] = 1;
106  axes[1][2] = 0;
107  axes[2][0] = 0;
108  axes[2][1] = 0;
109  axes[2][2] = 1;
110 
111  /* Get triangle edge vectors */
112  int64_t tri_edges[3][3];
113  for (int i = 0; i < 3; i++) {
114  for (int j = 0; j < 3; j++)
115  tri_edges[i][j] = tri[(i + 1) % 3][j] - tri[i][j];
116  }
117 
118  /* Triangle normal */
119  crossProduct(axes[3], tri_edges[0], tri_edges[1]);
120 
121  // Face edges and triangle edges
122  int ct = 4;
123  for (int i = 0; i < 3; i++) {
124  for (int j = 0; j < 3; j++) {
125  crossProduct(axes[ct], axes[j], tri_edges[i]);
126  ct++;
127  }
128  }
129 }
130 
135  int64_t tri[3][3],
136  int64_t /*error*/,
137  int triind)
138 {
139  int i;
141  inherit->index = triind;
142 
143  int64_t axes[NUM_AXES][3];
144  create_projection_axes(axes, tri);
145 
146  /* Normalize face normal and store */
147  double dedge1[] = {(double)tri[1][0] - (double)tri[0][0],
148  (double)tri[1][1] - (double)tri[0][1],
149  (double)tri[1][2] - (double)tri[0][2]};
150  double dedge2[] = {(double)tri[2][0] - (double)tri[1][0],
151  (double)tri[2][1] - (double)tri[1][1],
152  (double)tri[2][2] - (double)tri[1][2]};
153  crossProduct(inherit->norm, dedge1, dedge2);
155 
156  int64_t cubeedge[3][3];
157  for (i = 0; i < 3; i++) {
158  for (int j = 0; j < 3; j++) {
159  cubeedge[i][j] = 0;
160  }
161  cubeedge[i][i] = cube[1][i] - cube[0][i];
162  }
163 
164  /* Project the cube on to each axis */
165  for (int axis = 0; axis < NUM_AXES; axis++) {
166  CubeProjection &cube_proj = cubeProj[axis];
167 
168  /* Origin */
169  cube_proj.origin = dotProduct(axes[axis], cube[0]);
170 
171  /* 3 direction vectors */
172  for (i = 0; i < 3; i++)
173  cube_proj.edges[i] = dotProduct(axes[axis], cubeedge[i]);
174 
175  /* Offsets of 2 ends of cube projection */
176  int64_t max = 0;
177  int64_t min = 0;
178  for (i = 1; i < 8; i++) {
179  int64_t proj = (vertmap[i][0] * cube_proj.edges[0] + vertmap[i][1] * cube_proj.edges[1] +
180  vertmap[i][2] * cube_proj.edges[2]);
181  if (proj > max) {
182  max = proj;
183  }
184  if (proj < min) {
185  min = proj;
186  }
187  }
188  cube_proj.min = min;
189  cube_proj.max = max;
190  }
191 
192  /* Project the triangle on to each axis */
193  for (int axis = 0; axis < NUM_AXES; axis++) {
194  const int64_t vts[3] = {dotProduct(axes[axis], tri[0]),
195  dotProduct(axes[axis], tri[1]),
196  dotProduct(axes[axis], tri[2])};
197 
198  // Triangle
199  inherit->tri_proj[axis][0] = vts[0];
200  inherit->tri_proj[axis][1] = vts[0];
201  for (i = 1; i < 3; i++) {
202  if (vts[i] < inherit->tri_proj[axis][0])
203  inherit->tri_proj[axis][0] = vts[i];
204 
205  if (vts[i] > inherit->tri_proj[axis][1])
206  inherit->tri_proj[axis][1] = vts[i];
207  }
208  }
209 }
210 
216 {
217  // Copy inheritable projections
218  this->inherit = parent->inherit;
219 
220  // Shrink cube projections
221  for (int i = 0; i < NUM_AXES; i++) {
222  cubeProj[i].origin = parent->cubeProj[i].origin;
223 
224  for (int j = 0; j < 3; j++)
225  cubeProj[i].edges[j] = parent->cubeProj[i].edges[j] >> 1;
226 
227  cubeProj[i].min = parent->cubeProj[i].min >> 1;
228  cubeProj[i].max = parent->cubeProj[i].max >> 1;
229  }
230 }
231 
233 {
234  int i, j, k;
235  int bmask[3][2] = {{0, 0}, {0, 0}, {0, 0}};
236  unsigned char boxmask = 0;
237  int64_t child_len = cubeProj[0].edges[0] >> 1;
238 
239  for (i = 0; i < 3; i++) {
240  int64_t mid = cubeProj[i].origin + child_len;
241 
242  // Check bounding box
243  if (mid >= inherit->tri_proj[i][0]) {
244  bmask[i][0] = 1;
245  }
246  if (mid < inherit->tri_proj[i][1]) {
247  bmask[i][1] = 1;
248  }
249  }
250 
251  // Fill in masks
252  int ct = 0;
253  for (i = 0; i < 2; i++) {
254  for (j = 0; j < 2; j++) {
255  for (k = 0; k < 2; k++) {
256  boxmask |= ((bmask[0][i] & bmask[1][j] & bmask[2][k]) << ct);
257  ct++;
258  }
259  }
260  }
261 
262  // Return bounding box masks
263  return boxmask;
264 }
265 
269 void CubeTriangleIsect::shift(int off[3])
270 {
271  for (int i = 0; i < NUM_AXES; i++) {
272  cubeProj[i].origin += (off[0] * cubeProj[i].edges[0] + off[1] * cubeProj[i].edges[1] +
273  off[2] * cubeProj[i].edges[2]);
274  }
275 }
276 
281 {
282  for (int i = 0; i < NUM_AXES; i++) {
283  /*
284  int64_t proj0 = cubeProj[i][0] +
285  vertmap[inherit->cubeEnds[i][0]][0] * cubeProj[i][1] +
286  vertmap[inherit->cubeEnds[i][0]][1] * cubeProj[i][2] +
287  vertmap[inherit->cubeEnds[i][0]][2] * cubeProj[i][3] ;
288  int64_t proj1 = cubeProj[i][0] +
289  vertmap[inherit->cubeEnds[i][1]][0] * cubeProj[i][1] +
290  vertmap[inherit->cubeEnds[i][1]][1] * cubeProj[i][2] +
291  vertmap[inherit->cubeEnds[i][1]][2] * cubeProj[i][3] ;
292  */
293 
294  int64_t proj0 = cubeProj[i].origin + cubeProj[i].min;
295  int64_t proj1 = cubeProj[i].origin + cubeProj[i].max;
296 
297  if (proj0 > inherit->tri_proj[i][1] || proj1 < inherit->tri_proj[i][0]) {
298  return 0;
299  }
300  }
301 
302  return 1;
303 }
304 
306 {
307  for (int i = 0; i < NUM_AXES; i++) {
308 
309  int64_t proj0 = cubeProj[i].origin;
310  int64_t proj1 = cubeProj[i].origin + cubeProj[i].edges[edgeInd];
311 
312  if (proj0 < proj1) {
313  if (proj0 > inherit->tri_proj[i][1] || proj1 < inherit->tri_proj[i][0]) {
314  return 0;
315  }
316  }
317  else {
318  if (proj1 > inherit->tri_proj[i][1] || proj0 < inherit->tri_proj[i][0]) {
319  return 0;
320  }
321  }
322  }
323 
324  // printf( "Intersecting: %d %d\n", edgemap[edgeInd][0], edgemap[edgeInd][1] ) ;
325  return 1;
326 }
327 
329 {
330  int i = 3;
331 
332  int64_t proj0 = cubeProj[i].origin;
333  int64_t proj1 = cubeProj[i].origin + cubeProj[i].edges[edgeInd];
334  int64_t proj2 = inherit->tri_proj[i][1];
335  int64_t d = proj1 - proj0;
336  double alpha;
337 
338  if (d == 0)
339  alpha = 0.5;
340  else {
341  alpha = (double)((proj2 - proj0)) / (double)d;
342 
343  if (alpha < 0 || alpha > 1)
344  alpha = 0.5;
345  }
346 
347  return (float)alpha;
348 }
sqrt(x)+1/max(0
typedef double(DMatrix)[4][4]
Read Guarded memory(de)allocation.
const int edgemap[12][2]
Definition: Projections.cpp:28
const int centmap[3][3][3][2]
Definition: Projections.cpp:21
static int64_t dotProduct(const int64_t a[3], const int64_t b[3])
Definition: Projections.cpp:72
const int vertmap[8][3]
Definition: Projections.cpp:10
static void create_projection_axes(int64_t axes[NUM_AXES][3], const int64_t tri[3][3])
Definition: Projections.cpp:98
const int facemap[6][4]
Definition: Projections.cpp:43
static void crossProduct(int64_t res[3], const int64_t a[3], const int64_t b[3])
Definition: Projections.cpp:55
static void normalize(double a[3])
Definition: Projections.cpp:77
#define NUM_AXES
Definition: Projections.h:42
void shift(int off[3])
int isIntersecting() const
int isIntersectingPrimary(int edgeInd) const
CubeProjection cubeProj[NUM_AXES]
Projections of the cube vertices.
Definition: Projections.h:75
unsigned char getBoxMask()
TriangleProjection * inherit
Inheritable portion.
Definition: Projections.h:72
float getIntersectionPrimary(int edgeInd) const
static unsigned a[3]
Definition: RandGen.cpp:78
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
#define min(a, b)
Definition: sort.c:35
__int64 int64_t
Definition: stdint.h:89
int64_t origin
Definition: Projections.h:61
int64_t edges[3]
Definition: Projections.h:62
int64_t tri_proj[NUM_AXES][2]
Projections of triangle (min and max)
Definition: Projections.h:49
double norm[3]
Normal of the triangle.
Definition: Projections.h:52
int index
Index of polygon.
Definition: Projections.h:55
float max