| 1865 | namespace |
| 1866 | { |
| 1867 | int FindSplineIntersections |
| 1868 | ( |
| 1869 | int is0, int numSplines0, const Spline2 splines0[], |
| 1870 | int is1, int numSplines1, const Spline2 splines1[], |
| 1871 | int maxResults, |
| 1872 | int resultsI[][2], |
| 1873 | float resultsT[][2], |
| 1874 | float tolerance |
| 1875 | ) |
| 1876 | { |
| 1877 | if (maxResults <= 0 || numSplines0 == 0 || numSplines1 == 0) |
| 1878 | return 0; |
| 1879 | |
| 1880 | int count = 0; |
| 1881 | |
| 1882 | // once the lists are small enough, brute-force the remainder, as recalculating the bounds is not free |
| 1883 | if (numSplines0 >= 4 || numSplines1 >= 4) |
| 1884 | { |
| 1885 | // Terminate if the lists don't overlap |
| 1886 | Bounds2 b0 = FastBounds(splines0[0]); |
| 1887 | Bounds2 b1 = FastBounds(splines1[0]); |
| 1888 | |
| 1889 | for (int i = 1; i < numSplines0; i++) |
| 1890 | Add(b0, FastBounds(splines0[i])); |
| 1891 | for (int i = 1; i < numSplines1; i++) |
| 1892 | Add(b1, FastBounds(splines1[i])); |
| 1893 | |
| 1894 | if (!Intersects(b0, b1)) |
| 1895 | return 0; |
| 1896 | |
| 1897 | // Divide each spline list into two, and recurse |
| 1898 | int n00 = numSplines0 / 2; |
| 1899 | int n01 = numSplines0 - n00; |
| 1900 | int n10 = numSplines1 / 2; |
| 1901 | int n11 = numSplines1 - n10; |
| 1902 | |
| 1903 | count += FindSplineIntersections(is0 + 0, n00, splines0 + 0, is1 + 0, n10, splines1 + 0, maxResults - count, resultsI + count, resultsT + count, tolerance); |
| 1904 | count += FindSplineIntersections(is0 + 0, n00, splines0 + 0, is1 + n10, n11, splines1 + n10, maxResults - count, resultsI + count, resultsT + count, tolerance); |
| 1905 | count += FindSplineIntersections(is0 + n00, n01, splines0 + n00, is1 + 0, n10, splines1 + 0, maxResults - count, resultsI + count, resultsT + count, tolerance); |
| 1906 | count += FindSplineIntersections(is0 + n00, n01, splines0 + n00, is1 + n10, n11, splines1 + n10, maxResults - count, resultsI + count, resultsT + count, tolerance); |
| 1907 | |
| 1908 | return count; |
| 1909 | } |
| 1910 | |
| 1911 | SubSplineT2 st0, st1; |
| 1912 | |
| 1913 | st0.mT0 = 0.0f; |
| 1914 | st0.mT1 = 1.0f; |
| 1915 | st1.mT0 = 0.0f; |
| 1916 | st1.mT1 = 1.0f; |
| 1917 | |
| 1918 | for (int i0 = 0; i0 < numSplines0; i0++) |
| 1919 | for (int i1 = 0; i1 < numSplines1; i1++) |
| 1920 | { |
| 1921 | st0.mSpline = splines0[i0]; |
| 1922 | st1.mSpline = splines1[i1]; |
| 1923 | |
| 1924 | int numIntersections = FindSubSplineIntersections(st0, st1, 0, maxResults - count, resultsT + count, tolerance); |