// Aqsis
// Copyright (C) 1997 - 2001, Paul C. Gregory
//
// Contact: pgregory@aqsis.org
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU 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
// General Public License for more details.
//
// You should have received a copy of the GNU 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
/** \file
\brief Implements classes for storing mesh topology information..
\author Paul C. Gregory (pgregory@aqsis.org)
*/
#include "lath.h"
namespace Aqsis {
CqObjectPool CqLath::m_thePool;
//------------------------------------------------------------------------------
/**
* Get the lath counter clockwise about the facet.
* Get a pointer to the next lath in a counter clockwise direction about the
* associated facet, where the associated edge is a boundary edge.
* @return Pointer to the lath.
*/
CqLath* CqLath::ccfBoundary() const
{
// The associated edge is boundary, we will need to search backwards.
CqLath* pLdash=cf();
while(1)
{
CqLath* temp = pLdash->cf();
if(this == temp || NULL == temp)
break;
pLdash=temp;
}
// while(this != pLdash->cf() && NULL != pLdash->cf())
// pLdash=pLdash->cf();
assert(this == pLdash->cf());
return(pLdash);
}
//------------------------------------------------------------------------------
/**
* Get the edges surrounding a facet.
* Get a list of laths representing the esges making up a facet.
*
* @return Pointer to an array of lath pointers.
*/
void CqLath::Qfe(std::vector& Result)
{
TqInt len = 1;
CqLath* pNext = cf();
CqLath* pNexta = pNext;
while(this != pNext)
{
assert(NULL != pNext);
len++;
pNext = pNext->cf();
}
Result.resize(len);
// Laths representing the edges of the associated facet are obtained by following
// clockwise links around the face.
CqLath *pTmpLath = this;
Result[0] = pTmpLath;
TqInt index = 1;
while(this != pNexta)
{
Result[index++] = pNexta;
pNexta = pNexta->cf();
}
}
//------------------------------------------------------------------------------
/**
* Get the edges emanating from a vertex.
* Get a list of laths representing the edges which emanate from the vertex
* this lath represents.
*
* @return Pointer to an array of lath pointers.
*/
void CqLath::Qve(std::vector& Result)
{
TqInt len = cQve();
CqLath* pNext = cv();
CqLath* pLast = this;
Result.resize(len);
TqInt index = 0;
// Laths representing the edges that radiate from the associated vertex are obtained by
// following the clockwise vertex links around the vertex.
CqLath *pTmpLath = this;
Result[index++] = pTmpLath;
while(NULL != pNext && this != pNext)
{
Result[index++] = pNext;
pLast = pNext;
pNext = pNext->cv();
}
// If we hit a boundary, add the ec of this boundary edge and start again going backwards.
// @warning Adding ccf for the boundary edge means that the lath represents a different vertex.
if(NULL == pNext)
{
pLast = this;
pNext = ccv();
// We know we are going to hit a boundary in this direction as well so we can just look for that
// case as a terminator.
while(NULL != pNext)
{
Result[index++] = pNext;
pLast = pNext;
pNext = pNext->ccv();
}
// We have hit the boundary going the other way, so add the ccf of this boundary edge.
Result[index++] = pLast->cf();
}
}
//------------------------------------------------------------------------------
/**
* Get the vertices emanating from this vertex.
* Get a list of laths representing the vertices emanating from the vertex
* this lath represents.
*
* @return Pointer to an array of lath pointers.
*/
void CqLath::Qvv(std::vector& Result)
{
Qve(Result);
// We can get the laths for the vertices surrounding a vertex by getting the cf() for each
// lath in Qev. Note we must check first if the lath in Qve represents the same vertex as this
// as if there is a boundary case, the lath on the clockwise boundary will already point to the
// opposite vertex.
for(std::vector::iterator iLath = Result.begin(); iLath!=Result.end(); iLath++)
{
if((*iLath)->VertexIndex() == VertexIndex())
(*iLath) = (*iLath)->ccf();
}
}
//------------------------------------------------------------------------------
/**
* Get the facets which share this vertex.
* Get a list of laths which represent the facets which share the vertex this
* lath represents.
*
* @return Pointer to an array of lath pointers.
*/
void CqLath::Qvf(std::vector& Result)
{
TqInt len = cQvf();
CqLath* pNext = cv();
Result.resize(len);
TqInt index = 0;
// Laths representing the edges that radiate from the associated vertex are obtained by
// following the clockwise vertex links around the vertex.
CqLath *pTmpLath = this;
Result[index++] = pTmpLath;
while(NULL != pNext && this != pNext)
{
Result[index++] = pNext;
pNext = pNext->cv();
}
// If we hit a boundary, start again going backwards.
if(NULL == pNext)
{
pNext = ccv();
// We know we are going to hit a boundary in this direction as well so we can just look for that
// case as a terminator.
while(NULL != pNext)
{
Result[index++] = pNext;
pNext = pNext->ccv();
}
}
}
//------------------------------------------------------------------------------
/**
* Get the edges emanating from this edge.
* Get a list of laths which represent the edges which share a vertex with
* the edge this lath represents.
*
* @return Pointer to an array of lath pointers.
*/
void CqLath::Qee(std::vector& Result)
{
Result.clear();
std::vector ResQve1;
Qve(ResQve1);
std::vector ResQve2;
ccf()->Qve(ResQve2);
// The laths representing the edges radiating from the two vertices of the edge this lath represents
// can be implemented by taking the union of Qve for this and cf() and removing the duplicate cf() if
// it exists.
Result.swap(ResQve1);
//Result.insert(Result.end(), ResQve1.begin(), ResQve1.end());
std::vector::iterator iLath;
TqInt len2 = 0;
for(iLath = ResQve2.begin(); iLath!=ResQve2.end(); iLath++)
{
if(ec() != (*iLath) && this != (*iLath))
len2++;
}
TqInt index = Result.size();
Result.resize( Result.size() + len2 );
for(iLath = ResQve2.begin(); iLath!=ResQve2.end(); iLath++)
{
if(ec() != (*iLath) && this != (*iLath))
Result[index++] = (*iLath);
}
}
//------------------------------------------------------------------------------
/**
* Get the facets which surround this facet.
* Get a list of laths which represent the faces which share either a vertex
* or an edge with the facet this lath represents.
*
* @return Pointer to an array of lath pointers.
*/
void CqLath::Qff(std::vector& Result)
{
std::vector ResQfe;
Qfe(ResQfe);
// The laths representing the edges radiating from the two vertices of the edge this lath represents
// can be implemented by taking the union of Qve for this and cf() and removing the duplicate ec() if
// it exists.
std::vector::iterator iLath;
TqInt len = 0;
for(iLath = ResQfe.begin(); iLath!=ResQfe.end(); iLath++)
len += (*iLath)->cQve();
Result.resize(0);
Result.reserve(len);
for(iLath = ResQfe.begin(); iLath!=ResQfe.end(); ++iLath)
{
std::vector ResQev;
(*iLath)->Qve(ResQev);
std::vector::iterator iEdge;
for(iEdge = ResQev.begin(); iEdge!=ResQev.end(); ++iEdge)
{
CqLath* pNew = (*iEdge);
// Search for the new candidate by traversing the cf lists for all laths currrently in the
// result list.
bool fValid = true;
std::vector::iterator iCurr;
for(iCurr = Result.begin(); iCurr!=Result.end() && fValid; ++iCurr)
{
CqLath* pVisited =(*iCurr);
CqLath* pStart = pVisited;
do
{
if(pVisited == pNew)
{
fValid=false;
break;
}
pVisited = pVisited->cf();
}
while(pVisited != pStart);
}
if(fValid)
Result.push_back(pNew);
}
}
}
//------------------------------------------------------------------------------
/**
* Get the edges surrounding a facet.
* Get a list of laths representing the esges making up a facet.
*
* @return Pointer to an array of lath pointers.
*/
void CqLath::Qfe(std::vector& Result) const
{
TqInt len = 1;
const CqLath* pNext = cf();
const CqLath* pNexta = pNext;
while(this != pNext)
{
assert(NULL != pNext);
len++;
pNext = pNext->cf();
}
Result.resize(len);
// Laths representing the edges of the associated facet are obtained by following
// clockwise links around the face.
const CqLath *pTmpLath = this;
Result[0] = pTmpLath;
TqInt index = 1;
while(this != pNexta)
{
Result[index++] = pNexta;
pNexta = pNexta->cf();
}
}
//------------------------------------------------------------------------------
/**
* Get the edges emanating from a vertex.
* Get a list of laths representing the edges which emanate from the vertex
* this lath represents.
*
* @return Pointer to an array of lath pointers.
*/
void CqLath::Qve(std::vector& Result) const
{
TqInt len = cQve();
const CqLath* pNext = cv();
const CqLath* pLast = this;
Result.resize(len);
TqInt index = 0;
// Laths representing the edges that radiate from the associated vertex are obtained by
// following the clockwise vertex links around the vertex.
const CqLath *pTmpLath = this;
Result[index++] = pTmpLath;
while(NULL != pNext && this != pNext)
{
Result[index++] = pNext;
pLast = pNext;
pNext = pNext->cv();
}
// If we hit a boundary, add the ec of this boundary edge and start again going backwards.
// @warning Adding ccf for the boundary edge means that the lath represents a different vertex.
if(NULL == pNext)
{
pLast = this;
pNext = ccv();
// We know we are going to hit a boundary in this direction as well so we can just look for that
// case as a terminator.
while(NULL != pNext)
{
Result[index++] = pNext;
pLast = pNext;
pNext = pNext->ccv();
}
// We have hit the boundary going the other way, so add the ccf of this boundary edge.
Result[index++] = pLast->cf();
}
}
//------------------------------------------------------------------------------
/**
* Get the vertices emanating from this vertex.
* Get a list of laths representing the vertices emanating from the vertex
* this lath represents.
*
* @return Pointer to an array of lath pointers.
*/
void CqLath::Qvv(std::vector& Result) const
{
Qve(Result);
// We can get the laths for the vertices surrounding a vertex by getting the cf() for each
// lath in Qev. Note we must check first if the lath in Qve represents the same vertex as this
// as if there is a boundary case, the lath on the clockwise boundary will already point to the
// opposite vertex.
for(std::vector::iterator iLath = Result.begin(); iLath!=Result.end(); iLath++)
{
if((*iLath)->VertexIndex() == VertexIndex())
(*iLath) = (*iLath)->ccf();
}
}
//------------------------------------------------------------------------------
/**
* Get the facets which share this vertex.
* Get a list of laths which represent the facets which share the vertex this
* lath represents.
*
* @return Pointer to an array of lath pointers.
*/
void CqLath::Qvf(std::vector& Result) const
{
TqInt len = cQvf();
const CqLath* pNext = cv();
Result.resize(len);
TqInt index = 0;
// Laths representing the edges that radiate from the associated vertex are obtained by
// following the clockwise vertex links around the vertex.
const CqLath *pTmpLath = this;
Result[index++] = pTmpLath;
while(NULL != pNext && this != pNext)
{
Result[index++] = pNext;
pNext = pNext->cv();
}
// If we hit a boundary, start again going backwards.
if(NULL == pNext)
{
pNext = ccv();
// We know we are going to hit a boundary in this direction as well so we can just look for that
// case as a terminator.
while(NULL != pNext)
{
Result[index++] = pNext;
pNext = pNext->ccv();
}
}
}
//------------------------------------------------------------------------------
/**
* Get the edges emanating from this edge.
* Get a list of laths which represent the edges which share a vertex with
* the edge this lath represents.
*
* @return Pointer to an array of lath pointers.
*/
void CqLath::Qee(std::vector& Result) const
{
Result.clear();
std::vector ResQve1;
Qve(ResQve1);
std::vector ResQve2;
ccf()->Qve(ResQve2);
// The laths representing the edges radiating from the two vertices of the edge this lath represents
// can be implemented by taking the union of Qve for this and cf() and removing the duplicate cf() if
// it exists.
Result.swap(ResQve1);
//Result.insert(Result.end(), ResQve1.begin(), ResQve1.end());
std::vector::iterator iLath;
TqInt len2 = 0;
for(iLath = ResQve2.begin(); iLath!=ResQve2.end(); iLath++)
{
if(ec() != (*iLath) && this != (*iLath))
len2++;
}
TqInt index = Result.size();
Result.resize( Result.size() + len2 );
for(iLath = ResQve2.begin(); iLath!=ResQve2.end(); iLath++)
{
if(ec() != (*iLath) && this != (*iLath))
Result[index++] = (*iLath);
}
}
//------------------------------------------------------------------------------
/**
* Get the facets which surround this facet.
* Get a list of laths which represent the faces which share either a vertex
* or an edge with the facet this lath represents.
*
* @return Pointer to an array of lath pointers.
*/
void CqLath::Qff(std::vector& Result) const
{
std::vector ResQfe;
Qfe(ResQfe);
// The laths representing the edges radiating from the two vertices of the edge this lath represents
// can be implemented by taking the union of Qve for this and cf() and removing the duplicate ec() if
// it exists.
std::vector::iterator iLath;
TqInt len = 0;
for(iLath = ResQfe.begin(); iLath!=ResQfe.end(); iLath++)
len += (*iLath)->cQve();
Result.resize(0);
Result.reserve(len);
for(iLath = ResQfe.begin(); iLath!=ResQfe.end(); ++iLath)
{
std::vector ResQev;
(*iLath)->Qve(ResQev);
std::vector::iterator iEdge;
for(iEdge = ResQev.begin(); iEdge!=ResQev.end(); ++iEdge)
{
const CqLath* pNew = (*iEdge);
// Search for the new candidate by traversing the cf lists for all laths currrently in the
// result list.
bool fValid = true;
std::vector::iterator iCurr;
for(iCurr = Result.begin(); iCurr!=Result.end() && fValid; ++iCurr)
{
const CqLath* pVisited =(*iCurr);
const CqLath* pStart = pVisited;
do
{
if(pVisited == pNew)
{
fValid=false;
break;
}
pVisited = pVisited->cf();
}
while(pVisited != pStart);
}
if(fValid)
Result.push_back(pNew);
}
}
}
//------------------------------------------------------------------------------
/**
* Get the number of vertices surrounding a facet.
* Get a count of laths representing the vertices which make up the facet this
* lath represents.
*
* @return Count of laths.
*/
TqInt CqLath::cQfv() const
{
// Laths representing the edges of the associated facet are obtained by following
// clockwise links around the face.
TqInt c = 1; // Start with this one.
CqLath* pNext = cf();
while(this != pNext)
{
assert(NULL != pNext);
c++;
pNext = pNext->cf();
}
return( c );
}
//------------------------------------------------------------------------------
/**
* Get the number of vertices emanating from this vertex.
* Get a count of laths representing the vertices emanating from the vertex
* this lath represents.
*
* @return Count of laths.
*/
TqInt CqLath::cQvv() const
{
TqInt c = 1; // Start with this
// Laths representing the edges that radiate from the associated vertex are obtained by
// following the clockwise vertex links around the vertex.
CqLath* pNext = cv();
const CqLath* pLast = this;
while(NULL != pNext && this != pNext)
{
c++;
pLast = pNext;
pNext = pNext->cv();
}
// If we hit a boundary, add the ec of this boundary edge and start again going backwards.
// @warning Adding ccf for the boundary edge means that the lath represents a different vertex.
if(NULL == pNext)
{
pLast = this;
pNext = ccv();
// We know we are going to hit a boundary in this direction as well so we can just look for that
// case as a terminator.
while(NULL != pNext)
{
assert( pNext != this );
c++;
pLast = pNext;
pNext = pNext->ccv();
}
// We have hit the boundary going the other way, so add the ccf of this boundary edge.
c++;
}
return( c );
}
//------------------------------------------------------------------------------
/**
* Get the edges emanating from a vertex.
* Get a list of laths representing the edges which emanate from the vertex
* this lath represents.
*
* @return Pointer to an array of lath pointers.
*/
TqInt CqLath::cQve() const
{
TqInt len = 1;
CqLath* pNext = cv();
const CqLath* pLast = this;
while(NULL != pNext && this != pNext)
{
len++;
pLast = pNext;
pNext = pNext->cv();
}
// If we hit a boundary, add the ec of this boundary edge and start again going backwards.
// @warning Adding ccf for the boundary edge means that the lath represents a different vertex.
if(NULL == pNext)
{
pLast = this;
pNext = ccv();
// We know we are going to hit a boundary in this direction as well so we can just look for that
// case as a terminator.
while(NULL != pNext)
{
assert( pNext != this );
len++;
pLast = pNext;
pNext = pNext->ccv();
}
// We have hit the boundary going the other way, so add the ccf of this boundary edge.
len++;
}
return(len);
}
//------------------------------------------------------------------------------
/**
* Get the count of facets which share this vertex.
* Get a count of laths which represent the facets which share the vertex this
* lath represents.
*
* @return Pointer to an array of lath pointers.
*/
TqInt CqLath::cQvf() const
{
TqInt len = 1;
CqLath* pNext = cv();
while(NULL != pNext && this != pNext)
{
len++;
pNext = pNext->cv();
}
// If we hit a boundary, start again going backwards.
if(NULL == pNext)
{
pNext = ccv();
// We know we are going to hit a boundary in this direction as well so we can just look for that
// case as a terminator.
while(NULL != pNext)
{
len++;
pNext = pNext->ccv();
}
}
return(len);
}
} // namespace Aqsis