[et_pb_section fb_built=”1″ _builder_version=”3.22.7″][et_pb_row _builder_version=”3.22.7″][et_pb_column type=”4_4″ _builder_version=”3.22.7″][et_pb_text _builder_version=”3.22.7″]<\/p>\n
Plane-Curve intersection from algebraic point of view is quiet similar to Plane-Line intersection<\/strong><\/a> which we discussed in previous post. In this post I would like to take the same approach in finding the Plane-Curve intersection which involves root finding techniques, and in the next post we will also look at Face-Curve intersection<\/strong> method and we will use to implement a method for Plane-Curve intersection. If you are looking for a robust and fast solution , then feel free to jump to my next post . If by any chance you are interested in differential geometry and mathematics like me \ud83d\ude09 then please continue reading… <\/p>\n Let’s have a look again at the plane and curve parameterization: <\/span><\/p>\n [\/et_pb_text][et_pb_image src=”https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/03\/image001-2.png” align=”center” _builder_version=”3.22.7″ width=”83%”][\/et_pb_image][et_pb_text _builder_version=”3.22.7″]<\/p>\n Equation (1)<\/strong><\/em> represent a plane with normal vector n which passes through point p\u2080<\/strong><\/em> and Equation (2)<\/strong><\/em> is the parametric formulation of curve C<\/strong><\/em> with parameter t<\/strong><\/em>. C<\/strong><\/em> is a function which maps a real number to a position vector in 3d space. In this form t<\/em> <\/strong>is called natural parameter of curve C<\/em><\/strong>. P<\/strong> <\/em>represents the point on plane and the point on the curve in both equations, just like the Plane-Line intersection we replace the point p<\/strong><\/em> in equation (1)<\/strong><\/em> by its value from equation (2)<\/strong><\/em> and we solve the new equation for t<\/strong><\/em>. <\/p>\n [\/et_pb_text][et_pb_image src=”https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/03\/image003-2.png” align=”center” _builder_version=”3.22.7″ width=”40%”][\/et_pb_image][et_pb_text _builder_version=”3.22.7″]<\/p>\n In order to solve above equation we need to know about the function C<\/strong><\/em> in Revit API. There are two methods which can be used to evaluate the curve with given natural or normal parameter which are listed below <\/p>\n [\/et_pb_text][et_pb_text _builder_version=”3.22.7″ background_color=”#f2f2f2″ border_width_all=”1px” border_color_all=”#d3d3d3″ custom_margin=”-2px|||||” custom_padding=”11px|15px|0px|15px|false|true” saved_tabs=”all”]<\/p>\n [\/et_pb_text][et_pb_text _builder_version=”3.22.7″]<\/p>\n The first method simply evaluate the curve at given parameter and return the point on the curve. The second method is far more better, since it returns the potion of the point along with its derivatives which are useful in root finding technique which we will discuss later. Please read documentation for The equation (3)<\/strong><\/em> has one unknown (t)<\/strong><\/em> and if the curve is smooth and differentiable then the equation is also differentiable which means we can use newton method<\/a> for root finding . Although there are several roof finding algorithms<\/a> which can be used in this case, but I have selected the newton method as it is easy to implement and has quadratic convergence rate. As I mentioned above you may not use this algorithm for your code where the Plane-Curve intersection is used expensively and instead, please refer my next post on this topic. <\/p>\n The newton method requires to have the first derivative of equation (3)<\/strong><\/em> with respect to the unknown (t)<\/strong><\/em>. Here we shall write: <\/p>\n <\/p>\n [\/et_pb_text][et_pb_image src=”https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/03\/image005-2.png” align=”center” _builder_version=”3.22.7″ width=”40%”][\/et_pb_image][et_pb_text _builder_version=”3.22.7″]<\/p>\n Expanding above we get : <\/p>\n [\/et_pb_text][et_pb_image src=”https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/03\/image007-1.png” align=”center” _builder_version=”3.22.7″ width=”40%”][\/et_pb_image][et_pb_text _builder_version=”3.22.7″]<\/p>\n The second part is constant with respect to the t<\/em><\/strong> , therefore it is eliminated<\/p>\n [\/et_pb_text][et_pb_image src=”https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/03\/image009-1.png” align=”center” _builder_version=”3.22.7″ width=”40%”][\/et_pb_image][et_pb_text _builder_version=”3.22.7″]<\/p>\n Expanding the (4-2)<\/strong><\/em> using the derivative of the dot-product<\/a> we obtain: <\/p>\n [\/et_pb_text][et_pb_image src=”https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/03\/image009-2.png” align=”center” _builder_version=”3.22.7″ width=”60%”][\/et_pb_image][et_pb_text _builder_version=”3.22.7″]<\/p>\n Again the right expression is constant with respect to the (t) therefore we can eliminate and write :<\/p>\n [\/et_pb_text][et_pb_image src=”https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/03\/image011-1.png” align=”center” _builder_version=”3.22.7″ width=”40%”][\/et_pb_image][et_pb_text _builder_version=”3.22.7″]<\/p>\n In equation (4-3)<\/em><\/strong> we only need to the derivative of the function C<\/strong><\/em> with respect to the parameter t<\/strong><\/em> and then compute the dot product of it with plane normal. As already mentioned above the [\/et_pb_text][et_pb_text _builder_version=”3.22.7″ background_color=”#f2f2f2″ border_width_all=”1px” border_color_all=”#d3d3d3″ custom_margin=”-2px|||||” custom_padding=”11px|15px|0px|15px|false|true” saved_tabs=”all”]<\/p>\n [\/et_pb_text][et_pb_text _builder_version=”3.22.7″ custom_margin=”||2px|||”]<\/p>\n I’m not going to discuss the newton method<\/a> in full detail , The most basic version starts with a single-variable function f<\/i><\/span><\/strong><\/span> defined for a <\/span>real variable<\/a> <\/span>x<\/i><\/span><\/strong>, the function’s <\/span>derivative<\/a> <\/span>f\u2009<\/strong>\u2032<\/i><\/span>, and an initial guess <\/span>x<\/i><\/span>\u2080<\/span><\/em><\/strong> for a <\/span>root<\/a> of <\/span>f<\/i><\/span><\/strong>. If the function satisfies sufficient assumptions and the initial guess is close, then:<\/span><\/p>\n [\/et_pb_text][et_pb_image src=”https:\/\/www.parametriczoo.com\/wp-content\/uploads\/2020\/03\/image002.png” align=”center” _builder_version=”3.22.7″ width=”28%”][\/et_pb_image][et_pb_text _builder_version=”3.22.7″ custom_margin=”-4px|||||”]<\/p>\n The algorithm is pretty simple, we start with initial guess t<\/strong> <\/em>and in each iteration we compute the step size dx =<\/strong><\/em> -f(t)\/f'(t) . <\/strong><\/em>The <\/strong><\/em>parameter <\/strong>t <\/strong><\/em>is moved to the new position and the function f <\/strong><\/em>is evaluated again. This loop continues till either the value of function f <\/strong><\/em>is close to zero or the number of iteration exceeds a maximum value (here 100 iterations) . Below shows the implementation assuming the interval [t\u2081<\/span>,t\u2082<\/span>]<\/strong> <\/em>is the curve domain. <\/span><\/p>\n [\/et_pb_text][et_pb_text _builder_version=”3.22.7″ background_color=”#f2f2f2″ border_width_all=”1px” border_color_all=”#d3d3d3″ custom_margin=”-2px|||||” custom_padding=”11px|15px|0px|15px|false|true” saved_tabs=”all”]<\/p>\npublic<\/span> XYZ<\/a> Evaluate<\/span>(\n\tdouble<\/a> parameter<\/span>,\n\tbool<\/a> normalized<\/span>\n)\n<\/code><\/pre>\npublic<\/span> Transform<\/a> ComputeDerivatives<\/span>(\n\tdouble<\/a> parameter<\/span>,\n\tbool<\/a> normalized<\/span>\n)<\/code><\/pre>\nComputeDerivatives()<\/a> <\/span><\/code>as I’m not going to cover all details here.<\/p>\nComputeDerivatives()<\/a><\/span><\/code>method returns the first derivative of the function C<\/strong><\/em> in the BasisX vector of the resulted transformation matrix. This derivative can be also interpreted as the tangent vector<\/a> to the curve at parameter t<\/strong><\/em>. Now we have both requirements for Newton method, first the evaluation of the equation (3)<\/em><\/strong> which we call it function f(t)<\/em><\/strong> from now on and the first derivative of the function f<\/strong> <\/em>at parameter t <\/em><\/strong>which is written as df <\/em><\/strong>: <\/span><\/p>\n\/\/ compute C(t) and C'(t) <\/span>\ntr<\/span> =<\/span> cc<\/span>.<\/span>ComputeDerivatives<\/span>(<\/span>t<\/span>,<\/span> false<\/span>);<\/span>\n\/\/compute the objective function f(t)<\/span>\nf<\/span> =<\/span> (<\/span>tr<\/span>.<\/span>Origin<\/span> -<\/span> q<\/span>.<\/span>Origin<\/span>)<\/span>.<\/span>DotProduct<\/span>(<\/span>q<\/span>.<\/span>Normal<\/span>);<\/span>\n\/\/ compute the derivative of function f(t)<\/span>\ndf<\/span> =<\/span> tr<\/span>.<\/span>BasisX<\/span>.<\/span>DotProduct<\/span>(<\/span>q<\/span>.<\/span>Normal<\/span>);<\/span><\/pre>\n\/\/Newton method for finding the root of the function f(t)<\/span>\ndouble<\/span> f<\/span>;<\/span>\/\/ the value of the function in each iteration <\/span>\ndouble<\/span> df<\/span>;<\/span> \/\/ the first derivative of the function f at each iteration<\/span>\ndouble<\/span> dx<\/span> =<\/span> 0<\/span>;<\/span> \/\/ step size (delta x)<\/span>\nint<\/span> I<\/span> =<\/span> 0<\/span>;<\/span> \/\/ number of iterations <\/span>\nTransform<\/span> tr<\/span>;<\/span>\/\/= Transform.Identity;<\/span>\n \ndo<\/span>\n{<\/span>\n t<\/span> +=<\/span> dx<\/span>;<\/span> \/\/ move t to the new position <\/span>\n \/\/ ensure the parameter is within the limits<\/span>\n if<\/span> (<\/span>t<\/span> <<\/span> t1<\/span>)<\/span> \n {<\/span>\n t<\/span> =<\/span> t1<\/span>;<\/span> \n }<\/span>\n if<\/span> (<\/span>t<\/span> ><\/span> t2<\/span>)<\/span>\n {<\/span>\n t<\/span> =<\/span> t2<\/span>