What's the meanning of front/back vertices?

[YoungRainy]

I start a new issue for asking a new question.
In "SphericalGeometry.inl", line 582, The code is like this:

////////////////////////////////
// SphericalGeometry::Polygon //
////////////////////////////////
template< class Real > template< class VertexData >
void SphericalGeometry::Polygon< Real >::_split( Point3D< Real > pNormal , Real pOffset , int pIdx , Polygon &back , Polygon &front , std::vector< Point3D< Real > >& vertices , std::vector< PlanarSources > &pSources , std::vector< VertexData >* vData , std::unordered_map< unsigned long long , int >& vMap ) const
{
	std::vector< Real > values( _vertices.size() );
	bool frontSet = false , backSet = false;
	front.sourceID = back.sourceID = sourceID;

	// Evaluate the plane's function at the vertices and mark if front/back vertices have been found
	for( int i=0 ; i<size() ; i++ )
	{
		values[i] = Point3D< Real >::Dot( vertices[ _vertices[i] ] , pNormal ) - pOffset;

		// Don't split on edges near the pole
		if( pIdx>=0 && pSources[ _vertices[i] ].full() ) values[i] = 0;

		backSet |= ( values[i]<0 ) , frontSet |= ( values[i]>0 );
	}

	// If no vertices are in front or no vertices are behind, life is easy
	if( !frontSet ){  back._vertices = _vertices ;  back.mass = mass ; return; }
	if( !backSet  ){ front._vertices = _vertices ; front.mass = mass ; return; }

	enum
	{
		PLANE_STATE_BACK ,
		PLANE_STATE_FRONT ,
		PLANE_STATE_BOUNDARY
	};
	auto State = []( Real value )
	{
		if     ( value<0 ) return PLANE_STATE_BACK;
		else if( value>0 ) return PLANE_STATE_FRONT;
		else               return PLANE_STATE_BOUNDARY;
	};
	struct _VertexIndex
	{
		int idx , state;
		_VertexIndex( int i , int s ) : idx(i) , state(s) {}
	};

	// Compute the indices of the refined polygons and their associated states
	std::vector< _VertexIndex > vertexIndices;
	for( int i0=0 ; i0<size() ; i0++ )
	{
		int i1 = (i0+1)%size();
		vertexIndices.push_back( _VertexIndex( _vertices[i0] , State( values[i0] ) ) );
		// If the edge crosses the plane, we need to create a new vertex
		if( values[i0]*values[i1]<0 )
		{
			int vIdx;
			unsigned long long key = Key( _vertices[i0] , _vertices[i1] );
			if( vMap.find( key )==vMap.end() )
			{
				Real t = values[i0] / ( values[i0] - values[i1] );
				Point3D< Real > v = vertices[ _vertices[i1] ]*t + vertices[ _vertices[i0] ]*(Real)(1.-t);
				v /= (Real)Length( v );
				vIdx = (int)vertices.size();
				vertices.push_back( v );
				if( vData ) vData->push_back( (*vData)[ _vertices[i1] ]*t + (*vData)[ _vertices[i0] ]*(Real)(1.-t) );
				{
					PlanarSources ps;
					ps.addIndex( PlanarSources::SharedIndex( pSources[ _vertices[i0] ] , pSources[ _vertices[i1] ] ) );
					ps.addIndex( pIdx );
					pSources.push_back( ps );
				}
				vMap[key] = vIdx;
			}
			else vIdx = vMap[key];
			vertexIndices.push_back( _VertexIndex( vIdx , PLANE_STATE_BOUNDARY ) );
		}
	}

	for( int i=0 ; i<vertexIndices.size() ; i++ )
	{
		if( vertexIndices[i].state!=PLANE_STATE_BACK ) front._vertices.push_back( vertexIndices[i].idx );
		if( vertexIndices[i].state!=PLANE_STATE_FRONT ) back._vertices.push_back( vertexIndices[i].idx );
	}

	Real a0 = back.area( vertices ) , a1 = front.area( vertices );
	Real a = a0 + a1;
	if( a ) a0 /= a , a1 /= a;
	else a0 = a1 = (Real)1./2;
	back.mass = mass * a0 , front.mass = mass * a1;
}

I believed this function is used to calculate the vertices when the triangle mesh intersects the grid.
But I don't get the meaning of the "sourceID", and what's the states of "front, back, or boundary"? Does it mean the direction of the plane? if it is, the boundary means the vertice is on the boundary of the plane?

[YoungRainy]

Also, in "SphericalGeometry.h" file, line 167, the struct "PlannarSources",
The index is repeated twice, but this index is shared with?

Thank you, I am new for this area. it would be very grateful if you can help me with this.

[mkazhdan]

sourceID is the index of the triangle that is being intersected against the grid.
The clipping is done by intersecting the triangle with the planes bounding the sides of the cell.
For each vertex of the input polygon, we determine if it's in front of, behind, or on the clipping plane.

Not sure I follow the question about PlanarSources.

[YoungRainy]

Thank you for your patience.
Here is part of the class "Polygon"

	template< class Real >
	class Polygon
	{
	public:
		struct PlanarSources
		{
			int idx[2];
			PlanarSources( void ){ idx[0] = idx[1] = -1; }
			static int SharedIndex( const PlanarSources &ps1 , const PlanarSources &ps2 )
			{
				if( ps1.idx[0]>=0 )
					if( ps1.idx[0]==ps2.idx[0] || ps1.idx[0]==ps2.idx[1] ) return ps1.idx[0];
					else if( ps1.idx[1]>=0 ) if( ps1.idx[1]==ps2.idx[0] || ps1.idx[1]==ps2.idx[1] ) return ps1.idx[1];
					return -1;
			}
			void addIndex( int i )
			{
				if     ( idx[0]==-1 ) idx[0] = i;
				else if( idx[1]==-1 ) idx[1] = i;
				else if( i>=0 ) fprintf( stderr , "[WARNING] PlanarSources::addIndex: both indices assigned: %d %d <- %d\n" , idx[0] , idx[1] , i );
			}
			bool full( void ) const { return idx[1]>=0; }
		};

as you can see, in the struct, PlanarSources,
int idx[2]
with the function addIndex(int i), idx[0] == i , after it is called the first time, then idx[1] = i, then the function full will be true? This is where I am confused, and the sharedIndex ?

[mkazhdan]

After it's called the first time, idx[0]=i, idx[1]=-1 => full() = false
After it's called the second time, idx[1]=i -> full() = true
The point is that when you have a vertex on a clipped triangle it can be one of three cases:

1. It's an original vertex of the triangle.
2. It was obtained by intersecting an edge of the triangle with a plane.
3. It was obtained by intersecting an edge of the triangle with two planes.
   The last case is a singular case, but happens precisely at the poles.
   We use the PlanarSources data structures to avoid splitting an edge when one of its vertices is at the pole. (Otherwise, numerical imprecision could cause the code to believe the edge should be split.)

[YoungRainy]

Thank you so much. I am going to read more now.

[YoungRainy]

So, here, the PlanarSources is used to describe the vertices on the triangle.

As in the above image, the blue points are PlanarSources, the SourceID is the index of the black triangle, The "Polygon" also means this triangle? is it right?

[YoungRainy]

But in the class "Polygon", it has properity,

public:
int sourceID, theta, phi;

"theta" and "phi" , they are all singular, which is conflict with what I said above.
so, i am lost.

[mkazhdan]

Singular?
In the image, you are missing a bunch of blue vertices -- the ones that are the vertices of the lattice with the triangle. (These will have two planar sources. Most of the ones you've marked have only one. The original vertices gave zero.)

[YoungRainy]

I mean:
here, the variable int theta, phi,, is not vector<int> thetas, phis.

[mkazhdan]

For a given clipped polygon, (theta,phi) gives the index of the spherical cell in which the clipped polygon resides.