Page MenuHome

Freestyle: Adaptive Stroke Sampling
Needs ReviewPublic

Authored by Folkert de Vries (flokkievids) on Aug 17 2015, 9:50 PM.

Details

Summary

This patch adds adaptive stroke sampling to Freestyle.

Adaptive stroke sampling means that the density (amount of stroke vertices) depends on the delta curvature (so the amount of curvature change). Curvy areas will get more points, and therefore detail/smoothness than straight segments.

The vertex removal is based on the Simplification stroke shader, which in turn is based on:

simplify.js by Vladimir Agafonkin, the c++ implementation is based on simplify-rs by Calvin Metcalf.

currently implemented:

  • simplification of a collection of strokes
  • boilerplate for a c/python stroke shader

Diff Detail

Event Timeline

Folkert de Vries (flokkievids) retitled this revision from to Freestyle: Adaptive Stroke Sampling.
Folkert de Vries (flokkievids) updated this object.

This is a first draft of this method.

The code is quite messy at the moment.

  • I haven't been able to figure out how to enable C++11, so no auto/std::next/foreach+closure/maybe more cool stuff
  • The c++ stdlib doesn't have an ordered, easily searchable container with unique elements. In Python this is easily implementable (with abstract base classes), but I'm not so sure about c++.

This special container is needed to remove a lot of logic preventing the double pushing of the same stroke vertex (which causes a double free). Other fixes would almost certainly involve a lot of logic/boilerplate of their own.

further notes:

  • the angle calculation could be turned into an F0D operation (I personally would like this; can be reused by the TangentShaders)
  • I added new functions to vectors: sum (sum of all elements) and angle (angle in radians between two vectors, always between 0 and pi).

An algorithm question: how adaptive does the sampling need to be. can the sampling interval be constant between two points, or should it be a gradient based on the distance between and the angle at two points?

well, Curvature2DAngleF0D is already implemented. I'm not quite sure why the Tangent shaders don't use it already though: are there issues with it? Judging by the implementation, all seems fine.

Thanks for the patch submission. Here are my notes on some of the posed questions.

I am pretty new to C++11 so I don't have immediate answers to the questions on C++11 features. We might ask for some help from other core devs (e.g., Sergey) in this regard.

We can define the adaptive nature of the sampling method in different ways. Sampling results are an approximation of the original input stroke geometry, so what we need is a quantitative measure of how the approximation is good. One option is to allow users to specify a tolerance (i.e., an amount of allowed errors) as in the Bezier geometry modifier. Errors could then be defined, for example, based on the distance of a new stroke vertex from the original stroke geometry. Since we have many stroke vertices, the measure could be some summary statistic such as the sum of the distances evaluated at individual stroke vertices, and more simply the average distance. We need considerations here to make the parameters of the adaptive sampling artist-friendly.

As to Curvature2DAngleF0D, it computes the angle between an incoming and outgoing edges at individual stroke vertices. The Tangent shaders instead rely on freestyle.utils.angle_x_normal() that computes the angle between the normal direction and the X axis at each stroke vertex. These two look resemble but they are different.