An optimization approach for automated
as-built 3D modeling
Dr. F. Xue
6 Apr 2017
Dept. of REC, HKU
Hong Kong

Outline
1

Background & Opportunity

2

As-built Modeling as Optimization

3

Discussion & Future Research

F Xue: Auto as-built 3D modeling (Staff Seminar)

2

Section 1

BACKGROUND & OPPORTUNITY

F Xue: Auto as-built 3D modeling (Staff Seminar)

3

1.1 As-built 3D modeling of civil infrastructures
 As-built models [1]
 Increasingly important for AEC/FM
o Construction management
o Facility management

o Built env. conservation

An example of photogrammetry: Kowloon Wall City
(Source: patrick-@sketchfab.com)

o Business with VR/AR, etc.

 See as-planned, as-designed, as-demolished BIMs

 Popular technologies (surface models)
 Photogrammetry (videogrammetry)

An example of point cloud: Pompei City
(Source: MAP-Gamsau lab, CNRS, France)

 Point cloud
 3D Geographic information system
 Others (statistical rules, deep learning [2], etc.)
F Xue: Auto as-built 3D modeling (Staff Seminar)

: Architecture, Engineering and
Construction/ Facilities Management

An example of GIS-based: 3D Berlin
(Open Data, source: berlin.de)

4

1.1 The (semi-)automated as-built 3D modeling
 Two categories of methods
 Data-driven v.s. Model-driven

 Some challenges remains
 Unsatisfactory semantic/abstraction discovery
o  huge size (data-driven), poor reusability(model-driven)

 Others

F Xue: Auto as-built 3D modeling (Staff Seminar)

5

1.2 Derivative-free Optimization in OR
 Optimization (a.k.a. Mathematical programming)
 the selection of a best element (with regard to some criteria)

from some set of available alternatives.

𝐦𝐦𝐦𝐦𝐦𝐦 𝑓𝑓: ℝ𝑛𝑛 ⟼ ℝ
An example of optimization

 Nonlinear optimization
 When objective function or some constraints are nonlinear

 Derivative-free Optimization (DFO) [3]
 Objective function or constraints are unknown
o E.g., model selection, parameter tuning in simulations

o Especially when function is very expensive or unanalyzable

DFO: Manipulating a black-box
(Figure adapted from Wikipedia)

 Challenging (NP-hard), but achieved significant success

o In applied science and engineering such as molecular biology

and material sciences

: Operations Research

F Xue: Auto as-built 3D modeling (Staff Seminar)

6

1.3 An opportunity
 The questions
 Can the model generation be generally solved by DFO methods?
o If true, can semantic data be discovered at the same time?

 If all true, we can

AEC/FM
As-built
model
generation

 Map between a typical problem in AEC/FM and a class of

powerful algorithms in OR
o Also expose as-built model generation to many other

nonlinear methodologies

 Discover semantic (abstraction) information

DFO

OR
F Xue: Auto as-built 3D modeling (Staff Seminar)

7

Section 2

AS-BUILT MODELING AS OPTIMIZATION

F Xue: Auto as-built 3D modeling (Staff Seminar)

8

2.1 A meta-model of as-built 3D modeling
 Given a reference measurement, a set of parametric
components
 A meta-model of optimization is from such a
formulation:
Tells computers:
What to change
What is good

Rules to follow

 The variables (X ) are the parameters of the components;

𝐦𝐦𝐦𝐦𝐦𝐦 𝑓𝑓 𝑋𝑋

𝐬𝐬. 𝐭𝐭. 𝐴𝐴(𝑋𝑋) ≤ 0

Meta-model of constrained
optimization & its solution space

???

 The objective function ( f ) is to maximize the similarity (or

minimize dissimilarity) between the 3D model (as combinations
of the parametric components) and the measurement; and

 The constraints (A ) over the variables are the topological

relationships between components.

 Meta-: Abstraction

 from Greek prefix μετά-, “beyond”
F Xue: Auto as-built 3D modeling (Staff Seminar)

Reference
measurements

Parametric (&
semantic)
components
9

2.1 Computational algorithms for the meta-model
 Brutal-force search is impractical
 Fortunately, there are a long list of
off-the-peg algorithms for solving
such a meta-model as a black-box:
 Surrogate methods
o CMA-ES (Covariance matrix adap-

tation with evolution strategy) [5]
and its variants are competitive

 Trust-region methods

 Metaheuristics (GA, PSO, VNS, etc.)
 Hyper-heuristics, data mining
 … and Monte Carlo
F Xue: Auto as-built 3D modeling (Staff Seminar)

Comparison of algorithms for BBOB-2009 (Black-Box Optimization
Benchmarking, higher is better) [4]
10

2.1 The framework: A bird’s-eye view
 The full framework of optimization-based model generation
 Input 1: Reference measurements (photo, point clouds, video)
 Input 2: Semantic and parametric components
 Process: Systematically finding the fittest model by solving meta-model with DFO methods
 Output: A semantic as-built model

F Xue: Auto as-built 3D modeling (Staff Seminar)

The overall framework of optimization-based modeling

11

2.2 A pilot: A demolished building at campus
 The pilot case
 A demolished baroque-style two-storey building
o Once occupied by School of Tropical Medicine and School of

Pathology, HKU

 Input: A photo

 Preparing parametric components

A historical photo (Source: MTR
HKU Station, re-photographed by
an Android phone)

 Only apparent (>1m) components (for feasibility test)
 7 components were collected from 3D Warehouse of SketchUp
o With a keyword filter “baroque”

o With limited (3) pairs of conflicting components

 Door portico
 Tree × 2
 Wall × 2
 Windows × 2

 Adjusting components for the case

o Removing extra parts, alignment

F Xue: Auto as-built 3D modeling (Staff Seminar)

(Contributors: Mohamed EL Shahed, Richard,
KangaroOz 3D, Yoshi Productions, 3dolomouc,
Architect, Ben @ 3D Warehouse)
12

2.2 The meta-model
 Meta-model of as a constrained optimization problem
 Minimize the dissimilarity
o Between the projected image of model and the input photo
o E.g., Mean square error (MSE) of pixels or SSIM [6] 

 With respect to topological constraints

 Computational functions implemented on SketchUp (2016 Pro)

Ruby API
o Objective function interface

min f = dissimilarity
= 1-SSIM
(or maybe f =MSE of
pixels)
s.t. Semantic constraints
of position, scaling, and
ABOVE/ BELOW/
CONTAINS_ON for each
component

o Variables as parameters (per component)

Manifolds (0, 1) + scaling (xyz) + location (xyz) + rotation
(αβγ) = 4 ~ 6 variables

o Constraints of topological relationships

 A virtual Ground object is placed at first
F Xue: Auto as-built 3D modeling (Staff Seminar)

: Structural similarity
13

2.1 Details of the topological relationships
 Topological relationships
 Categories
o Adjacency: ABOVE, BELOW, NEXT_TO, …
o Separation: SEPERATED

o Containment: CONTAINS_ON, CONTAINS_IN
o Intersection: INTERSECTS_WITH
o Connectivity: CONNECTS_TO

 Semantic definition

 Adding properties like scaling and topological relationships to

their SketchUp dictionaries
o E.g., ABOVE, BELOW, CONTAINS_ON, etc.
F Xue: Auto as-built 3D modeling (Staff Seminar)

An example of the dictionary of
component in SketchUp

Time of preparation of
components
- Collection (~15 minutes)
- Adjustment (~30 minutes)
- Semantic def. (~15 minutes)
14

2.2 An earlier computational experiment in 2016
 Automated generation
 Two phases:
o Incremental (2,800 trials)
o Refinement (2,000 trials)

 The Solver: CMA-ES (C++

code [7] in a Ruby wrapper)
 Time: 3,822.4s
o After so much

simplification

 Fault-tolerant (see the trees)
 Semantic/grammar-enhanced

 : Should be much faster now.
F Xue: Auto as-built 3D modeling (Staff Seminar)

Automated generation of semantic as-built model as solving the nonlinear optimization problem,
by a well-known DFO algorithm CMA-ES in 3,822.4 seconds (4,800 trials, single thread) on an
Intel i5-6500 CPU (3.2 GHz)
15

2.2 Results and post-processing
 Obtained
 The facade in the photo
 Semantic links

 Post-processing
 Manual completion
o Copy & paste

 Georeferencing and

(a) Direct result: The façade in the photo

(b) The semantic links illustrated in Stanford
Protégé (Circle denotes a component class and a
diamond stands for an instance/object)

display in 3D

F Xue: Auto as-built 3D modeling (Staff Seminar)

(c) Manually completed approximate model (~15 minutes) (d) Georeferencing and illustration on Google
Earth, near MTR Exit A (~5 minutes) 16

3.3 OMG & live demonstration
 A library OMG (optimization-based model generator) is
under development
 A shared computational library with specific plugins for
o SketchUp, Revit, etc.

 Multiple meta-models with various
o Objective functions

o Measurement types, and
o Solving algorithms

 Multiple modeling options

One click
OMG

o Ontology-guided, free discovery, finetuning, etc.
o Extended the earlier pilot study

 Demo (more efficient now)
F Xue: Auto as-built 3D modeling (Staff Seminar)

17

Section 3

DISCUSSION & FUTURE RESEARCH

F Xue: Auto as-built 3D modeling (Staff Seminar)

18

3.1 Discussion
 Meta-modeling of as-built 3D modeling as constrained optimization
 Pros: General, simple, no explicit object recognition/segmentation (also challenging)
 Cons: A larger search space (slower), slow full projection, limited by pixels, less accurate

 Semantic definitions of components
 Pros: Realized ‘grammar’ of components, simplified optimization
 Cons: Some manual work needed, subject to redefinition from a project to another

 The framework as a whole
 Pros: High automation, reusing components and abstractions, less requirements on

equipment, tolerant to errors, scalable to new environments, (hopefully) semantically rich
 Cons: Less accurate in geometry, still in its infancy
 Answers to the question: 1) True; 2) Applicable to some relations
o Semantic recognition/segmentation is another pillar for semantic BIM

F Xue: Auto as-built 3D modeling (Staff Seminar)

19

3.2 Future research
 Effectiveness
 More didomains (e.g. infrastructures, etc.)
 Advanced DFO methods
 More objective functions
 On real BIM/CIM models instead of surface models

 Efficiency

We are still on the way (Source: clipartpanda.com)

 Efficient ways of manipulating point clouds (working…)
o E.g., kd-tree, approximate kNN, convex hull, planar and object

detection

 Extensions

 Shared component libraries for reusability (e.g., IFC-compatible)
 Handling other challenging AEC/FM problems
F Xue: Auto as-built 3D modeling (Staff Seminar)

The Roman aqueduct Pont du Gard
(Source: Wikipedia/ 3Dwarehouse.com)20

References
 [1] Volk, R., Stengel, J., and Schultmann, F. (2014). Building Information Modeling (BIM) for existing buildings—Literature

review and future needs. Automation in Construction, 38: 109-127.
 [2] Patraucean, V. (2016). Deep machine learning: key to the future of BIM? Cambridge: University of Cambridge, Mar 14 2016.

Accessed July 15 2016. http://www-smartinfra structure.eng.cam.ac.uk/news/viorica-patraucean-featured-in-infrastructureintelligence-.
 [3] Conn, A. R., Scheinberg, K., and Vicente, L. N. (2009). Introduction to derivative-free optimization. MPS-SIAM book series on

optimization (Vol. 8). SIAM.
 [4] Auger, A., Finck, S., Hansen, N., and Ros, R. (2010). BBOB 2009: Comparison tables of all algorithms on all noisy

functions (PhD thesis, INRIA).
 [5] Hansen, N., and Ostermeier, A. (2001). Completely derandomized self-adaptation in evolution strategies. Evolutionary

Computation, 9 (2): 159-195.
 [6] Wang, Z., Bovik, A. C., Sheikh, H. R., and Simoncelli, E. P. (2004). Image quality assessment: from error visibility to structural

similarity. IEEE Transactions on Image Processing, 13 (4): 600-612.
 [7] CMA-ESpp, an open source library, see: https://github.com/AlexanderFabisch/CMA-ESpp

F Xue: Auto as-built 3D modeling (Staff Seminar)

21

Thank You !