Splines extraction on Kopf-Lischinski algorithm, part 0

Introduction

This post is a continuation of “Splines extraction on Kopf-Lischinski algorithm, part 1“. The title contains “part 0”, because the algorithm step described here should be executed before the algorithm step described in “part 1”.

This blog post is kind of unstructured, but don’t worry, because I’m aware of that and is intentional.

Generalized Voronoi diagram generation

The algorithm described in this section was kind of documented already, but the documentation wasn’t good enough to be part of a post, then it was keep as a private home-made PDF.

Well, a Voronoi diagram is a black box where you put some points (the seeds) and you get some polygons (the cells). Each polygon contains all points that are closer to its seed than any other seed. There is a good article on Wikipédia and I won’t explain any further.

Kopf-Lischinski algorithm executes a bunch of operations on a graph and it uses a Voronoi diagrams to extract a visual representation from this graph. The simplest form of a Voronoi diagram works with 2D points-seeds, but we have higher-dimentional Voronoi diagrams, Voronoi diagrams using different distance functions and even Voronoi diagrams using complex non-points seeds. We are interested in these Voronoi diagrams using complex non-points seeds.

The below image has a representation of the output graph of the Kopf-Lischinski algorithm and its Voronoi diagram representation. The graph nodes are represented by circles, where nodes with the same color are similar and usually are connected. The connections of the nodes are represented by green lines.

An accurate generalized Voronoi diagram

The generalized Voronoi diagram is visual, then there is no special meaning to explain it in the previous image. The seeds of this diagram aren’t points, they are line segments. You just need to break a green line in two and add each half to its containing cell. You can note that some polygons aren’t convex.

The graph used as input has certain constraints that enable us to use some simple and fast operations instead of a full-featured and complex algorithm.

If a Voronoi cell is a polygon containing all points that are closer to its seed than any other seed, we can determine the edge of a Voronoi cell by the midpoint of two adjacent seeds. If we generate a vertex for each of its 8 directions, we will get an accurate Voronoi diagram.

A simplified generalized Voronoi diagram

We can get a simplified Voronoi diagram by forgetting about the top, bottom, left and right vertices (if we just generate the diagonal vertices). The simplified version doesn’t contain concave polygons.

The act of generating diagonal vertices is more complex than the act of generating the other vertices. We need to check if there is a connection with the other cell and, if this connection exists, generate two vertices. If the connection doesn’t exist, we generate a single vertex, but its position depends on the existence of a connection between its neighbors. Look the following figure.

A simplified generalized Voronoi diagram (detailed)

All information we need to generate the Voronoi diagram is located within its neighbors and the only extra tool we need to generate the points is the midpoint procedure. This is old news and it was already implemented in libdepixelize.

Metadata extraction

When we generate B-Splines using Kopf-Lischinski algorithm we need a way to separate points that create sharp corners and smooth points. The Kopf-Lischinski algorithm has techniques just to handle this issue. In libdepixelize, I decided to merge the point smoothness computation and Voronoi generation in one single phase. This is the phase where we can gather lot of info about the graph and we can propagate the smoothness data to later phases.

One note about the algorithm of this “metadata extraction” section is that some points will disappear during polygon union and we don’t care if the metadata about these points are accurate, then we can simplify the algorithm exploring this property. The below image will be citated all time during this time to how explain this algorithm:

Vertex types

There are two types of vertices generated in this special Voronoi diagram:

• White type: The type of the one labelled with “#1”. Node “#1” is contained by three cells, one purple and two yellows. The two yellow cells will be merged during polygon-union. There are two possibilities for the remaining cell in this kind of node:
  • When it has the same color. Then the node will disappear during polygon-union and we don’t care about its “smoothness” attribute.
  • When it has a different color. Then we say it is a valence-2 node.
• Cyan type: The type of the one labelled with “#2”. This type of node can appear in the border of the image and isn’t smooth or in the center of 4 cells and its smoothness isn’t predictable in advance. If it appears in center of four cells, then:
  • It can be in the middle of 4-connected cells and we don’t care about its “smoothness” attribute, because this node will disappear.
  • It can be in the middle of a valence-2 node and will be smooth.
  • It can be a valence-3 node and things start to get complex. After the polygon union, this node will be part of three different polygon and only two of these three nodes will share the same value for the “smoothness” attribute.

Problem explained, it’s time to algorithm! The algorithm is kind of repetitive (if we iterate the bottom-right node, compare with bottom and right nodes, then do all it again, but use nodes of different directions…), but the principle is the same for all “repetitive” code, then I’m only going to put the important parts and you’ll be able to see the full algorithm implemented in libdepixelize within a few hours. Lastly, this isn’t the first algorithm I came up with and I made a lot of iteractions already (lots of crumpled paper on my room’s floor), but I think the result can perform pretty fast and I’m content. This post is kind of a documentation and it will help me to not forget what I wanted to do in the code.

The above image represents the analysed data in the following code example, except for the fact that we don’t know what are the colors of the cells. We are iterating on the middle point of the image and the current iterated cell is cell A. The algorithm also uses the concept of “shading edge” and “contour edge” described in Kopf-Lischinski algorithm paper.

	A; //< cell A
	// current iterated node (the one in the middle of the image) smoothness
	A.smooth;
	// It's a cyan node!
	assert(!A.connected(D));
	assert(!B.connected(C));
	if ( A.connected(B) ) {
	if ( !C.connected(D) ) {
	bool foreign_is_contour = edge(C, D).contour();
	// the number of contour edges
	switch ( edge(A, C).contour()
	+ edge(B, D).contour()
	+ foreign_is_contour ) {
	case 2:
	A.smooth = !foreign_is_contour;
	break;
	default:
	assert(("precondition failed", false));
	// the following cases are only for documentation
	// of possible values (they don't change the algorithm)
	case 3: case 1: case 0:
	// {A, B} is the pair with the angle closest to 180 degrees
	A.smooth = true;
	}
	} else {
	// there might be 2-color, then A.smooth = true
	// or it might be 1-color and doesn't matter,
	// because the current node will disappear
	A.smooth = true;
	}
	} else if ( A.connected(C) ) {
	// very similar to the previous condition
	} else if ( B.connected(D) ) {
	bool foreign_is_contour = edge(C, D).contour();
	switch ( edge(A, B).contour()
	+ edge(A, C).contour()
	+ foreign_is_contour ) {
	case 2:
	A.smooth = !foreign_is_contour;
	break;
	default:
	assert(("precondition failed", false));
	case 3: case 1: case 0:
	// {B, D} is the pair with the angle closest to 180 degrees
	A.smooth = false;
	}
	} else if ( C.connected(D) ) {
	// very similar to the previous condition
	} else {
	// there is a 4-color pattern, where the current node
	// won't be smooth
	A.smooth = false;
	}

view raw metadata_extraction.cpp hosted with ❤ by GitHub

All images in this post were created using Inkscape and its awesome alignment tools.