d3tess Class Reference

A 2D tessellation with linked simplexes. More...

#include <d3tess.h>

Collaboration diagram for d3tess:

List of all members.

Public Member Functions
void	viadd (uintc v0, uintc v1, uintc v2, uintc n0=0, uintc n1=0, uintc n2=0)
void	minimizerSet (d3minoperator*m)
	Deletes the previous minimizer.
bool const	moveleft ()
bool const	moveright ()
bool const	movedown ()
bool const	boundaryorient ()
void	surfaceright ()
void	surfaceleft ()
simplexD2linked const &	cpsimplex () const
simplexface const	cpsimplexfaceget () const
void	cpsimplexfaceset (simplexface const &sf)
bool const	searchminimizetowardspoint (uintc p)
bool const	move_terminated (bool &insidesimplex, uint &viewableface, uintc p)
	One move - greedy.
void	initialize ()
	Uses the first three points build the first simplex, assumes the points can form a simplex.
void	addpoint (uintc k)
	Add an existing point to mesh creating new simplexes.
void	print (string &s) const
	Write the tessellation out.
ostream &	print (ostream &os) const
	Write the tessellation out.
istream &	serializeInverse (istream &is)
	Read the tessellation in.
bool const	valid (uintc k) const
bool const	debugcheck () const
	d3tess (uintc arrayMax)
	Constructor - reserves element size. The mesh is reset().
	~d3tess ()
	Destructor.
void	reset ()
	Reset the mesh.
bool const	isconnected (uintc a, uintc b) const
	Are the simplexes adjacent?
bool const	isconvex (uintc a, uintc b) const
	Are the simplexes adjacent and together convex?
bool const	surfaceviewable (uintc k) const
	Is the point viewable from vs's base?
bool const	flip ()
	Transform the virual triangle and base by flipping their triangles.
bool const	flip (uintc a, uintc b)
	Transform a and b by a flip if they are adjacent and together form a convex shape.
bool const	simplexdelete (uintc s)
	Delete the simplex.
void	simplexswap (uintc s0, uintc s1)
	Swap two simplexes.
void	removenullsimplexes ()
	Remove null simplexes if they exist by swapping and deleting end simplexes.
double const	cpbasemeasure () const
	Return the length of the cp's base line.
void	cppreserve (uint &cp0, virtualtriangle &vs0) const
	Save the current cp and orientation.
void	cppreserveInverse (uint const &cp0, virtualtriangle const &vs0)
	Restore the cp and orientation.
void	split2D (uintc w)
	Split the cp with the point w which is inside the triangle.
void	split1D (uintc s, uintc p0, uintc w0)
	Split simplex s on an edge at point w0 indexed by p0.
void	splitwithline (uintc s, uintc p0, uintc w0, uintc p1, uintc w1)
	Two points w0 and w1 on the boundary split the triangle. p0 and p1 index the points.
void	splitmidpoint1D (uintc s, uintc p1)
	Split the simplex on the 1D boundary in two. p1 is the point opposite the bounary edge.
Public Attributes
vector< pt3 >	pt
vector< simplexD2linked >	vi
uint	cp
virtualtriangle	vs
d3fan2	fan
d3minoperator*	minimizer
bool	debugenable
uint	movecounter

---

Detailed Description

A 2D tessellation with linked simplexes.

The third value is a function value at a point in 2D space.

Definition at line 29 of file d3tess.h.

---

Constructor & Destructor Documentation

d3tess::d3tess

(

uintc

arrayMax

)

Constructor - reserves element size. The mesh is reset().

Definition at line 350 of file d3tess.cpp.

References pt, reset(), and vi.

  : 
  fan(*this), 
  minimizer( new d3minoperator(*this) ),
  debugenable(true)
//  enablesplit(true),
//  enablefan(true)
{ 
  pt.reserve(arrayMax);
  vi.reserve(arrayMax);

  reset();
}

d3tess::~d3tess

(

)

Destructor.

Definition at line 344 of file d3tess.cpp.

References minimizer.

{
  delete minimizer;
  minimizer=0;
}

---

Member Function Documentation

void d3tess::addpoint

(

uintc

k

)

Add an existing point to mesh creating new simplexes.

Definition at line 631 of file d3tess.cpp.

References d3fan2::eval(), fan, searchminimizetowardspoint(), and split2D().

Referenced by addpointinsidemesh(), addrandompointtomesh(), and d3meshpointreader::eval().

{

  bool found = searchminimizetowardspoint(k);
  if (found)
  {

//cout << "*1: " << SHOW(enablesplit) << endl;
//    if (enablesplit==false)
//      return;

//cout << "*2" << endl;
    split2D(k);

    return;
  }


//cout << "*3: " << SHOW(enablefan) << endl;
//  if (enablefan==false);
//    return;

//cout << "*4" << endl;

  fan.eval(k);
}

bool const d3tess::boundaryorient

(

)

Definition at line 528 of file d3tess.cpp.

References cp, simplexD2linked::ni, virtualtriangle::set(), vi, and vs.

Referenced by keyboard().

{
  simplexD2linked const & x(vi[cp]);
  
  for (uint i=0; i<3; ++i)
    if(x.ni[0]==0)
    {
      vs.set(i);
      return true;
    }

  return false;
}

double const d3tess::cpbasemeasure

(

)

const

Return the length of the cp's base line.

Definition at line 554 of file d3tess.cpp.

References cp, point3< T >::distance(), simplexD2linked::pi, pt, virtualtriangle::v, vi, and vs.

{
  simplexD2linked const & x(vi[cp]);

  pt3 p0( pt[x.pi[vs.v[0]]]);
  pt3 p1( pt[x.pi[vs.v[1]]]);
  p0 -= p1;

  return p0.distance();
}

void d3tess::cppreserve	(	uint &	cp0,
		virtualtriangle &	vs0
	)			const

Save the current cp and orientation.

Definition at line 1071 of file d3tess.cpp.

References cp, and vs.

Referenced by d3tesspreserve::d3tesspreserve().

{
  cp0 = cp;
  vs0 = vs;
}

void d3tess::cppreserveInverse	(	uint const &	cp0,
		virtualtriangle const &	vs0
	)

Restore the cp and orientation.

Definition at line 1078 of file d3tess.cpp.

Referenced by d3tesspreserve::~d3tesspreserve().

{
  cp = cp0;
  vs = vs0;
}

simplexD2linked const& d3tess::cpsimplex

(

)

const [inline]

Definition at line 82 of file d3tess.h.

References cp, and vi.

Referenced by writecpcircleobj::draw(), and writecpobj::draw().

   { assert((cp!=0) && (cp<vi.size())); return vi[cp]; }

simplexface const d3tess::cpsimplexfaceget

(

)

const

Definition at line 542 of file d3tess.cpp.

References cp, virtualtriangle::v, virtualtriangle::validstate(), and vs.

{ 
  assert(vs.validstate()); 
  return simplexface(cp,vs.v[2]); 
}

void d3tess::cpsimplexfaceset

(

simplexface const &

sf

)

Definition at line 548 of file d3tess.cpp.

References cp, simplexface::face, simplexface::id, virtualtriangle::set(), and vs.

Referenced by d3fan::eval().

{
  cp = sf.id;
  vs.set(sf.face);
}

bool const d3tess::debugcheck

(

)

const

Definition at line 916 of file d3tess.cpp.

References debugenable, messageglobal(), valid(), and vi.

Referenced by d3fan2::eval(), d3fan::eval(), flip(), removenullsimplexes(), split1D(), split2D(), tessinit01(), tessinit02(), tessinitgeneral(), and test01().

{

  if (debugenable==false)
    return true;

// This function checks for correct links and
// duplicate traingles.
//
// Another test that could be added is to check the
// triangles winding. ie line(pi[0],pi[1]) to creat a halfplane h
// left and including the line.  h sees p[2]. Include degenerate case
// where all the points lie on the same line.

#ifndef NDEBUG

//cout << "DEBUG ON" << endl;

  bool res(true);
  uintc visz = vi.size();

  // Are the triangles unique.
  for (uint i=1; i<visz; ++i )
  {
    if ( vi[i].isnull() )
      continue;

    for (uint k=i+1; k<visz; ++k)
    {
      if (vi[i]==vi[k])
      {
        res=false;

        messageglobal() << "\n";
        messageglobal() << "error: triangles with the same points.\n";
        messageglobal() << "  check " << i << " " << k << "\n";
        messageglobal() << "vi[i]=" << vi[i] << "\n";
        messageglobal() << "vk[i]=" << vi[k] << "\n";
        messageglobal() << "\n";
        messageglobal() << *this;
      }
    }
  }
  assert(res==true);

  for (uint i=1; i<visz; ++i)
  {
    if ( vi[i].isnull() )
      continue;

    if(valid(i)==false)
    {
      res=false;
      messageglobal() << "error:  ";
      //messageglobal() << setw(2) << i;
      messageglobal() << "  " << vi[i] << "\n";
      messageglobal() << "Printing out tess." << "\n";
      messageglobal() << *this << "\n";
    }
  }

  assert(res==true);

  return res;

#else
  return true;
#endif

}

bool const d3tess::flip	(	uintc	a,
		uintc	b
	)

Transform a and b by a flip if they are adjacent and together form a convex shape.

Definition at line 996 of file d3tess.cpp.

References cp, debugcheck(), isconvex(), simplexD2linked::ni, simplexD2linked::niInverse(), simplexD2linked::pi, simplexD2linked::piInverse(), virtualtriangle::set(), virtualtriangle::v, vi, and vs.

{
//cout << a << " " << b << " " << isconvex(a,b) << " | ";
  if (isconvex(a,b)==false)
    return false;

  simplexD2linked const & A(vi[a]);
  simplexD2linked const & B(vi[b]);

  // Have vs base bordering triangle b.
  uint ai = A.niInverse(b);
  cp=a;
  vs.set(ai);

  // Extract point and neighbor information
  // from the mesh.

  uint p[4];

  for (uint i=0; i<3; ++i)
    p[i] = A.pi[ vs.v[i] ];
  p[3] = B.pi[B.niInverse(a)];

  uint n[4];
  n[0] = A.ni[ vs.v[0] ];
  n[1] = A.ni[ vs.v[1] ];
  n[2] = B.ni[ B.piInverse(p[0]) ];
  n[3] = B.ni[ B.piInverse(p[1]) ];

//for (uint i=0; i<4; ++i)
//  cout << "p[" << i << "]=" << p[i] << " ";
//cout << endl;

//for (uint i=0; i<4; ++i)
//  cout << "n[" << i << "]=" << n[i] << " ";
//cout << endl;

  // Overwrite the previous triangles with new ones.

  uint k[2];
  k[0] = a;
  k[1] = b;

  vi[k[0]] = simplexD2linked(p[3],p[2],p[0],n[1],n[3],k[1]);
  vi[k[1]] = simplexD2linked(p[2],p[3],p[1],n[2],n[0],k[0]);

  // Relink neighbors to new triangles.
  //   Test if the neighbor exists before resetting.
  if (n[3]!=0)
    vi[n[3]].changelink(b,a);
  if (n[0]!=0)
    vi[n[0]].changelink(a,b);

  // Have vs base bordering b.
  ai = A.niInverse(b);
  cp=a;
  vs.set(ai);

  debugcheck();

  return true; 
}

bool const d3tess::flip

(

)

Transform the virual triangle and base by flipping their triangles.

Definition at line 988 of file d3tess.cpp.

References cp, simplexD2linked::ni, virtualtriangle::v, vi, and vs.

Referenced by d3mincircle::eval(), d3mincentroid2::eval(), d3mincentroid::eval(), d3minboundary::eval(), and keyboard().

{
  simplexD2linked & x(vi[cp]);
  uint b = x.ni[vs.v[2]];

  return flip(cp,b);
}

void d3tess::initialize

(

)

Uses the first three points build the first simplex, assumes the points can form a simplex.

Definition at line 364 of file d3tess.cpp.

References halfspaceD2< PT, PD >::isInside(), pt, and vi.

Referenced by d3meshpointreader::eval(), and init02().

{
  assert(pt.size()>3);
  assert(vi.size()==1);

  pt3c & p0(pt[1]);
  pt3c & p1(pt[2]);
  pt3c & p2(pt[3]);

  halfspaceD2< pt3, double > h(p1,p0);
  if (h.isInside(p2)==false)
    vi.push_back( simplexD2linked(1,2,3, 0,0,0) );
  else
    vi.push_back( simplexD2linked(3,2,1, 0,0,0) );
}

bool const d3tess::isconnected	(	uintc	a,
		uintc	b
	)			const

Are the simplexes adjacent?

Definition at line 409 of file d3tess.cpp.

References vi.

Referenced by split1D(), and split2D().

{
#ifndef NDEBUG
  uintc sz(vi.size());
  assert(a<sz);
  assert(b<sz);
#endif

  //simplexD2linked const & A(vi[a]);
  //simplexD2linked const & B(vi[b]);

  if (vi[a].niInverseHas(b)==false)
    return false;

  if (vi[b].niInverseHas(a)==false)
    return false;

/*
  bool res;

  A.niInverse(res,b);
  if (res==false)
    return false;

  B.niInverse(res,a);
  if (res==false)
    return false;
*/

  return true;
}

bool const d3tess::isconvex	(	uintc	a,
		uintc	b
	)			const

Are the simplexes adjacent and together convex?

Definition at line 443 of file d3tess.cpp.

References halfspaceD2< PT, PD >::isInside(), simplexD2linked::niInverse(), simplexD2linked::pi, pt, and vi.

Referenced by d3mincircle::eval(), d3mincentroid2::eval(), d3mincentroid::eval(), d3minboundary::eval(), and flip().

{
#ifndef NDEBUG
  uintc sz(vi.size());
  assert(a<sz);
  assert(b<sz);
#endif

  simplexD2linked const & A(vi[a]);
  simplexD2linked const & B(vi[b]);

  bool res;

  uint ai = A.niInverse(res,b);
  if (res==false)
    return false;

  uint bi = B.niInverse(res,a);
  if (res==false)
    return false;

  pt3 const & P0(pt[A.pi[ai]]);
  pt3 const & P1(pt[A.pi[(ai+1)%3]]);
  pt3 const & P2(pt[A.pi[(ai+2)%3]]);

//cout << SHOW(P0) << " " << SHOW(P1) << " " << SHOW(P2) << endl;

  halfspaceD2< pt3, double > h1(P0,P1);
  halfspaceD2< pt3, double > h2(P2,P0);

  pt3 const & P3(pt[B.pi[bi]]);

  if (h1.isInside(P3)==false)
    return false;
  
  if (h2.isInside(P3)==false)
    return false;

  return true;
}

void d3tess::minimizerSet

(

d3minoperator*

m

)

Deletes the previous minimizer.

Definition at line 391 of file d3tess.cpp.

References minimizer.

Referenced by main(), and minimizermenu().

{
  assert(m!=0);

  delete minimizer;
  minimizer = m;
}

bool const d3tess::move_terminated	(	bool &	insidesimplex,
		uint &	viewableface,
		uintc	p
	)

One move - greedy.

Definition at line 690 of file d3tess.cpp.

References trianglespace< T, D >::hi, halfspaceD2< PT, PD >::isInside(), trianglespace< T, D >::isInside(), simplexD2linked::ni, and simplexD2linked::pi.

Referenced by searchminimizetowardspoint().

{
  //For measuring statistics only.
  ++movecounter;

  simplexD2linked & x(vi[cp]);

  assert(p<pt.size());
  point3<double> const & target(pt[p]);

  trianglespace<pt3,double> t
  ( 
    pt[ x.pi[0] ],
    pt[ x.pi[1] ],
    pt[ x.pi[2] ]
  );

  // Is the point inside the triangle?
  if (!t.isInside(target))
  {
    insidetriangle=true;

    return true;
  }

  for ( uint i=0; i<3; ++i )
  {
    // Is the target viewable?
    if (t.hi[i].isInside(target))
    {
      if(x.ni[i]==0)
      {
        viewableface=i;
        return true;
      }

      // Move
      cp = x.ni[i];

      return false;
    }
  }

  assert(false);

  return false;
}

bool const d3tess::movedown

(

)

Definition at line 511 of file d3tess.cpp.

References cp, simplexD2linked::ni, simplexD2linked::niInverse(), virtualtriangle::set(), virtualtriangle::v, vi, and vs.

Referenced by keyboard(), moveleft(), and moveright().

{
  simplexD2linked const & x(vi[cp]);

  uint cp2 = x.ni[ vs.v[2] ];
  if (cp2==0)
    return false;

  simplexD2linked const &  y(vi[cp2]);

  uint yi = y.niInverse(cp);
  cp = cp2;
  vs.set(yi);

  return true;
}

bool const d3tess::moveleft

(

)

Definition at line 485 of file d3tess.cpp.

References virtualtriangle::anticlockwise(), virtualtriangle::clockwise(), movedown(), and vs.

Referenced by keyboard(), and surfaceleft().

{
  vs.clockwise();

  if (movedown()==false)
  {
    vs.anticlockwise();
    return false;
  }

  return true;
}

bool const d3tess::moveright

(

)

Definition at line 498 of file d3tess.cpp.

References virtualtriangle::anticlockwise(), virtualtriangle::clockwise(), movedown(), and vs.

Referenced by keyboard(), and surfaceright().

{
  vs.anticlockwise();

  if (movedown()==false)
  {
    vs.clockwise();
    return false;
  }

  return true;
}

ostream & d3tess::print

(

ostream &

os

)

const

Write the tessellation out.

Definition at line 855 of file d3tess.cpp.

References pt, and vi.

{
  uintc ptsz = pt.size();
  os << ptsz << endl;

  for (uint i=0; i<ptsz; ++i)
  {
    os << setw(2) << i;
    os << "  " << pt[i] << endl;
  }

  uintc visz = vi.size();
  os << visz << endl;
  for (uint i=0; i<visz; ++i)
  {
    os << setw(2) << i;
    os << "  " << vi[i] << endl;
  }

  return os;
}

void d3tess::print

(

string &

s

)

const

Write the tessellation out.

Definition at line 826 of file d3tess.cpp.

References pt, and vi.

Referenced by operator<<().

{
  s="";
  uintc ptsz = pt.size();
  { stringstream ss; ss << ptsz; s+=(ss.str()+'\n'); }

  for (uint i=0; i<ptsz; ++i)
  {
    if (i<10)
      s += " ";
    if (i<100)
      s += " ";
    { stringstream ss; ss << i; s+=ss.str(); }
    s += ("  " + (string)(pt[i]) + '\n'); 
  }

  uintc visz = vi.size();
  { stringstream ss; ss << visz; s+=(ss.str()+'\n'); }
  for (uint i=0; i<visz; ++i)
  {
    if (i<10)
      s += " ";
    if (i<100)
      s += " ";
    { stringstream ss; ss << i; s+=ss.str(); }
    s += ("  " + (string)(vi[i]) + '\n');
  }
}

void d3tess::removenullsimplexes

(

)

Remove null simplexes if they exist by swapping and deleting end simplexes.

Definition at line 38 of file d3tess.cpp.

References debugcheck(), simplexswap(), and vi.

{    
  // Remove any null simplexes at the end of the 
  //   tessellation so the last simplex is non null 
  //   or there is no tessellation.
  if (vi[vi.size()-1].isnull())
  {
    for ( ; vi[vi.size()-1].isnull() && (vi.size()>1) ; )
      vi.pop_back();
  }

  // Swap null simplexes with non null simplexes
  //   and delete them.
  for (uint i=1; i<vi.size(); ++i)
  {
    if (vi[i].isnull()==false)
      continue;

    simplexswap(i,vi.size()-1);
    for ( ; vi[vi.size()-1].isnull() && (vi.size()>1) ; )
      vi.pop_back();
  }

  debugcheck();
}

void d3tess::reset

(

)

Reset the mesh.

vi[0] and pi[0] are the only items in vi and pi and are dummy values.

Definition at line 380 of file d3tess.cpp.

References cp, pt, and vi.

Referenced by d3tess(), mainmenu(), searchStats(), tessinit01(), tessinit02(), tessinitgeneral(), and timmingexperiment01().

{
  pt.clear();
  vi.clear();

  pt.push_back( pt3(0.0,0.0,0.0) );
  vi.push_back( simplexD2linked() );

  cp=1;
}

bool const d3tess::searchminimizetowardspoint

(

uintc

p

)

Definition at line 658 of file d3tess.cpp.

References virtualtriangle::anticlockwise(), move_terminated(), movecounter, virtualtriangle::v, and vs.

Referenced by addpoint(), addpointinsidemesh(), and searchStats().

{
  // Statistics only.
  movecounter = 0;

  bool notfound = false;
  bool isinside = false;
  uint viewableface;
  for ( ; !notfound; )
    notfound = move_terminated(isinside,viewableface,p);

  if (isinside==false)
  {
    if (vs.v[2]!=viewableface)
      vs.anticlockwise();
    else
      return isinside;

    if (vs.v[2]!=viewableface)
      vs.anticlockwise();
    else
      return isinside;

    if (vs.v[2]!=viewableface)
      assert(false);
  }
  
  return isinside;
}

istream & d3tess::serializeInverse

(

istream &

is

)

Read the tessellation in.

Definition at line 786 of file d3tess.cpp.

References cp, pt, and vi.

Referenced by operator>>().

{
  pt.clear();
  vi.clear();
  cp=1;

  pt3 p;

  uint sz;
  is >> sz;

  uint k;

  for (uint i=0; i<sz; ++i)
  {
    is >> k;
    is >> p;

    pt.push_back(p);
  }

  simplexD2linked t;

  is >> sz;
  for (uint i=0; i<sz; ++i)
  {
    is >> k;
    is >> t;

    vi.push_back(t);
  }

  return is;
}

bool const d3tess::simplexdelete

(

uintc

s

)

Delete the simplex.

Definition at line 316 of file d3tess.cpp.

References simplexD2linked::isnull(), simplexD2linked::ni, simplexD2linked::setnull(), and vi.

{
  if (s>=vi.size())
    return false;

  simplexD2linked & t(vi[s]);

  // If already deleted return true.
  if (t.isnull())
    return true;

  uint nb;

  // Visit each neighbor and unlink.
  for (int i=0; i<3; ++i)
  {
    nb = t.ni[i];
    if (nb!=0)
      vi[nb].changelink(s,0);
  }

  t.setnull();

  return true;
}

void d3tess::simplexswap	(	uintc	s0,
		uintc	s1
	)

Swap two simplexes.

Definition at line 64 of file d3tess.cpp.

References simplexD2linked::changelink(), simplexD2linked::ni, simplexD2linked::niInverse(), simplexD2linked::niInverseHas(), simplexD2linked::pi, and vi.

Referenced by removenullsimplexes().

{
  assert(s0<vi.size());
  assert(s1<vi.size());

  if (s0==s1)
    return;

  uint a[3];
  uint b[3];

  // Copy the neighbor links of both simplexes.
  uint i;

  simplexD2linked & A(vi[s0]);
  for (i=0; i<3; ++i)
    a[i] = A.ni[i];

  simplexD2linked & B(vi[s1]);
  for (i=0; i<3; ++i)
    b[i] = B.ni[i];

  // Change the links in the actual mesh.
  for (i=0; i<3; ++i)
  {
    if (a[i]==0)
      continue;

    simplexD2linked & x(vi[a[i]]);
    if (x.niInverseHas(s1)==false)
      x.changelink(s0,s1);
    else
    {
      // The case where the neighbor has both simplexes
      //   on its boundary.
      uint c = x.niInverse(s1);
      x.ni[ x.niInverse(s0) ] = s1;  
      x.ni[ c ] = s0;
    }
  }

  for (i=0; i<3; ++i)
  {
    if (b[i]==0)
      continue;
    simplexD2linked & x(vi[b[i]]);
    if (x.niInverseHas(s0)==false)
      x.changelink(s1,s0);
  }

  // Swap the simplexes s0 and s1 in memory
  uint c;
  for (i=0; i<3; ++i)
  {
    c = A.pi[i];
    A.pi[i] = B.pi[i];
    B.pi[i] = c;

    c = A.ni[i];
    A.ni[i] = B.ni[i];
    B.ni[i] = c;
  }
}

void d3tess::split1D	(	uintc	s,
		uintc	p0,
		uintc	w0
	)

Split simplex s on an edge at point w0 indexed by p0.

Definition at line 243 of file d3tess.cpp.

References debugcheck(), isconnected(), simplexD2linked::ni, simplexD2linked::niInverse(), simplexD2linked::pi, pt, and vi.

Referenced by splitmidpoint1D().

{
  assert(s<vi.size());

  uintc j = vi[s].piInverse(p0); 

  if (vi[s].ni[j]==0)
  {
    splitonboundarynoneighbor(s,j,w0);
    return;
  }

  // General Splitting on Boundary,
  //  four triangles produced.

  assert(w0<pt.size());
  assert(w0!=0);

  // Extract info from mesh.

  uint p[5];
  uint n[4];

  simplexD2linked & x(vi[s]);
  uint b = x.ni[j];
  assert(b!=0);
  simplexD2linked & y(vi[b]);

  assert( isconnected(s,b) );  

  uintc j2 = y.niInverse(s);

  p[0] = x.pi[(j+1)%3];
  p[1] = y.pi[j2];
  p[2] = x.pi[(j+2)%3];
  p[3] = x.pi[j];
  p[4] = w0;

  n[0] = x.ni[(j+1)%3];
  n[1] = x.ni[(j+2)%3];
  n[2] = y.ni[(j2+1)%3];
  n[3] = y.ni[(j2+2)%3];

  // Check the mesh before changing it.
  debugcheck();

  // Indexes to new triangles.
  uint k[4];
  k[0] = s;
  k[1] = b;
  k[2] = vi.size();
  k[3] = k[2]+1;

  x =           simplexD2linked(p[4],p[2],p[3],n[0],k[1],k[3]);
  y =           simplexD2linked(p[4],p[3],p[0],n[1],k[2],k[0]);
  vi.push_back( simplexD2linked(p[4],p[0],p[1],n[2],k[3],k[1]) );
  vi.push_back( simplexD2linked(p[4],p[1],p[2],n[3],k[0],k[2]) );

  if (n[0]!=0)
    vi[n[0]].changelink(s,k[0]);

  if (n[1]!=0)
    vi[n[1]].changelink(s,k[1]);

  if (n[2]!=0)
    vi[n[2]].changelink(b,k[2]);

  if (n[3]!=0)
    vi[n[3]].changelink(b,k[3]);

  debugcheck();
}

void d3tess::split2D

(

uintc

w

)

Split the cp with the point w which is inside the triangle.

Definition at line 568 of file d3tess.cpp.

References cp, debugcheck(), d3minoperator::eval(), isconnected(), minimizer, simplexD2linked::ni, simplexD2linked::pi, pt, and vi.

Referenced by addpoint().

{
  assert(w<pt.size());
  assert(w!=0);

  // Extract info from mesh.

  uint p[4];
  uint n[3];

//cout << SHOW(pt[w]) << "  ";
//cout << cpsimplex() << endl;

  simplexD2linked & x(vi[cp]);
  for (uint i=0; i<3; ++i)
  {
    p[i] = x.pi[i];
    n[i] = x.ni[i];
  }
  p[3] = w;

  debugcheck();

  // Indexes to new triangles.
  uint k[3];
  k[0] = cp;
  k[1] = vi.size();
  k[2] = k[1]+1;

  x =           simplexD2linked(p[3],p[1],p[2],n[0],k[1],k[2]);
  vi.push_back( simplexD2linked(p[3],p[2],p[0],n[1],k[2],k[0]) );
  vi.push_back( simplexD2linked(p[3],p[0],p[1],n[2],k[0],k[1]) );

  if (n[1]!=0)
    vi[n[1]].changelink(cp,k[1]);

  if (n[2]!=0)
    vi[n[2]].changelink(cp,k[2]);

  debugcheck();

  for (uint i=0; i<3; ++i)
  {
    if (n[i]==0)
      continue;

    assert(isconnected(n[i],k[i]));
  }

  for (uint i=0; i<3; ++i)
  {
    if (n[i]==0)
      continue;

    minimizer->eval(n[i],k[i]);
  }

  debugcheck();
}

void d3tess::splitmidpoint1D	(	uintc	s,
		uintc	p1
	)

Split the simplex on the 1D boundary in two. p1 is the point opposite the bounary edge.

Definition at line 18 of file d3tess.cpp.

References pt, split1D(), and vi.

Referenced by maxEdgeLength::eval().

{
  assert(s<vi.size());
  assert(p1<pt.size());

  simplexD2linked & S(vi[s]);

  assert(S.piInverseHas(p1)==true);

  uintc j = S.piInverse(p1);

  uintc a = S.pi[(j+1)%3];
  uintc b = S.pi[(j+2)%3];

  uintc n = pt.size();
  pt.push_back( (pt[a]+pt[b])*0.5 );

  split1D(s,p1,n);
}

void d3tess::splitwithline	(	uintc	s,
		uintc	p0,
		uintc	w0,
		uintc	p1,
		uintc	w1
	)

Two points w0 and w1 on the boundary split the triangle. p0 and p1 index the points.

Definition at line 131 of file d3tess.cpp.

References simplexD2linked::piInverseHas().

{
  uintc n0 = vi.size();
  assert(s<n0);

  // Neighboring triangle opposite p0
  uintc neib = vi[s].nifrom(p0);

  // If the first splitting point has no neighbor on the given 
  //   boundary then handle this case. 
  if (neib==0)
  {
    split1D(s,p0,w0);
    if ( vi[s].piInverseHas(p1) )
      split1D(n0,w0,w1);
    else
      split1D(s,w0,w1);

    return;
  }

  // The first split will create 4 new triangles and delete two.

  split1D(s,p0,w0);

  //  The second triangle to be split contains the point p0 but
  //    does not contain the point p1 as one of its points.

  uint k[4];
  k[0] = s;
  k[1] = neib;
  k[2] = n0;
  k[3] = n0+1;

  simplexD2linked *t;
  uint ki;
  for ( uint i=0; i<4; ++i )
  {
    ki=k[i];
    t = & vi[ki];
    if ( t->piInverseHas(p1) == true )
      continue;
    if ( t->piInverseHas(p0) == false )
      continue;

    split1D(ki,w0,w1);

    return;
  }

  assert(false);  // The case should have been handled.  
}

void d3tess::surfaceleft

(

)

Definition at line 898 of file d3tess.cpp.

References virtualtriangle::clockwise(), cp, moveleft(), virtualtriangle::v, vi, and vs.

Referenced by d3fan::eval(), and keyboard().

{
  assert( vi[cp].ni[ vs.v[2] ]==0 );

  if( vi[cp].ni[ vs.v[1] ]==0 )
  {
    vs.clockwise();
    return;
  }
  
  for ( ; moveleft(); );

  vs.clockwise();
}

void d3tess::surfaceright

(

)

Definition at line 883 of file d3tess.cpp.

References virtualtriangle::anticlockwise(), cp, moveright(), virtualtriangle::v, vi, and vs.

Referenced by d3fan::eval(), and keyboard().

{
  assert( vi[cp].ni[ vs.v[2] ]==0 );

  if( vi[cp].ni[ vs.v[0] ]==0 )
  {
    vs.anticlockwise();
    return;
  }
  
  for ( ; moveright(); );

  vs.anticlockwise();
}

bool const d3tess::surfaceviewable

(

uintc

k

)

const

Is the point viewable from vs's base?

Definition at line 399 of file d3tess.cpp.

References cp, halfspaceD2< PT, PD >::isInside(), simplexD2linked::pi, pt, virtualtriangle::v, vi, and vs.

Referenced by d3fan2::eval(), and d3fan::eval().

{
  simplexD2linked const & x(vi[cp]);
  halfspaceD2< pt3, double > h(pt[x.pi[vs.v[1]]],pt[x.pi[vs.v[0]]]);
  return h.isInside(pt[k]);
}

bool const d3tess::valid

(

uintc

k

)

const

Definition at line 742 of file d3tess.cpp.

References vi.

Referenced by debugcheck().

{
  if (k>=vi.size())
    return false;

  if (vi[k].isnull())
    return true;

  // Look at each neighbor for links.
  for (uint i=0, nb; i<3; ++i)
  {
    nb = vi[k].ni[i];
    if (nb==0)
      continue;

    bool res;

    // Each point bordering neighbor must also be one
    // of the neighbors own points.
    for (uint w=0; w<3; ++w)
    {
      if (w==i)
        continue;

      vi[nb].piInverse( res, vi[k].pi[w] );
      if (res==false)
        return false;
    }

    // The neighbor must have a pointer back to k.

    if (vi[nb].niInverseHas(k)==false)
      return false;

/*
    vi[nb].niInverse( res, k );
    if (res==false)
      return false;
*/
  }

  return true;
}

void d3tess::viadd	(	uintc	v0,
		uintc	v1,
		uintc	v2,
		uintc	n0 = 0,
		uintc	n1 = 0,
		uintc	n2 = 0
	)

Definition at line 1062 of file d3tess.cpp.

Referenced by tessinit01(), tessinit02(), and tessinitgeneral().

{ 
  vi.push_back( simplexD2linked(v0,v1,v2,n0,n1,n2) ); 
}

---

Member Data Documentation

uint d3tess::cp

Definition at line 38 of file d3tess.h.

Referenced by boundaryorient(), cpbasemeasure(), cppreserve(), cpsimplex(), cpsimplexfaceget(), cpsimplexfaceset(), writevoronoidiagramobj::draw(), d3fan2::eval(), flip(), movedown(), reset(), searchStats(), serializeInverse(), split2D(), surfaceleft(), surfaceright(), and surfaceviewable().

bool d3tess::debugenable

Definition at line 52 of file d3tess.h.

Referenced by debugcheck(), and main().

d3fan2 d3tess::fan

Definition at line 45 of file d3tess.h.

Referenced by addpoint().

d3minoperator* d3tess::minimizer

Definition at line 50 of file d3tess.h.

Referenced by d3fan2::eval(), d3fan::eval(), minimizerSet(), split2D(), and ~d3tess().

uint d3tess::movecounter

Definition at line 55 of file d3tess.h.

Referenced by searchminimizetowardspoint(), and searchStats().

vector<pt3> d3tess::pt

Definition at line 33 of file d3tess.h.

Referenced by addpoint(), addpointinsidemesh(), addrandompointtomesh(), addrandompointtomeshptvector(), cpbasemeasure(), d3tess(), writemulticolorobj::draw(), writecirclesobj::draw(), writecpcircleobj::draw(), writevoronoidiagramobj::draw(), writecpobj::draw(), writesimplicesobj::draw(), writegridobj::draw(), writewindingobj::draw(), writepointsobj::draw(), writesurfaceobj::draw(), d3mincircle::eval(), d3mincentroid2::eval(), d3mincentroid::eval(), d3minboundary::eval(), d3meshpointreader::eval(), init00(), init02(), initialize(), d3meshpartition::intersection(), isconvex(), d3meshpartition::isInside(), d3meshpartition::isOnBoundary(), d3tesstransform::multiply(), print(), reset(), searchStats(), serializeInverse(), split1D(), split2D(), splitmidpoint1D(), surfaceviewable(), tessinit01(), tessinit02(), tessinitgeneral(), d3tesstransform::transEval(), and d3tesstransform::translate().

vector<simplexD2linked> d3tess::vi

Definition at line 35 of file d3tess.h.

Referenced by boundaryorient(), cpbasemeasure(), cpsimplex(), d3tess(), debugcheck(), writemulticolorobj::draw(), writecirclesobj::draw(), writevoronoidiagramobj::draw(), writecpobj::draw(), writesimplicesobj::draw(), writegridobj::draw(), writewindingobj::draw(), writesurfaceobj::draw(), d3minrecursive::eval(), d3mincircle::eval(), d3mincentroid2::eval(), d3mincentroid::eval(), d3minboundary::eval(), d3fan2::eval(), flip(), init00(), initialize(), d3meshpartition::intersection(), isconnected(), isconvex(), d3meshpartition::isInside(), d3meshpartition::isOnBoundary(), movedown(), print(), removenullsimplexes(), reset(), serializeInverse(), simplexdelete(), simplexswap(), split1D(), split2D(), splitmidpoint1D(), surfaceleft(), surfaceright(), surfaceviewable(), timmingexperiment00(), timmingexperiment01(), and valid().

virtualtriangle d3tess::vs

Definition at line 40 of file d3tess.h.

Referenced by boundaryorient(), cpbasemeasure(), cppreserve(), cpsimplexfaceget(), cpsimplexfaceset(), writevoronoidiagramobj::draw(), writecpvoronoiobj::draw(), writecpobj::draw(), d3fan2::eval(), flip(), keyboard(), movedown(), moveleft(), moveright(), searchminimizetowardspoint(), surfaceleft(), surfaceright(), and surfaceviewable().

---

The documentation for this class was generated from the following files:

• cetessD2/d3tess.h
• cetessD2/d3tess.cpp