19e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com/* 29e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * Copyright 2012 Google Inc. 39e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * 49e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 59e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * found in the LICENSE file. 69e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com */ 79d5f99bc309a7d733e33a149bef295ae3c8b3ac1caryclark@google.com#include "QuadraticUtilities.h" 8c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com#include "CurveIntersection.h" 927accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com#include "Intersection_Tests.h" 10c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com#include "Parameterization_Test.h" 11639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com#include "TestUtilities.h" 12639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 13639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comconst Quadratic quadratics[] = { 14639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com {{0, 0}, {1, 0}, {1, 1}}, 15639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com}; 16639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 17639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comconst size_t quadratics_count = sizeof(quadratics) / sizeof(quadratics[0]); 18639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 19639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comint firstCubicCoincidenceTest = 0; 20639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 21639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comvoid CubicCoincidence_Test() { 22639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com // split large quadratic 23639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com // upscale quadratics to cubics 24639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com // compare original, parts, to see if the are coincident 25639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com for (size_t index = firstCubicCoincidenceTest; index < quadratics_count; ++index) { 26639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com const Quadratic& test = quadratics[index]; 27639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com QuadraticPair split; 28639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com chop_at(test, split, 0.5); 29639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com Quadratic midThird; 30639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com sub_divide(test, 1.0/3, 2.0/3, midThird); 31639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com Cubic whole, first, second, mid; 32639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com quad_to_cubic(test, whole); 33639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com quad_to_cubic(split.first(), first); 34639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com quad_to_cubic(split.second(), second); 35639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com quad_to_cubic(midThird, mid); 36639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (!implicit_matches(whole, first)) { 37aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkDebugf("%s-1 %d\n", __FUNCTION__, (int)index); 38639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 39639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (!implicit_matches(whole, second)) { 40aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkDebugf("%s-2 %d\n", __FUNCTION__, (int)index); 41639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 42639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (!implicit_matches(mid, first)) { 43aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkDebugf("%s-3 %d\n", __FUNCTION__, (int)index); 44639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 45639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (!implicit_matches(mid, second)) { 46aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkDebugf("%s-4 %d\n", __FUNCTION__, (int)index); 47639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 48639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (!implicit_matches(first, second)) { 49aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkDebugf("%s-5 %d\n", __FUNCTION__, (int)index); 50639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 51639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 52639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 5327accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 5427accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com// pairs of coincident cubics 5527accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com// The on curve points of each cubic should be on both parameterized cubics. 5627accef223a27fba437f5e825d99edbae20a045bcaryclark@google.comconst Cubic cubics[] = { 5727accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com { 58c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com { 1, -1}, 59c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com { 1.0/3, 1}, 60c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com {-1.0/3, -1}, 61c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com {-1, 1} 6227accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com }, 6327accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com { 64c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com {-1, 1}, 65c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com {-1.0/3, -1}, 66c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com { 1.0/3, 1}, 67c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com { 1, -1} 6827accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com }, 6927accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com { 7027accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com {0, 2}, 7127accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com {0, 1}, 7227accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com {1, 0}, 7327accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com {2, 0} 7427accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com }, { 7527accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com {2, 0}, 7627accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com {1, 0}, 7727accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com {0, 1}, 7827accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com {0, 2} 7927accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com }, 8027accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com { 8127accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com {315.74799999999999, 312.83999999999997}, 8227accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com {312.64400000000001, 318.13400000000001}, 8327accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com {305.83600000000001, 319.90899999999999}, 8427accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com {300.54199999999997, 316.80399999999997} 8527accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com }, { 8627accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com {317.12200000000001, 309.05000000000001}, 8727accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com {316.11200000000002, 315.10199999999998}, 8827accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com {310.38499999999999, 319.19}, 8927accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com {304.33199999999999, 318.17899999999997} 9027accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com } 9127accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com}; 9227accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 9327accef223a27fba437f5e825d99edbae20a045bcaryclark@google.comconst size_t cubics_count = sizeof(cubics) / sizeof(cubics[0]); 9427accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 9527accef223a27fba437f5e825d99edbae20a045bcaryclark@google.comint firstCubicParameterizationTest = 0; 9627accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 9727accef223a27fba437f5e825d99edbae20a045bcaryclark@google.comvoid CubicParameterization_Test() { 9827accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com for (size_t index = firstCubicParameterizationTest; index < cubics_count; ++index) { 9927accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com for (size_t inner = 0; inner < 4; inner += 3) { 10027accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com if (!point_on_parameterized_curve(cubics[index], cubics[index][inner])) { 101aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkDebugf("%s [%zu,%zu] 1 parameterization failed\n", 10227accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com __FUNCTION__, index, inner); 10327accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com } 10427accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com if (!point_on_parameterized_curve(cubics[index], cubics[index ^ 1][inner])) { 105aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkDebugf("%s [%zu,%zu] 2 parameterization failed\n", 10627accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com __FUNCTION__, index, inner); 10727accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com } 10827accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com } 109c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (!implicit_matches(cubics[index], cubics[index ^ 1])) { 110aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkDebugf("%s %d\n", __FUNCTION__, (int)index); 111c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 11227accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com } 11327accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com} 114