Topological TerrainMap Resolution:Intervisibility,Crest,andMilitaryCrestDonaldR.Barr,BardMansager,WilliamP.Fox,ThomasRiddleIntroductionThedepictionofterrain in computerized combatsimulationmodelsgenerallytakestheformofadiscreteapproximation.Themodeledterrain surfaceisoftenrepresentedbyastepfunctionoveratwo-dimensional domaincoveredbyatessellation of squares or hexagons.Militaryfield testing applications use suchdigitizedterrain maps in connection withtargettracking enhancements.Suchuses include improvements in accuracy of tracking in the elevation dimension("z-axis")using Global Positioning System(GPS--satellite)information.Digitalmaps areused inmany modeling applications in connection with computerdisplays ofunitson orabovetheterrain.In the case where the domain of theapproximating terrain surface is covered bysquares, itis commonto designate theterrain resolution in terms of the lengthofa side of such a square.Thus,"100-meterterrain",refers to anapproximatingfunctionwithdomainpartitioned intosquares100meters ona side.Astheresolution isincreased(25-meterand3-meterterraindatabasesarecommon)the size of the terraindata base increases exponentially.This drives up the costofdevelopmentof thedatabasefor agiven sizearea,as well asthe costofstoring the database and using it ina modeling application.An important determinantof interactionofopposing combatforces istheirintervisibility.Intervisibilitycalculationsmadebetweentwopoints onthegroundusingagivendigital terraindatabasecanprovideapproximations of howmuchofagivenunit(suchasanAbramstankoraninfantrysquad)locatedatonepoint is exposed to visual contact by an opposing unit an another point. Suchcalculationsarecomputationally expensive,generally involving algorithmsthatstepalongavector (ray)betweenthepoints,lookingforinterveningterrainwhichwouldinterruptstraightline-of-sight(LOS)betweenthepoints.Thecostofcomputing intervisibilitybetweenmanypairsof opposingunits,astheunits moveacross theterrain at time intervals,increases rapidly as theterrainresolution isincreased.Thequestiontobeconsideredforacombatmodeleris."Howmuchterrainresolution is enough?"Somecombatmodelers insistthatthere canneverbetoomuchresolution.Othermodelersbelievethatthereisa pointofdiminishingreturns.The answer probably lies in the modeling application.Fordriving'Department of Systems Engineering (USMA)2Department of Mathematics, Naval Postgraduate School, Monterey, CA195
195 Topological Terrain Map Resolution: Intervisibility, Crest, and Military Crest Donald R. Barr1 , Bard Mansager2 , William P. Fox, Thomas Riddle Introduction The depiction of terrain in computerized combat simulation models generally takes the form of a discrete approximation. The modeled terrain surface is often represented by a step function over a two-dimensional domain covered by a tessellation of squares or hexagons. Military field testing applications use such digitized terrain maps in connection with target tracking enhancements. Such uses include improvements in accuracy of tracking in the elevation dimension (“z-axis”) using Global Positioning System (GPS-satellite) information. Digital maps are used in many modeling applications in connection with computer displays of units on or above the terrain. In the case where the domain of the approximating terrain surface is covered by squares, it is common to designate the terrain resolution in terms of the length of a side of such a square. Thus, “100-meter terrain”, refers to an approximating function with domain partitioned into squares 100 meters on a side. As the resolution is increased (25-meter and 3-meter terrain data bases are common), the size of the terrain data base increases exponentially. This drives up the cost of development of the database for a given size area, as well as the cost of storing the database and using it in a modeling application. An important determinant of interaction of opposing combat forces is their intervisibility. Intervisibility calculations made between two points on the ground using a given digital terrain database can provide approximations of how much of a given unit (such as an Abrams tank or an infantry squad) located at one point is exposed to visual contact by an opposing unit an another point. Such calculations are computationally expensive, generally involving algorithms that step along a vector (ray) between the points, looking for intervening terrain which would interrupt straight line-of-sight (LOS) between the points. The cost of computing intervisibility between many pairs of opposing units, as the units move across the terrain at time intervals, increases rapidly as the terrain resolution is increased. The question to be considered for a combat modeler is, “How much terrain resolution is enough?” Some combat modelers insist that there can never be too much resolution. Other modelers believe that there is a point of diminishing returns. The answer probably lies in the modeling application. For driving 1 Department of Systems Engineering (USMA) 2 Department of Mathematics, Naval Postgraduate School, Monterey, CA
detailed realisticvisual depictions of movingunits onactual terrain onacomputerdisplay,greaterresolutionmaybenecessary.Forcombatmodelsrequiringtargetdetectionandengagements ina computersimulation,theremaybeonlymarginal valueinterrainresolutionbeyondsomeminimumthresholdvalue.Weconcentrateontheissueoftheaccuracyofintervisibilityapproximationsasafunctionofterrainresolution.ManymodelingstudiesfortheArmyhavebeendonetoattempttocharacterizethisresolutionissueforcombatmodelingingeneral. This is an attempt to better characterize the issue in regards tointervisibility onthe simulated battlefield.We alsoprovideexamplesthat relateback to military doctrine and tactics to motivate the user of this module.IntervisibilityOnTwo Dimensional TerrainWe begin by imagining a creature living on a two dimensional (x and z) terrainrepresented by the Cartesian graph of a function f over a domain D consisting ofa bounded interval of real numbers. At each point x in D, define the"intervisibility", I(x), to be the total length of the arc segments consisting of thepoints (z, f(z)) for z in D that are visible from the point (x, f(x). A point (z, f(z) isintervisible with (x, f(x) if there is no point (v, f(v) such that vis between x and zandf(v)isgreaterthantheheightoftheline segment connectingthetwogivenpoints at v.That is, for all v between x and z.f(v) ≤ f(x) + (f(x)-f(z)(v-x) / (x-z)Ina computermodelingalgorithmthis conditionis checked by comparingthethreeslopesbetweenpairsofpointsselectedfromthetwogivenpointsandthetest point (v, f(v).Aplot ofpoints (x, I(x)),which we call the“intervisibility curve"provides globalinformation aboutthe intervisibility characteristics oftheterrainf.For example,considertheterrainofaflatplainoverafiniteregionwithav-shapedvalleyrunningthroughit.Theinter-visibilitycurveofthecross-sectionalnormaltotheaxis of the valleyis shown inFigure 1.Then I(x) (seeFigure1)will bea stepfunction: for all x-values under the flat plain, I(x) will be the length of the arcassociatedwiththeplain.All pointsontheplainarevisiblefrompointsontheplain,andnopointsinthevalleycanbeseenfrominteriorpointsontheplain.Attheedgeof the valley,I(x) jumps to include arclengths of the valley since wecan now see into the valley from the edge. At points within the valley I (x)becomes a constant value.This shows I (x)mayhave points ofdiscontinuities(pointswherethederivativedoesnotexist)196
196 detailed realistic visual depictions of moving units on actual terrain on a computer display, greater resolution may be necessary. For combat models requiring target detection and engagements in a computer simulation, there may be only marginal value in terrain resolution beyond some minimum threshold value. We concentrate on the issue of the accuracy of intervisibility approximations as a function of terrain resolution. Many modeling studies for the Army have been done to attempt to characterize this resolution issue for combat modeling in general. This is an attempt to better characterize the issue in regards to intervisibility on the simulated battlefield. We also provide examples that relate back to military doctrine and tactics to motivate the user of this module. Intervisibility On Two Dimensional Terrain We begin by imagining a creature living on a two dimensional (x and z) terrain represented by the Cartesian graph of a function f over a domain D consisting of a bounded interval of real numbers. At each point x in D, define the “intervisibility”, I(x), to be the total length of the arc segments consisting of the points (z, f(z)) for z in D that are visible from the point (x, f(x)). A point (z, f(z)) is intervisible with (x, f(x)) if there is no point (v, f(v)) such that v is between x and z and f(v) is greater than the height of the line segment connecting the two given points at v. That is, for all v between x and z. f(v) < f(x) + (f(x)-f(z))(v-x) / (x-z). In a computer modeling algorithm this condition is checked by comparing the three slopes between pairs of points selected from the two given points and the test point (v, f(v)). A plot of points (x, I(x)), which we call the “intervisibility curve” provides global information about the intervisibility characteristics of the terrain f. For example, consider the terrain of a flat plain over a finite region with a v-shaped valley running through it. The inter-visibility curve of the cross-sectional normal to the axis of the valley is shown in Figure 1. Then I(x) (see Figure 1) will be a step function: for all x-values under the flat plain, I(x) will be the length of the arc associated with the plain. All points on the plain are visible from points on the plain, and no points in the valley can be seen from interior points on the plain. At the edge of the valley, I(x) jumps to include arc lengths of the valley since we can now see into the valley from the edge. At points within the valley I (x) becomes a constant value. This shows I (x) may have points of discontinuities (points where the derivative does not exist)
IntervisibilityforSimpleTerrain1.36089,5arg000.50L0.山ypyFigure1.Simpleterrainmodel (Cross-sectionofaplainwithavalley;showinbottomcurve)andcorrespondingintervisibilitycurve(topcurve).Asasecondexample,considerthefunctionf(x)=|cos(元x)overthedomainD=[0,1]. Then I (x) starts at zero at the lower end point, increases to a maximumnearx=1/3,thendropsrapidlytozeroatx=1/2(seeFigure2).Symmetryoff(x) about x=1/2 implies corresponding symmetry of 1.Over [0, 1/2], this is anexampleofwhattheArmyFieldManual21-26calls“convexterrain."Notealsothat themaximum intervisibilityoccurs well down the slopefrom the crest ofthehill at x = 0.AbsoluteCosineTerrainIntervisibilityCurve1.10584,17arg0.5=11,6.12303e-017,00.20.40.60.8.0.tlypyiFigure2.Intervisibilitymodel (dotted curve)foroneperiod oftheabsolutecosineterrain(solidcurve).Notethemaximumintervisibilityoccursatx=1/3197
197 Intervisibility for Simple Terrain 0 0.5 1 0 1 2 1.36089 0 F i arci 0 y , 1 i y i Figure 1. Simple terrain model (Cross-section of a plain with a valley; show in bottom curve) and corresponding intervisibility curve (top curve). As a second example, consider the function f(x) = |cos(p x)| over the domain D = [0,1]. Then I (x) starts at zero at the lower end point, increases to a maximum near x = 1/3, then drops rapidly to zero at x = 1/2 (see Figure 2). Symmetry of f(x) about x=1/2 implies corresponding symmetry of I. Over [0, 1/2], this is an example of what the Army Field Manual 21-26 calls “convex terrain.” Note also that the maximum intervisibility occurs well down the slope from the crest of the hill at x = 0. Absolute Cosine Terrain Intervisibility Curve 0 0.2 0.4 0.6 0.8 1 0 0.5 1 1.5 1.10584 6.12303e-017 F i arci 0 y , 1 i y i Figure 2. Intervisibility model (dotted curve) for one period of the absolute cosine terrain (solid curve). Note the maximum intervisibility occurs at x = 1/3
TerrainResolutionandComputationofI(x)Inthecase ofthistwodimensionalterrain,digitizedterraincanbecharacterizedby the height of terrain at a finite set of points Xn = (Xo, X1,.,xn), where n is ameasure of the resolution of the map.We order the x's sorted in increasing orderand assume they are equally spaced withinD.Theterrainmap supported bythedatabase,((xi,f(xi)):i=0,1,2,..,n) isapolygon formed by connecting adjoiningpoints of the form (Xi,f(x:), (Xi+1,f(xi+1): this polygon approximates the actualterrain (x,f(x)):xeD).Thedigitalterrain map approximation of intervisibility atpointx,I(x),isthenthesumofthelengthsofthepolygon segmentsvisiblefrom(x,f(x).Let'sconsider oneofourpreviousfunctions,f(x)=Jcos(元x)/over thedomainD=[0,1],over twoperiods.Theapproximating intervisibilitycurves for n=20,50,and 400 are shown inFigures 3 through5.The most accurate approximatingintervisibility curvemodel is shown inFigure5.Wenote the n=10 isa crudeapproximation.Tryingvaluesof n>100didnot significantly improvetheresolution.Thus,wemight conclude the resolution beyondn=1oo is notcosteffectivetomodelthisterrain's intervisibility.MilitaryDoctrineInvolvingIntervisibilityAs longassoldiershavefoughtbattles,combatantshavesoughttocontrolterrainfeatures thatriseabovethebattleground.Fromthesedecisivepoints,amilitary force has a distinct advantage.Defending from the high ground requiredtheattacker to expendadditional effort to negotiate the upward slope while thedefender concentrates solelyonfiringat theattackingforce.Fromthehighground,anoccupyingforcecanseethebattlefieldfromanenhancedperspectiveenablingtheforcetogain informationabouttheenemywhiledenying ittothe enemy.Early detection,for example,givesa leader anopportunityto seizecontrol ofthebattle.The leader cangainsurpriseover anunsuspectingenemyorgaintimetoaltertheir course of action.198
198 Terrain Resolution and Computation of I (x) In the case of this two dimensional terrain, digitized terrain can be characterized by the height of terrain at a finite set of points Xn = {x0, x1,.,xn}, where n is a measure of the resolution of the map. We order the x’s sorted in increasing order and assume they are equally spaced within D. The terrain map supported by the database, {(xi,f(xi)}: i=0,1,2,.,n} is a polygon formed by connecting adjoining points of the form (xi,f(xi)), (xi+1,f(xi+1)); this polygon approximates the actual terrain {(x,f(x)): xÎ D}. The digital terrain map approximation of intervisibility at point x, I (x), is then the sum of the lengths of the polygon segments visible from (x,f(x)). Let’s consider one of our previous functions, f(x) = |cos(p x)| over the domain D = [0,1], over two periods. The approximating intervisibility curves for n=20, 50, and 400 are shown in Figures 3 through 5. The most accurate approximating intervisibility curve model is shown in Figure 5. We note the n=10 is a crude approximation. Trying values of n > 100 did not significantly improve the resolution. Thus, we might conclude the resolution beyond n=100 is not cost effective to model this terrain’s intervisibility. Military Doctrine Involving Intervisibility As long as soldiers have fought battles, combatants have sought to control terrain features that rise above the battleground. From these decisive points, a military force has a distinct advantage. Defending from the high ground required the attacker to expend additional effort to negotiate the upward slope while the defender concentrates solely on firing at the attacking force. From the high ground, an occupying force can see the battlefield from an enhanced perspective enabling the force to gain information about the enemy while denying it to the enemy. Early detection, for example, gives a leader an opportunity to seize control of the battle. The leader can gain surprise over an unsuspecting enemy or gain time to alter their course of action
Absolute Cosine Terrain Intervisibility Curve,4.72744, 51Far11,6.12303e-017.00.20.40.60.8010,山ypyiFigure3.IntervisibilitywithN=20.Absolute Cosine Terrain IntervisibilityCurve,4.72744, 5Earc.1,6.12303e-017. 00.20.40.60.810.0.山ypyiFigure4.IntervisibilitywithN=50.199
199 Absolute Cosine Terrain Intervisibility Curve 0 0.2 0.4 0.6 0.8 1 0 1 2 3 4 5 4.72744 6.12303e-017 F i arci 0 y , 1 i y i Figure 3. Intervisibility with N = 20. Absolute Cosine Terrain Intervisibility Curve 0 0.2 0.4 0.6 0.8 1 0 1 2 3 4 5 4.72744 6.12303e-017 F i arci 0 y , 1 i y i Figure 4. Intervisibility with N = 50