Improve feature mapping The new algorithm computes all distances between each pair of feature from the source polygon and target polygon and tries to add them in turn from smalles to highest if: * The 2 features are not mapped yet. * We are not introducing too many crossings in the mapping. Test: Added Relnote: "Improved the feature maping algorithm, so more morphs should look more natural" Change-Id: I83287a0bd2a470f8a38b67c77bd19a957c054046
diff --git a/graphics/graphics-shapes/src/androidInstrumentedTest/kotlin/androidx/graphics/shapes/FeatureMappingTest.kt b/graphics/graphics-shapes/src/androidInstrumentedTest/kotlin/androidx/graphics/shapes/FeatureMappingTest.kt new file mode 100644 index 0000000..6fcfd49 --- /dev/null +++ b/graphics/graphics-shapes/src/androidInstrumentedTest/kotlin/androidx/graphics/shapes/FeatureMappingTest.kt
@@ -0,0 +1,128 @@ +/* + * Copyright 2024 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package androidx.graphics.shapes + +import org.junit.Test + +class FeatureMappingTest { + private val triangleWithRoundings = RoundedPolygon(3, rounding = CornerRounding(0.2f)) + private val triangle = RoundedPolygon(3) + private val square = RoundedPolygon(4) + private val squareRotated = RoundedPolygon(4).transformed(pointRotator(45f)) + + @Test + fun featureMappingTriangles() = + verifyMapping(triangleWithRoundings, triangle) { distances -> + distances.forEach { assert(it < 0.1f) } + } + + @Test + fun featureMappingTriangleToSquare() = + verifyMapping(triangle, square) { distances -> + // We have one exact match (both have points at 0 degrees), and 2 close ones + assert(distances.size == 3) + assertEqualish(distances[0], distances[1]) + assert(distances[0] < 0.3f) + assert(distances[2] < 1e-6f) + } + + @Test + fun featureMappingSquareToTriangle() = + verifyMapping(square, triangle) { distances -> + // We have one exact match (both have points at 0 degrees), and 2 close ones + assert(distances.size == 3) + + assertEqualish(distances[0], distances[1]) + assert(distances[0] < 0.3f) + assert(distances[2] < 1e-6f) + } + + @Test + fun featureMappingSquareRotatedToTriangle() = + verifyMapping(squareRotated, triangle) { distances -> + // We have a very bad mapping (the triangle vertex just in the middle of one of the + // square's sides) and 2 decent ones. + assert(distances.size == 3) + + assert(distances[0] > 0.5f) + assertEqualish(distances[1], distances[2]) + assert(distances[2] < 0.1f) + } + + @Test + fun featureMappingDoesntCrash() { + // Verify that complicated shapes can me matched (this used to crash before). + val checkmark = + RoundedPolygon( + floatArrayOf( + 400f, + -304f, + 240f, + -464f, + 296f, + -520f, + 400f, + -416f, + 664f, + -680f, + 720f, + -624f, + 400f, + -304f, + ) + ) + .normalized() + val verySunny = + RoundedPolygon.star( + numVerticesPerRadius = 8, + innerRadius = .65f, + rounding = CornerRounding(radius = .15f) + ) + .normalized() + verifyMapping(checkmark, verySunny) { + // Most vertices on the checkmark map to a feature in the second shape. + assert(it.size >= 6) + + // And they are close enough + assert(it[0] < 0.15f) + } + } + + private fun verifyMapping( + p1: RoundedPolygon, + p2: RoundedPolygon, + validator: (List<Float>) -> Unit + ) { + val f1 = MeasuredPolygon.measurePolygon(LengthMeasurer(), p1).features + val f2 = MeasuredPolygon.measurePolygon(LengthMeasurer(), p2).features + + // Maps progress in p1 to progress in p2 + val map = doMapping(f1, f2) + + // See which features where actually mapped and the distance between their representative + // points + val distances = buildList { + map.forEach { (progress1, progress2) -> + val feature1 = f1.find { it.progress == progress1 }!! + val feature2 = f2.find { it.progress == progress2 }!! + add(featureDistSquared(feature1.feature, feature2.feature)) + } + } + + validator(distances.sortedDescending()) + } +}
diff --git a/graphics/graphics-shapes/src/androidInstrumentedTest/kotlin/androidx/graphics/shapes/FloatMappingTest.kt b/graphics/graphics-shapes/src/androidInstrumentedTest/kotlin/androidx/graphics/shapes/FloatMappingTest.kt index 015c070..c409891 100644 --- a/graphics/graphics-shapes/src/androidInstrumentedTest/kotlin/androidx/graphics/shapes/FloatMappingTest.kt +++ b/graphics/graphics-shapes/src/androidInstrumentedTest/kotlin/androidx/graphics/shapes/FloatMappingTest.kt
@@ -17,6 +17,7 @@ package androidx.graphics.shapes import androidx.test.filters.SmallTest +import org.junit.Assert.assertThrows import org.junit.Test @SmallTest @@ -60,7 +61,7 @@ } @Test - fun multiplePointTes() = + fun multiplePointTest() = validateMapping(mapper = DoubleMapper(0.4f to 0.2f, 0.5f to 0.22f, 0f to 0.8f)) { x -> if (x < 0.4f) { (0.8f + x) % 1f @@ -72,6 +73,20 @@ } } + @Test + fun targetDoubleWrapThrows() { + assertThrows(IllegalArgumentException::class.java) { + DoubleMapper(0.0f to 0.0f, 0.3f to 0.6f, 0.6f to 0.3f, 0.9f to 0.9f) + } + } + + @Test + fun sourceDoubleWrapThrows() { + assertThrows(IllegalArgumentException::class.java) { + DoubleMapper(0.0f to 0.0f, 0.6f to 0.3f, 0.3f to 0.6f, 0.9f to 0.9f) + } + } + private fun validateMapping(mapper: DoubleMapper, expectedFunction: (Float) -> Float) { (0..9999).forEach { i -> val source = i / 10000f
diff --git a/graphics/graphics-shapes/src/androidInstrumentedTest/kotlin/androidx/graphics/shapes/TestUtils.kt b/graphics/graphics-shapes/src/androidInstrumentedTest/kotlin/androidx/graphics/shapes/TestUtils.kt index c755b50..0047478 100644 --- a/graphics/graphics-shapes/src/androidInstrumentedTest/kotlin/androidx/graphics/shapes/TestUtils.kt +++ b/graphics/graphics-shapes/src/androidInstrumentedTest/kotlin/androidx/graphics/shapes/TestUtils.kt
@@ -17,6 +17,7 @@ package androidx.graphics.shapes import android.graphics.Bitmap +import android.graphics.Matrix import androidx.core.graphics.get import kotlin.math.abs import org.junit.Assert.assertEquals @@ -119,6 +120,15 @@ internal fun identityTransform() = PointTransformer { x, y -> TransformResult(x, y) } +internal fun pointRotator(angle: Float): PointTransformer { + val matrix = Matrix().apply { setRotate(angle) } + return PointTransformer { x, y -> + val point = floatArrayOf(x, y) + matrix.mapPoints(point) + TransformResult(point[0], point[1]) + } +} + internal fun scaleTransform(sx: Float, sy: Float) = PointTransformer { x, y -> TransformResult(x * sx, y * sy) }
diff --git a/graphics/graphics-shapes/src/commonMain/kotlin/androidx/graphics/shapes/FeatureMapping.kt b/graphics/graphics-shapes/src/commonMain/kotlin/androidx/graphics/shapes/FeatureMapping.kt index 3ffa13f..d68b200 100644 --- a/graphics/graphics-shapes/src/commonMain/kotlin/androidx/graphics/shapes/FeatureMapping.kt +++ b/graphics/graphics-shapes/src/commonMain/kotlin/androidx/graphics/shapes/FeatureMapping.kt
@@ -46,24 +46,10 @@ } } - val (m1, m2) = - if (filteredFeatures1.size > filteredFeatures2.size) { - doMapping(filteredFeatures2, filteredFeatures1) to filteredFeatures2 - } else { - filteredFeatures1 to doMapping(filteredFeatures1, filteredFeatures2) - } + val featureProgressMapping = doMapping(filteredFeatures1, filteredFeatures2) - // Performance: Equivalent to `m1.zip(m2).map { (f1, f2) -> f1.progress to f2.progress }` and - // done to zip and create a Pairs list without creating unnecessary Iterators. - val mm = buildList { - for (i in m1.indices) { - if (i == m2.size) break - add(m1[i].progress to m2[i].progress) - } - } - - debugLog(LOG_TAG) { mm.joinToString { "${it.first} -> ${it.second}" } } - return DoubleMapper(*mm.toTypedArray()).also { dm -> + debugLog(LOG_TAG) { featureProgressMapping.joinToString { "${it.first} -> ${it.second}" } } + return DoubleMapper(*featureProgressMapping.toTypedArray()).also { dm -> debugLog(LOG_TAG) { val N = 10 "Map: " + @@ -76,6 +62,103 @@ } } +internal data class DistanceVertex( + val distance: Float, + val f1: ProgressableFeature, + val f2: ProgressableFeature +) + +/** + * Returns a mapping of the features between features1 and features2. The return is a list of pairs + * in which the first element is the progress of a feature in features1 and the second element is + * the progress of the feature in features2 that we mapped it to. The list is sorted by the first + * element. To do this: + * 1) Compute the distance for all pairs of features in (features1 x features2), + * 2) Sort ascending by by such distance + * 3) Try to add them, from smallest distance to biggest, ensuring that: a) The features we are + * mapping haven't been mapped yet. b) We are not adding a crossing in the mapping. Since the + * mapping is sorted by the first element of each pair, this means that the second elements of + * each pair are monotonically increasing, except maybe one time (Counting all pair of + * consecutive elements, and the last element to first element). + */ +internal fun doMapping( + features1: List<ProgressableFeature>, + features2: List<ProgressableFeature> +): List<Pair<Float, Float>> { + debugLog("LOG_TAG") { "Shape1 progresses: " + features1.map { it.progress }.joinToString() } + debugLog("LOG_TAG") { "Shape2 progresses: " + features2.map { it.progress }.joinToString() } + val distanceVertexList = + buildList { + for (f1 in features1) { + for (f2 in features2) { + val d = featureDistSquared(f1.feature, f2.feature) + if (d != Float.MAX_VALUE) add(DistanceVertex(d, f1, f2)) + } + } + } + .sortedBy { it.distance } + + // Special cases. + if (distanceVertexList.isEmpty()) return IdentityMapping + if (distanceVertexList.size == 1) + return distanceVertexList.first().let { + val f1 = it.f1.progress + val f2 = it.f2.progress + listOf(f1 to f2, (f1 + 0.5f) % 1f to (f2 + 0.5f) % 1f) + } + + return MappingHelper().apply { distanceVertexList.forEach { addMapping(it.f1, it.f2) } }.mapping +} + +private val IdentityMapping = listOf(0f to 0f, 0.5f to 0.5f) + +private class MappingHelper() { + // List of mappings from progress in the start shape to progress in the end shape. + // We keep this list sorted by the first element. + val mapping = mutableListOf<Pair<Float, Float>>() + + // Which features in the start shape have we used and which in the end shape. + private val usedF1 = mutableSetOf<ProgressableFeature>() + private val usedF2 = mutableSetOf<ProgressableFeature>() + + fun addMapping(f1: ProgressableFeature, f2: ProgressableFeature) { + // We don't want to map the same feature twice. + if (f1 in usedF1 || f2 in usedF2) return + + // Ret is sorted, find where we need to insert this new mapping. + val index = mapping.binarySearchBy(f1.progress) { it.first } + require(index < 0) { "There can't be two features with the same progress" } + + val insertionIndex = -index - 1 + val n = mapping.size + + // We can always add the first 1 element + if (n >= 1) { + val (before1, before2) = mapping[(insertionIndex + n - 1) % n] + val (after1, after2) = mapping[insertionIndex % n] + + // We don't want features that are way too close to each other, that will make the + // DoubleMapper unstable + if ( + progressDistance(f1.progress, before1) < DistanceEpsilon || + progressDistance(f1.progress, after1) < DistanceEpsilon || + progressDistance(f2.progress, before2) < DistanceEpsilon || + progressDistance(f2.progress, after2) < DistanceEpsilon + ) { + return + } + + // When we have 2 or more elements, we need to ensure we are not adding extra crossings. + if (n > 1 && !progressInRange(f2.progress, before2, after2)) return + } + + // All good, we can add the mapping. + mapping.add(insertionIndex, f1.progress to f2.progress) + usedF1.add(f1) + usedF2.add(f2) + } +} + /** * Returns distance along overall shape between two Features on the two different shapes. This * information is used to determine how to map features (and the curves that make up those @@ -90,41 +173,13 @@ debugLog(LOG_TAG) { "*** Feature distance ∞ for convex-vs-concave corners" } return Float.MAX_VALUE } - val c1x = (f1.cubics.first().anchor0X + f1.cubics.last().anchor1X) / 2f - val c1y = (f1.cubics.first().anchor0Y + f1.cubics.last().anchor1Y) / 2f - val c2x = (f2.cubics.first().anchor0X + f2.cubics.last().anchor1X) / 2f - val c2y = (f2.cubics.first().anchor0Y + f2.cubics.last().anchor1Y) / 2f - val dx = c1x - c2x - val dy = c1y - c2y - return dx * dx + dy * dy + return (featureRepresentativePoint(f1) - featureRepresentativePoint(f2)).getDistanceSquared() } -/** - * Returns a mapping of the features in f2 that best map to the features in f1. The result will be a - * list of features in f2 that is the size of f1. This is done to figure out what the best features - * are in f2 that map to the existing features in f1. For example, if f1 has 3 features and f2 has - * 4, we want to know what the 3 features are in f2 that map to the features in f1 (then we will - * create a placeholder feature in the smaller shape for the morph). - */ -internal fun doMapping(f1: MeasuredFeatures, f2: MeasuredFeatures): MeasuredFeatures { - // Pick the first mapping in a greedy way. - val ix = f2.indices.minBy { featureDistSquared(f1[0].feature, f2[it].feature) } - - val m = f1.size - val n = f2.size - - val ret = mutableListOf(f2[ix]) - var lastPicked = ix - for (i in 1 until m) { - // Check the indices we can pick, which one is better. - // Leave enough items in f2 to pick matches for the items left in f1. - val last = (ix - (m - i)).let { if (it > lastPicked) it else it + n } - val best = - (lastPicked + 1..last).minBy { featureDistSquared(f1[i].feature, f2[it % n].feature) } - ret.add(f2[best % n]) - lastPicked = best - } - return ret +internal fun featureRepresentativePoint(feature: Feature): Point { + val x = (feature.cubics.first().anchor0X + feature.cubics.last().anchor1X) / 2f + val y = (feature.cubics.first().anchor0Y + feature.cubics.last().anchor1Y) / 2f + return Point(x, y) } private val LOG_TAG = "FeatureMapping"
diff --git a/graphics/graphics-shapes/src/commonMain/kotlin/androidx/graphics/shapes/FloatMapping.kt b/graphics/graphics-shapes/src/commonMain/kotlin/androidx/graphics/shapes/FloatMapping.kt index b79a12a..8be02c5 100644 --- a/graphics/graphics-shapes/src/commonMain/kotlin/androidx/graphics/shapes/FloatMapping.kt +++ b/graphics/graphics-shapes/src/commonMain/kotlin/androidx/graphics/shapes/FloatMapping.kt
@@ -19,6 +19,8 @@ import androidx.collection.FloatList import androidx.collection.MutableFloatList import kotlin.jvm.JvmField +import kotlin.math.abs +import kotlin.math.min /** * Checks if the given progress is in the given progress range, since progress is in the [0..1) @@ -68,6 +70,8 @@ sourceValues.add(mappings[i].first) targetValues.add(mappings[i].second) } + // Both source values and target values should be monotonically increasing, with the + // exception of maybe one time (since progress wraps around). validateProgress(sourceValues) validateProgress(targetValues) } @@ -88,11 +92,34 @@ } } -// TODO(performance): Make changes to satisfy the lint warnings for unnecessary iterators creation. +// Verify that a list of progress values are all in the range [0.0, 1.0) and is monotonically +// increasing, with the exception of maybe one time in which the progress wraps around, this check +// needs to include all pairs of consecutive elements in the list plus the last to first element +// pair. +// For example: (0.0, 0.3, 0.6) is a valid list, so are (0.3, 0.6, 0.0) and (0.6, 0.3, 0.0). +// On the other hand, something like (0.5, 0.0, 0.7) is not (since it goes down twice, from 0.5 to +// 0.0 and then from to 0.7 to 0.5). internal fun validateProgress(p: FloatList) { - require(p.fold(true) { res, curr -> res && curr in 0f..1f }) { - "FloatMapping - Progress outside of range: " + p.joinToString() + var prev = p.last() + var wraps = 0 + for (i in 0 until p.size) { + val curr = p[i] + require(curr >= 0f && curr < 1f) { + "FloatMapping - Progress outside of range: " + p.joinToString() + } + require(progressDistance(curr, prev) > DistanceEpsilon) { + "FloatMapping - Progress repeats a value: " + p.joinToString() + } + if (curr < prev) { + wraps++ + require(wraps <= 1) { + "FloatMapping - Progress wraps more than once: " + p.joinToString() + } + } + prev = curr } - val wraps = (1 until p.size).count { p[it] < p[it - 1] } - require(wraps <= 1) { "FloatMapping - Progress wraps more than once: " + p.joinToString() } } + +// Distance between two progress values. +// Since progress wraps around, we consider a difference of 0.99 as a distance of 0.01 +internal fun progressDistance(p1: Float, p2: Float) = abs(p1 - p2).let { min(it, 1f - it) }