SRT

1
00:00:00,000 --> 00:00:02,000
This is the video presentation on the 

2
00:00:02,000 --> 00:00:04,000
meshing techniques and algorithms 

3
00:00:04,000 --> 00:00:07,000
presented in the paper titled "Quadrilateral 

4
00:00:07,000 --> 00:00:09,000
Meshes with Bounded Minimum Angle",

5
00:00:09,000 --> 00:00:11,000
previously published in the 

6
00:00:11,000 --> 00:00:13,000
proceedings of International Meshing 

7
00:00:13,000 --> 00:00:15,000
Roundtable, in October 2008. 

8
00:00:19,000 --> 00:00:22,000
We present an algorithm that utilizes

9
00:00:22,000 --> 00:00:24,500
a quadtree data structure to construct 

10
00:00:24,500 --> 00:00:27,000
a strictly convex quadrilateral mesh for 

11
00:00:27,000 --> 00:00:29,000
a simple polygonal region in which 

12
00:00:29,000 --> 00:00:31,000
no newly created angle is smaller than 

13
00:00:31,000 --> 00:00:34,000
18.43 degrees. This is the first known 

14
00:00:34,000 --> 00:00:36,000
result on quadrilateral mesh generation 

15
00:00:36,000 --> 00:00:39,000
with a provable guarantee on the minimum angle.

16
00:00:41,000 --> 00:00:044,500
We construct a quadtree subdivision based 

17
00:00:44,500 --> 00:00:46,500
only on the vertices of the polygon, 

18
00:00:46,500 --> 00:00:50,000
ensuring certain separation and balancing conditions. 

19
00:00:50,000 --> 00:00:52,500
The end-result is such that a quadtree 

20
00:00:52,500 --> 00:00:56,000
cell contains at most a single input vertex, 

21
00:00:56,000 --> 00:00:58,000
and if containing such a vertex, it is 

22
00:00:58,000 --> 00:01:01,000
surrounded by 24 empty cells of the same size. 

23
00:01:01,000 --> 00:01:04,000
In addition, neighboring quadtree cells

24
00:01:04,000 --> 00:01:06,000
differ by at most one level.

25
00:01:07,500 --> 00:01:10,000
We then take the dual of the quadtree, 

26
00:01:10,000 --> 00:01:12,000
and place additional Steiner points

27
00:01:12,000 --> 00:01:14,500
in select quadtree cells by identifying 

28
00:01:14,500 --> 00:01:17,000
and applying one of the six templates

29
00:01:17,000 --> 00:01:19,000
which are based on quadrant layout.

30
00:01:19,000 --> 00:01:21,000 
Additional Steiner points are necessary to

31
00:01:21,000 --> 00:01:24,000
quadrangulate properly within the template. 

32
00:01:25,000 --> 00:01:28,000
They are denoted by empty circles in these illustrations.

28
00:01:28,000 --> 00:01:31,000
Recall that quadrangulation of a polygon 

29
00:01:31,000 --> 00:01:34,000
requires an even number of vertices on the boundary. 

30
00:01:34,000 --> 00:01:36,000
The open polygonal chains on the boundary 

31
00:01:36,000 --> 00:01:38,000
of the templates need an even number of 

32
00:01:38,000 --> 00:01:41,000
vertices to be stitched together with a neighboring chain.

33
00:01:41,000 --> 00:01:43,000 
This is the reason for introducing additional

34
00:01:43,000 --> 00:01:46,000
Steiner points on these chains.

35
00:01:47,000 --> 00:01:50,000
Our recursive algorithm applies the templates

36
00:01:50,000 --> 00:01:52,000
to all internal nodes of the quadtree, 

37
00:01:52,000 --> 00:01:54,000
starting at the deepest subdivision level, 

38
00:01:54,000 --> 00:01:56,000
where the node is quadrangulated exactly 

39
00:01:56,000 --> 00:01:58,000
as shown in the previous template 

40
00:01:58,000 --> 00:01:59,000
illustrations.

41
00:01:59,000 --> 00:02:01,000
At an arbitrary level of subdivision, 

42
00:02:01,000 --> 00:02:04,000
each non-leaf child is already internally

43
00:02:04,000 --> 00:02:06,000
quadrangulated and we simply stitch the 

44
00:02:06,000 --> 00:02:08,000
children together.

45
00:02:09,500 --> 00:02:11,000
Once the meshing is completed, we warp 

46
00:02:11,000 --> 00:02:14,000
certain mesh vertices onto the original

47
00:02:14,000 --> 00:02:17,000 
input vertices. Notice that the 24 empty

48
00:02:17,000 --> 00:02:19,000 
cells of the same size surrounding an

49
00:02:19,000 --> 00:02:22,000 
input vertex guarantees a grid-like mesh 

50
00:02:22,000 --> 00:02:24,000
with 90-degree angles that makes the 

51
00:02:24,000 --> 00:02:25,000
warping possible.

52
00:02:26,000 --> 00:02:28,500
This concludes our point set based meshing 

53
00:02:28,500 --> 00:02:31,500
algorithm and we achieve a minimum angle 

54
00:02:31,500 --> 00:02:36,000
guarantee of 26.57 degrees. 

55
00:02:37,000 --> 00:02:39,000
We now adapt this mesh to incorporate

56
00:02:39,000 --> 00:02:42,000 
polygonal edges. The adaptation requires

57
00:02:42,000 --> 00:02:44,500 
polygons with no acute angles. Thus we

58
00:02:44,500 --> 00:02:47,000 
first pre-process the input polygon to

59
00:02:47,000 --> 00:02:50,000 
cut off acute corners. We will reintroduce

60
00:02:50,000 --> 00:02:52,000 
and process the acute corners later. 

61
00:02:53,000 --> 00:02:55,000
We then apply the point set based meshing 

62
00:02:55,000 --> 00:02:58,000
algorithm. Notice that the cutting of the

63
00:02:58,000 --> 00:03:00,000 
acute corners introduces more vertices 

64
00:03:00,000 --> 00:03:03,000
and thus forces a finer subdivision.

65
00:03:07,000 --> 00:03:09,000
A key ingredient in the adaptation

66
00:03:09,000 --> 00:03:11,500 
is additional edge-enforced quadtree

67
00:03:11,500 --> 00:03:14,000
subdivisions to ensure proper separations

68
00:03:14,000 --> 00:03:16,000 
of the edges. We now switch to a more

69
00:03:16,000 --> 00:03:18,000 
complex model to illustrate this.

70
00:03:27,000 --> 00:03:29,000
A polygonal edge intersects a finite

71
00:03:29,000 --> 00:03:32,000 
set of quadrilaterals in the existing mesh.

72
00:03:32,000 --> 00:03:34,000 
We define the quadrangulation chain

73
00:03:34,000 --> 00:03:37,000 
associated with this edge as the sequence

74
00:03:37,000 --> 00:03:39,000 
of edges of these quads that lie strictly

75
00:03:39,000 --> 00:03:42,000 
to the interior of the polygon. The idea

76
00:03:42,000 --> 00:03:44,500 
is to remove the mesh elements that lie

77
00:03:44,500 --> 00:03:47,000 
outside of this chain, and then 

78
00:03:47,000 --> 00:03:49,000 
quadrangulate the region between the 

79
00:03:49,000 --> 00:03:52,000
quadrangulation chain and its associated edge. 

80
00:03:53,500 --> 00:03:56,000
We now identify this chain algorithmically.

81
00:03:56,000 --> 00:03:59,000 
For each edge, we identify a series of

82
00:03:59,000 --> 00:04:01,000 
quadtree cells whose centers lie 

83
00:04:01,000 --> 00:04:04,000 
immediately above the associated edge. 

84
00:04:04,000 --> 00:04:08,000 
All such centers are proven to be on the quadrangulation chain.

85
00:04:08,000 --> 00:04:10,500 
Moreover all such cell centers are edge or 

86
00:04:10,500 --> 00:04:13,500
corner neighbors in the quadtree and are

87
00:04:13,500 --> 00:04:15,400 
connected by subchains containing at most

88
00:04:15,500 --> 00:04:18,000 
4 mesh edges in limited variations.

89
00:04:19,000 --> 00:04:21,000
The quadrangulation chains for consecutive 

90
00:04:21,000 --> 00:04:23,000
edges are then connected at the vertex

91
00:04:23,000 --> 00:04:25,000 
regions in a straightforward way thanks to 

92
00:04:25,000 --> 00:04:27,500
the strictly grid-like geometry of those

93
00:04:27,500 --> 00:04:30,000 
regions. Note that these corner connections

94
00:04:30,000 --> 00:04:32,000
create a single complete chain.

95
00:04:33,000 --> 00:04:35,500
We then unzip the mesh by removing the 

96
00:04:35,500 --> 00:04:38,000
mesh elements that lie outside of this 

97
00:04:38,000 --> 00:04:39,000
completed chain. 

98
00:04:40,700 --> 00:04:42,500
The region between each quadrangulation 

99
00:04:42,500 --> 00:04:45,300
chain and its associated edge is then

100
00:04:45,300 --> 00:04:47,000
quadrangulated with a minimum angle

101
00:04:47,000 --> 00:04:50,500 
guarantee of 18.43 degrees. We first

102
00:04:50,500 --> 00:04:52,500
drop perpendicular projections from

102
00:04:52,500 --> 00:04:54,000 
every cell center to the edge.

103
00:04:54,500 --> 00:04:56,500 
We then quadrangulate the regions 

104
00:04:56,500 --> 00:04:58,500
between each pair of consecutive

105
00:04:58,500 --> 00:05:01,800 
projections via limited case analysis.

106
00:05:01,800 --> 00:05:03,500 
Finally the vertex regions are

107
00:05:03,500 --> 00:05:05,300 
quadrangulated with the desired

108
00:05:05,300 --> 00:05:07,000 
angle bound. 

109
00:05:13,000 --> 00:05:14,500 
We now show the execution of the 

110
00:05:14,500 --> 00:05:16,500
algorithm on two datasets that

111
00:05:16,500 --> 00:05:18,000 
contain holes.

112
00:05:34,500 --> 00:05:36,500 
All acute vertices are meshed as a

113
00:05:36,500 --> 00:05:38,500 
post-processing step with a minimum

114
00:05:38,500 --> 00:05:41,000 
angle of 22.5 degrees.