[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[freetype2] anuj-distance-field f9b077b 18/95: [sdf] Added function to r
From: |
Anuj Verma |
Subject: |
[freetype2] anuj-distance-field f9b077b 18/95: [sdf] Added function to resolve corners. |
Date: |
Sun, 2 Aug 2020 01:10:27 -0400 (EDT) |
branch: anuj-distance-field
commit f9b077b4fedc372e62f713b2330dd9b576ac4d47
Author: Anuj Verma <anujv@iitbhilai.ac.in>
Commit: Anuj Verma <anujv@iitbhilai.ac.in>
[sdf] Added function to resolve corners.
---
[GSoC]ChangeLog | 12 ++++++
src/sdf/ftsdf.c | 115 ++++++++++++++++++++++++++++++++++++++++++++++++++++++--
2 files changed, 124 insertions(+), 3 deletions(-)
diff --git a/[GSoC]ChangeLog b/[GSoC]ChangeLog
index e094cec..e4f6e62 100644
--- a/[GSoC]ChangeLog
+++ b/[GSoC]ChangeLog
@@ -1,5 +1,17 @@
2020-06-27 Anuj Verma <anujv@iitbhilai.ac.in>
+ [sdf] Added function to resolve corners in case of
+ ambiguity.
+
+ * src/sdf/ftsdf.c (resolve_corner): Added function
+ to determine the correct sign in case there are
+ two sign for the same shortest distance (happens
+ around corners).
+
+ * src/sdf/ftsdf.c: Typo neartest_point -> nearest_point.
+
+2020-06-27 Anuj Verma <anujv@iitbhilai.ac.in>
+
[sdf] The module can now generate signed distance
fields for outline with only lines.
diff --git a/src/sdf/ftsdf.c b/src/sdf/ftsdf.c
index 912b543..2c96cbf 100644
--- a/src/sdf/ftsdf.c
+++ b/src/sdf/ftsdf.c
@@ -95,7 +95,7 @@
/* Nearest point the outline to a given point. */
/* [note]: This is not a *direction* vector, this */
/* simply a *point* vector on the grid. */
- FT_16D16_Vec neartest_point;
+ FT_16D16_Vec nearest_point;
/* The normalized direction of the curve at the */
/* above point. */
@@ -642,6 +642,112 @@
/**************************************************************************
*
* @Function:
+ * resolve_corner
+ *
+ * @Description:
+ * At some places on the grid two edges can give opposite direction
+ * this happens when the closes point is on of the endpoint, in that
+ * case we need to check the proper sign.
+ *
+ * This can be visualized by an example:
+ *
+ * x
+ *
+ * o
+ * ^ \
+ * / \
+ * / \
+ * (a) / \ (b)
+ * / \
+ * / \
+ * / v
+ *
+ * Suppose `x' is the point whose shortest distance from an arbitrary
+ * contour we want to find out. It is clear that `o' is the nearest
+ * point on the contour. Now to determine the sign we do a cross
+ * product of shortest distance vector and the edge direction. i.e.
+ *
+ * => sign = cross( ( x - o ), direction( a ) )
+ *
+ * From right hand thumb rule we can see that the sign will be positive
+ * and if check for `b'.
+ *
+ * => sign = cross( ( x - o ), direction( b ) )
+ *
+ * In this case the sign will be negative. So, to determine the correct
+ * sign we divide the plane in half and check in which plane the point
+ * lies.
+ *
+ * Divide:
+ *
+ * |
+ * x |
+ * |
+ * o
+ * ^|\
+ * / | \
+ * / | \
+ * (a) / | \ (b)
+ * / | \
+ * / \
+ * / v
+ *
+ * We can see that `x' lies in the plane of `a', so we take the sign
+ * determined by `a'. This can be easily done by calculating the
+ * orthogonality and taking the greater one.
+ *
+ * @Input:
+ * [TODO]
+ *
+ * @Return:
+ * [TODO]
+ */
+ static SDF_Signed_Distance
+ resolve_corner( SDF_Signed_Distance sdf1,
+ SDF_Signed_Distance sdf2,
+ FT_26D6_Vec point )
+ {
+ FT_16D16_Vec dist;
+
+ FT_16D16 ortho1;
+ FT_16D16 ortho2;
+
+ /* if they are not equal return the shorter */
+ if ( sdf1.squared_distance != sdf2.squared_distance )
+ return sdf1.squared_distance < sdf2.squared_distance ?
+ sdf1 : sdf2;
+
+ /* if there is not ambiguity in the sign return any */
+ if ( sdf1.sign == sdf2.sign )
+ return sdf1;
+
+ /* final check: Make sure nearest point is same. If not */
+ /* then return any, it is not the shortest distance. */
+ if ( sdf1.nearest_point.x != sdf2.nearest_point.x ||
+ sdf1.nearest_point.y != sdf2.nearest_point.y )
+ return sdf1;
+
+ /* calculate the distance vectors, will be same for both */
+ dist.x = sdf1.nearest_point.x - FT_26D6_16D16( point.x );
+ dist.y = sdf1.nearest_point.y - FT_26D6_16D16( point.y );
+
+ FT_Vector_NormLen( &dist );
+
+ /* use cross product to find orthogonality */
+ ortho1 = FT_MulFix( sdf1.direction.x, dist.y ) -
+ FT_MulFix( sdf1.direction.y, dist.x );
+ ortho1 = FT_ABS( ortho1 );
+
+ ortho2 = FT_MulFix( sdf2.direction.x, dist.y ) -
+ FT_MulFix( sdf2.direction.y, dist.x );
+ ortho2 = FT_ABS( ortho2 );
+
+ return ortho1 > ortho2 ? sdf1 : sdf2;
+ }
+
+ /**************************************************************************
+ *
+ * @Function:
* get_min_distance_line
*
* @Description:
@@ -762,10 +868,11 @@
cross = FT_MulFix( nearest_vector.x, line_segment.y ) -
FT_MulFix( nearest_vector.y, line_segment.x );
+ /* [OPTIMIZATION]: Pre-compute this direction. */
FT_Vector_NormLen( &line_segment );
/* assign the output */
- out->neartest_point = nearest_point;
+ out->nearest_point = nearest_point;
out->sign = cross < 0 ? 1 : -1;
out->squared_distance = FT_MulFix( nearest_vector.x, nearest_vector.x ) +
FT_MulFix( nearest_vector.y, nearest_vector.y );
@@ -862,10 +969,12 @@
(SDF_Edge*)edge_list.head->data,
point, ¤t_dist ) );
- /* [TODO]: *IMPORTANT* Add corner checking function. */
if ( current_dist.squared_distance >= 0 &&
current_dist.squared_distance < min_dist.squared_distance )
min_dist = current_dist;
+ else if ( current_dist.squared_distance ==
+ min_dist.squared_distance )
+ min_dist = resolve_corner( min_dist, current_dist, point );
edge_list.head = edge_list.head->next;
}
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [freetype2] anuj-distance-field f9b077b 18/95: [sdf] Added function to resolve corners.,
Anuj Verma <=