---

gugr_face.cpp

Go to the documentation of this file.

/* LIBGUL - Geometry Utility Library
 * Copyright (C) 1998-1999 Norbert Irmer
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

#include "stdafx.h"

#include <iostream>

#include "gul_types.h"
#include "gul_vector.h"
#include "gul_matrix.h"
#include "guge_normalize.h"
#include "guma_lineq.h"
#include "guar_exact.h"
#include "gugr_basics.h"
#include "gugr_regularize.h"
#include "gugr_triangulate.h"
#include "gugr_planesweep.h"
#include "gugr_contour.h"
#include "gul_io.h"
#include "gul_std.h"
#include "gugr_io.h"

namespace gugr {

using gul::VMProduct;
using guma::GaussJordan;
using gul::point;
using gul::point2;
using gul::Ptr;
using guge::CalcBoundingBoxE;
using guge::UpdateBoundingBoxE;
using guar::Interval;
using gul::Max;
using guar::GetRatio;
using guar::Test;
using gul::rtr;
using gul::Swap;
using gul::cross_product;

using gul::ListNode;
using gul::List;
using gul::ListNodeInfo;
using gul::point;
using gul::itriangle;

using gul::set;
using gul::normalize;
using guar::Interval;
using guar::Sqrt;
using guar::Test;

#if 0

template< class T >
bool FaceArea( 
       int nVerts, const Ptr< point<T> >& Verts, int faceleft, int faceright,
       point<T> *retNormal, int *retFaceleft, int *retFaceright, T *retArea,
       int *ret_nTrii, Ptr<int[3]> *retTrii )
{
  gugr::triangle_list Tri;
  gugr::triangle *tri,*tri_next;
  T area;
  point<T> v,p1,p2,p3;
  Ptr<int[3]> Trii;
  int count,i0,i1,i2;

  if( !DoTriangulateFace( nVerts, Verts, faceleft, faceright, &Tri, retNormal,
                          retFaceleft, retFaceright ) )
    return false;

  // calculate the area of the polygon (for lighting calculations)

  Trii.reserve_pool(Tri.nElems);
  count = 0;
  
  tri = Tri.First();
  Tri.ReleaseElems();
  area = (T)0;
  while( tri != 0 )
  {
    // this could be done more optimal !!!!

    i0 = Trii[count][0] = (int)tri->v[0].m_rep->reserved;
    i1 = Trii[count][1] = (int)tri->v[1].m_rep->reserved;
    i2 = Trii[count][2] = (int)tri->v[2].m_rep->reserved;
    p1 = Verts[i0];
    p2 = Verts[i1];
    p3 = Verts[i2];

    v = gul::cross_product(p2-p1,p3-p1);
    area += gul::length(v)/(T)2;

    tri_next = tri->next;
    delete tri;     // delete triangle rec;
    tri = tri->next;

    count++;
  }
  *retArea = area;
  *ret_nTrii = count;
  *retTrii = Trii;

  return true;
}
// template instantiation
template bool FaceArea<float>( 
  int nVerts, const Ptr< point<float> >& Verts, int faceleft, int faceright,
  point<float> *retNormal, int *retFaceleft, int *retFaceright, float *retArea,
  int *ret_nfloatrii, Ptr<int[3]> *retfloatrii );
template bool FaceArea<double>( 
 int nVerts, const Ptr< point<double> >& Verts, int faceleft, int faceright,
 point<double> *retNormal, int *retFaceleft, int *retFaceright, double *retArea,
 int *ret_ndoublerii, Ptr<int[3]> *retdoublerii );

#endif

/*-------------------------------------------------------------------------
  calculates the plane in which the vertices of a polygon, consisting of a
  single contour with coplanar 3d vertices, lies.
 
  it tries to avoid calculating a normal vector which is totally
  wrong (because of rounding errors) by calculating the normal at the vertex
  which gives the smallest upper/lower bound ratio by interval arithmetic
--------------------------------------------------------------------------*/

template< class T >
GULAPI bool CalcPlane( 
                int nVerts, const Ptr< point<T> >& Verts,
                point<T>& o, point<T>& b1, point<T>& b2, point<T>& b3 )
{
  Interval ix0,iy0,iz0,ix1,iy1,iz1,ix2,iy2,iz2,ibx1,iby1,ibz1,ibx2,iby2,ibz2;
  Interval ilen,ilen2,inx,iny,inz;
  double rat,rat1;
  int i0,i1,i2,irat0,irat1,irat2;
  point<T> v1,v2;

  irat0 = -1;
  rat = rtr<double>::giant();  // start with a gigantic ratio

  for( i0 = 0; i0 < nVerts; i0++ )
  {
    ix0 = Verts[i0].x;
    iy0 = Verts[i0].y;
    iz0 = Verts[i0].z;
    
    i1 = i0+1; if( i1 == nVerts ) i1 = 0;
    i2 = i1+1; if( i2 == nVerts ) i2 = 0;

    // calc first basis vector

    ix1 = Verts[i1].x;
    iy1 = Verts[i1].y;
    iz1 = Verts[i1].z;

    ibx1 = ix1 - ix0;
    iby1 = iy1 - iy0;
    ibz1 = iz1 - iz0;

    // normalize b1

    ilen2 = ibx1*ibx1 + iby1*iby1 + ibz1*ibz1;
    ilen = Sqrt( ilen2 ); 
    if( Test(ilen)==0 ) continue;   // avoid division by zero

    ibx1 = ibx1 / ilen;
    iby1 = iby1 / ilen;
    ibz1 = ibz1 / ilen;

    // calc second basis vector of plane

    ix2 = Verts[i2].x;
    iy2 = Verts[i2].y;
    iz2 = Verts[i2].z;

    ibx2 = ix2 - ix0;
    iby2 = iy2 - iy0;
    ibz2 = iz2 - iz0;

    // project vector onto b1 

    ilen = ibx2*ibx1 + iby2*iby1 + ibz2*ibz1;

    // get the component orthogonal to b1

    ibx2 = ibx2 - ilen * ibx1;
    iby2 = iby2 - ilen * iby1;
    ibz2 = ibz2 - ilen * ibz1;

    // normalize b2

    ilen2 = ibx2*ibx2 + iby2*iby2 + ibz2*ibz2;
    ilen = Sqrt( ilen2 ); 
    if( Test(ilen)==0 ) continue;   // avoid division by zero

    ibx2 = ibx2 / ilen;
    iby2 = iby2 / ilen;
    ibz2 = ibz2 / ilen;

    // calculate the crossproduct of b1 and b2

    inx = iby1*ibz2 - ibz1*iby2;
    iny = ibz1*ibx2 - ibx1*ibz2;
    inz = ibx1*iby2 - iby1*ibx2;

    // normalize it (superfluous since b1 and b2 are orthonormal)

    ilen2 = inx*inx + iny*iny + inz*inz;
    ilen = Sqrt( ilen2 ); 
    if( Test(ilen)==0 ) continue;

    inx = inx / ilen;
    iny = iny / ilen;
    inz = inz / ilen;

    rat1 = GetRatio(inx*inx + iny*iny + inz*inz);
    if( rat1 < rat ) 
    {
      rat  = rat1;
      irat0 = i0;
      irat1 = i1;
      irat2 = i2;
    }
  }
  if( (irat0 < 0) || (rat == rtr<double>::giant()) ) return false;
  i0 = irat0;
  i1 = irat1;
  i2 = irat2;
 
  // the same calculation as above, now with floating point arithmetic

  o = Verts[i0];
  v1 = Verts[i1] - o;
  v2 = Verts[i2] - o;
  normalize(&b1,v1);
  b2 = v2 - (v2*b1)*b1;
  normalize(&b2,b2);
  b3 = cross_product(b1,b2);
  normalize(&b3,b3);

  return true;
}
// template instantiation
template GULAPI bool CalcPlane( 
       int nVerts, const Ptr< point<float> >& Verts,
       point<float>& o, point<float>& b1, point<float>& b2, point<float>& b3 );
template GULAPI bool CalcPlane( 
   int nVerts, const Ptr< point<double> >& Verts,
   point<double>& o, point<double>& b1, point<double>& b2, point<double>& b3 );

/*----------------------------------------------------------------------
  Check if a contour is lefthanded (if the contour self-intersects this
  check makes no sense)
----------------------------------------------------------------------*/

template< class T >
GULAPI bool CheckLeftHandedness( 
             int nP, const Ptr< point<T> >& P, const Ptr< Ptr<T> >& Ti,
             bool& lefthanded, bool& selfintersect )
{
  polyline pl;
  Ptr< point2<T> > P2;
  Ptr<T> v3,v2;
  List< ListNode<segment> > segs,outsegs;
  ListNode<segment> *seg;
  graph_edge_list E;
  graph_vertex_list V;
  rational far_minx,far_maxx,far_miny,far_maxy;
  T minx,maxx,miny,maxy;
  T dx,dy,scale,scalei;
  int i,left;
  List< ListNode< ListNodeInfo< ListNode<graph_edge *> > > > *L;
  graph_edge *e;
  List< ListNode<graph_edge *> > *Le;
  unsigned long *cbuf = 
    (unsigned long *)alloca(gul::rtr<T>::mantissa_length());
  
  if( !nP ) return false;

  // project vertices onto plane

  P2.reserve_pool(nP);
  v3.reserve_pool(4);
  v2.reserve_pool(4);

  for( i = 0; i < nP; i++ )
  {
    v3[0] = P[i].x;
    v3[1] = P[i].y;
    v3[2] = P[i].z;
    v3[3] = (T)1;

    VMProduct(4,4,v3,Ti,v2);

    P2[i].x = v2[0];
    P2[i].y = v2[1];
  }

  CalcBoundingBoxE( nP, P2, minx, maxx, miny, maxy );

  dx = maxx - minx;
  dy = maxy - miny;
  scale = dx > dy ? dx : dy;
  minx -= scale;
  miny -= scale;
  scalei = (T)1.0/scale;

  /*
  Dump<float>::set_transformation(minx,miny,scale,scale);
  */

  pl.init( nP, P2, minx, miny, scalei ); 

  AppendContour( &pl, 0, 1, segs );
 
  IntersectSegments( segs, &E, &V, true );

  /*
  std::cout << "EDGES AFTER INTERSECTION\n";
  std::cout << "========================\n";
  Dump<float>::dump_edges( E.head );
  std::cout << "\n";
  */

  far_miny = far_minx = rational( guar::ULong(0x100000), -1 );
  far_maxy = far_maxx = rational( coord2int((T)2,cbuf),cbuf) +
                                      rational( guar::ULong(0x100000) );

  RemoveUnnecessaryEdges( E, V, far_maxx, far_maxy, 1, 0, outsegs );

  e = E.First(); if( !e ) return false; // internal error

  // backpointer to the segment edge lists which contain the fist edge
  L = (List< ListNode< ListNodeInfo< ListNode<graph_edge *> > > > *)
                                                               e->reserved[1].p;
  // the first backpointed List
  Le = L->First()->el.m_L;

  // find the corresponding segment 
  for( seg = segs.First(); seg != 0; seg = seg->next )
    if( &seg->el.e == Le ) break;

  if( !seg ) return false;  // internal error
  
  if( e->l.IsHorizontal() || (e->l.dx().test() < 0) )
    left = e->f[1].i;         // edge orientation different
  else
    left = e->f[0].i;

  lefthanded = (left != 1);

  // check if there were self-intersections
  
  for( seg = segs.First(); seg != 0; seg = seg->next )
    if( seg->el.e.nElems != 1 ) break;

  selfintersect = (seg != 0);

  // delete data which would not be automatically destructed

  e = E.First();
  while( e )         // delete backpointer lists
  {
    L = (List< ListNode< ListNodeInfo< ListNode<graph_edge *> > > > *)
                                                               e->reserved[1].p;
    L->DeleteElems();
    delete L; 
    e->reserved[1].p = 0;
    e = e->next;
  }    

  return true;
}
template GULAPI bool CheckLeftHandedness( 
           int nP, const Ptr< point<float> >& P,  const Ptr< Ptr<float> >& Ti,
           bool& lefthanded, bool& selfintersect );
template GULAPI bool CheckLeftHandedness( 
           int nP, const Ptr< point<double> >& P, const Ptr< Ptr<double> >& Ti,
           bool& lefthanded, bool& selfintersect );


template< class T >
void Polygon3dTo2d(
            const List< ListNode< gul::polyline< point<T> > > >& C3, 
            const Ptr< Ptr< T > >& Ti,
            List< ListNode< gul::polyline< point2<T> > > >& C2 )
{
  ListNode< gul::polyline< point<T> > > *c3;
  ListNode< gul::polyline< point2<T> > > *c2;
  int i;
  Ptr<T> v3,v2;

  v3.reserve_pool(4);
  v2.reserve_pool(4);

  c3 = C3.First();
  while( c3 )
  {
    c2 = new ListNode< gul::polyline< point2<T> > >;
    C2.Append( c2 );

    c2->el.n = c3->el.n;
    c2->el.P.reserve_pool( c3->el.n );
   
    for( i = 0; i < c3->el.n; i++ )
    {
      v3[0] = c3->el.P[i].x;
      v3[1] = c3->el.P[i].y;
      v3[2] = c3->el.P[i].z;
      v3[3] = (T)1;

      VMProduct(4,4,v3,Ti,v2);

      c2->el.P[i].x = v2[0];
      c2->el.P[i].y = v2[1];
    }

    c3 = c3->next;
  }
}
// template instantiation
template void Polygon3dTo2d(
            const List< ListNode< gul::polyline< point<float> > > >& C3, 
            const Ptr< Ptr< float > >& Ti,
            List< ListNode< gul::polyline< point2<float> > > >& C2 );
template void Polygon3dTo2d(
            const List< ListNode< gul::polyline< point<double> > > >& C3, 
            const Ptr< Ptr< double > >& Ti,
            List< ListNode< gul::polyline< point2<double> > > >& C2 );

/*------------------------------------------------------------------------
  Triangulate a polygon with 3d vertices, normals, and texture coordinates
-------------------------------------------------------------------------*/

template< class T >
GULAPI void TriangulatePolygon3d(
            const List< ListNode< gul::polyline< point<T> > > >& C3,
            const List< ListNode< gul::polyline< point<T> > > >& N3,
            const List< ListNode< gul::polyline< point<T> > > >& T3,
            const Ptr< Ptr< T > >& Ti,
            Ptr< point2<T> >& D,
            Ptr< point<T> >& F,
            Ptr< point<T> >& N,
            Ptr< point<T> >& Tx,
            int *nTri,
            Ptr<itriangle>& Tri )
{
  T minx,maxx,miny,maxy;
  T dx,dy,scale,scalei;
  ListNode< gugr::polyline > *pn,*inc;
  ListNode< gul::polyline< point<T> > > *inF,*inN,*inT;
  List< ListNode< gul::polyline< point2<T> > > > C2;
  ListNode< gul::polyline< point2<T> > > *c2;
  List< ListNode<polyline> > Pl;
  List< ListNode<segment> > segs,outsegs;
  ListNode<segment> *seg;
  graph_edge_list E;
  graph_vertex_list V;
  rational far_minx,far_maxx,far_miny,far_maxy;
  unsigned long *cbuf = 
    (unsigned long *)alloca(gul::rtr<T>::mantissa_length());
  int nv,i,nt;
  Ptr< point<T> > &sumF = F, &sumN = N, &sumT = Tx;
  Ptr<T> sumW;
  graph_vertex *vn;
  graph_edge *e;
  ListNode<graph_edge *> *en;
  Interval iu,iv;
  T u,v,u1,u2,v1,v2,su,sv,alpha,w,wi,giant;
  point<T> fB,nB,fE,nE,tB,tE,f,n,t;
  bool end;
  triangle_list tri;
  triangle *tr;

  if( C3.nElems == 0 ) return;

  giant = gul::rtr<T>::giant();

  Polygon3dTo2d( C3, Ti, C2 );

  c2 = C2.First();
  CalcBoundingBoxE( c2->el.n, c2->el.P, minx, maxx, miny, maxy );
  c2 = c2->next;

  while( c2 )
  {
    UpdateBoundingBoxE( c2->el.n, c2->el.P, minx, maxx, miny, maxy );
    c2 = c2->next;
  }

  dx = maxx - minx;
  dy = maxy - miny;
  scale = dx > dy ? dx : dy;
  minx -= scale;
  miny -= scale;
  scalei = (T)1.0/scale;

  c2 = C2.First();
  while( c2 )
  {
    pn = new ListNode<gugr::polyline>();
    Pl.Append( pn );
    pn->el.init( c2->el.n, c2->el.P, minx, miny, scalei ); 
    c2 = c2->next;
  }

  inc = Pl.First();
  inF = C3.First();
  inN = N3.First();
  inT = T3.First();

  while( inc )
  {
    AppendContourFNT( &inc->el, inF->el.P, inN->el.P, inT->el.P, 0, 0, segs );
    inc = inc->next;
    inF = inF->next;
    inN = inN->next;
    inT = inT->next;
  }

  IntersectSegments( segs, &E, &V, true );

  far_miny = far_minx = rational( guar::ULong(0x100000), -1 );
  far_maxy = far_maxx = rational( coord2int((T)2,cbuf),cbuf) +
                                      rational( guar::ULong(0x100000) );

  RemoveUnnecessaryEdges( E, V, far_maxx, far_maxy, 1, 0, outsegs );
    
  ISDeleteBackpointers(E); // the backpointers were used to remove edge entries
                           // from 'segs' in 'RemoveUnnecessaryEdges'
  outsegs.DeleteElems();

  // if the contours intersect each other 3d points and normals must be
  // calculated at the intersections  

  nv = V.nElems;
  D.reserve_pool(nv);
  sumF.reserve_pool(nv);
  sumN.reserve_pool(nv);
  sumT.reserve_pool(nv);
  sumW.reserve_pool(nv);

  i = 0;
  vn = V.First();
  while( vn )
  {
    vn->v.m_rep->reserved.i = i;  // enumber vertices

    iu = vn->v.v().x.get_bounds();
    iv = vn->v.v().y.get_bounds();
    u = (T)((iu.m_low+iu.m_high)/2.0);
    v = (T)((iv.m_low+iv.m_high)/2.0);
    u = gugr::cnv2coord(u)*scale + minx; 
    v = gugr::cnv2coord(v)*scale + miny; 

    D[i].x = u;
    D[i].y = v;
    set( sumF[i], (T)0 );
    set( sumN[i], (T)0 );
    sumW[i] = (T)0;

    i++;    
    vn = vn->next;
  }

  for( seg = segs.First(); seg != 0; seg = seg->next )
  {
    // get function value and normal of start and end point of segment
    fB = *((seg_point_info< point<T> > *)seg->el.reserved[0])->f;
    nB = *((seg_point_info< point<T> > *)seg->el.reserved[0])->n;
    tB = *((seg_point_info< point<T> > *)seg->el.reserved[0])->t;
    fE = *((seg_point_info< point<T> > *)seg->el.reserved[1])->f;
    nE = *((seg_point_info< point<T> > *)seg->el.reserved[1])->n;
    tE = *((seg_point_info< point<T> > *)seg->el.reserved[1])->t;
 
    // get u,v of segment start point
    iu = seg->el.E.x.get_bounds();
    iv = seg->el.E.y.get_bounds();
    u = (T)((iu.m_low+iu.m_high)/2.0);
    v = (T)((iv.m_low+iv.m_high)/2.0);
    u2 = cnv2coord(u)*scale + minx; 
    v2 = cnv2coord(v)*scale + miny; 

    // get u,v of segment end point
    iu = seg->el.B.x.get_bounds();
    iv = seg->el.B.y.get_bounds();
    u = (T)((iu.m_low+iu.m_high)/2.0);
    v = (T)((iv.m_low+iv.m_high)/2.0);
    u1 = cnv2coord(u)*scale + minx; 
    v1 = cnv2coord(v)*scale + miny; 
 
    su = u2 - u1;
    sv = v2 - v1;

    // travert edges on this segment

    en = seg->el.e.First();
    if( !en ) continue;
    e = en->el;
    if( e->l.IsHorizontal() || (e->l.dx().test() < 0) )
      end = 0;
    else
      end = 1;

    for( ; en != 0; en = en->next )
    {
      e = en->el;

      /* ---- first point of edge --------------------------- */

      vn = e->v[!end];
      i = vn->v.m_rep->reserved.i;
      u = D[i].x - u1;
      v = D[i].y - v1;
    
      if( su > sv )
        alpha = u/su;
      else if( sv > (T)0 )
        alpha = v/sv;
      else
        alpha = (T)0;

      if( (alpha == (T)0) || (alpha >= (T)1) )
      {
        wi = giant;
      }
      else 
      {
        if( alpha > (T)0.5 )
        {
          u = u2 - D[i].x;
          v = v2 - D[i].y;
        }
        w = u*u + v*v;
        if( w > (T)0 ) wi = (T)1.0/w;
        else wi = giant;
      }

      f = ((T)1.0-alpha)*fB + alpha*fE;
      n = ((T)1.0-alpha)*nB + alpha*nE;
      t = ((T)1.0-alpha)*tB + alpha*tE;

      if( wi >= giant )
      {
        if( sumW[i] >= (T)0 )
        {
          sumW[i] = (T)-1.0;
          sumF[i] = -f;
          sumN[i] = -n;
          sumT[i] = -t;
        }
        else
        {
          sumW[i] -= (T)1.0;
          sumF[i] -= f;
          sumN[i] -= n;
          sumT[i] -= t;
         }
      }
      else
      {
        sumW[i] += wi;
        sumF[i] += wi*f;
        sumN[i] += wi*n;
        sumT[i] += wi*t;
      }

      /* ---- second point of edge --------------------------- */

      if( en->next && (en->next->el->v[!end] == e->v[end]) )
        continue;    // will be processed with next edge
 
      vn = e->v[end];
      i = vn->v.m_rep->reserved.i;
      u = D[i].x - u1;
      v = D[i].y - v1;
    
      if( su > sv )
        alpha = u/su;
      else if( sv > (T)0 )
        alpha = v/sv;
      else
        alpha = (T)0;

      if( (alpha == (T)0) || (alpha >= (T)1) )
      {
        wi = giant;
      }
      else 
      {
        if( alpha > (T)0.5 )
        {
          u = u2 - D[i].x;
          v = v2 - D[i].y;
        }
        w = u*u + v*v;
        if( w > (T)0 ) wi = (T)1.0/w;
        else wi = giant;
      }

      f = ((T)1.0-alpha)*fB + alpha*fE;
      n = ((T)1.0-alpha)*nB + alpha*nE;
      t = ((T)1.0-alpha)*tB + alpha*tE;

      if( wi >= giant )
      {
        if( sumW[i] >= (T)0 )
        {
          sumW[i] = (T)-1;
          sumF[i] = -f;
          sumN[i] = -n;
          sumT[i] = -t;
         }
        else
        {
          sumW[i] -= (T)1;
          sumF[i] -= f;
          sumN[i] -= n;
          sumT[i] -= t;
        }
      }
      else
      {
        sumW[i] += wi;
        sumF[i] += wi*f;
        sumN[i] += wi*n;
        sumT[i] += wi*t;
      }
    }
  }

  for( i = 0; i < nv; i++ )
  {
    wi = (T)1/sumW[i];
    sumF[i] *= wi;
    sumN[i] *= wi;
    sumT[i] *= wi;
  }  

  // delete not needed data
  segs.DeleteElems();

  /* ---- finally, triangulate the graph ------------------- */

  Regularize( &E, &V );

  Triangulate( &E, &V, far_minx, &tri );

  nt = tri.nElems;
  Tri.reserve_pool(nt);
  tr = tri.First(); 

  for( i = 0; i < nt; i++ )
  {
    Tri[i].v[0] = tr->v[0].m_rep->reserved.i;
    Tri[i].v[1] = tr->v[1].m_rep->reserved.i;
    Tri[i].v[2] = tr->v[2].m_rep->reserved.i;
    tr = tr->next;
  }
  *nTri = nt;
}
// template instantiation
template GULAPI void TriangulatePolygon3d<float>(
            const List< ListNode< gul::polyline< point<float> > > >& C3,
            const List< ListNode< gul::polyline< point<float> > > >& N3,
            const List< ListNode< gul::polyline< point<float> > > >& T3,
            const Ptr< Ptr< float > >& Ti,
            Ptr< point2<float> >& D,
            Ptr< point<float> >& F,
            Ptr< point<float> >& N,
            Ptr< point<float> >& Tx,
            int *nTri,
            Ptr<itriangle>& Tri );

template GULAPI void TriangulatePolygon3d<double>(
            const List< ListNode< gul::polyline< point<double> > > >& C3,
            const List< ListNode< gul::polyline< point<double> > > >& N3,
            const List< ListNode< gul::polyline< point<double> > > >& T3,
            const Ptr< Ptr< double > >& Ti,
            Ptr< point2<double> >& D,
            Ptr< point<double> >& F,
            Ptr< point<double> >& N,
            Ptr< point<double> >& Tx,
            int *nTri,
            Ptr<itriangle>& Tri );


}

---