Surface Reconstruction
Home	Algorithm	Gallery	Server	Download	Links

Algorithm

Starting from a seed facet, a piecewise linear surface is grown by adding Delaunay triangles one by one. The most plausible triangles are added in the first place, in a way that prevents the appearance of topological singularities. The output is thus guaranteed to be a piecewise linear orientable manifold, possibly with boundary.

You can find technical details in the technical report ECG-TR-124202-01 entitled "Greedy Delaunay Based Surface Reconstruction Algorithm.

Experimental Results

Results displayed in the tables below were obtained on a PC with an Intel Pentium i686 1GHz processor and 1Gb RAM. We implemented this algorithm using the CGAL library.

Surfaces without Boundary

For closed surfaces, the number of boundary edges indicates the topological quality of the reconstruction. Note that in this case, no user defined parameter is needed.

Data Delaunay Reconstruction t

Model points cells t₁ points triangles boundary t₂ t₃

Mechanic 12593 85158 0,99 12593 25194 0 1,03 0 2,02

blade 882954 6071275 103,76 878724 1757123 1005 105,28 20,38 229,42

bunny 35946 249345 2,75 35943 71882 0 3,19 0,01 5,95

cube 866 4172 2,78 861 1718 0 0,04 0,02 2,84

dragon 435545 314951 49,02 422441 844546 442 47,86 97,75 194,63

happy 542548 3864194 63,36 522701 1045009 567 70,02 182,27 315,65

knot108s 10000 93505 0,83 10000 20000 0 1,03 0,01 1,87

mechpart 4102 30638 0,38 4098 8204 0 0,33 0,03 0,74

papaine1 12577 92619 0,9 12562 25120 0 1,07 0,02 1,99

papaine2 18059 131943 1,39 18045 36086 0 1,54 0,02 2,95

hand 327323 2302290 38,57 327290 654596 0 33,25 0,56 72,38

holes3 3999 29352 0,25 3999 8006 0 0,33 0,01 0,59

horse 48485 342428 3,94 48473 96942 0 4,46 0,39 8,75

oilpmp 30933 200516 2,91 130919 61834 0 2,58 0,04 5,53

sphere 926 5070 0,52 926 1848 0 0,04 0 0,56

torus_random 499 3633 0,03 499 998 0 0,04 0 0,07

knuckle 6062 43401 1.22 5976 11990 4 0.64 0 1.86

Data	Delaunay	Reconstruction	t
Model	points	cells	t₁	points	triangles	boundary	t₂	t₃
Mechanic	12593	85158	0,99	12593	25194	0	1,03	0	2,02
blade	882954	6071275	103,76	878724	1757123	1005	105,28	20,38	229,42
bunny	35946	249345	2,75	35943	71882	0	3,19	0,01	5,95
cube	866	4172	2,78	861	1718	0	0,04	0,02	2,84
dragon	435545	314951	49,02	422441	844546	442	47,86	97,75	194,63
happy	542548	3864194	63,36	522701	1045009	567	70,02	182,27	315,65
knot108s	10000	93505	0,83	10000	20000	0	1,03	0,01	1,87
mechpart	4102	30638	0,38	4098	8204	0	0,33	0,03	0,74
papaine1	12577	92619	0,9	12562	25120	0	1,07	0,02	1,99
papaine2	18059	131943	1,39	18045	36086	0	1,54	0,02	2,95
hand	327323	2302290	38,57	327290	654596	0	33,25	0,56	72,38
holes3	3999	29352	0,25	3999	8006	0	0,33	0,01	0,59
horse	48485	342428	3,94	48473	96942	0	4,46	0,39	8,75
oilpmp	30933	200516	2,91	130919	61834	0	2,58	0,04	5,53
sphere	926	5070	0,52	926	1848	0	0,04	0	0,56
torus_random	499	3633	0,03	499	998	0	0,04	0	0,07
knuckle	6062	43401	1.22	5976	11990	4	0.64	0	1.86

t₁ = Delaunay, t₂ = main algorithm, t₃ = postprocessing.

Surfaces with Boundary

For surfaces with boundary, the parameter K has to be tuned by the user. Applying some flips to the output reconstruction should improve visual quality at low cost. When the post processing step is not needed, the total running time of the algorithm seems in practice to be less than twice the time spent computing the Delaunay triangulation. If the post processing step is required, running times can become much larger because removals in Delaunay triangulations are costly.

Data Delaunay Reconstruction t

Model points cells t₁ points triangles boundary t₂ t₃

Avant_Auto 59497 394366 5,46 59491 118232 748 5,27 0,25 10,98

Culbu 71150 483383 6,12 71150 142210 88 6,52 0,03 12,67

BootSki 33711 239977 2,94 33700 66005 1393 3,04 3,29 9,27

British_Museum 51095 340275 4,15 51053 101899 251 4,42 0,18 8,75

CarDoor 489205 3217628 56,86 488278 973402 3334 49,12 13,43 119,48

DryerBody 31013 192207 6,66 31010 61093 921 2,34 0,33 9,33

DryerHandle1 49786 319549 18,77 49786 98811 759 3,94 0,02 22,73

DryerHandle2 64464 408629 15,67 64464 128260 666 5,13 0,02 20,82

HairDryer 51563 321389 14,75 51563 10248 641 3,95 0,02 18,72

Robinet 13962 101468 1,17 13884 27309 455 1,4 0,17 2,74

Rth 13894 94824 1,07 13894 27557 231 1,16 0 2,23

Tomo 47861 330959 4,72 47839 92861 2883 15,99 0,12 20,83

Voiture 407577 2646522 46,29 403629 801332 7524 37,46 44,58 128,33

bear 29648 203529 3,64 29621 58553 687 2,4 0,11 6,15

cactus 3280 22908 2,69 3277 6532 20 0,24 0 2,93

cat10 10000 66700 0,69 10000 19908 90 0,82 0 1,51

ch1000 59104 383939 5,57 59104 117707 499 5,26 0,03 10,86

distcap 12745 86887 0,9 12744 25325 161 1,04 0 1,94

engine 11360 73253 1,02 11360 22360 356 0,98 0,01 2,01

hypersheet 6752 52366 0,6 6752 12575 935 0,61 0,01 1,22

club0h 15245 103129 1,17 15232 30438 24 1,30 0,06 2,53

foundry 4101 28111 0,26 4101 7958 242 0,34 0 0,6

mannequin 12772 86663 0,91 12768 25366 168 1,03 0,03 1,97

mmal25 25921 172441 2,89 25921 51201 639 2,98 0,02 5,89

mmma25 6561 43359 0,6 6561 12833 287 0,56 0 1,16

moeller 20020 137183 1,62 20020 39964 74 1,71 0,01 3,34

monkey2 10000 68462 2,98 10000 19611 387 0,84 3,82

nascar 20621 129788 1,58 20619 40725 515 1,65 0,01 2,88

seat 14812 96922 5,16 14812 29248 374 1,29 0 6,45

skidoored 37973 257065 3,08 37960 75389 531 3,33 0,05 6,46

Data	Delaunay	Reconstruction	t
Model	points	cells	t₁	points	triangles	boundary	t₂	t₃
Avant_Auto	59497	394366	5,46	59491	118232	748	5,27	0,25	10,98
Culbu	71150	483383	6,12	71150	142210	88	6,52	0,03	12,67
BootSki	33711	239977	2,94	33700	66005	1393	3,04	3,29	9,27
British_Museum	51095	340275	4,15	51053	101899	251	4,42	0,18	8,75
CarDoor	489205	3217628	56,86	488278	973402	3334	49,12	13,43	119,48
DryerBody	31013	192207	6,66	31010	61093	921	2,34	0,33	9,33
DryerHandle1	49786	319549	18,77	49786	98811	759	3,94	0,02	22,73
DryerHandle2	64464	408629	15,67	64464	128260	666	5,13	0,02	20,82
HairDryer	51563	321389	14,75	51563	10248	641	3,95	0,02	18,72
Robinet	13962	101468	1,17	13884	27309	455	1,4	0,17	2,74
Rth	13894	94824	1,07	13894	27557	231	1,16	0	2,23
Tomo	47861	330959	4,72	47839	92861	2883	15,99	0,12	20,83
Voiture	407577	2646522	46,29	403629	801332	7524	37,46	44,58	128,33
bear	29648	203529	3,64	29621	58553	687	2,4	0,11	6,15
cactus	3280	22908	2,69	3277	6532	20	0,24	0	2,93
cat10	10000	66700	0,69	10000	19908	90	0,82	0	1,51
ch1000	59104	383939	5,57	59104	117707	499	5,26	0,03	10,86
distcap	12745	86887	0,9	12744	25325	161	1,04	0	1,94
engine	11360	73253	1,02	11360	22360	356	0,98	0,01	2,01
hypersheet	6752	52366	0,6	6752	12575	935	0,61	0,01	1,22
club0h	15245	103129	1,17	15232	30438	24	1,30	0,06	2,53
foundry	4101	28111	0,26	4101	7958	242	0,34	0	0,6
mannequin	12772	86663	0,91	12768	25366	168	1,03	0,03	1,97
mmal25	25921	172441	2,89	25921	51201	639	2,98	0,02	5,89
mmma25	6561	43359	0,6	6561	12833	287	0,56	0	1,16
moeller	20020	137183	1,62	20020	39964	74	1,71	0,01	3,34
monkey2	10000	68462	2,98	10000	19611	387	0,84		3,82
nascar	20621	129788	1,58	20619	40725	515	1,65	0,01	2,88
seat	14812	96922	5,16	14812	29248	374	1,29	0	6,45
skidoored	37973	257065	3,08	37960	75389	531	3,33	0,05	6,46

t₁ = Delaunay, t₂ = main algorithm, t₃ = postprocessing.