curve_tools/intersections.py

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