Guillaume Damiand
email: guillaume.damiand@liris.cnrs.fr

Jarek Rossignac

Rasterized Planar Face Complex

Keywords: Planar polygonal meshes, Combinatorial maps, Compact representation, Topology preserving rasterization

We consider a Planar Face Complex (PFC). It is defined by the immersion of a planar and connected graph G, which comprises a set of vertices joined by curved edges. G decomposes the plane into faces that need not be manifold or open-regularized and may be bounded by a single loop edge. The PFC may, for example, be used to represent the complex street network of a city, the decomposition of a continent into countries, or the inhomogeneous structure made of a large set of regions of different materials possibly with internal cracks. The rasterized Planar Face Complex (rPFC) proposed here provides a compact representation of an approximation of a PFC, where the precise location of each vertex is quantized to the pixel that contains it and where the precise geometry of each curved edge is approximated by the ordered list (with possible repetitions) of the pixels traversed by (a chosen polygonal approximation of) the edge. We claim three key contributions: (1) The geometric error between a PFC and its rPFC is bounded by the pixel half-diagonal.

(2) In spite of such a drastic discretization of the geometry, the rPFC captures the exact topology of the original PFC (provided that no street lies entirely inside a single pixel) and supports standard graph traversal operators that permit to walk the loop of sidewalks along the streets that bound a face, to cross a street to the opposite sidewalk, or to cross streets in order while walking around their common junction. (3) The local connectivity and order information needed to provide the above functionality is stored at each pixel using only about 4 bits per crossing. We discuss the details of this representation, our implementation of its exact construction, four possible embodiments that offer different space/time efficiency compromises, experimental results, relations between rPFC and prior solutions.

Introduction

We propose a rasterized representation for planar face graphs. It may be used to model planar multi-material structures [START_REF] Kwok | Geometric analysis and computation using layered depth-normal images for three-935 dimensional microfabrication[END_REF], street networks [START_REF] Schmidt | Forest point processes for the automatic extraction of networks in raster data[END_REF], geological models [START_REF] Castanié | Volumeexplorer: Roaming large volumes to couple visualization and data processing for 945 oil and gas exploration[END_REF], or to describe accurate rasterization of planar maps of overlapping SVG elements [START_REF] Dalstein | Vector graphics complexes[END_REF]. Our representation, called rasterized Planar Face Complex (rPFC), stores only a few symbols for each pixel intersected by the edges. It supports exact topological graph traversal, even when a pixel overlap with several regions and contains several vertices.

Many previously proposed representations of planar face graphs either store the connectivity using integer references (a solution that has a high storage cost) or re-sample the graph at intersections with grid lines and discard the topology information about what happens inside a pixel.

Our solution unifies these approaches and provides a compact, per pixel representation. It provides a spatial decomposition of the connectivity of the graph into local (per pixel) descriptors that can be stored using a constant number of bits per pixel and streamed as needed. [START_REF] Kallmann | Star-vertices: a compact representation for planar meshes with adjacency information[END_REF] Our solution stores the topology of the original complex (assuming that no edge lies entirely inside a single pixel ) and is capable of representing sub-pixel connectivity. Hence, it should be distinguished from pure imagebased approaches that only store a face color or scalar 25 per pixel and from approaches that re-sample the graph at intersections with grid lines and that discard the original connectivity information. In fact, rPFC may be easily configured to extend these approaches by providing them with a space efficient representation of the exact topology 30 in each pixel.

The paper is organized as follows. In Sect. 2, we define the Planar Face Complex and the operators that we advocate for traversing its graph in a consistent manner. In Sect. 3, we outline our approach, explaining our exact ras-35 terization process, the computation of the local (per pixel) connectivity, and its compact encoding. In Sect. [START_REF] Dalstein | Vector graphics complexes[END_REF], we explain how we use it to support traversal of the original graph and ordered access to vertex and face attributes. In Sect. 5, we discuss four embodiment options, and some im- plementation details. In Sect. 6, we present experimental results. In Sect. 7, we compare our approach to relevant prior art. In Sect. 8, we summarize our contributions and outline future challenges. Consider a connected, curved, planar one-complex defined by a set of vertices in the plane and by a set of possibly curved and relatively open edges that connect them. We assume a proper embedding: (1) different vertices do not coincide, (2) each edge is manifold (free from self-intersection), and (3) the relative interior of each edge is disjoint from other edges and vertices. This set of edges and vertices is the embedding of a planar graph, G.

Background and terminology

Let U be the set theoretic union of the point sets of the 55 vertices and edges of G. Consider the complement, !U, of U. Each maximally connected component of !U is called a face. Note that a face is topologically open (i.e., it does not contain its boundary). Because we assume that G is connected, a face cannot have holes (i.e., its boundary must be connected). However, the boundary, B, of a face, F, may contain cracks (edges bounded by F on both sides) and pinch points (non-manifold vertices). G may have multi-edges (more than one edge joining any given pair of vertices) and loops (edges that start and end at the same vertex). All faces are bounded (i.e., fit in a disk of finite radius) except for one, which we call the external face.

We distinguish three types of vertices: dead ends (which bound a single edge of G), turns (which bound two edges) and junctions (which bound 3 or more edges).

We use the term Planar Face Complex (PFC) when referring to the faces, edges, and vertices of a decomposition of the plane by such a connected and curved, planar one-complex. An example is shown in Fig. 1. (their vertices). A pixel is stabbed when its intersection with G is not empty.

Our goal is to provide a compact representation of a

Sidewalks and operators

In this subsection, we describe a generic representation and associated traversal operators for PFC. We assume that the input PFC is formulated using such a representation (or an equivalent one) and we want to construct a 90 new rasterized representation of the PFC that supports the original traversal operators exactly, so that the application that uses these operators does not need to be changed.

We use the term street for each edge of G. With each street, we associate two sidewalks, one on each side. We 95 orient each sidewalk, S, so that its street, S.E , lies on the right of S (with respect to this orientation). We chose this non-standard terminology to distinguish the elements of G from those of the proposed representation. A sidewalk is stabbing a pixel, P, when its street, E, traverses P (splits 100 it into two or more faces).

We use S.V to denote the vertex at which sidewalk S starts and S.F to denote the face abutting to S. Note that the circularly ordered list of the sidewalks of a face forms an oriented loop that goes clockwise around that face.

105

We use three primary sidewalk operators that map a sidewalk S to a neighboring sidewalk (see Fig. The collection of these three operators defines a Combinatorial Map [START_REF] Lienhardt | N-Dimensional generalized combinatorial maps and cellular quasi-manifolds[END_REF][START_REF] Damiand | Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing[END_REF] (the tuple of the set of sidewalks and of the set of these operators is an algebra). Note that S.P is the inverse of S.N (i.e., S.N.P=S) and that S.O is an involution (i.e., S.O.O=S).

Various data structures have been proposed to support these operations. We discuss some in Sect. 7. Note that in 2D, a combinatorial map is equivalent to several other data structures such as Half-Edge, Corner Table, or Doubly Connected Edge List (DCEL) (see [START_REF] Damiand | Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing[END_REF]).

As done in several modern representations, we associate sidewalks with consecutive integer IDs. To simplify presentation, we will assume that S refers either to the abstract concept of a sidewalk or to the associated integer ID, depending on the context. Two arrays are often used to store the maps for two sidewalk operators: N[S] stores S.N and P[S] stores S.P. Trading processing time for storage, one may avoid storing P[S] explicitly and compute S.P, each time it is needed, by traversing the loop around S.F and returning the last sidewalk reached before returning to S.

Assuming that the IDs of S and of S.O are consecutive makes it unnecessary to store the "opposite" map explicitly in an array O[] (S.O may be computed from S as S+1 if S is even and S-1 otherwise).

Our goal is to provide a more compact, yet localized (per pixel), representation of the O[], P[] and N[] maps of a rasterized version of a PFC, which we call the rasterized Planar Face Complex (and abbreviate rPFC).

Rasterized Planar Face Complex (rPFC)

In this section, we describe the proposed approach for computing the rPFC of a PCF. Our solution is based on a numerically robust rasterization process that performs the following steps: (1) identify the set of pixels that contains (the edges and vertices of) graph G, (2) split stabbing (entering and leaving the same pixel) street by inserting split vertices, (3) order the entering sidewalks around each pixel, and, (4) for each pixel, store the "next" map between entering and exiting sidewalks in a compact form, as a sequence of symbols (which we call a word ) taken from a small codebook of 7 or fewer symbols.

Compact data structures for storing these words while providing fast access to neighboring pixels are discussed in Sect. 5.

Rasterization and refinement of G

During the rasterization step, for each vertex and for each edge of G, we identify the pixels that contain it. Furthermore, for each edge E of G, and for each pixel P that E exits or enters, we identify the roads through which it does so.

To avoid dealing with singular configurations where a vertex of G lies exactly on a road or crossroad and configurations where a street of G passes exactly through a crossroad or overlaps with a road, we use a special version of Simulation of Simplicity [START_REF] Edelsbrunner | Simulation of simplicity, a technique to cope with degenerate cases in geometric computations[END_REF] and bias our geometric tests so as to produce results consistent with a virtual perturba-165 tion of G that avoids such singularities (for example, when a street of G passes through a crossroad, we assume that it passes below it or on the right of it, depending on the street orientation. Similarly, when a vertex of G lies on a road or crossroad, we assume that it lies above, to the 170 right, or both, depending on the configuration).

In our implementation, we assume that each street is represented by an approximating manifold polygonal curve. We chose in this paper to describe the input PFC in terms of curved, rather than straight, streets to empha-175 size the fact that the sampling vertices along these curved streets are not considered as vertices of the graph G and to not decompose the curved street into small straight or curved edge segments each having different sidewalks. The exact geometry of a street, its sample points, and its de-180 composition into straight line segments will be lost during rasterization. Only the connectivity between faces, streets, and junction or turn vertices will be preserved.

Rasterization distinguishes two types of pixels: shared pixels (which contain a junction, dead-end, or turn vertex 185 of G or that are traversed by an street of G) and private pixels (which are each fully contained in a single face of the PFC).

To simplify explanations and terminology, in the remainder of the paper, we assume that we first construct a 190 refined version, R, of graph G. R is obtained by initializing it to G and by identifying all street segments where a street, E, splits (i.e., enters and leaves) a pixel, P. In each such segment, we insert (into R) a new split vertex, V, anywhere along that segment. A street E that splits R is defined implicitly by G and by the pixel grid. Although it could be constructed easily during the above rasterization process, it can be processed from its implicit form directly using the representation of G without the need for storing the split vertices explicitly. But for simplicity of presentation, we assume below that R has been constructed and that we have access to its sidewalks and to primary operators on them.

For clarity and conciseness, to distinguish G from R, we use the term dart when referring to the sidewalks of R and we will use the term edge when referring to a street of R. We will use lowercase letters for darts (for example, d) and for their operators (d.o, d.p, d.n, d.v, d.e, d.f). Note that to each sidewalk of G corresponds a set of one or more darts of R.

Our solution is based on the fundamental validity assumption: we require that no street of G (and hence no edge of R) lies entirely in a single pixel. There are two important benefits of enforcing this assumption and of considering R rather than G: [START_REF] Kwok | Geometric analysis and computation using layered depth-normal images for three-935 dimensional microfabrication[END_REF] No edge of R splits a pixel and (2) in each shared pixel, each connected component of R contains exactly one vertex of R.

A simple way to ensure that the pixel grid has sufficient resolution to preserve the original topology of G is to require that the pixel diagonal be smaller than the shortest edge of G.

Computing and ordering the crossings of a pixel

We process each shared pixel, P, one at a time. We identify each dart, d, of R that enters P (i.e., for which the starting vertex, d.v, lies outside of P and the ending vertex d.o.v lies in P). We compute the corresponding crossing (unique point where edge d.e crosses one of the roads in the boundary of P). We label the crossing using one of the 4 tags {'W','N','E','S'} depending on whether the crossing lies on the left, top, right or bottom road around P. Finally, we order the crossings of P clockwise around P, starting at the lower left crossroad of P.

To order the crossings along a road, we derive a rational expression for each crossing based on the standard slopeintercept formula. Assuming that the coordinates of the pixels are represented (or have been quantized) to 16 bits each, the exact ordering can be computed by performing only additions and multiplications on long integers.

Local dart indices

The integer symbol index , s, is used to identify the crossings and crossroads of a pixel P in clockwise order around the border of P, starting from the lower-left crossroad. Observe that each crossing corresponds to a set of two opposite darts, d and d.o, of R. Each dart, d, intersects two pixels: it exits a pixel, Q, and enters a road-adjacent pixel, P. Dart d has a different dart index in each one of these two pixels.

Consider a dart, d, that enters or exits pixel P. Let i(d,P) denote the dart index of d with respect to P. Note Note that four values of s are not associated with darts: they correspond to the crossroads of P.

A dart, d, that enters or exits pixel P is identified locally 265 in P by (i,T), where i is the dart index of d in P and T is the tag of the crossing associated with d in P, and globally by the triplet (i,T,P).

Conversion between local indices of a dart

Given the local index, i, of a dart, d, that enters (resp.

270 exits) pixel P with tag T, we want to compute the pixel Q that d exits (resp. enters) and the local index j and tag U of d in Q. Below, we describe informally the conversion procedure, (j,U,Q)=Convert(i,T,P), using an example that illustrates one of the possible configurations.

275

In Fig. 4, we know that dart (15,'E',P) exits pixel P, because it's dart index (i = 15) in P is odd. Since d exits P by the east side (T='E'), Q lies on the right of P and d enters Q by the west side (U='W'). We also know that j must be even. Below, we explain how we compute j.

280

Let B be the road between P and Q crossed by d. Let T (resp. U) be the tag associated with B in P (resp. Q). To compute j, we first compute:

• c = number of darts with tag T in P;

• x 0 = the local index of the first dart with tag T in P;

285

• e 0 = the local index of the first dart with tag U in Q. and then set j = e 0 + (x 0 + c -i -1).

Note that c, x 0 , and e 0 are always even. Thus, if i is even, then j is odd, and vice versa. In the example of

Encoding of the combinatorial map in a pixel

In the previous subsection, we explained how to convert between the two local representations of a dart in adjacent pixels. In this section, we propose a compact encoding of the primary operators (previous, opposite, and next) between darts that enter pixel P and darts that exit it.

Computing the local index of the opposite dart

Given dart, d, with local index i in P, we do not need to store an explicit encoding of the local index of the opposite dart, d.o, because, as explained earlier, it is defined implicitly as i + 1 (if i is even) or as i -1 (otherwise). Remember that darts d and d.o pass through the same crossing. Hence they have the same tag in P.

Compact encoding of the next dart map 305

Our encoding of the topology of R in a given pixel P builds a word (sequence of symbols) by considering, in clockwise order around the pixel, each crossing and each crossroad (pixel corner) and by assigning a symbol to each. The '+' symbols correspond to crossroads and is used to separate the crossings into the four sub-lists ('W', 'N', 'E', and 'S'). Furthermore, the occurrence of the 4 th '+' symbol always indicates the end of the word. Figure 5 shows the word for a particular pixel.

Our choice of the symbol assigned to each crossing and its computation, described below, encodes the connected components of R in P (i.e., the subsets of crossings that are connected by the portion of R in P) and makes it easy to compute the "next" map for each incoming dart. We use different symbols to distinguish crossings that open (i.e., start) a new connected component, that continue (i.e., add a branch to) the current component, and that close the current component. We use different symbols to distinguish between components connected to a split vertex added in R, components connected to an original junction or turn in G, and edges leading to a dead end.

For fully general PFC (with dead ends and turns), we define the following seven symbols:

• '=' : leads to a dead end Starting from the lower left corner, the first crossing is labelled '(', because it denotes the first encounter with a new component connected to a turn vertex.

340

The next crossing is also labelled '(', because we encounter a new component, this time connected to a junction vertex (our encoding does not distinguish explicitly between junction and turn vertices, but this distinction may be easily established during traversal by using the 345 "rotate" operators on the darts of the component to count the number of incident edges on the vertex to which the component is connected).

The next crossing is labelled '[', indicating that we have encountered a new component connected to a split vertex 350 (that is not a proper vertex of G, but was inserted during the construction of R).

The next crossing is labelled '=', indicating that we have encountered a new component, but that the dart, d, that enters P through that crossing is connected to a dead-end 355 vertex. Hence, the connected component is closed right away. At this point, we still have 3 active components.

The next crossing is labelled ']' to indicate that we close the component that was activated last (the component of the split vertex). At this point, we still have two active 360 components left.

The next crossing is labelled 'Y', indicating that it corresponds to an edge that is connected to the junction vertex, V, of the current (last opened) component. 'Y' also implies that this crossing is neither the first nor the last (in 365 the order around P) that is connected to V.

The next crossing is labelled ')', indicating that we have reached the last edge of the current component, which is the one connected to the valence 3 junction vertex.

The final crossing is labelled ')', indicating that we have 370 reached the last of the edges connected to the turn vertex.

Algorithm for computing a pixel's word

To compute the word (i.e., the array W[] of symbols) for a given pixel, P, we start with the following two steps:

(1) we identify all the edges of R that intersect P (remem-375 ber that each edge of R has a single crossing with the boundary of P) and (2) we order their crossing around P.

Then As we progress around the border of P, we keep track of the which road we are on and append to W a '+' each time we reach a crossroad. For each pixel, we store a compact encoding of its word.

To avoid the computational cost of visiting all edges of 390 R for each pixel, one may envision rasterizing R once and keeping track, at each pixel, of the edges that stab it. But such a solution would require a considerable amount of storage per pixel. Our implementation processes the pixels one row at a time, in top-down order, and maintains a list of active edges of R (those stabbing the current row).

The connectivity of R is fully represented by the list of shared pixels and by their words.

Geometric error bound

rPFC encodes the ordered sequence of pixels stabbed 400 by each street, E, of the original graph G. Let U be the union of these pixels and C be their center-points. U is the Minkowski sum of C with a pixel centered at the origin. Since, by construction, E is contained in U, the Hausdorff distance between E and C does not exceed half of the pixel 405 diagonal.

Adaptive version of rPFC

The presence of relatively short streets in G imposes an upper-bound on pixel size. When the exact topology must be preserved and simplification is not an option, such a constraint increases the pixel resolution and the number of stabbed pixels, hence also the storage and performance cost. To address this problem, we envision the option of a variable resolution rPFC. It stores a coarse resolution rPFC in which some of the stabbed pixels may be identi-415 fied. These are each split into 4 quadrants, for which the word encoding may be accessed or transmitted through progressive refinements. This can be repeated recursively (as in a quad-tree).

Usage of rPFC 420

Here, we explain how we use these words and simple local procedures to support all primary dart and sidewalk operators and to retrieve associations of color or other attributes with the faces, edges, or vertices of the PFC. Let k be the dart index of entering dart d with respect to pixel P and let T be its tag. Let c = k/2 be the symbol index of the corresponding crossing. Let s be the symbol associated with that crossing. When s is '[', d is the first dart around P that reaches a split vertex, v. We want to find the unique dart d.n that leaves v and is not d.o. To find the symbol index 450 c of its crossing, we imagine walking around the boundary of P clockwise until we find the matching ']' symbol. Here, the term matching implies that we skip over, possibly nested, matching pairs ('[',']' or '(',')') and ignore all other symbols. In practice, we do not walk around P, but 455 simply read the symbols in the order in which they appear in the word associated with P, starting from symbol index c = d/2 + 1. The dart index of d.n is 2c + 1. We also want to know the tag, T, of d.n. To compute it, we initialize it (T=U), and advance T to the next tag, each time we pass a '+'.

When s is '(', we follow the same process as for '['.

When s is ')', 'Y' or ']', we follow the same process, but walking backwards (i.e., reading the symbols in reverse order). Note that for ')' and 'Y', we need to stop either encounter first openings ('(' and '[') before the corresponding closings. So, in Algo. 2, we keep the nesting count, n, of active components ('(' and '[' increment n and ')' and ']' decrements it) and return the index of the outgoing dart of the crossing for which n = 0.

When entering dart d correspond to a closing, we must move counterclockwise, skip over pairs of matching closings and openings, until we find an opening that matches the closing of d. For conciseness, in Algo. 2, we use the same loop to handle both clockwise and counterclockwise traversal. To differentiate them we use a variable dir. Furthermore, because openings increment the counter n and closings decrement it, when walking counterclockwise, n is negative. Also note that we use the test (n = -1 and s='Y') to identify the first 'Y' crossing encountered while 485 walking counterclockwise from d.

Intra-pixel "previous"

Given the dart index of a dart, d, that exits pixel P, computing d.p is done by using exactly the same principle as in Algo. 2, but changing the direction of the traversals.

Inter-pixel operators

The previous subsection focused on computing intrapixel operators: dart indices for darts d.p, d.o, and d.n that lie in the same pixel as dart d. Here, we discuss interpixel operators for next, previous and opposite.

495

Each dart, d, has two global descriptors in an rPFC: (x,T,P) in the pixel P that it exits and (e,U,Q) in the pixel Q that it enters. Remember that x is odd and e is even. By convention, we associate dart d with (x,T,P) because pixel P contains the vertex where d starts. 500 So, d.n is obtained by starting with the descriptor (x,T,P) of d, using the Convert() procedure, given in Sect. 3.2.2, to obtain descriptor (y,V,Q), and performing the intra-pixel next operator on (y,V,Q) in Q.

Similarly, d.p is obtained by starting with the descriptor 505 (x,T,P) of d, performing the intra-pixel previous operator on (x,T,P) and then using Convert() on the result to obtain descriptor (y,V,Q) in Q. Finally, d.o is obtained by starting with the descriptor (x,T,P) of d, using Convert() to obtain descriptor 510 (y,V,Q), and performing the intra-pixel opposite operator on (y,V,Q) in Q.

Mapping between darts of R and sidewalk of G

Sidewalks of G and operators on them can be implemented using darts of R and their operators. Remember 515 that each sidewalk of G is decomposed into a series of one or more darts of R, that are connected by split vertices. We associate a sidewalk, S, of G with the first dart, d, of R in the corresponding list. Hence, S inherit the vertex and face of d. Let dart(S) denote the dart in R that is as-520 sociated with sidewalk S of G. Similarly, let Sidewalk (d) denote the sidewalk of G associated with dart d of R.

Let d.e denote the last dart of a series that starts at d and contains all the darts of the same sidewalk of G. d.e is computed by iterating "next" until we reach a dart with 525 an end vertex that is not a split. Similarly, d.b is the first dart of a series that ends at dart d and contains all the darts of the same sidewalk (d.p is computed by iterating "previous" until we reach a dart with a beginning vertex that is not a split).

530

We can implement the primary operators on sidewalks as follows:

• S.N = Sidewalk(dart(S).e.n)

• S.O = Sidewalk(dart(S).e.o)

• S.P = Sidewalk(dart(S).p.b) 535 Hence, we are able to use the S.P, S.O, and S.N operators on G from the information contained in the words stored at the shared pixels of the proposed rPFC.

Indexing vertices, edges and faces

In some applications, it is desired to associate an attribute (color or property) with each face, edge, vertex. In modern data structures for face meshes, this is often done for face attributes by associating consecutive integer IDs with the faces and by storing the attribute values in an array indexed by the face IDs. For example F[f] may be the value of face attribute (say color) of face with ID f. Let us assume that such an array F[] exists and is controlled by the application.

The question that we address here is not the cost of storing the attribute values, but the space and time cost of using the rPFC to associate each dart, d, of R with the face ID, d.f, of the incident face.

We also must address the cost of associating each face, f, with at least one dart, d, on its boundary, such that d.f=f. We propose a partial solution inspired by previous work on mesh compression [START_REF] Rossignac | Edgebreaker: Connectivity compression for triangle meshes[END_REF][START_REF] Gurung | Zipper: A compact connectivity data structure for triangle meshes[END_REF][START_REF] Gurung | LR: Compact connectivity representation for triangle meshes[END_REF], where the faces IDs are assigned based on a specific traversal order of the graph. For example, we can use the depth-first traversal proposed in [START_REF] King | Guaranteed 3.67V bit encoding of planar triangle graphs[END_REF] and assign the next available integer f to each face when it is first encountered. A fast approach that only requires a relatively shallow stack requires storing a onebit marker with each vertex to indicate whether the vertex has already been visited.

This approach allows to use the attribute F[f] when processing (for example coloring) the corresponding face. The solution can also be used to support the picking of a face by clicking on a private pixel (it suffices to use the above approach to render each face with a color that encodes its index and retrieve the color of the picked pixel). The advantage of this solution is that it does not require any additional storage (except of course for the array F[] of attributed). Similar solutions may be used to associate attributes with the darts, vertices, and edges of R and hence of G.

We see two important drawbacks of such a partial approach: (1) Accessing (measuring or displaying) a particular vertex, edge, or face requires performing the traversal of the entire graph. (2) When an algorithm uses the dart operators to perform a different or a partial graph traversal and arrives at a dart d, we do not have direct access to its ID, nor to the IDs of its vertex d.v or face d.f. Of course, these could be retrieved at no additional storage cost by performing the depth first traversal and stopping when it reaches d, but this cost would raise the computational cost of the algorithm and would lower its performance.

Data structures for rPFC

In this section, we first discuss strategies for compact representations of individual symbols and words and then outline four different architectures for rPFC representations: (1) A matrix with constant size entries, one per pixels, that has many advantages, but requires a large amount of storage in configurations with a relatively large proportion of private pixels, (2) A pixel adjacency graph with variable size representation of words that requires storing with most shared pixels the addresses of their neighbors, (3) A version of the above that does not store private pixels and is attractive or modeling street maps or river graphs, and (4) A compact version of the above where addresses The maximal number of crossings, m, is 4. Thus, each word, W[i,j], is stored using 25 bits (addresses are multiples of #15 in hexadecimal). Words starting with '1' identify stabbed pixels.

of neighbors are not stored, but need to be retrieved by a partial traversal of the corresponding row of pixels. 600

Compact encoding of symbols and words

The set of symbols used in an rPFC depends on the topology of G and on the application's needs. But in any case, we can replace ']' by ')' because, without ambiguity, each closes the component opened last either by '[' or by 605 '('. When using the remaining 6 symbols "()Y[=+", the symbol entropy ranges from 1.3 to 1.9 depending on the model and pixel size. It averages 1.5 bits per symbol for targeted applications.

Rather than using Huffman or entropy codes, we use

V1: Matrix of fixed size record

In the V1 architecture, the rPFC is encoded by a matrix , W [], of words, one for each pixel (shared or private) (see Fig. 6). Each word, W[i,j], is stored using 4m + 5 bits, where m is the maximum of the numbers of cross-625 ings per pixel (we use 1 bit to differentiate private from shared pixels, and for each shared pixel, we use 1 bit for each one of the four '+' symbols and 4 bits for each one of the other symbols). In our experiments, about 98% of pixels have no more than 6 crossings (average for all our 630 models and all our different number of pixels, see Sect. 6) and hence could be encoded in 32 bits, about 99% of pixels have no more than 14 crossings and hence could be encoded in 64 bits, but, in some models, a minute fraction of pixels have more crossings (up to 18 in the worst case in 635 our experiments) and should be encoded using an exception mechanism. For private pixels, this constant storage 1 @N @S @N @S @N @S @S @E @E @S @E @E @E @E @S 0 @N @S @S @E @N @S @N @E @N @E @E @N @E @E @E @N 6 encoded with the V2 architecture. Red (resp. blue, green) arrows represent @S (resp. @N, @E) addresses.

No information is stored for private pixels, except for a 1 bit mask.

(minus the one bit) may be used to store the face ID and possibly the distance to the boundary or some other scalar field.

The main properties of V1 are: (1) identification of private pixels and face membership classification at constant cost, and (2) constant cost access to the encoding W [i,j] of the word of each shared pixel during graph traversal;

V2: Pixel adjacency graph with variable size records

In the V2 architecture, the rPFC is encoded by an array , R[], of bitsets, one for each row (see example in Fig. 7). Each bitset, R[j], is the concatenation of the encoding of all words of pixels in row j. Each word is now encoded using variable size records. To support constant time cost access to neighboring shared pixels during graph traversal, we store, at each shared pixel (i,j), in addition to its private/shared bit and to its word, up to three references: (1) the address (beginning of the descriptor), @E, of the previous pixel (i-1,j) in row j, (2) the address, @S, 655 of the south neighbor (i,j + 1) in row j + 1, and (3) the address, @N, of the north neighbor (i,j -1) in row j -1. @E is encoded as a relative displacement (the bit-length of the descriptor of pixel (i -1,j)). @N and @S are absolute bit-indices in the corresponding rows. Each address is 660 encoded using a minimal, although known, number of bits (typically 6 for @E and 12 for @S and @N) that depends on the length of each row and on the maximum record size. Each reference is only encoded when the corresponding neighbor pixel is shared. Note that we do not need to store the address of pixel (i + 1,j) to access it from pixel (i,j). Even though the length of the word of (i,j) is not fixed, and hence, not know a priori, it can be easily established be identifying the last '+' in that word.

We use a fixed format for private pixels. It includes a 0 to distinguish them from shared ones and also a fixed (possibly null) number of bits that may be used to identify the face or material type and optionally to store a scalar field, which may for example capture the distance from the boundary of the face or some physical property, such 675 as heat.

V3: Version of V2 without private pixels

The V3 architecture, is almost identical to V2, but does not store anything for private pixels. It is particularly useful for applications which do not support face membership 680 or material queries and are instead focused on the traversal and analysis of graph G. With additional storage per face and with additional cost per query, V3 could be extended to support such queries. The layout for the V3 architecture is the one shown in Fig. 7, but without the 685 '0' pixels.

V4: Version of V3 without addresses

The V4 architecture is a variant of V3 where we trade performance for space. Instead of storing for each shared pixel up to three neighbors' addresses (as explained for 690 V2), we recompute these addresses when needed. This solution is based on the key observation upon that the @E, @N, and @S addresses can be computed (each time they are needed) by starting from the beginning of the corresponding row (j + 1, j, or j -1) and by walking East 695 by the desired number of records.

We could store the shared/private bit for each pixel to facilitate this process, but we do not have to. Indeed, for row j, we simply walk until we encounter a pixel that has (i,j) as East neighbor. To identify the south neighbor, 700 we walk along row j + 1 and count the number of visited shared pixels that have a north neighbor (that have at least one crossing on their north road). We stop when this count matches to the number of pixels along row j, from pixel (0,j) to pixel (i,j), that have a south neighbor. The 705 layout for the V4 architecture is the one shown in Fig. 7, but without the '0' pixels and without the @S, @N, and @E addresses.

Indexing vertices and faces

In some applications, it is desired to provide direct ac-710 cess from a face to one of its darts and inversely, from a dart to its face. To do so, for each face, f, we walk along the loop of its darts and identify the root dart (the dart d with the lexicographically smallest index composed of the fixed-length strings representing coordinates of the 715 pixel containing d.v and of the dart index in that pixel). We use array Root to encode the root dart of face f as Root[f]. This provides constant cost access from f to d. Now, to compute d.f, we use the next operator to walk from d around the loop of f. During that walk, we identify 720 the root dart r of f. Then, we search f such that Root[f]=r. To reduce the cost of the search from O(F ) to O(logF ), where F is the face count, we sort the face indices so that the array Root is sorted.

Experiments

725

We have computed rPFC representations for two different types of 2D face meshes. 2D Voronoi diagram of random points and GIS data of countries. To ensure that the input data satisfies our constraint that no edge lies entirely in a pixel, in a preprocessing step we simplify the input face mesh (one could use a variant of [START_REF] Rossignac | Multi-resolution 3d approximations for rendering complex scenes[END_REF] or a feature preserving simplification [START_REF] Salinas | Structure-aware mesh decimation[END_REF]).

In these experiments, we use the encoding given in Sect. 5.1, with 1 bit for '+', 3 bits for other symbols "(Y)[", and without '=' for dead-ends.

Data sets used in experiments

Firstly, we use face meshes computed as 2D Voronoi diagrams of random points generated in a disk of radius 500. Five face meshes were generated from 1,000, 2,000, 4,000, 8,000 and 16,000 points. In a post-processing, 20% of edges are randomly removed from the 2D Voronoi diagram, in order to decrease the face mesh regularity. The face mesh obtained for 2,000 points is shown in Fig. 8(a).

The number of vertices of these face meshes are respectively 1,550, 3,174, 6,479, 13,094 and 26,244; the number of edges 1,945, 3,976, 8,113, 16,439, and 33,032; and the number of faces 399, 806, 1,644, 3,359, and 6,810.

Secondly, we used geographic information system (GIS) data obtained from http://www.gadm.org/ web site, which provides a spatial database of the location of the world's administrative areas. We used Brasil, China, France, England, Russia and USA countries (see Fig. 8(b) for the USA data set). The files are provided in the Shapefile format, a popular geospatial vector data format for GIS softwares.

The number of vertices of the original meshes are respectively 560,823, 815,556, 246,880, 424,717, 1,662,902 and 57,406; the number of edges are 560,882, 815,622, 247,606, 424,993, 1,663,102, 57,506; and the number of faces are 849, 2,021, 763, 1,113, 5,899, 345.

In both cases, we computed our four versions of rPFC representations, for numbers of pixels in the horizontal direction equal to 128, 256, 512, 1024, 2048, 4096, 8192, 16384 (while computing automatically the number of pixels in the vertical direction).

The entropy per symbol depends on the model and the pixel sizes. In average for the five synthetic face meshes, it starts from e = 1.9 for 128 pixels in the horizontal direction and decreases to e = 1.3 for 16,384 pixels. The entropy per words, in average for the five models, starts from e = 6.6 770 and decreases to e = 2.6. Entropy per words decreases when the number of pixels increases because the number of different words does.

In average for the six GIS maps, the entropy per symbol starts from e = 1.9 for 128 pixels in the horizontal direction 775 and decreases to e = 1.4 for 16384 pixels. The entropy per words, in average for the six models, starts from e = 5 and decreases to e = 3. The maximal size of pixel words is between 6 and 16, and is equal to 6.04 in average.

Storage analysis 780

In Table 1, we compared the storage used in the proposed data structures. Column CM reports storage for a combinatorial map representation of the simplified version of G. It stores, three references (d.n, d.v, and d.f) for each dart, d, two integer pixel coordinates for each vertex, and 785 one dart reference for each face. Column CM S reports storage for a rasterized version of CM , augmented with a bit mask that identifies shared pixels, and, for each shared pixel, with a list of references to the vertices it contains. Although the largest of all four, storage for V1 is smaller 790 than uncompressed (32 bits per pixel) image format, except at low resolution. V2 uses between 35% and 80% less storage than CMS, while providing more functionality. V3 is between 80% and 95% more compact than CMS. It is also more compact than CM for GIS models. V4 is 795 the most compact. It requires between 85% and 99% less storage than CMS. For the GIS maps, it uses less storage than CM. For our synthetic meshes, it becomes more storage expensive than CM at high pixel resolution, when average-length edges stab several pixels.

800

To further reduce storage, we identify the 2 k most frequent words and use k + 1 bits to encode each of them (using the leading bit to distinguish them form others). We pick k to minimize total storage (typically 1 ≤ k ≤ 6). This trivial compression reduces storage by about 5% for V2, 20% for V3, and 58% for V4.

Comparison of traversed elements

We did a second experiment in order to compare our different representations in term of operations. For that, we iterated through all the faces of each rPFC, and for each one, we traversed through its contour by using the next operation. During this traversal, we computed the number of accessed pixels. Results are given in Table 2 for the synthetic face meshes and the GIS maps.

We can see on these results that the number of traversed pixels is much more important when iterating through the V4 version than for the V3 representation. Indeed, each time we need to move to the pixel above (resp. below) of the current pixel, pixels in the previous (resp. next) row are iterated starting from the beginning of the row. In average, V4 traverses between 10 and 58 times the number of pixels traversed by V3. This implies of course a big overhead for operations, but this is the price to pay in order to have a very compact representation.

In order to limit this overhead, it is possible to store 825 traversed elements during an operation and use this cache when possible instead of recomputing the next, previous or opposite relations.

Relation to prior art

We divide relevant prior art into four categories: ( The partition of a portion of the plane into regions (faces), each assigned a different color, may be represented as a rasterized image: coloring each pixel based on the region that contains its center. The image may be represented compactly using a fixed number of bytes per pixel.

More compact encodings include RLE (Run Length Encoding) and quadtree [START_REF] Samet | Connected component labeling using quadtrees[END_REF]. Such a digitization of a PFC not only suffers from the same quantization error as the rPFC, but also eliminates all cracks and dead ends and hence cannot be used to represent street networks. Furthermore it may disconnect regions at constrictions thinner than a pixel and offers no bound on the Hausdorff error between the original boundary of a face and the boundary of its rasterized version. The proposed rPFC does not suffer from these shortcomings and offers from the same localization capabilities (constant cost computation of the face ID for a query point in a private pixel) and streaming capabilities.

Graph connectivity

Various data structures for polygon meshes have been proposed over the last few decades: [START_REF] Baumgart | Winged-edge polyhedron representation[END_REF][START_REF] Mäntylä | An Introduction to Solid Modeling[END_REF][START_REF] Alumbaugh | Compact array-based mesh data structures[END_REF][START_REF] Dobkin | Primitives for the manipulation of three-dimensional subdivisions[END_REF][START_REF] Castelli Aleardi | Succinct representations of planar maps[END_REF][START_REF] Kallmann | Star-vertices: a compact representation for planar meshes with adjacency information[END_REF][START_REF] Kettner | Using generic programming for designing a data structure for polyhedral surfaces[END_REF][START_REF] Snoeyink | Tripod: a minimalist data structure for embedded triangulations[END_REF][START_REF] Sieger | Design, implementation, and evaluation of the Surface mesh data structure[END_REF]. Some are discussed in [START_REF] Botsch | Polygon Mesh Processing[END_REF]. Many of them store Geometry (the coordinates of each vertex) and, Connectivity (references to d.v, d.f, d.n, d.p, and d.o for each dart). More compact representations have been proposed for polygon graphs [START_REF] Blelloch | Succinct representations of separable graphs[END_REF][START_REF] Blandford | Compact representations of simplicial meshes in two and three dimensions[END_REF] and for triangle meshes [START_REF] Campagna | Direct edges -a scalable representation for triangle meshes[END_REF][START_REF] Castelli Aleardi | Catalog-based representation of 2D triangulations[END_REF][START_REF] Castelli Aleardi | Explicit array-based compact data structures for triangulations[END_REF][START_REF] Gurung | SQuad: 1020 Compact representation for triangle meshes[END_REF][START_REF] Gurung | LR: Compact connectivity representation for triangle meshes[END_REF][START_REF] Yamanaka | A compact encoding of plane triangulations with efficient query supports[END_REF][START_REF] Alumbaugh | Compact array-based mesh data structures[END_REF][START_REF] Luffel | Grouper: A compact, streamable triangle mesh data structure[END_REF]. Their connectivity storage cost per triangle is only a few times larger than that of compressed representations [START_REF] Rossignac | Edgebreaker: Connectivity compression for triangle meshes[END_REF][START_REF] Rossignac | 3D mesh compression[END_REF][START_REF] Maglo | Hudelot, 3D mesh compression: Survey, comparisons, and emerging trends[END_REF]. Even though some variants have been proposed recently that support streaming [START_REF] Gurung | SQuad: 1020 Compact representation for triangle meshes[END_REF]35] or graph editing [START_REF] Aleardi | ESQ: Editable squad representation for triangle meshes[END_REF], most these compact representations do not support efficient connectivity editing or streaming, because they assign vertex and triangle IDs in a specific order, and because they use global ID. Furthermore, they do not support spatial indexing.

The rPFC solution proposed here strives to unify and combine the best features of the above two categories of representations, but without resorting to the systematic resampling of the PFC edges that is preformed by approaches in the following two categories and that may re-875 sult in drastic and unbounded connectivity changes.

Crossings with grid lines

Several approaches insert crossings where edges of G intersect inter-pixel grid lines and recompute or define implicitly a simplified (vertex free) topology of G inside each pixel (or voxel) [START_REF] Benouamer | Bridging the gap between CSG and Brep via a triple ray representation[END_REF][START_REF] Shade | Layered depth im-1045 ages[END_REF] or obtain a simplified surface through edge collapses that eliminate all original vertices [START_REF] Szymczak | Piecewise regular meshes: Construction and compression[END_REF].

In particular, the Layer Depth Image (LDI) and their "Hermite" extensions, the Layer Depth-Normal Image 885 (LDNI) representations accelerate Boolean operations and other analysis and manufacturing planning tasks [START_REF] Kwok | Geometric analysis and computation using layered depth-normal images for three-935 dimensional microfabrication[END_REF].

rPFC can be trivially augmented by associating with each crossing its geometric position along the corresponding road (for example encoded using 6 bits). In that case, rPFC could be viewed as an extension of the LDI model, where, in addition to the crossings, we encode the explicit connectivity inside each pixel, and hence do not need to infer it from the crossing or from the associated tangents.

A vertex per shared pixel 895

Arguably the dual of the above category is the set of approaches that generate a single vertex per shared pixel (or voxel) either via resampling, via edge contraction simplification, or by computing the dual of results obtained by solutions in the previous category [START_REF] Ju | Dual contouring of hermite data[END_REF][START_REF] Zhang | Dual contouring with topology-preserving simplification using enhanced cell represen-1055 tation[END_REF][START_REF] Campen | Dual loops meshing: Quality quad layouts on manifolds[END_REF]. 900 rPFC could be viewed as an extension of such dual models: for a modest cost, it makes it possible to encode explicitly a variety of topologies with possibly multiple components and vertices per pixel.

A hierarchical structure (octree, kd-tree) is sometimes 905 used to reduce storage cost for the private pixels (voxels) [START_REF] Kim | Multi-phase fluid simulations using regional level sets[END_REF] or to support progressive refinements, of the connectivity [START_REF] Kraemer | Extension of half-edges for the representation of multiresolution subdivision surfaces[END_REF] or of the topology [START_REF] Valette | Progressive lossless mesh compression via incremental parametric refinement[END_REF], or to support adaptive resolution [START_REF] Gandoin | Progressive lossless compression of 1070 arbitrary simplicial complexes[END_REF].

Summary and conclusion 910

The proposed rPFC approximates vertex and curved edge geometry of a PFC by the list of pixels they intersect, but represents graph connectivity exactly and hence supports exact topological graph traversal. It can accommodate non trivial topology in a pixel, including multiple 915 vertices and multiple connected components, but assumes that no edge fits entirely inside a single pixel. If this happens, the invalid model must be simplified by a set of edge contractions or the pixel size must be reduced.

The rPFC decomposes the graph connectivity descrip-920 tion into a set of local maps, one per pixel, and stores each map using a very compact representation. As such, it offers a new paradigm that makes it possible to provide spatial indexing to both quantized geometry and exact topology of a valid PFC that may be complex both 925 combinatorially and topologically. Future challenges include extensions to irregular grids, multi-resolution grids, and, of course, 3D.

40

  Author version of paper "Rasterized Planar Face Complex; Damiand G., Rossignac J.; Computer-Aided Design (CAD), Volume 90, pages 146-156, September 2017". Thanks to Elsevier.

Figure 1 :

 1 Figure 1: A Planar Face Complex (PFC) with 14 curved edges, 5 faces, a non-manifold vertex (B) on the boundary of the external (infinite) face, a crack (from C to E), and a dead-end vertex (I).

45 2. 1 .

 451 Planar Face Complex (PFC)

Figure 2 :

 2 Figure2: Primary sidewalks operators in a PFC map a sidewalk S to the opposite one, S.O on the other side of the curved street, to the next, S.N, along the clockwise sidewalk loop of face S.F, and to the previous one, S.P along that loop. The derived rotate operator, S.R, maps S to the next sidewalks that emanates from S.V and is obtained by rotating clockwise around S.V. Note that S.R may be derived as the composition S.P.O of the previous and opposite maps.

  2): • S.N = next sidewalk along the loop of S.F • S.P = previous sidewalk along the loop of S.F • S.O = opposite sidewalk (on the other side of S.E) 110

Figure 3 :

 3 Figure 3: Refined graph R with original vertices of G shown as disks and inserted split vertices shown as diamonds. Note that pixel (1,1) is split twice by the same street, (A,B), of G, which in R is replaced by 4 streets: (A,2), (2,1), (1,3), and (3,B).

Figure 4 :

 4 Figure 4: Local indices of darts in adjacent pixels. Notice that two indices are skipped for each crossroad. Global dart identifiers (15,'E',P) and (4,'W',Q) refer to the same dart, which exits P by the East side and enters Q from the West side.

Fig. 4 ,Figure 5 :

 45 Figure 5: A pixel with 8 crossings. Its next map is encoded by the word "(([=+]+Y+))+".

•

  '+' : denotes crossroad • '[' : starts a component connected to a split • ']' : ends a component connected to a split • '(' : starts a component connected to a junction • 'Y' : adds a branch to a junction 335 • ')' : ends a component connected to a junction An example is shown in Fig. 5.

4. 1 .

 1 Using pixel words for supporting dart operators in R 425 We show here how to use the word (the content of array W) of a pixel P to compute the dart indices of d.o, d.n and d.p from the dart index of an entering dart d. 4.1.1. Intra-pixel "opposite" Let k be the dart index of a dart d that enters pixel 430 P. The dart index of d.o is k + 1 if k is even and k -1 otherwise. Moreover, d.o and d have the same tag. 4.1.2. Intra-pixel "next" Given the local dart index, k, of a dart, d, that enters a pixel, P, we use the following procedure to compute the 435 local index of d.n that exits P, and the tag of d.n. Note that the starting vertex of d.n is in P, because any dart of R that enters a pixel P reaches a vertex of R in P. Computing d.n requires distinguishing different cases. A relatively simple algorithm is presented in Algo. 2 and 440 explained below.

445

  When s is '=', d reaches a dead end and hence d.n is d.o. Therefore, the dart index of d.n is k + 1.

Figure 6 :

 6 Figure 6: Example of rPFC (grey) encoded with the V1 architecture.The maximal number of crossings, m, is 4. Thus, each word, W[i,j], is stored using 25 bits (addresses are multiples of #15 in hexadecimal). Words starting with '1' identify stabbed pixels.

Figure 7 :

 7 Figure 7: rPFC of Fig.6encoded with the V2 architecture. Red (resp. blue, green) arrows represent @S (resp. @N, @E) addresses. No information is stored for private pixels, except for a 1 bit mask.

Figure 8 :

 8 Figure 8: (a) One face mesh obtained from a Voronoi 2D diagram of 2,000 random points, where 20% of edges are randomly removed. (b) The GIS map of USA states.

  , we visit them in order around P and, for each incoming dart, d, we use the dart operators in R to assess what kind of a component (dead end, split, junction or 380 turn) d connects to and whether d opens, continues, or closes a component. Depending on these findings, we set the symbol of the corresponding crossing and add it to the word of P (write it into the next available entry of the W array). The details are shown in Algo. 1.

	Algorithm 1: Symbol of a dart
	Input: d: a dart that enters into pixel P.
	Output: symbol associated with the crossing of d.
	d2← d;
	repeat
	d2← d2.n;
	until d2.n.v is not in pixel P ;
	if d=d2.o then return '=';
	else if isSplitVertex(d.n.v) then
	if i(d.n,P)>i(d,P) then return '[';
	else return ']';
	else if i(d2,P)>i(d,P) then return '(';
	else
	d2← d.o;
	repeat
	d2← d2.p;
	until d2.p.v is not in pixel P ;
	if i(d2,P)>i(d,P) then return 'Y';
	else return ')';

Table 1 :

 1 Memory space for the synthetic face meshes (first 8 rows) and for the GIS maps (last 8 rows). Each value is the mean for the all tested model (five generated face meshes or six GIS maps). #pixel is the number of pixels; #simplif-v the number of vertices of the simplified mesh; #split-v the number of split vertices added by the rasterization. CM (resp. CMS) is the computed memory size of an equivalent representation of a combinatorial map of the simplified version of G (resp. R). CMS includes, for each pixel, the list of vertices of R that it contains. V1, . . . , V4 are our different representations, using frequent words. V2 versions do not store any information for private pixels, which are thus encoded by only 1 bit. Each memory size is given in kilo-bytes (kb columns) and in bit-per-pixel (bps columns).

		#pixels	#simplif-v #split-v	CM	CMS		V1		V2		V3		V4
					kb	bps	kb	bps	kb	bps	kb	bps	kb	bps	kb	bps
	Synth. face meshes	128×128 256×257 512×514 1,024×1,028 2,048×2,055 4,096×4,111 8,192×8,221 16,384×16,443	2,057 4,710 7,200 8,650 9,373 9,741 9,919 10,015 1,840,125 9,532 24,787 54,532 112,336 227,575 457,976 918,663	50 115 163 189 201 208 211 212 0.0065 92,244 2.8 756,396 24 195 97 76 14 546 68 272 5.2 1,518 47 949 1.5 3,806 29 3,359 0.39 7,905 15 13,375 0.10 16,871 8.2 53,461 0.03 37,883 4.6 189,101	38 34 29 26 26 26 23 10,731 1.3 2,443 34 16 34 92 11 88 200 6.2 170 446 3.5 318 1,142 2.2 615 3,302 1.6 1,240 23 38,107 1.1 5,004	17 11 5.3 2.5 1.2 148 16 39 60 90 0.60 265 0.30 498 0.15 964 0.029 8.2 4.8 1.9 0.70 0.29 0.13 0.06
		128×69	577	1,403	8	7.3	24	22	32	29	5 4.5	4	3.7	2	1.7
		256×138	1,509	3,256	22	5.1	63	14	126	29	13 3.0	9	2.0	3	0.80
	GIS maps	512×275 1,024×549 2,048×1,097 4,096×2,194	3,501 7,402 14,450 26,204	7,429 16,666 36,642 78,544	49 102 215 377	2.9 1.5 0.79 0.34	149 8.7 363 5.3 1,188 4.3 3,486 3.2	499 1,991 8,778 35,107	29 29 32 32	36 2.1 109 1.6 367 1.3 1,301 1.2	19 41 91 194	1.1 0.60 0.33 0.18	7 14 28 58	0.39 0.20 0.10 0.05
		8,192×4,387	46,093	165,303	640	0.15	9,425 2.1 127,229	29	4,819 1.1	412	0.09 117	0.03
		16,384×8,774	77,963	341,157 1,591	0.090 27,996 1.6 508,901	29 18,449 1.0	853 0.049 231 0.013
			Synthetic face meshes						GIS maps
		#pixels	V3			V4			#pixels		V3			V4
		128×128	7,215	44%	201,576 1,232%		128×69		862	9.8%	11,315 129%
		256×257	17,914	27%	759,020 1,156%		256×138		1,895	5.4%	29,100	82%
		512×514	37,208	14%	1,940,132	738%		512×275		4,177	2.9%	74,386	53%
		1,024×1,028	74,027	7.0%	4,122,003	392%		1,024×549		9,182	1.6%	186,591	33%
		2,048×2,055	147,380	3.5%	8,428,277	200%	2,048×1,097		19,876 0.89%	448,478	20%
		4,096×4,111	294,040	1.7% 17,030,686	101%	4,096×2,194		42,038 0.47% 1,022,653	11%
		8,192×8,221	587,287 0.87% 34,247,793	51%	8,192×4,387		87,320 0.24% 2,247,795	6.3%
		16,384×16,443 1,173,840 0.44% 68,733,223	25%	16,384×8,774 178,425 0.12% 4,793,714	3.3%

Table 2 :

 2 Comparison of performance between V3 and V4, showing the total number of pixels accessed during a walk around each face of G.

several pixels will be split several times, once per splitting segment. Note that a curved street may split the same pixel more than once as shown in Fig.3at pixel (1,1) for the left-most of the two streets between vertices A and B. These insertions do not alter the geometry of the graph, 200 but increases the street count.

Acknowledgements

This project received funding from the European Unions 930 Horizon 2020 Research and Innovation program under the Marie Sklodowska-Curie (grant 659526).