Table of Contents
- Date
- 2018/08/15
This part of the manual describes how to digitize 3D parametric curves using a simple semi-automatic method.
3D Parametric Curves
Here we consider curves defined by parametric equations i.e., a group of functions of one variable, and hereafter called parametric curves. Each coordinate of a parametric curve, for a given parameter \( t \), is given by a corresponding function e.g., a parametric equation of a circle is given as \( \gamma : t \mapsto ( cos (t), sin(t) ) \). This module is related to digitization of 3D parametric curves.
In DGtal, each 3D parametric curve must be a model of C3DParametricCurve to be digitized.
Digitization - The algorithm
In this section we describe how to digitize 3D parametric curves using naive digitization method. Note that, the name of the method reflects the fact that this is a very naive method, which simply samples a curve with a given step parameter, and it is a numerical method that does not have any solid theoretical basis rooted in digital geometry. But in comparison to other known methods, that generate 26-connected digital curves, it does not require the coordinates' functions to be re-parametrized by each other, which often would involve existence of inverses of such functions. Such inverses even when they exist can be difficult to find.
In short the algorithm implemented in NaiveParametricCurveDigitizer3D.h is as follows.
Input: a 3D parametric curve \( \gamma \) (model of C3DParametricCurve), sampling step \( t \), and a sampling interval \( [t_{min}, t_{max}] \) such that \( t \in [t_{min}, t_{max}] \). Optionally, the user may provide a search parameter \( K_{NEXT} > 0 \) that controls how 26-adjacent neighbors are found. By default \( K_{NEXT} = 5 \).
Output: A sequence of integer points, which connectivity, in some places, may depends on \( K_{NEXT}, t \) and the relation between the curve's curvature and the digital grid (see some examples below).
Simplified pseudo-code:
Create a raw digitization
while \( t \in [t_{min}, t_{tmax}] \) dopoint = [ \( \gamma(t) \)] // [.] stands for a rounding function
weights[point] = weights[point] + 1
if not buffer.hasElement(point) thenbuffer.push_back(point)
t = t + step
digital_curve.push_back(buffer[0])
Refine the digitization by keeping only the most meaningful points i.e., points of high coverage of \( \gamma \).
for \(i = 1\) while \( i <\) size(buffer) do for \( j = i + 1 \) and \( k = 0 \) while \( j <\) size(buffer) and \( k < K_{NEXT} \) do
if is26Connected(digital_curve.back(), buffer[j]) and weights[buffer[j]] \( > \) weights[buffer[i]] then
\( i = j \)
\(k = 0 \)
else
\( k = k + 1 \)
\( j = j + 1 \)
digital_curve.push_back(buffer[i])
\( i = i + 1 \)Due to the weights fluctuations or curve behaviour we can still have points that should be removed to ensure 26-connectivity.
for \( i = 0 \) while \( i <\) size(buffer) do \( tmp = i + 1 \)
for \( j = i + 1 \) and \( k = 0 \) while \( j <\) size(buffer) and \( k < K_{NEXT} \) do if is26Connected(digital_curve[i], digital_curve[j]) then
\( tmp = j \)
\( k = 0 \)
else
\( k = k + 1 \)
\( j = j + 1 \)
digital_curve.erase(i + 1, tmp)
\( i = tmp + 1 \)
In the implemented version the buffer has size three times the value of \( K_{NEXT} \), and each time the buffer is flushed a part of the digital curve is created (see the two first nested loops in the code above). Also, the implemented version can treat closed curves and collect useful metadata.
Additional Information
The digitization implemented in NaiveParametricCurveDigitizer3D can collect, for each point of the output digital curve, information like
- weights i.e., the point importance
- time - a time value that minimize the distance between the integer point and \( \gamma \) for a given time step.
Note that, the time information is not computed by default therefore if not needed the user should avoid calling NaiveParametricCurveDigitizer3D::digitize(back_inserter_iterator, back_inserter_iterator), and use NaiveParametricCurveDigitizer3D::digitize(back_inserter_iterator), instead.
Examples
Example below shows how to digitize an elliptic helix (see EllipticHelix.h).
Before using NaiveParametricCurveDigitizer3D, you must include the following headers:
Note that, EllipticHelix.h should be replaced with the desirable curve. The list of 3D parametric curves is given below. Note that, EllipticHelix is the only curve that implements inverse functions (see EllipticHelix.h) for more information.
Then, you can construct the needed types as follows:
Also, we can state instances of the digitizer and the curve:
Finally, we can compute a digitization together with the meta information by calling:
The meta information can be then used, for example, to find main axis:
See exampleParamCurve3dDigitization.cpp and exampleTrofoliKnot.cpp
Implemented Curves
Elliptic Helix (see EllipticHelix.h)
Knot \( 3_1 \) (see Knot_3_1.h)
Knot \( 3_2 \) (see Knot_3_2.h)
Knot \( 4_1 \) (see Knot_4_1.h)
Knot \( 4_3 \) (see Knot_4_3.h)
Knot \( 5_1 \) (see Knot_5_1.h)
Knot \( 5_2 \) (see Knot_5_2.h)
Knot \( 6_2 \) (see Knot_6_2.h)
Knot \( 7_4 \) (see Knot_7_4.h)
For more information about parametrized knots see https://www.maa.org/sites/default/files/images/upload_library/23/stemkoski/knots/page1.html by Lee Stemkoski of Adelphi University.
Geometric Transformations of 3D Parametric Curves
It is possible to rotate a 3D parametric curve around an arbitrary origin and an axis by using DecoratorParametricCurveTransformation.
Example below shows how to digitize an elliptic helix (see EllipticHelix.h) rotated by \( \frac{\pi}{3} \) around \( \omega = (\frac{1}{\sqrt{2}}, 0, \frac{1}{\sqrt{2}}) \).
Before using DecoratorParametricCurveTransformation, you must include the following headers:
Then, you can construct the needed types as follows:
Also, we can state an instance of the curve i.e., elliptic helix of radii 30, 20 and distance between each period equal 1:
and we then state an instance of the decorator:
Finally, we can compute a digitization together with the meta information by calling:
See exampleParamCurve3dDigitizationTransformationDecorator.cpp.
Handling Problems
In this section we discuss how to deal with problems such as curves that do not lead to a 26-connected digitization with the default parameters ( \( K_{NEXT}, t_{step} \)).
Step values
High step values can lead to disconnections in the digitization. For example, knot $3_1$ with scaling factors all equal 10 for a step 0.03 leads to
In order, to solve the above issue it is necessary to lower the step value e.g., to 0.003.
A high step value can also lead to wrong weights which can impact quality of the digitization.
Connectivity Problems
By trying to digitize a curve with a high, with respect to the grid, curvature we can arrive at a connectivity problems. For instance, if we consider an elliptic helix of radii 20, 1 and period distance 1, and \( K_{NEXT} = 2 \), we can observe connectivity issues i.e., there are at least three points such that they are 26-connected to each other and therefore the curve is not 26-connected in such a place.
In order to resolve the issue it is necessary to increase the value of \( K_{NEXT} \).
List of related examples: exampleParamCurve3dDigitization.cpp, exampleParamCurve3dDigitizationTransformationDecorator.cpp, exampleTrofoliKnot.cpp
