Next: Surface Discretization Up: Mesh Generation Previous: Vertex Discretization


Curve Discretization

To estimate the number of segments to be used to discretize a curve, a binary tree is built in the parametric space of the curve. The depth of the tree is controlled by the ratio of the size (length) of the tree cell in the real space and the mesh size extracted from the octree. This tree structure is then used to evaluate the mass curve (Fig. 2.13) by integrating the required mesh density

(2.58)


where and represent the mesh density and mesh size (extracted from the octree) along the curve, denotes length of curve arc, and is a curve parameter in the range from to . Note that the actual integration is done numerically over individual cells of the binary tree. The number of segments is chosen as

(2.59)


where brackets stand for the integer part of the enclosed quantity and the coefficient is used to round to the nearest integer. The discretization of the curve is then obtained by splitting the mass curve to pieces where positions of the nodes to be generated on the model curve (Fig. 2.13) are defined by a parameter which is implicitly given by

(2.60)


The actual calculation of is done by locating the appropriate cell in the binary tree (that stores the mass curve) and performing linear interpolation in that cell. Each created segment is connected to its end nodes and each newly created (internal) node is registered into the octree. The new segments and nodes are also classified to the curve being discretized. Since the octree data structure is employed for the mesh size control, a gradual and very smooth discretization is achieved which does not need further optimization.

Only top parent model curves (curves which are not fixed to any other curve) are subjected to the discretization. Since there may be vertices fixed to the curve, it is necessary to accommodate these vertices into the discretization while preserving their position. This is done by discretizing the curve piecewise (starting from the beginning of the curve), each time using a part of the curve between two successive vertices. This is reflected by changing the limits of integration in Eqs (2.58), (2.59), and (2.60)

(2.61)


(2.62)


(2.63)


where and denote the curve parameters of two successive (previous and next) vertices defining the appropriate part of the curve. The complete curve discretization is then obtained by collecting the segmentations of its individual parts.



Next: Surface Discretization Up: Mesh Generation Previous: Vertex Discretization

Daniel Rypl
2005-12-07