Study on three-dimensional freehand stroke creation

Abstract

The automotive frames that can be created consciously with three-dimensional freehand strokes are quite important and useful in the early stage of automotive styling. However, all the strokes are drawn on the screen in two-dimensional. This study focuses on the creation of three-dimensional freehand strokes by applying the interpolation algorithm in two orthogonal planes, the projection algorithm and the resultant matrix algorithm. The fitting algorithms of strokes have been developed as the bridges between the traditional two-dimensional sketching and three-dimensional digital modeling. The stylists could use the digital tablet and pen to sketch the frames or outlines of a vehicle in three-dimensional space and then those could be used for establishing the automotive surfaces in any engineering software.

Introduction

Freehand sketching used by automotive stylists is a traditional way to express the ideas in the creative design, especially in the early stage of conceptual design. The freehand strokes in raster can be then combined into a vector stroke in the early researches by Li et al.^1–4 The curves, however, are still flat. How to obtain a spatial curve by freehand sketching becomes a key in the application of automotive styling from two-dimensional (2D) to three-dimensional (3D). Reversely, the key of 3D stroke fitting is how to reduce the dimension from 3D to 2D in some ways.

There are some sketching systems developed, such as the early touching system, Sutherland’s ⁵ SketchPad, the later optical input system, Grossman et al.’s ⁶ Shape Tape, digital tape drawing system,^7,8 and Gesture 3D ⁹ use liquid crystal display (LCD) digital pen as input. The systems above are still in 2D. Teddy, ¹⁰ Digital Clay, ¹¹ and EverybodyLovesSketch^12,13 offer the novel drawing environments based on the natural, seamless mapping of 2D to 3D. EverybodyLovesSketch system also gives some gesture commands during sketching.

There are some ways to get the spatial strokes, such as the intersection method of quadric surfaces and geometric method. Liu ¹⁴ have investigated the intersection method of free-form surface based on convex hull. Xue-yi Li et al. ¹⁵ have dealt with free-form surface based on curve projection. Lane and Riesenfeld’s ¹⁶ study have referred piecewise polynomial surfaces. Using the intersection of two surfaces to create 3D stroke is developed in AutoSketch 2010—a freehand sketching system prototyped by Li et al. ⁴ research group in Jilin University, China (as shown in Figure 1). However, it is difficult to carry out on the local modification once the intersecting line is obtained.

Figure 1.

Create a spatial curve in AutoSketch system: (a) select two surfaces, (b) intersecting curve, and (c) only the curve left.

Three methods will be discussed here. The main idea is to create a spatial stroke based on interpolation, projection, and intersection. The algorithms have been tested in AutoSketch. The examples show that sketching in 3D is feasible.

Preprocessing of strokes

Determine fitting interval

In order to avoid an ambiguity in fitting, the interval of fitting must be limited according to the original stroke and the modifying stroke. The straight line l is the intersecting line of the plane M containing the original stroke and the screen plane N (as shown in Figure 2). The vector $\hat{\mu }$ is the normal of plane M, and $\hat{\nu }$ is the normal of plane N. The normal vectors are perpendicular to each other. So, the points on the straight line l can be expressed as follows

$$l=a\hat{\mu }+b\hat{\nu }$$

(1)

Figure 2.

Normal of planes M and N.

Because the points on the straight line l are located in the two planes at the same time, the coefficients are

$$\{\begin{array}{c}\multicolumn{1}{c}{a=\frac{N\hat{\mu }·\hat{\nu }-M\Vert \hat{\nu }{\Vert }^2}{{(\hat{\mu }·\hat{\nu })}^2-\Vert \hat{\mu }{\Vert }^2\Vert \hat{\nu }{\Vert }^2}}\\ \multicolumn{1}{c}{b=\frac{M\hat{\mu }·\hat{\nu }-N\Vert \hat{\mu }{\Vert }^2}{{(\hat{\mu }·\hat{\nu })}^2-\Vert \hat{\mu }{\Vert }^2\Vert \hat{\nu }{\Vert }^2}}\end{array}$$

(2)

Assume that the first and the last points of the original stroke are $p_0$ and $p_{n-1}$ , respectively, where n is the total number of points on the stroke. Using the coordinate values of $p_0$ and $p_{n-1}$ in equation (1), the points $r_0$ and $r_{n-1}$ , with the shortest distance from $p_0$ and $p_{n-1}$ to the straight line l, respectively, can be calculated using the Euclidean distance measurement method.

The fitting interval of modifying stroke between $q_0$ and $q_{n-1}$ can be determined by moving the points $r_0$ and $r_{n-1}$ , along the normal vector $\hat{\mu }$ , respectively. In Figure 3, the shaded area between the dotted lines is the fitting interval of modifying stroke.

Figure 3.

Fitting interval of modifying stroke.

Fitting judgment

While sketching the modifying stroke Q on the screen plane N, it is necessary to judge whether the two ends of Q are located within the fitting interval or not. If so, the modification will be continuous until the two ends get out of the interval. The modification of stroke is completed and then it could go to the next step. If the two ends do not exceed the boundaries, the modifying stroke does not meet the fitting demand and needs to be extended between the two ends in both the directions. The sections outside of fitting interval are ignored (as shown in Figure 4).

Figure 4.

Procedure of interval locking: (a) determine the interval boundaries, (b) extend Q stroke in the right, and (c) extend Q in the left.

Stroke fitting in two orthogonal planes

Interpolated point

For anyone point $p_i$ from the original stroke, the point $r_i$ with the shortest distance from $p_i$ to the straight line l, is easy to be obtained. However, the point $q_i$ on the modifying stroke with the shortest distance from point $r_i$ needs to be calculated by interpolation (as shown in Figure 5).

Figure 5.

Calculation of interpolated point.

Offset and offset point

Assume that the original stroke is located in the xz plane, for example, and the normal of plane is along the y-axis. The coordinate of $p_i$ is $(x_i,y_i,z_i)$ . Similarly, the modifying stroke is located in the xy plane, and the coordinates of $q_2$ and $r_2$ are $(q_x,q_y,q_z)$ and $(r_x,r_y,r_z)$ , respectively. Therefore, the offset of $p_i$ in the y-axis is

$${\Delta }_i=\sqrt{{(q_x-r_x)}^2+{(q_y-r_y)}^2+{(q_z-r_z)}^2}$$

(3)

The coordinate of offset point $p{\prime }_i$ is $(x_i,y_i+{\Delta }_i,z_i)$ , and $p{\prime }_2$ is marked as red in Figure 6. Similarly, the coordinate of offset point $p{\prime }_2$ could be $(x_2+{\Delta }_2,y_2,z_2)$ if the original stroke is located in the plane yz and the modifying stroke in the plane xy or xz or could be $(x_2,y_2,z_2+{\Delta }_2)$ if the original stroke is located in the plane xy and the modifying stroke in the plane yz or xz. All of the offset points are kept in an array $Q\prime [p{\prime }_i]$ .

Figure 6.

Offset point.

Creation of spatial stroke

The spatial stroke can be created using the data in the array $Q\prime [p{\prime }_i]$ and the function of B-spline stroke in combination with AutoSketch. There are four steps as follows:

• First, two strokes are selected from the stack of stroke set, which are marked as highlight for 3D stroke fitting;

• Second, the location relationship of two strokes is judged to determine whether the two planes are orthogonal ones or not. If so, 3D stroke fitting is processed. Otherwise, the algorithm is stopped;

• Third, the lengths of two strokes are calculated, and the interval is determined and then the interpolating points and offset points are calculated;

• Finally, if 3D fitting is successful, all of the offset points are used to draw a B-spline stroke (as shown in Figure 7).

Figure 7.

3D stroke after fitting.

Test of the fitting algorithm

Here gives an example to demonstrate the 3D stroke fitting in two orthogonal planes (as shown in Figure 8). Some strokes are sketched at first on the screen plane N and then they are combined together as the original stroke (as shown in Figure 8(a) and (b)). The screen plane N is rotated and overlapped with the plane M, so that the original stroke is located in the plane M. Some new strokes are sketched again in the screen plane N (as shown in Figure 8(c)) and then they will be joined together as the modifying stroke. The modifying stroke in the plane N and the original stroke in the plane M are used to create a 3D stroke (as shown in Figure 8(d)). If changing the modifying stroke further by drawing some new strokes in the plane N (as shown in Figure 8(e)), the final 3D stroke will be improved at the same time (as shown in Figure 8(a) and (f)). The algorithm works well when strokes are simple and not closed. But the ambiguous results will occur sometimes for the closed strokes. Therefore, the projective algorithm has been applied to deal with the case. Only the parallel projection is taken into account in the stroke fitting.

Figure 8.

Offset point: (a) sketching strokes, (b) stroke after combination, (c) switch the working plane, (d) 3D stroke fitting, (e) modify further, and (f) new 3D stroke.

Stroke fitting based on projection

Stroke based on orthographic projection

The relationship of the stroke and the projective plane is orthogonal (as shown in Figure 9(a)). Assume that the stroke P is a set of points $P=\{p_0,p_1,\dots ,p_n\}$ , in which the coordinate of any point is $p_i(x_i,y_i,z_i)$ . The plane of $\hat{\mu }\mathrm{Qt}$ and the plane M is orthogonal, where the vector $\hat{\mu }$ is the normal of the plane M, the point Q is the cross point of the stroke P and the plane M, and the point $t_i(x_{\mathrm{ti}},y_{\mathrm{ti}},z_{\mathrm{ti}})$ is the projective point of $p_i(x_i,y_i,z_i)$ along the vector $\hat{\mu }$ . Therefore, the projective stroke T is the projection of the stroke P. Assume that three points are $A(x_1,y_1,z_1)$ , $B(x_2,y_2,z_2)$ , and $C(x_3,y_3,z_3)$ on the plane M, respectively. The vectors are as follows

$$\{\begin{array}{c}\hfill \overline{p_i{t}_i}=(x_{\mathrm{ti}}-x_i,y_{\mathrm{ti}}-y_i,z_{\mathrm{ti}}-z_i)\hfill \\ \multicolumn{1}{c}{\overline{\mathrm{AB}}=(x_2-x_1,y_2-y_1,z_2-z_1)}\\ \multicolumn{1}{c}{\overline{\mathrm{AC}}=(x_3-x_1,y_3-y_1,z_3-z_1)}\end{array}$$

(4)

Figure 9.

Stroke fitting based on the projection: (a) orthographic projection and (b) oblique projection.

According to the relationship of orthogonal projection, there are $\overline{p_i{t}_i}\perp \overline{\mathrm{AB}}$ and $\overline{p_i{t}_i}\perp \overline{\mathrm{AC}}$ , so that

$$\{\begin{array}{c}\hfill {(x_{\mathrm{ti}}-x)}_i(x_2-x_1)+(y_{\mathrm{ti}}-y_i)(y_2-y_1)+(z_{\mathrm{ti}}-z_i)(z_2-z_1)=0\hfill \\ \multicolumn{1}{c}{(x_{\mathrm{ti}}-x_i)(x_3-x_1)+(y_{\mathrm{ti}}-y_i)(y_3-y_1)+(z_{\mathrm{ti}}-z_i)(z_3-z_1)=0}\end{array}$$

(5)

For a given equation $A_{1}x+B_{1}y+C_{1}z+1=0$ of the plane M, there are

$$\left[\begin{array}{ccc}\hfill x_1\hfill & \hfill y_1\hfill & \hfill z_1\hfill \\ \multicolumn{1}{c}{x_2}& \hfill y_2\hfill & \hfill z_2\hfill \\ \multicolumn{1}{c}{x_3}& \hfill y_3\hfill & \hfill z_3\hfill \end{array}\right]\left[\begin{array}{c}\hfill A_1\hfill \\ \multicolumn{1}{c}{B_1}\\ \multicolumn{1}{c}{C_1}\end{array}\right]+\left[\begin{array}{c}\hfill 1\hfill \\ \multicolumn{1}{c}{1}\\ \multicolumn{1}{c}{1}\end{array}\right]=0$$

(6)

Therefore, the coefficients are

$$\left[\begin{array}{c}\hfill A_1\hfill \\ \multicolumn{1}{c}{B_1}\\ \multicolumn{1}{c}{C_1}\end{array}\right]=-{\left[\begin{array}{ccc}\hfill x_1\hfill & \hfill y_1\hfill & \hfill z_1\hfill \\ \multicolumn{1}{c}{x_2}& \hfill y_2\hfill & \hfill z_2\hfill \\ \multicolumn{1}{c}{x_3}& \hfill y_3\hfill & \hfill z_3\hfill \end{array}\right]}^{-1}\left[\begin{array}{c}\hfill 1\hfill \\ \multicolumn{1}{c}{1}\\ \multicolumn{1}{c}{1}\end{array}\right]$$

(7)

The point $t_i(x_{\mathrm{ti}},y_{\mathrm{ti}},z_{\mathrm{ti}})$ is also on the plane M, that is, $A_1{x}_{\mathrm{ti}}+B_1{y}_{\mathrm{ti}}+C_1{z}_{\mathrm{ti}}+1=0$ . It can be solved as follows

$$\left[\begin{array}{c}\hfill x_{\mathrm{ti}}\hfill \\ \multicolumn{1}{c}{y_{\mathrm{ti}}}\\ \multicolumn{1}{c}{z_{\mathrm{ti}}}\end{array}\right]=-{\left[\begin{array}{ccc}\hfill x_2-x_1\hfill & \hfill y_2-y_1\hfill & \hfill z_2-z_1\hfill \\ \multicolumn{1}{c}{x_3-x_1}& \hfill y_3-y_1\hfill & \hfill z_3-z_1\hfill \\ \multicolumn{1}{c}{A_1}& \hfill B_1\hfill & \hfill C_1\hfill \end{array}\right]}^{-1}\left[\begin{array}{c}\hfill E_1\hfill \\ \multicolumn{1}{c}{E_2}\\ \multicolumn{1}{c}{E_3}\end{array}\right]$$

(8)

where

$$\left[\begin{array}{c}\hfill E_1\hfill \\ \multicolumn{1}{c}{E_2}\\ \multicolumn{1}{c}{E_3}\end{array}\right]=\left[\begin{array}{c}\hfill x_i(x_2-x_1)+y_i(y_2-y_1)+z_i(z_2-z_1)\hfill \\ \multicolumn{1}{c}{x_i(x_3-x_1)+y_i(y_3-y_1)+z_i(z_3-z_1)}\\ \multicolumn{1}{c}{-1}\end{array}\right]$$

Stroke based on oblique projection

It is a kind of parallel projection, but the projection plane is not perpendicular to the projective ray. Orthographic projection can be interpreted as a kind of oblique projection along the normal. Similarly, its projection plane M is defined by Q and $\hat{\mu }$ . The projective direction is $\hat{\omega }$ (as shown in Figure 9(b)). Using the addition and subtraction of vectors, the point can be obtained as follows

$$\{\begin{array}{c}\hfill P=S+\hat{\omega }\hfill \\ \multicolumn{1}{c}{P=\alpha S+\hat{\mu }}\\ \multicolumn{1}{c}{\alpha S=S+\hat{\nu }}\\ \multicolumn{1}{c}{\hat{\omega }=\hat{\mu }+\hat{\nu }}\end{array}$$

(9)

The projective stroke S in parametric pattern is $S=S(t-\hat{\mu }-\hat{\nu })$ if the mapping relationship between P and S is $P=S+\hat{\mu }+\hat{\nu }$ .

The relationship between the freehand sketching plane and the projective stroke plane is restricted by orthographic projection. If sketching in one plane in the world coordinate system, the projection of the stroke is done only along its normal direction. However, oblique projection is relatively flexible and the stroke projection can be done by the vector transformation on any projection plane.

Lofting

It is a kind of method of surface construction based on the projection, in which the surface is modified by a spline. ¹⁷ The stroke is drawn in a plane and then modified by a spline to form a spatial stroke. Here, the screen plane is considered as the projective plane M, and the projective stroke as a spline for lofting to create surfaces (yellow ones as shown in Figure 9(a) and (b)). The procedure of surface construction is as follows:

• First, it needs to find out a sectional stroke, which is a planar and defined under the screen coordinate system. The values of vertices can be calculated through a set of points obtained by the Newton method in the orthographic or oblique projective stroke and then the control vertices will be calculated by the reverse mapping;

• Second, it is to find out a spline, which is planar or spatial. Here, the projective direction should be determined, and the end vertex is considered as the point, the target point, transformed from the screen plane to space. Obviously, the target point is located within the projection plane but not necessarily on the sectional stroke. The spline reflects the shape of the vertical distribution of the loft surface, so that the node vector of the spline coincides with the one on the surface, in the longitudinal direction;

• Third, the sectional stroke is translated to space until the origin and the target points are overlapped. In orthographic projection, the sectional stroke has been located within the normal plane because the spline is the normal vector of the projective plane, that is, the screen plane. For oblique projection, the sectional stroke should be rotated to the normal plane at the target point of the spline. According to the geometrical invariability, the transformation is conducted only for the B-spline control points of sectional stroke;

• Finally, the lofting surface is created according to those B-spline control points after the reverse mapping.

Create 3D stroke

A 3D stroke will be created to realize the fitting of 3D stroke through the projection of an original stroke on the lofting surface, which is lofted by a sectional stroke along a spline. The fitting process is understood to find the interpolation points ${\tau }_i$ closest to the data points $p_i(x_i,y_i,z_i)$ of the original stroke on the lofting surface. ¹⁸

A surface $S(u,v)$ and the vector from the surface to anyone point p can be expressed as a parametric function

$$\tau (u,v)=S(u,v)-p$$

(10)

and it meets the condition: the straight line $S(u,v)-p$ and the tangent plane of the surface in the point is perpendicular, that is, the line must be perpendicular to the partial derivatives $S_u(u,v)$ and $S_v(u,v)$ in each direction as follows

$$\{\begin{array}{c}\hfill f(u,v)=\tau (u,v)·S_u(u,v)=0\hfill \\ \multicolumn{1}{c}{g(u,v)=\tau (u,v)·S_v(u,v)=0}\end{array}$$

(11)

The closest points are available by solving the equations. Similar to the issue encountered with the orthographic projection, the Newton iterative method is applied. Through the evaluation of distributed point on the surface, the parameter $(u_0,v_0)$ closest to the evaluated point is considered as the initial value of Newton iterative method. Suppose that

$${\sigma }_i=\left[\begin{array}{c}\hfill {\delta }_u\hfill \\ \multicolumn{1}{c}{{\delta }_v}\end{array}\right]=\left[\begin{array}{c}\hfill u_{i+1}-u_i\hfill \\ \multicolumn{1}{c}{v_{i+1}-v_i}\end{array}\right]$$

(12)

$${\varsigma }_i=\left[\begin{array}{cc}\hfill f_u(u_i,v_i)\hfill & \hfill f_v(u_i,v_i)\hfill \\ \multicolumn{1}{c}{g_u(u_i,v_i)}& \hfill g_v(u_i,v_i)\hfill \end{array}\right]$$

(13)

where

$$\{\begin{array}{c}\hfill f_u(u_i,v_i)=\Vert S_u(u_i,v_i){\Vert }^2+\tau (u_i,v_i)·S_{\mathrm{uu}}(u_i,v_i)\hfill \\ \multicolumn{1}{c}{f_v(u_i,v_i)=S_u(u_i,v_i)·S_v(u_i,v_i)+\tau (u_i,v_i)·S_{\mathrm{uv}}(u_i,v_i)}\\ \multicolumn{1}{c}{g_u(u_i,v_i)=S_u(u_i,v_i)·S_v(u_i,v_i)+\tau (u_i,v_i)·S_{\mathrm{vu}}(u_i,v_i)}\\ \multicolumn{1}{c}{g_v(u_i,v_i)=\Vert S_v(u_i,v_i){\Vert }^2+\tau (u_i,v_i)·S_{\mathrm{vv}}(u_i,v_i)}\end{array}$$

$$k_i=-\left[\begin{array}{c}\hfill f(u_i,v_i)\hfill \\ \multicolumn{1}{c}{g(u_i,v_i)}\end{array}\right]$$

(14)

In the ith step of Newton iteration, the matrix equation of ${\sigma }_i$ is solved, ${\varsigma }_i{\sigma }_i=k_i$ , and the parameters are calculated as follows

$$\{\begin{array}{c}\hfill u_{i+1}={\delta }_u+u_i\hfill \\ \multicolumn{1}{c}{v_{i+1}={\delta }_v+v_i}\end{array}$$

(15)

Similar to the discussion in section “Stroke based on orthographic projection,” the checking conditions are stated as follows:

• The overlapped point is checked according to $\Vert S(u_i,v_i)-P\Vert \le {\epsilon }_1$ ;

• The zero cosine is checked to make it perpendicular between $S(u_i,v_i)-P$ and $S_u(u_i,v_i)$ , and between $S(u_i,v_i)-P$ and $S_v(u_i,v_i)$ , that is

  $$\begin{array}{c}\frac{\Vert S_u(u_i,v_i)·(S(u_i,v_i)-P)\Vert }{\Vert S_u(u_i,v_i)\Vert \Vert S(u_i,v_i)-P\Vert }\le {\epsilon }_2\hfill \\ \frac{\Vert S_v(u_i,v_i)·(S(u_i,v_i)-P)\Vert }{\Vert S_v(u_i,v_i)\Vert \Vert S(u_i,v_i)-P\Vert }\le {\epsilon }_2\hfill \end{array}$$

  (16)

If either of these two conditions is not met, then the iteration is continued, and two additional conditions are checked as follows: whether the parameters are located between the domains $a\le u_i\le b$ and $c\le v_i\le d$ or not and whether there is a significant change in the parameter or not as follows

$$\Vert (u_{i+1}-u_i{S}_u(u_i,v_i))+(v_{i+1}-v_i{S}_v(u_i,v_i))\Vert \le {\epsilon }_2$$

(17)

If this condition is met, then the iteration is over. The current parameter ${\tau }_i$ is the best of the root. The 3D stroke will be created after the B-spline fitting.

Examples of projective fitting

Here are some examples of 3D stroke fitting based on the projection realized in AutoSketch. The first example is to sketch a line (after the stroke standardization of stroke) on the screen plane N (as shown in Figure 10(a)) and switch it into the plane M, which is perpendicular to the screen plane N. The projection of the line on the screen plane N is still a straight line (as shown in Figure 10(b)). It will be modified by sketching some strokes to form a new modifying stroke, which is to change reversely the shape of the line. Therefore, the line becomes a stroke, which is still a planar one and is located in the plane P (as shown in Figure 10(c)).

Figure 10.

Projective fitting of a line: (a) original stroke, (b) projection of line, and (c) 3D stroke created.

The next two examples show that the closed stroke fitting in 3D. A closed triangle is drawn by sketching three strokes (after the geometric standardization of stroke) on the screen plane N (as shown in Figure 11(a)). It is switched into the plane M, and its projective line on the screen plane N is still a straight line (as shown in Figure 11(b)). Modifying the projective line by sketching some new strokes can form a new modifying stroke (as shown in Figure 11(c)) and then the planar triangle is bent into the spatial triangle. Similarly, a closed circle can be obtained by sketching one or some strokes on the screen plane N (as shown in Figure 12(a)). The screen plane N is then flipped into the plane M in a different way (as shown in Figure 12(b)). The projection of the circle on the screen plane is also a straight line. It can be modified and then to modify the circle actually to make it become a spatial stroke (as shown in Figure 12(c)).

Figure 11.

Projective fitting of a closed triangle: (a) a closed triangle, (b) projection of triangle, and (c) 3D triangle created.

Figure 12.

Projective fitting of a closed circle: (a) original stroke, (b) projective stroke, and (c) 3D stroke created.

The last example demonstrates how to sketch a lamp frame or outlines of vehicle. At first, a working plane is defined, which may be the screen plane N or a plane W (as shown in Figure 13(a)) in the front 3/4 view, for instance, so that the strokes drawn on the screen N are actually drawn on the working plane W. The strokes was smoothed and processed to form a closed planar outline of lamp (as shown in Figure 13(b) and (c)). The working plane is turned into another view (as shown in Figure 13(d)), and a modifying stroke is sketched to bend the frame of lamp (as shown in Figure 13(e)). Now the frame of lamp is a spatial one to meet the actual requirement of automotive styling (as shown in Figure 13(f)), and then the surface of lamp is created according to the frame. Some details are added to complete the design of lamp (as shown in Figure 13(g)–(i)).

Figure 13.

Sketching a lamp frame: (a) strokes on the plane W, (b) stroke processing, (c) closed frame of lamp in 2D, (d) sketch a modifying stroke, (e) curved frame of lamp, (f) 3D frame of lamp, (g) sketch on the surface of lamp, (h) add the details, and (i) add some ornaments.

Orthographic resultant method

Algorithm

In the freehand sketching, the drawing deviation is unavoidable. A mathematical model of surface intersection is built at first in order to make an accurate expression of the position of the intersection stroke. The calculation process of 3D reconstruction is degraded; the spatial stroke is projected onto the screen plane and then is fitted in real time to realize the fitting of its original spatial stroke.

The convex hull construction of spatial stroke is the basis for calculating interpolation of the spatial intersection stroke. The idea of incremental algorithm of calculating the convex hull in 2D space is extended to 3D one. Unlike in 2D space, the data structure of convex hull in 3D space is composed of vertices, edges, and surface, which also allows adding or deleting each element.

The incremental algorithm of convex hull in 3D is similar to it in 2D. Each scattered spatial data point will be processed and combined with the previous point within the convex hull. All the coplanar points can produce a planar convex polygon in 2D, and the convex hull in 3D is considered as a cone (as shown in Figure 14). The visible surface must be removed from the current convex hull and the surface of cone must be added.

Figure 14.

Current convex hull of spatial points.

A spatial surface is composed of convex hull data points, which is presented by the strokes corresponding to nodes with the same parameters in the u and v directions (as shown in Figure 15). A local change of a surface patch will occur when the stroke is changed in the u or v parametric direction. It shows that the purpose of changing the surface shape can be achieved by changing the shape of the parametric strokes.

Figure 15.

Local changes of a surface patch.

The projective stroke in the xy, yz, or xz plane can be obtained, respectively, through the projection of a spatial stroke along the axial direction. The shapes of projective strokes are different. The extended surface can be obtained easily by expanding the projective stroke along the normal of the projective plane (as shown in Figure 16(a) and (b), where S is the spatial stroke and $P_{\mathrm{xy}}$ and $P_{\mathrm{yz}}$ are the projective strokes of the stroke S). The intersecting stroke of the extended surfaces is the original spatial stroke S (as shown in Figure 17), which shows the relationship between the spatial strokes and the extended surfaces.

Figure 16.

Extended surfaces.

Figure 17.

Intersection of extended surfaces.

From a mathematical point of view to solve the problem of computer graphics, solving the intersecting curve of two surfaces can be understood as follows: the ternary simultaneous equations with the higher order of the two surfaces are built at first, and the equations are eliminated. The two coordinate parameters left represent the orthographic projection of surface on the projective plane.

The concept of resultant is introduced here to solve the problem above. The definition of resultant is as follows: for two polynomials

$$\{\begin{array}{c}\hfill f\left(x\right)=a_0{x}^n+a_1{x}^{n-1}+\cdots +a_{n-1}x+a_n\hfill \\ \multicolumn{1}{c}{g\left(x\right)=b_0{x}^m+b_1{x}^{m-1}+\cdots +b_{m-1}x+b_m}\end{array}$$

(18)

the determinant of coefficient is

$$\left[\begin{array}{c}\hfill a_0{a}_1\cdots a_n\hfill \\ \multicolumn{1}{c}{a_0{a}_1\cdots a_n}\\ \multicolumn{1}{c}{\cdots }\\ \multicolumn{1}{c}{a_0{a}_1\cdots a_n}\\ \multicolumn{1}{c}{b_0{b}_1\cdots b_m}\\ \multicolumn{1}{c}{b_0{b}_1\cdots b_m}\\ \multicolumn{1}{c}{\cdots }\\ \multicolumn{1}{c}{b_0{b}_1\cdots b_m}\end{array}\right]$$

(19)

which is called the resultant of polynomials $f(x)$ and $g(x)$ , denoted by $R(f,g)$ .

Resultant theorem

Assume that there is one indeterminate in the polynomials in equation (18) and $m,n>0$ . The necessary and sufficient condition of $R(f,g)=0$ is that the coefficients of $f(x)$ and $g(x)$ are $a_0=0$ and $b_0=0$ , or there is inconstant common factor.

The theorem is very important to deal with the problem discussed above. Assume that $f(x,y)$ and $g(x,y)$ are bivariate polynomials with real coefficients and are required

$$\{\begin{array}{c}\hfill f(x,y)=0\hfill \\ \multicolumn{1}{c}{g(x,y)=0}\end{array}$$

(20)

with all solutions in the domain of real numbers so that $f(x,y)$ and $g(x,y)$ can be written as follows

$$\{\begin{array}{c}\hfill f(x,y)=\sum _{i=0}^n{a}_i\left(y\right)x^{n-i}\hfill \\ \multicolumn{1}{c}{g(x,y)=\sum _{j=0}^m{b}_j\left(y\right)x^{m-j}}\end{array}$$

(21)

where $a_i(y)$ and $b_j(y)$ , $i=0,1,\dots ,n\mathrm{and}j=0,1,\dots ,m$ , are the polynomials of y. $f(x,y)$ and $g(x,y)$ are considered as the resultant of coordinate y, denoted by $R_x(f,g)$ as follows

$$\left[\begin{array}{c}\hfill a_0\left(y\right)a_1\left(y\right)\cdots a_n\left(y\right)\hfill \\ \multicolumn{1}{c}{a_0\left(y\right)a_1\left(y\right)\cdots a_n\left(y\right)}\\ \multicolumn{1}{c}{\cdots }\\ \multicolumn{1}{c}{a_0\left(y\right)a_1\left(y\right)\cdots a_n\left(y\right)}\\ \multicolumn{1}{c}{}\\ \multicolumn{1}{c}{b_0\left(y\right)b_1\left(y\right)\cdots b_m\left(y\right)}\\ \multicolumn{1}{c}{b_0\left(y\right)b_1\left(y\right)\cdots b_m\left(y\right)}\\ \multicolumn{1}{c}{\cdots }\\ \multicolumn{1}{c}{b_0\left(y\right)b_1\left(y\right)\cdots b_m\left(y\right)}\end{array}\right]$$

(22)

Solving shows that if $(x_0,y_0)$ is a solution of equation (20), the root of $R_x(f,g)=0$ is $y_0$ ; on the contrary, if the root of it is $y_0$ , $a_0(y_0)=b_0(y_0)=0$ or there is a real number $x_0$ so that $(x_0,y_0)$ is a real solution of equation (20). That is to say, getting the real root $y_0$ from $R_x(f,g)=0$ , there must be $(x_0,y_0)$ to satisfy equation (20) if $a_0(y_0)=b_0(y_0)=0$ is not established.

From the point of view of geometric mathematics, $f(x,y)=0$ and $g(x,y)=0$ represent two planar curves, and $R_x(f,g)=0$ is the intersection of these two curves. The conclusion above is extended to 3D space. Assume that a pair of ternary polynomials with real coefficients is $f(x,y,z)$ and $g(x,y,z)$ , which are considered as the polynomials about parameter z, and are written as

$$\{\begin{array}{c}\hfill f(x,y,z)=\sum _{i=0}^n{a}_i(x,y)z^{n-i}\hfill \\ \multicolumn{1}{c}{g(x,y,z)=\sum _{j=0}^m{b}_j(x,y)z^{m-j}}\end{array}$$

(23)

where $a_i(x,y)$ and $b_j(x,y)$ are the polynomials of x and y, $i=0,1,\dots ,n\mathrm{and}j=0,1,\dots ,m$ , denoted by $R_{\mathrm{z}}(f,g)$ as follows

$$\left[\begin{array}{c}\hfill a_0(x,y)a_1(x,y)\cdots a_n(x,y)\hfill \\ \multicolumn{1}{c}{a_0(x,y)a_1(x,y)\cdots a_n(x,y)}\\ \multicolumn{1}{c}{\cdots }\\ \multicolumn{1}{c}{a_0(x,y)a_1(x,y)\cdots a_n(x,y)}\\ \multicolumn{1}{c}{b_0(x,y)b_1(x,y)\cdots b_m(x,y)}\\ \multicolumn{1}{c}{b_0(x,y)b_1(x,y)\cdots b_m(x,y)}\\ \multicolumn{1}{c}{\cdots }\\ \multicolumn{1}{c}{b_0(x,y)b_1(x,y)\cdots b_m(x,y)}\end{array}\right]$$

(24)

Similarly, if the root $(x_0,y_0,z_0)$ is a solution of $f(x,y,z)=0$ and $g(x,y,z)=0$ , $(x_0,y_0)$ must be a root of $R_z(f,g)=0$ ; otherwise, for a root $(x_0,y_0)$ when $R_z(f,g)=0$ , either $a_0(x_0,y_0)=b_0(x_0,y_0)=0$ is set up or there is a real root $z_0$ to make $(x_0,y_0,z_0)$ be a real solution of equation (23).

The geometric meaning of the mathematical model is: $f(x,y,z)=0$ and $g(x,y,z)=0$ represent two space surfaces, $R_z(f,g)=0$ stands for the orthographic projective curve which the intersecting curve of these two surfaces project on the xy plane (as shown in Figure 18). So $R_y(f,g)=0$ stands for the one project on the xz plane, and $R_x(f,g)=0$ stands for the one project on the yz plane.

Figure 18.

Geometric meaning of resultant method.

Examples

The algorithm above was applied in AutoSketch system and tested. Here gives an example of 3D stroke creation.

Some strokes (the dotted ones as shown in Figure 17(a)) are sketched on the screen plane N, which is the working plane currently. They are joined together through the combination algorithm ¹¹ into a smooth stroke (the orange stroke as shown in Figure 19(a)). This is the first stroke for 3D stroke creation, which is located in the xy plane and will not be changed later on after switching the working plane on the floor (as shown in Figure 19(b)). Now the working plane and the screen plane N are perpendicular to each other. An extended virtual surface is created by giving an extending vector (the positive z-axis is used here as show in Figure 19(c)) and then is pointed as the new working plane (a surface). Now some new strokes (dotted ones as shown in Figure 19(d)) are sketched on the screen plane N and combined as the second stroke (yellow one as shown in Figure 19(e)) for 3D stroke creation, which is located in the xz plane. The projective stroke of the second stroke is on the working plane, which is fitted by the first and the second strokes (green one as shown in Figure 19(f)). It looks like sketching directly on the working surface while sketching the second stroke, because they are overlapped while looking the screen. The projective stroke is an actual required 3D stroke. If modifying the second stroke further, new modifying stroke(s) can be drawn on the screen plane N (dotted ones as shown in Figure 19(g)) and then the second stroke is changed in shape (brown one as shown in Figure 19(h)). The 3D stroke is also changed at the same time (pink one as shown in Figure 19(i)). This example shows a typical case. In general, the extending vector can be in any direction. Therefore, the extending surface may be changed.

Figure 19.

First stroke created in AutoSketch: (a) multi-strokes and their combination, (b) change the working plane, (c) an extended surface created, (d) new multi-strokes sketched on the screen, (e) combined to a new stroke, (f) its projective stroke on the working plane, (g) new stroke for modification, (h) the new stroke changed, and (i) projective stroke changed then.

Another example shows how to draw a side waist outline of vehicle. A stroke is sketched first in the xy plane in the current working coordinate system and selected with highlight in red (as shown in Figure 20). If it needs to be modified in the z direction, the current working plane is set to be parallel to the plane xz, and a modifying stroke is sketch on it (green one as shown in Figure 21). Therefore, the new 3D stroke is created (as shown in Figure 22). This is a spatial waist outline that meets the curve features of automotive styling.

Figure 20.

Choose a smooth stroke on the plane xy.

Figure 21.

Draw the modifying stroke.

Figure 22.

New 3D stroke after fitting.

Conclusion

The research has discussed three issues to create 3D stroke based on the previous studies in the planar stroke combination algorithms developed. The first algorithm of 3D stroke fitting is realized by calculating simply the interpolation points of two strokes, which are located in two orthogonal planes. This algorithm is suitable for the simple strokes. It does not work well for the closed strokes. Therefore, the second one has been developed to work well with the case. It creates 3D stroke by the projection of two strokes in two orthogonal planes and the lofting. The third one has investigated the 3D stroke obtained from the intersecting stroke or curve of two surfaces. It projects a spatial stroke onto the screen plane to get a projective stroke, which is modified on the screen, and then the original spatial stroke is changed reversely by intersection. Three methods have been prototyped in AutoSketch system. Comparing three algorithms, the first one is simple and easy to calculate, the second one is suitable for more cases, and the third one gives a more general solution. However, the reliability and availability of algorithms need to be improved further.