CN102663811A - Real-time three-dimensional visualization method of large-scale scene city building based on spatial cognition - Google Patents

Abstract

The invention relates to a method for three-dimensional visualization of large-scene urban buildings based on spatial cognition. Based on Gestalt psychology and urban image theory, the method adopts single-chain clustering method to cluster large-scale architectural models, and uses Delaunay triangulation and polyline simplification methods to quickly merge and simplify the classification results, so as to establish The multi-detail level model of urban buildings realizes the interactive 3D visualization of large scenes and high-density urban buildings. The method provided by the invention well conforms to the principles of approach, similarity, and same direction in the Gestalt theory, and simultaneously maintains elements such as urban roads, boundaries, and iconic city images.

Description

A kind of large scene urban architecture real-time three-dimensional visualization method based on spatial cognition

One, technical field

The present invention relates to a kind of large scene urban architecture real-time three-dimensional visualization method, belong to the Spatial Information Technology field based on spatial cognition.

Two, background technology

In three-dimensional digital city, BUILDINGS MODELS is its most important component as the important embodiment of city speciality.Under the prerequisite that keeps the certain space geometric accuracy; The architectural entity of visual expression large scene; Make it to satisfy people's visual custom; Meeting the objective impression of people to the city, help people accurately and fast to obtain city space information, is the research content of geospatial information cognition and computer vision field.In order to accelerate the visual speed of large scene, high density urban architecture, realize real time interactive operation, need simplify and set up level of detail model (LOD) BUILDINGS MODELS.

Because the city is the system of height hommization, the simplification of building and visual expression not only will be considered the relation on geometry and the topology, more want cognition (cognition just the comprises visual cognition) rule of account of human.Tradition is applicable to the single geometric model that comprises a large amount of detailed information (like relief block etc.) based on the short-cut method of grid more, and comprises a large amount of BUILDINGS MODELSs in the three-dimensional digital city scene, and most BUILDINGS MODELS profile is simple, and reducible leeway is less.Use classic method and successively single BUILDINGS MODELS is simplified, can not effectively improve visual speed, so the merging that the research that BUILDINGS MODELS is simplified mainly concentrates on adjacent building is with comprehensive.There is a very important part to be the comprehensive of buildings in the comprehensive research of map; But two-dimensional map comprehensively can be introduced new summit usually; The introducing on new summit will cause the increase of data volume, for the system of progressive transmission Network Based, also will cause the reduction of transmission and display efficiency.Simultaneously, with respect to the expression of two dimension, the adding of elevation information provides abundant profound information, thereby can be by natural perception and the memory of observer to space and spatial relationship, more directly duplicates and shines upon real world.This requires the process of simplification and the cognitive law that the result should meet the observer, so comprehensive with respect to the building of two dimension, it is to be solved that the three-dimensional building simplified models of large scene has more problem to have.The present invention combines Gestalt theoretical, it is merged factor improve, and makes it more meet human cognitive law, and the building of the method that combines the Delaunay triangulation after to cluster comprehensively simplify, to raise the efficiency.

It is theoretical to the present invention is based on Gestalt psychology and city image; Adopt the strand clustering procedure that extensive BUILDINGS MODELS is carried out cluster; And the method that adopts Delaunay triangulation and polyline merges fast cluster result and simplifies, and sets up large scene with this and builds the detail model.The method that literary composition of the present invention provides well met in the Gestalt theory approaching, similar, wait principle in the same way, kept key elements such as urban road, border, significant city image simultaneously.

Three, summary of the invention

1, purpose: the object of the invention is based on Gestalt psychology and city image theoretical; Adopt the strand clustering procedure that extensive BUILDINGS MODELS is carried out cluster; And the method that adopts Delaunay triangulation and polyline merges fast classification results and simplifies; Set up urban architecture detail model with this, realize that the interactive three-dimensional of large scene, high density urban architecture is visual.

2, technical scheme: a kind of techniqueflow of the large scene urban architecture real-time three-dimensional visualization method based on spatial cognition is as shown in Figure 1, and concrete steps are following:

Step 1: utilize Gestalt psychology and city image theory to carry out the BUILDINGS MODELS cluster

Theoretical according to Gestalt psychology, figure is done as a whole by consciousness, and has certain correlativity between the each several part.People's vision is merged into an integral body according to certain organization rule with each several part, and these combination rules comprise proximity, similarity, good continuity and closure etc.

In building is comprehensive, in order to obtain to meet the result of cognitive law, also need analyzes distance relation, position relation and similarity and continuity etc. between building, and confirm Merge Scenarios according to analysis result.The key of building merge algorithm also is how to obtain its morphological feature and spatial relationship each other.On the other hand, when building merges, not only to consider the relation of adjacent building, also will consider the vision shape characteristic on the yardstick of city simultaneously.City image is meant the image of the high level overview of in people's brains outside urban environment being summarized, and it comprises five dvielements: road, border, zone, node and sign.Road is the subject element of city image perception; The border is meant except unexpected other boundary line of road, like the river etc.; The zone is meant the difference in functionality district in city, like central business district etc.; Node can be a tie point, like the road node, also can be the centrostigma of some characteristic, like square etc.; The characteristics of sign are to have uniqueness and significant in a certain respect.The simplification of urban architecture should keep this five dvielement as far as possible, makes that the building after simplifying meets the image of people to the city, helps people's effective identification spatial information, remains on the direction feeling when browsing.In this five dvielement, road be most important also be should be preferentially maintained.The present invention has combined city image theory and Gestalt psychology when building is comprehensively with simplification on a large scale, effectively kept road information, also takes into account zone and node information simultaneously to a certain extent.

Cluster has two effects, at first is the distribution pattern of identification building target, and the essential characteristic that building will keep and give prominence in simplifying is the characteristic of groups of building; Next is in order to raise the efficiency, and each type is considered to independently, merges and simplifies and will in class, carry out, and the data of other type need not to participate in calculating, and computing velocity is improved.Therefore cluster is one step of key of building shortcut calculation on a large scale.

The present invention adopts Monotone Chain hierarchical clustering method to guarantee that city image key elements such as road are able to preserve after cluster, with adjacency N as the cluster criterion, with the spatial relationship of better reflection buildings on two dimensional surface.

For the convenience of narrating, at first provide one group of definition.

Point arrives the distance on limit (line segment): for a v and straight-line segment s, cross a some v, do the vertical line of s.If intersection point v _tDrop on the line segment s, then v and v _tDistance be the distance (be referred to as vertical range) of a v to line segment s; Otherwise, get the minimum value of a v in the l two-end-point distance as the distance of a v to s.(being referred to as end-point distances).

Put polygonal distance: the bee-line of putting each limit of polygon.

Bee-line between the polygon: do not have polygon p crossing and relation of inclusion for two ₁And p ₂,

● calculate p ₁All summits to p ₂Minimum value in the distance is designated as d ₁

● same, ask and calculate p ₂All summits are to p ₁Bee-line d ₂

● get d ₁, d ₂In smaller value as polygon p ₁And p ₂Between bee-line d _Min, i.e. d _Min=min (d ₁, d ₁);

Two polygonal adjacent edge:

● ask the bee-line of calculating between two polygons, and in asking the calculation process, record d _MinCorresponding summit and limit and classification (being vertical range or end-point distances);

● if d _MinBe vertical range, suppose d _MinPairing polygon vertex is v _i, corresponding limit does Ask v respectively _iThe limit at place

With

Angle (just ask the angle of calculating place, both sides straight line, span is between 0 to 90 degree).

In, with

The angle smaller is designated as s ₁, the limit Be designated as s ₂, s ₁, s ₂Be called as one group of adjacent edge.

● if d _MinBe end-point distances, i.e. a polygonal vertex v _iWith another polygonal vertex v _iAt a distance of recently, then show adjacent edge will

The middle generation.Ask

and the angle of

; And

angle with

, two minimum limit of angle is adjacent edge.

Adjacency between the polygon: calculate s ₁, s ₂Length be respectively l ₁And l ₂, with s ₂Project to s ₁On, trying to achieve its projected length is l ₁'; In like manner, s ₁At s ₂On projected length be respectively l ₁' and l ₂', polygon P then ₁And P ₂Between adjacency d _NearCan be expressed as:

d _near＝d _min×(1-N×λ) (1)

N＝(l ₁′/l ₁+l ₂′/l ₂)/2 (2)

Here, N is used for representing the position relation of adjacent edge, works as s ₁And s ₂When parallel and relative fully, l ₁'=l ₁, l ₂'=l ₂, N=1, λ are as weight factor, and value is between 0 to 1., d definite at λ _MinUnder the identical situation, N is big more, d _NearMore little, should preferentially be gathered is one type.Adopt adjacency, not only can reflect the distance relation between the buildings, also reflected the relative direction relation of relative orientation relation and adjacent edge to a certain extent, λ is used for confirming apart from N at d _NearIn the ratio that accounts for, λ is big more, it is big more that N accounts for weight, just means that also the position relation of adjacent edge should be paid the utmost attention to; λ is more little, and it is more little that N accounts for weight, and promptly minor increment d plays a leading role between polygon.The λ value is comparatively desirable at 0.6 o'clock.

In order to calculate polygon p _iAnd p _jBetween adjacency, asking for of adjacent edge is crucial.In order to raise the efficiency, at first foundation comprises this two convex closures that polygon is new.Adopt the Graham-Scan algorithm when convex closure is set up, its time complexity is O (nlogn).Through convex closure, can reduce and to carry out the number of vertex that distance is asked calculation.

If the convex closure of finally trying to achieve is made up of two polygonal summits, the limit of convex closure can be divided into two types: one type of connection be same polygonal summit, two another kind of end points belong to two polygons, such limit is known as the border.Convex closure comprises two borders, and four summits on these two borders are with p _iAnd p _jThe summit be divided into two groups, one group of calculating of participating in adjacent edge, another group then can not participated in the calculating of adjacent edge.Shown in the figure on Fig. 2 left side,

and

is one group of border.v _1-1And v _1-6With p ₁The summit be divided into two groups.First group comprises vertex v _1-1, v _1-2..., v _1-5And v _1-6, these summits are apart from p ₂Nearer, should participate in calculating; And another group vertex v _1-7And v _1-8Then away from p ₂, when calculating, can not consider.Same p ₂Vertex v _2-2And v _2-3Also can not participate in calculating.So there is p on the summit of participating at last calculating ₁V _1-1, v _1-2..., v _1-5And v _1-6, and p ₂V _2-4, v _2-5..., v _2-8, v _2-1, final calculating is p ₁The limit

And p ₂The limit

It is one group of adjacent edge

If the convex closure of finally trying to achieve is made up of a polygonal summit fully, show that this polygonal convex closure has comprised another polygon.Shown in the figure on Fig. 2 the right, p ₂Be positioned at polygon p fully ₁Convex closure in, so big that polygonal convex closure will surround one or more slits with this polygon, and little polygon must be positioned at a slit.The calculating of adjacent edge is participated on the point and the little polygonal summit that form this slit.In the figure of Fig. 2 the right, vertex v is arranged _1-7, v _1-8, v _1-9, v _1-10Slit that surrounds and vertex v _1-5, v _1-1, v _1-6The another one slit that surrounds.Through judging p ₂Be positioned at { v _1-7, v _1-8, v _1-9, v _1-10In, so find the solution adjacent edge, only need use p ₂Summit and p ₁Vertex v _1-7, v _1-8, v _1-9, v _1-10

Step 2: the merging of BUILDINGS MODELS is with comprehensive between cluster

(1) merging of building on the two-dimensional projection plane between the class

After cluster, the polygon in every type is merged into a polygon, the polygon after being combined carries out comprehensively.When two polygons were merged into a new polygon, inevitable white space was included in the newly-generated polygon.At merging phase, utilize the summit of participating in adjacent edge again, generate the Delaunay triangulation network of belt restraining condition, then, definition connects triangle to (T ₁, T ₂), a diabolo (T ₁, T ₂) being known as that to connect triangle right, and if only if this triangle is to satisfying following three conditions:

● T1 and T2 share a limit, and this limit connects p ₁And p ₂

● another of T1 limit s ₁Connect p ₁Two summits;

● another of T2 limit s ₂Connect p ₂Two summits.

For one right in abutting connection with triangle, its limit s ₁And s ₂Adjacency be d by note _PairrEach triangle of adjacent triangle centering all has a limit connecting to belong to same leg-of-mutton two summits.For this limit, two situation are arranged: a kind of situation is that these two summits are adjacent, and promptly this edge overlaps with former polygonal limit, otherwise then is second kind of situation.If two triangles all satisfy first kind of situation, it is right then to be referred to as strict adjacent triangle, otherwise it is right to be referred to as non-strict adjacent triangle.If have one or more strictnesses right between two polygons to be combined, then calculate the right d of these triangles in abutting connection with triangle _Pairr, with having minimum d _PairrStrictness connect two polygons to be combined to produce new polygon in abutting connection with triangle to being used for.If do not have strict adjacent triangle right between two polygons, then choose and have minimum d _PairNon-strict contiguous triangle to connecting polygon.

(2) two-dimensional projection plane amalgamation result is comprehensive

The polygon that is formed by connecting through above-mentioned way has comprised too much detailed information, and it is further comprehensive to be combined the result.Adopt the Visvalingam-Whyatt polyline reduction algorithm, remove tiny sunk part.For narrating conveniently, define one type of triangle and be the depression triangle: according to counterclockwise direction, vertex v on the polygon _iWith its former and later two vertex v _I-1, v _I+1, form triangle { v _I-1, v _i, v _I+1, if along from v _I-1Through v _iAnd v _I+1Come back to v _I-1Direction be CW, then this triangle is defined as the depression triangle.Summit to two polygon portion other than connected portion travels through judgement successively, and the set of vertices triangularity that each point is adjacent with its front and back judges whether this triangle is the depression triangle.If, then write down its area, after traversal finishes, the corresponding summit of depression triangle that the deletion area is minimum.The process on reference area and deletion summit occurs up to the triangle that do not cave in above repeating, and perhaps all leg-of-mutton areas that cave in are all greater than till the given threshold value.Area threshold δ a tries to achieve through formula (3):

δa＝a _avg/λ (3)

Suppose that two polygons of tape merge are positioned at the l layer of tree, a _AvgBe the mean value of all area of a polygon of this layer.λ is the weight of user's appointment, and λ is set to 50.After having removed tiny concave polygon, the result after simplifying is further traveled through, this time the purpose of traversal is to be reduced to a limit to essentially identical two adjacent edges of direction.Calculate each to adjacent edge, if its angle is greater than certain angle threshold (this threshold value is set to 175 °), then these two limits can be reduced to a limit.

The present invention also meets visual law simultaneously reducing detailed information and keeping between the profile information of original building and obtained balance preferably, and promptly contiguous object is done as a whole by cognitive.Simultaneously, also avoided too much blank ground to be comprised in the newly-generated building, so city image information such as square can be able to preserve.

3) by 2.5 new dimension BUILDINGS MODELSs of comprehensive generation

For newly-generated polygon, the roof height of the BUILDINGS MODELS that it is corresponding equals to add the original two BUILDINGS MODELSs average height separately behind the weight coefficient, shown in formula (4):

$h=\underset{i=1}{\overset{n}{\mathrm{\Σ}}}(h_i\·a_i)/\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{a}_i---\left(4\right)$

In formula (4), h is the height after merging, h _iBe the height of child node, a _iBe the projected area of child node building on two dimensional surface xoy.

For the crossing situation in the class, then, two polygons are merged through asking the calculation intersection point, remove initiate intersection point then, adopt the Visvalingam-Whyatt algorithm synthesis again, high computational is the same.For the situation that comprises in the class, directly to get the bigger polygon of area and go up final amalgamation result as two dimensional surface xoy, height recomputates according to formula (4) and gets final product.

Step 3: make up the multiresolution urban architecture model

After pretreatment stage is accomplished, adopt the model after the tree structure storage is simplified.Because there is not the introducing on new summit, apex coordinate stores separately, each node of tree structure, and the numbering of only storing its corresponding vertex, rather than the storage node coordinate is as shown in Figure 3.Can avoid same summit to be repeated storage like this, can reduce storage space.In addition, each node also needs information such as storing highly, area.

The strand clustering procedure can be so that road be able to preserve after cluster with other boundary informations.But the strand clustering procedure only merges two buildings at every turn.The clustering tree level of so final generation is dark excessively, if will contain n the final cluster of data set of building for having only a node, the clustering tree that then generates will have the n layer.To take more storage space like this.For n initial node, be lg (n) by its degree of depth that generates the binary tree of complete equipilibrium.If with the degree of depth of tree be reduced to n ' (n ' can be provided as lg (n) or lg (n)/λ), can pass through n '-1 threshold value, the degree of depth of setting is compressed to n '.

In the process of cluster, when running to certain step,, then produce a threshold value herein if the used adjacency d of this step cluster is far longer than the adjacency in several steps.Based on such thought, when cluster, note used adjacency of each step; And be stored in the array; This array is referred to as distance sequence, according to the character of strand clustering procedure, in distance sequence; D is tactic by from small to large, the rate of growth r of adjacency _iFor

r _i＝(d _i+1-d _i)/d _i (5)

D wherein _iAnd d _I+12 adjacent adjacencies among the expression distance sequence.

Because hope the number of plies of tree is reduced to n ', so need n '-1 threshold value.So choose maximum n '-1 r,, generate a threshold value D for each r.By r _iWhen generating D, be worth desirable (d _I+1+ d _i)/2, perhaps any one greater than d _iAnd d _I+1Value.Then with this n '-1 threshold value according to from small to large sequential storage in array threshold sequence, as shown in Figure 4, to be used for that the number of plies of tree is reduced to n '.

But the tree that generates like this is not a balance, promptly some node have a too much child node, promptly a lot of buildings can be in viewpoint when far away, unexpected quilt is merged into building.In order to avoid the generation of this situation as far as possible, the maximum child node that each node can have is set counts δ p.For the bearing-age tree of n ' the layer complete equipilibrium that has n building to generate, for each non-leaf node, the child node number that it has is p:

$p=\mathrm{int}\left(\sqrt[n^{\′}-1]{n}\right)---\left(6\right)$

Therefore, δ p can be arranged to a value greater than p, like 2p.For certain one deck of tree, if this layer has m node, the always total m of these nodes _ChIndividual child node, m so _ChShould be less than or equal to m * δ p.According to this condition, inspection is by the node of each layer of the tree of threshold sequence compression generation and the number of its child node.When by D _lWhen the compression several layers becomes one new layer, the m if this layer does not satisfy condition _Ch≤m * δ p then means D _lAnd D _L-1Span too big, to such an extent as to a lot of building is merged into a building suddenly.So in threshold value, D _L-1And D _lBetween insert a new threshold value D _NewD _NewGenerative process following: at first, in distance sequence, extract and be positioned at interval [D _L-1, D _l] an interior cross-talk array, maximum r place produces new threshold value D in this subnumber group then _NewUse D _NewProduce new layer, check this new layer of m that whether satisfies condition _Ch≤m * δ p.If do not satisfy, then use interval [D _L-1, D _New] in distance sequence, extract new subnumber group, upgrade D with producing new threshold value _NewOld value.Repeat said process, up to by D _NewThe new layer of m that satisfies condition that produces _Ch≤m * δ p is then with D _NewBe inserted into D _L-1And D _lBetween.

Step 4: Interactive Visualization

Set up the BUILDINGS MODELS of detail, higher along with moving of viewpoint from the level of detail of the near BUILDINGS MODELS of viewpoint distance, and the model rendering of the available lower level of building at a distance.Be that standard is different with the distance in the classic method, the present invention is the standard that level of detail is divided to merge the projected size of error on screen that produces.The distance of model apart from viewpoint not only considered in the division of this standard, also considered the size of the error of model own.

In visualization process, the error that human eye can obviously be experienced mainly can be divided into two types, and one type relevant with highly, though the child node height is different, after merging, its father node has only an elevation information; Another kind of relevant with area, in the BUILDINGS MODELS merging process, originally blank zone can be included in the polygon after the merging between the building, causes on the two-dimensional level face, and the area of father node is greater than the area of its child node.After generating three-dimensional model, the building roof area also can correspondingly increase.

These two types of errors all need be considered.But the roaming mode is not simultaneously, and the influence to visual effect of these two types of errors is different.When the building internetwork roaming; The basic along continuous straight runs of sight line, this moment, building was at a distance often blocked by building nearby, so the long-pending variation of building surface at a distance is difficult for coming to light; And person walks is between building; Perception to the building roof is positioned at backseat, but the height change of building can indicate the height of buildings especially at a distance by strong by perception.So should stress to consider height error this moment.When the roaming mode changed top-down looking down into, the profile on building roof was the information of primary significance that human eye gets access to, and elevation information is positioned at backseat.So should mainly consider the distortion of roof contour this moment.

To with non-leaf node, circulation is asked for it and is comprised the high building height H in the child node _Max, and the height H of minimum building _MinStep is following:

If leaf node is positioned at the n layer, then ask in the n-1 layer H of each node earlier _MaxAnd H _Min, and then ask and calculate the n-2 layer, in all child nodes of each node, maximum H _MaxH as this node _Max, minimum H _MinH as this node _MinRepeat this process, up to having calculated till the 0th layer.Definition discrepancy in elevation Δ H=H _Max-H _Min, represent the discrepancy in elevation between the high building and minimum building in the pairing primitive architecture of each node.Obviously, for leaf node, Δ H=0.The roof area of definition father node deducts its pairing primitive architecture crowd's roof area sum, as newly-increased roof area Δ A.The process of resolving also is to adopt bottom-up circulation, confirms two threshold value δ thus _H, δ _A, its meaning does, and the corresponding original groups of building of child node project on the screen, and its high building and minimum building height difference should be less than δ _HIndividual pixels tall, newly-increased roof area project to should be less than δ on the screen _AIndividual pixel.

Adopt the difference in height of high building and minimum building height under the following method approximate expression screen coordinate system.If the vertical field of view angle FOV of video camera, and nearly cutting identity distance is from being D _Near, then can try to achieve nearly cutting face height H _Near

H _near＝D _near×tan(FOV)×2 (7)

The viewport height is H _ViewIndividual pixel, n on the corresponding screen of unit length on the then near cutting face _ScaleIndividual pixel, n _Scale=H _View/ H _NearProject on the nearly cutting face discrepancy in elevation Δ H is approximate, for each node, the distance of establishing this node center and video camera is D _Node, considering has the angle theta of sight line and surface level,

ΔH′＝ΔH×(D _near/D _node)×cos(θ)

ΔH _view＝ΔH′×n _scale (8)

Δ H _ViewBe the pixel count of discrepancy in elevation Δ H correspondence on screen.Same, for Δ A, be similar to earlier and try to achieve its projection on nearly cutting face, try to achieve its projected size Δ A on screen again _View

ΔA′＝ΔA×(D _near/D _node) ²×sin(θ)

ΔA _view＝ΔA′×n _scale (9)

In the process of scene walkthrough, the angle of direction of visual lines and video camera are apart from the position real-time change of node.Calculate Δ Hview and Δ Aview in real time, if Δ Hview＜δ H, and Δ Aview＜δ A, then play up this node; Otherwise this node is not played up, and recurrence is judged its child node.

3, advantage and effect: (1) the present invention combines city image and Gestalt psychology theory; Standard when a kind of new distance metric mode is provided as the building cluster; BUILDINGS MODELS is merged the factor to be improved; Make it more meet human cognitive law; And the extensive building of the method that combines the Delaunay triangulation after to cluster comprehensively simplify, and makes amalgamation result reducing detailed information and approaching and obtain balance preferably between these two targets of original building profile, improved large-scale city architectural rendering and visual efficient.(2) method provided by the invention met in the Gestalt psychology theory approaching, similar, wait principle in the same way, kept key elements such as urban road, border, significant city image simultaneously.

Four, description of drawings

Fig. 1 techniqueflow synoptic diagram of the present invention

Fig. 2 polygonal convex closure to be combined (shown in the dotted line)

Fig. 3 simplifies result's tree-like storage mode.The summit numbering of corresponding this node of storage of array of each node

The generation flow process of used threshold value during the compression of Fig. 4 hierarchical tree

Fig. 5 (a) primitive architecture model equatorial projection figure

Fig. 5 (b) adopts the merging synoptic diagram of the building equatorial projection figure of contiguous cluster

Fig. 5 (c) adopts the merging synoptic diagram (the merging degree increases gradually) of the building equatorial projection figure of contiguous cluster

Fig. 5 (d) adopts the merging synoptic diagram (the merging degree increases once more) of the building equatorial projection figure of contiguous cluster

Fig. 5 (e) corresponding with (b) adopted the amalgamation result of Euclidean distance

Fig. 5 (f) adopts the amalgamation result of Euclidean distance with (c) corresponding

Fig. 5 (g) adopts the amalgamation result of Euclidean distance with (d) corresponding

Fig. 6 (a) simplifies consuming time and asd number graph of a relation

Fig. 6 (b) simplifies consuming time and number of vertex magnitude relation figure

The visual city of Fig. 7 the present invention three-dimensional scene

Five, embodiment

The present invention relates to a kind of large scene urban architecture real-time three-dimensional visualization method based on spatial cognition, the concrete steps of this method are following:

Step 1: utilize Gestalt psychology and city image theory to carry out the BUILDINGS MODELS cluster

Theoretical according to Gestalt psychology, figure is done as a whole by consciousness, and has certain correlativity between the each several part.People's vision is merged into an integral body according to certain organization rule with each several part, and these combination rules comprise proximity, similarity, good continuity and closure etc.

In building is comprehensive, in order to obtain to meet the result of cognitive law, also need analyzes distance relation, position relation and similarity and continuity etc. between building, and confirm Merge Scenarios according to analysis result.The key of building merge algorithm also is how to obtain its morphological feature and spatial relationship each other.On the other hand, when building merges, not only to consider the relation of adjacent building, also will consider the vision shape characteristic on the yardstick of city simultaneously.City image is meant the image of the high level overview of in people's brains outside urban environment being summarized, and it comprises five dvielements: road, border, zone, node and sign.Road is the subject element of city image perception; The border is meant except unexpected other boundary line of road, like the river etc.; The zone is meant the difference in functionality district in city, like central business district etc.; Node can be a tie point, like the road node, also can be the centrostigma of some characteristic, like square etc.; The characteristics of sign are to have uniqueness and significant in a certain respect.The simplification of urban architecture should keep this five dvielement as far as possible, makes that the building after simplifying meets the image of people to the city, helps people's effective identification spatial information, remains on the direction feeling when browsing.In this five dvielement, road be most important also be should be preferentially maintained.The present invention has combined city image theory and Gestalt psychology when building is comprehensively with simplification on a large scale, effectively kept road information, also takes into account zone and node information simultaneously to a certain extent.

Cluster has two effects, at first is the distribution pattern of identification building target, and the essential characteristic that building will keep and give prominence in simplifying is the characteristic of groups of building; Next is in order to raise the efficiency, and each type is considered to independently, merges and simplifies and will in class, carry out, and the data of other type need not to participate in calculating, and computing velocity is improved.Therefore cluster is one step of key of building shortcut calculation on a large scale.

The present invention adopts Monotone Chain hierarchical clustering method to guarantee that city image key elements such as road are able to preserve after cluster, with adjacency N as the cluster criterion, with the spatial relationship of better reflection buildings on two dimensional surface.

For the convenience of narrating, at first provide one group of definition.

Point arrives the distance on limit (line segment): for a v and straight-line segment s, cross a some v, do the vertical line of s.If intersection point v _tDrop on the line segment s, then v and v _tDistance be the distance (be referred to as vertical range) of a v to line segment s; Otherwise, get the minimum value of a v in the l two-end-point distance as the distance of a v to s.(being referred to as end-point distances).

Put polygonal distance: the bee-line of putting each limit of polygon.

Bee-line between the polygon: do not have polygon p crossing and relation of inclusion for two ₁And p ₂,

● calculate p ₁All summits to p ₂Minimum value in the distance is designated as d ₁

● same, ask and calculate p ₂All summits are to p ₁Bee-line d ₂

● get d ₁, d ₂In smaller value as polygon p ₁And p ₂Between bee-line d _Min, i.e. d _Min=min (d ₁, d ₁);

Two polygonal adjacent edge:

● ask the bee-line of calculating between two polygons, and in asking the calculation process, record d _MinCorresponding summit and limit and classification (being vertical range or end-point distances);

● if d _MinBe vertical range, suppose d _MinPairing polygon vertex is v _i, corresponding limit does

Ask v respectively _iThe limit at place

With

Angle (just ask the angle of calculating place, both sides straight line, span is between 0 to 90 degree).

In, with

The angle smaller is designated as s ₁, the limit

Be designated as s ₂, s ₁, s ₂Be called as one group of adjacent edge.

● if d _MinBe end-point distances, i.e. a polygonal vertex v _iWith another polygonal vertex v _iAt a distance of recently, then show adjacent edge will

The middle generation.Ask

and the angle of

; And

angle with

, two minimum limit of angle is adjacent edge.

Adjacency between the polygon: calculate s ₁, s ₂Length be respectively l ₁And l ₂, with s ₂Project to s ₁On, trying to achieve its projected length is l ₁'; In like manner, s ₁At s ₂On projected length be respectively l ₁' and l ₂', polygon P then ₁And P ₂Between adjacency d _NearCan be expressed as:

d _near＝d _min×(1-N×λ) (1)

N＝(l ₁′/l ₁+l ₂′/l ₂)/2 (2)

Here, N is used for representing the position relation of adjacent edge, works as s ₁And s ₂When parallel and relative fully, l ₁'=l ₁, l ₂'=l ₂, N=1, λ are as weight factor, and value is between 0 to 1., d definite at λ _MinUnder the identical situation, N is big more, d _NearMore little, should preferentially be gathered is one type.Adopt adjacency, not only can reflect the distance relation between the buildings, also reflected the relative direction relation of relative orientation relation and adjacent edge to a certain extent, λ is used for confirming apart from N at d _NearIn the ratio that accounts for, λ is big more, it is big more that N accounts for weight, just means that also the position relation of adjacent edge should be paid the utmost attention to; λ is more little, and it is more little that N accounts for weight, and promptly minor increment d plays a leading role between polygon.The λ value is comparatively desirable at 0.6 o'clock.

In order to calculate polygon p _iAnd p _jBetween adjacency, asking for of adjacent edge is crucial.In order to raise the efficiency, at first foundation comprises this two convex closures that polygon is new.Adopt the Graham-Scan algorithm when convex closure is set up, its time complexity is O (nlog n).Through convex closure, can reduce and to carry out the number of vertex that distance is asked calculation.

If the convex closure of finally trying to achieve is made up of two polygonal summits, the limit of convex closure can be divided into two types: one type of connection be same polygonal summit, two another kind of end points belong to two polygons, such limit is known as the border.Convex closure comprises two borders, and four summits on these two borders are with p _iAnd p _jThe summit be divided into two groups, one group of calculating of participating in adjacent edge, another group then can not participated in the calculating of adjacent edge.Shown in the figure on Fig. 2 left side, and

is one group of border.v _1-1And v _1-6With p ₁The summit be divided into two groups.First group comprises vertex v _1-1, v _1-2..., v _1-5And v _1-6, these summits are apart from p ₂Nearer, should participate in calculating; And another group vertex v _1-7And v _1-8Then away from p ₂, when calculating, can not consider.Same p ₂Vertex v _2-2And v _2-3Also can not participate in calculating.So there is p on the summit of participating at last calculating ₁V _1-1, v _1-2..., v _1-5And v _1-6, and p ₂V _2-4, v _2-5..., v _2-8, v _2-1, final calculating is p ₁The limit

And p ₂The limit It is one group of adjacent edge

If the convex closure of finally trying to achieve is made up of a polygonal summit fully, show that this polygonal convex closure has comprised another polygon.Shown in the figure on Fig. 2 the right, p ₂Be positioned at polygon p fully ₁Convex closure in, so big that polygonal convex closure will surround one or more slits with this polygon, and little polygon must be positioned at a slit.The calculating of adjacent edge is participated on the point and the little polygonal summit that form this slit.In the figure of Fig. 2 the right, vertex v is arranged _1-7, v _1-8, v _1-9, v _1-10Slit that surrounds and vertex v _1-5, v _1-1, v _1-6The another one slit that surrounds.Through judging p ₂Be positioned at { v _1-7, v _1-8, v _1-9, v _1-10In, so find the solution adjacent edge, only need use p ₂Summit and p ₁Vertex v _1-7, v _1-8, v _1-9, v _1-10

Step 2: the merging of BUILDINGS MODELS is with comprehensive between cluster

(1) merging of building on the two-dimensional projection plane between the class

After cluster, the polygon in every type is merged into a polygon, the polygon after being combined carries out comprehensively.When two polygons were merged into a new polygon, inevitable white space was included in the newly-generated polygon.At merging phase, utilize the summit of participating in adjacent edge again, generate the Delaunay triangulation network of belt restraining condition, then, definition connects triangle to (T ₁, T ₂), a diabolo (T ₁, T ₂) being known as that to connect triangle right, and if only if this triangle is to satisfying following three conditions:

● T1 and T2 share a limit, and this limit connects p ₁And p ₂

● another of T1 limit s ₁Connect p ₁Two summits;

● another of T2 limit s ₂Connect p ₂Two summits.

For one right in abutting connection with triangle, its limit s ₁And s ₂Adjacency be d by note _PairrEach triangle of adjacent triangle centering all has a limit connecting to belong to same leg-of-mutton two summits.For this limit, two situation are arranged: a kind of situation is that these two summits are adjacent, and promptly this edge overlaps with former polygonal limit, otherwise then is second kind of situation.If two triangles all satisfy first kind of situation, it is right then to be referred to as strict adjacent triangle, otherwise it is right to be referred to as non-strict adjacent triangle.If have one or more strictnesses right between two polygons to be combined, then calculate the right d of these triangles in abutting connection with triangle _Pairr, with having minimum d _PairrStrictness connect two polygons to be combined to produce new polygon in abutting connection with triangle to being used for.If do not have strict adjacent triangle right between two polygons, then choose and have minimum d _PairNon-strict contiguous triangle to connecting polygon.

(2) two-dimensional projection plane amalgamation result is comprehensive

The polygon that is formed by connecting through above-mentioned way has comprised too much detailed information, and it is further comprehensive to be combined the result.Adopt the Visvalingam-Whyatt polyline reduction algorithm, remove tiny sunk part.For narrating conveniently, define one type of triangle and be the depression triangle: according to counterclockwise direction, vertex v on the polygon _iWith its former and later two vertex v _I-1, v _I+1, form triangle { v _I-1, v _i, v _I+1, if along from v _I-1Through v _iAnd v _I+1Come back to v _I-1Direction be CW, then this triangle is defined as the depression triangle.Summit to two polygon portion other than connected portion travels through judgement successively, and the set of vertices triangularity that each point is adjacent with its front and back judges whether this triangle is the depression triangle.If, then write down its area, after traversal finishes, the corresponding summit of depression triangle that the deletion area is minimum.The process on reference area and deletion summit occurs up to the triangle that do not cave in above repeating, and perhaps all leg-of-mutton areas that cave in are all greater than till the given threshold value.Area threshold δ a tries to achieve through formula (3):

δa＝a _avg/λ (3)

Suppose that two polygons of tape merge are positioned at the l layer of tree, a _AvgBe the mean value of all area of a polygon of this layer.λ is the weight of user's appointment, and λ is set to 50.After having removed tiny concave polygon, the result after simplifying is further traveled through, this time the purpose of traversal is to be reduced to a limit to essentially identical two adjacent edges of direction.Calculate each to adjacent edge, if its angle is greater than certain angle threshold (this threshold value is set to 175 °), then these two limits can be reduced to a limit.

The present invention also meets visual law simultaneously reducing detailed information and keeping between the profile information of original building and obtained balance preferably, and promptly contiguous object is done as a whole by cognitive.Simultaneously, also avoided too much blank ground to be comprised in the newly-generated building, so city image information such as square can be able to preserve.

3) by 2.5 new dimension BUILDINGS MODELSs of comprehensive generation

For newly-generated polygon, the roof height of the BUILDINGS MODELS that it is corresponding equals to add the original two BUILDINGS MODELSs average height separately behind the weight coefficient, shown in formula (4):

$h=\underset{i=1}{\overset{n}{\mathrm{\Σ}}}(h_i\·a_i)/\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{a}_i---\left(4\right)$

In formula (4), h is the height after merging, h _iBe the height of child node, a _iBe the projected area of child node building on two dimensional surface xoy.

For the crossing situation in the class, then, two polygons are merged through asking the calculation intersection point, remove initiate intersection point then, adopt the Visvalingam-Whyatt algorithm synthesis again, high computational is the same.For the situation that comprises in the class, directly to get the bigger polygon of area and go up final amalgamation result as two dimensional surface xoy, height recomputates according to formula (4) and gets final product.

Step 3: make up the multiresolution urban architecture model

After pretreatment stage is accomplished, adopt the model after the tree structure storage is simplified.Because there is not the introducing on new summit, apex coordinate stores separately, each node of tree structure, and the numbering of only storing its corresponding vertex, and the storage node coordinate is not as shown in Figure 3.Can avoid same summit to be repeated storage like this, can reduce storage space.In addition, each node also needs information such as storing highly, area.

The strand clustering procedure can be so that road be able to preserve after cluster with other boundary informations.But the strand clustering procedure only merges two buildings at every turn.The clustering tree level of so final generation is dark excessively, if will contain n the final cluster of data set of building for having only a node, the clustering tree that then generates will have the n layer.To take more storage space like this.For n initial node, be lg (n) by its degree of depth that generates the binary tree of complete equipilibrium.If with the degree of depth of tree be reduced to n ' (n ' can be provided as lg (n) or lg (n)/λ), can pass through n '-1 threshold value, the degree of depth of setting is compressed to n '.

In the process of cluster, when running to certain step,, then produce a threshold value herein if the used adjacency d of this step cluster is far longer than the adjacency in several steps.Based on such thought, when cluster, note used adjacency of each step; And be stored in the array; This array is referred to as distance sequence, according to the character of strand clustering procedure, in distance sequence; D is tactic by from small to large, the rate of growth r of adjacency _iFor

r _i＝(d _i1-d _i)/d _i (5)

D wherein _iAnd d _I+12 adjacent adjacencies among the expression distance sequence.

Because hope the number of plies of tree is reduced to n ', so need n '-1 threshold value.So choose maximum n '-1 r,, generate a threshold value D for each r.By r _iWhen generating D, be worth desirable (d _I+1+ d _i)/2, perhaps any one greater than d _iAnd d _I+1Value.Then with this n '-1 threshold value according to from small to large sequential storage in array threshold sequence, as shown in Figure 4, to be used for that the number of plies of tree is reduced to n '.

But the tree that generates like this is not a balance, promptly some node have a too much child node, promptly a lot of buildings can be in viewpoint when far away, unexpected quilt is merged into building.In order to avoid the generation of this situation as far as possible, the maximum child node that each node can have is set counts δ p.For the bearing-age tree of n ' the layer complete equipilibrium that has n building to generate, for each non-leaf node, the child node number that it has is p:

$p=\mathrm{int}\left(\sqrt[n^{\′}-1]{n}\right)---\left(6\right)$

Therefore, δ p can be arranged to a value greater than p, like 2p.For certain one deck of tree, if this layer has m node, the always total m of these nodes _ChIndividual child node, m so _ChShould be less than or equal to m * δ p.According to this condition, inspection is by the node of each layer of the tree of threshold sequence compression generation and the number of its child node.When by D _lWhen the compression several layers becomes one new layer, the m if this layer does not satisfy condition _Ch≤m * δ p then means D _lAnd D _L-1Span too big, to such an extent as to a lot of building is merged into a building suddenly.So in threshold value, D _L-1And D _lBetween insert a new threshold value D _NewD _NewGenerative process following: at first, in distance sequence, extract and be positioned at interval [D _L-1, D _l] an interior cross-talk array, maximum r place produces new threshold value D in this subnumber group then _NewUse D _NewProduce new layer, check this new layer of m that whether satisfies condition _Ch≤m * δ p.If do not satisfy, then use interval [D _L-1, D _New] in distance sequence, extract new subnumber group, upgrade D with producing new threshold value _NewOld value.Repeat said process, up to by D _NewThe new layer of m that satisfies condition that produces _Ch≤m * δ p is then with D _NewBe inserted into D _L-1And D _lBetween.

Step 4: Interactive Visualization

Set up the BUILDINGS MODELS of detail, higher along with moving of viewpoint from the level of detail of the near BUILDINGS MODELS of viewpoint distance, and the model rendering of the available lower level of building at a distance.Be that standard is different with the distance in the classic method, the present invention is the standard that level of detail is divided to merge the projected size of error on screen that produces.The distance of model apart from viewpoint not only considered in the division of this standard, also considered the size of the error of model own.

In visualization process, the error that human eye can obviously be experienced mainly can be divided into two types, and one type relevant with highly, though the child node height is different, after merging, its father node has only an elevation information; Another kind of relevant with area, in the BUILDINGS MODELS merging process, originally blank zone can be included in the polygon after the merging between the building, causes on the two-dimensional level face, and the area of father node is greater than the area of its child node.After generating three-dimensional model, the building roof area also can correspondingly increase.

These two types of errors all need be considered.But the roaming mode is not simultaneously, and the influence to visual effect of these two types of errors is different.When the building internetwork roaming; The basic along continuous straight runs of sight line, this moment, building was at a distance often blocked by building nearby, so the long-pending variation of building surface at a distance is difficult for coming to light; And person walks is between building; Perception to the building roof is positioned at backseat, but the height change of building can indicate the height of buildings especially at a distance by strong by perception.So should stress to consider height error this moment.When the roaming mode changed top-down looking down into, the profile on building roof was the information of primary significance that human eye gets access to, and elevation information is positioned at backseat.So should mainly consider the distortion of roof contour this moment.

To with non-leaf node, circulation is asked for it and is comprised the high building height H in the child node _Max, and the height H of minimum building _MinStep is following:

If leaf node is positioned at the n layer, then ask in the n-1 layer H of each node earlier _MaxAnd H _Min, and then ask and calculate the n-2 layer, in all child nodes of each node, maximum H _MaxH as this node _Max, minimum H _MinH as this node _MinRepeat this process, up to having calculated till the 0th layer.Definition discrepancy in elevation Δ H=H _Max-H _Min, represent the discrepancy in elevation between the high building and minimum building in the pairing primitive architecture of each node.Obviously, for leaf node, Δ H=0.The roof area of definition father node deducts its pairing primitive architecture crowd's roof area sum, as newly-increased roof area Δ A.The process of resolving also is to adopt bottom-up circulation, confirms two threshold value δ thus _H, δ _A, its meaning does, and the corresponding original groups of building of child node project on the screen, and its high building and minimum building height difference should be less than δ _HIndividual pixels tall, newly-increased roof area project to should be less than δ on the screen _AIndividual pixel.

Adopt the difference in height of high building and minimum building height under the following method approximate expression screen coordinate system.If the vertical field of view angle FOV of video camera, and nearly cutting identity distance is from being D _Near, then can try to achieve nearly cutting face height H _Near

H _near＝D _near×tan(FOV)×2 (7)

The viewport height is H _ViewIndividual pixel, n on the corresponding screen of unit length on the then near cutting face _ScaleIndividual pixel, n _Scale=H _View/ H _NearProject on the nearly cutting face discrepancy in elevation Δ H is approximate, for each node, the distance of establishing this node center and video camera is D _Node, considering has the angle theta of sight line and surface level,

ΔH′＝ΔH×(D _near/D _node)×cos(θ)

ΔH _view＝ΔH′×n _scale (8)

Δ H _ViewBe the pixel count of discrepancy in elevation Δ H correspondence on screen.Same, for Δ A, be similar to earlier and try to achieve its projection on nearly cutting face, try to achieve its projected size Δ A on screen again _View

ΔA′＝ΔA×(D _near/D _node) ²×sin(θ)

ΔA _view＝ΔA′×n _scale (9)

In the process of scene walkthrough, the angle of direction of visual lines and video camera are apart from the position real-time change of node.Calculate Δ Hview and Δ Aview in real time, if Δ Hview＜δ H, and Δ Aview＜δ A, then play up this node; Otherwise this node is not played up, and recurrence is judged its child node.

Embodiment 1:

Dispose 3.00GHz Intel (R) Pentium (R) 4CPU at one, the 2GB internal memory is implemented on the computing machine of ATI mobility radeon X300 video card.

At first contrasted the cluster result that adopts adjacency and Euclidean distance.Fig. 5 (a) is the original building polygon, and it contains 37 buildings, and the degree of depth of the hierachy number after hoping to compress is int (lg (37)/1.5); Cluster result when Fig. 5 (b), (c), (d) are clustering criteria for adopting adjacency, and the merging degree increases successively gradually; Fig. 5 (e), (f), (g) adopt Euclidean distance as the simplification result apart from the factor.Can find out that through contrast the present invention adopts adjacency, better, better keep road information simultaneously with respect to trend and the similarity between building of groups of building.

To the efficient that building is simplified, the present invention and document " Chang, R., Butkiewicz; T., Ziemkiewicz, C., Wartell; z., Ribarsky, W.and Pollard, N.; 2008.Legible Simplification of Textured Urban Models, IEEEComputer Graphics and Applications, 28 (3), 27-36. " contrast.The algorithm complex of the document is O (n under the worst situation ³), it is O (n that the present invention asks the time complexity of calculating the Delaunay triangulation ²), adopt the convex closure algorithm that it is reduced to O (m ²), same, the time complexity that adjacency is asked for also is O (m ²).M be two adjacent triangles do not have disallowablely, participate in the number of vertex of Delaunay triangulation, and the algorithm time complexity of convex closure is O (nlogn).The complexity of polyline of the present invention is O (n log n).Therefore, in the whole process, time complexity of the present invention will be lower than O (n ²).Fig. 6 has shown the relation between the number of vertex on simplification time and BUILDINGS MODELS number and the 2 d plane picture; Dotted portion is the quafric curve that is simulated by experimental data among the figure; It is thus clear that along with the increase of data volume, the simplification time approximately increases with the speed of quadratic power.

Merging integrated approach of the present invention also compares with people's such as Article document Chang method.The document adopts the method for convex closure evolution, at first generates polygonal convex closure to be combined, and the limit to convex closure splits then, up to the limit of convex closure number count greater than two child node limits summation 75% till.Because the shape of building often differs greatly, split when finishing, most detailed information is deleted in possible some type, and most detailed information still is retained in other types, so cause the degree of integration meeting of different cluster results different.Compare; The present invention is to the node that is positioned at same layer when comprehensive; Adopt the area identical threshold value,, make amalgamation result reduce detailed information and approach between these two targets of original building profile and obtain balance preferably so can guarantee with the degree of integration of the node of one deck approximately basically.

For further proving advantage of the present invention, build data as check with the part of Haidian District Beijing.These data comprise 35,138 buildings, totally 913,603 building projection summits.The degree of depth of hierarchical tree is compressed to int (lg1809)/1.5), promptly 9 layers.When visual, discrepancy in elevation threshold value δ _HBe set at 20 pixels, newly-increased roof area threshold value δ _ABe set at 200 pixels, its display effect is as shown in Figure 7.The present invention has reduced the level of detail of building at a distance, has effectively reduced to play up consuming timely, has kept city images such as groups of building, road, sign atural object preferably simultaneously, between rendering efficiency and rendering effect, has kept balance preferably.

Claims (1)

1. The steps of a method for real-time three-dimensional visualization of large scene urban buildings based on spatial cognition include: (1) Building clustering method based on Gestalt psychology and urban image theory The invention adopts a monotone chain hierarchical clustering method to ensure that urban image elements such as roads are preserved after clustering, and uses the adjacent distance N as a clustering judgment standard to better reflect the spatial relationship of buildings on a two-dimensional plane. In order to calculate the adjacent distance between polygons p _i and p _j , a new convex hull containing these two polygons is first established, and the Graham-Scan algorithm is used when the convex hull is established; the convex hull contains two boundaries, and the four boundaries of these two boundaries Vertices Divide the vertices of p _i and p _j into two groups, one group participates in the calculation of adjacent edges, and the other group does not participate in the calculation of adjacent edges; if the final convex hull is completely composed of vertices of a polygon, it indicates that the polygon The convex hull of the larger polygon contains another polygon, then the convex hull of the larger polygon and the polygon must form one or more gaps, and the small polygon must be located in a gap, and the points forming the gap and the vertices of the small polygon participate in Computation of adjacent edges. (2) Merge and synthesis of building models between clusters 1) Incorporation of inter-class buildings on a 2D projection plane After clustering, the polygons in each class are first merged into one polygon, and then the merged polygons are synthesized. In the merge stage, the vertices participating in the adjacent edges are reused to generate a Delaunay triangulation with constraints. If two There are one or more strictly adjacent triangle pairs between two polygons, then calculate the adjacent distance of these triangle pairs, use the strict adjacent triangle pair with the minimum adjacent distance to connect the two polygons to be merged to produce a new polygon, if two If there are no strictly adjacent triangle pairs between polygons, a non-strictly adjacent triangle pair with the smallest adjacent distance is selected to connect the polygons. 2) Synthesis of merging results of two-dimensional projected planes The polygons connected by the above methods include too much detailed information, and the merged results need to be further synthesized, using the method of Visvalingam-Whyatt polyline simplification algorithm to remove the small concave parts; according to the counterclockwise direction, a vertex v _i on the polygon and its front and back vertices v _i-1 , v _i+1 to _form a triangle {v _i-1 , v _{i ,} v _{i+ 1} }. Returning to the direction of v _i-1 as clockwise, the triangle is defined as a sunken triangle; the vertices at the non-connection of the two polygons are traversed and judged sequentially, and each point forms a triangle with its front and rear adjacent vertices, and the judgment Whether this triangle is a sunken triangle; if it is, record its area, after the traversal, delete the vertex corresponding to the sunken triangle with the smallest area, repeat the above process of calculating the area and deleting the vertex, until no sunken triangle appears, or all sunken triangles Until the area is greater than the given threshold, the area threshold is calculated by formula (3). δa= _aavg /λ (3) Assuming that the two polygons with merging are located at layer l of the tree, a _avg is the average area of all polygons in this layer, and λ is a user-specified weight. After removing the small concave polygons, the simplified results are further traversed , calculate each pair of adjacent sides, if the included angle is greater than a certain angle threshold, then the two sides can be simplified into one side. 3) A new 3D building model is generated by synthesis For the newly generated polygon, the roof height of the corresponding building model is equal to the average height of the original two building models after adding the weight coefficient, as shown in formula (4): $\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span>{\mathrm{<span\; class="notranslate">\; a</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; /</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; a</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; )</span>$ In formula (4), h is the combined height, h _i is the height of the sub-node, a _i is the projected area of the sub-node building on the two-dimensional plane xoy, and for the intra-class intersection, calculate the intersection point , merge the two polygons, then remove the newly added intersection point, and then use the Visvalingam-Whyatt algorithm to synthesize, and the height calculation is the same as above; for the case of inclusion in the class, directly take the polygon with a larger area as the final merge result on the two-dimensional plane xoy, The height can be recalculated according to formula (4). (3) Build a multi-resolution 3D building model After the preprocessing stage is completed, the simplified model is stored in a tree structure, and the vertex coordinates are stored separately. Each node in the tree structure only stores the number of its corresponding vertex, not the node coordinates. In addition, each Each node also needs to store information such as height and area; for n initial nodes, the depth of a fully balanced binary tree generated by it is lg(n). If the depth of the tree is reduced to n', you can pass n' -1 threshold to compress the depth of the tree to n'; when clustering, record the adjacent distance used in each step and store it in the array distance sequence. According to the nature of the single chain clustering method, in the distance sequence Among them, d is arranged in order from small to large, and the growth rate r _i of the adjacent distance is, r _i =(d _i+1 -d _i )/d _i (5) Among them, d _i and d _i+1 represent two adjacent distances in the distance sequence. Select the largest n'-1 r, generate a threshold D for each r, and then store the n'-1 thresholds in the array threshold sequence in order from small to large, so as to use the number of layers of the tree Reduced to n', set the maximum number of sub-nodes δp that each node can have, for a fully balanced result tree with n' layers generated by n buildings, for each non-leaf node, the number of sub-nodes it has is p: $\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; int</span>}<span\; class="notranslate">\; (</span>\sqrt[{\mathrm{<span\; class="notranslate">\; no</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}]{\mathrm{<span\; class="notranslate">\; no</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 6</span>}<span\; class="notranslate">\; )</span>$ Check the number of nodes and its sub-nodes in each layer of the tree generated by threshold sequence compression, when several layers are compressed by D _l to become a new layer, if this layer does not satisfy the condition m _ch ≤ m×δp, in Threshold, insert a new threshold D _new between D _l-1 and D _l , the generation process of D _new is as follows: First, extract a sub-array located in the interval [D _l-1 , D _l ] in the distance sequence , and then generate a new threshold D _new at the maximum r in this sub-array, use D _new to generate a new layer, check whether this new layer satisfies the condition m _ch ≤ m×δp, if not, use the interval [D _l-1 , D _new ] Extract new sub-arrays in the distance sequence, update the old value of D _new with a new threshold value, repeat the above process until the new layer generated by D _new satisfies the condition m _ch ≤ m×δp, and then set D _new is inserted between D _l-1 and D _l ·. (4) Interactive visualization Taking the projected size of the combined errors on the screen as the standard for the level of detail division, for non-leaf nodes, loop to obtain the highest building height H _max and the lowest building height H _min among the child nodes contained in it, the process as follows: Assuming that the leaf node is located in layer n, first calculate the H _max and H _min of each node in layer n-1, and then calculate the maximum H among all child nodes of each node in layer n-2 _max is used as the H _max of the node, and the smallest H _min is used as the H _min of the node. Repeat this step until the calculation of the 0th layer is completed; define the height difference ΔH=H _max -H _min , which means that each node The height difference between the tallest building and the lowest building in the corresponding original building, obviously, for a leaf node, ΔH=0, define the sum of the roof area of the parent node minus the roof area of the corresponding original building group, as The newly added roof area ΔA, the calculation procedure is the same as the calculation process of the height difference ΔH, and also uses a bottom-up cycle, thus determining two thresholds δ _H , δ _A , which means that a child node corresponds to the original When the buildings are projected onto the screen, the height difference between the highest building and the lowest building should be less than δ _H pixel heights, and the newly added roof area should be less than δ _A pixels when projected on the screen. Use the following method to express the height difference between the highest building and the lowest building height in the screen coordinate system. First, calculate the correspondence between the unit length of the near clipping plane and the viewport pixels. Set the vertical field of view FOV of the camera and the distance of the near clipping plane as D _near , then the height H _near of the near clipping plane can be obtained. H _near ＝D _near ×tan(FOV)×2 (7) The viewport height is H _view pixels, then the unit length on the near clipping plane corresponds to n _scale pixels on the screen, n _scale = H _view /H _near , secondly, the height difference ΔH is approximately projected onto the near clipping plane, for each node, set the distance between the center of this node and the camera as D _node , considering the angle θ between the line of sight and the horizontal plane, there is, ΔH'＝ΔH×(D _near /D _node )×cos(θ) ΔH _view = ΔH′×n _scale (8) ΔH _view is the number of pixels corresponding to the height difference ΔH on the screen. Similarly, for ΔA, first approximate its projection on the near clipping plane, and then obtain its projection size ΔA _view on the screen. ΔA'＝ΔA×(D _near /D _node ) ² ×sin(θ) ΔA _view = ΔA ′×n _scale (9) In the process of scene roaming, the angle of sight direction and the position of the camera from the node change in real time, calculate ΔHview and ΔAview in real time, if ΔHview<δH, and ΔAview<δA, then render this node, otherwise, this node is not is rendered, recursively judge its child nodes.

Images