Continuous collision detection for elliptic disks

ContinuousCollisionDetectionforEllipticDisksYi-KingChoi,WenpingWang,YangLiu∗DepartmentofComputerScience,TheUniversityofHongKong,HongKongMyung-SooKimDepartmentofComputerEng.,SeoulNationalUniversity,Seoul,SouthKoreaAbstractCollisiondetectionandavoidanceisimportantforvarioustasksinrobotics.Com-paredwithcommonlyusedcirculardisks,ellipticdisksprovidecompactshaperepre-sentationforrobotsorothervehiclesconfinedtomoveinthe2Dplane.Furthermore,ellipticdisksallowsimpleranalyticrepresentationthanrectangularboxesdo;thismakesiteasiertoperformcontinuouscollisiondetection.Weshallpresentafastandaccuratemethodforcontinuouscollisiondetectionbetweentwomovingellipticdisks;continuouscollisiondetectiondoesnotneedtosamplethetimedomainofmotion,thusavoidingmissingpossiblecollisionbetweentimesamples.Basedonsomenewalgebraicconditionsontheseparationoftwoellipses,wereducecollisiondetectionfortwomovingellipsestotheproblemofdetectingrealrootsofaunivariateequa-tionwhichisthediscriminantofthecharacteristicpolynomialofthetwoellipses.Varioustechniquesareinvestigatedindetailforrobustandaccurateprocessingofthisunivariateequationfortwoclassesofcommonlyusedmotions:(1)planarscrewmotions;and(2)planarrationalmotions,i.e.motionsthatcanberepresentedasrationalfunctionsofthetimeparametert.Experimentalresultsarepresentedtodemonstratetheefficiency,accuracyandrobustnessofourmethod.Keywords—ellipses,ellipticdisks,rationalmotion,collisiondetection,interferenceanalysis1IntroductionCollisiondetectionisimportantinroboticsforpathplanningorsimulation.Avoidanceofcollisionbetweenmovingobjectsisgreatlyfacilitatedbyaccuratecollisiondetection∗ThisworkwassupportedbytheResearchGrantCouncilofHongKong.1algorithms.Inapplicationswherereal-timeresponseismandatory,theefficiencyofcolli-siondetectionalgorithmsisalsoofhighimportance.Althoughmanycollisiondetectionalgorithmsarecateredfor3Dapplications[12],therearestillnumerousotherapplicationsinwhichmovingobjectsareconfinedtobeinthe2Dplane.Someexamplesarefromrobotorvehiclepathplanningwheretherobotsandvehiclesrepresentedby2Dfiguresmoveinthe2Dplane,andtherobotmovementsmayfollowanypathswitharbitraryrotations.Whentherearemorethanonerobotmovinginthesamespace,collisiondetectionbetweentheserobotsbecomescritical.Apartfromequippingtherobotswithsensorsforonlinecol-lisionavoidance,itisoftenalsonecessarytohavetherobotpathsplannedandverifiedinadvance.Eveninthe2Dsetting,theoutlineofanobjectcanbequitecomplex.Inthiscaseatwo-phaseapproachtocollisiondetectioniswidelyadoptedinpractice.Tofacilitatethecollisiondetectionprocess,objectsareoftenenclosedbysimplegeometricentities,whichweshallcallenclosingobjects(alsocalledboundingobjectsintheliterature),sothatsimplercollisiondetectioncanfirstbeperformedontheseenclosingobjects;morecomplicatedcomputationoncollisiondetectionfortheoriginalobjectswillonlybecarriedoutaftertheirenclosingobjectshavebeendetectedtobeoverlapping.Thecommonlyusedenclosingobjectsincludecirculardisksandrectangles.Thereare,ingeneral,twocriteriainchoosingthetypeofenclosingobjectstobeusedinaparticularapplication.Thefirstisaboutboundingtightness;thatis,enclosingobjectsshouldbeastightaspossiblesothatwhentwoenclosedobjectsareseparate,theirenclosingobjectsshouldbeseparatemostofthetime.Thiscriterionservestosavetimebyensuringthatmanynon-collidingpairsarenotsubjecttofurtherprocessingoncetheirenclosingobjectsarefoundtobeseparate.Thesecondcriterionisthatthecollisiondetectionforapairofenclosingobjectsshouldbesimpleandveryfast,sincethisoperationnormallyneedstobedonemanytimes,i.e.foreverypairofobjectspresentinanenvironment.Thus,basedontheseconsiderations,itisnothardtounderstandwhycirculardiscs(andspheresin3Dcaseforthismatter)arecommonlyusedasboundingobjectsofrobotsintheplane(e.g.[17]);collisiondetectionforapairofcirclesisalmosttrivial,thereforecanbeperformedveryefficiently.Interferencetestingofcirculardiscshasalsowellbeenstudiedincomputationalgeometry[18,23,24].Ellipsesprovideamuchtighterboundingvolumethancircles.Whenaunionofellipsesorcirclesareused,normallyfarfewerellipsesareneededthancirclestoencloseagivenobjectwiththesamedegreeoftightness.Thereforetheuseofellipsesasenclosingobjectscanpotentiallyleadtosignificantimprovementofaccuracyandefficiencyincollisionde-tection.However,littleworkcanbefoundintheliteratureonusingellipsesasenclosingobjects,largelybecauseofthelackofeffectivemeansofdetectingcollisionforellipses.Overall,thereareseveralmajorissuesinusingellipsesasenclosingobjects;theseincludecomputingthesmallestenclosingellipseofagivenobject,detectingcollisionoftwomovingellipses,andcomputingthepenetrationdistanceoftwooverlappingellipses,etc.Inthispaperweshallfocusoncollisiondetectionoftwoellipticdiskswithpre-specifiedcontinuousmotion.(Weshallsometimesusethetermsellipseandellipticdiskinterchangeably,whenthereisnodangerofconfusion.Strictlyspeaking,anellipticdiskcomprisestheboundary2pointsandinteriorpointsofanellipse.)Thoroughanalysisandclassificationofintersectionofgeneralconicscanbefoundinclassicalalgebraicgeometry,e.g.[1,2].Theseresultsare,however,forconicsinthecomplex(