
ISSN 12149675 Server vznikl za podpory Grantové agentury ČR. 17. ročník 
Témata
Doporučujeme
Kontakt

Automatic Knotclouds Placement Algorithm for Quadratic DMSspline FunctionVydáno dne 06. 09. 2011 (10496 přečtení)Tento článek se zabývá algoritmem přidělování přídavných bodů pro kvadratickou DMSsplajnovou funkci s ohledem na splnění podmínek normality. Řešení tohoto problému je předpokladem pro použití této funkce v modelově orientované videokompresi. Automatic Knotclouds Placement Algorithm for Quadratic DMSspline FunctionThis article deals with automatic knotclouds placement algorithm for quadratic DMSspline function with regard to fulfillment of condition of normality. Solving this problem is a prerequisite for using this function in a modelbased video cooding. Keywords: Quadratic DMSspline function; Surface approximation; Human head model; Automatic knotclouds placement. IntroductionIn computer graphics, a crucial aspect is to create the 3D scene using the smallest number of polygons, while maintaining a realistic scene. A small number of polygons is necessary because it allows for faster transmission of the given scene, more precisely with low bit rate. However, the objects represented by a small number of polygons seem to be discontinuous (unrealistic). This disadvantage of discontinuity can be wellcompensated for by the approximation of polygonal surfaces (smoothing) by employing various approximation methods. One of these methods is the DMSspline function. The following figure (Fig. 1) shows an example of an approximated surface using the quadratic DMSspline function. Figure 1: Example of quadratic DMSsurface. Surfaces in computer graphicsIn geometric modelling surfaces are often represented by a set of n functions N_{i}: R^{2} → R with 0 ≤ i < n and corresponding control point c_{i} ∈ R^{3} [1], [2], [3], [4]. Also a domain Ω ⊂ R^{2} is defined. A point on the surface corresponding to a point c_{i} ∈ Ω is then defined as:
Some desired properties of these surfaces are:
Several surface classes (dependent on the choice of the blending functions N_{i} are used in computer graphics. Many of those are defined piecewise, i.e. the surface is constructed by defining smaller parts of the surface, called patches, each defined over a part of the domain which are then put together to form the total surface. The patches typically have rectangular or triangular domains. Triangular domains are sometimes preferred because they allow modelling surfaces with arbitrary polygonal domain (very polygon can be triangulated, but not all polygons can be build with rectangular domains). DMSspline functionDMSsplines were developed and first published in 1992 by W. Dahmen, C. A. Micchelim and H. P. Seidel; The name DMS is derived from the initials of their surnames [2], [5], [6], [7], [8], [9]. DMSsplines are functions that combine global smoothness of linear splines with the possibility of local control, thus the pleasant features of Bpatches. DMSsplines are due to the complexity of their definition unattractive to conventional modelling. However, global smoothness makes them suitable for variable modelling because we do not achieve by adding restrictions to the location of control points. DMSspline surface is like many other surfaces a weighted sum of control points. The weight of control points is given by blending function. DMSsplines as weighted functions use triangular spline functions. For DMSspline surface of degree ν_{i}, each control point is weighted by triangular spline degree n and by multiplication constant. In order to define DMSspline the domain triangular spline and other parameters need to define as well:
After we have provided these parameters, we can define a DMSspline surface. Each control point c^{I}_{β} is weighted by a simplex spline. The knotset of this simplex spline will contain n + 3 knots, hence the simplex spline will have degree n. The knotset of the simplex spline to weight c^{I}_{β} consists of a union of pre fixes of knotclouds defined in the vertices of the triangle I. The closer c^{I}_{β} lays to a vertex t_{j} of I, the more knots are taken from the corresponding knotcloud. Formally we have as definition . The simplex spline M(.V^{I}_{β} ) times a constant is then used as blending function for control point c^{I}_{β}. Let the set M(uV^{I}_{β}) be a triangle that consists of the last knots of the heads of the knotclouds of which consists, hence . The constant is then defined as . This constant is necessary to obtain affine invariance of the surface. The point on a surface, corresponding to a point u in the domain can now be expressed as:
To guarantee affine invariance and the convexhull property of DMSsplines we have to show that . To guarantee affine invariance and the convexhull property for surfaces requires more restrictions on the knotplacement than for infinite surface which is describing in next sections. A triangle I∈I may have nonzero influence (Fig. 2) outside the half open convex hull of the triangle I. This is a fundamental difference with usual surface constructions like Bpatches. This interference of triangles triangulation ensures global DMSspline functions smoothness.Figure 2: A single triangle I ∈I with its supports (green). Evaluation of Quadratic DMSspline FunctionQuadratic DMSspline functions have degree n = 2. The weights of control points, which depend on the evaluation point u, use quadratic triangular spline functions. In the nongeneralized case of quadratic DMSspline function, control points are a scalar value (rcoordinate). Quadratic DMSspline ElementQuadratic DMSspline element is defined as contribution of one triangle (t_{00}, t_{10}, t_{20}) of triangulation I to final DMSspline function. Support of this element is a dedicated set of points V = {t_{00}, t_{01}, t_{02}, t_{10}, t_{11}, t_{12}, t_{20}, t_{20}, t_{22}}. (See Fig. 2) Quadratic DMSspline element is defined as:
Table 1: Definition of quadratic triangular spline sets. Number of quadratic triangular splines and number of control points is (n+1)(n+2)/2 = (2+1)(2+2)/2 = 6, from which 3 are placed near the vertices of triangle I after their orthographic projection to the plane (h, v). Control point, placed on vertex of the triangle, is called vertex control point and the one placed on the edge is called side control point. Figure 2 illustrates support of the triangle I interference to other triangles in the triangulation I at given vertex and knotclouds position.Quadratic DMSspline FunctionThe final DMS quadratic spline function over the triangulation I is formed by contribution of quadratic DMSspline elements. Support of this function is determined as conjunction support of particular elements. Each vertex t_{i0} of triangulation I has two knotcloud points t_{i1} and t_{i2} assigned. If two or more triangles have common vertex then they also have common knotclouds. Number of control points c^{I}_{β} is defined as Imultiple of control points for single quadratic DMS element; ((n+1)(n+2)/2)I = ((2+1)(2+2)/2)I = 6I. And also, if two or more triangles have common vertex or edge then their control points have the same value. Final nongeneralized DMSspline function is defined as:
Quadratic DMSsurface over Arbitrary TriangulationCalculation of DMSsurface is based on generalizations of DMSspline function. When calculating the quadratic DMSspline functions, only rcoordinates of control points weighted by corresponding triangular splines are used. On the other hand, when calculating DMSsurface, this function is divided to three separate components and h,v and r are weighted separate. In this case control points lay in R^{3}. The result of DMSfunction calculation in u is point of DMSsurface defined by its three coordinates. Quadratic DMSsurface is then defined as:
Condition of NormalityCondition of normality is valid over whole triangulation I only for some allocations of knots. Knots must comply with following conditions:Conditions of normality for all vertices General conditions for all knotclouds (Fig. 3):
Figure 3: Conditions of normality  general. (Nonaccepted positions)
Additional condition for vertex t_{i0} inside of a triangulation (i.e. vertex t_{i0} is not boundary vertex of triangulation):
Figure 4: Conditions of normality  inside of triangulation. (No accepted positions)
Figure 5: Knotclouds placement for vertices t_{i0} on a triangulation border. Automatic Knotclouds Generation
This method is enhancement of the heuristic univariate Monte Carlo algorithm [10]. This method has one degree of freedom, i.e. the distance of knots from the vertex t_{i0} which they belong to (with regard to additional conditions described herein before). 1. Find all triangle where vertex t_{i0} is one of triangular vertices (Fig. 6). Figure 6: All triangles where vertex t_{i0} is one of its vertices. (red circles) 2. Determine two lines p_{1} and p_{2} passing trough vertex t_{i0} and axes of the largest angle α_{1} and the second largest α_{2} of these triangles. (Fig. 7, A) Figure 7: Knotclouds placement technique for vertex t_{i0} inside the triangulation I. 3. Define lengths D_{1} and D_{2}. Length D_{1} as approximately one third of shorter edge length d_{1} of triangle with the largest angle and with vertex t_{i0} and length D_{2} as approximately one third of shorter edge length d_{1} of triangle with the second largest angle and with vertex t_{i0}. (Fig. 7, B) 4. Placement of knots t_{i1} and t_{i2} on line p_{1}, resp. p_{2} in distance D_{1}, respectively D_{2} rom vertex t_{i0} inside of the triangle with the largest angle, respectively second largest angle. (Fig. 7, C) 5. Check if conditions of normality for knotclouds are met. If not, then reduce distance (in case, if knots extend to other triangles supports, where vertex t_{i0} is one of triangle vertices), respectively change line p_{1} (p_{2}) angle (in case, if knots are collinear with any vertex or one knot lay on the edge of a triangles). If after these steps, do not reached the conditions of normality over the whole triangulation, the triangulation is inconvenient and needs to control. Next figure (Fig. 8) illustrates knotclouds t_{i1} and t_{i2} placement of vertex t_{i0}. (Note: Connection between these points is only illustrative for better orientation in triangulation scheme.) Figure 8: Knotclouds placement for vertex t_{i0} inside the triangulation I. Knotclouds on the border of the triangulation (The vertex t_{i0} lay on the border of triangulation)
Figure 9: Determine of lines p_{1}, p_{2} and edges d_{1}, d_{2} single triangle.
 Define lengths D_{1} and D_{2} Length D_{1} as approximately one third of edge d_{1} length of triangle with vertex t_{i0} and closer to line p_{1}. Length D_{2} as approximately one third of edge d_{2} length of triangle with vertex t_{i0} and closer to line p_{2}. (Fig. 9, A). 2. Determine external angle γ which contain triangles edges, where is t_{i0} one of vertices (Fig. 10). Figure 10: Determine of angle γ.
If external angle γ > 180° continue:
Figure 11: Determine of lines p_{1}, p_{2} and edges d_{1}, d_{2} (multiple triangles, angle γ > 180°).
 Define lengths D_{1} and D_{2}. Length D_{1} as approximately one third of edge d_{1} length of triangle with vertex t_{i0} and closer to line p_{1}. Length D_{2} as approximately one third of edge d_{2} length of triangle with vertex t_{i0} and closer to line p_{2} (Fig. 10, B). 3. Determine two lines p_{1} and p_{2} passing thought vertex t_{i0} and axes of the largest angle α_{1} and second largest α_{2} these triangles. (Fig. 12, A) Figure 12: Determine of lines p_{1}, p_{2} and edges d_{1}, d_{2} (multiple triangles, angle γ < 180°).
4. Define lengths D_{1} and D_{2}. Length D_{1} as approximately one third of shorter edge d_{1} length of triangle with vertex t_{i0} and largest angles. Length D_{1} as approximately one third of shorter edge d_{1} length of triangle with vertex t_{i0} and second largest angles. (Fig. 12, B)
Next figure (Fig. 13) illustrates knotclouds t_{i1} and t_{i2} placement of vertex t_{i0}. (Note: Connection between these points is only illustrative for better orientation in triangulation scheme.) Figure 13: Knotcloud placement for vertex t_{i0} on the border the triangulation I. Influence of Knotclouds Placement to Approximation Surface of Human HeadKnotclouds influence the approximated surface in particular triangulation triangles’ supports intersection, where vertex having these knotclouds assigned is one of vertices. The knotclouds have the greatest influence in the area of the vertex to which they are assigned. After meeting conditions of knotclouds placement described in section Condition of Normality the approximated surface can be formed. Influence of knotclouds placement of approximated surface is exemplified on displacement of knots ti1 and ti2 of vertex ti0 (Fig. 14) in the left eyebrow area of CANDIDE 316 model [11]. Figure (Fig. 15) shows knotclouds placement generated by the method described in section Automatic Knotclouds Generation and approximated DMSsurface.Figure 14: Triangulation with knotclouds placement. A: initial position of knots; B: Detail A  placement of knots t_{i1} and t_{i2} of vertex. Figure 15: Initial position of knotclouds and approximated surface: A: left eyebrow area; B, C: approximated surface  front view filled (unfilled)triangulation after second interpolation and first DMS approximation with lighting and with averaging of normal vectors of particularly triangles. D, E: Approximation surface  left view filled (unfilled) triangulation after second interpolation and first DMS approximation with lighting and with averaging of normal vectors of particularly triangles.
Following figures (Fig. 16) show described affects of placement knotclouds.
 Type A: Triangulation a knotclouds placement t_{i1} and t_{i2} of vertex t_{i0}. Figure 16: Example of displacement of knotclouds.
The following figure (Fig. 17) shows incorrect placement knot t_{i2} which interferes in support of triangle out of the area defined by triangles where vertex is one of vertices. Figure 17: Example of incorrect knotclouds placement: A: left eyebrow area; B, C: approximated surface – front view filled (unfilled) triangulation after second interpolation and first DMS approximation with lighting and with averaging of normal vectors of particularly triangles. D, E: Approximation surface – left view filled (unfilled) triangulation after second interpolation and first DMS approximation with lighting and with averaging of normal vectors of particularly triangles. Following figures (Fig. 18 and 19) show the example of using DMSspline approximation with texture mapping. The CANDIDE 316 model used with texture of an attractive woman face, which is a research result at University of Regensburg [12] is shown in the folowing figures: Figure 18: Process of approximation and texture mapping (front view). A: Basic triangulation; B: Control points mesh for quadratic DMSsurface; C: Approximated triangulation; D: Real human head texture mapped on a 3D model. Figure 19: Process of approximation and texture mapping (left view). A: Basic triangulation; B: Control points mesh for quadratic DMSsurface; C: Approximated triangulation; D: Real human head texture mapped on a 3D model. Summary and Conclusions
The main goal of this work was to propose an effective way of using the quadratic DMSspline function to approximate surface area. The use of the quadratic DMSspline function requires solving of automatic knotclouds and side control point placement. In this article I propose a solution for the problem of automatic knotclouds placement with regard to fulfillment of condition of normality over the whole triangulation. Furthermore, the article shows usage of DMSspline function to approximate triangular mesh of CANDIDE 316 human head model. Proposed algorithm includes six steps which lead to the placement of knotclouds to the position to ensure normality of the whole triangulation with respect to surface smoothness. AcknowledgmentsThis article has originated thanks to the support from the Ministry of Education, Youth and Sports of Czech Republic within the project MSM6840770014. Bibliography
[1] Piegl L. and Tiller W. The NURBS Book. SpringerVerlag, 2nd edition, 1997. Autor: M. Nemčík Pracoviště: České vysoké učení technické v Praze, FEL 
Projekty a aktuality
01.03.2012: PROJEKT
Výzkum a vývoj nového komunikačního systému s vícekanálovým přístupem a mezivrstvovou spoluprací pro průmyslové aplikace TA02011015
01.01.2012: PROJEKT Vývoj adaptabilních datových a procesních systémů pro vysokorychlostní, bezpečnou a spolehlivou komunikaci v extrémních podmínkách VG20122014095
09.10.2010: PROJEKT Výzkum a vývoj datového modulu 10 Gbit/s pro optické a mikrovlnné bezdrátové spoje, FRTI2/621
09.01.2010: PROJEKT Sítě s femtobuňkami rozšířené o řízení interference a koordinaci informací pro bezproblémovou konektivitu, FP7ICT20094 248891
09.11.2008: PROJEKT Ochrana člověka a techniky před vysokofrekvenčním zářením, FIIM5/202
20.06.2008: Schválení Radou pro výzkum a vývoj jako recenzovaný časopis
01.04.2007: PROJEKT Pokročilá optimalizace návrhu komunikačních systémů pomocí neuronových sítí, GA102/07/1503
01.07.2006: Doplnění sekce pro registrované 12.04.2005: Zavedeno recenzování článků 30.03.2005: Výzkumný záměr Výzkum perspektivních informačních a komunikačních technologií MSM6840770014
29.11.2004: Přiděleno ISSN 04.11.2004: Spuštění nové podoby Access serveru 18.10.2004: PROJEKT Optimalizace přenosu dat rychlostí 10 Gbit/s, GA102/04/0773
04.09.2004: PROJEKT Specifikace kvalitativních kritérií a optimalizace prostředků pro vysokorychlostní přístupové sítě, NPV 1ET300750402
04.06.2004: PROJEKT Omezující faktory při širokopásmovém přenosu signálu po metalických párech a vzájemná koexistence s dalšími systémy, GA102/03/0434

Tento web site byl vytvořen prostřednictvím phpRS  redakčního systému napsaného v PHP jazyce.
Na této stránce použité názvy programových produktů, firem apod. mohou být ochrannými známkami
nebo registrovanými ochrannými známkami příslušných vlastníků.