4
$\begingroup$

I'm unable to find even a starting point to this problem, so any guidance of any sort would be awesome. First a short paragraph on fonts.

Fonts

From what I know, fonts in general are described as (close oriented) curves. Multiple curves describe the area that should be filled, as shown here :

Example of curves describing a font

Here we have 2 curves for A, but for example there could be 3 for a B. Note that in my example, the width of the font is constant but that's not always the case (for example a in the next image)

My goal

I'm trying to go from this shape, which is basically a line with thickness, to really just a line. A sort of collapse of the width of the font to a wire text as below :

The process

On the left is the process I want to achieve. On the right is a comparison before/after.

This process looks to me complex. For example, fonts are described as closed curves which wouldn't be guaranteed in this wire-like state. Think of an i, where the bottom part would be just a line. To show you just one case where the process can become complex, let's take a look at the top of an A :

Edge-case of top part of "A" letter

The original A (orange) have unrelated topologies, between the outter curve (2 points) and the inner curve (1 point). The process should probably create 2 points. I feel like there are a lot of edge-cases like that, for example how do you collapse a . (initially a circle/disc) : to a smaller circle, or to a point, ...

My conditions

  1. To be somewhat procedural
  2. So, no manual modelling
  3. To work for this kind of fonts (basically, sans-serif with solid borders :

Type of fonts expected

I would consider as acceptable answer if the solution only work for constant-width fonts (like most of the examples above). It would already be a great starting point.

  1. To work for letters and numbers, if possible with usual characters too (,.- ...).

My question

Do you have any idea how to approach that problem ? Is there an easy way to achieve that ? Otherwise, would you know the name of a method or algorithm ? Or do you think it's impossible to implement a general solution, under these conditions ?

Any help would be greatly appreciated. Thank you for reading me !

$\endgroup$
13
  • 1
    $\begingroup$ There are may different fonts and many different characters. I don't think there is a practical general solution☻Character "A" does not represent the actual problem, which is way more complex. $\endgroup$ Mar 31 at 2:29
  • 3
    $\begingroup$ I suspect this to be a way more complex problem than it seems at first. It might be easier to do it manually. What do you need this for? Maybe it's possible to solve the original problem easier. $\endgroup$ Mar 31 at 4:22
  • 2
    $\begingroup$ @Lutzi This is the best I could come up with in the hope of getting a general solution: blend-exchange.com/b/xYvorWeE $\endgroup$
    – ugorek
    Mar 31 at 13:27
  • 1
    $\begingroup$ Look at this vectorization of thick lines. $\endgroup$
    – Leander
    Apr 2 at 17:28
  • 1
    $\begingroup$ @ugorek Why my blender is crashing, when I try to open your file? $\endgroup$
    – p6majo
    Apr 2 at 20:42

2 Answers 2

6
+150
$\begingroup$

(Using Blender 3.6.8)

Searching to characterize curves connecting outlining curves to backbones, it was observed that backbones could be defined as intersection of surfaces extruded from outlining curves. A new approach was derived, not relying in particular on thresholds. It is reported in an other post. The present research is postponed.

Research Progress Report

The results reported are not satisfying, but show some perspective of improvements.

Results

This figure illustrates, with black dots, preliminary control points from which curves could be defined, for characters of varying complexity.

Approach

The detection of the backbone of a character relies on the distance to the curves defining its outline, and on assumptions about its shape. Two grids are used. The distance and its gradient are computed on a fine grid, to identify points along ridges. The statistical local organisation of subsets of ridge points is analysed using a coarse grid, to identify pieces of curve.

Information from the fine grid

Fine grid results

This figure illustrates the distance to outlining curves. This field is normalized between 0 and 1 per character. White is below 5% ; Green is below 25% ; Blue is below 50% ; Magenta is below 75% ; Yellow is below 95% ; Red is above.
It is to notice that useful control points (black dots) are above 50%, and also that the maximal distance is obviously varying along a ridge for not constant-width characters (like B and é). But even for constant-width characters (like A and X), local maxima are located at crossings.

Information from the coarse grid

Coarse grid information

This figure illustrates basic information inferred by analysing the ridge points (in light grey) clustered per face of the coarse grid. The preliminary control points (in black) are computed as the barycentre of such clusters. Green faces are empty of ridge points. Blue faces are undersampled and the ridge points of these should be transferred to a neighbouring face ; otherwise, statistical analysis is biased. Dark grey faces are yet to analyse to identify strait or curved segments, crossings, extraneous segments connected to outlining curves, isolated points, ...

GeometryNodes modifier overview

GN Main graph

1. The coarse grid dimension is hardcoded to 8x8 faces. Each face is then divided into 16x16 smaller faces to define the fine grid.
2. The Target group node is providing the surface from which the distance is computed.
3. The Distance group node is building the fine grid, it is tagging independent parts for multi-parts characters, and it is computing the normalized distance.
4. The Gradient Edge group node is computing the distance gradient components along X and Y per edge.
5. The Gradient Vertex group node is assembling the distance gradient components per vertex. It is also tagging points where the slope goes from increasing to decreasing. Such points are candidates as ridge points.
6. The Ridge group node is filtering candidate points by limiting the distance gradient slope according to a user-defined Threshold, and by discarding points with distance below 1% (hardcoded). As the distance gradient is discontinuous along ridges, it is expected that its magnitude is below 1. So the Threshold is set to 0.98 by default.
7. The Filter group node is building the coarse grid and it is assigning the ridge points to coarse faces. Then subgroup nodes are used to apply local analyses, like detecting empty or undersampled faces.

Gallery

(NB :The following pictures are illustrating intermediate results, without intent to be fully descriptive.)

Extruded surface to compute the distance and to tag independent parts: GN Target

Fine grid with Z equal to the distance. "Outside" points are set with negative distance: GN Distance

Tagging of "inside" fine grid points with independent parts ID taking advantage of the Mesh Island node: GN Parts

Gradient of the distance evaluated at vertices, from the gradient computed per edge: GN Gradient

Candidates as ridge points where the gradient sign is changing at least in one direction, X or Y: GN Overturn

Filtering of candidates to tag ridge points: GN tag ridge

Duplication of the coarse grid, one copy per independent part: GN Filter

Perspectives

  • Join undersampled faces.
  • Use simple linear regression to identify strait segments.
  • Use simple linear regression to identify extraneous segments connected to outlining curves.
  • Use islands detection to identify isolated points.
  • Identify curved segments from remaining faces.
  • Identify junctions from remaining faces.
  • Read from someone using Blender version above 3.6.8 with more advanced nodes, like Points to Curves node.

Resources

$\endgroup$
1
  • $\begingroup$ As this work is still under progress, I do not write detailed description of the GN sub-graphs as these might change to support new features. Some are already version number 3 after complete redesign... $\endgroup$ Apr 6 at 23:15
1
$\begingroup$

(Using Blender 3.6.8)

Reseach Progress Report

The reported approach, yet incomplete, shows promising results.

Results

This figure illustrates identified "backbone" curves for characters of varying complexity, using a Curve to Mesh node with a Curve Circle profile.

Approach

The detection of the backbone of a character relies on the distance to the curves defining its outline. It is observed that this distance grows linearly along the local line perpendicular to the outlining curve for each point along this curve. Rotating such a line built in the (X,Y) plane along the local tangent to the curve by 45 degrees defines the steepest path toward the ridge where lies the searched backbone.
Edges sampled along the outlining curve are extruded "at 45 degrees" to build faces to intersect. The same way, points are sampled along the outlining curve and a Raycast node is used to compute the intersection along the ray rotated "at 45 degrees". Because these sampled points are connected in a Mesh Line, the resulting intersection defines a list of connected edges, that are afterwards converted to a curve.

Approach

This figure illustrates the process for the "O" character. The original curves are divided in four "rims" which are extruded inwards "at 45 degrees". Adjacent faces of same colour belong to the same rim. Each rim is also sampled with points that are shifted along rays "rotated at 45 degrees" until intersecting opposite faces. Intersections are identified with cubes. To avoid self-intersection, the configuration is duplicated along the Z axis, with the faces associated to one single rim deleted per copy.

GeometryNodes modifier overview

(NB :The following pictures are illustrating intermediate results, without intent to be fully descriptive.)

Main graph

GN Main

1. The Rim group node is splitting the original curves in "rims" connecting two adjacent control points.
2. The Extrude Rim group node is building the faces to intersect from the previously identified rims.
3. The Corner group node is storing data about each control point, including its two adjacent rims and it is computing the bisector between.
4. The Extrude Corner group node is building the faces to intersect for concave corners.
5. The Intersect group node is computing the intersection from rays emitted by sampling the rims, with the faces built previously.
6. One list of connected edges per rim is produced. No filtering is applied at this time.

Identifying the rims

GN Rim

1. Rim data are stored in a "table" (as a Grid) with two columns (along X axis), one per end, and with as many rows (along Y axis) as pairs of adjacent control points. It is assumed that curves are cyclic.
2. In this table, only edges connecting ends (i.e. aligned with X axis) are kept. So data stored per rim (i.e. per edge) are safely transferred to ends (i.e. points).
3. The Rim Left and Rim Right group nodes are retrieving data from the original curve control points to define both ends. In particular, position, tangent vector and factor are stored.
4. Strait rims are detected by checking aligned tangents and connecting segment. These are tagged with type Vector (i.e. 2), following the handle types nomenclature.

Building from the rims the faces to intersect

GN Rim extruded

1. The Rake group node is uniformly sampling each rim. Samples are stored as a Mesh Line to preserve connectivity between adjacent points. Linear interpolation in (X,Y) is used for strait rims. For curved rims, the factor is interpolated, then a Sample Curve node is used to recover the local position and tangent.
2. The achieved edges are extruded along the Z axis. Then the Top vertices are moved by rotation, around the local tangent, of the vector connecting them to the curve. This is how the "extrusion at 45 degrees" is achieved.
3. It is to notice on the picture above that "gaps" are remaining between extruded patches when the angle between adjacent rim tangents is larger than 180 degrees (e.g. between red and green faces at mid-height junction).

Computing the bisectors

GN Corner

1. Corner data are stored in a Point Cloud, one point per original curve control point.
2. From the left and right handles, the bisector at each corner is computed.
3. It is to notice that tangents are usually aligned at the junction with curved rims, leading to a singular case for the bisector algebra. For this special case, the bisector is recovered by rotation of the unitary vector along Z axis around the local tangent, by 45 degrees.
4. Corners with angle between left and right handles larger than 180 degrees are tagged as "concave".

Building from the concave corners the faces to intersect

GN Corner extruded

1. It is observed that the "distance from a point" function level set is a cone of 45 degrees half-angle, i.e. with Depth equal to Radius Top.
2. As a corner is shared by two adjacent rims, only a half-cone is kept, requiring an even number of Vertices.
3. The achieved faces are slightly shifted along the Z axis to avoid self-intersection with cone apex.
4. Half-cones are instanced at each concave corner.
5. The half-cone X axis is aligned with the bisector direction vector projected in the (X,Y) plane.
6. It is to notice on the picture above some failure at the junction between the two outer curves. Two cones are almost superimposed, with a full pink one. This is because two control points are very close there ; these should have been merged beforehand.

Computing the intersections

GN Intersect duplicate

1. Let $N$ be the number of rims. There are $N \times (N-1)$ combinations of two different rims to intersect.
2. To compute the intersection of rim of index $i$ with all rims of index $j$ such that $j \neq i$, the extruded faces are duplicated $N$ times along the Z axis. This yields $N \times N$ combinations. Then for the $i^\textrm{th}$ copy, faces belonging to rim $i$ are deleted to avoid self-intersection. This yields the sought $N \times (N-1)$ combinations.
3. Afterwards edges belonging to each rim $i$ are shifted along the Z axis to the "height" of the $i^\textrm{th}$ copy.

GN Intersect zoom

1. A Raycast node is used to compute the intersection. The Source Position is set to the position of points sampled along a rim. The Ray Direction is recovered by rotation of the unitary vector along Z axis around the local tangent, by 45 degrees.
2. The figure above illustrates the process for the first two rims of character "B". Cubes are instanced at the Hit Position to visualise intersections. Black strait lines are drawn only to visualise rays ; these are not involved in computing the intersection (Mesh Boolean node is not used).

GN Intersect multi-rims

1. This figure illustrates one of the most complex configuration that will require further research.
2. A single rim is intersecting two different curved rims (in yellow and blue, from left to right). Between, it is intersecting the cone from a concave corner (in pink).
3. So this rim yields at most three pieces of curve along the backbone. Ends should be computed to refine the junction between these adjacent pieces of curve.
4. An other improvement could be in removing the part along the cone, to keep only two pieces of curve.

Perspectives

  • Merge by distance control points from the original curves that are too close together ; these yield near singular cases easier to remove than to solve.
  • Remove duplicated backbones from the same both intersecting rims.
  • From a very dense sampling of backbones, identify underlying curves (in particular strait ones) to reduce as much as possible the number of final control points.
  • Remove curves connecting the backbone to the outlining curves.
  • Identify crossings of strait curves to remove the portion along extruded cones (from concave corners) and to bridge gaps.
  • Investigate the singularity of the dot character (.).

Resources

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .