Peter Robert Gustaaf Bak - Imperial Spiral - Imperial College London [PDF]

modelling techniques are discussed and AEGIS is shown to offer design ...... virtue of their two dimensional nature, do

0 downloads 9 Views 22MB Size

Recommend Stories


Untitled - Imperial College London
Come let us be friends for once. Let us make life easy on us. Let us be loved ones and lovers. The earth

Imperial College
It always seems impossible until it is done. Nelson Mandela

Dr. Matthew Hodes, Imperial College London Position
Pretending to not be afraid is as good as actually not being afraid. David Letterman

Senior Lecturer Experimental Geotechnics, Imperial College London
Why complain about yesterday, when you can make a better tomorrow by making the most of today? Anon

Imperial College Healthcare
Be who you needed when you were younger. Anonymous

imperial
Goodbyes are only for those who love with their eyes. Because for those who love with heart and soul

Constitution of Imperial College Union.pdf
You can never cross the ocean unless you have the courage to lose sight of the shore. Andrè Gide

Imperial College Union Media Group
Ask yourself: When was the last time you did something that you were afraid of? Next

Imperial College London Shaping a Spacetime from Causal Structure
Ask yourself: What am I most thankful for? Next

Imperial College London MSc EXAMINATION May 2014 BLACK HOLES
Silence is the language of God, all else is poor translation. Rumi

Idea Transcript


A p p lie d

S o lid

M o d e llin g

In M in e ra l R e s o u rc e s E n g in e e rin g

A thesis submitted to the University of London (Imperial College Of Science, Technology and Medicine)

by

P eter R o b ert G u sta a f B ak

In fulfilment of the requirements for the degree of Doctor of Philosophy

January 1991

A b s tra c t

The spatial information management systems developed for use in the Minerals industry, al­ though far in advance of traditional ‘pen and paper’ methods, offer little more than the automa­ tion of manual processes. There is a need for more sophisticated tools which can assist planners in characterising a subsurface environment and optimising engineering designs. This thesis investigates the application of Solid Modelling techniques in Mineral Resources Engi­ neering and presents a prototype A dvanced E n g in eerin g G rap h ics In fo rm a tio n S ystem (A E G IS ). The latter employs a hybrid representation scheme which integrates a boundary model with a form of adaptive spatial enumeration known as lin ear octree encoding. Such a scheme is able to model both geometric structure and spatial composition simultaneously and offers advanced functionality including 3D visualisation, integral property calculations and spatial search. The mathematical modelling concepts employed in A E G IS are discussed in detail and algorithms are presented for: • Solid model generation; • Boolean operations on solid objects; • Integral property calculations; • 3D visualisation; • Spatial search; • Model sectioning; • Component contouring. The functionality and validity of the hybrid scheme is verified through practical application. Both synthetic and genuine data sets are modelled and analysed: engineering structures are intersected with geological features, integral properties are calculated, 3D perspective images are generated and spatial queries are performed. The advantages and disadvantages of the modelling techniques are discussed and A E G IS is shown to offer design functions which are new to the Minerals Industry. In conclusion, the application of boundary and octree modelling in alternative disciplines of geoscience is considered and further research is proposed.

1

T h is is a b la n k page.

A c k n o w le d g e m e n ts

The author wishes to thank Dr. Andrew J.B . Mill for initiating this research, offering both advice and support and stimulating intellectual thought. Thanks also go to Dr. Robin Smith whose administrative contribution was invaluable during the former stages of the project. Numerous people have contributed to the reported work and their interest and efforts axe sincerely appreciated. Certain contributions deserve special recognition: • Dr. Irene Gargantini and Harvey Atkinson at the University of Western Ontario. • Professor Tosiyasu L. Kunii at the University of Tokyo. • Dave Steffe and Harry Wilson at B P Minerals Ltd. • Jonathan Raper at Birkbeck College. • Colleagues of the C A D Research Group, Imperial College. The research was funded by the Science and Engineering Research Council, B P Minerals Ltd. and James Capel Co. This funding is appreciated. Finally, sincere thanks are given to the authors parents for their financial and emotional support, the authors wife for the frustration she has had to endure and to Simon Grose-Hodge for his loyal friendship.

in

T h is is a b la n k page.

C o n te n ts

Glossary

xix

1 Introduction

1

1 .1

Spatial Information Management: A Review .................................................................

3

1.2

Research O b je c tiv e s ............................................................................................................

8

1.3

P la t e s ......................................................................................................................................

11

2 Review and Analysis of Solid Modelling Techniques

15

2.1

Mathematical Point-Set M o d e ls........................................................................................

15

2.2

Mathematical Surface-Based M o d e ls ..............................................................................

17

2.3

Computer Representations..................................................................................................

18

2.4

Decomposition M o d e ls........................................................................................................

21

2.4.1

Primitive Instancing Schem es...............................................................................

21

2.4.2

Space Subdivision S ch e m e s..................................................................................

22

2.4.3

Cell Decom positions..............................................................................................

26

Constructive M o d e ls ...........................................................................................................

27

2.5.1

Sweep Representations...........................................................................................

27

2.5.2

Constructive Solid G e o m e try ..............................................................................

29

Boundary M odels..................................................................................................................

34

2.6.1

Planar Polygon Boundary Models

.....................................................................

34

2.6.2

Curved Surface Boundary Models

.....................................................................

38

2.7

Hybrid M o d e ls .....................................................................................................................

40

2.8

Chosen Solid Modelling Approach

43

2.5

2.6

..................................................................................

3 Boundary Representation in AEGIS 3.1

3.2

45

Model Creation - Surface T rian g u latio n ........................................................................

46

3 .1.1

M apping.....................................................................................................................

50

3.1.2

B ranchin g ..................................................................................................................

51

3.1.3

C a p p in g .....................................................................................................................

53

Model Creation - Description L a n g u a g e ........................................................................

54

v

vi

CONTENTS

3.3

3.2.1

H exah ed ro n s............................................................................................................

54

3.2.2

E llip s o id s ...................................................................................................................

55

3.2.3

Volumes of Revolution............................................................................................

57

P la t e s .....................................................................................................................................

61

4 Adaptive Spatial Subdivision in A E G I S

73

4.1

Linear Octree Encoding - The Mathematical M o d e l .................................................

73

4.2

The Linear Octree Encoding S ch em e...............................................................................

75

4.3

The Linear Octree Data S tr u c tu r e ..................................................................................

77

4.3.1

Octree Attributes.....................................................................................................

78

Linear Octree G e n e ra tio n ..................................................................................................

81

4.4.1

Transformation of the Object S p a c e ..................................................................

84

4.4.2

The Encoding Algorithm

.....................................................................................

85

4.4.3

The Compression Algorithm ..................................................................................

85

4.4.4

Encoding a Block M o d el........................................................................................

86

4.4.5

Encoding of Line Models

.....................................................................................

88

4.4.6

Encoding of Surface M o d e ls..................................................................................

91

4.4.7

Encoding of Solid M o d e ls .....................................................................................

93

4.4.7.1

Octant Connectivity - Te rm in o lo g y..................................................

93

4.4.7.2

Octant Connectivity - Solid M o d e ls ..................................................

95

4.4.7.3

Octant Connectivity - Surface M odels...............................................

95

4.4.7.4

Implementation of the Solid Model Generation P r o c e s s ................... 100

4.4

4.5

4.6

4.7

4.8

Octree M anip ulation............................................................................................................

107

4.5.1

Set Operations on Linear Octree M odels...........................................................

107

4.5.2

Transformations of Linear Octree M o d e ls ........................................................

110

Octree A n a ly sis......................................................................................................................

115

4.6.1

Integral Properties of Linear OctreeM o d e ls......................................................

115

4.6.2

Connected Component Labelling ofLinear Octree M o d e ls ............................

117

4.6.3

Spatial Search

.........................................................................................................

117

4.6.3.1

The Neighbour Finding A lg o rithm .....................................................

119

4.6.3.2

Regular and Irregular Spatial Search.................................................

126

4.6.3.3

Connected Spatial S e a rch .....................................................................

128

Linear Octree D is p la y .........................................................................................................

133

4.7.1 Tracking.......................................................................................................................

138

P la t e s ......................................................................................................................................

139

CONTENTS

vii

5 Practical Application and Assessment of AEGIS

151

5.1

Data S e t s .................................................................................................................................

15 1

5.2

Practical Application..............................................................................................................

153

5.2.1

Model C reatio n ........................................................................................................

153

5.2.2

Model A n a ly s is ........................................................................................................

154

System Assessm ent...............................................................................................................

159

5.3.1

.....................................................................................................

161

5.3.1.1

Boundary M o d e ls ..................................................................................

161

5.3.1.2

Octree M o d e ls ........................................................................................

162

5.3.2

Surface T ria n g u la tio n ...........................................................................................

165

5.3.3

Description L a n g u a g e ...........................................................................................

166

5.3.4

Statistical Gridding

...............................................................................................

166

5.3.5

Geological Process Sim ulation..............................................................................

166

5.3.6

Octree Model Generation Algorithms

..............................................................

167

5.3.7

Boundary Model Modification Functions...........................................................

167

5.3.8

Octree Model Modification Functions

..............................................................

168

5.3.9

Boundary Model Display Capabilities

..............................................................

168

5.3.10 Octree Model Display C a p a b ilitie s.....................................................................

169

5.3 .11 Integral Property C a lc u la tio n s ...........................................................................

170

5.3.12 Spatial Search Functions........................................................................................

170

5.3.13 Tracking.....................................................................................................................

17 1

5.3.14 Spatial and Relational Q u e r y ..............................................................................

172

5.3.15 Geometric Data Conversion..................................................................................

172

5.3.16 Sectioning and Contouring

..................................................................................

173

P l a t e s ......................................................................................................................................

175

5.3

5.4

Model Accuracy

6 Discussion

187

7 Conclusion

191

References

193

A Point-Set Topology: Basic Concepts

199

A. l

Point-Set Topology............................................................................................................

B Algebraic Topology: Surfaces and Plane Models B. l

199

203

The Euler-Poincare Form ula............................................................................................... 207

viii

CONTENTS

C A Basic Reflection Model

211

C .l

Diffuse Reflection.................................................................................................................

2 11

C.2

Specular Reflection..............................................................................................................

2 11

C.3

Ambient Illumination

.......................................................................................................

212

C.4

Depth C u e in g ........................................................................................................................

213

D Effects of Resolution on Octree Model Accuracy

215

E Effects of Scale Factor on Octree Model Accuracy

217

L is t o f F ig u r e s

1.1

U nderground M ine D evelopm ent P h a s e s ........................................................................

2

1.2

E x tran e ity o f Block M o d e ls ..................................................................................................

5

2.1

R eg u larisatio n of a Solid M o d e l ........................................................................................

16

2.2

A S elf-In tersectin g P o ly h e d ro n ...........................................................................................

18

2.3

A N on-R ealisable 2 - M a n i f o l d ...........................................................................................

18

2.4

A n A m biguous S olid M o d e l ...............................................................................................

20

2.5

P rim itiv e In stan c e o f a P r i s m ...........................................................................................

21

2.6

P rim itiv e In stan c es which are n o t U n i q u e .....................................................................

22

2.7

R egular S p atial Subdivision M o d e l .....................................................................................

24

2.8

A daptive S p atial S ubdivision M o d e l ..................................................................................

24

2.9

C ell D ecom position M odel of a C y l i n d e r ........................................................................

26

2.10 T ra n sla tio n a l Sweep

............................................................................................................

28

2.11 R o ta tio n a l S w e e p ..................................................................................................................

28

2.12 Volume S w e e p .........................................................................................................................

28

2.13 D egeneracy of Sweep M o d e ls ...............................................................................................

29

2.14 C ylindrical H alf-Space M o d e l ...........................................................................................

30

2.15 A C SG T r e e ............................................................................................................................

32

2.16 P olyhedral M odel o f a C u b e ...............................................................................................

34

2.17 F u ll W inged-Edge D a ta S t r u c t u r e .....................................................................................

36

2.18 In co n sisten cy in C SG to B o u n d ary M odel C o n v ersio n

...............................................

38

2.19 C o o n s’ P a t c h .........................................................................................................................

39

2.20 R egular an d Irreg u lar Space C urve N e tw o r k s .................................................................

41

2.21 C o-existing In d e p en d en t H ybrid R ep re sen tatio n A r c h i t e c t u r e s .................................

42

2.22 The B lack Hole E f f e c t .........................................................................................................

43

3.1

G raph R ep re sen tatio n o f A d jacen t C o n to u r L o o p s .........................................................

47

3.2

In itia lisa tio n of T rian g u latio n P r o c e s s ...........................................................................

47

3.3

T rian g u lated S p an n in g S urface

3.4

G raph T heoretic R ep re sen tatio n o f T rian g u la tio n P r o c e s s ...........................................

49

3.5

A Topologically In v alid S p an n in g S u r f a c e ........................................................................

50

...............................................................................

IX

48

LIST O F FIGU R E S

X

3.6

M apping o f A djacent C o n to u r L o o p s ...............................................................................

51

3.7

G en eral B ran ch in g M e th o d ...................................................................................................

52

3.8

M ultiple B r a n c h in g ................................................................................................................

52

3.9

T rian g u latio n of Line S e g m e n t s .........................................................................................

52

3.10 A Surface B o u n d ary with ‘O pen’ E n d s ............................................................................

53

3 .11 A Capped Surface B o u n d a r y ................................................................................................

53

3.12 C o-o rd in ate A rray G en eratio n fo r H e x a h e d r o n s ............................................................

55

3.13 C o-ordinate A rray G en eratio n fo r E l l ip s o i d s ..................................................................

56

3.14 C o -o rd in ate A rray G en eratio n fo r Volumes of R e v o lu tio n ...........................................

58

3.15 T ran sfo rm atio n of a Volume of R e v o lu tio n .....................................................................

60

4.1

A P h y sical Object an d the corresponding M ath em a tica l O ctree M o d e l ....................

74

4.2

A n A bstract Octree R e p r e s e n t a t i o n ...................................................................................

76

4.3

A ‘P ru n e d ’ Octree R e p re s e n ta tio n ......................................................................................

76

4.4

O ctal N o t a t i o n ......................................................................................................................

78

4.5

The Octree M ath em atical M odel fo r a Sim ple O b j e c t ..................................................

79

4.6

The A bstract Octree R ep resen tatio n o f a Sim ple O b j e c t ..............................................

79

4.7

M apping of an Object D o m ain to an O ctree U n iv e r s e ..................................................

82

4.8

The B it In terla cin g T e c h n iq u e ............................................................................................

86

4.9

O c ta n t C o m p r e s s io n ............................................................................................................

87

4.10 P ro jectio n of a Line onto an O rthogonal P l a n e ...........................................................

90

4 .11 R asteriz atio n of a L ine using a D ifferen tial A l g o r i t h m ..............................................

90

4.12 R asteriz atio n of a Polygon using a S can C o nversion T e c h n i q u e ..............................

92

4.13 C onnectivity o f O c t a n t s ......................................................................................................

94

4.14 C onnectivity o f L in ear Octree ‘S o lid ’ M o d e ls ..................................................................

96

4.15 C onnectivity o f L in ear Octree ‘S o lid ’ M odels - 0 ( 2 ) - a d ja c e n c y .................................

97

4.16 C onnectivity o f L in ear Octree ‘S o lid ’ M odels - 0 ( 8 ) - a d ja c e n c y .................................

98

4.17 C onnectivity o f L in ear Octree ‘S u rfa c e ’ M o d e l s ...........................................................

99

4.18 Solid Model G en eratio n - S et D ifference O p e r a t i o n .....................................................

101

4.19 Solid M odel G en eratio n - C onnected C o m p o n en t L a b e llin g ........................................

102

4.20 Solid M odel G en eratio n - S et Union O p e r a t i o n ...........................................................

103

4.21 C onnectivity o f B ack-projected V oxels ...............................................................................

106

4.22 C onnectivity fo r B ack-projection I n c r e m e n t s ..................................................................

108

4.23 N o n -regularity o f C lassical Set O p e r a t i o n s .....................................................................

109

4.24 Venn D iag ram s fo r Octree S et O p e r a t i o n s .....................................................................

Ill

4.25 O ctree Decoding - The B it Unfolding T e c h n iq u e ...........................................................

113

LIST O F FIGURES

xi

4.26 The M o st S ig n ifican t V o x e l ...............................................................................................

113

4.27 Id e n tific atio n o f a C onnected C o m p o n e n t ........................................................................

118

4.28 M ost S ig n ifican t D ig its fo r R ight an d Left N e ig h b o u rs .................................................

120

4.29 M ost S ig n ifican t D ig its fo r D ow n an d Up N e ig h b o u r s .................................................

120

4.30 M o st S ig n ifican t D ig its fo r B ack an d F ro n t N e ig h b o u r s ..............................................

12 1

4.31 The N eighbour o f an O c t a n t ...............................................................................................

124

4.32 A D is ta n t N e ig h b o u r .........................................................................................................

125

4.33 The S licing P r o c e s s ................................................................................................................

13 1

4.34 Search D irectio n s fo r a M odified N eighbour F in d in g A lg o rith m .................................

132

4.35 D im en sio n o f the View V o l u m e .........................................................................................

133

4.36 T ran sfo rm atio n o f th e O ctree U niverse in to the View V o l u m e .................................

134

4.37 An O ctree U niverse Viewed with a known View P la n e N o r m a l .................................

136

5.1

S urface A rea of a T riangle in E uclidean FT S p a c e ........................................................

161

5.2

N o n -R ig id R o tatio n o f an Octree M o d e l ........................................................................

169

A .l

A D isk a n d Topologically E q u ivalent F ig u r e s .................................................................

199

A.2

The N eighbourhood o f a P o i n t ............................................................................................

200

A . 3 The N ear P o in ts o f a set S

...............................................................................................

200

B . l C reating a C ylinder fro m a R e c ta n g le ...................................................................................203 B.2

The P la n e M odel o f a C y l i n d e r .........................................................................................

205

B.3

The P la n e M odel o f a S p h e r e ............................................................................................

206

B.4

The P la n e M odel o f a T o r u s ...............................................................................................

206

B.5

The P la n e M odel o f a P ro jectiv e P l a n e ............................................................................

206

B.6

The P la n e M odel o f the C onnected Sum o f two T o r i ......................................................207

B.7

Solids w ith N o n -m an ifo ld S u r f a c e s ..................................................................................

208

B . 8 P la n e M odels o f a C u b e .....................................................................................................

209

C . l The E n erg y o f In c id e n t L i g h t ............................................................................................

212

C.2

S pecular R eflection f o r a M irro r S u r f a c e ............................................................................ 212

G.3

Specular R eflection fo r a S hiny S u r f a c e ................................................................................213

L IS T O F F IG U R E S

L is t o f T a b le s

2.1

B o u n d ary R ep re sen tatio n o f a C u b e ..................................................................................

36

4.1

N o ta tio n fo r the L in ea r O ctree E ncoding S c h e m e ........................................................

77

4.2

O c ta n t Labelling fo r F ig u re J ^ . 5 ........................................................................................

80

4.3

C om plete L in ea r O ctree fo r F igure

...........................................................................

83

4.4

L in ea r O ctree fo r a R esolution R = 9 U n i v e r s e ...........................................................

104

4.5

B o u n d ary M odel fo r a R ectan g u lar B o x ...........................................................................

104

4.6

T ransform ed B o u n d ary M odel fo r a R ectan g u lar B o x ...................................................

105

4.7

C ase A nalyses fo r O ctree Set O p e r a tio n s ........................................................................

110

4.8

C ase A nalysis F u n c tio n s to D eterm in e A d jacen t N e ig h b o u r s .......................................... 121

4.9

B it T rend in the M ost S ig n ifican t D i g i t s ........................................................................

122

4.10 P rio rity O rder fo r O c ta n t L a b e llin g ..................................................................................

135

4.11 Visibility o f an O c t a n t ........................................................................................................

137

5.1

C o n to u r D a ta fo r the M olson P r o j e c t ..............................................................................

155

5.2

B o u n d ary M odel D a ta fo r the M olson P r o j e c t ..............................................................

156

5.3

S haft D etails fo r the M olson P r o j e c t ...............................................................................

156

5.4

M olson P ro je c t Block M odel D a t a .....................................................................................

157

5.5

O ctree M odel G en eratio n T im es fo r the M olson P r o j e c t ................................................

158

5.6

O ctree M odel B oolean O p erations fo r the M olson P r o j e c t ............................................

158

5.7

M olson P ro je c t Ore R e s e r v e s ...........................................................................................

159

5.8

C onnected C o m ponents in the M olson P r o j e c t ..............................................................

160

5.9

E rro r E s tim a te s in S urface A rea

.....................................................................................

162

4. 5

D.l

Volume an d S urface

A rea C alcu latio n s fo r an O ctree Encoded T o r u s .................215

D.2

Volume an d S urface

A rea C alcu latio n s fo r an O ctree Encoded S p h e r e ................ 215

D.3

Volume an d S urface

A rea C alcu latio n s fo r an O ctree E ncoded C y l i n d e r ............. 216

D. 4 Volume a n d Surface

A rea C alcu latio n s fo r an O ctree E ncoded P olyhedron

E. l E rro r E stim a te s fo r

an O ctree Encoded Sphere a t R eso lu tio n R = 4 ................... 217

E.2

an O ctree Encoded Sphere a t R esolution R = 5 .........217

E rro r E stim a te s fo r

xiii

. . . . 216

xiv

LIST O F T A B L E S E.3

E rro r E stim a te s fo r an Octree E ncoded Sphere a t R eso lu tio n R = 6 ........................

218

E.4

E rro r E stim a te s fo r an Octree E ncoded Sphere a t R esolution R = 7 ........................

218

E.5

E rro r E stim a te s fo r an O ctree Encoded Sphere a t R eso lu tio n R = 8 ........................

219

L is t o f P r o g r a m s

4.1

A L in e a r O ctree D a ta S tru ctu re Im plem en ted as an A r r a y ........................................

84

4.2

A L in e a r Octree D a ta S tru ctu re Im p lem en ted as a L inked L i s t .................................

84

4.3

The E ncoding A lgorithm using B it I n t e r la c i n g ..............................................................

88

4.4

The O ctree B it U nfolding A l g o r i t h m ..............................................................................

112

4.5

L ist S can A lgorithm to C alculate In teg ral P ro p e rtie s

.................................................

116

4.6

E x tra c t o f A lgorithm to D eterm in e A d jacen t N e i g h b o u r s ...........................................

123

4.7

N eighbour F in d in g A l g o r i t h m ...........................................................................................

127

4.8

A ‘H exahedron’ Search (E n c o d in g )

..................................................................................

129

4.9

A ‘H exahedron’ S earch (N eighbour F i n d i n g ) .................................................................

129

4.10 A ‘L in e ’ S e a r c h .....................................................................................................................

130

4.11 The S licing A l g o r i t h m ........................................................................................................

132

xv

L IS T O F P R O G R A M S

L is t o f P la t e s

1.1

W ire F ram e M odel o f an U nderground M ine L a y o u t ....................................................

11

1.2

S urface M odel of Geological F e a t u r e s ..............................................................................

11

1.3

A n A liased Block M o d e l .....................................................................................................

13

1.4

A n In v alid Solid M o d e l ........................................................................................................

13

3.1

A W arped S urface

...............................................................................................................

61

3.2

A P ris m a tic H e x a h e d ro n .....................................................................................................

61

3.3

A N o n -p rism atic H e x a h e d r o n ...........................................................................................

63

3.4

A W arped N o n -p rism atic H e x a h e d ro n ..............................................................................

63

3.5

E llip so id P r im itiv e s ...............................................................................................................

65

3.6 S urface o f R e v o lu tio n ............................................................................................................

65

3.7

Volume o f R evolution - The T o r u s ..................................................................................

67

3.8

S p iral o f T r a n s l a t i o n ............................................................................................................

67

3.9

R a d ia l S p i r a l .........................................................................................................................

69

3.10 R a d ia l S p iral of T r a n s l a t i o n ...............................................................................................

69

3.11 A T ransform ed T o r u s ............................................................................................................

71

4.1

A n O ctree M odel o f A P o in t D a ta S e t .............................................................................

139

4.2

A n O ctree M odel o f A P o in t D a ta S et (I n te r io r )

........................................................

139

4.3

A n O ctree M odel o f A C o n to u r D a ta S e t ........................................................................

141

4.4

A n O ctree M odel o f A Topographic S u rfa c e .....................................................................

141

4.5

C om position o f an O ctree M o d e l .....................................................................................

143

4.6

A n O ctree M odel a t R esolution R = 1 ( T ra n sfo rm atio n E x a m p l e ) ............................

143

4.7

A n O ctree M odel a t R esolution R = 7 (S p a tia l S earch E x a m p l e ) ..................................145

4.8

E xam ples o f R egular an d Irreg u lar S p atial S e a r c h e s ....................................................

145

4.9

E xam ples of C onnected S p atial S e a r c h e s ........................................................................

147

4.10 C o n to u rin g a S l i c e ...............................................................................................................

147

4.11 D ep th S hading of a L in ear O ctree M o d e l ........................................................................

149

4.12 F la t S hading o f a L in ea r O ctree M o d e l ...........................................................................

149

5.1

175

B o u n d ary M odel o f the M olson P ro ject M in eralised Z o n e .......................................... XVII

xviii

LIST O F P L A T E S

5.2

B o u n d ary M odel of the M olson P ro je c t U nderground O p e n in g s ..................................

175

5.3

B o u n d ary M odel o f the M olson P ro je c t U nderground U t i l i t i e s ..................................

177

5.4

W ire-fram e Im ag e o f the M olson P r o j e c t ........................................................................

177

5.5

S haded Im age o f the M olson P ro ject B o u n d ary M odel (V iew 1 ) .............................

179

5.6

S haded Im age o f the M olson P ro ject B o u n d ary M odel ( View 2 ) .............

179

5.7

S haded Im ag e o f the M olson P ro je c t Octree M o d e l ........................................................

181

5.8

S haded Im ag e o f the M olson P ro je c t O ctree M odel ( I n t e r i o r ) ....................................

181

5.9

Im ag e of a G rade C o n to u r O ctree M o d e l ........................................................................

183

5.10 B o u n d ary M odel o f the S leem an P ro je c t T opography ......................................................

183

5.11 B o u n d ary M odel o f the L abatt P ro je c t O p e n - p i t ............................................................

185

5.12 B o u n d ary M odel o f the S leem an P ro je c t Access R a m p ...................................................

185

G lo s s a ry

A E G IS B-Rep CAD CSG EEC FEM GDM G ID B S G IS GW B Kbytes M IC L M IPS M RE M SB M SD M SV Mbytes RD BM S VPN VRC

Advanced Engineering Graphics Information System Boundary Representation Computer Aided Design Constructive Solid Geometry European Economic Community Finite Element Modelling/ Mesh Graph Data Model G-Octree/G-Quadtree Image Data Base System Geographic Information System Geometric Workbench Kilo Bytes Mineral Industries Computing Limited Million Instructions Per Second Mineral Resources Engineering Most Significant Bit Most Significant Digit Most Significant Voxel Million Bytes Relational Data Base Management System View Plane Normal View Reference Co-ordinate

xix

XX

This is a blank page.

Chapter 1

In tro d u c tio n

A quantitative model, including rock property characterisation, for a three dimensional (3D) subsurface environment is a common requirement in many geoscientific disciplines: petroleum reservoir representation to support enhanced oil recovery, ground water contamination modelling at hazardous waste sites and geotechnical site investigation for complex construction projects (Turner, 1989) are some examples. In Mineral Resources Engineering (M RE) such character­ isation, along with knowledge of the geometric dimensions and spatial relations of subsurface features, is essential for effective resource evaluation, mine design and production planning. In examining the data associated with subsurface features and the development of an under­ ground mine, it is convenient to distinguish between the pre-production and production phases of an operation. During pre-production geostatistical, geological and economic information, in conjunction with mine planning i.e. surface and underground layouts, process plant design, shaft design and a host of other engineering designs, is appraised to determine project feasibility. Dur­ ing production phases extraction methods and associated design considerations are modified, in detail, as more accurate information becomes available (Figure 1.1). Such data can be categorised as: G eo lo g ical D a t a - Geological data includes the geometric dimensions, spatial distribution, physical properties and composition of geological features. U t ilit y D a t a - Utility data includes the geometric dimensions and location of mine layouts and engineering facilities. H is to r ic a l D a ta - Historical data includes all time related information such as production and maintenance schedules, costs, economic variables etc. The efficient collection, storage, manipulation and retrieval i.e. in fo rm atio n m an ag em en t, of such data is an essential part of any mining operation. Traditionally, spatial data relating to a mining project are stored and manipulated as manual records e.g. maps, plans, sections, lithological and stratigraphic logs, seismic logs, and engineering drawings. Such non-digital graphical m odels are cumbersome, error prone, inefficient and, by virtue of their two dimensional nature, do not allow effective representation of the true 3D environment. The latter is essential in modelling behavioural phenomenon such as stress in the rock mass and air flow in ventilation circuits. With increased expectations in the evaluation, design and planning processes, there is an obvious need for more advanced methods of spatial information management. 1

C H A P T E R 1. I N T R O D U C T I O N

2

Exploration Geological Survey Geotechnical Survey Remote Sensing Borehole Drilling Sampling Programme

Resource Evaluation Geological Interpretation

Preliminary Mine Design Surface Layouts

Geotechnical Interpretation

Underground Layouts

Geostatistical Analysis

Process Plant Design

Geological Modelling

Shaft Design

Grade Modelling

Architectural Design

Ore Reserve Estimation

Electrical Design

Economic Analysis

Civil Engineering Design

Mining Method Decisions

Mechanical Engineering Design

Production Control Underground Surveying

Production Planning Geostatistical Analysis

Sampling

Dynamic Ore Reserves

Geological Mapping

Economic Modelling

Borehole Logging

Development Scheduling

Advance Measurement

Stoping Scheduling

Environmental Control

Selective Mining Alternatives

Equipment Scheduling

Resource Planning

Production Reporting Maintenance of Equipment

,

Mechanical Engineering Design

Detailed Mine Design Primary Development

Panel and Stope Design

Ventilation

Underground Services

Rock Mechanics

Geological Interpretation

Materials Handling

Equipment Selection

Budgets and Production Costs

Figure 1.1: U nderground M ine D evelopm ent P h a se s

1.1. SPATIAL I N F O R M A T I O N M A N A G E M E N T : A R E V I E W 1.1

Spatial I n f o r m a t i o n M a n a g e m e n t : A

3

Review

With the advent of automated mapping systems, data management tools and advanced com­ puter graphics, effective spatial information management can be achieved best using computer technology. Over the past 10 years (Rhind, 1989) a host of products have been developed which are referred to generically as G eographic In fo rm a tio n S ystem s (GIS). These systems allow sophisticated resource management of surface features: • automatic map generation; • interactive map modification; • the association of attribute data with spatial entities; • arbitrary scaling; • spatial query; • spatial searches; • the calculation of distances and surface areas. Such functionality offers an immediate improvement upon the traditional management techniques discussed. However, G IS are limited to modelling 2D and 2^D entities and are unsuitable for the representation of a true 3D environment (Turner, 1989; Rhind, 1989). Although there does not exist a system which can apply the functionality of a G IS to a 3D subsurface environment (Raper, 1989; Rhind, 1989; Kelk, 1989), there are a number of systems which offer cogent visualisation and limited analytical capability. Pertinent examples of such systems are discussed: In 1975, Notley and Wilson (Notley et a l ., 1975) developed a system which modelled underground mine layouts as 3D wire fra m e s (see Plate 1.1). A variety of perspective views could be generated using an ordered set of 3D co-ordinates digitised from plans and sections. Although this system was unable to model geological structures and lacked analytical functionality, it was a precursor to a variety of 3D geological modelling systems. Klein and models to treated as surfaces is

Pflug, at the Geological Institute in Freiburg, have investigated the use of surface represent the subsurface environment (Klein et al., 1989). Geological structures are homogeneous bodies and defined by a surface boundary. The representation of these a ‘mesh’ of polygonal elements which are generated from serial sections using surface tria n g u la tio n methods (Klein et al., 1989). With advanced computer graphics techniques, such polygonal meshes can be visualised as shaded perspective images. By utilising a number of light­ ing models, transparency techniques and depth cueing the ability to perceive shape is enhanced, as shown in Plate 1.2. A similar system to that of Klein and Pflug, called G Q C A D ™ , has been developed at the Ecole Nationale Superieure de Geologie. Instead of using polygonal elements, this system represents geological structures as a mesh of curved surface patches. The latter are generated by discrete sm ooth in te rp o la tio n of physical geological properties such as porosity (Mallet, 1989). This

C H A P T E R 1. I N T R O D U C T I O N

4

approach has the joint advantage of defining surface boundaries from ‘continuous’ data, rather than discrete serial sections, and allowing interactive model modification. Although the Klein/Pflug and G O ^ A D ™ systems exemplify current visualisation and model creation functionality, surface models are limited in their ability to represent geological prop­ erty variation within heterogeneous bodies. Such bodies are an integral part of any subsurface environment and can be represented using volume models. A common method of modelling volume is to decompose an environment of interest into a set of discrete disjoint blocks. Each block, which has a known size and location, is assigned a set of attribute values. The latter may include any of the previously mentioned data types i.e. geological, utility, or historical. Such a model is referred to as a block model. Unlike surface models, block models define explicitly the composition of space and can represent heterogeneous bodies. By utilising variable block sizes, such models can also represent structural boundaries, although only approximately. Furthermore, integral properties are computationally simple to calculate and, if attribute data are manipulated using a re la tio n a l d atabase m a n a g e m e n t sy stem (RDBM S) (Henley et al., 1988), it is possible to perform sp atial query , such as: • “What rock type is at a given point?”. • “What is the distance between two points?”. • “Identify all regions with a grade value greater than ‘x’ grammes per tonne?” . • “Where is electrical substation No. A ?”. • “When was Diamond Drill Hole No. E65 drilled and by whom?”. Such query is an essential requirement in the evaluation, design and planning of a mining project. Although block models have numerous advantages over surface models, the use of discrete 3D units to represent 2D surfaces has certain limitations: G e o sta tistica l In te g rity - Optimum block dimensions determined using geostatistical con­ siderations may be too coarse to accurately represent structural boundaries. Conversely, block dimensions suitable for modelling structural detail may result in a false impression of geostatistical integrity (Houlding, 1987). M in e L a y o u t A p p ro x im atio n - The dimensions of existing mine layouts are measured to an accuracy of 0.1 metre while the locations of survey control points are measured to an accuracy of 0.006 metre (Bak, 1987). Maintaining such accuracy in a block model is impractical as large computer memory requirements reduce computational efficiency; mine layout representations are approximate. For example, consider a project which has 10 kilometres of tunnels with a 5 metre X 6 m e tre cross-section. The number of blocks required to model the surface of these tunnels, to an accuracy of 0.1 metre, is « 5.3 million, as illustrated in Figure 1.2. Such a model requires « 5.3 M bytes of computer memory, assuming only one byte of data per block, and « 2 1.2 M bytes of computer memory, assuming one 32 bit integer per block.

1.1. SPATIAL I N F O R M A T I O N M A N A G E M E N T : A R E V I E W

5

In d ire c t M o d el C reatio n - Surface boundaries of geological structures are, presently, defined using either process simulation techniques (Thiessen et a l ., 1986) or semi-automated con­ struction methods (Lynx, 1988; Klein et a l ., 1989). Both approaches generate surface models which are converted to block models through ra s te riz a tio n 1 (Kaufman, 1987). As yet, no algorithms have been reported which can directly generate the block model of a geological surface boundary from ‘raw’ data e.g. drill logs. P o o r V isu a lis a tio n - The discretisation of space into a finite number of ‘blocks’ generates an aliased , or undersampled, image. Such visualisation is less cogent than for a surface model, as is illustrated by the example block model in Plate 1.3.

6m @ 0.1 m accuracy = 30 units 5 m @ 0.1 m accuracy = 25 units 10 km @ 0.1 m accuracy = 50,000 units Total = (((30 + 25) x 2) - 4) x 50,000 = 5.3 million

Figure 1.2: E x tran e ity of Block M odels These limitations can be overcome by integrating a block model with a surface model. Such an approach has been taken by a number of groups. Notable examples are Mineral Industries Computing Ltd. (M ICL) and Lynx Geosystems Inc. The M IC L D a ta m in e system, which uses triangular meshes, or w ire-fram e models12, to represent mine openings and geological structures, achieves integration by converting surface models into block models (Henley et al ., 1988). Although this approach improves model creation and visu­ alisation, analytical functions, which are performed on block models only, suffer approximation error.

1A general discussion on rasterization techniques is given in Procedural Elements for Computer Graphics (Rogers, 1985). A specific example of such a technique is presented in Section 4.4.5. 2M ICL use the term ‘wire-frame’ to describe their implementation of surface models. This is incorrect termi­ nology as the Datamine system treats each triangle in a surface mesh as a planar polygon. Such a mesh contains surface information which, by common definition, is contradictory to a wire-frame model: the correct term is boundary representation, as will be discussed in Chapter 2.

C H A P T E R 1. I N T R O D U C T I O N

6

The L ynx system avoids approximation error by treating surface and block models as independent entities. Mine openings and geological structures are represented by three parallel planes spaced at finite thickness intervals: solid m odel com ponents (Houlding, 1987). The intersection of such components with blocks does not require surface to block model conversion and, thus, the benefits of both modelling approaches is ensured without loss of accuracy. Although both the D a ta m in e and Lynx systems offer true 3D spatial data management ca­ pabilities, the surface modelling techniques employed neither support Boolean operations nor consider the concept of so lid ity 3; invalid solid models are easily generated. The latter may be self-intersecting, unbounded i.e. the surface boundary is not continuous, or suffer interference, as shown in Plate 1.4. Such characteristics result in design errors which include: • incorrect volume and mass calculations; • misleading visualisation i.e. incorrect plans and sections; • contradictory results from spatial queries. To overcome these problems, a number of researchers have investigated the use of solid m odelling techniques. The most notable of these include Karonen (1985) at the Helsinki University of Technology, Kavouras (1987) at the University of New Brunswick and Curran (1989) at the University of Toronto. Curran has applied A u to S o lid ™ to numerous mining projects. This system is based on a solid modelling technique known as C o n stru ctiv e S olid G eo m etry4 . Although the latter ensures model validity and allows both effective visualisation and integral property calculations, model creation and modification becomes prohibitively complex as the geometric complexity of the subsurface environment increases (Curran, 1989). The D aedalus system, developed by Kavouras (1987), uses a technique known as O ctree E ncoding which is a form of block modelling. By utilising variable sized blocks and recursive decomposition of space, a maximum model dimension of 225 x 225 X 225 units can be achieved. This enables the system to represent any complex geometric structure to an accuracy56of 0.006 metre at a scale of 1 in 200,000 (Kavouras, 1987). Unlike the Constructive Solid Geometry technique, the computational complexity of model creation, which is achieved using a d escrip tio n lan g u ag e6 and through conversion from a surface model (Smart, 1986), is independent of geometric complexity. Furthermore, because space is recursively decomposed, homogeneous and heterogeneous entities can be represented in the same ‘octree’ model at different resolutions; the encoding technique offers all the benefits of block modelling yet, ensures both model validity and geostatistical integrity and reduces approximation errors associated with modelling mine layouts.

3The definition of ‘solidity’ is presented in Chapter 2 . ^Constructive Solid Geometry is discussed in Chapter 2 . 5Practical experience, as discussed in Section 5.3.1.2, indicates that this claim is dubious. 6A description language allows the automatic creation of regular geometric shapes using mathematical con­ structs and parametric variables.

1.1. SPATIAL I N F O R M A T I O N M A N A G E M E N T : A R E V I E W

7

One characteristic of the octree encoding technique is that blocks are spatially indexed using a hierarchical encoding scheme. Such indexing allows any block in the model to be accessed efficiently and, therefore, facilitates a number of spatial searches (Kavouras, 1987): • interactive data retrieval using a graphical interface; • range retrieval i.e. identify all defined entities within a specified region of space; • closest neighbour analysis i.e. given a point in space, identify the closest entity of interest. Kavouras has claimed that these searches improve significantly the design process and, with fur­ ther development and application, can assist in the determination of optimal solutions (Kavouras, 1987). Examples of such applications include identifying surface boundaries, simulating particle or fluid flow and connected com ponent labelling. The latter is an image processing technique used to identify discrete homogeneous components and their spatial distribution. Although the D aed alu s system offers certain advanced functionality, the visualisation of octree models is computationally expensive and time consuming. Dedicated hardware is required to achieve display times comparable with those for surface models (Kaufman et a l., 1988). Karonen overcomes the problems of both A utoS olid ™ and D aedalus by integrating a variant of the octree encoding technique with a surface-based solid modeller known as the G eom etric W orkbench (G W B ). The latter models the surface boundary of homogeneous entities using ver­ tices, edges, faces and construction functions called E u ler operators (Karonen, 1985). These operators ensure that models are valid and that model creation and modification tasks, although computationally complex, are interactive and ‘transparent’ i.e. easy for the user to perform. As with the Klein/Pflug system, the G W B allows cogent visualisation but is unable to model heterogeneous bodies. Furthermore, integral property calculations within the G W B are compu­ tationally expensive requiring the solution of the integral:

1=

f f JS

(?) dp

where S is a solid and / (p ) is a function defining the set of points p within S . These limitations are overcome by converting the surface models to bintree models using a p o in t-in -p o ly h ed ro n test (Karonen, 1985). Bintree encoding is similar to octree encoding and offers equivalent functionality. The difference between the two techniques lies in the method of subdivision which is binary for the bintree and 8-ary for the octree. Karonen’s method of integration does not utilise the full potential of the bintree encoding tech­ nique as most modelling functions are performed on the surfaced-based solid models; bintree encoding is only used to represent heterogeneous entities and to perform integral property cal­ culations. This approach excludes such functionality as spatial search and increases overall computational complexity (Karonen, 1985). In summary, the spatial information management systems developed for use in the Minerals industry, although far in advance of the traditional ‘pen and paper’ methods, offer little more than the automation of manual processes. One exception is the D aedalus system which allows spatial searching. The latter cannot, realistically, be performed without computer technology and, as discussed, assists in the determination of optimal design solutions. There is an obvious need to

C H A P T E R 1. I N T R O D U C T I O N

8

further investigate the application of solid modelling techniques in mineral resources engineering and to determine new functionality which will improve both subsurface characterisation and mineral extraction. 1.2

Research Objectives

The objective of this research is to investigate current solid modelling theory and to identify a technique, suitable for the representation of 3D geoscientific environments, which is mathe­ matically robust and offers sufficiently wide functionality to be of use in all aspects of mineral resources engineering. Such a mandate requires the development of generic algorithms which can be tailored to the needs of each contributing discipline; problem specific functions are too numerous to achieve generality. With reference to the systems discussed in the previous section and given current computer technology, the generic algorithms of interest can be categorised as: M o d e l creation - There are three distinct methods of model creation: • S urface trian g u latio n : Surface triangulation of 2D contours and structural outlines is an effective method of generating 3D surface boundaries of geometrically complex homogeneous entities. • D e sc rip tio n language: A description language, which includes both functional and procedural modelling methods, allows the automatic creation of regular geometric shapes using mathematical constructs and parametric variables, is an effective method of generating the 3D surface boundaries of objects which cannot be defined as a series of 2D contours or sections e.g. a spiral access ramp. • S ta tistic a l gridding: The variation of mineral content or rock property within the subsurface environment is commonly determined using extension methods such as inverse distance weighting and geostatistical interpolation. Other methods, which are not considered in this thesis, include geological structure defini­ tion through process simulation and interactive boundary definition using a m a n -m a c h in e in terface.

M o d e l m o d ificatio n - Modification functions are essential for updating and changing existing models. Such functions include Boolean set operations , rigid tran sfo rm a tio n s, thresholding and blending fu n c tio n s. The latter allow the moulding of new parts onto existing 3D geometries while thresholding is a method of compositing variables into ranges. V is u a lis a tio n - An effective method of validating the geometry of an object or verifying a design is through cogent visualisation. Such visualisation includes: • 3D orthographic and perspective display; • hidden line and surface removal; • light source simulation; • shading; • transparency control;

1.2. R E S E A R C H OBJECTIVES

9

• view transformation. A n a ly sis - A number of generic functions should be implemented to assist in analytical opera­ tions. Such functions include: • In teg ral property calculation: Integral property calculations determine volume, mass and surface area of both homogeneous and heterogeneous entities. • S p atial search: Spatial search functions are valuable in determining object interfer­ ence, the distribution of homogeneous parts within a heterogeneous environment i.e. connected com ponent labelling, connected paths through the model and the spatial relation between entities i.e. adjacency. • S p atial query.

• R e latio n al query. • G eom etric D a ta C onversion: Conversion between model formats allows the integra­ tion of various design functions. For example, stress analysis in rock mechanics and ground water flow and transport study require spatial information in the form of fin ite /b o u n d a ry elem en t m eshes. Similarly, production scheduling and ventilation cir­ cuit design utilise directed graphs and cross-sectional areas: numerous design functions require geometric information. • S ectio n in g an d contouring: Working plans, maps, sections and engineering drawings are used to assist in the design process. It is essential, therefore, to be able to sec­ tion a model in any orientation and to contour any entities within the subsurface environment. To maintain generality, the modelling approach must take into consideration certain spatial characteristics associated with a subsurface environment: G eom etric C o m p le x ity - Geological structures and surface boundaries defined by threshold­ ing techniques, have irregular shapes which are difficult to represent using mathematical primitives; they are geom etrically complex. R e so lu tio n C o m p le x ity - The dimensions of structural features and the volume of rock asso­ ciated with a known geological property, determined by sample density and interpolation methods, vary greatly within a subsurface environment. Such variation is referred to as reso lu tio n complexity.

C o m p o sitio n a l C o m p le x ity - Geological property variation within a subsurface environment is extremely complex. Most features are heterogeneous and can only be discretised through thresholding; they are com positionally complex. In a c ce ssib ility - A subsurface environment is inaccessible without extensive excavation. In­ formation characterising such an environment is, therefore, incomplete and, sometimes, conflicting. In fulfilling these objectives, the contribution of this research to the applied earth sciences will be a greater understanding of the spatial complexities of a 3D subsurface environment and an A d v a n c e d Engineering Graphics Information S y s t e m (A E G IS) which offers generic functionality. The latter has application in a variety of geoscientific disciplines including Mining, Petroleum, Geotechnical and Environmental engineering, among others.

C H A P T E R 1. I N T R O D U C T I O N

10

This is a blank page.

1.3.

PLA TES

1.3

Plates

11

Plate 1.1: Wire F ram e Model of an U nderground M ine L ayout

Plate 1.2: Surface Model of Geological F eatu res (K lein , 1 9 8 9 )

CHAPTERL

12

This is a blank page.

INTRODUCTION

1.3. PLATES

13

Plate 1.3:

Plate 1.4:

A n A lia s e d B lo ck M o d el

A n In v a lid S o lid M o d e l - T h e ‘re d ’ c o m p o n e n t in te rfe re s w ith th e ‘g re e n ’ c o m p o n e n t

C H A P T E R 1. I N T R O D U C T I O N

14

This is a blank page.

Chapter 2

R e v ie w a n d A n a ly s is o f S o lid M o d e llin g T e c h n iq u e s

Solid m odelling is a body of theory and techniques which attempts to represent the geometric dimensions and spatial relations of physical ‘solid’ objects in such a way as to allow arbitrary geometric interrogation. The latter separates solid modelling from other forms of 3D modelling which tend to focus on specific points of interest (Mantyla, 1988). For example, visualisation is best achieved using shape m odels while surface properties are best represented using su rface m odels. Both these forms of modelling represent objects by their bounding surface and do not consider the internal volume.

To be able to analyse the functionality of the various solid modelling techniques it is important to understand the underlying theory. Many papers have been written on specific aspects of this theory, however, only a few have attempted to embrace it in its entirety. One such text, A n In tro d u c tio n to Solid M odelling by Martti Mantyla (1988), offers a succinct presentation and is the basis for the following discussion. Solid modelling can be perceived at three different levels (Requicha, 1980; Mantyla, 1988): 1. P h y sic al Objects: A physical object is a real world entity which exists in Euclidean 3D space ( E 3) and has infinite complexity. 2. M ath em a tica l Models: A mathematical model is one which idealises the so lidity of a physical object. Such a model should offer an intuitively clear understanding of the physical object and allow an ‘algorithmic’ study of its physical properties. 3. R ep resentations: A representation is an abstract concept which describes a mathematical model by means of notation and sem an tics. The latter define rules which associate the notation with geometry. Intuitively, a physical solid object is a portion of E 3 which has a known composition, a bounding surface and Euclidean properties, specifically volume. Such an intuitive characterisation is not mathematically robust and, thus, solid modelling theory utilises point-set and algebraic topology1 to qualify the concept of solidity (Mantyla, 1988; Requicha, 1980).

2 .1

M a th e m a tic a l P o in t-S e t M odels

The most general mathematical model of a solid object is a subset of E 3 : a set of points. Intuitively, such a set should be a single entity of finite dimension and have a continuous surface. 1Basic topological terms and concepts are presented in Appendices A and B. A more detailed explanation of the theory of topology is given in A Combinatorial Introduction to Topology (Henle, 1979).

15

16

C H A P T E R 2. R E V I E W A N D ANALYSIS O F SOLID M O D E L L I N G T E C H N I Q U E S

A : Object with ‘dangling’ surface and line

B : Regularised solid object —‘dangling’ surface and line are removed

Figure 2.1: R eg u larisatio n o f a S olid M odel Using point-set topology, this intuitive concept of a solid can be formally stated as (Mantyla, 1988): D e fin itio n 2 .1 A so lid is a bounded, closed an d connected subset o f E z. The class of point sets permitted by this definition includes all ‘solid’ sets. However, it also includes subsets of E 3 which do not have the Euclidean property of volume, such as points, lines and surfaces. To exclude such subsets from the notion of solidity, the latter can be further characterised using the concept of regularity (Requicha, 1980; Mantyla, 1988): D e fin itio n 2.2 The reg u larisatio n o f a p o in t set P , r ( P ) , is defined by

r ( P ) = c (> (P ) ) where c (P ) is the closure o f P a n d i (P ) is the in te rio r o f P . Such a se t is term e d a regular set.

The effect of regularisation is that all ‘dangling’ and ‘isolated’ parts of a point set are cut away to leave a set with a continuous surface or skin (Mantyla, 1988; Requicha, 1980). This is illustrated in Figure 2.1. Requicha (Requicha, 1977) summarises a bounded, closed, connected and regular subset of E 3 as an r-set. In the natural world a solid physical object has Euclidean properties which are independent of location and orientation; the object remains invariant under rig id tra n sfo rm a tio n s i.e. translations and rotations. Obviously, r-sets which model physical objects should have a similar characteristic. Mantyla formely defines rig id ity as (Mantyla, 1988): D e fin itio n 2.3 A rigid m odel is an equivalence class o f p o in t sets o f E 3 sp an n ed by the equiva­ lence relatio n o ; L et A a n d B be subsets o f E 3. T hen A a rig id tran sfo rm atio n .

o

B holds iff A can be m apped to B with

2.2. M A T H E M A T I C A L S U R FACE - B A S ED M O D E L S

17

One characteristic of an r-set is that, although it is a finite portion of space, it has infinite complexity. Such complexity can not be represented in a computer using direct methods and al­ ternative indirect methods must be employed. This requirement is referred to as re p re s e n ta tio n a l fin ite n e ss and can be achieved by further qualifying the concept of solidity using su rface-based m odels (Mantyla, 1988; Requicha, 1980; Baer et al ., 1979).

2.2

Mathematical Surface-Based Models

Surface-based mathematical models describe the surface boundary of a physical object by “a collection of faces which are glued together so that they form a complete, closing polyhedron or ‘skin’ around the object” (Mantyla, 1988). Using algebraic topology, this informal concept of a surface boundary can be formally stated as (Mantyla, 1988): D efin itio n 2.4 The surface boundary o f a so lid is a com pact, connected a n d o rien tab le 2m anifold.

The topological properties of 2-manifolds are well understood and are succinctly expressed by the Euler-Poincare formula:

F + V -E

=

2(S - H )

(2.1)

where F , V and E are the number of faces, vertices and edges in a polyhedron, S is the number of connected surfaces and H denotes the genus of the surface or the number of holes through the body. A detailed discussion on the Euler-Poincare formula is given in Appendix B. Intuitively, the surface boundary of a physical solid object should not intersect itself. Although Definition B.5 (Appendix B) enforces this characteristic topologically, certain surface boundaries, by virtue of Mobius’ rule, can be made to intersect themselves by the physical dimensions of the geometry used to embed them in E 3. This is illustrated in Figure 2.2. No purely topological condition can prevent self-intersection (Baer et al ., 1979); a surface boundary must be further characterised: D efin itio n 2 .5 T he su rface boundary o f a solid can n o t be self-in tersectin g . If the surface boundary of an r-set P, 6 (P ), is a compact, connected, orientable and nonselfintersecting 2-manifold M, P is a re alisa tio n of M in E 3: P is a m an ifo ld solid. Assuming this terminology and the above definitions, all surface boundaries have a realisation in E 3. However, not all r-sets are realisations of some surface boundary i.e. they do not obey the Euler-Poincare formula, as illustrated in Figure 2.3 (Mantyla, 1988). Such r-sets are referred to as n o n -m an ifo ld solids.

The bounding surface of a non-manifold solid is not a 2-manifold and, as such, cannot be di­ rectly modelled using topological properties. To overcome this problem, present practice treats such solids as the rigid combination of manifold solids. One method of determining these man­ ifold components is presented in G eom etric a n d Solid M odeling: A n In tro d u c tio n by Hoffman (Hoffman, 1989). Having characterised the concept of solidity and defined a suitable mathematical modelling space it is now possible to consider appropriate computer representations.

18

C H A P T E R 2. R E V I E W A N D ANALYSIS O F SOLID M O D E L L I N G T E C H N I Q U E S

Figure 2.2: A S elf-Intersecting P olyhedron

2.3

C o m p u t e r Representations

There are a number of approaches to representing solid models in a computer. These approaches differ in the modelling spaces, representation spaces and re p resen ta tio n schem es they support. To be able to discuss these differences and to determine the functionality of each approach it is important to define some desirable properties and associated terminology: Representation Space - Syntactically correct representations are finite structures constructed with symbols from an alphabet of syntactical rules. The collection of all syntactically cor­ rect representations is called a rep resen ta tio n space R . An element of R is a re p resen ta tio n r (Requicha, 1980). M o d ellin g Space - A m ath em atical m odelling space M is one whose elements are the mathe­ matical models of solids. An element of M is a solid m odel m (Requicha, 1980; Mantyla, 1988).

Representation Scheme - A representation scheme s is a relation between the elements of M and R (Requicha, 1980): s : M -y R

2.3. C O M P U T E R R E P R E S E N T A T I O N S The notation {m ,r } 1988).

19

Es denotes that r ER

is the image of m

EM

under s (Mantyla,

D o m a in - The d o m ain D of s is the set of physical objects which can be modelled in the space M.

R an g e - The range V of s is the set of solids m which can be represented in R. V a lid R e p resen tatio n - A representation r in the range V belongs to R and has corresponding elements in D . Such a representation is said to be valid (Requicha, 1980). U n am b ig u o u s R epresen tation - A representation r in V is said to be unam b ig u o u s if it corresponds to a single model in D (Mantyla, 1988): (m , r} £ s A (m ,) r }

Es

=>

m = m1

U n iq u e R ep resen tatio n - A representation r in V is said to be unique if the corresponding model in D has only one representation in V (Mantyla, 1988): {m, r}

Es A

{ m ,r '}

Es

=>■

r = r'

Using the above terminology some desirable properties can now be presented: 1. E xpressive Power: The expressive power of a representation scheme is determined by the extent of the domain D and the accuracy to which the elements of the domain can be modelled mathematically. 2. Validity: The validity of a representation scheme is determined by the extent of the range V . It ensures the integrity of representations and prevents the creation and manipulation of meaningless solid models. 3. Unambiguity: A representation scheme is unambiguous if all its valid representations are, themselves, unambiguous. Unambiguity ensures that a representation contains sufficient information to uniquely compute any mathematical property of the corresponding solid model. For example, an ambiguous representation may have multiple values of volume while its unambiguous counterpart will only have one such value. This is illustrated in Figure 2.4. 4. Uniqueness: A representation scheme is unique if all its valid representations are, them­ selves, unique. This property determines the equality of solid models. For example, a unique representation will be independent of orientation whereas a non-unique representa­ tion will change with orientation (Mantyla, 1988). 5. C onciseness: The conciseness of a representation scheme is determined by the amount of information required to represent a particular solid model. Generally, concise schemes are preferable as validity is easier to ensure and computer storage is minimal. However, in many practiced situations selective extraneity improves computational efficiency as relevant information need not be derived (Requicha, 1980).

6.

C losure o f O perations: If model creation, modification and manipulation operations pre­ serve the validity of representations they are said to close. If such operations do not close the validity of a representation scheme is not ensured.

C H A P T E R 2. R E V I E W A N D ANALYSIS O F SOLID M O D E L L I N G T E C H N I Q U E S

20

7. E ase o f Solid M odel C reatio n : The ease with which valid representations can be created is of obvious importance. Generally, schemes utilise d escrip tio n languages to reduce human interaction. The effectiveness of such languages is determined by how concise a solid model can be described and the robustness of validity checking mechanisms.

8.

C o m p u ta tio n a l E ase a n d A pplicability : The application of a representation scheme to a

given problem is determined by many of the properties presented above and the complexity of computing a solution. For example, it may be computationally simple to generate an image of an ambiguous representation yet, extremely difficult to calculate its volume.

Having presented some desirable properties of representation schemes it is possible to analyse the functionality of the various solid modelling techniques commonly used. According to Requicha (Requicha, 1980) there are six such techniques. Mantyla (Mantyla, 1988) categorises these into three generic classes:

1.

Decomposition Models.

2. Constructive Models. 3. Boundary Models. Multi-representational or hybrid models are a fourth class which employ several of the generic models simultaneously.

2.4. D E C O M P O S I T I O N M O D E L S

21

(‘prism’, n, r,

Figure 2.5: P rim itiv e In stan c e o f a P ris m 2.4

Decomposition Models

Decomposition models describe solids as a collection of primitive point sets which are ‘glued’ together. The type of primitive point sets used distinguishes between variations of the method. 2.4.1

Primitive Instancing S c h e m e s

The primitive are positioned represented by be represented

instancing technique models a physical object by families of point sets which in E 3 without intersection. Each member of a family, a p rim itiv e in s ta n c e , is a fixed-length tuple of values. For example, instances of the family of prisms can by tuples of the form: (p r is m , n, r, h )

where p r is m is a character string signifying the family, n is the number of sides and r and h are the radius and height of the circumscribing cylinder (Figure 2.5). Positioning of an instance is achieved by a rigid transformation which can be represented by a five-value tuple: (9 ,< j> ,8 x ,8 y ,8 z )

where 6 and are the angles of azimuth and elevation and 8x ,8 y and 8z are the translations along the x ,y and z axes. A distinguishing feature of primitive instancing schemes is the lack of means for combining instances to form more complex models. Generally, the latter are created by positioning each instance appropriately i.e. without intersection. This feature, along with a number of other characteristics, limits the value of such schemes. E xpressive power: The domain D is determined, primarily, by the families of instances. The latter are restricted to shapes which are mathematically understood; natural parameterisation of complex objects is difficult. Combinatorial operations also influence the domain but, as already discussed, they are limited. Validity: If each family is a valid solid then the validity of each instance can be ensured by simple enforcement algorithms. For example, the parameters of the tuple (p r is m , n , r, h ) must satisfy

22

C H A P T E R 2. R E V I E W A N D ANALYSIS O F SOLID M O D E L L I N G T E C H N I Q U E S

the fo llo w in g in e q u a litie s to ensure v a lid ity :

n r h

U n a m b ig u ity :

> > >

3 0 0

In s ta n c e s are u n a m b ig u o u s as each tu p le re p re se n ts a u n iq u e s o lid m o d e l: p r im itiv e

in s t a n c in g sch e m e s are u n a m b ig u o u s.

U n iq u en ess:

In sta n c e s are n o t u n iq u e as c a n be d e m o n s tra te d b y an e x a m p le . C o n s id e r th e tw o

in sta n c e s ( T —

b r i c k , l , h l , h 2,w 1,w 2 )

and

(b lo c k ,? , h ' , w ’)

a s illu s tr a te d in F ig u r e 2.6 ( M a n t y la ,

1988). G iv e n th e fo llo w in g c o n d itio n s, the tu p le s rep re se nt the sa m e s o lid m o d e l:

1=

1'

hi h2 — h1 vol — w 2 — w 1 Conciseness : P a r a m e tric re p re se n tatio n is concise. Closure of operations: O p e r a t io n s are clo se d if p r im itiv e s are p o s it io n e d w it h o u t in te rse c tio n . C om putational ease and applicability: T h e m a th e m a tic s fo r c a lc u la t in g th e p r o p e r tie s o f a n in sta n c e are w e ll u n d e rsto o d .

U n fo rtu n a te ly , each fa m ily o f in s ta n c e s re q u ire s a d iffe re n t c a l­

c u la tio n fo r s im ila r p ro p e rtie s and, therefore, fa m ily -s p e c ific k n o w le d g e m u s t be b u ilt in to the a p p ro p ria te a lg o r ith m s . T h is n o n -u n ifo rm m e th o d o f c o m p u t a t io n re q u ire s ne w a lg o r it h m s for every a p p lic a tio n a n d for each p rim itiv e .

2.4 .2

S p ace S ubdivision Schem es

In S e c tio n 2.1 a so lid m o d e l w a s defined in te rm s o f a m a t h e m a t ic a l p o in t set. B e c a u s e o f the in fin ite c o m p le x ity o f su ch a m o d e l it is n o t p o ssib le to lis t each p o in t in th e set. I t is p o ssib le , how ever, to lis t the set o f cu b e s or

units of space w h ic h are c o n ta in e d c o m p le te ly, or p a r tia lly , in

the m o d e l. I f these cu b e s are a ssu m e d to be n o n -o v e rla p p in g a n d o f u n ifo r m size a n d o rie n ta tio n the re su ltin g m o d e l is a

regular subdivision o f sp ace a n d is c a lle d an exhaustive enum eration.

F ig u r e 2.7 sh o w s the re g u la r s u b d iv is io n m o d e l o f a c y lin d e r.

A: T-brickprimitive

F ig u r e 2.6:

B :Block primitive

Prim itive Instances which are no t Unique

23

2.4. D E C O M P O S I T I O N M O D E L S

A cube can be represented by its eight corner points. In an exhaustive enumeration cubes have regularity and need only be defined by a single corner or centroid and a dimension. By imposing a specific spatial scanning order the {x, y, z } co-ordinates of each representative point can be mapped to an {t,y, k} element of a binary array such that the value of an element identifies the occupancy state of the corresponding cube. For example, one convention may associate the decimal value 1 with a ‘solid’ cube and a decimal value of 0 with an ‘empty’ cube. Such binary arrays are often referred to as sp atial arrays. Exhaustive enumerations are simple in concept and have a general domain. The latter is, however, approximate as surfaces of the object boundary that are not coplanar with the coordinate planes of the modelling space cannot be modelled precisely. Although this is limiting for certain applications, spatial arrays utilise integer arithmetic allowing a wide variety of algorithms to be performed with computational ease. The most restrictive characteristic of exhaustive enumerations is the massive memory required to model objects with any degree of accuracy. For example, assume the cylinder in Figure 2.7 to have a radius of 10m, a height of 30m and a central axis which is parallel to one axis of the modelling space. The memory requirements and associated extraneity2 for different modelling spaces would be: Modelling Space (unit3)

Dimension of Cube mxm Xm

Extraneity

Volume Error

Memory Required Kbits

300 60 30

0.1 x 0.1 x 0.1

35.8 % 36.0% 3 7 .3 %

2.57% 3 .13 % 6.95%

27,000 216 27

0.5 x 0.5 x 0.5 1.0x 1.0 x 1.0

Both the problems of memory and extraneity can be overcome by utilising the spatial coherency of solid objects. A daptive subdivision schemes achieve this by changing the size of each unit of space to fit the object of interest; a coherent region can be modelled by a few large cubes rather than many small cubes. Meagher (Meagher, 1982) has shown that for adaptive subdivision the number of cubes (or elements) required to model an object is proportional to the surface area of the object while for regular subdivision the number of elements required is proportional to the volume. A prime example of an adaptive subdivision scheme is the Octree rep resen tatio n which recursively subdivides the modelling space into eight equal sized cubes or octants. This recursive process is applied to those octants which lie on the surface boundary of the object i.e. those that are neither wholly inside nor wholly outside the boundary. Figure 2.8 is an adaptive subdivision model of the cylinder in Figure 2.7. The representation of an octree model is a hierarchical 8-ary tree. Each octant in the model is symbolised by a node in the tree where a node consists of an integer value and eight pointers. As with spatial arrays, the integer value identifies the occupancy of the associated octant. For example, if the octant is fully occupied by the object the integer value is set to ‘1 ’ and if it is not occupied by the object the integer value is set to ‘O’. Such octants, being homogeneous, are not further subdivided and their pointers are set to ‘nil’. If the octant lies on the surface boundary of the object it is subdivided in eight smaller octants and the pointers of the node will point to 2Extraneity is a measure of conciseness. For a block model this is the ratio: number of occupied cubes / total number of cubes in spatial array.

24

C H A P T E R 2. R E V I E W A N D ANALYSIS O F SOLID M O D E L L I N G T E C H N I Q U E S

Figure 2.7: R egular S p atial Subdivision M odel

Figure 2.8: A daptive S p atial S ubdivision M odel

2.4. D E C O M P O S I T I O N M O D E L S

25

these eight sons. The integer value is set appropriately. Figure 4.2 (in Chapter 4) illustrates a tree structure representing an octree model. An alternative to the pointer based method of octree representation is a lin e a r octree representa­ tion. This technique uses a p ath address which identifies the position of a node in the tree without the need for pointers3. The main advantage of this approach is that memory requirements are reduced by up to 8 0 % of a pointer based octree model (Gargantini, 1982). There are a number of variations to the octree concept of adaptive subdivision. One example is the bintree (Samet et a/., 1985) which recursively subdivides space into two equally sized units rather than eight cubes. These variations have similar properties to the octree scheme and are, therefore, not discussed. A good review is given in The D esign an d A n aly sis o f S p a tia l D a ta S tru c tu re s (Samet, 1990). One characteristic of spatial subdivision schemes is that the composition of a point in E 3 is known. This allows effective spatial search including p o in t/so lid , cu rv e/so lid and s u r f a c e /so lid classification4 (Hoffmann, 1989), border determination and identification of connected compo­ nents. In general, spatial subdivision schemes have properties favourable to a wide variety of applica­ tions. Certain characteristics have, however, limited their popularity. E xpressive power: As discussed, physical objects are modelled with a degree of approximation. Given this restriction, spatial subdivision schemes have an extremely general domain. Validity: Each unit of space in a subdivision scheme is a valid solid model and, therefore, all such schemes are valid. Due to the complexity of connectivity, however, a physical object may not be a single valid model but a combination of several valid models. This is discussed in Section 4.4.7. U nam biguity a n d Uniqueness: All spatial subdivision schemes are unambiguous and, for a fixed

resolution, are also unique. C onciseness: As discussed, exhaustive enumeration is not concise. Even though adaptive subdi­ vision schemes reduce memory requirements they are not considered to be concise. C losure o f operations: With both regular and adaptive subdivision schemes most operations are closed when applied to models which map onto the same region of E 3. One operation which is not closed is arbitrary rotation; units of space which are rotated by an angle that is not a multiple of 90° will not be coplanar with the co-ordinate planes of the initial modelling space. E ase o f so lid m odel creation: Model creation is based on conversion from other representation schemes. An alternative approach, which identifies the occupancy of space using interactive graphics techniques, has been developed by Yamaguchi (Yamaguchi et a l ., 1984). Intuitively, this method is restrictive and time consuming. C o m p u ta tio n a l ease a n d applicability: Spatial subdivision schemes have computationally simple algorithms involving list scans, tree traversals and case analyses. However, due to the size of model representations, many algorithms are slow. This reduces the applicability of such schemes as interactive functionality is a primary requirement in working environments.

3A d e ta ile d d iscu ssio n on lin e a r octree rep resen tation is given in C h a p t e r 4. 4

E n t it y c la s s ific a tio n d e te rm in e s w heth er the e n tity o f in terest exists w ith in a so lid o r k n o w n re g io n o f E 3 .

S u c h sea rch fu n c tio n s are d iscu ssed , w ith respect to lin e a r octree e n c o d in g , in S e ctio n 4.6.3.

26

C H A P T E R 2. R E V I E W A N D ANALYSIS O F SOLID M O D E L L I N G T E C H N I Q U E S

2.4 .3

C ell D eco m p o sitio n s

Cell decomposition schemes are similar to space subdivision schemes in that they model an object by discrete units of space, or cells, which are non-overlapping. The latter, instead of being a cube or a rectangle, can be any solid model which is topologically equivalent to a sphere. Figure 2.9 is a cell decomposition model of the cylinder in Figure 2.7.

Figure 2.9:

C e ll D e c o m p o sitio n M o d e l o f a C y lin d e r

Cell decomposition schemes have the advantage of offering a general domain without approx­ imation. However, if cells have surface boundaries which are not planar it is computation ally difficult to ensure validity and to calculate geometric properties. Such schemes have a limited application.

E x p re s siv e p o w er: As stated, the domain of cell decomposition schemes is general. If curved surfaces define the boundary of each cell the domain is exact up to the degree of the cells, typically quadratic (Mantyla, 1988). V alidity: A valid cell decomposition model has cells which are non-overlapping i.e. they must be either disjoint or connected by a corner point, an edge or a face. To ensure validity every pair of cells must be tested for intersection. For cells with non-planar faces, such as biquadratic surface patches, this can be a computationally expensive process.

U n a m b ig u ity a n d U n iq u en ess: A valid cell decomposition model is unambiguous but not unique (Mantyla, 1988; Requicha, 1980).

C o n c ise n e ss: Cell decompositions are relatively concise. A common representation consists of a list of 3D co-ordinates, defining c o n tro l p o in ts , and a list of cell e le m e n ts. Each cell element has a type code, which defines a parametric equation describing the element, and a set of pointers which identify the associated control points5 stored in the co-ordinate list. A typical example is a quadratic cell which might have 20 control points and two type codes defining a quadratic curve and a biquadratic surface patch (Mantyla, 1988).

5C o n t r o l p o in ts , also referred to as k n o t s , d eterm ine the shap e of a lg e b ra ic curves a n d su rfa ces. T h e la tte r are fu r th e r d iscu ssed in S e c tio n 2.6.2.

2.5.

C O N ST R U C TIV E M O D ELS

27

C losure o f operations-. In general, the mathematics for modifying cells with curved elements are either unknown or computationally expensive (Mantyla, 1988); closure of operations cannot be considered. E ase o f solid model creatio n : Intuitively, interactive generation of models with ‘curved’ cells is

complex as the validity of such cells is difficult to ensure. As with space subdivision schemes, cell decompositions are created by conversion from other representations. C o m p u ta tio n a l ease an d applicability: The difficulty of ensuring validity and the computational

complexity of model modification limits the general application of cell decomposition schemes. The use of algebraic curves and surfaces is, however, of value in determining the numerical solution of differential equations. One such application is Finite Element Modelling (FEM ). 2.5

Constructive M o d e l s

As with decomposition schemes, constructive models describe solid objects as a collection of primitive point sets. The construction operations used to combine these primitives are, however, more general including Boolean operations and rigid transformations. Variations of the method are distinguished by the type of primitive point sets used. 2.5.1

S w e e p Representations

The basic concept of sweep representation schemes is to create a solid model by sweeping a contour along a space curve. The primitive point set defined in this way can be represented by a set of parameters describing the contour and the space curve. There are three basic models which can be created by sweeping: 1. T ran slatio n al an d R o ta tio n a l Sweep Models: Consider, as an example, a closed curve which delimits a disk. If it is translated along a straight line segment the resultant model is a solid cylinder which can be represented by a radius r and a length l: a translational sweep as illustrated in Figure 2.10. A disk swept along an arbitrary spline: a g en eralised cy lin d er , is another example of a translational sweep model. If the curve is rotated about a local co-ordinate axis the resultant model is a solid torus which can be represented by a radius r and an angle of rotation 6: a rotational sweep as illustrated in Figure 2 .11. 2. Volume Sweep Models: A volume sweep model is one in which a parameterised volume is swept along a space curve. To illustrate such a model consider the torus in Figure 2 .11. It could be created by sweeping a sphere of radius r along a closed space curve of radius r f as illustrated in Figure 2.12. 3. G en eral Sweep Models: A general sweep model is one in which a space curve is swept along another space curve. Intuitively, sweep representations have a general domain which is exact. Unfortunately, it is difficult to ensure the validity of this domain as degeneracy is easily created. To illustrate degeneracy consider two examples: If a planar area A ,with a fixed orientation, is translated along a path P that has a tangent parallel to the plane containing A, then the interior of the resulting volume m a y have self-intersections.

28

C H A P T E R 2. R E V I E W A N D ANALYSIS O F SOLID M O D E L L I N G T E C H N I Q U E S

Figure 2.10: T ra n sla tio n a l Sweep

Figure 2 .11: R o ta tio n a l Sweep

angle 0

Figure 2.12: Volume Sweep

2.5. C O N S T R U C T I V E M O D E L S

2 9

A : Degeneracy of a rotational sweep through self-intersection

B : Degeneracy of a translational sweep resulting in a 2D object

Figure 2.13: D egeneracy o f Sweep M odels If the path P is, itself, parallel to the plane containing A, then the resulting sweep model will be two dimensional. Figure 2.13 depicts these two examples. In general, there is no closed-form mathematical description of the surface bounding a swept volume (Requicha, 1980; Hoffmann, 1989). For example, the cylinder in Figure 2.10 is bounded by finite areas on two linear surfaces and on one quadratic surface. Although rigid transformations can be readily performed on such models, Boolean operations are computationally complex and the mathematics of integral property calculations are unknown (Requicha, 1980); sweep representation schemes have limited application. 2.5.2

Constructive Solid G e o m e t r y

The C on stru ctiv e Solid G eom etry (CSG) representation schemes model physical solid objects as either Boolean constructions on primitive point sets or as combinations of solid components via regularised se t o p erations 6. In both approaches the model primitives are defined by irreducible polynomial functions which are analytic and real-valued (Requicha, 1980; Mantyla, 1988): (z,t/>*) | f { x , y , z ) > 0 Such primitive point sets are referred to as half-spaces as all the points which satisfy the function / (x, y, z ) > 0 are in the set of interest while those that satisfy the function / (x, y, z ) < 0 define its compliment; space is divided into two distinct regions. If a function defines a finite point-set, such as a sphere, it is both bounded and an r-set: it is a solid component. If, however, a function defines an infinite point set, such as a planar half-space, the primitive is unbounded and, therefore, is not an r-set. Solid components can be created by combining such half-spaces using classical Boolean operators. For example, consider a cylindrical solid component C . The latter can be constructed by combining two planar half6Regularised set operations, denoted by U*, fl* and \ * , are regularity-preserving variants of the classical Boolean operations. They are further discussed, with respect to linear octree encoding, in Section 4.5.1.

C H A P T E R 2. R E V I E W A N D ANALYSIS O F SOLID M O D E L L I N G T E C H N I Q U E S

30

F ig u r e 2.14:

Cylindrical Half-Space Model

sp a c e s a n d o n e c y lin d r ic a l h a lf-sp a c e u s in g a series o f in te rse c t o p e ra to rs ( M a n t y la , 1988) a s d e p ic te d in F ig u r e 2.14:

H S 1 : x 2 + y2 - r 2 < 0 HS2 : z > 0 H S 3 : z —h < 0 C = HS, n H S2 n H S3 w h e re r a n d

h are th e r a d iu s a n d h e ig h t o f th e c y lin d e r, re spe ctive ly.

H a v in g d e fin e d a n u m b e r o f s o lid c o m p o n e n ts, a so lid m o d e l c a n be c o n stru c te d b y c o m b in in g the c o m p o n e n ts u s in g re g u la rise d set o p e ra to rs a n d r ig id tr a n s fo rm a tio n s .

S u c h m o d e ls are,

gen erally, re p re se n te d in tw o p a rts:

1.

Com ponent representation: A s w it h p r im itiv e in sta n c e s, a c o m m o n m e th o d o f re p re se n tin g a h a lf-sp a c e is b y a ty p e cod e a n d a lis t o f size p a ra m e te rs. A n a lte rn a tiv e m e t h o d is to define a p o ly n o m ia l fu n c tio n in m a t r ix fo r m ( M a n t y la , 1988):

A12 A22 •^31 A32 A 4l A42 A ll

/(x,y,z) =

[x y z 1]

A 21

■^•13 A ia A23 A24 A33 A34 A43 A44

x y

z

1

and store the 16 coefficients, Ayy, or the 10 coefficients derived by evaluating the matrix products, in an array or list structure. This method is not concise.

2.5. C O N S T R U C T I V E M O D E L S

31

2. C o n stru c tio n o p erato rs representation: Construction operations are represented by a binary tree structure called a CSG tree. The non-terminal nodes of this tree represent either

rigid transformations or regularised set operations while leaf nodes represent the primitive components (Requicha, 1980; Mantyla, 1988): ( C SG tree)

::=

{p rim itiv e )| ( C SG tree){set o p eratio n ){ C S G tree )| {CSG tree){rig id m o tio n )

where {p rim itive) is a component representation, {rigid m o tio n ) is either a translation or a rotation and {set op eratio n ) is one of the regularised set operations U"',n* and \*. A CSG tree is illustrated in Figure 2.15. If a primitive in the C S G tree is the combination of a series of unbounded half-spaces, it can, itself, be represented by a C S G tree where (p rim itiv e ) is an unbounded half-space and {set o p eratio n ) is one of the classical Boolean operations U ,n and \ . Such a C S G tree may be used many times in the tree representing a complete solid model. The hierarchical nature of C S G representations lends itself to algorithms which utilise a d iv id ean d -co n q u er strategy. The latter divides a problem into a number of parts, recursively solves each part and combines the partial solutions to obtain the total solution. The computational efficiency and functionality of this approach has made C S G schemes one of the most widely used solid modelling techniques (Requicha, 1980; Mantyla, 1988). Some properties of C S G schemes do, however, restrict their use in certain ‘volume investigation’ applications such as medical angiography (Greenberg et al., 1989) and petroleum reservoir modelling (Jones, 1988). E xpressive power: The domain of a C S G scheme is dependent on the half-spaces which define the primitive solid components and the available combinatorial and transformational operators. Given the variety of possible half-spaces and the rigorous mathematics of these operators, such a domain is both extensive and exact. Validity: If a C S G tree has primitives which are all bounded (r-sets) it will be a valid repre­ sentation as neither regularised set operations nor rigid transformations destroy boundedness (Mantyla, 1988). This is only true, however, if the operators are general and can be applied to all the primitives in the domain.

If the primitives of the tree are unbounded validity is difficult to ensure requiring algorithms78 which are both memory and time intensive (Hoffmann, 1989). U nam biguity a n d Uniqueness: All valid C S G trees are unambiguous but not necessarily unique (Requicha, 1980; Mantyla, 1988). C onciseness: The conciseness of a C S G scheme varies according to the available primitives and the geometric complexity of the physical solid object. In general, mechanical parts can be represented concisely while natural objects, such as subsurface geological features and human organs, which axe geometrically complex, cannot.

Another factor which affects conciseness is the amount of attribute information required for graphical display. Edges and faces are not explicitly defined in a C S G model. As their de­ termination is computationally complex, requiring either ray casting or boundary ev a lu a tio n *, 7O n e m e th o d o f lo c a tin g th e in te rse ctio n s o f fam ilies o f surfaces is to use G r o b n e r b a se s te c h n iq u e s . T h e s e are d iscu ssed in G e o m e t r ic a n d S o lid M o d e lin g : A n I n t r o d u c t i o n ( H o ffm a n n , 1989). 8R a y c a s tin g a n d b o u n d a r y e v a lu a tio n te ch n iq u e s are w ell d o c u m e n te d a n d are n o t d iscu ssed in th is thesis.

32

C H A P T E R 2. R E V I E W A N D ANALYSIS O F SOLID M O D E L L I N G T E C H N I Q U E S

Figure 2.15: A C SG Tree

2.5. C O N S T R U C T I V E M O D E L S m o s t C S G sc h e m e s m a in t a in a S e c tio n 2.6) o f th e object.

33

b o u n d a ry file

w h ic h is a

b o u n d a ry r e p re s e n ta tio n

(d isc u sse d in

S u c h a file in c re a se s th e a m o u n t o f d a t a s to re d a n d d e cre ases the

degree o f c on cise n e ss.

C lo su re o f o p e ra tio n s:

A s th e c o n s tr u c tio n o p e ra to r s in a C S G m o d e l m u s t be c lo se d to ensure

v a lid ity , C S G re p re se n ta tio n s are closed .

E a s e o f s o lid m o d e l c rea tio n :

S o lid m o d e l c re a tio n is fu n d a m e n t a lly

an

in te ra c tiv e p ro c e ss u t ilis in g

e ith er a t e x t u a l la n g u a g e , m a t h e m a t ic a l c o n s tr u c ts o r g r a p h ic a l interfaces.

F o r e x a m p le , the

m o d e l in F ig u r e 2.15 c o u ld b e c re a te d u s in g th e fo llo w in g te x t u a l la n g u a g e : B lo c k

:

H e ig h t - 1

L e n gth - 4

W id t h - 4

P y r a m id

:

H e ig h t - 1

L e n gth - 4

W id t h - 2

C y lin d e r

:

A x is - Z

R a d iu s - 1

H e ig h t - 1

T r a n s la t e P y r a m i d in X : 1 T r a n s la t e C y lin d e r in Y : 2 T r a n s la t e C y lin d e r in X : 5 B lo c k u n io n P y r a m id m in u s C y lin d e r o r th e m a t h e m a t ic a l c o n s tr u c t (H o ffm a n n , 1989): (b lo c k ( 1 , 4 , 4 )

U* x -tra n s la te

( p y r a m id ( 1 , 2 ) , 1)) \ *

x -t r a n s la te ( y -tr a n s la te (z -c y lin d e r ( 1 , 1 ) , 2 ), 5) A m o re a lg o r it h m ic c re a tio n p ro c e ss e x tru d e s 2 D se c tio n s o f o bje cts in d e p th to fo r m a 3 D so lid w h ic h is p a r s e d a u t o m a t ic a lly in to c o m b in a t io n s o f p r im itiv e c o m p o n e n ts (B r o w n , 1982). W it h m o d e rn g r a p h ic s te c h n o lo gy , m a n y r e g u la r sh a p e s, su c h a s m e c h a n ic a l p a r ts , c a n b e cre ate d w ith re la tiv e ease. F o r g e o m e tric a lly c o m p le x s h a p e s these m e t h o d s are c u m b e rso m e .

C o m p u ta tio n a l e ase a n d a p p lica b ility :

C S G sch e m e s are b a s e d o n a rig o ro u s m a t h e m a t ic a l b a c k ­

g r o u n d a n d , th u s, th e ir fu n c tio n a lit y is extensive. C o m m o n to m a n y o f th e se fu n c tio n s are the

s e t m e m b e rs h ip c la s s ific a tio n 9

a lg o r it h m s w h ic h u tilise th e d iv id e -a n d -c o n q u e r stra te g y .

T h e se

a lg o r it h m s are c o m p u t a t io n a lly efficient for C S G trees th a t are w e ll b a la n c e d i.e. th e p r o b le m can be s p lit in to p a r t s o f e q u a l size ( M a n t y la , 1988). I f the tree is n o t b a la n c e d th e c o m p le x ity o f the c o m p u t a t io n c a n in cre a se ra p id ly . O n e e x a m p le w h e re t h is h a s a d is tin c t effect is in c a lc u la t in g in te g ra l p ro p e rtie s:

f

J A u*B

fd V = { fd V + [ fd V JA

f

J a \-b

JB

fd V =

f

Ja

w h e re / is a s im p le read-valued s c a la r fu n c tio n ,

dV

dV - [ fd V J A n*B A

and

B

are p o in t se ts re p re se n tin g a s o lid a n d

is th e v o lu m e diffe re n tial. T h e m a in p r o b le m is s o lv in g a n in te g ra l ove r th e in te rse c tio n o f

a n a r b it r a r y n u m b e r o f p r im itiv e s (L e e

et

a/., 1982); th e m o re im b a la n c e d th e tree, th e gre ate r

th e in t e r a c tio n be tw e e n p r im itiv e s a n d th e gre a te r th e c o m p u t a t io n a l lo a d (Le e

e t a l .,

1982).

®The set membership classification algorithms classify a candidate point set C against a reference point set R by determining which parts of C are inside, on the boundary and outside of R\ three sets CinR^ C on R and C ou tR (Mantyla, 1988). The mathematics of these algorithms have been widely reported and are not discussed in this thesis. A detailed explanation is presented by Tilove in Set membership classification: a united approach to geometric intersection problems (Tilove, 1980).

C H A P T E R 2. R E V I E W A N D ANALYSIS O F SOLID M O D E L L I N G T E C H N I Q U E S

34

Figure 2.16: P olyhedral M odel o f a Cube

2.6

Boundary Models

Both decomposition and C S G schemes model physical solid objects as point sets. An alternative approach is to model the solidity of an object by describing its surface boundary: a boundary model. Such a surface can be regarded as a ‘mosaic’ of faces which satisfy certain topological criteria and have a compact mathematical representation: a boundary re p re se n ta tio n or B-rep. (Mantyla, 1988). In general, faces are either p la n a r polygons or p aram eterise d bicubic surface patches.

2.6.1

Planar Po ly go n B o u n d a r y M o d e l s

In a planar polygon boundary model, also referred to sis a polyhedral model, faces are planar polygons described by a set of straight lines, or edges. The latter are, themselves, described by two 3D co-ordinates, or vertices as illustrated in Figure 2.16. The simplest representation of a polyhedral model, the explicit polygon B-rep. (Foley et al., 1982), is a list of vertex co-ordinates where the sequential order of the co-ordinates indicates the connectivity of vertices and edges. Consider the cube in Figure 2.16. The explicit polygon representation would be:

2.6. B O U N D A R Y M O D E L S

35

F ace

V e rte x c o -o rd in a te s

A

( ( * i, y i, * i) ( ( z 2, y 2, z 2)

A

( ( * 6 , y 6 , z 6)

(x 2yy2 jz2) (x 3 iy6 iz6) ( s 5,y s ,z 5)

A

( ( * * , y 5, z 5)

(* i,y i,* i)

A

((so y *,**)

A

( ( * 2 , y 2, z 2)

A

( s 3, y 3,23)

(X4,!/4,Z4)) ( Z 3,!/3,Z3))

(z 3,y 3,z 3)

(x 7,y 7,z 7) (x 3y y 8, z3) (*4 ,y 4 ,z 4) ( x7,y 7>z7)

(* i,y i,* i)

( x 5, y s , z s)

(* e , y « ,* « ) )

( z 7, y 7, z 7))

(x 3,y 3, z 3) ) (x 8 ,y s ,z 3))

S u c h a re p re se n ta tio n is n o t c o n c ise a s the c o -o rd in a te s fo r each v e rte x are s to re d th re e tim es. T h is e x tra n e ity c a n be e lim in a te d b y u s in g a

vertex-based B -re p . in w h ic h th e c o -o r d in a t e s o f

each ve rte x are o n ly s to re d once a n d are referenced b y a se t o f p o in te rs:

V e rte x

V e rte x

num ber

c o -o rd in a te s

t>i

(* i,y n * i) ( x 7 iy2 iz2)

v2 t>3 ^4 v6

v7 t>8

{x3,y 3>z3) (x 4 ,y 4 ,z 4) (x 3 ly3 )z3) {x6,y 6,z 6) {x7>y7, z7) {x3yy3,z 8)

Face

V e rtic e s

A

(vi» V2, v 3, u 4)

A

(v 2, v 6, v 7, v 3)

A

(t>6, v 5, v 8, v 7)

A

(v s,v x ,t;4,t;8)

A

(V4,V3,V 7, V 8)

A

{v2, v1, v3, v 6)

T o p o lo g ic a l p ro p e rtie s are re p re se n te d im p lic itly in b o t h th e e x p lic it a n d v e r te x -b a s e d m o d e ls. T h e se p ro p e rtie s c a n b e c o m p u t a t io n a lly e x p e n sive to d e te rm in e a n d a s th e y are r e g u la r ly u se d in m a n y o p e ra tio n s, su c h a s v a lid it y c h e c k in g , h id d e n su rfa c e re m o v a l a n d se t m e m b e r s h ip c la s s i­ fic a tio n s, th e ir e x p lic it re p re se n ta tio n is d e sirable . T h e

winged-edge d a t a s tru c tu re , d e v e lo p e d b y

B a u m g a r t ( B a u m g a r t , 1974), ac h ie ve s th is b y re p re se n tin g face-face n e ig h b o u r h o o d s a n d p o ly g o n o rie n ta tio n : a n

edge-based B -re p .

A c c o r d in g to D e fin itio n B . 4 ( A p p e n d ix B ) e very edge e in a re a lisa b le p la n e m o d e l is id e n tifie d e x a c tly tw ice a n d , th u s, a p p e a r s in e x a c tly tw o faces; tw o o th e r e d ge s

e1 a n d e" m u s t a p p e a r e o c c u rs

after e in th ese faces ( M a n t y la , 1988). F u rth e rm o re , a s e ach face is c o n s iste n tly o rie n te d ,

e x a c tly once in a p o s itiv e o rie n ta tio n a n d e x a c tly once in a n e g a tiv e o r ie n ta tio n ( M a n t y la , 1988). T h e w in g e d -e d g e d a t a s tr u c tu re re p re se n ts these p ro p e rtie s by:

• o rie n tin g a n e d ge b y d e fin in g a s ta r t a n d end vertex; • la b e llin g th e tw o faces, in w h ic h a n ed ge ap p e a rs, as e ith e r

clockwise o r counterclockwise

a c c o rd in g to the o rie n ta tio n o f th e edge; • id e n tify in g th e tw o e d ge s w h ic h a p p e a r before a n d afte r a n e d ge fo r e ach a s s o c ia t e d face: ‘n e x t ’ a n d ‘p r e v io u s ’ e d ge s in b o t h th e c lo ck w ise a n d c o u n te rc lo c k w ise faces; • re c o rd in g a n ed ge or

handle fo r each face.

T h e fu ll w in g e d -e d g e d a t a s tr u c t u r e is d e p ic te d in F ig u r e 2.17 a n d illu s t r a t e d b y th e re p re se n ta ­ tio n o f th e e x a m p le c u b e in T a b le 2.1.

C H A P T E R 2. R E V I E W A N D ANALYSIS O F SOLID M O D E L L I N G T E C H N I Q U E S

Figure 2.17: F u ll W inged-Edge D a ta S tru c tu re edge

v-start v -e n d

few feew

pew new

ei

vi

V2

fl



e

e2

V2

V3

fl

f2

e

fs

e

e3

V3

V4

e4

V1

V4

fl f4

f4

f x

e5

V2

V5

f6

e6

V2

V6

f2

f6

V8

f4

f5

e7

V4

\

2

eS e

peew neew

e2

e6

es

e3

e8

e6

e4 e7

e7

e8

e3

ei

e9

e4

e2 e4

e io

e l2 e9

e l2

en

e3

en

e io

e2

ei

e8

V3

V7

fs

f2

e9

V5

V6

f6

f3

e3 e5

e6

e io

V7

f2

f3

e6

e8

en

e i2 e9

f3

e7

e 12

e io

f4

e8 e9

e il

e7

es

e io

V6

e ll

V7

V8

f5

e i2

V5

V8

f3

vertex

handle

coordinates

V1

ei

( xi y izi)

face

handle

V2

e2

( x2 y2 z 2)

fl

ei

V3

e3

( x 3 y3 z s)

f2

e2

V4

e4

( x4 y 4 z 4)

f3

e9

V5

e9

( x5 y5 z 5)

U

e5

V6

e io

( x6 y 6 z 6)

fs

e il

V7

en

( x 7 y? z 7 )

f6

e6

V8

e i2

00X 00 00N

36

Table 2.1: B o u n d ary R ep re sen tatio n of a Cube using the W inged-Edge D a ta S tru ctu re

2.6. B O U N D A R Y M O D E L S

37

The edge-based representation described ensures that a polyhedral model is topologically valid; every edge can be appropriately identified by ‘tracing’ every face in the model. To illustrate this procedure consider face / 5 in Table 2.1. The handle edge (en ) has a clockwise orientation for the face and, thus, the next edge (new) is e7. Similarly, the edge next (neew) to e7 is e3. The latter has a counterclockwise orientation for face / 5; it is next to e8 (neew). The next edge in the polygon is en which is the handle: every edge in the face has been identified once. Although topological validity is ensured, the representation does not ensure g eo m etric in teg rity (Mantyla, 1988) i.e. by assigning inappropriate geometric information to a topologically valid surface boundary self-intersection can occur. This characteristic demands alternative validity checking algorithms which are computationally expensive. As polyhedral models describe surface boundaries using planar polygonal elements, cogent visu­ alisation is easily achieved. This has strongly influenced the popularity of such models in many computer graphics applications. Certain properties, however, have restricted their use in more analytical applications. E xpressive p o w er : The domain of a polyhedral B-rep. scheme is extensive as the polygons can be n-sided and positioned in any orientation. However, such a domain is not necessarily exact as a polyhedral model consists of planar faces. Validity: Topological validity of polyhedral models can be attained simply by ensuring that the

Euler-Poincare formula is satisfied. This can be achieved by using an appropriate representation such as the winged-edge data structure. As indicated, validity is also determined by geometric integrity which requires that (Requicha, 1980): • vertex co-ordinates must represent a single point in E s; • edges must be disjoint or intersect at a common vertex; • faces must be disjoint or intersect at a common edge or vertex. These conditions require set membership classifications which are computationally expensive (Requicha, 1980; Tilove, 1980; Mantyla, 1988) U nam biguity a n d Uniqueness: All valid polyhedral B-rep. schemes are unambiguous but not necessarily unique (Requicha, 1980; Mantyla, 1988). C onciseness: To ensure validity a polyhedral B-rep. records face, edge and vertex neighbour­ hoods. Such a representation is extraneous and is, in general, not considered to be concise (Requicha, 1980; Mantyla, 1988). C losure o f operations: If a polyhedral model is a valid solid model, rigid transformations will

close. Set operations, however, may not close; both classical and regularised Boolean operations are based on topological theory and do not consider geometric integrity. E ase o f solid m odel creation: The construction of any reasonably complex polyhedral model is beyond the capabilities of most users (Mantyla, 1988). Model creation is achieved by means of:

D e scrip tio n Lan gu ag es - A description language uses textual and mathematical constructs to generate a polyhedral model of a known mathematical shape. Such languages, which are similar to those used in C S G schemes, are difficult to implement as rigorous controls are required to ensure model validity. An example of a description language is discussed in Section 3.2.

38

C H A P T E R 2. R E V I E W A N D ANALYSIS O F SOLID M O D E L L I N G T E C H N I Q U E S

Surface T ria n g u la tio n s - The surface boundary of many solid objects can be represented by a set of co n to u r strin g s. If the points on these strings are connected in a controlled fashion it is possible to generate a polyhedral model: su rface trian g u latio n . Such models are approximate as the initial data is incomplete (except for rectilinear shapes such as cubes). A surface triangulation algorithm is discussed in Section 3.1. C o n ve rsio n from C S G - Conversion from C S G models, also referred to as boundary ev alu a­ tio n , is a common method of model creation. Unfortunately, the available domain offered by this approach is limited as many C S G models are difficult to realise in a B-rep. scheme (Mantyla, 1988). For example, the object in Figure 2.18 can be represented in a C S G scheme as the difference of two cylinders. As a polyhedral model, however, this object is difficult to represent; the edge where the two cylinders touch appears in four faces and is not topologically valid.

Figure 2.18: In co n sisten cy in C SG to B o u n d ary M odel C onversion C o m p u ta tio n a l ease a n d applicability: As stated, the validity of polyhedral models is difficult to ensure, requiring set membership classifications. The latter, also used in Boolean operations, axe not difficult conceptually, but their implementation is complex; primitive geometric and topological operations must be designed for all the possible positions of incidence (Hoffmann, 1989). Furthermore, as classification algorithms require numerical techniques, the precision and stability of calculations are not guaranteed (Hoffmann, 1989). These characteristics have limited the use of polyhedral B-rep. schemes in analytical applications.

2.6.2

C u r v e d Surface B o u n d a r y M o d e l s

In a curved surface boundary model faces are parametric bicubic surface patches which are described by known points, vectors and curves. Intuitively, such patches are unit squares of elastic material which twist and distort in space to fit a part of the surface of the physical solid object. By using blending and in terp o latio n equations these patches can be joined to make a ‘mathematical quilt’: the surface boundary of the solid object (Krouse, 1981). A surface patch is a finite region of space. The x, y and z co-ordinates of each point in this space can be expressed by a third-order or cubic polynomial of two (b i ) parameters s and t: a parametric bicubic surface patch. The form of the parametric equation x (s,£) is:

2.6. B O U N D A R Y M O D E L S

3 9

an s3£3 + a 21s 2t 3 + a 31s t 3 + a 4lt 3 +

a l2s 3t 2 a 22s 2t 2 a 32st a 42t 2

+ + + +

a l3s st CL2 3 s t a 33s t a 43t

+

+ + +

a 14s 3 a 24s 2 a 34s

+ + +

a 4A

The equations y (s, t ) and z (s , t) have similar forms. Varying both parameters from 0 to 1 defines all the points on the patch (Foley et al ., 1982). The sixteen bicubic coefficients can be expressed in terms of four control points and their asso­ ciated tan g en t vectors. The latter indicate the slope of the surface in the x, y and z directions at the known points. This is illustrated by the C oons’ patch (named after the late Steven Coons) in Figure 2.19 (Foley et al ., 1982).

s

Figure 2.19: C oons’ P atch The mathematics of calculating bicubic coefficients is discussed in many texts and, therefore, there is no need for further explanation. One such text is C om putational Geometry for Design and M anufacture (Faux et al ., 1979). The simplest representation of curved surface boundary models is an array of control points and associated tangent vectors. The number of control points required for each patch is determined by the form of the bicubic polynomial. For example, the H erm ite form requires only four points while both the B ezier and B-spline forms require twelve points (Foley et al., 1982). In general, such a representation is more concise than a polyhedral representation. Another advantage of curved surface B-rep. schemes over polyhedral B-rep. schemes is that the domain is both extensive and exact: control points and tangent vectors can be manipulated to fit precisely the surface of the physical solid object of interest. Unfortunately, these advantages are severely compromised by the increased computational complexity of analytical functions:

C H A P T E R 2. R E V I E W A N D ANALYSIS O F SOLID M O D E L L I N G T E C H N I Q U E S

40

B o o lean O p erations - Common to all Boolean operations is the problem of identifying the intersection of two or more surfaces. One approach to solving this problem is curve tracin g (Hoffmann, 1989): Construct a local approximation, such as a curve tangent, at a point p on the curve of intersection of two or more surfaces. Estimate the next point on the curve by stepping along the approximation. Refine the estimate using an iterative method. The approximant used at a curve point p is a truncated Taylor expansion of the intersec­ tion and the estimated next point is refined using the Newton-Raphson method (Hoffmann, 1989). Both the latter and the Taylor expansion are numerical methods which are compu­ tationally time consuming and sensitive to hardware precision. In te g ral P ro p e rtie s - Integral properties can be calculated by either applying the divergence theorem 10 to a polyhedral approximation of the curved surface (Lee, 1982) or performing an approximate integration over the curved patches (Timmer et a/., 1980). Both approaches introduce errors which have not been analysed fully. The construction of a curved surface model is, generally, a complex process involving the gener­ ation of surface patches from a space curve netw ork (Kimura, 1984). The latter is a ‘mesh’ of parametric cubic curved line segments. These curves, which are the edges of parametric bicubic surface patches, are generated by interpolating between control points10 11 The latter are either user defined or generated by other systems. For example, the G O C A D ™ system generates a space curve network by converting a contour data set into a triangulated network and interpolating between vertices (Mallet, 1989). Generating surface patches from a space curve network is computationally complex and requires a regular mesh. If the mesh is irregular, as illustrated in Figure 2.20, the generation process is extremely difficult. There is, as yet, no adequate mathematical theory for handling such cases (Kimura, 1984; Mallet, 1989). The difficulty of model creation, along with the computational complexity of analytical functions, limits the use of curved surface B-rep. schemes in many applications. In general, such schemes are used for surface modelling rather than solid modelling.

2.T

H y b rid M odels

The modelling schemes discussed so far all have certain disadvantages. Intuitively, a combination of these schemes would overcome these disadvantages and offer a superior modelling technique. This concept has led to the development of hybrid re p resen ta tio n schem es. The most common approach to hybrid representation is to combine two or more independent schemes by converting one model to another. For example, the visualisation of C S G models is improved by conversion to a boundary model. The types of hybrid representations which are based on this approach can be characterised by their p rim a ry and secondary representations. At present, two major architectures are used. These are illustrated in Figure 2.21 (Mantyla, 1988). 10T h e m e th o d o f d ire ct in te g ra tio n is an a lte rn a tiv e to th e use o f th e d iverg en ce th e o re m . B o th these m e th o d s are discussed in A n I n t r o d u c t i o n to S o lid M o d e lin g ( M a n ty la , 1988). 11 T h e m a th e m a tic s o f p a ra m e tric c u b ic curves is s im ila r to th a t o f p a ra m e tric b ic u b ic surface p a tch es a n d is discu ssed fu lly in num erou s tex ts.

2.7. H Y B R I D M O D E L S

A : Regular Space Network

41

B : Irregular Space Network

Figure 2.20: R egular an d Irreg u lar Space C urve N etw orks Schemes which have C S G trees as a primary representation convert to a boundary model using the boundary evaluation technique and to a decomposition model using set membership classi­ fications. Such schemes have improved display capabilities and more efficient integral property calculations over pure C S G representation (Mantyla, 1988). Unfortunately, as already discussed, both boundary evaluation and set membership classifications can be computationally complex and, in certain cases, are unable to realise a correct conversion. The second group of schemes have as their primary representation a boundary model. The advantages of such schemes are specific to particular applications: • Conversion from C SG trees improves model creation by incorporating more sophisticated description languages. This is only of value if elements of the domain are regular mathe­ matical objects. • Conversion to decomposition models12 allows more efficient validity and interference check­ ing. Unfortunately, this process does not assist in correcting invalid models as converting back from decomposition to boundary models is neither robust nor computationally easy. An alternative approach to hybrid representation in teg ra te s two schemes, typically a decompo­ sition model with either a C S G tree or a boundary model (Mantyla, 1988). The most effective example of such a scheme is the E x ten d ed Octree developed by Brunet, Navazo and Ayala (Navazo et a l ., 1986). Unlike standard octrees, as discussed, the extended octree model uses octants to index the geometric entities of a boundary model. Recursive subdivision is applied until an octant contains either a vertex, an edge, a face, or is homogeneous. Each complex octant is a pointer to its associated geometric entity which is stored in an edge-based data structure. 12A n a lg o rith m to con vert a p o ly h e d r a l b o u n d a ry m o d e l to a lin e a r o ctre e is presented in S e c tio n 4 .4 . A lte r n a tiv e m e th o d s are d iscu ssed in p ap ers p resen ted b y M e a g h e r (M e a g h e r, 1982), C h a n ( C h a n e t a l., 1986) a n d T a m m in e n ( T a m m in e n e t a l., 1984) am o ng o th e rs.

42

C H A P T E R 2. R E V I E W A N D ANALYSIS O F SOLID M O D E L L I N G T E C H N I Q U E S

A : Primary Representation — CSG Tree

B : Primary Representation — Boundary Model Figure 2.21: C o-existing In dependent H ybrid R ep re sen tatio n A rch itectu res The extended octree, and similar schemes such as the polytree (Carlbom, 1987) and the enhanced octree (Fujimura et al., 1985), overcome most of the disadvantages of both boundary and regular spatial subdivision representations: • The representation is more concise than a pure octree model. • Boolean operations axe simpler to perform than for those in pure B-rep. schemes (although more complex than for those in pure octree schemes). • A boundary model can be reconstructed from the complex octants without loss of infor­ mation (Navazo et a l ., 1986). • Integral properties are simple to calculate. One characteristic of octree based integrated hybrid representations, termed the black hole ef­ fect (Durst et a l ., 1989), limits the use of such schemes in applications where solid objects are geometrically complex (Brunet, 1990). If a face in a polyhedral model has a high aspect ratio i.e. it is long and thin, the number of subdivisions required to ensure that an octant contains only one geometric entity can be extensive. This is illustrated in Figure 2.22 (Durst et al ., 1989). Such subdivision is ‘heavy’ i.e. requires a large amount of memory, difficult to predict or ‘see’ and theoretically infinite or ‘bottomless’: a black hole (Durst et al., 1989).

2.8. C H O S E N SOLID M O D E L L I N G A P P R O A C H

43

Figure 2.22: The Black Hole Effect

2.8

C hosen Solid M odelling A p p ro ach

Based on the theory of solid modelling, system evaluation, present and foreseeable technology and the experiences of researchers such as Kavouras, Karonen, Mantyla, Samet, Gargantini, Brunet and others, it is proposed that a hybrid scheme combining two independent techniques: boundary representation and adaptive spatial subdivision, is an effective method of modelling a 3D subsurface environment which has high resolution, compositional and geometric complexity. Adaptive spatial enumeration, which is uniquely suited to representing universes with composi­ tional complexity, has numerous favourable characteristics: •

General dom ain : Although objects are modelled with a degree of approximation, the ex­ pressive power of adaptive spatial subdivision is extremely general. For a subsurface envi­ ronment, this approximation error is inconsequential (Mill et al ., 1989) as the initial model creation process is itself approximate; both surface triangulation and statistical gridding use interpretive techniques based on incomplete information.



Recursive decomposition: The recursive nature of spatial subdivision facilitates the mod­ elling of universes with a high resolution complexity.



Spatial composition: Every unit of space within the model has a known composition. This allows the representation of a universe with a high compositional complexity i.e. both heterogeneous and homogeneous entities simultaneously.



Inherent validity.

• Closure of operations. • Model modification: Boolean operations and rigid transformations are computationally

simple. •

Spatial indexing: The hierarchical spatial indexing technique allows spatial search and de­ creases overall computational complexity; most algorithms involve list scans, tree traversals and case analyses.

Other advantages of adaptive spatial subdivision, which have not been discussed, include:

C H A P T E R 2. R E V I E W A N D ANALYSIS O F SOLID M O D E L L I N G T E C H N I Q U E S

44

• R D B M S in teg ra tio n : The hierarchical indexing method used in adaptive spatial subdivision labels each known unit of space with a unique key or index. By using such keys as either fields within a relational table or as table id en tifiers it is possible to integrate the spatial model with a RDBM S. Mao, at the Kunii Laboratory, has shown that such integration allows effective relational query of attribute information associated with a spatial model (Mao et al., 1989). • F in ite E lem en t M eshing : Shephard, at the Rensselaer Polytechnic Institute, has developed an automated finite element mesh generator based on octree encoding and adaptive anal­ ysis. The input to this generator is a geometric octree model; adaptive spatial subdivision can be integrated with F E M (Shephard et al ., 1988). Although adaptive spatial subdivision has numerous favourable characteristics and certain unique advantages over other solid modelling techniques (in a 3D subsurface modelling application), the scheme has two distinct disadvantages:

1.

V isualisation: The visualisation of an adaptive spatial subdivision model is a computa­ tionally intensive process requiring advanced and powerful hardware to achieve acceptable display times. Furthermore, because surface boundaries are approximated by orthogo­ nal faces, it is difficult to apply advanced graphics techniques such as shading and depth cueing13.

2. M odel creatio n : The creation of an adaptive spatial subdivision model is best achieved by conversion from a surface model. Certain direct creation methods have been developed (Yamaguchi et al ., 1984; Yau et al., 1981), however, Smart has shown these to be of little use in a geoscientific applications (Smart, 1986). Boundary representation overcomes these disadvantages as it offers cogent visualisation and allows model creation through both surface triangulation and a description language.

13R ecen t te ch n o lo g ica l develop m ents have show n th a t the cogent v isu a lisa tio n o f vo x el m o d e ls i.e. b lo ck m o d els, c a n be a chieved w ith a p p ro p ria te h a rd w a re . A t the tim e o f p re lim in a ry in v e stig a tio n , how ever, such c a p a b ility was n o t a v a ila b le .

C h a p te r 3

B o u n d a r y R e p r e s e n t a t i o n in A E G I S

Numerous surface-based modelling systems have been developed which use boundary represen­ tation. Many of these offer extensive model creation and visualisation functionality while only a few offer comprehensive solid modelling capabilities i.e. closure of operations, topological validity checking mechanisms, boolean operations etc. Given that the function of boundary representation in A E G IS is to assist in the creation and visualisation of geometric shapes and with the relative abundance of surface-based modelling systems, it was felt that the implementation of a surface triangulation algorithm, a description language and a 3D display system would neither be a contribution to science nor a practical proposition given the available time and man-power: boundary model creation and visualisation in A E G IS is fulfilled by a commercial system known as M o v ie.B Y U 1. It should be noted that the choice of M ovie.BYU was strongly influenced by budget constraints. The M ovie.BYU system, which for the rest of this thesis will be referred to as ‘Movie’, is a “general purpose computer graphics software system which displays and manipulates data repre­ senting mathematical models whose geometry may be described in terms of polygonal elements, polyhedral solid elements, or contour line definitions” (Christiansen et al., 1986). It comprises a series of five F O R T R A N programs which operate on a vertex-based boundary model. O f these programs only D isplay, U tility and M osaic are utilised in A E G IS . ‘Display’ is an interactive display program which has extensive functionality including model and view transformations, hidden line and surface removal, a variety of shading models, colour control, transparency, shadow generation, fog simulation and image enhancement capabilities. This program operates on 3D polygonal surface mesh models stored in a hierarchical database. The latter allows individual objects in the modelling domain to be displayed and manipulated independently. Furthermore, copies of an object can be grouped together and treated as a single entity giving great flexibility in scene composition. ‘U tility’ is an interactive model creation program which uses a description language to generate the polygonal surface mesh of irregular and warped hexahedrons, thick partial ellipsoids and bodies of revolution and/or translation. The program also facilitates data editing such as polygon generalisation and orientation, file merges and vertex manipulation. ‘Mosaic’ is an interactive program which generates a polygonal surface mesh from a set of planar parallel contours. This generation process utilises a sh o rte st d iagonal heuristic surface triangu­ lation algorithm developed by Christiansen and Sedeberg (Christiansen et a l ., 1978). As many of the contributors to Movie are pioneers of 3D computer graphics e.g. David Evans and Gary Watkins, the system is regarded as an industry standard. As such, the rendering concepts 1M o v i e . B Y U w as d e v e lo p e d a t th e U n iv e rs ity o f U t a h a n d B r ig h a m Y o u n g U n iv e r s it y ( B Y U ) a n d is c u r r e n tly b e in g d is t rib u te d b y th e E n g in e e r in g C o m p u te r G r a p h ic s L a b o r a to r y at B Y U .

45

46

C H A P T E R 3. B O U N D A R Y R E P R E S E N T A T I O N IN AEGIS

and algorithms used in Movie are documented in both technical papers and monographs. A regurgitation of these monographs is unwarranted. Suggested references include F u n d a m e n ta ls o f In te ra c tiv e C o m p u ter G rap h ics (Foley et al., 1982), P rocedural E lem en ts fo r C o m p u ter G raphics (Rogers, 1985) and F u n d a m e n ta ls o f T h ree-D im ensional C om p u ter G raphics (Watt, 1989). Although rendering techniques have been adequately documented, methods of model creation are not as widely reported and, therefore, this chapter will concentrate on the surface triangulation algorithm used in Mosaic and the description language used in Utility. 3.1

M o d e l Creation - Surface Triangulation

Surface triangulation is a process which generates a 3D polygonal surface mesh by connecting points on 2D planar parallel contour or border lines. More formally, this can be stated as (Ganapathy et al., 1982): Given two borders represented by point sequences p , , i = 0, l,...,m — 1 and q j , j = — 1 produce a set of triangular faces forming the best spanning surface.

0,1 ,..., n

Although the qualification of a ‘best’ spanning surface is subjective, it is possible to define an ‘acceptable’ surface as one which satisfies two topological constraints: 1. Each contour seg m en t , the line connecting two consecutive points on a contour, appears in exactly one surface tile where a surface tile is a triangular face enclosed by a contour segment and two diagonals, or spans. The latter must be connected to the endpoints of the contour segment as illustrated in Figure 3.1a. 2. Every span is identified with exactly one other span. These constraints can be enforced by representing two adjacent contour or border lines as a directed graph G (V, A ) where the set of vertices V corresponds to all possible spans and the set of arcs A corresponds to all possible tiles. This is illustrated in Figure 3.16 where vertex v,j is the span { p , —* q j } and the arc {vty, vt+ 1J} represents the triangle { p i,q j,P i+ i} In the context of graph theory, the above constraints can be stated as (Smart, 1986):

1.

Each arc should be the result of a positive unit increment in either i or j .

2. The path from the first to the last vertex in the graph should be connected. If the initial span in the triangulation process is {px «-> q i}, the spanning surface can be any path from vxl to vmn; the number of possible paths and, thus, spanning surfaces, is (Ganapathy et a l ., 1982): A (m,n)

(m + n)! m! x n!

Intuitively, some criterion must be defined to determine a single path through the graph. In Mosaic this criterion is the least su m to tal length of all connecting spans (Christiansen et al ., 1986).

3.1. M O D E L C R EA T IO N - SU RFA CE TR IA N G U LA TIO N

47

A : Polygonal Element

G k )translate

=

('> 3 > k )rotaU

=

V

*

R \ ]

0 0 oA 0 1 0 0 0 0 1 0 tk 1 )

(4.18)

U , t j , t k are th e tr a n s la tio n v a lu e s in the i , j a n d k d ire c tio n s re spe ctive ly.

T h e r o ta tio n m a t r ix 7

R is:

R (

* T J1

T is:

( 1

w h ere

*0



(p c o s xp (sin 9 sin ; struct line.points *line, *temp_line; line = bresenham_line(base_vertex_i, base.vertex.j, base.vertex.k, apex.vertex.i, apex.vertex.j, apex.vertex.k) ; while (line != NULL) { code = encode(line->i, line->j, line->k); found.node = binary.search(code); /* Process the result of the binary search: *) Write to disk *) Calculate integral properties *) Visualise etc. */ temp.line = line; line = line->next_line; free(temp.line);> Program 4.10: A R egular ‘L in e ’ S earch u tilising the E ncoding A lgorithm

function. The adjacent neighbours of the (contact) surface voxels identified are then determined using the neighbour finding algorithm. The object number of each neighbour represents an adjacent component. These numbers are recorded and are used in further processing. The function of the surface contour search is to generate a set of cartesian co-ordinates which, when sequentially connected, define a contour string in a plane orthogonal to the universe axes. To achieve this a voxel surface, which can be identified by using either the border or the contact search function, must be sliced , sorted and decoded. A slice is a set of voxels which lies in a plane orthogonal to the axes of the universe. If such a slice is intersected with a surface the resultant voxel set will be a contour at the given i , j or k elevation. This process is referred to as slicing and is illustrated in Figure 4.33 and shown in Plate 4.10. Implementation of the process can be achieved by performing a list scan operation and an investigation of the component of each octal string which corresponds to the axis of elevation. An octree set intersection operation is unnecessary, as illustrated in Program code fragment 4 .11. The voxel set representing a contour string is stored in ascending order (a characteristic of the linear octree encoding scheme). Such an order does not convey any information about the connectivity of points in the string and, therefore, the voxel set must be sorted accordingly. The latter is achieved by use of a modified neighbour finding algorithm which has a limited set of adjacency directions determined by the orientation of the slice. For example, if the slice is parallel to the i O j plane the adjacency directions will be {R , D , L, U }, as illustrated in Figure 4.34.

C H A P T E R 4. A D A P T I V E SPATIAL SUBDIVISION IN AEGIS

132

/* /* /* /* /*

This algorithm assumes that all octants have a grouping factor of 0 i.e. they are voxels. If the octree model has not been decomposed prior to slicing a decomposition function can be used to process appropriate octants i.e. those that intersect the desired elevation.

*/ */ */ */ */

struct octree_node linear_octree[MAX_NODES]; i = slice = 0; mask = 1; bit_position = 1 «

axis;

/* ‘axis’ has values which equate to bit /* positions (refer to bit interlacing /* algorithm): /* i == 0 : j == 1 : k == 2

*/ */ */ */

while (i < resolution) { /* This control loop is equivalent */ if ((mask & elevation) > 0) { /* to encoding a spatial index. */ slice |= bit_position; mask « = 1; bit_position « = 3; > else { mask « = 1; bit_position « = 3; > i++;> for (i = 0; i < number_of_nodes; i++) I if((slicefelinear_octree[ i ] .code) = = slice) process(linear_octree[i]) ; >

{

/* Identify and process */ /* voxels at the desired */ /* elevation. */

> Program 4 .11: The Slicing A lgorithm

Figure 4.34: Search D irectio n s fo r a M odified N eighbour F in d in g A lgorithm

4.7. LIN EA R O C T R E E D ISPLA Y

4.7

133

Linear Octree Display

The linear octree display algorithm, used in A E G IS , was developed by Irene Gargantini (Gargantini et al., 1986) and implemented in a system called L inoct (Atkinson et al ., 1987). The algorithm is based on a back-to-front mechanism which utilises the spatial ordering of the linear octree to identify hidden surfaces. Visible octants are projected with a parallel projection and displayed using both depth shading and a basic reflection model. The algorithm proceeds by defining a direction of view using a 3D transformation, sorting the octal strings of the linear octree in a ‘back-to-front’ order and ‘painting’ the octants on to the screen. The octree universe is assumed to exist in a right handed world co-ordinate system, with axes {a : ,y ,z } . The dimension of this universe is 2 R x 2 R X 2 R . However, to ensure that the entire universe is visible from all angles, it is expanded to a maximum dimension of (Figure 4.35): (V

3)

2r

X

(\/3 )

2r

X

2r

This expanded universe is referred to as the view volume. The direction from the origin of the view volume to the viewer is given by a vector {x u, yv, zv}, called the view p lan e n o rm a l (V PN ). As the display screen is assumed to be normal to the V P N at all times, a second co-ordinate system, referred to as the view reference co -o rd in ate system (V R C ), is defined by axes { u ,v ,n } where N coincides with the V P N (Gargantini et al., 1986). Figure 4.36 illustrates the relation between these co-ordinate systems. To view an object it is projected onto the view plane using an ax o n o m etric orth o g rap h ic projec­ tion. The latter assumes that the direction of projection (view) is coincident with the V P N and that the view plane may be freely orientated about the principle axes. The view volume axes {x, y , z } can be mapped onto the V R C { u , v ,V P N } axes in two steps: firstly rotating the x and z axes about the y axis, such that the positive z axis coincides with the projection of the V P N on the x O z plane, and secondly rotating the y and z axes about the x axis such that the positive z axis coincides with the V P N . The x axis maps on to the u axis and the z axis maps on to the V P N (Gargantini et al., 1986).

Figure 4.35: D im en sio n o f the View Volume

C H A P T E R 4. A D A P T I V E SPATIAL SUBDIVISION IN AEGIS

134

Figure 4.36: T ra n sfo rm atio n o f the O ctree Universe in to the View Volume The rotations are performed about the origin of the view volume co-ordinate system which, conventionally, is located at (0,0,0). Such rotations position the objects of interest outside the view volume and, therefore, two translations are required to maintain a field of view. The complete transformation is given by a matrix called the v iew .m atrix (Gargantini et a l ., 1986):

v ie w jm a trix

-^origin — *centre * Ry ' Rx *^centre —► origin

sin 9

(

0

= > v ie w jm a trix —

—COS0 2

—(cos 0)(sin ) cos —(sin 9 ) (sin ) 2

(cos 9 ) (cos ) sin

Smile Life

When life gives you a hundred reasons to cry, show life that you have a thousand reasons to smile

Get in touch

© Copyright 2015 - 2024 PDFFOX.COM - All rights reserved.