Mesh generation using quadtrees Quadtree

a balanced leaf has @ 1 corner in side.

consider leaf of quadtree , corresponding cell



v


{\displaystyle v}

.



v


{\displaystyle v}

balanced (for mesh generation) if cell s sides intersected corner points of neighbouring cells @ once on each side. means quadtree levels of leaves adjacent



v


{\displaystyle v}

differ @ 1 level of



v


{\displaystyle v}

. when true leaves, whole quadtree balanced (for mesh generation).

consider cell



v


{\displaystyle v}

,



5
×
5


{\displaystyle 5\times 5}

neighbourhood of same-sized cells centred @



v


{\displaystyle v}

. call neighbourhood extended cluster. quadtree well-balanced if balanced, , every leaf



u


{\displaystyle u}

contains point of point set, extended cluster in quadtree , extended cluster contains no other point of point set.

creating mesh done follows:

we consider corner points of tree cells vertices in our triangulation. before transformation step have bunch of boxes points in of them. transformation step done in following manner: each point, warp closest corner of cell meet , triangulate resulting 4 quadrangles make nice triangles (the interested reader referred chapter 12 of har-peled more details on makes nice triangles).

the remaining squares triangulated according simple rules. each regular square (no points within , no corner points in sides), introduce diagonal. note due way in separated points well-balancing property, no square corner intersecting side 1 warped. such, can triangulate squares intersecting corners follows. if there 1 intersected side, square becomes 3 triangles adding long diagonals connecting intersection opposite corners. if there 4 intersected sides, split square in half adding edge between 2 of 4 intersections, , connect these 2 endpoints remaining 2 intersection points. other squares, introduce point in middle , connect 4 corners of square each intersection point.

at end of all, have nice triangulated mesh of our point set built quadtree.