Introduction
MultiSurface
, CompositeSurface
, Solid
, MultiSolid
, CompositeSolid
. Unlike other implementations, val3dity fully supports interior boundaries for both surfaces and for solids, and also the interactions between different solids can be validated. The only restriction is that edges need to be linear, and surfaces planar. This is a common restriction in the GIS world (CityGML does not support curves arcs and parametric surfaces) and primitives from other fields (IFC) can always be discretised into linear/planar ones. Furthermore, val3dity supports a few GIS input formats, the validation reports have been designed to help users easily identify errors, and the validation of CityGML BuildingParts
(namely their topological interaction with others) is now supported.Background
Definitions of 3D primitives in ISO19107
GM_Point
, a 1D a GM_Curve
, a 2D a GM_Surface
, and a 3D a GM_Solid
. A d-dimensional primitive is built with a set of (d−1)-dimensional primitives, e.g. a GM_Solid
is formed of several GM_Surfaces
, which are formed of several GM_Curves
, which are themselves formed of GM_Point
.-
aggregate: a collection of primitives of the same dimensionality that is simply used to bundle together geometries. An aggregate does not prescribe any topological relationships between the primitives, they can overlap or be disconnected.
-
composite: a collection of d-dimensional primitives that form a d-manifold, which is a topological space that is locally like a d-dimensional Euclidean space (\(\mathbb {R}^{d}\)). A concrete example would be a composite of surfaces (2-manifold): each surface is a 2-manifold, and all the surfaces together also form a single 2-manifold. This implies that they are not allowed to overlap and/or to be disjoint.
Definitions of 3D primitives in val3dity
-
GM_Curves
can only be linear -
GM_Surfaces
can only be planar
Multi*
and a composite is a Composite*
. The following 3D primitives are thus supported by val3dity:
-
MultiSurface
-
CompositeSurface
-
Solid
-
MultiSolid
-
CompositeSolid
LinearRings
are linear GM_Curves
, and Polygons
are planar GM_Surfaces
.
CompositeSurface
that is closed (it does not contain any boundary; it is ‘watertight’) and orientable is referred to as a Shell
. Shells
are the basis to define the boundaries of a Solid
; notice that in the figure the Solid
has two Shells
: one representing the exterior boundary (the cube in grey) and one the interior one (the cube in light blue), the latter defines a ‘void’ in the solid. The boundaries of a Solid
are allowed to interact with each other under certain rules, these are explained in details in Ledoux [19].MultiSolid
is an aggregate of Solids
, and they are allowed to intersect and/or be disconnected.CompositeSolid
, formed by the Solids
A and B, should fulfil the following two assertions:
-
Assertion #1: their interior should not overlap (A o ∩B o =∅)
-
Assertion #2: their union should form one solid (A∪B= one
Solid
)
Related work
MultiSurface
, i.e. a set of surfaces embedded in 3D which could, or not, form a volume.isClosed()
) to verify whether a set of surfaces forms a closed volume. This does not support interior shells, and the documentation does not specify whether self-intersection is verified or whether non-manifoldness is taken into account. Also, errors in each surface are not validated, one would have to project each of them to a 2D plane and run the 2D validation functions separately. Aggregates and composites are not handled.Polygons
cannot have interior rings. In two scientific papers describing the details of Oracle’s validation capabilities in 3D, Colley et al. [9] and Kazar et al. [16] falsely claim that this definition is ISO19107-compliant, while most of the figures clearly indicate otherwise; tests I ran with Oracle Spatial also confirms this. CompositeSolids
are listed as 3D primitives in the documentation, but since the volumetric primitive used to build them are not following the international definitions, the CompositeSolid
does not either.Polygons
are disallowed.Solids
because the first version of val3dity is used in the background. Aggregates and composites are however not currently supported.Solids
, as well as aggregates/composites, were ignored.Implementation
Primitives are validated hierarchically
Solids
, and extends it so that MultiSolids
and CompositeSolids
are handled.Solid
is represented by a list of Shells
(which are CGAL::Polyhedron_3
), and the interactions between the different shells are validated with my own code using the Boolean operations in CGAL::Nef_polyhedron_3
.CompositeSolid
, the 3D primitives are validated hierarchically:
-
the lower-dimensionality primitives (the
LinearRings
andPolygons
) are validated by first projecting them to a 2D plane (obtained with least-square adjustment), and then using 2D validation methods;× -
then these are assembled into
Shells
and/or surfaces, and their validity is analysed; -
then the
Solids
are validated (e.g. the interactions between differentShells
, the orientation of the normals, etc.) -
finally, for
CompositeSolids
, the interactions between theSolids
are analysed.
Polygon
forming a CompositeSolid
is not valid, the validator will report that error but will not continue the validation at the next level (to avoid “cascading” errors); all the primitives at one level are however validated.-
errors related to specific City Objects in the CityGML data model [11, 23]. Currently these are only for CityGML
Buildings
, but they will be in the future extended to other classes if there is a need from practitioners. And also other standards will be included, e.g. IndoorGML is currently under development.×
A fast C++ implementation
-
2D Polygons: used to represent each ring of a
Polygons
; -
3D Polyhedral Surfaces: used to represent one
Shell
; -
3D Boolean Operations on Nef Polyhedra: used to represent one
Solid
and to model and verify the interactions between theShells
, but also the interactions between the differentSolids
of aCompositeSolid
and the different parts of aBuilding
; -
3D Minkowski Sum of Polyhedra: used when a tolerance is used to validate
CompositeSolids
andBuildingParts
(see the section below);
Polygon
must be planar, the concept of tolerance is not mentioned. Tolerances for the following can be defined:
-
planarity of
Polygons
: the tolerances used have been agreed upon by the community in the OGC Quality Interoperability Experiments [24];× -
snapping between vertices: since in many formats, e.g. GML, the same vertex needs to have its coordinates listed for each
Polygon
, a tolerance must be used to identified if they are the same; -
overlap between
Solids
orBuildingParts
, as explained below.
Building
or Bridge
) are processed and all their 3D primitives are validated. Other GML files are simply scanned and their 3D primitives are validated according to the rules in ISO19107, all the rest is ignored. For OBJ and OFF files (formats without semantics and used mostly for visualisation), each primitive will be validated according to the ISO19107 rules, therefore one must specify how the primitive(s) should be validated (as MultiSurface
, CompositeSurface
, or Solid
).Interactions between solids are validated with a tolerance
CompositeSolid
, formed for instance by the Solids
A and B, should fulfil the 2 assertions defined in the ‘Background’ section. While these can be verified with Boolean operations, in practice we often encounter datasets where two Solids
overlap (or are disjoint) by a very small amount, e.g. the overlapping volume would be around 10cm 3 for a Building
. While the overlap is an error, in practice reporting this as an error can be a nuisance for the user.CompositeSolids
. This can be seen as a generalisation to 3D of the tolerance used for the 2D validation of polygon, see for example van Oosterom et al. [25]. As shown in Fig. 6, the mathematical morphology theory in 3D [27] is used to erode and dilate Solids
by a user-defined parameter. Erosion is performed when the overlap between Solids
is verified (A
o
∩B
o
=∅), and dilation when disjointness is verified (A∪B= one Solid
). These operations are realised by a series of operators that uses the Minkowski sum of a Solid
with a structuring element (a cube or dodecahedron in this case); as shown in Boeters et al. [6] and Donkers [10] the shape of the element will influence the resulting shape and thus the results. The perfect structuring element would be a sphere (would not yield errors, as an approximation by a dodecahedron does), however the closer the structuring element approximates a sphere the more computation time will be necessary.
Buildings
having one or more BuildingParts
can also be validated with an overlap tolerance. However, only the overlap assertion is verified, since BuildingParts
are allowed to be disjoint; the CityGML standard is not clear about this, but this was confirmed as the intended behaviour [17].Solid
and the structuring element). This can be observed in the experiments with real-world datasets in the next section.Reporting errors to the user
Shell
contains a hole, its location is provided; (ii) if a Polygon
forming a Solid
is invalid, then its identifier is reported (and if it does not have one then its position in the input file is reported); (iii) if two Solids
in a CompositeSolid
overlap, the identifiers of the Solids
are reported, etc. val3dity outputs a validation report, in JSON format, where for each (CityGML) object and 3D primitive the validation errors are listed. The report is both human- and machine-readable. As shown in Fig. 7, it is also possible to navigate this report with an interactive HTML viewer containing a summary and a list of detailed errors for each primitive and object.
Results
How is the validator validated?
pytest
framework10 and a custom setup, and tests, among others:
-
all the error codes one by one; there are several files and each of them contains one and only one error, see Fig. 8 for eight randomly chosen cases;×
-
empty files and geometries, invalid input file formats. It should be noticed that val3dity does not validate the schema of the input, the main reason is that often small errors are not an issue for the validation and val3dity can recover from them (in the same way that a web browser can often display invalid HTML);
-
various valid geometries, larger files and boundary conditions;
-
command-line user input.
Testing with different real-world 3D city models
Buildings
| Primitives | Time validation | |||||||
---|---|---|---|---|---|---|---|---|---|
Sizea | Total | Parts | Repb | Valid | Total | Valid | Default | Overlap_tol=0.05c | |
Berlin1 | 933MB | 22 771 | 3 | S+Sem | 74% | 89 736 | 90% | 1m19 s | 1m19 s (74%) |
DenHaag2 | 22MB | 844 | 507 | S | 61% | 1 990 | 85% | 39 s | 10m29 s (80%) |
Montréal3 | 125MB | 581 | 0 | Sem | 73% | 1 744 | 88% | 3 s | 3 s (73%) |
NRW4 | 16MB | 797 | 95 | S | 83% | 928 | 77% | 5 s | 35 s (83%) |
–report_json report.json
’ so that a report is generated, and the default values were used:
-
snap tolerance: 1mm
-
planarity tolerance (distance-to-plane): 1cm
-
planarity tolerance (normals orientation): 20 degrees
-
overlap tolerance: unused/0cm; and as explained below with 5cm too
Buildings
(with, oddly, only 3 having BuildingParts
). Some of these are stored as Solid
, and for some only semantic surfaces are stored, without any geometry defined. For the second case, we can assume that the meaning was that the semantic surface should be represented as a MultiSurface
, and thus val3dity offers that option on-the-fly (‘–geom_is_sem_surfaces
’). Observe that the whole process (parsing the file, validating, and outputting the report) takes only 1m19s. However, it should be observed here that speed was not the main goal of val3dity, its main goals are that it is accurate and that it provides meaningful feedback to the user. Informing the user about the nature of the error and having the most efficient code are contradictory goals. One could easily and quickly report that a Shell
is non-manifold, but reporting to the user the location of the non-manifold case, with the identifier of each surfaces involved, requires using different data structures and a slower processing time.Buildings
stored as Solids
, but 507 of them have BuildingParts
. The validation performed with the default values, and thus no overlap tolerance overlapping buildings, leads to several errors (only 61% of Buildings
are valid). However, if we use an overlap tolerance of 5cm, then this number goes up to 80%; notice that the validation time is greatly affected: it is 16 times slower and takes 10m29s.Buildings
, but as it is often the case with CityGML, no geometry is explicitly stored, only semantic surfaces are present. The dataset was thus validated with these as MultiSurface
, and the whole process took only 3s. This dataset is interesting because the only errors present are very simple ones that could be fixed easily: errors 101 and 102 (see Fig. 3).Buildings
. All the buildings are stored as Solids
, but interestingly there is a mix of LoD1 and LoD2 (which has no influence as far as validation is concerned). As is the case with other datasets containing BuildingParts
, using an overlap tolerance (of 5cm) significantly slows down the validation process, but in this case removes the two errors 601 that were present. Furthermore, there are 76 primitives that are non-planar (errors 203 and 204), but if a planarity tolerance of 10cm is used and error 204 is ignored (does not cause problems for several applications) then this number goes down to only 2 primitives.Conclusions
BuildingParts
. For instance, one could verify whether two of the Buildings
in her file are overlapping, or whether these are properly connected to the terrain (so that they do not float a few centimetres above it). I also plan to implement other semantic models and develop specific geometric validation functions, e.g. in IndoorGML ensuring that the navigation graph is consistent with the subdivision space.Availability and requirements
-
Project name: val3dity
-
Project home page: https://github.com/tudelft3d/val3dity
-
Documentation: http://geovalidation.bk.tudelft.nl/val3dity/docs/
-
Operating system(s): Platform independent
-
Programming language: C++
-
Other requirements: CGAL, GEOS, Boost
-
License: GNU General Public License v3.0