Mixing
Tangent line to a 3D curve at a given 3D point
$begingroup$
I'm trying to compute tangent vector(x,y,z) to a 3D curve(start x1,y1,z1 end x2,y2,z2) at a point (x0,y0,z0). Can anyone tell if this information is sufficient to calculate the tangent vector? If yes can anyone tell the formula with the help of some values. Help is greatly appreciated!!!
3d curves math-software
asked Jan 10 at 14:44
KushKush
1
$endgroup$
add a comment |
$begingroup$
I'm trying to compute tangent vector(x,y,z) to a 3D curve(start x1,y1,z1 end x2,y2,z2) at a point (x0,y0,z0). Can anyone tell if this information is sufficient to calculate the tangent vector? If yes can anyone tell the formula with the help of some values. Help is greatly appreciated!!!
3d curves math-software
asked Jan 10 at 14:44
KushKush
1
$endgroup$
$begingroup$
You need some equation or description of the curve. There are a lot of them that go through three points in space.
$endgroup$
– amd
Jan 10 at 20:47
add a comment |
$begingroup$
I'm trying to compute tangent vector(x,y,z) to a 3D curve(start x1,y1,z1 end x2,y2,z2) at a point (x0,y0,z0). Can anyone tell if this information is sufficient to calculate the tangent vector? If yes can anyone tell the formula with the help of some values. Help is greatly appreciated!!!
3d curves math-software
asked Jan 10 at 14:44
KushKush
1
$endgroup$
I'm trying to compute tangent vector(x,y,z) to a 3D curve(start x1,y1,z1 end x2,y2,z2) at a point (x0,y0,z0). Can anyone tell if this information is sufficient to calculate the tangent vector? If yes can anyone tell the formula with the help of some values. Help is greatly appreciated!!!
3d curves math-software
3d curves math-software
asked Jan 10 at 14:44
KushKush
1
asked Jan 10 at 14:44
KushKush
1
asked Jan 10 at 14:44
KushKush
1
asked Jan 10 at 14:44
KushKush
1
asked Jan 10 at 14:44
KushKush
1
1
$begingroup$
You need some equation or description of the curve. There are a lot of them that go through three points in space.
$endgroup$
– amd
Jan 10 at 20:47
add a comment |
$begingroup$
You need some equation or description of the curve. There are a lot of them that go through three points in space.
$endgroup$
– amd
Jan 10 at 20:47
$begingroup$
You need some equation or description of the curve. There are a lot of them that go through three points in space.
$endgroup$
– amd
Jan 10 at 20:47
$begingroup$
You need some equation or description of the curve. There are a lot of them that go through three points in space.
$endgroup$
– amd
Jan 10 at 20:47
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Can anyone tell if this information is sufficient to calculate the tangent vector?
No. We need to know the shape of the curve.
Knowing the curve passes via $vec{p}_s = (x_s , y_s , z_s)$ and $vec{p}_e = (x_e , y_e , z_e)$ does not tell us anything about the shape of the curve. In the simplest case, the curve would be a straight line, and in that case its tangent is everywhere the same, $vec{p}_e - vec{p}_s$.
In computer programs, cubic Bézier curves are ubiquitous. They are defined using four points. The curve passes through the first point $vec{p}_1 = (x_1 , y_1 , z_1) = vec{p}_s$ and the last point $vec{p}_4 = (x_4 , y_4 , z_4) = vec{p}_e$, but the other two just control the shape of the curve. Mathematically,
$$bbox{ begin{cases}
x(t) = (1-t)^3 x_1 + 3 (1-t)^2 t x_2 + 3 (1-t) t^2 x_3 + t^3 x_4 \
y(t) = (1-t)^3 y_1 + 3 (1-t)^2 t y_2 + 3 (1-t) t^2 y_3 + t^3 y_4 \
z(t) = (1-t)^3 z_1 + 3 (1-t)^2 t z_2 + 3 (1-t) t^2 z_3 + t^3 z_4 \
end{cases}, quad 0 le t le 1 } tag{1}label{NA1}$$
Note that that notation is just a good, easy form to express the curve. We could write the curve coordinates as third-degree polynomials,
$$bbox{ begin{cases}
x(t) = X_0 + t X_1 + t^2 X_2 + t^3 X_3 \
y(t) = Y_0 + t Y_1 + t^2 Y_2 + t^3 Y_3 \
z(t) = Z_0 + t Z_1 + t^2 Z_2 + t^3 Z_3 \
end{cases} }, quad bbox{begin{cases}
X_0 = x_1 \
X_1 = 3 x_2 - 3 x_1 \
X_2 = 3 x_3 - 6 x_2 + 3 x_1 \
X_3 = x_4 - 3 x_3 + 3 x_2 - x_1 \
end{cases} } tag{2}label{NA2}$$
but in computer programs $eqref{NA1}$ is more numerically stable.
Non-uniform rational B-splines are a more general form of curves, used especially in modeling. You can obtain the tangent vectors on NURBS using basically the same way as below; you just use the NURBS equations for the coordinates instead.
If you've ever used Inkscape to doodle shapes, you probably have used the Bézier curve tool to draw cubic Bézier curves already. Start and end points are shown as boxy dots, and those control points as "handles", a circular dot connected to the start or end point on the curve. They are used in PostScript and SVG formats as well.
The tangent vector at any point $t$ along the curve is simply the derivative of the coordinates. Using $eqref{NA2}$ above,
$$bbox{ begin{cases}
displaystyle frac{d x(t)}{d t} = X_1 + 2 X_2 t + 3 t^2 X_3 \
displaystyle frac{d y(t)}{d t} = Y_1 + 2 Y_2 t + 3 t^2 Y_3 \
displaystyle frac{d z(t)}{d t} = Z_1 + 2 Z_2 t + 3 t^2 Z_3 \
end{cases} } tag{3}label{NA3}$$
However, we can also describe the tangent in quadratic Bézier form, by deriving $eqref{NA1}$, and reordering the terms. We get
$$bbox{ begin{cases}
displaystyle frac{d x(t)}{d t} = (1-t)^2 ( 3 x_2 - 3 x_1) + 2 (1-t) t ( 3 x_3 - 3 x_2 ) + t^2 ( 3 x_4 - 3 x_3 ) \
displaystyle frac{d y(t)}{d t} = (1-t)^2 ( 3 y_2 - 3 y_1) + 2 (1-t) t ( 3 y_3 - 3 y_2 ) + t^2 ( 3 y_4 - 3 y_3 ) \
displaystyle frac{d z(t)}{d t} = (1-t)^2 ( 3 z_2 - 3 z_1) + 2 (1-t) t ( 3 z_3 - 3 z_2 ) + t^2 ( 3 z_4 - 3 z_3 ) \
end{cases} } tag{4}label{NA4}$$
This form, $eqref{NA4}$, is again numerically quite stable, and is very suitable for use in a computer program.
That leaves one more problem to solve: how to find the curve parameter $t$ that corresponds to a point I already have?
There are algebraic solutions for linear curves (lines), quadratic curves, and cubic curves. Essentially, you can pick one of the coordinate functions, say $x$, and solve
$$x(t) - x = 0$$
using any root-finding algorithm. For quadratic curves, you find up to two real $t$; for cubic, up to three real $t$. You ignore non-real roots and $t lt 0$ and $t gt 0$, and check the candidates left if $y(t) = y$ and $z(t) = z$ at sufficient precision.
In computer programs, you always do such tests as $lvert y(t) - y rvert le epsilon$ and $lvert z(t) - z rvert le epsilon$, where $epsilon$ represents the precision in your coordinates: the largest difference in coordinates that you consider neglible. For example, if you read your point cloud coordinates with three decimals, use $epsilon = 0.0005$.
If your computer program already implements a fast curve point evaluation function (the simple form is fast enough!), a binary search in $t$ may prove faster. (It is also a very interesting approach if you have many curve types, or use polynomial functions of possibly very high degree for your curves.) The only "trick" needed is that because some curves have loops (i.e., the coordinates are not monotonic functions), you may have to split the initial $0 le t le 1$ to smaller ranges, to ensure you find the $t$ on the curve closest to the specified point, rather than a value of $t$ that is closer than its nearby points. (It is the difference between local and global minima.)
Essentially, you pick one of the coordinate functions, a range $0 le t_{min} lt t_{max} le 1$ in which the function is monotonic (increases or decreases, but not both), and then
Function BSearch(coordfunc, target, tmin, tmax, epsilon):
Let vmin = coordfunc(tmin) - target
Let vmax = coordfunc(tmax) - target
If vmin > vmax:
Let ttmp = tmin ; tmin = tmax ; tmax = ttmp
Let vtmp = vmin ; vmin = vmax ; vmax = vtmp
End If
If vmin > 0:
Return tmin
Else If vmax < 0:
Return tmax
End If
Loop:
Let t = (tmin + tmax) / 2
If vmax - vmin <= epsilon:
Return t
End If
Let v = coordfunc(t) - target
If (v < 0) and (v >= vmin):
tmin = t
Else
If (v > 0) and (v <= vmax):
tmax = t
Else
If (v == 0):
Return t
Else:
# Function is non-monotonic.
Return Failed
End If
End Loop
End Loop
The function will return the value of t that is closest to the target coordinate, within the range specified. If it detects the function is non-monotonic, it will return Failed. Because the function is only sampled, it does not reliably detect non-monotonic functions, and can return a non-optimal t for such functions.
answered Jan 11 at 1:36
Nominal AnimalNominal Animal
7,0332517
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3068714%2ftangent-line-to-a-3d-curve-at-a-given-3d-point%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Can anyone tell if this information is sufficient to calculate the tangent vector?
No. We need to know the shape of the curve.
Knowing the curve passes via $vec{p}_s = (x_s , y_s , z_s)$ and $vec{p}_e = (x_e , y_e , z_e)$ does not tell us anything about the shape of the curve. In the simplest case, the curve would be a straight line, and in that case its tangent is everywhere the same, $vec{p}_e - vec{p}_s$.
In computer programs, cubic Bézier curves are ubiquitous. They are defined using four points. The curve passes through the first point $vec{p}_1 = (x_1 , y_1 , z_1) = vec{p}_s$ and the last point $vec{p}_4 = (x_4 , y_4 , z_4) = vec{p}_e$, but the other two just control the shape of the curve. Mathematically,
$$bbox{ begin{cases}
x(t) = (1-t)^3 x_1 + 3 (1-t)^2 t x_2 + 3 (1-t) t^2 x_3 + t^3 x_4 \
y(t) = (1-t)^3 y_1 + 3 (1-t)^2 t y_2 + 3 (1-t) t^2 y_3 + t^3 y_4 \
z(t) = (1-t)^3 z_1 + 3 (1-t)^2 t z_2 + 3 (1-t) t^2 z_3 + t^3 z_4 \
end{cases}, quad 0 le t le 1 } tag{1}label{NA1}$$
Note that that notation is just a good, easy form to express the curve. We could write the curve coordinates as third-degree polynomials,
$$bbox{ begin{cases}
x(t) = X_0 + t X_1 + t^2 X_2 + t^3 X_3 \
y(t) = Y_0 + t Y_1 + t^2 Y_2 + t^3 Y_3 \
z(t) = Z_0 + t Z_1 + t^2 Z_2 + t^3 Z_3 \
end{cases} }, quad bbox{begin{cases}
X_0 = x_1 \
X_1 = 3 x_2 - 3 x_1 \
X_2 = 3 x_3 - 6 x_2 + 3 x_1 \
X_3 = x_4 - 3 x_3 + 3 x_2 - x_1 \
end{cases} } tag{2}label{NA2}$$
but in computer programs $eqref{NA1}$ is more numerically stable.
Non-uniform rational B-splines are a more general form of curves, used especially in modeling. You can obtain the tangent vectors on NURBS using basically the same way as below; you just use the NURBS equations for the coordinates instead.
If you've ever used Inkscape to doodle shapes, you probably have used the Bézier curve tool to draw cubic Bézier curves already. Start and end points are shown as boxy dots, and those control points as "handles", a circular dot connected to the start or end point on the curve. They are used in PostScript and SVG formats as well.
The tangent vector at any point $t$ along the curve is simply the derivative of the coordinates. Using $eqref{NA2}$ above,
$$bbox{ begin{cases}
displaystyle frac{d x(t)}{d t} = X_1 + 2 X_2 t + 3 t^2 X_3 \
displaystyle frac{d y(t)}{d t} = Y_1 + 2 Y_2 t + 3 t^2 Y_3 \
displaystyle frac{d z(t)}{d t} = Z_1 + 2 Z_2 t + 3 t^2 Z_3 \
end{cases} } tag{3}label{NA3}$$
However, we can also describe the tangent in quadratic Bézier form, by deriving $eqref{NA1}$, and reordering the terms. We get
$$bbox{ begin{cases}
displaystyle frac{d x(t)}{d t} = (1-t)^2 ( 3 x_2 - 3 x_1) + 2 (1-t) t ( 3 x_3 - 3 x_2 ) + t^2 ( 3 x_4 - 3 x_3 ) \
displaystyle frac{d y(t)}{d t} = (1-t)^2 ( 3 y_2 - 3 y_1) + 2 (1-t) t ( 3 y_3 - 3 y_2 ) + t^2 ( 3 y_4 - 3 y_3 ) \
displaystyle frac{d z(t)}{d t} = (1-t)^2 ( 3 z_2 - 3 z_1) + 2 (1-t) t ( 3 z_3 - 3 z_2 ) + t^2 ( 3 z_4 - 3 z_3 ) \
end{cases} } tag{4}label{NA4}$$
This form, $eqref{NA4}$, is again numerically quite stable, and is very suitable for use in a computer program.
That leaves one more problem to solve: how to find the curve parameter $t$ that corresponds to a point I already have?
There are algebraic solutions for linear curves (lines), quadratic curves, and cubic curves. Essentially, you can pick one of the coordinate functions, say $x$, and solve
$$x(t) - x = 0$$
using any root-finding algorithm. For quadratic curves, you find up to two real $t$; for cubic, up to three real $t$. You ignore non-real roots and $t lt 0$ and $t gt 0$, and check the candidates left if $y(t) = y$ and $z(t) = z$ at sufficient precision.
In computer programs, you always do such tests as $lvert y(t) - y rvert le epsilon$ and $lvert z(t) - z rvert le epsilon$, where $epsilon$ represents the precision in your coordinates: the largest difference in coordinates that you consider neglible. For example, if you read your point cloud coordinates with three decimals, use $epsilon = 0.0005$.
If your computer program already implements a fast curve point evaluation function (the simple form is fast enough!), a binary search in $t$ may prove faster. (It is also a very interesting approach if you have many curve types, or use polynomial functions of possibly very high degree for your curves.) The only "trick" needed is that because some curves have loops (i.e., the coordinates are not monotonic functions), you may have to split the initial $0 le t le 1$ to smaller ranges, to ensure you find the $t$ on the curve closest to the specified point, rather than a value of $t$ that is closer than its nearby points. (It is the difference between local and global minima.)
Essentially, you pick one of the coordinate functions, a range $0 le t_{min} lt t_{max} le 1$ in which the function is monotonic (increases or decreases, but not both), and then
Function BSearch(coordfunc, target, tmin, tmax, epsilon):
Let vmin = coordfunc(tmin) - target
Let vmax = coordfunc(tmax) - target
If vmin > vmax:
Let ttmp = tmin ; tmin = tmax ; tmax = ttmp
Let vtmp = vmin ; vmin = vmax ; vmax = vtmp
End If
If vmin > 0:
Return tmin
Else If vmax < 0:
Return tmax
End If
Loop:
Let t = (tmin + tmax) / 2
If vmax - vmin <= epsilon:
Return t
End If
Let v = coordfunc(t) - target
If (v < 0) and (v >= vmin):
tmin = t
Else
If (v > 0) and (v <= vmax):
tmax = t
Else
If (v == 0):
Return t
Else:
# Function is non-monotonic.
Return Failed
End If
End Loop
End Loop
The function will return the value of t that is closest to the target coordinate, within the range specified. If it detects the function is non-monotonic, it will return Failed. Because the function is only sampled, it does not reliably detect non-monotonic functions, and can return a non-optimal t for such functions.
answered Jan 11 at 1:36
Nominal AnimalNominal Animal
7,0332517
$endgroup$
add a comment |
$begingroup$
Can anyone tell if this information is sufficient to calculate the tangent vector?
No. We need to know the shape of the curve.
Knowing the curve passes via $vec{p}_s = (x_s , y_s , z_s)$ and $vec{p}_e = (x_e , y_e , z_e)$ does not tell us anything about the shape of the curve. In the simplest case, the curve would be a straight line, and in that case its tangent is everywhere the same, $vec{p}_e - vec{p}_s$.
In computer programs, cubic Bézier curves are ubiquitous. They are defined using four points. The curve passes through the first point $vec{p}_1 = (x_1 , y_1 , z_1) = vec{p}_s$ and the last point $vec{p}_4 = (x_4 , y_4 , z_4) = vec{p}_e$, but the other two just control the shape of the curve. Mathematically,
$$bbox{ begin{cases}
x(t) = (1-t)^3 x_1 + 3 (1-t)^2 t x_2 + 3 (1-t) t^2 x_3 + t^3 x_4 \
y(t) = (1-t)^3 y_1 + 3 (1-t)^2 t y_2 + 3 (1-t) t^2 y_3 + t^3 y_4 \
z(t) = (1-t)^3 z_1 + 3 (1-t)^2 t z_2 + 3 (1-t) t^2 z_3 + t^3 z_4 \
end{cases}, quad 0 le t le 1 } tag{1}label{NA1}$$
Note that that notation is just a good, easy form to express the curve. We could write the curve coordinates as third-degree polynomials,
$$bbox{ begin{cases}
x(t) = X_0 + t X_1 + t^2 X_2 + t^3 X_3 \
y(t) = Y_0 + t Y_1 + t^2 Y_2 + t^3 Y_3 \
z(t) = Z_0 + t Z_1 + t^2 Z_2 + t^3 Z_3 \
end{cases} }, quad bbox{begin{cases}
X_0 = x_1 \
X_1 = 3 x_2 - 3 x_1 \
X_2 = 3 x_3 - 6 x_2 + 3 x_1 \
X_3 = x_4 - 3 x_3 + 3 x_2 - x_1 \
end{cases} } tag{2}label{NA2}$$
but in computer programs $eqref{NA1}$ is more numerically stable.
Non-uniform rational B-splines are a more general form of curves, used especially in modeling. You can obtain the tangent vectors on NURBS using basically the same way as below; you just use the NURBS equations for the coordinates instead.
If you've ever used Inkscape to doodle shapes, you probably have used the Bézier curve tool to draw cubic Bézier curves already. Start and end points are shown as boxy dots, and those control points as "handles", a circular dot connected to the start or end point on the curve. They are used in PostScript and SVG formats as well.
The tangent vector at any point $t$ along the curve is simply the derivative of the coordinates. Using $eqref{NA2}$ above,
$$bbox{ begin{cases}
displaystyle frac{d x(t)}{d t} = X_1 + 2 X_2 t + 3 t^2 X_3 \
displaystyle frac{d y(t)}{d t} = Y_1 + 2 Y_2 t + 3 t^2 Y_3 \
displaystyle frac{d z(t)}{d t} = Z_1 + 2 Z_2 t + 3 t^2 Z_3 \
end{cases} } tag{3}label{NA3}$$
However, we can also describe the tangent in quadratic Bézier form, by deriving $eqref{NA1}$, and reordering the terms. We get
$$bbox{ begin{cases}
displaystyle frac{d x(t)}{d t} = (1-t)^2 ( 3 x_2 - 3 x_1) + 2 (1-t) t ( 3 x_3 - 3 x_2 ) + t^2 ( 3 x_4 - 3 x_3 ) \
displaystyle frac{d y(t)}{d t} = (1-t)^2 ( 3 y_2 - 3 y_1) + 2 (1-t) t ( 3 y_3 - 3 y_2 ) + t^2 ( 3 y_4 - 3 y_3 ) \
displaystyle frac{d z(t)}{d t} = (1-t)^2 ( 3 z_2 - 3 z_1) + 2 (1-t) t ( 3 z_3 - 3 z_2 ) + t^2 ( 3 z_4 - 3 z_3 ) \
end{cases} } tag{4}label{NA4}$$
This form, $eqref{NA4}$, is again numerically quite stable, and is very suitable for use in a computer program.
That leaves one more problem to solve: how to find the curve parameter $t$ that corresponds to a point I already have?
There are algebraic solutions for linear curves (lines), quadratic curves, and cubic curves. Essentially, you can pick one of the coordinate functions, say $x$, and solve
$$x(t) - x = 0$$
using any root-finding algorithm. For quadratic curves, you find up to two real $t$; for cubic, up to three real $t$. You ignore non-real roots and $t lt 0$ and $t gt 0$, and check the candidates left if $y(t) = y$ and $z(t) = z$ at sufficient precision.
In computer programs, you always do such tests as $lvert y(t) - y rvert le epsilon$ and $lvert z(t) - z rvert le epsilon$, where $epsilon$ represents the precision in your coordinates: the largest difference in coordinates that you consider neglible. For example, if you read your point cloud coordinates with three decimals, use $epsilon = 0.0005$.
If your computer program already implements a fast curve point evaluation function (the simple form is fast enough!), a binary search in $t$ may prove faster. (It is also a very interesting approach if you have many curve types, or use polynomial functions of possibly very high degree for your curves.) The only "trick" needed is that because some curves have loops (i.e., the coordinates are not monotonic functions), you may have to split the initial $0 le t le 1$ to smaller ranges, to ensure you find the $t$ on the curve closest to the specified point, rather than a value of $t$ that is closer than its nearby points. (It is the difference between local and global minima.)
Essentially, you pick one of the coordinate functions, a range $0 le t_{min} lt t_{max} le 1$ in which the function is monotonic (increases or decreases, but not both), and then
Function BSearch(coordfunc, target, tmin, tmax, epsilon):
Let vmin = coordfunc(tmin) - target
Let vmax = coordfunc(tmax) - target
If vmin > vmax:
Let ttmp = tmin ; tmin = tmax ; tmax = ttmp
Let vtmp = vmin ; vmin = vmax ; vmax = vtmp
End If
If vmin > 0:
Return tmin
Else If vmax < 0:
Return tmax
End If
Loop:
Let t = (tmin + tmax) / 2
If vmax - vmin <= epsilon:
Return t
End If
Let v = coordfunc(t) - target
If (v < 0) and (v >= vmin):
tmin = t
Else
If (v > 0) and (v <= vmax):
tmax = t
Else
If (v == 0):
Return t
Else:
# Function is non-monotonic.
Return Failed
End If
End Loop
End Loop
The function will return the value of t that is closest to the target coordinate, within the range specified. If it detects the function is non-monotonic, it will return Failed. Because the function is only sampled, it does not reliably detect non-monotonic functions, and can return a non-optimal t for such functions.
answered Jan 11 at 1:36
Nominal AnimalNominal Animal
7,0332517
$endgroup$
add a comment |
$begingroup$
Can anyone tell if this information is sufficient to calculate the tangent vector?
No. We need to know the shape of the curve.
Knowing the curve passes via $vec{p}_s = (x_s , y_s , z_s)$ and $vec{p}_e = (x_e , y_e , z_e)$ does not tell us anything about the shape of the curve. In the simplest case, the curve would be a straight line, and in that case its tangent is everywhere the same, $vec{p}_e - vec{p}_s$.
In computer programs, cubic Bézier curves are ubiquitous. They are defined using four points. The curve passes through the first point $vec{p}_1 = (x_1 , y_1 , z_1) = vec{p}_s$ and the last point $vec{p}_4 = (x_4 , y_4 , z_4) = vec{p}_e$, but the other two just control the shape of the curve. Mathematically,
$$bbox{ begin{cases}
x(t) = (1-t)^3 x_1 + 3 (1-t)^2 t x_2 + 3 (1-t) t^2 x_3 + t^3 x_4 \
y(t) = (1-t)^3 y_1 + 3 (1-t)^2 t y_2 + 3 (1-t) t^2 y_3 + t^3 y_4 \
z(t) = (1-t)^3 z_1 + 3 (1-t)^2 t z_2 + 3 (1-t) t^2 z_3 + t^3 z_4 \
end{cases}, quad 0 le t le 1 } tag{1}label{NA1}$$
Note that that notation is just a good, easy form to express the curve. We could write the curve coordinates as third-degree polynomials,
$$bbox{ begin{cases}
x(t) = X_0 + t X_1 + t^2 X_2 + t^3 X_3 \
y(t) = Y_0 + t Y_1 + t^2 Y_2 + t^3 Y_3 \
z(t) = Z_0 + t Z_1 + t^2 Z_2 + t^3 Z_3 \
end{cases} }, quad bbox{begin{cases}
X_0 = x_1 \
X_1 = 3 x_2 - 3 x_1 \
X_2 = 3 x_3 - 6 x_2 + 3 x_1 \
X_3 = x_4 - 3 x_3 + 3 x_2 - x_1 \
end{cases} } tag{2}label{NA2}$$
but in computer programs $eqref{NA1}$ is more numerically stable.
Non-uniform rational B-splines are a more general form of curves, used especially in modeling. You can obtain the tangent vectors on NURBS using basically the same way as below; you just use the NURBS equations for the coordinates instead.
If you've ever used Inkscape to doodle shapes, you probably have used the Bézier curve tool to draw cubic Bézier curves already. Start and end points are shown as boxy dots, and those control points as "handles", a circular dot connected to the start or end point on the curve. They are used in PostScript and SVG formats as well.
The tangent vector at any point $t$ along the curve is simply the derivative of the coordinates. Using $eqref{NA2}$ above,
$$bbox{ begin{cases}
displaystyle frac{d x(t)}{d t} = X_1 + 2 X_2 t + 3 t^2 X_3 \
displaystyle frac{d y(t)}{d t} = Y_1 + 2 Y_2 t + 3 t^2 Y_3 \
displaystyle frac{d z(t)}{d t} = Z_1 + 2 Z_2 t + 3 t^2 Z_3 \
end{cases} } tag{3}label{NA3}$$
However, we can also describe the tangent in quadratic Bézier form, by deriving $eqref{NA1}$, and reordering the terms. We get
$$bbox{ begin{cases}
displaystyle frac{d x(t)}{d t} = (1-t)^2 ( 3 x_2 - 3 x_1) + 2 (1-t) t ( 3 x_3 - 3 x_2 ) + t^2 ( 3 x_4 - 3 x_3 ) \
displaystyle frac{d y(t)}{d t} = (1-t)^2 ( 3 y_2 - 3 y_1) + 2 (1-t) t ( 3 y_3 - 3 y_2 ) + t^2 ( 3 y_4 - 3 y_3 ) \
displaystyle frac{d z(t)}{d t} = (1-t)^2 ( 3 z_2 - 3 z_1) + 2 (1-t) t ( 3 z_3 - 3 z_2 ) + t^2 ( 3 z_4 - 3 z_3 ) \
end{cases} } tag{4}label{NA4}$$
This form, $eqref{NA4}$, is again numerically quite stable, and is very suitable for use in a computer program.
That leaves one more problem to solve: how to find the curve parameter $t$ that corresponds to a point I already have?
There are algebraic solutions for linear curves (lines), quadratic curves, and cubic curves. Essentially, you can pick one of the coordinate functions, say $x$, and solve
$$x(t) - x = 0$$
using any root-finding algorithm. For quadratic curves, you find up to two real $t$; for cubic, up to three real $t$. You ignore non-real roots and $t lt 0$ and $t gt 0$, and check the candidates left if $y(t) = y$ and $z(t) = z$ at sufficient precision.
In computer programs, you always do such tests as $lvert y(t) - y rvert le epsilon$ and $lvert z(t) - z rvert le epsilon$, where $epsilon$ represents the precision in your coordinates: the largest difference in coordinates that you consider neglible. For example, if you read your point cloud coordinates with three decimals, use $epsilon = 0.0005$.
If your computer program already implements a fast curve point evaluation function (the simple form is fast enough!), a binary search in $t$ may prove faster. (It is also a very interesting approach if you have many curve types, or use polynomial functions of possibly very high degree for your curves.) The only "trick" needed is that because some curves have loops (i.e., the coordinates are not monotonic functions), you may have to split the initial $0 le t le 1$ to smaller ranges, to ensure you find the $t$ on the curve closest to the specified point, rather than a value of $t$ that is closer than its nearby points. (It is the difference between local and global minima.)
Essentially, you pick one of the coordinate functions, a range $0 le t_{min} lt t_{max} le 1$ in which the function is monotonic (increases or decreases, but not both), and then
Function BSearch(coordfunc, target, tmin, tmax, epsilon):
Let vmin = coordfunc(tmin) - target
Let vmax = coordfunc(tmax) - target
If vmin > vmax:
Let ttmp = tmin ; tmin = tmax ; tmax = ttmp
Let vtmp = vmin ; vmin = vmax ; vmax = vtmp
End If
If vmin > 0:
Return tmin
Else If vmax < 0:
Return tmax
End If
Loop:
Let t = (tmin + tmax) / 2
If vmax - vmin <= epsilon:
Return t
End If
Let v = coordfunc(t) - target
If (v < 0) and (v >= vmin):
tmin = t
Else
If (v > 0) and (v <= vmax):
tmax = t
Else
If (v == 0):
Return t
Else:
# Function is non-monotonic.
Return Failed
End If
End Loop
End Loop
The function will return the value of t that is closest to the target coordinate, within the range specified. If it detects the function is non-monotonic, it will return Failed. Because the function is only sampled, it does not reliably detect non-monotonic functions, and can return a non-optimal t for such functions.
answered Jan 11 at 1:36
Nominal AnimalNominal Animal
7,0332517
$endgroup$
Can anyone tell if this information is sufficient to calculate the tangent vector?
No. We need to know the shape of the curve.
Knowing the curve passes via $vec{p}_s = (x_s , y_s , z_s)$ and $vec{p}_e = (x_e , y_e , z_e)$ does not tell us anything about the shape of the curve. In the simplest case, the curve would be a straight line, and in that case its tangent is everywhere the same, $vec{p}_e - vec{p}_s$.
In computer programs, cubic Bézier curves are ubiquitous. They are defined using four points. The curve passes through the first point $vec{p}_1 = (x_1 , y_1 , z_1) = vec{p}_s$ and the last point $vec{p}_4 = (x_4 , y_4 , z_4) = vec{p}_e$, but the other two just control the shape of the curve. Mathematically,
$$bbox{ begin{cases}
x(t) = (1-t)^3 x_1 + 3 (1-t)^2 t x_2 + 3 (1-t) t^2 x_3 + t^3 x_4 \
y(t) = (1-t)^3 y_1 + 3 (1-t)^2 t y_2 + 3 (1-t) t^2 y_3 + t^3 y_4 \
z(t) = (1-t)^3 z_1 + 3 (1-t)^2 t z_2 + 3 (1-t) t^2 z_3 + t^3 z_4 \
end{cases}, quad 0 le t le 1 } tag{1}label{NA1}$$
Note that that notation is just a good, easy form to express the curve. We could write the curve coordinates as third-degree polynomials,
$$bbox{ begin{cases}
x(t) = X_0 + t X_1 + t^2 X_2 + t^3 X_3 \
y(t) = Y_0 + t Y_1 + t^2 Y_2 + t^3 Y_3 \
z(t) = Z_0 + t Z_1 + t^2 Z_2 + t^3 Z_3 \
end{cases} }, quad bbox{begin{cases}
X_0 = x_1 \
X_1 = 3 x_2 - 3 x_1 \
X_2 = 3 x_3 - 6 x_2 + 3 x_1 \
X_3 = x_4 - 3 x_3 + 3 x_2 - x_1 \
end{cases} } tag{2}label{NA2}$$
but in computer programs $eqref{NA1}$ is more numerically stable.
Non-uniform rational B-splines are a more general form of curves, used especially in modeling. You can obtain the tangent vectors on NURBS using basically the same way as below; you just use the NURBS equations for the coordinates instead.
If you've ever used Inkscape to doodle shapes, you probably have used the Bézier curve tool to draw cubic Bézier curves already. Start and end points are shown as boxy dots, and those control points as "handles", a circular dot connected to the start or end point on the curve. They are used in PostScript and SVG formats as well.
The tangent vector at any point $t$ along the curve is simply the derivative of the coordinates. Using $eqref{NA2}$ above,
$$bbox{ begin{cases}
displaystyle frac{d x(t)}{d t} = X_1 + 2 X_2 t + 3 t^2 X_3 \
displaystyle frac{d y(t)}{d t} = Y_1 + 2 Y_2 t + 3 t^2 Y_3 \
displaystyle frac{d z(t)}{d t} = Z_1 + 2 Z_2 t + 3 t^2 Z_3 \
end{cases} } tag{3}label{NA3}$$
However, we can also describe the tangent in quadratic Bézier form, by deriving $eqref{NA1}$, and reordering the terms. We get
$$bbox{ begin{cases}
displaystyle frac{d x(t)}{d t} = (1-t)^2 ( 3 x_2 - 3 x_1) + 2 (1-t) t ( 3 x_3 - 3 x_2 ) + t^2 ( 3 x_4 - 3 x_3 ) \
displaystyle frac{d y(t)}{d t} = (1-t)^2 ( 3 y_2 - 3 y_1) + 2 (1-t) t ( 3 y_3 - 3 y_2 ) + t^2 ( 3 y_4 - 3 y_3 ) \
displaystyle frac{d z(t)}{d t} = (1-t)^2 ( 3 z_2 - 3 z_1) + 2 (1-t) t ( 3 z_3 - 3 z_2 ) + t^2 ( 3 z_4 - 3 z_3 ) \
end{cases} } tag{4}label{NA4}$$
This form, $eqref{NA4}$, is again numerically quite stable, and is very suitable for use in a computer program.
That leaves one more problem to solve: how to find the curve parameter $t$ that corresponds to a point I already have?
There are algebraic solutions for linear curves (lines), quadratic curves, and cubic curves. Essentially, you can pick one of the coordinate functions, say $x$, and solve
$$x(t) - x = 0$$
using any root-finding algorithm. For quadratic curves, you find up to two real $t$; for cubic, up to three real $t$. You ignore non-real roots and $t lt 0$ and $t gt 0$, and check the candidates left if $y(t) = y$ and $z(t) = z$ at sufficient precision.
In computer programs, you always do such tests as $lvert y(t) - y rvert le epsilon$ and $lvert z(t) - z rvert le epsilon$, where $epsilon$ represents the precision in your coordinates: the largest difference in coordinates that you consider neglible. For example, if you read your point cloud coordinates with three decimals, use $epsilon = 0.0005$.
If your computer program already implements a fast curve point evaluation function (the simple form is fast enough!), a binary search in $t$ may prove faster. (It is also a very interesting approach if you have many curve types, or use polynomial functions of possibly very high degree for your curves.) The only "trick" needed is that because some curves have loops (i.e., the coordinates are not monotonic functions), you may have to split the initial $0 le t le 1$ to smaller ranges, to ensure you find the $t$ on the curve closest to the specified point, rather than a value of $t$ that is closer than its nearby points. (It is the difference between local and global minima.)
Essentially, you pick one of the coordinate functions, a range $0 le t_{min} lt t_{max} le 1$ in which the function is monotonic (increases or decreases, but not both), and then
Function BSearch(coordfunc, target, tmin, tmax, epsilon):
Let vmin = coordfunc(tmin) - target
Let vmax = coordfunc(tmax) - target
If vmin > vmax:
Let ttmp = tmin ; tmin = tmax ; tmax = ttmp
Let vtmp = vmin ; vmin = vmax ; vmax = vtmp
End If
If vmin > 0:
Return tmin
Else If vmax < 0:
Return tmax
End If
Loop:
Let t = (tmin + tmax) / 2
If vmax - vmin <= epsilon:
Return t
End If
Let v = coordfunc(t) - target
If (v < 0) and (v >= vmin):
tmin = t
Else
If (v > 0) and (v <= vmax):
tmax = t
Else
If (v == 0):
Return t
Else:
# Function is non-monotonic.
Return Failed
End If
End Loop
End Loop
The function will return the value of t that is closest to the target coordinate, within the range specified. If it detects the function is non-monotonic, it will return Failed. Because the function is only sampled, it does not reliably detect non-monotonic functions, and can return a non-optimal t for such functions.
answered Jan 11 at 1:36
Nominal AnimalNominal Animal
7,0332517
answered Jan 11 at 1:36
Nominal AnimalNominal Animal
7,0332517
answered Jan 11 at 1:36
Nominal AnimalNominal Animal
7,0332517
answered Jan 11 at 1:36
Nominal AnimalNominal Animal
7,0332517
7,0332517
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3068714%2ftangent-line-to-a-3d-curve-at-a-given-3d-point%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
You need some equation or description of the curve. There are a lot of them that go through three points in space.
$endgroup$
– amd
Jan 10 at 20:47