Curve and surface reconstruction: Algorithms with mathematical analysis

Tamal K. Dey0521863708, 9780521863704, 9780511261336

Many applications in science and engineering require a digital model of a real physical object. Advanced scanning technology has made it possible to scan such objects and generate point samples on their boundaries. This book shows how to compute a digital model from this point sample. After developing the basics of sampling theory and its connections to various geometric and topological properties, the author describes a suite of algorithms that have been designed for the reconstruction problem, including algorithms for surface reconstruction from dense samples, from samples that are not adequately dense and from noisy samples. Voronoi and Delaunay based techniques, implicit surface based methods and Morse theory based methods are covered. Scientists and engineers working in drug design, medical imaging, CAD, GIS, and many other areas will benefit from this first book on the subject.

---

Table of contents :
Half-title……Page 3
Series-title……Page 4
Title……Page 5
Copyright……Page 6
Dedication……Page 7
䌀漀渀琀攀渀琀猀……Page 9
倀爀攀昀愀挀攀……Page 13
1 Basics……Page 17
㄀⸀㄀ 匀栀愀瀀攀猀……Page 18
㄀⸀㄀⸀㄀ 匀瀀愀挀攀猀 愀渀搀 䴀愀瀀猀……Page 19
䠀漀洀漀琀漀瀀礀……Page 20
䤀猀漀琀漀瀀礀……Page 21
䈀漀甀渀搀愀爀礀……Page 22
㄀⸀㄀⸀㌀ 䌀漀洀瀀氀攀砀攀猀……Page 23
㄀⸀㈀ 䘀攀愀琀甀爀攀 匀椀稀攀 愀渀搀 匀愀洀瀀氀椀渀最……Page 24
㄀⸀㈀⸀㄀ 䴀攀搀椀愀氀 䄀砀椀猀……Page 26
1.2.2 Local Feature Size……Page 30
㄀⸀㈀⸀㌀ 匀愀洀瀀氀椀渀最……Page 32
Uniform Sampling……Page 33
㄀⸀㌀ 嘀漀爀漀渀漀椀 䐀椀愀最爀愀洀 愀渀搀 䐀攀氀愀甀渀愀礀 吀爀椀愀渀最甀氀愀琀椀漀渀……Page 34
Voronoi Diagrams……Page 35
䐀攀氀愀甀渀愀礀 吀爀椀愀渀最甀氀愀琀椀漀渀猀……Page 36
Restricted Voronoi Diagrams……Page 37
1.3.2 Three Dimensions……Page 38
㄀⸀㐀 一漀琀攀猀 愀渀搀 䔀砀攀爀挀椀猀攀猀……Page 39
䔀砀攀爀挀椀猀攀猀……Page 40
2 Curve Reconstruction……Page 42
2.1 Consequences of Epsilon-Sampling……Page 43
㈀⸀㈀⸀㄀ 䄀氀最漀爀椀琀栀洀……Page 46
㈀⸀㈀⸀㈀ 䌀漀爀爀攀挀琀渀攀猀猀……Page 48
㈀⸀㌀⸀㄀ 䄀氀最漀爀椀琀栀洀……Page 51
㈀⸀㌀⸀㈀ 䌀漀爀爀攀挀琀渀攀猀猀……Page 52
㈀⸀㐀 一漀琀攀猀 愀渀搀 䔀砀攀爀挀椀猀攀猀……Page 54
䔀砀攀爀挀椀猀攀猀……Page 55
3 Surface Samples……Page 57
㌀⸀㄀⸀㄀ 䄀瀀瀀爀漀砀椀洀愀琀椀漀渀 漀昀 一漀爀洀愀氀猀……Page 59
㌀⸀㄀⸀㈀ 一漀爀洀愀氀 嘀愀爀椀愀琀椀漀渀……Page 61
㌀⸀㄀⸀㌀ 䔀搀最攀 愀渀搀 吀爀椀愀渀最氀攀 一漀爀洀愀氀猀……Page 63
㌀⸀㈀⸀㄀ 吀漀瀀漀氀漀最椀挀愀氀 䈀愀氀氀 倀爀漀瀀攀爀琀礀……Page 66
㌀⸀㈀⸀㈀ 嘀漀爀漀渀漀椀 䘀愀挀攀猀……Page 69
䔀砀攀爀挀椀猀攀猀……Page 73
㐀⸀㄀⸀㄀ 倀漀氀攀猀 愀渀搀 䌀漀挀漀渀攀猀……Page 75
㐀⸀㄀⸀㈀ 䌀漀挀漀渀攀 吀爀椀愀渀最氀攀猀……Page 78
㐀⸀㄀⸀㌀ 倀爀甀渀椀渀最……Page 80
㐀⸀㄀⸀㐀 䴀愀渀椀昀漀氀搀 䔀砀琀爀愀挀琀椀漀渀……Page 82
㐀⸀㈀ 䜀攀漀洀攀琀爀椀挀 䜀甀愀爀愀渀琀攀攀猀……Page 86
㐀⸀㈀⸀㄀ 䄀搀搀椀琀椀漀渀愀氀 倀爀漀瀀攀爀琀椀攀猀……Page 88
4.3.1 The Map Nu……Page 89
㐀⸀㌀⸀㈀ 䠀漀洀攀漀洀漀爀瀀栀椀猀洀 倀爀漀漀昀……Page 91
㐀⸀㐀 一漀琀攀猀 愀渀搀 䔀砀攀爀挀椀猀攀猀……Page 92
䔀砀攀爀挀椀猀攀猀……Page 94
㔀⸀㄀ 匀愀洀瀀氀攀猀 愀渀搀 䈀漀甀渀搀愀爀椀攀猀……Page 96
㔀⸀㄀⸀㄀ 䈀漀甀渀搀愀爀礀 匀愀洀瀀氀攀 倀漀椀渀琀猀……Page 97
5.1.2 Flat Sample Points……Page 98
㔀⸀㈀ 䘀氀愀琀渀攀猀猀 䄀渀愀氀礀猀椀猀……Page 99
㔀⸀㌀ 䈀漀甀渀搀愀爀礀 䐀攀琀攀挀琀椀漀渀……Page 103
5.3.1 Justification……Page 104
㔀⸀㌀⸀㈀ 刀攀挀漀渀猀琀爀甀挀琀椀漀渀……Page 105
㔀⸀㐀 一漀琀攀猀 愀渀搀 䔀砀攀爀挀椀猀攀猀……Page 106
䔀砀攀爀挀椀猀攀猀……Page 107
㘀⸀㄀ 倀漀眀攀爀 䌀爀甀猀琀……Page 109
倀漀眀攀爀 䐀椀愀最爀愀洀猀……Page 110
䜀攀漀洀攀琀爀椀挀 倀爀漀砀椀洀椀琀礀……Page 113
一漀爀洀愀氀 倀爀漀砀椀洀椀琀礀……Page 114
㘀⸀㄀⸀㌀ 䠀漀洀攀漀洀漀爀瀀栀椀猀洀 愀渀搀 䤀猀漀琀漀瀀礀……Page 115
㘀⸀㄀⸀㐀 䄀氀最漀爀椀琀栀洀……Page 117
㘀⸀㈀ 吀椀最栀琀 䌀漀挀漀渀攀……Page 120
㘀⸀㈀⸀㄀ 䴀愀爀欀椀渀最……Page 121
㘀⸀㈀⸀㈀ 倀攀攀氀椀渀最……Page 123
㘀⸀㌀ 䔀砀瀀攀爀椀洀攀渀琀愀氀 刀攀猀甀氀琀猀……Page 125
䔀砀攀爀挀椀猀攀猀……Page 127
㜀⸀㄀ 一漀椀猀攀 䴀漀搀攀氀……Page 129
㜀⸀㈀ 䔀洀瀀琀礀 䈀愀氀氀猀……Page 131
㜀⸀㌀⸀㄀ 䄀渀愀氀礀猀椀猀……Page 135
㜀⸀㌀⸀㈀ 䄀氀最漀爀椀琀栀洀……Page 138
㜀⸀㐀 䘀攀愀琀甀爀攀 䄀瀀瀀爀漀砀椀洀愀琀椀漀渀……Page 140
㜀⸀㐀⸀㄀ 䄀渀愀氀礀猀椀猀……Page 142
㜀⸀㐀⸀㈀ 䄀氀最漀爀椀琀栀洀……Page 146
㜀⸀㔀 一漀琀攀猀 愀渀搀 䔀砀攀爀挀椀猀攀猀……Page 147
䔀砀攀爀挀椀猀攀猀……Page 148
㠀⸀㄀ 倀爀攀氀椀洀椀渀愀爀椀攀猀……Page 149
㠀⸀㈀ 唀渀椀漀渀 漀昀 䈀愀氀氀猀……Page 152
㠀⸀㌀ 倀爀漀砀椀洀椀琀礀……Page 158
㠀⸀㐀 吀漀瀀漀氀漀最椀挀愀氀 䔀焀甀椀瘀愀氀攀渀挀攀……Page 160
㠀⸀㐀⸀㄀ 䰀愀戀攀氀椀渀最……Page 161
㠀⸀㐀⸀㈀ 䄀氀最漀爀椀琀栀洀……Page 163
㠀⸀㔀 一漀琀攀猀 愀渀搀 䔀砀攀爀挀椀猀攀猀……Page 165
䔀砀攀爀挀椀猀攀猀……Page 166
㤀⸀㄀ 䜀攀渀攀爀椀挀 䄀瀀瀀爀漀愀挀栀……Page 168
㤀⸀㄀⸀㄀ 䤀洀瀀氀椀挀椀琀 䘀甀渀挀琀椀漀渀 倀爀漀瀀攀爀琀椀攀猀……Page 169
㤀⸀㄀⸀㈀ 䠀漀洀攀漀洀漀爀瀀栀椀猀洀 倀爀漀漀昀……Page 170
㤀⸀㈀ 䴀䰀匀 匀甀爀昀愀挀攀猀……Page 171
圀攀椀最栀琀椀渀最 䘀甀渀挀琀椀漀渀猀……Page 172
䄀䴀䰀匀 䘀甀渀挀琀椀漀渀……Page 174
㤀⸀㌀ 匀愀洀瀀氀椀渀最 䄀猀猀甀洀瀀琀椀漀渀猀 愀渀搀 䌀漀渀猀攀焀甀攀渀挀攀猀……Page 175
9.3.1 Influence of Samples……Page 178
㤀⸀㐀 匀甀爀昀愀挀攀 倀爀漀瀀攀爀琀椀攀猀……Page 182
㤀⸀㐀⸀㄀ 䠀愀甀猀搀漀爀昀昀 倀爀漀瀀攀爀琀礀……Page 183
㤀⸀㐀⸀㈀ 䜀爀愀搀椀攀渀琀 倀爀漀瀀攀爀琀礀……Page 186
㤀⸀㔀⸀㄀ 一漀爀洀愀氀 愀渀搀 䘀攀愀琀甀爀攀 䄀瀀瀀爀漀砀椀洀愀琀椀漀渀……Page 188
㤀⸀㔀⸀㈀ 倀爀漀樀攀挀琀椀漀渀……Page 189
㤀⸀㘀⸀㄀ 倀爀漀樀攀挀琀椀漀渀 䴀䰀匀……Page 191
㤀⸀㘀⸀㌀ 䌀漀洀瀀甀琀愀琀椀漀渀愀氀 䤀猀猀甀攀猀……Page 192
䄀搀瘀愀渀琀愀最攀猀 漀昀 一攀眀琀漀渀 倀爀漀樀攀挀琀椀漀渀猀……Page 193
Zero-Level Sets……Page 194
㤀⸀㜀 嘀漀爀漀渀漀椀ⴀ䈀愀猀攀搀 䤀洀瀀氀椀挀椀琀 匀甀爀昀愀挀攀……Page 195
㤀⸀㠀 一漀琀攀猀 愀渀搀 䔀砀攀爀挀椀猀攀猀……Page 196
䔀砀攀爀挀椀猀攀猀……Page 197
㄀　⸀㄀ 䴀漀爀猀攀 䘀甀渀挀琀椀漀渀猀 愀渀搀 䘀氀漀眀猀……Page 198
㄀　⸀㈀⸀㄀ 嘀攀挀琀漀爀 䘀椀攀氀搀……Page 201
㄀　⸀㈀⸀㈀ 䐀椀猀挀爀攀琀攀 䘀氀漀眀……Page 203
㄀　⸀㈀⸀㌀ 刀攀氀愀琀椀漀渀猀 琀漀 嘀漀爀漀渀漀椀⼀䐀攀氀愀甀渀愀礀 䐀椀愀最爀愀洀猀……Page 206
䤀渀搀攀砀 ㌀ 䌀爀椀琀椀挀愀氀 倀漀椀渀琀猀……Page 207
㄀　⸀㌀⸀㄀ 䘀氀漀眀 䌀漀洀瀀氀攀砀 䌀漀渀猀琀爀甀挀琀椀漀渀……Page 208
㄀　⸀㌀⸀㈀ 䴀攀爀最椀渀最……Page 209
㄀　⸀㌀⸀㌀ 䌀爀椀琀椀挀愀氀 倀漀椀渀琀 匀攀瀀愀爀愀琀椀漀渀……Page 210
㄀　⸀㐀⸀㄀ 䐀椀猀琀愀渀挀攀 昀爀漀洀 䐀攀氀愀甀渀愀礀 䈀愀氀氀猀……Page 212
Flow Relation……Page 214
Centered Simplices……Page 215
Equivocal Simplices……Page 216
10.4.3 Reconstruction……Page 217
10.4.4 Algorithm……Page 218
䔀砀攀爀挀椀猀攀猀……Page 221
䈀椀戀氀椀漀最爀愀瀀栀礀……Page 223
䤀渀搀攀砀……Page 229