Robust and Efficient Computation of the Clost Point on a Spline Curve Hongling Wang,Joph Kearney,and Kendall Atkinson
Abstract.Parametric cubic spline curves are commonly ud to
model the geometry of road surfaces in real-time driving simulators.
Roads are reprented by space curves that define a curvilinear frame
of reference in which three-dimensional points are expresd in coordi-
nates of distance along the curve,offt from the central axis,and loft
from the road surface.Simulators must map from global Cartesian
coordinates to local road coordinates at very high frequencies.A key
component in this mapping is the computation of the clost point on
the central axis of the road to a three-dimensional point expresd in
Cartesian coordinates.The paper investigates a two-step method that
如何拦截骚扰电话exploits the complementary strengths of two optimization techniques:
Newton’s method and quadratic minimization.
§1.Introduction
Parametric cubic spline curves provide a natural basis for modeling the geometry of road surfaces in real-time driving simulators.The road model is ud by programs that control the behavior of autonomous vehicles and pedestrians populating the virtual urban environment.In many simula-tors,roads are reprented by space curves that define a central axis or spine of a ribbon-like surface[6].A surface normal is defined at each point on the curve allowing the ribbon to twist about its spine.The rib-bon establishes a curvilinear coordinate system in which points in space are expresd in coordinates of distance along the central axis,offt from the axis,and loft from the road surface.The ribbon structure provides a natural coordinate frame for computing the local geometry of navigable surfaces.This geometry is important for wayfinding of autonomous agents and also determines the spatial relationships among agents.
Curve and Surface Design:Saint-Malo2002397 Tom Lyche,Marie-Laurence Mazure,and Larry L.Schumaker(eds.),pp.397–405. Copyright o c2003by Nashboro Press,Brentwood,TN.
遏制是什么意思
ISBN0-9728482-0-7.
All rights of reproduction in any form rerved.
398H.Wang,J.Kearney,and K.Atkinson While some simulation computations are most effectively implement-
ed using ribbon coordinates,other computations are most effectively im-plemented using Cartesian coordinates.For example,behavior modules
that track roads and avoid obstacles,are most easily expresd with ob-
ject locations reprented in ribbon coordinates.However,the dynamics code that computes object motions from control parameters t by object
behaviors is most simply written in Cartesian coordinates.Becau the computations are performed at very high frequency,it is esntial to have
efficient and robust code to map from ribbon coordinates to Cartesian co-
事业单位退休年龄
ordinates and to compute the inver mapping from Cartesian coordinates to local ribbon coordinates.
The mapping from Cartesian to ribbon coordinates is frequently a -
rious computational bottleneck in driving simulators.The key component in this mapping is the computation of the clost point on the central axis
of the ribbon to a three-dimensional point expresd in Cartesian coor-dinates.Conventional optimization techniques such as Newton’s method
or quadratic minimization work well most of the time.However,we’ve
found that the standard techniques consistently fail(converge very slowly or diverge)at a small number of points on many ordinary curves.Becau
of the frequency with which the mappings are housands
of times a cond for a modestly complex simulation)even the rare problematic instances are likely to occur with regularity.This leads to
unacceptable computational delays and can halt a simulation if the opti-mization procedure is not terminated.
To address weakness with standard optimization techniques,we植物生长变化
prent a two stage technique that combines quadratic minimization and Newton’s method.
§2.The Problem
A parametric cubic spline curve modeling the centerline of a curved road
can be expresd as[5],
糖尿病人能喝牛奶吗(x(s),y(s),z(s)),0≤s≤L,
where s denotes arc length,L is the arc length of the entire spline curve,
and x(s),y(s),and z(s)are cubic spline functions with equally spaced
breakpoints{s0,s1,...,s n}with s0=0and s n=L.The functions x,y, and z are C2on[0,L].
At each time step of a simulation,the dynamics module computes a new position in Cartesian coordinates for every moving object.Given an object’s location in Cartesian coordinates,our problem is tofind the clost point on a road centerline to the object.
Let p0=(x0,y0,z0)be the position of an object(e Figure1).The
square of the distance between position p0and position(x(s),y(s),z(s))
Clost Point on a Spline399
Fig.1.Vector p1p0and the tangent vector of a cubic spline curve on p1.
on a spline curve is
D(s)=(x(s)−x0)2+(y(s)−y0)2+(z(s)−z0)2,(1) where x(s),y(s),and z(s)are cubic spline functions of the parameter s. The value s∗that minimizes D(s)determines p1=(x(s∗),y(s∗),z(s∗)),
p1p0is the clost point to p0on the cubic spline curve.The vector−−→perpendicular to the tangent vector of the cubic spline curve on p1.The distance between p0and p1,which is the length of the vector−−→
神马电源p1p0,is the smallest distance between the position p0and the cubic spline curve.
We approach the mapping computation as an optimization problem. To meet the stringent demands of real-time simulation,it is important that the lected optimization method converges to an accurate solution very quickly.While the average speed of this computation matters,it is of paramount importance that the maximum time does not overrun the time allotted for a simulation step by the scheduler.Thus,the demands of the application call for a method that is accurate,fast,and almost never fails. With the requirements in mind,we examine three optimization tech-niques:Newton’s method,quadratic minimization,and a new technique that combines quadratic minimization and Newton’s method.
§2.Quadratic Minimization Method
Quadratic minimization us quadratic interpolation to minimize a one-variable function,in our ca D(s).Suppo that˜s1,˜s2,and˜s3are given as initial estimates of s∗,the value that optimizes D(s).The quadratic
400H.Wang,J.Kearney,and K.Atkinson polynomial that interpolates D(s)at˜s1,˜s2,and˜s3is given by,
P(s)=
(s−˜s2)(s−˜s3)
(˜s1−˜s2)(˜s1−˜s3)
D(˜s1)
+
(s−˜s1)(s−˜s3)
(˜s2−˜s1)(˜s2−˜s3)
D(˜s2)
+
(s−˜s1)(s−˜s2)
口语
(˜s3−˜s1)(˜s3−˜s2)
D(˜s3).
The minimum of P(s)is ud to approximate the minimum of D(s).The minimum of P(s)is given by
s∗,k=1
2
·y23D(˜s1)+y31D(˜s2)+y12D(˜s3)
s23D(˜s1)+s31D(˜s2)+s12D(˜s3)
,k=1,2,3,···,(2)
where s ij=˜s i−˜s j and y ij=˜s2i−˜s2j for i,j∈{1,2,3}.We pick three values from˜s1,˜s2,˜s3,and s∗,k by eliminating the value which gives the largest P(s)among the4values,and continue in a like manner until some error tolerance for P(s)is achieved.It can be shown that with a sufficiently good t of initial guess,the iteration will converge at a superlinear rate to s∗[3,4].
Quadratic minimization needs three initial estimates of s∗.In our application,we usually have a good guess of which gment,[s i,s i+1], contains s∗bad on the simulation state at the previous time step.An object typically enters a road at one end or the thefirst or last gment.)As the object moves along a road,we track its position and velocity.Knowing s∗at the previous step and the object’s velocity, we can predict the value of s∗at the current step.
Becau the spline gments are all of equal length,we can calculate the index,i,of the gment containing the initial estimate,美的结构
i= s∗,0
l
,(3)
where l is the arc length of each gment of the spline curve.We u as
our three initial estimates of s∗the values s i,s i+s i+1
2,and s i+1.
When s∗lies near a gment boundary,error in the initial estimate may cau us to choo the wrong gment.This is detected when the iteration converges to a value outside the gment boundaries[s i,s i+1]. In this ca,we attempt to solve s∗on adjacent gments.
Sometimes we are unable to predict s∗from previous states(for ex-ample,when an object moves from offroad terrain to a road.)When we are unable to compute a good initial estimate,we attempt to solve for s∗on each successive gment of the curve.
Clost Point on a Spline401
Fig.2.Distance curve between p0and points on the spline gment in Figure1.
The road curves we ek to model are typically smooth and have low curvature relative to their width.The width of a road surface must be less than the radius of curvature of the road axis spline to prevent lf interctions.As a conquence,there is a single nearest point on the spline for all points on the surface of a road.Thus,the mapping from Cartesian coordinates to ribbon coordinates is unique.
We expect quadratic minimization method to work well for our prob-lem becau the minimum distance between a point p0on the surface of the road and the spine of the road is normally well-approximated by a parabola.For example,Figure2graphs the minimum distance from a point p0to a spline gment.
We tested the quadratic minimization method on a variety of cubic spline curves reprentative of road curves ud in driving simulation.For each curve,we randomly generated a cloud of points near the curve and computed,for each of the points,the clost point on the curve.Ex-perimental results showed that quadratic minimization converged to an accurate solution in fewer than8iterations for about one third of the test points.In the remaining cas,a solution was usually found although it som
etimes took hundreds of iterations to converge.In a small percentage of cas the method diverged and no solution was found.Clor exam-ination of cas in which the method diverged or converged very slowly revealed that the early iterations made progress toward a solution,but as the optimal value was approached it jumped about in a small interval surrounding the optimum.
§3.Newton’s Method
The value s∗that minimizes D(s)in formula(1)satisfies D (s∗)=0.We can u Newton’s method tofind a root of this equation.This leads to
