curve_tools/intersections.py

   1 # SPDX-License-Identifier: GPL-2.0-or-later
   2
   3 import bpy
   4 from . import mathematics
   5 from . import curves
   6 from . import util
   7
   8 from mathutils import Vector
   9
  10 algoPOV = None
  11 algoDIR = None
  12
  13
  14 class BezierSegmentIntersectionPoint:
  15     def __init__(self, segment, parameter, intersectionPoint):
  16         self.segment = segment
  17         self.parameter = parameter
  18         self.intersectionPoint = intersectionPoint
  19
  20
  21 class BezierSegmentsIntersector:
  22     def __init__(self, segment1, segment2, worldMatrix1, worldMatrix2):
  23         self.segment1 = segment1
  24         self.segment2 = segment2
  25         self.worldMatrix1 = worldMatrix1
  26         self.worldMatrix2 = worldMatrix2
  27
  28     def CalcFirstIntersection(self, nrSamples1, nrSamples2):
  29         algorithm = bpy.context.scene.curvetools.IntersectCurvesAlgorithm
  30
  31         if algorithm == '3D':
  32             return self.CalcFirstRealIntersection3D(nrSamples1, nrSamples2)
  33
  34         if algorithm == 'From_View':
  35             global algoDIR
  36             if algoDIR is not None:
  37                 return self.CalcFirstRealIntersectionFromViewDIR(nrSamples1, nrSamples2)
  38
  39             global algoPOV
  40             if algoPOV is not None:
  41                 return self.CalcFirstRealIntersectionFromViewPOV(nrSamples1, nrSamples2)
  42
  43         return None
  44
  45     def CalcFirstIntersection3D(self, nrSamples1, nrSamples2):
  46         fltNrSamples1 = float(nrSamples1)
  47         fltNrSamples2 = float(nrSamples2)
  48
  49         limitDistance = bpy.context.scene.curvetools.LimitDistance
  50
  51         for iSample1 in range(nrSamples1):
  52             segPar10 = float(iSample1) / fltNrSamples1
  53             segPar11 = float(iSample1 + 1) / fltNrSamples1
  54             P0 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=segPar10)
  55             P1 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=segPar11)
  56
  57             for iSample2 in range(nrSamples2):
  58                 segPar20 = float(iSample2) / fltNrSamples2
  59                 segPar21 = float(iSample2 + 1) / fltNrSamples2
  60                 Q0 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=segPar20)
  61                 Q1 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=segPar21)
  62
  63                 intersectionPointData = mathematics.CalcIntersectionPointLineSegments(P0, P1, Q0, Q1, limitDistance)
  64                 if intersectionPointData is None:
  65                     continue
  66
  67                 intersectionSegment1Parameter = segPar10 + (intersectionPointData[0] / fltNrSamples1)
  68                 intersectionPoint1 = BezierSegmentIntersectionPoint(self.segment1,
  69                                                                     intersectionSegment1Parameter,
  70                                                                     intersectionPointData[2])
  71
  72                 intersectionSegment2Parameter = segPar20 + (intersectionPointData[1] / fltNrSamples2)
  73                 intersectionPoint2 = BezierSegmentIntersectionPoint(self.segment2,
  74                                                                     intersectionSegment2Parameter,
  75                                                                     intersectionPointData[3])
  76
  77                 return [intersectionPoint1, intersectionPoint2]
  78
  79         return None
  80
  81     def CalcFirstRealIntersection3D(self, nrSamples1, nrSamples2):
  82         fltNrSamples1 = float(nrSamples1)
  83         fltNrSamples2 = float(nrSamples2)
  84
  85         limitDistance = bpy.context.scene.curvetools.LimitDistance
  86
  87         for iSample1 in range(nrSamples1):
  88             segPar10 = float(iSample1) / fltNrSamples1
  89             segPar11 = float(iSample1 + 1) / fltNrSamples1
  90             P0 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=segPar10)
  91             P1 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=segPar11)
  92
  93             for iSample2 in range(nrSamples2):
  94                 segPar20 = float(iSample2) / fltNrSamples2
  95                 segPar21 = float(iSample2 + 1) / fltNrSamples2
  96                 Q0 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=segPar20)
  97                 Q1 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=segPar21)
  98
  99                 intersectionPointData = mathematics.CalcIntersectionPointLineSegments(P0, P1, Q0, Q1, limitDistance)
 100                 if intersectionPointData is None:
 101                     continue
 102
 103                 # intersection point can't be an existing point
 104                 intersectionSegment1Parameter = segPar10 + (intersectionPointData[0] / (fltNrSamples1))
 105                 worldPoint1 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=intersectionSegment1Parameter)
 106                 if (mathematics.IsSamePoint(P0, worldPoint1, limitDistance)) or \
 107                    (mathematics.IsSamePoint(P1, worldPoint1, limitDistance)):
 108
 109                     intersectionPoint1 = None
 110                 else:
 111                     intersectionPoint1 = BezierSegmentIntersectionPoint(self.segment1,
 112                                                                         intersectionSegment1Parameter,
 113                                                                         worldPoint1)
 114
 115                 intersectionSegment2Parameter = segPar20 + (intersectionPointData[1] / (fltNrSamples2))
 116                 worldPoint2 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=intersectionSegment2Parameter)
 117                 if (mathematics.IsSamePoint(Q0, worldPoint2, limitDistance)) or \
 118                    (mathematics.IsSamePoint(Q1, worldPoint2, limitDistance)):
 119
 120                     intersectionPoint2 = None
 121                 else:
 122                     intersectionPoint2 = BezierSegmentIntersectionPoint(self.segment2,
 123                                                                         intersectionSegment2Parameter,
 124                                                                         worldPoint2)
 125
 126                 return [intersectionPoint1, intersectionPoint2]
 127
 128         return None
 129
 130     def CalcFirstIntersectionFromViewDIR(self, nrSamples1, nrSamples2):
 131         global algoDIR
 132
 133         fltNrSamples1 = float(nrSamples1)
 134         fltNrSamples2 = float(nrSamples2)
 135
 136         for iSample1 in range(nrSamples1):
 137             segPar10 = float(iSample1) / fltNrSamples1
 138             segPar11 = float(iSample1 + 1) / fltNrSamples1
 139             P0 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=segPar10)
 140             P1 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=segPar11)
 141
 142             for iSample2 in range(nrSamples2):
 143                 segPar20 = float(iSample2) / fltNrSamples2
 144                 segPar21 = float(iSample2 + 1) / fltNrSamples2
 145                 Q0 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=segPar20)
 146                 Q1 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=segPar21)
 147
 148                 intersectionPointData = mathematics.CalcIntersectionPointsLineSegmentsDIR(P0, P1, Q0, Q1, algoDIR)
 149                 if intersectionPointData is None:
 150                     continue
 151
 152                 intersectionSegment1Parameter = segPar10 + (intersectionPointData[0] / fltNrSamples1)
 153                 worldPoint1 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=intersectionSegment1Parameter)
 154                 intersectionPoint1 = BezierSegmentIntersectionPoint(self.segment1,
 155                                                                     intersectionSegment1Parameter,
 156                                                                     worldPoint1)
 157
 158                 intersectionSegment2Parameter = segPar20 + (intersectionPointData[1] / fltNrSamples2)
 159                 worldPoint2 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=intersectionSegment2Parameter)
 160                 intersectionPoint2 = BezierSegmentIntersectionPoint(self.segment2,
 161                                                                     intersectionSegment2Parameter,
 162                                                                     worldPoint2)
 163
 164                 return [intersectionPoint1, intersectionPoint2]
 165
 166         return None
 167
 168     def CalcFirstRealIntersectionFromViewDIR(self, nrSamples1, nrSamples2):
 169         global algoDIR
 170
 171         fltNrSamples1 = float(nrSamples1)
 172         fltNrSamples2 = float(nrSamples2)
 173
 174         limitDistance = bpy.context.scene.curvetools.LimitDistance
 175
 176         for iSample1 in range(nrSamples1):
 177             segPar10 = float(iSample1) / fltNrSamples1
 178             segPar11 = float(iSample1 + 1) / fltNrSamples1
 179             P0 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=segPar10)
 180             P1 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=segPar11)
 181
 182             for iSample2 in range(nrSamples2):
 183                 segPar20 = float(iSample2) / fltNrSamples2
 184                 segPar21 = float(iSample2 + 1) / fltNrSamples2
 185                 Q0 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=segPar20)
 186                 Q1 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=segPar21)
 187
 188                 intersectionPointData = mathematics.CalcIntersectionPointsLineSegmentsDIR(P0, P1, Q0, Q1, algoDIR)
 189                 if intersectionPointData is None:
 190                     continue
 191
 192                 # intersection point can't be an existing point
 193                 intersectionSegment1Parameter = segPar10 + (intersectionPointData[0] / (fltNrSamples1))
 194                 worldPoint1 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=intersectionSegment1Parameter)
 195                 if (mathematics.IsSamePoint(P0, worldPoint1, limitDistance)) or \
 196                    (mathematics.IsSamePoint(P1, worldPoint1, limitDistance)):
 197
 198                     intersectionPoint1 = None
 199                 else:
 200                     intersectionPoint1 = BezierSegmentIntersectionPoint(self.segment1,
 201                                                                         intersectionSegment1Parameter,
 202                                                                         worldPoint1)
 203
 204                 intersectionSegment2Parameter = segPar20 + (intersectionPointData[1] / (fltNrSamples2))
 205                 worldPoint2 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=intersectionSegment2Parameter)
 206                 if (mathematics.IsSamePoint(Q0, worldPoint2, limitDistance)) or \
 207                    (mathematics.IsSamePoint(Q1, worldPoint2, limitDistance)):
 208
 209                     intersectionPoint2 = None
 210                 else:
 211                     intersectionPoint2 = BezierSegmentIntersectionPoint(self.segment2,
 212                                                                         intersectionSegment2Parameter,
 213                                                                         worldPoint2)
 214
 215                 return [intersectionPoint1, intersectionPoint2]
 216
 217         return None
 218
 219     def CalcFirstIntersectionFromViewPOV(self, nrSamples1, nrSamples2):
 220         global algoPOV
 221
 222         fltNrSamples1 = float(nrSamples1)
 223         fltNrSamples2 = float(nrSamples2)
 224
 225         for iSample1 in range(nrSamples1):
 226             segPar10 = float(iSample1) / fltNrSamples1
 227             segPar11 = float(iSample1 + 1) / fltNrSamples1
 228             P0 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=segPar10)
 229             P1 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=segPar11)
 230
 231             for iSample2 in range(nrSamples2):
 232                 segPar20 = float(iSample2) / fltNrSamples2
 233                 segPar21 = float(iSample2 + 1) / fltNrSamples2
 234                 Q0 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=segPar20)
 235                 Q1 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=segPar21)
 236
 237                 intersectionPointData = mathematics.CalcIntersectionPointsLineSegmentsPOV(P0, P1, Q0, Q1, algoPOV)
 238                 if intersectionPointData is None:
 239                     continue
 240
 241                 intersectionSegment1Parameter = segPar10 + (intersectionPointData[0] / fltNrSamples1)
 242                 worldPoint1 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=intersectionSegment1Parameter)
 243                 intersectionPoint1 = BezierSegmentIntersectionPoint(self.segment1,
 244                                                                     intersectionSegment1Parameter,
 245                                                                     worldPoint1)
 246
 247                 intersectionSegment2Parameter = segPar20 + (intersectionPointData[1] / fltNrSamples2)
 248                 worldPoint2 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=intersectionSegment2Parameter)
 249                 intersectionPoint2 = BezierSegmentIntersectionPoint(self.segment2,
 250                                                                     intersectionSegment2Parameter,
 251                                                                     worldPoint2)
 252
 253                 return [intersectionPoint1, intersectionPoint2]
 254
 255         return None
 256
 257     def CalcFirstRealIntersectionFromViewPOV(self, nrSamples1, nrSamples2):
 258         global algoPOV
 259
 260         fltNrSamples1 = float(nrSamples1)
 261         fltNrSamples2 = float(nrSamples2)
 262
 263         limitDistance = bpy.context.scene.curvetools.LimitDistance
 264
 265         for iSample1 in range(nrSamples1):
 266             segPar10 = float(iSample1) / fltNrSamples1
 267             segPar11 = float(iSample1 + 1) / fltNrSamples1
 268             P0 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=segPar10)
 269             P1 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=segPar11)
 270
 271             for iSample2 in range(nrSamples2):
 272                 segPar20 = float(iSample2) / fltNrSamples2
 273                 segPar21 = float(iSample2 + 1) / fltNrSamples2
 274                 Q0 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=segPar20)
 275                 Q1 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=segPar21)
 276
 277                 intersectionPointData = mathematics.CalcIntersectionPointsLineSegmentsPOV(P0, P1, Q0, Q1, algoPOV)
 278                 if intersectionPointData is None:
 279                     continue
 280
 281                 # intersection point can't be an existing point
 282                 intersectionSegment1Parameter = segPar10 + (intersectionPointData[0] / fltNrSamples1)
 283                 worldPoint1 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=intersectionSegment1Parameter)
 284                 if (mathematics.IsSamePoint(P0, worldPoint1, limitDistance)) or \
 285                    (mathematics.IsSamePoint(P1, worldPoint1, limitDistance)):
 286
 287                     intersectionPoint1 = None
 288                 else:
 289                     intersectionPoint1 = BezierSegmentIntersectionPoint(self.segment1,
 290                                                                         intersectionSegment1Parameter,
 291                                                                         worldPoint1)
 292
 293                 intersectionSegment2Parameter = segPar20 + (intersectionPointData[1] / fltNrSamples2)
 294                 worldPoint2 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=intersectionSegment2Parameter)
 295                 if (mathematics.IsSamePoint(Q0, worldPoint2, limitDistance)) or \
 296                    (mathematics.IsSamePoint(Q1, worldPoint2, limitDistance)):
 297
 298                     intersectionPoint2 = None
 299                 else:
 300                     intersectionPoint2 = BezierSegmentIntersectionPoint(self.segment2,
 301                                                                         intersectionSegment2Parameter,
 302                                                                         worldPoint2)
 303
 304                 return [intersectionPoint1, intersectionPoint2]
 305
 306         return None
 307
 308     def CalcIntersections(self, nrSamples1, nrSamples2):
 309         algorithm = bpy.context.scene.curvetools.IntersectCurvesAlgorithm
 310
 311         if algorithm == '3D':
 312             return self.CalcIntersections3D(nrSamples1, nrSamples2)
 313
 314         if algorithm == 'From_View':
 315             global algoDIR
 316             if algoDIR is not None:
 317                 return self.CalcIntersectionsFromViewDIR(nrSamples1, nrSamples2)
 318
 319             global algoPOV
 320             if algoPOV is not None:
 321                 return self.CalcIntersectionsFromViewPOV(nrSamples1, nrSamples2)
 322
 323         return [[], []]
 324
 325     def CalcIntersections3D(self, nrSamples1, nrSamples2):
 326         rvIntersections1 = []
 327         rvIntersections2 = []
 328
 329         fltNrSamples1 = float(nrSamples1)
 330         fltNrSamples2 = float(nrSamples2)
 331
 332         limitDistance = bpy.context.scene.curvetools.LimitDistance
 333
 334         for iSample1 in range(nrSamples1):
 335             segPar10 = float(iSample1) / fltNrSamples1
 336             segPar11 = float(iSample1 + 1) / fltNrSamples1
 337             P0 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=segPar10)
 338             P1 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=segPar11)
 339
 340             for iSample2 in range(nrSamples2):
 341                 segPar20 = float(iSample2) / fltNrSamples2
 342                 segPar21 = float(iSample2 + 1) / fltNrSamples2
 343                 Q0 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=segPar20)
 344                 Q1 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=segPar21)
 345
 346                 intersectionPointData = mathematics.CalcIntersectionPointLineSegments(P0, P1, Q0, Q1, limitDistance)
 347                 if intersectionPointData is None:
 348                     continue
 349
 350                 intersectionSegment1Parameter = segPar10 + (intersectionPointData[0] / fltNrSamples1)
 351                 worldPoint1 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=intersectionSegment1Parameter)
 352                 intersectionPoint1 = BezierSegmentIntersectionPoint(self.segment1,
 353                                                                     intersectionSegment1Parameter,
 354                                                                     worldPoint1)
 355                 rvIntersections1.append(intersectionPoint1)
 356
 357                 intersectionSegment2Parameter = segPar20 + (intersectionPointData[1] / fltNrSamples2)
 358                 worldPoint2 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=intersectionSegment2Parameter)
 359                 intersectionPoint2 = BezierSegmentIntersectionPoint(self.segment2,
 360                                                                     intersectionSegment2Parameter,
 361                                                                     worldPoint2)
 362                 rvIntersections2.append(intersectionPoint2)
 363
 364         return [rvIntersections1, rvIntersections2]
 365
 366     def CalcIntersectionsFromViewDIR(self, nrSamples1, nrSamples2):
 367         global algoDIR
 368
 369         rvIntersections1 = []
 370         rvIntersections2 = []
 371
 372         fltNrSamples1 = float(nrSamples1)
 373         fltNrSamples2 = float(nrSamples2)
 374
 375         for iSample1 in range(nrSamples1):
 376             segPar10 = float(iSample1) / fltNrSamples1
 377             segPar11 = float(iSample1 + 1) / fltNrSamples1
 378             P0 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=segPar10)
 379             P1 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=segPar11)
 380
 381             for iSample2 in range(nrSamples2):
 382                 segPar20 = float(iSample2) / fltNrSamples2
 383                 segPar21 = float(iSample2 + 1) / fltNrSamples2
 384                 Q0 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=segPar20)
 385                 Q1 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=segPar21)
 386
 387                 intersectionPointData = mathematics.CalcIntersectionPointsLineSegmentsDIR(P0, P1, Q0, Q1, algoDIR)
 388                 if intersectionPointData is None:
 389                     continue
 390
 391                 intersectionSegment1Parameter = segPar10 + (intersectionPointData[0] / fltNrSamples1)
 392                 worldPoint1 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=intersectionSegment1Parameter)
 393                 intersectionPoint1 = BezierSegmentIntersectionPoint(self.segment1,
 394                                                                     intersectionSegment1Parameter,
 395                                                                     worldPoint1)
 396                 rvIntersections1.append(intersectionPoint1)
 397
 398                 intersectionSegment2Parameter = segPar20 + (intersectionPointData[1] / fltNrSamples2)
 399                 worldPoint2 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=intersectionSegment2Parameter)
 400                 intersectionPoint2 = BezierSegmentIntersectionPoint(self.segment2,
 401                                                                     intersectionSegment2Parameter,
 402                                                                     worldPoint2)
 403                 rvIntersections2.append(intersectionPoint2)
 404
 405         return [rvIntersections1, rvIntersections2]
 406
 407     def CalcIntersectionsFromViewPOV(self, nrSamples1, nrSamples2):
 408         global algoPOV
 409
 410         rvIntersections1 = []
 411         rvIntersections2 = []
 412
 413         fltNrSamples1 = float(nrSamples1)
 414         fltNrSamples2 = float(nrSamples2)
 415
 416         for iSample1 in range(nrSamples1):
 417             segPar10 = float(iSample1) / fltNrSamples1
 418             segPar11 = float(iSample1 + 1) / fltNrSamples1
 419             P0 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=segPar10)
 420             P1 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=segPar11)
 421
 422             for iSample2 in range(nrSamples2):
 423                 segPar20 = float(iSample2) / fltNrSamples2
 424                 segPar21 = float(iSample2 + 1) / fltNrSamples2
 425                 Q0 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=segPar20)
 426                 Q1 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=segPar21)
 427
 428                 intersectionPointData = mathematics.CalcIntersectionPointsLineSegmentsPOV(P0, P1, Q0, Q1, algoPOV)
 429                 if intersectionPointData is None:
 430                     continue
 431
 432                 intersectionSegment1Parameter = segPar10 + (intersectionPointData[0] / fltNrSamples1)
 433                 worldPoint1 = self.worldMatrix1 @ self.segment1.CalcPoint(parameter=intersectionSegment1Parameter)
 434                 intersectionPoint1 = BezierSegmentIntersectionPoint(self.segment1,
 435                                                                     intersectionSegment1Parameter,
 436                                                                     worldPoint1)
 437                 rvIntersections1.append(intersectionPoint1)
 438
 439                 intersectionSegment2Parameter = segPar20 + (intersectionPointData[1] / fltNrSamples2)
 440                 worldPoint2 = self.worldMatrix2 @ self.segment2.CalcPoint(parameter=intersectionSegment2Parameter)
 441                 intersectionPoint2 = BezierSegmentIntersectionPoint(self.segment2,
 442                                                                     intersectionSegment2Parameter,
 443                                                                     worldPoint2)
 444                 rvIntersections2.append(intersectionPoint2)
 445
 446         return [rvIntersections1, rvIntersections2]
 447
 448
 449 class BezierSplineIntersectionPoint:
 450     def __init__(self, spline, bezierSegmentIntersectionPoint):
 451         self.spline = spline
 452         self.bezierSegmentIntersectionPoint = bezierSegmentIntersectionPoint
 453
 454
 455 class BezierSplinesIntersector:
 456     def __init__(self, spline1, spline2, worldMatrix1, worldMatrix2):
 457         self.spline1 = spline1
 458         self.spline2 = spline2
 459         self.worldMatrix1 = worldMatrix1
 460         self.worldMatrix2 = worldMatrix2
 461
 462     def CalcIntersections(self):
 463         rvIntersections1 = []
 464         rvIntersections2 = []
 465
 466         try:
 467             nrSamplesPerSegment1 = int(self.spline1.resolution / self.spline1.nrSegments)
 468         except:
 469             nrSamplesPerSegment1 = 2
 470         if nrSamplesPerSegment1 < 2:
 471             nrSamplesPerSegment1 = 2
 472
 473         try:
 474             nrSamplesPerSegment2 = int(self.spline2.resolution / self.spline2.nrSegments)
 475         except:
 476             nrSamplesPerSegment2 = 2
 477         if nrSamplesPerSegment2 < 2:
 478             nrSamplesPerSegment2 = 2
 479
 480         for segment1 in self.spline1.segments:
 481             for segment2 in self.spline2.segments:
 482                 segmentsIntersector = BezierSegmentsIntersector(segment1, segment2,
 483                                                                 self.worldMatrix1, self.worldMatrix2)
 484                 segmentIntersections = segmentsIntersector.CalcIntersections(nrSamplesPerSegment1, nrSamplesPerSegment2)
 485                 if segmentIntersections is None:
 486                     continue
 487
 488                 segment1Intersections = segmentIntersections[0]
 489                 for segmentIntersection in segment1Intersections:
 490                     splineIntersection = BezierSplineIntersectionPoint(self.spline1, segmentIntersection)
 491                     rvIntersections1.append(splineIntersection)
 492
 493                 segment2Intersections = segmentIntersections[1]
 494                 for segmentIntersection in segment2Intersections:
 495                     splineIntersection = BezierSplineIntersectionPoint(self.spline2, segmentIntersection)
 496                     rvIntersections2.append(splineIntersection)
 497
 498         return [rvIntersections1, rvIntersections2]
 499
 500
 501 class CurvesIntersector:
 502     @staticmethod
 503     def FromSelection():
 504         selObjects = bpy.context.selected_objects
 505         if len(selObjects) != 2:
 506             raise Exception("len(selObjects) != 2")  # shouldn't be possible
 507
 508         blenderActiveCurve = bpy.context.active_object
 509         blenderOtherCurve = selObjects[0]
 510         if blenderActiveCurve == blenderOtherCurve:
 511             blenderOtherCurve = selObjects[1]
 512
 513         aCurve = curves.Curve(blenderActiveCurve)
 514         oCurve = curves.Curve(blenderOtherCurve)
 515
 516         return CurvesIntersector(aCurve, oCurve)
 517
 518     @staticmethod
 519     def ResetGlobals():
 520         global algoPOV
 521         algoPOV = None
 522         global algoDIR
 523         algoDIR = None
 524
 525     @staticmethod
 526     def InitGlobals():
 527         CurvesIntersector.ResetGlobals()
 528         global algoPOV
 529         global algoDIR
 530
 531         algo = bpy.context.scene.curvetools.IntersectCurvesAlgorithm
 532         if algo == 'From_View':
 533             regionView3D = util.GetFirstRegionView3D()
 534             if regionView3D is None:
 535                 print("### ERROR: regionView3D is None. Stopping.")
 536                 return
 537
 538             viewPerspective = regionView3D.view_perspective
 539             print("--", "viewPerspective:", viewPerspective)
 540
 541             if viewPerspective == 'ORTHO':
 542                 viewMatrix = regionView3D.view_matrix
 543                 print("--", "viewMatrix:")
 544                 print(viewMatrix)
 545
 546                 algoDIR = Vector((viewMatrix[2][0], viewMatrix[2][1], viewMatrix[2][2]))
 547                 print("--", "algoDIR:", algoDIR)
 548
 549             # ## TODO: doesn't work properly
 550             if viewPerspective == 'PERSP':
 551                 viewMatrix = regionView3D.view_matrix
 552                 print("--", "viewMatrix:")
 553                 print(viewMatrix)
 554
 555                 algoPOV = regionView3D.view_location.copy()
 556                 print("--", "algoPOV:", algoPOV)
 557
 558                 otherPOV = Vector((viewMatrix[0][3], viewMatrix[1][3], viewMatrix[2][3]))
 559                 print("--", "otherPOV:", otherPOV)
 560
 561                 localPOV = Vector((0, 0, 0))
 562                 globalPOV = viewMatrix * localPOV
 563                 print("--", "globalPOV:", globalPOV)
 564
 565                 perspMatrix = regionView3D.perspective_matrix
 566                 print("--", "perspMatrix:")
 567                 print(perspMatrix)
 568
 569                 globalPOVPersp = perspMatrix * localPOV
 570                 print("--", "globalPOVPersp:", globalPOVPersp)
 571
 572             if viewPerspective == 'CAMERA':
 573                 camera = bpy.context.scene.camera
 574                 if camera is None:
 575                     print("### ERROR: camera is None. Stopping.")
 576                     return
 577
 578                 print("--", "camera:", camera)
 579                 cameraData = camera.data
 580                 print("--", "cameraData.type:", cameraData.type)
 581
 582                 cameraMatrix = camera.matrix_world
 583                 print("--", "cameraMatrix:")
 584                 print(cameraMatrix)
 585
 586                 if cameraData.type == 'ORTHO':
 587                     cameraMatrix = camera.matrix_world
 588                     # algoDIR = Vector((cameraMatrix[2][0], cameraMatrix[2][1], cameraMatrix[2][2]))
 589                     algoDIR = Vector((- cameraMatrix[0][2], - cameraMatrix[1][2], - cameraMatrix[2][2]))
 590                     print("--", "algoDIR:", algoDIR)
 591
 592                 if cameraData.type == 'PERSP':
 593                     algoPOV = camera.location.copy()
 594                     print("--", "algoPOV:", algoPOV)
 595
 596     def __init__(self, activeCurve, otherCurve):
 597         self.activeCurve = activeCurve
 598         self.otherCurve = otherCurve
 599
 600         CurvesIntersector.InitGlobals()
 601
 602     def CalcIntersections(self):
 603         rvIntersections1 = []
 604         rvIntersections2 = []
 605
 606         worldMatrix1 = self.activeCurve.curve.matrix_world
 607         worldMatrix2 = self.otherCurve.curve.matrix_world
 608
 609         for spline1 in self.activeCurve.splines:
 610             for spline2 in self.otherCurve.splines:
 611                 splineIntersector = BezierSplinesIntersector(spline1, spline2, worldMatrix1, worldMatrix2)
 612                 splineIntersections = splineIntersector.CalcIntersections()
 613                 if splineIntersections is None:
 614                     continue
 615
 616                 spline1Intersections = splineIntersections[0]
 617                 for splineIntersection in spline1Intersections:
 618                     rvIntersections1.append(splineIntersection)
 619
 620                 spline2Intersections = splineIntersections[1]
 621                 for splineIntersection in spline2Intersections:
 622                     rvIntersections2.append(splineIntersection)
 623
 624         return [rvIntersections1, rvIntersections2]
 625
 626     def CalcAndApplyIntersections(self):
 627         mode = bpy.context.scene.curvetools.IntersectCurvesMode
 628
 629         if mode == 'Empty':
 630             return self.CalcAndApplyEmptyAtIntersections()
 631         if mode == 'Insert':
 632             return self.CalcAndApplyInsertAtIntersections()
 633         if mode == 'Split':
 634             return self.CalcAndApplySplitAtIntersections()
 635
 636         return [0, 0]
 637
 638     def CalcAndApplyEmptyAtIntersections(self):
 639         intersections = self.CalcIntersections()
 640         intersectionsActive = intersections[0]
 641         intersectionsOther = intersections[1]
 642
 643         nrActive = 0
 644         nrOther = 0
 645
 646         affect = bpy.context.scene.curvetools.IntersectCurvesAffect
 647
 648         if (affect == 'Both') or (affect == 'Active'):
 649             for splineIntersection in intersectionsActive:
 650                 iPoint = splineIntersection.bezierSegmentIntersectionPoint.intersectionPoint
 651                 bpy.ops.object.empty_add(type='PLAIN_AXES',
 652                                          align='WORLD',
 653                                          location=(iPoint.x, iPoint.y, iPoint.z), rotation=(0, 0, 0))
 654                 nrActive += 1
 655
 656         if (affect == 'Both') or (affect == 'Other'):
 657             for splineIntersection in intersectionsOther:
 658                 iPoint = splineIntersection.bezierSegmentIntersectionPoint.intersectionPoint
 659                 bpy.ops.object.empty_add(type='PLAIN_AXES',
 660                                          align='WORLD',
 661                                          location=(iPoint.x, iPoint.y, iPoint.z), rotation=(0, 0, 0))
 662                 nrOther += 1
 663
 664         return [nrActive, nrOther]
 665
 666     def CalcAndApplyInsertAtIntersections(self):
 667         nrActive = 0
 668         nrOther = 0
 669
 670         affect = bpy.context.scene.curvetools.IntersectCurvesAffect
 671         affectA = (affect == 'Both') or (affect == 'Active')
 672         affectO = (affect == 'Both') or (affect == 'Other')
 673
 674         for iSplineA in range(len(self.activeCurve.splines)):
 675             splineA = self.activeCurve.splines[iSplineA]
 676             nrSegmentsA = len(splineA.segments)
 677             resPerSegA = splineA.resolutionPerSegment
 678
 679             for iSplineO in range(len(self.otherCurve.splines)):
 680                 splineO = self.otherCurve.splines[iSplineO]
 681                 nrSegmentsO = len(splineO.segments)
 682                 resPerSegO = splineO.resolutionPerSegment
 683
 684                 iSegA = 0
 685                 while True:
 686                     segA = splineA.segments[iSegA]
 687
 688                     iSegO = 0
 689                     while True:
 690                         segO = splineO.segments[iSegO]
 691
 692                         segIntersector = BezierSegmentsIntersector(segA, segO,
 693                                                                    self.activeCurve.worldMatrix,
 694                                                                    self.otherCurve.worldMatrix)
 695                         segFirstIntersection = segIntersector.CalcFirstIntersection(resPerSegA, resPerSegO)
 696
 697                         if segFirstIntersection is not None:
 698                             intPointA = segFirstIntersection[0]
 699                             intPointO = segFirstIntersection[1]
 700                             # else does something weird if 1 of them is None..
 701                             if (intPointA is not None) and (intPointO is not None):
 702                                 if affectA:
 703                                     if intPointA is not None:
 704                                         splineA.InsertPoint(segA, intPointA.parameter)
 705
 706                                         nrActive += 1
 707                                         nrSegmentsA += 1
 708
 709                                 if affectO:
 710                                     if intPointO is not None:
 711                                         splineO.InsertPoint(segO, intPointO.parameter)
 712
 713                                         nrOther += 1
 714                                         nrSegmentsO += 1
 715
 716                         iSegO += 1
 717                         if not (iSegO < nrSegmentsO):
 718                             break
 719
 720                     iSegA += 1
 721                     if not (iSegA < nrSegmentsA):
 722                         break
 723
 724                 if affectO:
 725                     splineO.RefreshInScene()
 726
 727             if affectA:
 728                 splineA.RefreshInScene()
 729
 730         return [nrActive, nrOther]
 731
 732     def CalcAndApplySplitAtIntersections(self):
 733         nrActive = 0
 734         nrOther = 0
 735
 736         affect = bpy.context.scene.curvetools.IntersectCurvesAffect
 737         affectA = (affect == 'Both') or (affect == 'Active')
 738         affectO = (affect == 'Both') or (affect == 'Other')
 739
 740         nrSplinesA = len(self.activeCurve.splines)
 741         nrSplinesO = len(self.otherCurve.splines)
 742
 743         iSplineA = 0
 744         while True:
 745             splineA = self.activeCurve.splines[iSplineA]
 746             nrSegmentsA = len(splineA.segments)
 747             resPerSegA = splineA.resolutionPerSegment
 748
 749             iSplineO = 0
 750             while True:
 751                 splineO = self.otherCurve.splines[iSplineO]
 752                 nrSegmentsO = len(splineO.segments)
 753                 resPerSegO = splineO.resolutionPerSegment
 754
 755                 iSegA = 0
 756                 while True:
 757                     segA = splineA.segments[iSegA]
 758
 759                     iSegO = 0
 760                     while True:
 761                         segO = splineO.segments[iSegO]
 762
 763                         segIntersector = BezierSegmentsIntersector(segA, segO,
 764                                                                    self.activeCurve.worldMatrix,
 765                                                                    self.otherCurve.worldMatrix)
 766                         segFirstIntersection = segIntersector.CalcFirstIntersection(resPerSegA, resPerSegO)
 767
 768                         if segFirstIntersection is not None:
 769                             intPointA = segFirstIntersection[0]
 770                             intPointO = segFirstIntersection[1]
 771                             # else does something weird if 1 of them is None..
 772                             if (intPointA is not None) and (intPointO is not None):
 773                                 if affectA:
 774                                     if intPointA is not None:
 775                                         print("--", "splineA.Split():")
 776                                         newSplinesA = splineA.Split(segA, intPointA.parameter)
 777                                         if newSplinesA is not None:
 778                                             newResolutions = splineA.CalcDivideResolution(segA, intPointA.parameter)
 779                                             newSplinesA[0].resolution = newResolutions[0]
 780                                             newSplinesA[1].resolution = newResolutions[1]
 781
 782                                             splineA = newSplinesA[0]
 783                                             self.activeCurve.splines[iSplineA] = splineA
 784                                             self.activeCurve.splines.insert(iSplineA + 1, newSplinesA[1])
 785
 786                                             nrActive += 1
 787
 788                                 if affectO:
 789                                     if intPointO is not None:
 790                                         print("--", "splineO.Split():")
 791                                         newSplinesO = splineO.Split(segO, intPointO.parameter)
 792                                         if newSplinesO is not None:
 793                                             newResolutions = splineO.CalcDivideResolution(segO, intPointO.parameter)
 794                                             newSplinesO[0].resolution = newResolutions[0]
 795                                             newSplinesO[1].resolution = newResolutions[1]
 796
 797                                             splineO = newSplinesO[0]
 798                                             self.otherCurve.splines[iSplineO] = splineO
 799                                             self.otherCurve.splines.insert(iSplineO + 1, newSplinesO[1])
 800
 801                                             nrOther += 1
 802
 803                         nrSegmentsO = len(splineO.segments)
 804                         iSegO += 1
 805                         if not (iSegO < nrSegmentsO):
 806                             break
 807
 808                     nrSegmentsA = len(splineA.segments)
 809                     iSegA += 1
 810                     if not (iSegA < nrSegmentsA):
 811                         break
 812
 813                 nrSplinesO = len(self.otherCurve.splines)
 814                 iSplineO += 1
 815                 if not (iSplineO < nrSplinesO):
 816                     break
 817
 818             nrSplinesA = len(self.activeCurve.splines)
 819             iSplineA += 1
 820             if not (iSplineA < nrSplinesA):
 821                 break
 822
 823         if affectA:
 824             print("")
 825             print("--", "self.activeCurve.RebuildInScene():")
 826             self.activeCurve.RebuildInScene()
 827         if affectO:
 828             print("")
 829             print("--", "self.otherCurve.RebuildInScene():")
 830             self.otherCurve.RebuildInScene()
 831
 832         return [nrActive, nrOther]