Blender  V3.3
mathutils_geometry.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
7 #include <Python.h>
8 
9 #include "mathutils.h"
10 #include "mathutils_geometry.h"
11 
12 /* Used for PolyFill */
13 #ifndef MATH_STANDALONE /* define when building outside blender */
14 # include "BKE_curve.h"
15 # include "BKE_displist.h"
16 # include "BLI_blenlib.h"
17 # include "BLI_boxpack_2d.h"
18 # include "BLI_convexhull_2d.h"
19 # include "BLI_delaunay_2d.h"
20 # include "MEM_guardedalloc.h"
21 #endif
22 
23 #include "BLI_math.h"
24 #include "BLI_utildefines.h"
25 
26 #include "../generic/py_capi_utils.h"
27 #include "../generic/python_utildefines.h"
28 
29 /*-------------------------DOC STRINGS ---------------------------*/
30 PyDoc_STRVAR(M_Geometry_doc, "The Blender geometry module");
31 
32 /* ---------------------------------INTERSECTION FUNCTIONS-------------------- */
33 
34 PyDoc_STRVAR(M_Geometry_intersect_ray_tri_doc,
35  ".. function:: intersect_ray_tri(v1, v2, v3, ray, orig, clip=True)\n"
36  "\n"
37  " Returns the intersection between a ray and a triangle, if possible, returns None "
38  "otherwise.\n"
39  "\n"
40  " :arg v1: Point1\n"
41  " :type v1: :class:`mathutils.Vector`\n"
42  " :arg v2: Point2\n"
43  " :type v2: :class:`mathutils.Vector`\n"
44  " :arg v3: Point3\n"
45  " :type v3: :class:`mathutils.Vector`\n"
46  " :arg ray: Direction of the projection\n"
47  " :type ray: :class:`mathutils.Vector`\n"
48  " :arg orig: Origin\n"
49  " :type orig: :class:`mathutils.Vector`\n"
50  " :arg clip: When False, don't restrict the intersection to the area of the "
51  "triangle, use the infinite plane defined by the triangle.\n"
52  " :type clip: boolean\n"
53  " :return: The point of intersection or None if no intersection is found\n"
54  " :rtype: :class:`mathutils.Vector` or None\n");
55 static PyObject *M_Geometry_intersect_ray_tri(PyObject *UNUSED(self), PyObject *args)
56 {
57  const char *error_prefix = "intersect_ray_tri";
58  PyObject *py_ray, *py_ray_off, *py_tri[3];
59  float dir[3], orig[3], tri[3][3], e1[3], e2[3], pvec[3], tvec[3], qvec[3];
60  float det, inv_det, u, v, t;
61  bool clip = true;
62  int i;
63 
64  if (!PyArg_ParseTuple(args,
65  "OOOOO|O&:intersect_ray_tri",
66  UNPACK3_EX(&, py_tri, ),
67  &py_ray,
68  &py_ray_off,
70  &clip)) {
71  return NULL;
72  }
73 
74  if (((mathutils_array_parse(dir, 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_ray, error_prefix) !=
75  -1) &&
77  orig, 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_ray_off, error_prefix) != -1)) == 0) {
78  return NULL;
79  }
80 
81  for (i = 0; i < ARRAY_SIZE(tri); i++) {
83  tri[i], 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_tri[i], error_prefix) == -1) {
84  return NULL;
85  }
86  }
87 
88  normalize_v3(dir);
89 
90  /* find vectors for two edges sharing v1 */
91  sub_v3_v3v3(e1, tri[1], tri[0]);
92  sub_v3_v3v3(e2, tri[2], tri[0]);
93 
94  /* begin calculating determinant - also used to calculated U parameter */
95  cross_v3_v3v3(pvec, dir, e2);
96 
97  /* if determinant is near zero, ray lies in plane of triangle */
98  det = dot_v3v3(e1, pvec);
99 
100  if (det > -0.000001f && det < 0.000001f) {
101  Py_RETURN_NONE;
102  }
103 
104  inv_det = 1.0f / det;
105 
106  /* calculate distance from v1 to ray origin */
107  sub_v3_v3v3(tvec, orig, tri[0]);
108 
109  /* calculate U parameter and test bounds */
110  u = dot_v3v3(tvec, pvec) * inv_det;
111  if (clip && (u < 0.0f || u > 1.0f)) {
112  Py_RETURN_NONE;
113  }
114 
115  /* prepare to test the V parameter */
116  cross_v3_v3v3(qvec, tvec, e1);
117 
118  /* calculate V parameter and test bounds */
119  v = dot_v3v3(dir, qvec) * inv_det;
120 
121  if (clip && (v < 0.0f || u + v > 1.0f)) {
122  Py_RETURN_NONE;
123  }
124 
125  /* calculate t, ray intersects triangle */
126  t = dot_v3v3(e2, qvec) * inv_det;
127 
128  /* ray hit behind */
129  if (t < 0.0f) {
130  Py_RETURN_NONE;
131  }
132 
133  mul_v3_fl(dir, t);
134  add_v3_v3v3(pvec, orig, dir);
135 
136  return Vector_CreatePyObject(pvec, 3, NULL);
137 }
138 
139 /* Line-Line intersection using algorithm from mathworld.wolfram.com */
140 
141 PyDoc_STRVAR(M_Geometry_intersect_line_line_doc,
142  ".. function:: intersect_line_line(v1, v2, v3, v4)\n"
143  "\n"
144  " Returns a tuple with the points on each line respectively closest to the other.\n"
145  "\n"
146  " :arg v1: First point of the first line\n"
147  " :type v1: :class:`mathutils.Vector`\n"
148  " :arg v2: Second point of the first line\n"
149  " :type v2: :class:`mathutils.Vector`\n"
150  " :arg v3: First point of the second line\n"
151  " :type v3: :class:`mathutils.Vector`\n"
152  " :arg v4: Second point of the second line\n"
153  " :type v4: :class:`mathutils.Vector`\n"
154  " :rtype: tuple of :class:`mathutils.Vector`'s\n");
155 static PyObject *M_Geometry_intersect_line_line(PyObject *UNUSED(self), PyObject *args)
156 {
157  const char *error_prefix = "intersect_line_line";
158  PyObject *tuple;
159  PyObject *py_lines[4];
160  float lines[4][3], i1[3], i2[3];
161  int ix_vec_num;
162  int result;
163 
164  if (!PyArg_ParseTuple(args, "OOOO:intersect_line_line", UNPACK4_EX(&, py_lines, ))) {
165  return NULL;
166  }
167 
168  if ((((ix_vec_num = mathutils_array_parse(
169  lines[0], 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_lines[0], error_prefix)) != -1) &&
170  (mathutils_array_parse(lines[1],
171  ix_vec_num,
172  ix_vec_num | MU_ARRAY_SPILL | MU_ARRAY_ZERO,
173  py_lines[1],
174  error_prefix) != -1) &&
175  (mathutils_array_parse(lines[2],
176  ix_vec_num,
177  ix_vec_num | MU_ARRAY_SPILL | MU_ARRAY_ZERO,
178  py_lines[2],
179  error_prefix) != -1) &&
180  (mathutils_array_parse(lines[3],
181  ix_vec_num,
182  ix_vec_num | MU_ARRAY_SPILL | MU_ARRAY_ZERO,
183  py_lines[3],
184  error_prefix) != -1)) == 0) {
185  return NULL;
186  }
187 
188  /* Zero 3rd axis of 2D vectors. */
189  if (ix_vec_num == 2) {
190  lines[1][2] = 0.0f;
191  lines[2][2] = 0.0f;
192  lines[3][2] = 0.0f;
193  }
194 
195  result = isect_line_line_v3(UNPACK4(lines), i1, i2);
196  /* The return-code isn't exposed,
197  * this way we can check know how close the lines are. */
198  if (result == 1) {
199  closest_to_line_v3(i2, i1, lines[2], lines[3]);
200  }
201 
202  if (result == 0) {
203  /* Collinear. */
204  Py_RETURN_NONE;
205  }
206 
207  tuple = PyTuple_New(2);
208  PyTuple_SET_ITEMS(tuple,
209  Vector_CreatePyObject(i1, ix_vec_num, NULL),
210  Vector_CreatePyObject(i2, ix_vec_num, NULL));
211  return tuple;
212 }
213 
214 /* Line-Line intersection using algorithm from mathworld.wolfram.com */
215 
217  M_Geometry_intersect_sphere_sphere_2d_doc,
218  ".. function:: intersect_sphere_sphere_2d(p_a, radius_a, p_b, radius_b)\n"
219  "\n"
220  " Returns 2 points on between intersecting circles.\n"
221  "\n"
222  " :arg p_a: Center of the first circle\n"
223  " :type p_a: :class:`mathutils.Vector`\n"
224  " :arg radius_a: Radius of the first circle\n"
225  " :type radius_a: float\n"
226  " :arg p_b: Center of the second circle\n"
227  " :type p_b: :class:`mathutils.Vector`\n"
228  " :arg radius_b: Radius of the second circle\n"
229  " :type radius_b: float\n"
230  " :rtype: tuple of :class:`mathutils.Vector`'s or None when there is no intersection\n");
231 static PyObject *M_Geometry_intersect_sphere_sphere_2d(PyObject *UNUSED(self), PyObject *args)
232 {
233  const char *error_prefix = "intersect_sphere_sphere_2d";
234  PyObject *ret;
235  PyObject *py_v_a, *py_v_b;
236  float v_a[2], v_b[2];
237  float rad_a, rad_b;
238  float v_ab[2];
239  float dist;
240 
241  if (!PyArg_ParseTuple(
242  args, "OfOf:intersect_sphere_sphere_2d", &py_v_a, &rad_a, &py_v_b, &rad_b)) {
243  return NULL;
244  }
245 
246  if (((mathutils_array_parse(v_a, 2, 2, py_v_a, error_prefix) != -1) &&
247  (mathutils_array_parse(v_b, 2, 2, py_v_b, error_prefix) != -1)) == 0) {
248  return NULL;
249  }
250 
251  ret = PyTuple_New(2);
252 
253  sub_v2_v2v2(v_ab, v_b, v_a);
254  dist = len_v2(v_ab);
255 
256  if (/* out of range */
257  (dist > rad_a + rad_b) ||
258  /* fully-contained in the other */
259  (dist < fabsf(rad_a - rad_b)) ||
260  /* co-incident */
261  (dist < FLT_EPSILON)) {
262  /* out of range */
263  PyTuple_SET_ITEMS(ret, Py_INCREF_RET(Py_None), Py_INCREF_RET(Py_None));
264  }
265  else {
266  const float dist_delta = ((rad_a * rad_a) - (rad_b * rad_b) + (dist * dist)) / (2.0f * dist);
267  const float h = powf(fabsf((rad_a * rad_a) - (dist_delta * dist_delta)), 0.5f);
268  float i_cent[2];
269  float i1[2], i2[2];
270 
271  i_cent[0] = v_a[0] + ((v_ab[0] * dist_delta) / dist);
272  i_cent[1] = v_a[1] + ((v_ab[1] * dist_delta) / dist);
273 
274  i1[0] = i_cent[0] + h * v_ab[1] / dist;
275  i1[1] = i_cent[1] - h * v_ab[0] / dist;
276 
277  i2[0] = i_cent[0] - h * v_ab[1] / dist;
278  i2[1] = i_cent[1] + h * v_ab[0] / dist;
279 
281  }
282 
283  return ret;
284 }
285 
286 PyDoc_STRVAR(M_Geometry_intersect_tri_tri_2d_doc,
287  ".. function:: intersect_tri_tri_2d(tri_a1, tri_a2, tri_a3, tri_b1, tri_b2, tri_b3)\n"
288  "\n"
289  " Check if two 2D triangles intersect.\n"
290  "\n"
291  " :rtype: bool\n");
292 static PyObject *M_Geometry_intersect_tri_tri_2d(PyObject *UNUSED(self), PyObject *args)
293 {
294  const char *error_prefix = "intersect_tri_tri_2d";
295  PyObject *tri_pair_py[2][3];
296  float tri_pair[2][3][2];
297 
298  if (!PyArg_ParseTuple(args,
299  "OOOOOO:intersect_tri_tri_2d",
300  &tri_pair_py[0][0],
301  &tri_pair_py[0][1],
302  &tri_pair_py[0][2],
303  &tri_pair_py[1][0],
304  &tri_pair_py[1][1],
305  &tri_pair_py[1][2])) {
306  return NULL;
307  }
308 
309  for (int i = 0; i < 2; i++) {
310  for (int j = 0; j < 3; j++) {
312  tri_pair[i][j], 2, 2 | MU_ARRAY_SPILL, tri_pair_py[i][j], error_prefix) == -1) {
313  return NULL;
314  }
315  }
316  }
317 
318  const bool ret = isect_tri_tri_v2(UNPACK3(tri_pair[0]), UNPACK3(tri_pair[1]));
319  return PyBool_FromLong(ret);
320 }
321 
322 PyDoc_STRVAR(M_Geometry_normal_doc,
323  ".. function:: normal(vectors)\n"
324  "\n"
325  " Returns the normal of a 3D polygon.\n"
326  "\n"
327  " :arg vectors: Vectors to calculate normals with\n"
328  " :type vectors: sequence of 3 or more 3d vector\n"
329  " :rtype: :class:`mathutils.Vector`\n");
330 static PyObject *M_Geometry_normal(PyObject *UNUSED(self), PyObject *args)
331 {
332  float(*coords)[3];
333  int coords_len;
334  float n[3];
335  PyObject *ret = NULL;
336 
337  /* use */
338  if (PyTuple_GET_SIZE(args) == 1) {
339  args = PyTuple_GET_ITEM(args, 0);
340  }
341 
342  if ((coords_len = mathutils_array_parse_alloc_v(
343  (float **)&coords, 3 | MU_ARRAY_SPILL, args, "normal")) == -1) {
344  return NULL;
345  }
346 
347  if (coords_len < 3) {
348  PyErr_SetString(PyExc_ValueError, "Expected 3 or more vectors");
349  goto finally;
350  }
351 
352  normal_poly_v3(n, coords, coords_len);
353  ret = Vector_CreatePyObject(n, 3, NULL);
354 
355 finally:
356  PyMem_Free(coords);
357  return ret;
358 }
359 
360 /* --------------------------------- AREA FUNCTIONS-------------------- */
361 
362 PyDoc_STRVAR(M_Geometry_area_tri_doc,
363  ".. function:: area_tri(v1, v2, v3)\n"
364  "\n"
365  " Returns the area size of the 2D or 3D triangle defined.\n"
366  "\n"
367  " :arg v1: Point1\n"
368  " :type v1: :class:`mathutils.Vector`\n"
369  " :arg v2: Point2\n"
370  " :type v2: :class:`mathutils.Vector`\n"
371  " :arg v3: Point3\n"
372  " :type v3: :class:`mathutils.Vector`\n"
373  " :rtype: float\n");
374 static PyObject *M_Geometry_area_tri(PyObject *UNUSED(self), PyObject *args)
375 {
376  const char *error_prefix = "area_tri";
377  PyObject *py_tri[3];
378  float tri[3][3];
379  int len;
380 
381  if (!PyArg_ParseTuple(args, "OOO:area_tri", UNPACK3_EX(&, py_tri, ))) {
382  return NULL;
383  }
384 
385  if ((((len = mathutils_array_parse(tri[0], 2, 3, py_tri[0], error_prefix)) != -1) &&
386  (mathutils_array_parse(tri[1], len, len, py_tri[1], error_prefix) != -1) &&
387  (mathutils_array_parse(tri[2], len, len, py_tri[2], error_prefix) != -1)) == 0) {
388  return NULL;
389  }
390 
391  return PyFloat_FromDouble((len == 3 ? area_tri_v3 : area_tri_v2)(UNPACK3(tri)));
392 }
393 
394 PyDoc_STRVAR(M_Geometry_volume_tetrahedron_doc,
395  ".. function:: volume_tetrahedron(v1, v2, v3, v4)\n"
396  "\n"
397  " Return the volume formed by a tetrahedron (points can be in any order).\n"
398  "\n"
399  " :arg v1: Point1\n"
400  " :type v1: :class:`mathutils.Vector`\n"
401  " :arg v2: Point2\n"
402  " :type v2: :class:`mathutils.Vector`\n"
403  " :arg v3: Point3\n"
404  " :type v3: :class:`mathutils.Vector`\n"
405  " :arg v4: Point4\n"
406  " :type v4: :class:`mathutils.Vector`\n"
407  " :rtype: float\n");
408 static PyObject *M_Geometry_volume_tetrahedron(PyObject *UNUSED(self), PyObject *args)
409 {
410  const char *error_prefix = "volume_tetrahedron";
411  PyObject *py_tet[4];
412  float tet[4][3];
413  int i;
414 
415  if (!PyArg_ParseTuple(args, "OOOO:volume_tetrahedron", UNPACK4_EX(&, py_tet, ))) {
416  return NULL;
417  }
418 
419  for (i = 0; i < ARRAY_SIZE(tet); i++) {
420  if (mathutils_array_parse(tet[i], 3, 3 | MU_ARRAY_SPILL, py_tet[i], error_prefix) == -1) {
421  return NULL;
422  }
423  }
424 
425  return PyFloat_FromDouble(volume_tetrahedron_v3(UNPACK4(tet)));
426 }
427 
429  M_Geometry_intersect_line_line_2d_doc,
430  ".. function:: intersect_line_line_2d(lineA_p1, lineA_p2, lineB_p1, lineB_p2)\n"
431  "\n"
432  " Takes 2 segments (defined by 4 vectors) and returns a vector for their point of "
433  "intersection or None.\n"
434  "\n"
435  " .. warning:: Despite its name, this function works on segments, and not on lines.\n"
436  "\n"
437  " :arg lineA_p1: First point of the first line\n"
438  " :type lineA_p1: :class:`mathutils.Vector`\n"
439  " :arg lineA_p2: Second point of the first line\n"
440  " :type lineA_p2: :class:`mathutils.Vector`\n"
441  " :arg lineB_p1: First point of the second line\n"
442  " :type lineB_p1: :class:`mathutils.Vector`\n"
443  " :arg lineB_p2: Second point of the second line\n"
444  " :type lineB_p2: :class:`mathutils.Vector`\n"
445  " :return: The point of intersection or None when not found\n"
446  " :rtype: :class:`mathutils.Vector` or None\n");
447 static PyObject *M_Geometry_intersect_line_line_2d(PyObject *UNUSED(self), PyObject *args)
448 {
449  const char *error_prefix = "intersect_line_line_2d";
450  PyObject *py_lines[4];
451  float lines[4][2];
452  float vi[2];
453  int i;
454 
455  if (!PyArg_ParseTuple(args, "OOOO:intersect_line_line_2d", UNPACK4_EX(&, py_lines, ))) {
456  return NULL;
457  }
458 
459  for (i = 0; i < ARRAY_SIZE(lines); i++) {
460  if (mathutils_array_parse(lines[i], 2, 2 | MU_ARRAY_SPILL, py_lines[i], error_prefix) == -1) {
461  return NULL;
462  }
463  }
464 
465  if (isect_seg_seg_v2_point(UNPACK4(lines), vi) == 1) {
466  return Vector_CreatePyObject(vi, 2, NULL);
467  }
468 
469  Py_RETURN_NONE;
470 }
471 
473  M_Geometry_intersect_line_plane_doc,
474  ".. function:: intersect_line_plane(line_a, line_b, plane_co, plane_no, no_flip=False)\n"
475  "\n"
476  " Calculate the intersection between a line (as 2 vectors) and a plane.\n"
477  " Returns a vector for the intersection or None.\n"
478  "\n"
479  " :arg line_a: First point of the first line\n"
480  " :type line_a: :class:`mathutils.Vector`\n"
481  " :arg line_b: Second point of the first line\n"
482  " :type line_b: :class:`mathutils.Vector`\n"
483  " :arg plane_co: A point on the plane\n"
484  " :type plane_co: :class:`mathutils.Vector`\n"
485  " :arg plane_no: The direction the plane is facing\n"
486  " :type plane_no: :class:`mathutils.Vector`\n"
487  " :return: The point of intersection or None when not found\n"
488  " :rtype: :class:`mathutils.Vector` or None\n");
489 static PyObject *M_Geometry_intersect_line_plane(PyObject *UNUSED(self), PyObject *args)
490 {
491  const char *error_prefix = "intersect_line_plane";
492  PyObject *py_line_a, *py_line_b, *py_plane_co, *py_plane_no;
493  float line_a[3], line_b[3], plane_co[3], plane_no[3];
494  float isect[3];
495  const bool no_flip = false;
496 
497  if (!PyArg_ParseTuple(args,
498  "OOOO|O&:intersect_line_plane",
499  &py_line_a,
500  &py_line_b,
501  &py_plane_co,
502  &py_plane_no,
504  &no_flip)) {
505  return NULL;
506  }
507 
508  if (((mathutils_array_parse(line_a, 3, 3 | MU_ARRAY_SPILL, py_line_a, error_prefix) != -1) &&
509  (mathutils_array_parse(line_b, 3, 3 | MU_ARRAY_SPILL, py_line_b, error_prefix) != -1) &&
510  (mathutils_array_parse(plane_co, 3, 3 | MU_ARRAY_SPILL, py_plane_co, error_prefix) != -1) &&
511  (mathutils_array_parse(plane_no, 3, 3 | MU_ARRAY_SPILL, py_plane_no, error_prefix) !=
512  -1)) == 0) {
513  return NULL;
514  }
515 
516  /* TODO: implements no_flip */
517  if (isect_line_plane_v3(isect, line_a, line_b, plane_co, plane_no) == 1) {
518  return Vector_CreatePyObject(isect, 3, NULL);
519  }
520 
521  Py_RETURN_NONE;
522 }
523 
525  M_Geometry_intersect_plane_plane_doc,
526  ".. function:: intersect_plane_plane(plane_a_co, plane_a_no, plane_b_co, plane_b_no)\n"
527  "\n"
528  " Return the intersection between two planes\n"
529  "\n"
530  " :arg plane_a_co: Point on the first plane\n"
531  " :type plane_a_co: :class:`mathutils.Vector`\n"
532  " :arg plane_a_no: Normal of the first plane\n"
533  " :type plane_a_no: :class:`mathutils.Vector`\n"
534  " :arg plane_b_co: Point on the second plane\n"
535  " :type plane_b_co: :class:`mathutils.Vector`\n"
536  " :arg plane_b_no: Normal of the second plane\n"
537  " :type plane_b_no: :class:`mathutils.Vector`\n"
538  " :return: The line of the intersection represented as a point and a vector\n"
539  " :rtype: tuple pair of :class:`mathutils.Vector` or None if the intersection can't be "
540  "calculated\n");
541 static PyObject *M_Geometry_intersect_plane_plane(PyObject *UNUSED(self), PyObject *args)
542 {
543  const char *error_prefix = "intersect_plane_plane";
544  PyObject *ret, *ret_co, *ret_no;
545  PyObject *py_plane_a_co, *py_plane_a_no, *py_plane_b_co, *py_plane_b_no;
546  float plane_a_co[3], plane_a_no[3], plane_b_co[3], plane_b_no[3];
547  float plane_a[4], plane_b[4];
548 
549  float isect_co[3];
550  float isect_no[3];
551 
552  if (!PyArg_ParseTuple(args,
553  "OOOO:intersect_plane_plane",
554  &py_plane_a_co,
555  &py_plane_a_no,
556  &py_plane_b_co,
557  &py_plane_b_no)) {
558  return NULL;
559  }
560 
561  if (((mathutils_array_parse(plane_a_co, 3, 3 | MU_ARRAY_SPILL, py_plane_a_co, error_prefix) !=
562  -1) &&
563  (mathutils_array_parse(plane_a_no, 3, 3 | MU_ARRAY_SPILL, py_plane_a_no, error_prefix) !=
564  -1) &&
565  (mathutils_array_parse(plane_b_co, 3, 3 | MU_ARRAY_SPILL, py_plane_b_co, error_prefix) !=
566  -1) &&
567  (mathutils_array_parse(plane_b_no, 3, 3 | MU_ARRAY_SPILL, py_plane_b_no, error_prefix) !=
568  -1)) == 0) {
569  return NULL;
570  }
571 
572  plane_from_point_normal_v3(plane_a, plane_a_co, plane_a_no);
573  plane_from_point_normal_v3(plane_b, plane_b_co, plane_b_no);
574 
575  if (isect_plane_plane_v3(plane_a, plane_b, isect_co, isect_no)) {
576  normalize_v3(isect_no);
577 
578  ret_co = Vector_CreatePyObject(isect_co, 3, NULL);
579  ret_no = Vector_CreatePyObject(isect_no, 3, NULL);
580  }
581  else {
582  ret_co = Py_INCREF_RET(Py_None);
583  ret_no = Py_INCREF_RET(Py_None);
584  }
585 
586  ret = PyTuple_New(2);
587  PyTuple_SET_ITEMS(ret, ret_co, ret_no);
588  return ret;
589 }
590 
592  M_Geometry_intersect_line_sphere_doc,
593  ".. function:: intersect_line_sphere(line_a, line_b, sphere_co, sphere_radius, clip=True)\n"
594  "\n"
595  " Takes a line (as 2 points) and a sphere (as a point and a radius) and\n"
596  " returns the intersection\n"
597  "\n"
598  " :arg line_a: First point of the line\n"
599  " :type line_a: :class:`mathutils.Vector`\n"
600  " :arg line_b: Second point of the line\n"
601  " :type line_b: :class:`mathutils.Vector`\n"
602  " :arg sphere_co: The center of the sphere\n"
603  " :type sphere_co: :class:`mathutils.Vector`\n"
604  " :arg sphere_radius: Radius of the sphere\n"
605  " :type sphere_radius: sphere_radius\n"
606  " :return: The intersection points as a pair of vectors or None when there is no "
607  "intersection\n"
608  " :rtype: A tuple pair containing :class:`mathutils.Vector` or None\n");
609 static PyObject *M_Geometry_intersect_line_sphere(PyObject *UNUSED(self), PyObject *args)
610 {
611  const char *error_prefix = "intersect_line_sphere";
612  PyObject *py_line_a, *py_line_b, *py_sphere_co;
613  float line_a[3], line_b[3], sphere_co[3];
614  float sphere_radius;
615  bool clip = true;
616 
617  float isect_a[3];
618  float isect_b[3];
619 
620  if (!PyArg_ParseTuple(args,
621  "OOOf|O&:intersect_line_sphere",
622  &py_line_a,
623  &py_line_b,
624  &py_sphere_co,
625  &sphere_radius,
627  &clip)) {
628  return NULL;
629  }
630 
631  if (((mathutils_array_parse(line_a, 3, 3 | MU_ARRAY_SPILL, py_line_a, error_prefix) != -1) &&
632  (mathutils_array_parse(line_b, 3, 3 | MU_ARRAY_SPILL, py_line_b, error_prefix) != -1) &&
633  (mathutils_array_parse(sphere_co, 3, 3 | MU_ARRAY_SPILL, py_sphere_co, error_prefix) !=
634  -1)) == 0) {
635  return NULL;
636  }
637 
638  bool use_a = true;
639  bool use_b = true;
640  float lambda;
641 
642  PyObject *ret = PyTuple_New(2);
643 
644  switch (isect_line_sphere_v3(line_a, line_b, sphere_co, sphere_radius, isect_a, isect_b)) {
645  case 1:
646  if (!(!clip || (((lambda = line_point_factor_v3(isect_a, line_a, line_b)) >= 0.0f) &&
647  (lambda <= 1.0f)))) {
648  use_a = false;
649  }
650  use_b = false;
651  break;
652  case 2:
653  if (!(!clip || (((lambda = line_point_factor_v3(isect_a, line_a, line_b)) >= 0.0f) &&
654  (lambda <= 1.0f)))) {
655  use_a = false;
656  }
657  if (!(!clip || (((lambda = line_point_factor_v3(isect_b, line_a, line_b)) >= 0.0f) &&
658  (lambda <= 1.0f)))) {
659  use_b = false;
660  }
661  break;
662  default:
663  use_a = false;
664  use_b = false;
665  break;
666  }
667 
669  use_a ? Vector_CreatePyObject(isect_a, 3, NULL) : Py_INCREF_RET(Py_None),
670  use_b ? Vector_CreatePyObject(isect_b, 3, NULL) : Py_INCREF_RET(Py_None));
671 
672  return ret;
673 }
674 
675 /* keep in sync with M_Geometry_intersect_line_sphere */
677  M_Geometry_intersect_line_sphere_2d_doc,
678  ".. function:: intersect_line_sphere_2d(line_a, line_b, sphere_co, sphere_radius, clip=True)\n"
679  "\n"
680  " Takes a line (as 2 points) and a sphere (as a point and a radius) and\n"
681  " returns the intersection\n"
682  "\n"
683  " :arg line_a: First point of the line\n"
684  " :type line_a: :class:`mathutils.Vector`\n"
685  " :arg line_b: Second point of the line\n"
686  " :type line_b: :class:`mathutils.Vector`\n"
687  " :arg sphere_co: The center of the sphere\n"
688  " :type sphere_co: :class:`mathutils.Vector`\n"
689  " :arg sphere_radius: Radius of the sphere\n"
690  " :type sphere_radius: sphere_radius\n"
691  " :return: The intersection points as a pair of vectors or None when there is no "
692  "intersection\n"
693  " :rtype: A tuple pair containing :class:`mathutils.Vector` or None\n");
694 static PyObject *M_Geometry_intersect_line_sphere_2d(PyObject *UNUSED(self), PyObject *args)
695 {
696  const char *error_prefix = "intersect_line_sphere_2d";
697  PyObject *py_line_a, *py_line_b, *py_sphere_co;
698  float line_a[2], line_b[2], sphere_co[2];
699  float sphere_radius;
700  bool clip = true;
701 
702  float isect_a[2];
703  float isect_b[2];
704 
705  if (!PyArg_ParseTuple(args,
706  "OOOf|O&:intersect_line_sphere_2d",
707  &py_line_a,
708  &py_line_b,
709  &py_sphere_co,
710  &sphere_radius,
712  &clip)) {
713  return NULL;
714  }
715 
716  if (((mathutils_array_parse(line_a, 2, 2 | MU_ARRAY_SPILL, py_line_a, error_prefix) != -1) &&
717  (mathutils_array_parse(line_b, 2, 2 | MU_ARRAY_SPILL, py_line_b, error_prefix) != -1) &&
718  (mathutils_array_parse(sphere_co, 2, 2 | MU_ARRAY_SPILL, py_sphere_co, error_prefix) !=
719  -1)) == 0) {
720  return NULL;
721  }
722 
723  bool use_a = true;
724  bool use_b = true;
725  float lambda;
726 
727  PyObject *ret = PyTuple_New(2);
728 
729  switch (isect_line_sphere_v2(line_a, line_b, sphere_co, sphere_radius, isect_a, isect_b)) {
730  case 1:
731  if (!(!clip || (((lambda = line_point_factor_v2(isect_a, line_a, line_b)) >= 0.0f) &&
732  (lambda <= 1.0f)))) {
733  use_a = false;
734  }
735  use_b = false;
736  break;
737  case 2:
738  if (!(!clip || (((lambda = line_point_factor_v2(isect_a, line_a, line_b)) >= 0.0f) &&
739  (lambda <= 1.0f)))) {
740  use_a = false;
741  }
742  if (!(!clip || (((lambda = line_point_factor_v2(isect_b, line_a, line_b)) >= 0.0f) &&
743  (lambda <= 1.0f)))) {
744  use_b = false;
745  }
746  break;
747  default:
748  use_a = false;
749  use_b = false;
750  break;
751  }
752 
754  use_a ? Vector_CreatePyObject(isect_a, 2, NULL) : Py_INCREF_RET(Py_None),
755  use_b ? Vector_CreatePyObject(isect_b, 2, NULL) : Py_INCREF_RET(Py_None));
756 
757  return ret;
758 }
759 
761  M_Geometry_intersect_point_line_doc,
762  ".. function:: intersect_point_line(pt, line_p1, line_p2)\n"
763  "\n"
764  " Takes a point and a line and returns a tuple with the closest point on the line and its "
765  "distance from the first point of the line as a percentage of the length of the line.\n"
766  "\n"
767  " :arg pt: Point\n"
768  " :type pt: :class:`mathutils.Vector`\n"
769  " :arg line_p1: First point of the line\n"
770  " :type line_p1: :class:`mathutils.Vector`\n"
771  " :arg line_p1: Second point of the line\n"
772  " :type line_p1: :class:`mathutils.Vector`\n"
773  " :rtype: (:class:`mathutils.Vector`, float)\n");
774 static PyObject *M_Geometry_intersect_point_line(PyObject *UNUSED(self), PyObject *args)
775 {
776  const char *error_prefix = "intersect_point_line";
777  PyObject *py_pt, *py_line_a, *py_line_b;
778  float pt[3], pt_out[3], line_a[3], line_b[3];
779  float lambda;
780  PyObject *ret;
781  int pt_num = 2;
782 
783  if (!PyArg_ParseTuple(args, "OOO:intersect_point_line", &py_pt, &py_line_a, &py_line_b)) {
784  return NULL;
785  }
786 
787  /* accept 2d verts */
788  if ((((pt_num = mathutils_array_parse(
789  pt, 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_pt, error_prefix)) != -1) &&
791  line_a, 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_line_a, error_prefix) != -1) &&
793  line_b, 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_line_b, error_prefix) != -1)) == 0) {
794  return NULL;
795  }
796 
797  /* do the calculation */
798  lambda = closest_to_line_v3(pt_out, pt, line_a, line_b);
799 
800  ret = PyTuple_New(2);
801  PyTuple_SET_ITEMS(ret, Vector_CreatePyObject(pt_out, pt_num, NULL), PyFloat_FromDouble(lambda));
802  return ret;
803 }
804 
805 PyDoc_STRVAR(M_Geometry_intersect_point_tri_doc,
806  ".. function:: intersect_point_tri(pt, tri_p1, tri_p2, tri_p3)\n"
807  "\n"
808  " Takes 4 vectors: one is the point and the next 3 define the triangle. Projects "
809  "the point onto the triangle plane and checks if it is within the triangle.\n"
810  "\n"
811  " :arg pt: Point\n"
812  " :type pt: :class:`mathutils.Vector`\n"
813  " :arg tri_p1: First point of the triangle\n"
814  " :type tri_p1: :class:`mathutils.Vector`\n"
815  " :arg tri_p2: Second point of the triangle\n"
816  " :type tri_p2: :class:`mathutils.Vector`\n"
817  " :arg tri_p3: Third point of the triangle\n"
818  " :type tri_p3: :class:`mathutils.Vector`\n"
819  " :return: Point on the triangles plane or None if its outside the triangle\n"
820  " :rtype: :class:`mathutils.Vector` or None\n");
821 static PyObject *M_Geometry_intersect_point_tri(PyObject *UNUSED(self), PyObject *args)
822 {
823  const char *error_prefix = "intersect_point_tri";
824  PyObject *py_pt, *py_tri[3];
825  float pt[3], tri[3][3];
826  float vi[3];
827  int i;
828 
829  if (!PyArg_ParseTuple(args, "OOOO:intersect_point_tri", &py_pt, UNPACK3_EX(&, py_tri, ))) {
830  return NULL;
831  }
832 
833  if (mathutils_array_parse(pt, 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_pt, error_prefix) ==
834  -1) {
835  return NULL;
836  }
837  for (i = 0; i < ARRAY_SIZE(tri); i++) {
839  tri[i], 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_tri[i], error_prefix) == -1) {
840  return NULL;
841  }
842  }
843 
844  if (isect_point_tri_v3(pt, UNPACK3(tri), vi)) {
845  return Vector_CreatePyObject(vi, 3, NULL);
846  }
847 
848  Py_RETURN_NONE;
849 }
850 
851 PyDoc_STRVAR(M_Geometry_closest_point_on_tri_doc,
852  ".. function:: closest_point_on_tri(pt, tri_p1, tri_p2, tri_p3)\n"
853  "\n"
854  " Takes 4 vectors: one is the point and the next 3 define the triangle.\n"
855  "\n"
856  " :arg pt: Point\n"
857  " :type pt: :class:`mathutils.Vector`\n"
858  " :arg tri_p1: First point of the triangle\n"
859  " :type tri_p1: :class:`mathutils.Vector`\n"
860  " :arg tri_p2: Second point of the triangle\n"
861  " :type tri_p2: :class:`mathutils.Vector`\n"
862  " :arg tri_p3: Third point of the triangle\n"
863  " :type tri_p3: :class:`mathutils.Vector`\n"
864  " :return: The closest point of the triangle.\n"
865  " :rtype: :class:`mathutils.Vector`\n");
866 static PyObject *M_Geometry_closest_point_on_tri(PyObject *UNUSED(self), PyObject *args)
867 {
868  const char *error_prefix = "closest_point_on_tri";
869  PyObject *py_pt, *py_tri[3];
870  float pt[3], tri[3][3];
871  float vi[3];
872  int i;
873 
874  if (!PyArg_ParseTuple(args, "OOOO:closest_point_on_tri", &py_pt, UNPACK3_EX(&, py_tri, ))) {
875  return NULL;
876  }
877 
878  if (mathutils_array_parse(pt, 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_pt, error_prefix) ==
879  -1) {
880  return NULL;
881  }
882  for (i = 0; i < ARRAY_SIZE(tri); i++) {
884  tri[i], 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_tri[i], error_prefix) == -1) {
885  return NULL;
886  }
887  }
888 
889  closest_on_tri_to_point_v3(vi, pt, UNPACK3(tri));
890 
891  return Vector_CreatePyObject(vi, 3, NULL);
892 }
893 
895  M_Geometry_intersect_point_tri_2d_doc,
896  ".. function:: intersect_point_tri_2d(pt, tri_p1, tri_p2, tri_p3)\n"
897  "\n"
898  " Takes 4 vectors (using only the x and y coordinates): one is the point and the next 3 "
899  "define the triangle. Returns 1 if the point is within the triangle, otherwise 0.\n"
900  "\n"
901  " :arg pt: Point\n"
902  " :type pt: :class:`mathutils.Vector`\n"
903  " :arg tri_p1: First point of the triangle\n"
904  " :type tri_p1: :class:`mathutils.Vector`\n"
905  " :arg tri_p2: Second point of the triangle\n"
906  " :type tri_p2: :class:`mathutils.Vector`\n"
907  " :arg tri_p3: Third point of the triangle\n"
908  " :type tri_p3: :class:`mathutils.Vector`\n"
909  " :rtype: int\n");
910 static PyObject *M_Geometry_intersect_point_tri_2d(PyObject *UNUSED(self), PyObject *args)
911 {
912  const char *error_prefix = "intersect_point_tri_2d";
913  PyObject *py_pt, *py_tri[3];
914  float pt[2], tri[3][2];
915  int i;
916 
917  if (!PyArg_ParseTuple(args, "OOOO:intersect_point_tri_2d", &py_pt, UNPACK3_EX(&, py_tri, ))) {
918  return NULL;
919  }
920 
921  if (mathutils_array_parse(pt, 2, 2 | MU_ARRAY_SPILL, py_pt, error_prefix) == -1) {
922  return NULL;
923  }
924  for (i = 0; i < ARRAY_SIZE(tri); i++) {
925  if (mathutils_array_parse(tri[i], 2, 2 | MU_ARRAY_SPILL, py_tri[i], error_prefix) == -1) {
926  return NULL;
927  }
928  }
929 
930  return PyLong_FromLong(isect_point_tri_v2(pt, UNPACK3(tri)));
931 }
932 
933 PyDoc_STRVAR(M_Geometry_intersect_point_quad_2d_doc,
934  ".. function:: intersect_point_quad_2d(pt, quad_p1, quad_p2, quad_p3, quad_p4)\n"
935  "\n"
936  " Takes 5 vectors (using only the x and y coordinates): one is the point and the "
937  "next 4 define the quad,\n"
938  " only the x and y are used from the vectors. Returns 1 if the point is within the "
939  "quad, otherwise 0.\n"
940  " Works only with convex quads without singular edges.\n"
941  "\n"
942  " :arg pt: Point\n"
943  " :type pt: :class:`mathutils.Vector`\n"
944  " :arg quad_p1: First point of the quad\n"
945  " :type quad_p1: :class:`mathutils.Vector`\n"
946  " :arg quad_p2: Second point of the quad\n"
947  " :type quad_p2: :class:`mathutils.Vector`\n"
948  " :arg quad_p3: Third point of the quad\n"
949  " :type quad_p3: :class:`mathutils.Vector`\n"
950  " :arg quad_p4: Fourth point of the quad\n"
951  " :type quad_p4: :class:`mathutils.Vector`\n"
952  " :rtype: int\n");
953 static PyObject *M_Geometry_intersect_point_quad_2d(PyObject *UNUSED(self), PyObject *args)
954 {
955  const char *error_prefix = "intersect_point_quad_2d";
956  PyObject *py_pt, *py_quad[4];
957  float pt[2], quad[4][2];
958  int i;
959 
960  if (!PyArg_ParseTuple(args, "OOOOO:intersect_point_quad_2d", &py_pt, UNPACK4_EX(&, py_quad, ))) {
961  return NULL;
962  }
963 
964  if (mathutils_array_parse(pt, 2, 2 | MU_ARRAY_SPILL, py_pt, error_prefix) == -1) {
965  return NULL;
966  }
967  for (i = 0; i < ARRAY_SIZE(quad); i++) {
968  if (mathutils_array_parse(quad[i], 2, 2 | MU_ARRAY_SPILL, py_quad[i], error_prefix) == -1) {
969  return NULL;
970  }
971  }
972 
973  return PyLong_FromLong(isect_point_quad_v2(pt, UNPACK4(quad)));
974 }
975 
976 PyDoc_STRVAR(M_Geometry_distance_point_to_plane_doc,
977  ".. function:: distance_point_to_plane(pt, plane_co, plane_no)\n"
978  "\n"
979  " Returns the signed distance between a point and a plane "
980  " (negative when below the normal).\n"
981  "\n"
982  " :arg pt: Point\n"
983  " :type pt: :class:`mathutils.Vector`\n"
984  " :arg plane_co: A point on the plane\n"
985  " :type plane_co: :class:`mathutils.Vector`\n"
986  " :arg plane_no: The direction the plane is facing\n"
987  " :type plane_no: :class:`mathutils.Vector`\n"
988  " :rtype: float\n");
989 static PyObject *M_Geometry_distance_point_to_plane(PyObject *UNUSED(self), PyObject *args)
990 {
991  const char *error_prefix = "distance_point_to_plane";
992  PyObject *py_pt, *py_plane_co, *py_plane_no;
993  float pt[3], plane_co[3], plane_no[3];
994  float plane[4];
995 
996  if (!PyArg_ParseTuple(args, "OOO:distance_point_to_plane", &py_pt, &py_plane_co, &py_plane_no)) {
997  return NULL;
998  }
999 
1000  if (((mathutils_array_parse(pt, 3, 3 | MU_ARRAY_SPILL, py_pt, error_prefix) != -1) &&
1001  (mathutils_array_parse(plane_co, 3, 3 | MU_ARRAY_SPILL, py_plane_co, error_prefix) != -1) &&
1002  (mathutils_array_parse(plane_no, 3, 3 | MU_ARRAY_SPILL, py_plane_no, error_prefix) !=
1003  -1)) == 0) {
1004  return NULL;
1005  }
1006 
1007  plane_from_point_normal_v3(plane, plane_co, plane_no);
1008  return PyFloat_FromDouble(dist_signed_to_plane_v3(pt, plane));
1009 }
1010 
1012  M_Geometry_barycentric_transform_doc,
1013  ".. function:: barycentric_transform(point, tri_a1, tri_a2, tri_a3, tri_b1, tri_b2, tri_b3)\n"
1014  "\n"
1015  " Return a transformed point, the transformation is defined by 2 triangles.\n"
1016  "\n"
1017  " :arg point: The point to transform.\n"
1018  " :type point: :class:`mathutils.Vector`\n"
1019  " :arg tri_a1: source triangle vertex.\n"
1020  " :type tri_a1: :class:`mathutils.Vector`\n"
1021  " :arg tri_a2: source triangle vertex.\n"
1022  " :type tri_a2: :class:`mathutils.Vector`\n"
1023  " :arg tri_a3: source triangle vertex.\n"
1024  " :type tri_a3: :class:`mathutils.Vector`\n"
1025  " :arg tri_b1: target triangle vertex.\n"
1026  " :type tri_b1: :class:`mathutils.Vector`\n"
1027  " :arg tri_b2: target triangle vertex.\n"
1028  " :type tri_b2: :class:`mathutils.Vector`\n"
1029  " :arg tri_b3: target triangle vertex.\n"
1030  " :type tri_b3: :class:`mathutils.Vector`\n"
1031  " :return: The transformed point\n"
1032  " :rtype: :class:`mathutils.Vector`'s\n");
1033 static PyObject *M_Geometry_barycentric_transform(PyObject *UNUSED(self), PyObject *args)
1034 {
1035  const char *error_prefix = "barycentric_transform";
1036  PyObject *py_pt_src, *py_tri_src[3], *py_tri_dst[3];
1037  float pt_src[3], pt_dst[3], tri_src[3][3], tri_dst[3][3];
1038  int i;
1039 
1040  if (!PyArg_ParseTuple(args,
1041  "OOOOOOO:barycentric_transform",
1042  &py_pt_src,
1043  UNPACK3_EX(&, py_tri_src, ),
1044  UNPACK3_EX(&, py_tri_dst, ))) {
1045  return NULL;
1046  }
1047 
1048  if (mathutils_array_parse(pt_src, 3, 3 | MU_ARRAY_SPILL, py_pt_src, error_prefix) == -1) {
1049  return NULL;
1050  }
1051  for (i = 0; i < ARRAY_SIZE(tri_src); i++) {
1052  if (((mathutils_array_parse(tri_src[i], 3, 3 | MU_ARRAY_SPILL, py_tri_src[i], error_prefix) !=
1053  -1) &&
1054  (mathutils_array_parse(tri_dst[i], 3, 3 | MU_ARRAY_SPILL, py_tri_dst[i], error_prefix) !=
1055  -1)) == 0) {
1056  return NULL;
1057  }
1058  }
1059 
1060  transform_point_by_tri_v3(pt_dst, pt_src, UNPACK3(tri_dst), UNPACK3(tri_src));
1061 
1062  return Vector_CreatePyObject(pt_dst, 3, NULL);
1063 }
1064 
1066  PyObject *py_verts;
1068 };
1069 
1070 static void points_in_planes_fn(const float co[3], int i, int j, int k, void *user_data_p)
1071 {
1072  struct PointsInPlanes_UserData *user_data = user_data_p;
1073  PyList_APPEND(user_data->py_verts, Vector_CreatePyObject(co, 3, NULL));
1074  user_data->planes_used[i] = true;
1075  user_data->planes_used[j] = true;
1076  user_data->planes_used[k] = true;
1077 }
1078 
1079 PyDoc_STRVAR(M_Geometry_points_in_planes_doc,
1080  ".. function:: points_in_planes(planes)\n"
1081  "\n"
1082  " Returns a list of points inside all planes given and a list of index values for "
1083  "the planes used.\n"
1084  "\n"
1085  " :arg planes: List of planes (4D vectors).\n"
1086  " :type planes: list of :class:`mathutils.Vector`\n"
1087  " :return: two lists, once containing the vertices inside the planes, another "
1088  "containing the plane indices used\n"
1089  " :rtype: pair of lists\n");
1090 static PyObject *M_Geometry_points_in_planes(PyObject *UNUSED(self), PyObject *args)
1091 {
1092  PyObject *py_planes;
1093  float(*planes)[4];
1094  uint planes_len;
1095 
1096  if (!PyArg_ParseTuple(args, "O:points_in_planes", &py_planes)) {
1097  return NULL;
1098  }
1099 
1100  if ((planes_len = mathutils_array_parse_alloc_v(
1101  (float **)&planes, 4, py_planes, "points_in_planes")) == -1) {
1102  return NULL;
1103  }
1104 
1105  /* NOTE: this could be refactored into plain C easy - py bits are noted. */
1106 
1108  .py_verts = PyList_New(0),
1109  .planes_used = PyMem_Malloc(sizeof(char) * planes_len),
1110  };
1111 
1112  /* python */
1113  PyObject *py_plane_index = PyList_New(0);
1114 
1115  memset(user_data.planes_used, 0, sizeof(char) * planes_len);
1116 
1117  const float eps_coplanar = 1e-4f;
1118  const float eps_isect = 1e-6f;
1119 
1120  const bool has_isect = isect_planes_v3_fn(
1121  planes, planes_len, eps_coplanar, eps_isect, points_in_planes_fn, &user_data);
1122  PyMem_Free(planes);
1123 
1124  /* Now make user_data list of used planes. */
1125  if (has_isect) {
1126  for (int i = 0; i < planes_len; i++) {
1127  if (user_data.planes_used[i]) {
1128  PyList_APPEND(py_plane_index, PyLong_FromLong(i));
1129  }
1130  }
1131  }
1132  PyMem_Free(user_data.planes_used);
1133 
1134  {
1135  PyObject *ret = PyTuple_New(2);
1136  PyTuple_SET_ITEMS(ret, user_data.py_verts, py_plane_index);
1137  return ret;
1138  }
1139 }
1140 
1141 #ifndef MATH_STANDALONE
1142 
1143 PyDoc_STRVAR(M_Geometry_interpolate_bezier_doc,
1144  ".. function:: interpolate_bezier(knot1, handle1, handle2, knot2, resolution)\n"
1145  "\n"
1146  " Interpolate a bezier spline segment.\n"
1147  "\n"
1148  " :arg knot1: First bezier spline point.\n"
1149  " :type knot1: :class:`mathutils.Vector`\n"
1150  " :arg handle1: First bezier spline handle.\n"
1151  " :type handle1: :class:`mathutils.Vector`\n"
1152  " :arg handle2: Second bezier spline handle.\n"
1153  " :type handle2: :class:`mathutils.Vector`\n"
1154  " :arg knot2: Second bezier spline point.\n"
1155  " :type knot2: :class:`mathutils.Vector`\n"
1156  " :arg resolution: Number of points to return.\n"
1157  " :type resolution: int\n"
1158  " :return: The interpolated points\n"
1159  " :rtype: list of :class:`mathutils.Vector`'s\n");
1160 static PyObject *M_Geometry_interpolate_bezier(PyObject *UNUSED(self), PyObject *args)
1161 {
1162  const char *error_prefix = "interpolate_bezier";
1163  PyObject *py_data[4];
1164  float data[4][4] = {{0.0f}};
1165  int resolu;
1166  int dims = 0;
1167  int i;
1168  float *coord_array, *fp;
1169  PyObject *list;
1170 
1171  if (!PyArg_ParseTuple(args, "OOOOi:interpolate_bezier", UNPACK4_EX(&, py_data, ), &resolu)) {
1172  return NULL;
1173  }
1174 
1175  for (i = 0; i < 4; i++) {
1176  int dims_tmp;
1177  if ((dims_tmp = mathutils_array_parse(
1178  data[i], 2, 3 | MU_ARRAY_SPILL | MU_ARRAY_ZERO, py_data[i], error_prefix)) == -1) {
1179  return NULL;
1180  }
1181  dims = max_ii(dims, dims_tmp);
1182  }
1183 
1184  if (resolu <= 1) {
1185  PyErr_SetString(PyExc_ValueError, "resolution must be 2 or over");
1186  return NULL;
1187  }
1188 
1189  coord_array = MEM_callocN(dims * (resolu) * sizeof(float), error_prefix);
1190  for (i = 0; i < dims; i++) {
1192  UNPACK4_EX(, data, [i]), coord_array + i, resolu - 1, sizeof(float) * dims);
1193  }
1194 
1195  list = PyList_New(resolu);
1196  fp = coord_array;
1197  for (i = 0; i < resolu; i++, fp = fp + dims) {
1198  PyList_SET_ITEM(list, i, Vector_CreatePyObject(fp, dims, NULL));
1199  }
1200  MEM_freeN(coord_array);
1201  return list;
1202 }
1203 
1204 PyDoc_STRVAR(M_Geometry_tessellate_polygon_doc,
1205  ".. function:: tessellate_polygon(veclist_list)\n"
1206  "\n"
1207  " Takes a list of polylines (each point a pair or triplet of numbers) and returns "
1208  "the point indices for a polyline filled with triangles. Does not handle degenerate "
1209  "geometry (such as zero-length lines due to consecutive identical points).\n"
1210  "\n"
1211  " :arg veclist_list: list of polylines\n"
1212  " :rtype: list\n");
1213 /* PolyFill function, uses Blenders scan-fill to fill multiple poly lines. */
1214 static PyObject *M_Geometry_tessellate_polygon(PyObject *UNUSED(self), PyObject *polyLineSeq)
1215 {
1216  PyObject *tri_list; /* Return this list of tri's */
1217  PyObject *polyLine, *polyVec;
1218  int i, len_polylines, len_polypoints;
1219  bool list_parse_error = false;
1220  bool is_2d = true;
1221 
1222  /* Display #ListBase. */
1223  ListBase dispbase = {NULL, NULL};
1224  DispList *dl;
1225  float *fp; /* Pointer to the array of malloced dl->verts to set the points from the vectors. */
1226  int totpoints = 0;
1227 
1228  if (!PySequence_Check(polyLineSeq)) {
1229  PyErr_SetString(PyExc_TypeError, "expected a sequence of poly lines");
1230  return NULL;
1231  }
1232 
1233  len_polylines = PySequence_Size(polyLineSeq);
1234 
1235  for (i = 0; i < len_polylines; i++) {
1236  polyLine = PySequence_GetItem(polyLineSeq, i);
1237  if (!PySequence_Check(polyLine)) {
1238  BKE_displist_free(&dispbase);
1239  Py_XDECREF(polyLine); /* May be null so use #Py_XDECREF. */
1240  PyErr_SetString(PyExc_TypeError,
1241  "One or more of the polylines is not a sequence of mathutils.Vector's");
1242  return NULL;
1243  }
1244 
1245  len_polypoints = PySequence_Size(polyLine);
1246  if (len_polypoints > 0) { /* don't bother adding edges as polylines */
1247  dl = MEM_callocN(sizeof(DispList), "poly disp");
1248  BLI_addtail(&dispbase, dl);
1249  dl->type = DL_INDEX3;
1250  dl->nr = len_polypoints;
1251  dl->type = DL_POLY;
1252  dl->parts = 1; /* no faces, 1 edge loop */
1253  dl->col = 0; /* no material */
1254  dl->verts = fp = MEM_mallocN(sizeof(float[3]) * len_polypoints, "dl verts");
1255  dl->index = MEM_callocN(sizeof(int[3]) * len_polypoints, "dl index");
1256 
1257  for (int index = 0; index < len_polypoints; index++, fp += 3) {
1258  polyVec = PySequence_GetItem(polyLine, index);
1259  const int polyVec_len = mathutils_array_parse(
1260  fp, 2, 3 | MU_ARRAY_SPILL, polyVec, "tessellate_polygon: parse coord");
1261  Py_DECREF(polyVec);
1262 
1263  if (UNLIKELY(polyVec_len == -1)) {
1264  list_parse_error = true;
1265  }
1266  else if (polyVec_len == 2) {
1267  fp[2] = 0.0f;
1268  }
1269  else if (polyVec_len == 3) {
1270  is_2d = false;
1271  }
1272 
1273  totpoints++;
1274  }
1275  }
1276  Py_DECREF(polyLine);
1277  }
1278 
1279  if (list_parse_error) {
1280  BKE_displist_free(&dispbase); /* possible some dl was allocated */
1281  return NULL;
1282  }
1283  if (totpoints) {
1284  /* now make the list to return */
1285  BKE_displist_fill(&dispbase, &dispbase, is_2d ? ((const float[3]){0, 0, -1}) : NULL, false);
1286 
1287  /* The faces are stored in a new DisplayList
1288  * that's added to the head of the #ListBase. */
1289  dl = dispbase.first;
1290 
1291  tri_list = PyList_New(dl->parts);
1292  if (!tri_list) {
1293  BKE_displist_free(&dispbase);
1294  PyErr_SetString(PyExc_RuntimeError, "failed to make a new list");
1295  return NULL;
1296  }
1297 
1298  int *dl_face = dl->index;
1299  for (int index = 0; index < dl->parts; index++) {
1300  PyList_SET_ITEM(tri_list, index, PyC_Tuple_Pack_I32(dl_face[0], dl_face[1], dl_face[2]));
1301  dl_face += 3;
1302  }
1303  BKE_displist_free(&dispbase);
1304  }
1305  else {
1306  /* no points, do this so scripts don't barf */
1307  BKE_displist_free(&dispbase); /* possible some dl was allocated */
1308  tri_list = PyList_New(0);
1309  }
1310 
1311  return tri_list;
1312 }
1313 
1314 static int boxPack_FromPyObject(PyObject *value, BoxPack **r_boxarray)
1315 {
1316  Py_ssize_t len, i;
1317  PyObject *list_item, *item_1, *item_2;
1318  BoxPack *boxarray;
1319 
1320  /* Error checking must already be done */
1321  if (!PyList_Check(value)) {
1322  PyErr_SetString(PyExc_TypeError, "can only back a list of [x, y, w, h]");
1323  return -1;
1324  }
1325 
1326  len = PyList_GET_SIZE(value);
1327 
1328  boxarray = MEM_mallocN(sizeof(BoxPack) * len, __func__);
1329 
1330  for (i = 0; i < len; i++) {
1331  list_item = PyList_GET_ITEM(value, i);
1332  if (!PyList_Check(list_item) || PyList_GET_SIZE(list_item) < 4) {
1333  MEM_freeN(boxarray);
1334  PyErr_SetString(PyExc_TypeError, "can only pack a list of [x, y, w, h]");
1335  return -1;
1336  }
1337 
1338  BoxPack *box = &boxarray[i];
1339 
1340  item_1 = PyList_GET_ITEM(list_item, 2);
1341  item_2 = PyList_GET_ITEM(list_item, 3);
1342 
1343  box->w = (float)PyFloat_AsDouble(item_1);
1344  box->h = (float)PyFloat_AsDouble(item_2);
1345  box->index = i;
1346 
1347  /* accounts for error case too and overwrites with own error */
1348  if (box->w < 0.0f || box->h < 0.0f) {
1349  MEM_freeN(boxarray);
1350  PyErr_SetString(PyExc_TypeError,
1351  "error parsing width and height values from list: "
1352  "[x, y, w, h], not numbers or below zero");
1353  return -1;
1354  }
1355 
1356  /* verts will be added later */
1357  }
1358 
1359  *r_boxarray = boxarray;
1360  return 0;
1361 }
1362 
1363 static void boxPack_ToPyObject(PyObject *value, const BoxPack *boxarray)
1364 {
1365  Py_ssize_t len, i;
1366  PyObject *list_item;
1367 
1368  len = PyList_GET_SIZE(value);
1369 
1370  for (i = 0; i < len; i++) {
1371  const BoxPack *box = &boxarray[i];
1372  list_item = PyList_GET_ITEM(value, box->index);
1373  PyList_SET_ITEM(list_item, 0, PyFloat_FromDouble(box->x));
1374  PyList_SET_ITEM(list_item, 1, PyFloat_FromDouble(box->y));
1375  }
1376 }
1377 
1378 PyDoc_STRVAR(M_Geometry_box_pack_2d_doc,
1379  ".. function:: box_pack_2d(boxes)\n"
1380  "\n"
1381  " Returns a tuple with the width and height of the packed bounding box.\n"
1382  "\n"
1383  " :arg boxes: list of boxes, each box is a list where the first 4 items are [x, y, "
1384  "width, height, ...] other items are ignored.\n"
1385  " :type boxes: list\n"
1386  " :return: the width and height of the packed bounding box\n"
1387  " :rtype: tuple, pair of floats\n");
1388 static PyObject *M_Geometry_box_pack_2d(PyObject *UNUSED(self), PyObject *boxlist)
1389 {
1390  float tot_width = 0.0f, tot_height = 0.0f;
1391  Py_ssize_t len;
1392 
1393  PyObject *ret;
1394 
1395  if (!PyList_Check(boxlist)) {
1396  PyErr_SetString(PyExc_TypeError, "expected a list of boxes [[x, y, w, h], ... ]");
1397  return NULL;
1398  }
1399 
1400  len = PyList_GET_SIZE(boxlist);
1401  if (len) {
1402  BoxPack *boxarray = NULL;
1403  if (boxPack_FromPyObject(boxlist, &boxarray) == -1) {
1404  return NULL; /* exception set */
1405  }
1406 
1407  /* Non Python function */
1408  BLI_box_pack_2d(boxarray, len, &tot_width, &tot_height);
1409 
1410  boxPack_ToPyObject(boxlist, boxarray);
1411  MEM_freeN(boxarray);
1412  }
1413 
1414  ret = PyTuple_New(2);
1415  PyTuple_SET_ITEMS(ret, PyFloat_FromDouble(tot_width), PyFloat_FromDouble(tot_height));
1416  return ret;
1417 }
1418 
1419 PyDoc_STRVAR(M_Geometry_box_fit_2d_doc,
1420  ".. function:: box_fit_2d(points)\n"
1421  "\n"
1422  " Returns an angle that best fits the points to an axis aligned rectangle\n"
1423  "\n"
1424  " :arg points: list of 2d points.\n"
1425  " :type points: list\n"
1426  " :return: angle\n"
1427  " :rtype: float\n");
1428 static PyObject *M_Geometry_box_fit_2d(PyObject *UNUSED(self), PyObject *pointlist)
1429 {
1430  float(*points)[2];
1431  Py_ssize_t len;
1432 
1433  float angle = 0.0f;
1434 
1435  len = mathutils_array_parse_alloc_v(((float **)&points), 2, pointlist, "box_fit_2d");
1436  if (len == -1) {
1437  return NULL;
1438  }
1439 
1440  if (len) {
1441  /* Non Python function */
1443 
1444  PyMem_Free(points);
1445  }
1446 
1447  return PyFloat_FromDouble(angle);
1448 }
1449 
1450 PyDoc_STRVAR(M_Geometry_convex_hull_2d_doc,
1451  ".. function:: convex_hull_2d(points)\n"
1452  "\n"
1453  " Returns a list of indices into the list given\n"
1454  "\n"
1455  " :arg points: list of 2d points.\n"
1456  " :type points: list\n"
1457  " :return: a list of indices\n"
1458  " :rtype: list of ints\n");
1459 static PyObject *M_Geometry_convex_hull_2d(PyObject *UNUSED(self), PyObject *pointlist)
1460 {
1461  float(*points)[2];
1462  Py_ssize_t len;
1463 
1464  PyObject *ret;
1465 
1466  len = mathutils_array_parse_alloc_v(((float **)&points), 2, pointlist, "convex_hull_2d");
1467  if (len == -1) {
1468  return NULL;
1469  }
1470 
1471  if (len) {
1472  int *index_map;
1473  Py_ssize_t len_ret, i;
1474 
1475  index_map = MEM_mallocN(sizeof(*index_map) * len * 2, __func__);
1476 
1477  /* Non Python function */
1478  len_ret = BLI_convexhull_2d(points, len, index_map);
1479 
1480  ret = PyList_New(len_ret);
1481  for (i = 0; i < len_ret; i++) {
1482  PyList_SET_ITEM(ret, i, PyLong_FromLong(index_map[i]));
1483  }
1484 
1485  MEM_freeN(index_map);
1486 
1487  PyMem_Free(points);
1488  }
1489  else {
1490  ret = PyList_New(0);
1491  }
1492 
1493  return ret;
1494 }
1495 
1496 /* Return a PyObject that is a list of lists, using the flattened list array
1497  * to fill values, with start_table and len_table giving the start index
1498  * and length of the toplevel_len sub-lists.
1499  */
1500 static PyObject *list_of_lists_from_arrays(const int *array,
1501  const int *start_table,
1502  const int *len_table,
1503  int toplevel_len)
1504 {
1505  PyObject *ret, *sublist;
1506  int i, j, sublist_len, sublist_start, val;
1507 
1508  if (array == NULL) {
1509  return PyList_New(0);
1510  }
1511  ret = PyList_New(toplevel_len);
1512  for (i = 0; i < toplevel_len; i++) {
1513  sublist_len = len_table[i];
1514  sublist = PyList_New(sublist_len);
1515  sublist_start = start_table[i];
1516  for (j = 0; j < sublist_len; j++) {
1517  val = array[sublist_start + j];
1518  PyList_SET_ITEM(sublist, j, PyLong_FromLong(val));
1519  }
1520  PyList_SET_ITEM(ret, i, sublist);
1521  }
1522  return ret;
1523 }
1524 
1525 PyDoc_STRVAR(
1526  M_Geometry_delaunay_2d_cdt_doc,
1527  ".. function:: delaunay_2d_cdt(vert_coords, edges, faces, output_type, epsilon, "
1528  "need_ids=True)\n"
1529  "\n"
1530  " Computes the Constrained Delaunay Triangulation of a set of vertices,\n"
1531  " with edges and faces that must appear in the triangulation.\n"
1532  " Some triangles may be eaten away, or combined with other triangles,\n"
1533  " according to output type.\n"
1534  " The returned verts may be in a different order from input verts, may be moved\n"
1535  " slightly, and may be merged with other nearby verts.\n"
1536  " The three returned orig lists give, for each of verts, edges, and faces, the list of\n"
1537  " input element indices corresponding to the positionally same output element.\n"
1538  " For edges, the orig indices start with the input edges and then continue\n"
1539  " with the edges implied by each of the faces (n of them for an n-gon).\n"
1540  " If the need_ids argument is supplied, and False, then the code skips the preparation\n"
1541  " of the orig arrays, which may save some time."
1542  "\n"
1543  " :arg vert_coords: Vertex coordinates (2d)\n"
1544  " :type vert_coords: list of :class:`mathutils.Vector`\n"
1545  " :arg edges: Edges, as pairs of indices in `vert_coords`\n"
1546  " :type edges: list of (int, int)\n"
1547  " :arg faces: Faces, each sublist is a face, as indices in `vert_coords` (CCW oriented)\n"
1548  " :type faces: list of list of int\n"
1549  " :arg output_type: What output looks like. 0 => triangles with convex hull. "
1550  "1 => triangles inside constraints. "
1551  "2 => the input constraints, intersected. "
1552  "3 => like 2 but detect holes and omit them from output. "
1553  "4 => like 2 but with extra edges to make valid BMesh faces. "
1554  "5 => like 4 but detect holes and omit them from output.\n"
1555  " :type output_type: int\\n"
1556  " :arg epsilon: For nearness tests; should not be zero\n"
1557  " :type epsilon: float\n"
1558  " :arg need_ids: are the orig output arrays needed?\n"
1559  " :type need_args: bool\n"
1560  " :return: Output tuple, (vert_coords, edges, faces, orig_verts, orig_edges, orig_faces)\n"
1561  " :rtype: (list of `mathutils.Vector`, "
1562  "list of (int, int), "
1563  "list of list of int, "
1564  "list of list of int, "
1565  "list of list of int, "
1566  "list of list of int)\n"
1567  "\n");
1568 static PyObject *M_Geometry_delaunay_2d_cdt(PyObject *UNUSED(self), PyObject *args)
1569 {
1570  const char *error_prefix = "delaunay_2d_cdt";
1571  PyObject *vert_coords, *edges, *faces, *item;
1572  int output_type;
1573  float epsilon;
1574  bool need_ids = true;
1575  float(*in_coords)[2] = NULL;
1576  int(*in_edges)[2] = NULL;
1577  int *in_faces = NULL;
1578  int *in_faces_start_table = NULL;
1579  int *in_faces_len_table = NULL;
1580  Py_ssize_t vert_coords_len, edges_len, faces_len;
1581  CDT_input in;
1582  CDT_result *res = NULL;
1583  PyObject *out_vert_coords = NULL;
1584  PyObject *out_edges = NULL;
1585  PyObject *out_faces = NULL;
1586  PyObject *out_orig_verts = NULL;
1587  PyObject *out_orig_edges = NULL;
1588  PyObject *out_orig_faces = NULL;
1589  PyObject *ret_value = NULL;
1590  int i;
1591 
1592  if (!PyArg_ParseTuple(args,
1593  "OOOif|p:delaunay_2d_cdt",
1594  &vert_coords,
1595  &edges,
1596  &faces,
1597  &output_type,
1598  &epsilon,
1599  &need_ids)) {
1600  return NULL;
1601  }
1602 
1603  vert_coords_len = mathutils_array_parse_alloc_v(
1604  (float **)&in_coords, 2, vert_coords, error_prefix);
1605  if (vert_coords_len == -1) {
1606  return NULL;
1607  }
1608 
1609  edges_len = mathutils_array_parse_alloc_vi((int **)&in_edges, 2, edges, error_prefix);
1610  if (edges_len == -1) {
1611  goto exit_cdt;
1612  }
1613 
1615  &in_faces, &in_faces_start_table, &in_faces_len_table, faces, error_prefix);
1616  if (faces_len == -1) {
1617  goto exit_cdt;
1618  }
1619 
1620  in.verts_len = (int)vert_coords_len;
1621  in.vert_coords = in_coords;
1622  in.edges_len = edges_len;
1623  in.faces_len = faces_len;
1624  in.edges = in_edges;
1625  in.faces = in_faces;
1626  in.faces_start_table = in_faces_start_table;
1627  in.faces_len_table = in_faces_len_table;
1628  in.epsilon = epsilon;
1629  in.need_ids = need_ids;
1630 
1631  res = BLI_delaunay_2d_cdt_calc(&in, output_type);
1632 
1633  ret_value = PyTuple_New(6);
1634 
1635  out_vert_coords = PyList_New(res->verts_len);
1636  for (i = 0; i < res->verts_len; i++) {
1637  item = Vector_CreatePyObject(res->vert_coords[i], 2, NULL);
1638  if (item == NULL) {
1639  Py_DECREF(ret_value);
1640  Py_DECREF(out_vert_coords);
1641  goto exit_cdt;
1642  }
1643  PyList_SET_ITEM(out_vert_coords, i, item);
1644  }
1645  PyTuple_SET_ITEM(ret_value, 0, out_vert_coords);
1646 
1647  out_edges = PyList_New(res->edges_len);
1648  for (i = 0; i < res->edges_len; i++) {
1649  item = PyTuple_New(2);
1650  PyTuple_SET_ITEM(item, 0, PyLong_FromLong((long)res->edges[i][0]));
1651  PyTuple_SET_ITEM(item, 1, PyLong_FromLong((long)res->edges[i][1]));
1652  PyList_SET_ITEM(out_edges, i, item);
1653  }
1654  PyTuple_SET_ITEM(ret_value, 1, out_edges);
1655 
1656  out_faces = list_of_lists_from_arrays(
1657  res->faces, res->faces_start_table, res->faces_len_table, res->faces_len);
1658  PyTuple_SET_ITEM(ret_value, 2, out_faces);
1659 
1660  out_orig_verts = list_of_lists_from_arrays(
1662  PyTuple_SET_ITEM(ret_value, 3, out_orig_verts);
1663 
1664  out_orig_edges = list_of_lists_from_arrays(
1666  PyTuple_SET_ITEM(ret_value, 4, out_orig_edges);
1667 
1668  out_orig_faces = list_of_lists_from_arrays(
1670  PyTuple_SET_ITEM(ret_value, 5, out_orig_faces);
1671 
1672 exit_cdt:
1673  if (in_coords != NULL) {
1674  PyMem_Free(in_coords);
1675  }
1676  if (in_edges != NULL) {
1677  PyMem_Free(in_edges);
1678  }
1679  if (in_faces != NULL) {
1680  PyMem_Free(in_faces);
1681  }
1682  if (in_faces_start_table != NULL) {
1683  PyMem_Free(in_faces_start_table);
1684  }
1685  if (in_faces_len_table != NULL) {
1686  PyMem_Free(in_faces_len_table);
1687  }
1688  if (res) {
1690  }
1691  return ret_value;
1692 }
1693 
1694 #endif /* MATH_STANDALONE */
1695 
1696 static PyMethodDef M_Geometry_methods[] = {
1697  {"intersect_ray_tri",
1698  (PyCFunction)M_Geometry_intersect_ray_tri,
1699  METH_VARARGS,
1700  M_Geometry_intersect_ray_tri_doc},
1701  {"intersect_point_line",
1702  (PyCFunction)M_Geometry_intersect_point_line,
1703  METH_VARARGS,
1704  M_Geometry_intersect_point_line_doc},
1705  {"intersect_point_tri",
1706  (PyCFunction)M_Geometry_intersect_point_tri,
1707  METH_VARARGS,
1708  M_Geometry_intersect_point_tri_doc},
1709  {"closest_point_on_tri",
1710  (PyCFunction)M_Geometry_closest_point_on_tri,
1711  METH_VARARGS,
1712  M_Geometry_closest_point_on_tri_doc},
1713  {"intersect_point_tri_2d",
1714  (PyCFunction)M_Geometry_intersect_point_tri_2d,
1715  METH_VARARGS,
1716  M_Geometry_intersect_point_tri_2d_doc},
1717  {"intersect_point_quad_2d",
1719  METH_VARARGS,
1720  M_Geometry_intersect_point_quad_2d_doc},
1721  {"intersect_line_line",
1722  (PyCFunction)M_Geometry_intersect_line_line,
1723  METH_VARARGS,
1724  M_Geometry_intersect_line_line_doc},
1725  {"intersect_line_line_2d",
1726  (PyCFunction)M_Geometry_intersect_line_line_2d,
1727  METH_VARARGS,
1728  M_Geometry_intersect_line_line_2d_doc},
1729  {"intersect_line_plane",
1730  (PyCFunction)M_Geometry_intersect_line_plane,
1731  METH_VARARGS,
1732  M_Geometry_intersect_line_plane_doc},
1733  {"intersect_plane_plane",
1734  (PyCFunction)M_Geometry_intersect_plane_plane,
1735  METH_VARARGS,
1736  M_Geometry_intersect_plane_plane_doc},
1737  {"intersect_line_sphere",
1738  (PyCFunction)M_Geometry_intersect_line_sphere,
1739  METH_VARARGS,
1740  M_Geometry_intersect_line_sphere_doc},
1741  {"intersect_line_sphere_2d",
1743  METH_VARARGS,
1744  M_Geometry_intersect_line_sphere_2d_doc},
1745  {"distance_point_to_plane",
1747  METH_VARARGS,
1748  M_Geometry_distance_point_to_plane_doc},
1749  {"intersect_sphere_sphere_2d",
1751  METH_VARARGS,
1752  M_Geometry_intersect_sphere_sphere_2d_doc},
1753  {"intersect_tri_tri_2d",
1754  (PyCFunction)M_Geometry_intersect_tri_tri_2d,
1755  METH_VARARGS,
1756  M_Geometry_intersect_tri_tri_2d_doc},
1757  {"area_tri", (PyCFunction)M_Geometry_area_tri, METH_VARARGS, M_Geometry_area_tri_doc},
1758  {"volume_tetrahedron",
1759  (PyCFunction)M_Geometry_volume_tetrahedron,
1760  METH_VARARGS,
1761  M_Geometry_volume_tetrahedron_doc},
1762  {"normal", (PyCFunction)M_Geometry_normal, METH_VARARGS, M_Geometry_normal_doc},
1763  {"barycentric_transform",
1764  (PyCFunction)M_Geometry_barycentric_transform,
1765  METH_VARARGS,
1766  M_Geometry_barycentric_transform_doc},
1767  {"points_in_planes",
1768  (PyCFunction)M_Geometry_points_in_planes,
1769  METH_VARARGS,
1770  M_Geometry_points_in_planes_doc},
1771 #ifndef MATH_STANDALONE
1772  {"interpolate_bezier",
1773  (PyCFunction)M_Geometry_interpolate_bezier,
1774  METH_VARARGS,
1775  M_Geometry_interpolate_bezier_doc},
1776  {"tessellate_polygon",
1777  (PyCFunction)M_Geometry_tessellate_polygon,
1778  METH_O,
1779  M_Geometry_tessellate_polygon_doc},
1780  {"convex_hull_2d",
1781  (PyCFunction)M_Geometry_convex_hull_2d,
1782  METH_O,
1783  M_Geometry_convex_hull_2d_doc},
1784  {"delaunay_2d_cdt",
1785  (PyCFunction)M_Geometry_delaunay_2d_cdt,
1786  METH_VARARGS,
1787  M_Geometry_delaunay_2d_cdt_doc},
1788  {"box_fit_2d", (PyCFunction)M_Geometry_box_fit_2d, METH_O, M_Geometry_box_fit_2d_doc},
1789  {"box_pack_2d", (PyCFunction)M_Geometry_box_pack_2d, METH_O, M_Geometry_box_pack_2d_doc},
1790 #endif
1791  {NULL, NULL, 0, NULL},
1792 };
1793 
1794 static struct PyModuleDef M_Geometry_module_def = {
1795  PyModuleDef_HEAD_INIT,
1796  "mathutils.geometry", /* m_name */
1797  M_Geometry_doc, /* m_doc */
1798  0, /* m_size */
1799  M_Geometry_methods, /* m_methods */
1800  NULL, /* m_reload */
1801  NULL, /* m_traverse */
1802  NULL, /* m_clear */
1803  NULL, /* m_free */
1804 };
1805 
1806 /*----------------------------MODULE INIT-------------------------*/
1807 PyMODINIT_FUNC PyInit_mathutils_geometry(void)
1808 {
1809  PyObject *submodule = PyModule_Create(&M_Geometry_module_def);
1810  return submodule;
1811 }
typedef float(TangentPoint)[2]
void BKE_curve_forward_diff_bezier(float q0, float q1, float q2, float q3, float *p, int it, int stride)
Definition: curve.cc:1717
display list (or rather multi purpose list) stuff.
void BKE_displist_free(struct ListBase *lb)
Definition: displist.cc:69
@ DL_INDEX3
Definition: BKE_displist.h:26
@ DL_POLY
Definition: BKE_displist.h:20
void BKE_displist_fill(const struct ListBase *dispbase, struct ListBase *to, const float normal_proj[3], bool flip_normal)
void BLI_box_pack_2d(BoxPack *boxarray, unsigned int len, float *r_tot_x, float *r_tot_y)
Definition: boxpack_2d.c:269
int BLI_convexhull_2d(const float(*points)[2], int n, int r_points[])
float BLI_convexhull_aabb_fit_points_2d(const float(*points)[2], unsigned int n)
CDT_result * BLI_delaunay_2d_cdt_calc(const CDT_input *input, const CDT_output_type output_type)
void BLI_delaunay_2d_cdt_free(CDT_result *result)
void BLI_addtail(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition: listbase.c:80
MINLINE int max_ii(int a, int b)
bool isect_tri_tri_v2(const float p1[2], const float q1[2], const float r1[2], const float p2[2], const float q2[2], const float r2[2])
Definition: math_geom.c:2541
void plane_from_point_normal_v3(float r_plane[4], const float plane_co[3], const float plane_no[3])
Definition: math_geom.c:209
int isect_point_quad_v2(const float p[2], const float v1[2], const float v2[2], const float v3[2], const float v4[2])
Definition: math_geom.c:1536
int isect_line_line_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3], float r_i1[3], float r_i2[3])
Definition: math_geom.c:2935
MINLINE float area_tri_v2(const float v1[2], const float v2[2], const float v3[2])
bool isect_plane_plane_v3(const float plane_a[4], const float plane_b[4], float r_isect_co[3], float r_isect_no[3]) ATTR_WARN_UNUSED_RESULT
Definition: math_geom.c:2134
void transform_point_by_tri_v3(float pt_tar[3], float const pt_src[3], const float tri_tar_p1[3], const float tri_tar_p2[3], const float tri_tar_p3[3], const float tri_src_p1[3], const float tri_src_p2[3], const float tri_src_p3[3])
Definition: math_geom.c:3862
int isect_line_sphere_v3(const float l1[3], const float l2[3], const float sp[3], float r, float r_p1[3], float r_p2[3])
Definition: math_geom.c:1349
bool isect_point_tri_v3(const float p[3], const float v1[3], const float v2[3], const float v3[3], float r_isect_co[3])
Definition: math_geom.c:3397
int isect_line_sphere_v2(const float l1[2], const float l2[2], const float sp[2], float r, float r_p1[2], float r_p2[2])
Definition: math_geom.c:1411
float line_point_factor_v2(const float p[2], const float l1[2], const float l2[2])
Definition: math_geom.c:3274
void closest_on_tri_to_point_v3(float r[3], const float p[3], const float v1[3], const float v2[3], const float v3[3])
Definition: math_geom.c:980
float dist_signed_to_plane_v3(const float p[3], const float plane[4])
Definition: math_geom.c:461
float area_tri_v3(const float v1[3], const float v2[3], const float v3[3])
Definition: math_geom.c:92
int isect_seg_seg_v2_point(const float v0[2], const float v1[2], const float v2[2], const float v3[2], float vi[2])
Definition: math_geom.c:1296
float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3])
Definition: math_geom.c:3254
float closest_to_line_v3(float r_close[3], const float p[3], const float l1[3], const float l2[3])
Definition: math_geom.c:3176
bool isect_line_plane_v3(float r_isect_co[3], const float l1[3], const float l2[3], const float plane_co[3], const float plane_no[3]) ATTR_WARN_UNUSED_RESULT
Definition: math_geom.c:2078
float normal_poly_v3(float n[3], const float verts[][3], unsigned int nr)
Definition: math_geom.c:71
int isect_point_tri_v2(const float pt[2], const float v1[2], const float v2[2], const float v3[2])
Definition: math_geom.c:1516
bool isect_planes_v3_fn(const float planes[][4], int planes_len, float eps_coplanar, float eps_isect, void(*callback_fn)(const float co[3], int i, int j, int k, void *user_data), void *user_data)
Definition: math_geom.c:2168
float volume_tetrahedron_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
Definition: math_geom.c:231
MINLINE float normalize_v3(float r[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void mul_v3_fl(float r[3], float f)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void add_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void sub_v2_v2v2(float r[2], const float a[2], const float b[2])
MINLINE float len_v2(const float a[2]) ATTR_WARN_UNUSED_RESULT
unsigned int uint
Definition: BLI_sys_types.h:67
#define UNPACK3_EX(pre, a, post)
#define UNPACK4(a)
#define ARRAY_SIZE(arr)
#define UNPACK4_EX(pre, a, post)
#define UNUSED(x)
#define UNPACK3(a)
#define UNLIKELY(x)
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint i1
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble y2 _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat y2 _GL_VOID_RET _GL_VOID GLint GLint GLint y2 _GL_VOID_RET _GL_VOID GLshort GLshort GLshort y2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLuint *buffer _GL_VOID_RET _GL_VOID GLdouble t _GL_VOID_RET _GL_VOID GLfloat t _GL_VOID_RET _GL_VOID GLint t _GL_VOID_RET _GL_VOID GLshort t _GL_VOID_RET _GL_VOID GLdouble t
Read Guarded memory(de)allocation.
ATTR_WARN_UNUSED_RESULT const BMVert * v
SIMD_FORCE_INLINE btScalar angle(const btVector3 &v) const
Return the angle between this and another vector.
Definition: btVector3.h:356
#define powf(x, y)
Definition: cuda/compat.h:103
void * user_data
int len
Definition: draw_manager.c:108
GPUBatch * quad
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_callocN)(size_t len, const char *str)
Definition: mallocn.c:31
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
int mathutils_array_parse_alloc_viseq(int **array, int **start_table, int **len_table, PyObject *value, const char *error_prefix)
Definition: mathutils.c:372
int mathutils_array_parse(float *array, int array_num_min, int array_num_max, PyObject *value, const char *error_prefix)
Definition: mathutils.c:98
int mathutils_array_parse_alloc_vi(int **array, int array_dim, PyObject *value, const char *error_prefix)
Definition: mathutils.c:335
int mathutils_array_parse_alloc_v(float **array, int array_dim, PyObject *value, const char *error_prefix)
Definition: mathutils.c:259
#define MU_ARRAY_ZERO
Definition: mathutils.h:203
#define MU_ARRAY_SPILL
Definition: mathutils.h:206
PyObject * Vector_CreatePyObject(const float *vec, const int vec_num, PyTypeObject *base_type)
static PyObject * M_Geometry_intersect_ray_tri(PyObject *UNUSED(self), PyObject *args)
PyDoc_STRVAR(M_Geometry_doc, "The Blender geometry module")
static PyObject * M_Geometry_intersect_line_line(PyObject *UNUSED(self), PyObject *args)
static PyObject * M_Geometry_intersect_line_line_2d(PyObject *UNUSED(self), PyObject *args)
static PyObject * M_Geometry_intersect_point_quad_2d(PyObject *UNUSED(self), PyObject *args)
static PyObject * M_Geometry_closest_point_on_tri(PyObject *UNUSED(self), PyObject *args)
static PyObject * M_Geometry_volume_tetrahedron(PyObject *UNUSED(self), PyObject *args)
static PyObject * M_Geometry_normal(PyObject *UNUSED(self), PyObject *args)
static PyObject * M_Geometry_points_in_planes(PyObject *UNUSED(self), PyObject *args)
static PyObject * M_Geometry_barycentric_transform(PyObject *UNUSED(self), PyObject *args)
static PyObject * M_Geometry_intersect_line_sphere_2d(PyObject *UNUSED(self), PyObject *args)
static PyObject * M_Geometry_intersect_sphere_sphere_2d(PyObject *UNUSED(self), PyObject *args)
static PyObject * M_Geometry_distance_point_to_plane(PyObject *UNUSED(self), PyObject *args)
static PyObject * M_Geometry_intersect_point_line(PyObject *UNUSED(self), PyObject *args)
static PyObject * M_Geometry_intersect_plane_plane(PyObject *UNUSED(self), PyObject *args)
static PyObject * M_Geometry_intersect_point_tri(PyObject *UNUSED(self), PyObject *args)
static PyObject * M_Geometry_intersect_point_tri_2d(PyObject *UNUSED(self), PyObject *args)
static PyObject * M_Geometry_intersect_line_sphere(PyObject *UNUSED(self), PyObject *args)
static int boxPack_FromPyObject(PyObject *value, BoxPack **r_boxarray)
static PyObject * M_Geometry_intersect_line_plane(PyObject *UNUSED(self), PyObject *args)
static void points_in_planes_fn(const float co[3], int i, int j, int k, void *user_data_p)
static PyObject * M_Geometry_box_pack_2d(PyObject *UNUSED(self), PyObject *boxlist)
static PyObject * M_Geometry_interpolate_bezier(PyObject *UNUSED(self), PyObject *args)
static void boxPack_ToPyObject(PyObject *value, const BoxPack *boxarray)
static PyObject * M_Geometry_intersect_tri_tri_2d(PyObject *UNUSED(self), PyObject *args)
static PyObject * M_Geometry_tessellate_polygon(PyObject *UNUSED(self), PyObject *polyLineSeq)
static PyObject * M_Geometry_area_tri(PyObject *UNUSED(self), PyObject *args)
PyMODINIT_FUNC PyInit_mathutils_geometry(void)
static char faces[256]
#define fabsf(x)
Definition: metal/compat.h:219
static double epsilon
int PyC_ParseBool(PyObject *o, void *p)
#define PyC_Tuple_Pack_I32(...)
Definition: py_capi_utils.h:88
#define PyTuple_SET_ITEMS(op_arg,...)
return ret
float(* vert_coords)[2]
int(* edges)[2]
int * faces_len_table
int * faces_start_table
int * faces_start_table
int * verts_orig_len_table
int * edges_orig_len_table
int * verts_orig_start_table
int * faces_orig_start_table
int * edges_orig_start_table
int * faces_orig_len_table
int(* edges)[2]
int * faces_len_table
float(* vert_coords)[2]
short type
Definition: BKE_displist.h:55
short col
Definition: BKE_displist.h:57
float * verts
Definition: BKE_displist.h:58
int * index
Definition: BKE_displist.h:59
void * first
Definition: DNA_listBase.h:31