Public Member Functions
void	process (Array< Vector3 > &vertexArray, Array< Vector2 > &texCoordArray, Array< Vector3 > &normalArray, Array< Array< int > * > &indexArrayArray, float normAngle, float texRadius, float normRadius)

	WeldHelper (float vertRadius)

Private Member Functions
int	getIndex (const Vector3 &v, const Vector3 &n, const Vector2 &t)

void	updateTriLists (Array< Array< int > * > &indexArrayArray, const Array< Vector3 > &vertexArray, const Array< Vector3 > &normalArray, const Array< Vector2 > &texCoordArray)

void	unroll (const Array< Array< int > * > &indexArrayArray, const Array< Vector3 > &vertexArray, const Array< Vector2 > &texCoordArray, Array< Vector3 > &unrolledVertexArray, Array< Vector2 > &unrolledTexCoordArray)

void	computeFaceNormals (const Array< Vector3 > &vertexArray, Array< Vector3 > &faceNormalArray)

void	smoothNormals (const Array< Point3 > &vertexArray, const Array< Vector3 > &normalArray, Array< Vector3 > &smoothNormalArray)

Private Attributes
PointHashGrid< VNTi >	weldGrid

Array< Vector3 > *	outputVertexArray

Array< Vector3 > *	outputNormalArray

Array< Vector2 > *	outputTexCoordArray

float	vertexWeldRadius

float	normalWeldRadius2

float	texCoordWeldRadius2

float	normalSmoothingAngle

Constructor & Destructor Documentation

G3D::_internal::WeldHelper::WeldHelper ( float vertRadius )

inline

  :
  weldGrid(max(vertRadius, 0.1f), AreaMemoryManager::create()),
  vertexWeldRadius(vertRadius) {
  }

Member Function Documentation

void G3D::_internal::WeldHelper::computeFaceNormals	(	const Array< Vector3 > &	vertexArray,
		Array< Vector3 > &	faceNormalArray
	)

inlineprivate

For every three vertices, compute the face normal and store it three times. Sliver triangles have a zero surface normal, which we will later take to match any surface normal.

  {
 # ifdef VERBOSE
  debugPrintf("WeldHelper::computeFaceNormals\n");
 # endif
 
  debugAssertM(vertexArray.size() % 3 == 0, "Input is not a triangle soup");
  debugAssertM(faceNormalArray.size() == 0, "Output must start empty.");
 
  for (int v = 0; v < vertexArray.size(); v += 3) {
  const Vector3& e0 = vertexArray[v + 1] - vertexArray[v];
  const Vector3& e1 = vertexArray[v + 2] - vertexArray[v];
 
  // Note that the length may be zero in the case of sliver polygons, e.g.,
  // those correcting a T-junction. Scale up by 256 to avoid underflow when
  // multiplying very small edges
  const Vector3& n = (e0.cross(e1 * 256.0f)).directionOrZero();
 
  // Append the normal once per vertex.
  faceNormalArray.append(n, n, n);
  }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

int G3D::_internal::WeldHelper::getIndex	(	const Vector3 &	v,
		const Vector3 &	n,
		const Vector2 &	t
	)

inlineprivate

Returns the index of the vertex in outputVertexArray/outputNormalArray/outputTexCoordArray that is within the global tolerances of v,n,t. If there is no such vertex, adds it to the arrays and returns that index.

Called from updateTriLists().

  {
  PointHashGrid<VNTi>::SphereIterator it = 
  weldGrid.begin(Sphere(v, vertexWeldRadius));
 
  if (n.isZero()) {
  // Don't bother trying to match the surface normal, since this vertex has no surface normal.
  while (it.isValid()) {
  if ((t - it->texCoord).squaredLength() <= texCoordWeldRadius2) {
  // This is the vertex
  return it->index;
  }
  ++it;
  }
  } else {
  while (it.isValid()) {
  if (((n - it->normal).squaredLength() <= normalWeldRadius2) &&
  ((t - it->texCoord).squaredLength() <= texCoordWeldRadius2)) {
  // This is the vertex
  return it->index;
  }
  ++it;
  }
  }
 
  // Note that a sliver triangle processed before its neighbors may reach here
  // with a zero length normal.
 
  // The vertex does not exist. Create it.
  const int i = outputVertexArray->size();
  outputVertexArray->append(v);
  outputNormalArray->append(n);
  outputTexCoordArray->append(t);
 
  // Store in the grid so that it will be remembered.
  weldGrid.insert(VNTi(v, n, t, i));
 
  return i;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

void G3D::_internal::WeldHelper::process	(	Array< Vector3 > &	vertexArray,
		Array< Vector2 > &	texCoordArray,
		Array< Vector3 > &	normalArray,
		Array< Array< int > * > &	indexArrayArray,
		float	normAngle,
		float	texRadius,
		float	normRadius
	)

inline

Algorithm:

Unroll the indexed triangle list into a triangle list, where there are duplicated vertices.
Compute face normals for all triangles, and expand those into the triangle vertices.
At each vertex, average all normals that are within normalSmoothingAngle.
Generate output indexArrayArray. While doing so, merge all vertices where the distance between position, texCoord, and normal is within the thresholds.

  {
 # ifdef VERBOSE
  debugPrintf("WeldHelper::process\n");
 # endif
 
  normalSmoothingAngle = normAngle;
  normalWeldRadius2 = square(normRadius);
  texCoordWeldRadius2 = square(texRadius);
 
  const bool hasTexCoords = (texCoordArray.size() > 0);
 
  if (hasTexCoords) {
  debugAssertM(vertexArray.size() == texCoordArray.size(), 
  "Input arrays are not parallel.");
  }
 
  // Create an area memory manager for fast deallocation
  Array<Vector3> unrolledVertexArray;
  Array<Vector3> unrolledFaceNormalArray;
  Array<Vector3> unrolledSmoothNormalArray;
  Array<Vector2> unrolledTexCoordArray;
 
  unrolledVertexArray.reserve(vertexArray.size());
  unrolledFaceNormalArray.reserve(vertexArray.size());
  unrolledSmoothNormalArray.reserve(vertexArray.size());
  unrolledTexCoordArray.reserve(vertexArray.size());
 
  if (! hasTexCoords) {
  // Generate all zero texture coordinates
  texCoordArray.resize(vertexArray.size());
  }
 
  // Generate a flat (unrolled) triangle list with texture coordinates.
  unroll(indexArrayArray, vertexArray, texCoordArray, 
  unrolledVertexArray, unrolledTexCoordArray);
 
  // Put the output back into the input slots. 
  outputVertexArray = &vertexArray;
  outputNormalArray = &normalArray;
  outputTexCoordArray = &texCoordArray;
  outputVertexArray->fastClear();
  outputNormalArray->fastClear();
  outputTexCoordArray->fastClear();
 
  // For every three vertices, generate their face normal and store it at 
  // each vertex. The output array has the same length as the input.
  computeFaceNormals(unrolledVertexArray, unrolledFaceNormalArray);
 
  // Compute smooth normals at vertices.
  if (unrolledFaceNormalArray.size() > 0) {
  smoothNormals(unrolledVertexArray, unrolledFaceNormalArray, unrolledSmoothNormalArray);
  unrolledFaceNormalArray.clear();
  }
 
  // Regenerate the triangle lists
  updateTriLists(indexArrayArray, unrolledVertexArray, unrolledSmoothNormalArray, unrolledTexCoordArray);
 
  if (! hasTexCoords) {
  // Throw away the generated texCoords
  texCoordArray.resize(0);
  }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

void G3D::_internal::WeldHelper::smoothNormals	(	const Array< Point3 > &	vertexArray,
		const Array< Vector3 > &	normalArray,
		Array< Vector3 > &	smoothNormalArray
	)

inlineprivate

Computes smoothNormalArray, whose elements are those of normalArray averaged with neighbors within the angular cutoff.

  {
  if (normalSmoothingAngle <= 0) {
  smoothNormalArray = normalArray;
  return;
  }
 
 # ifdef VERBOSE
  debugPrintf("WeldHelper::smoothNormals\n");
 # endif
 
  // Create an area memory manager for fast deallocation
  MemoryManager::Ref mm = AreaMemoryManager::create(iRound(sizeof(VN) * normalArray.size() * 1.5));
 
  const float cosThresholdAngle = (float)cos(normalSmoothingAngle);
 
  debugAssert(vertexArray.size() == normalArray.size());
  smoothNormalArray.resize(normalArray.size());
 
  if (vertexWeldRadius == 0) {
  // Look for vertices with the exactly identical normal only
 # ifdef VERBOSE
  debugPrintf("Taking fast path\n");
 # endif
 
  // Maximum expected faces that meet at a vertex
  static const int k = 8;
 
  // Maps vertices to the indices of normals at that vertex
  Table<Point3, SmallArray<Vector3, k> > normalTable;
  for (int v = 0; v < vertexArray.size(); ++v) {
  bool ignore = false;
  SmallArray<Vector3, k>& list = normalTable.getCreate(vertexArray[v], ignore);
  list.append(normalArray[v]);
  }
 
  for (int v = 0; v < vertexArray.size(); ++v) {
  Vector3 sum;
 
  const Vector3& original = normalArray[v];
 
  const SmallArray<Vector3, k>& list = normalTable[vertexArray[v]];
 
  for (int i = 0; i < list.size(); ++i) {
  const Vector3& N = list[i];
  const float cosAngle = N.dot(original);
 
  if (cosAngle > cosThresholdAngle) {
  // This normal is close enough to consider. Avoid underflow by scaling up
  sum += (N * 256.0f);
  }
  }
 
  const Vector3& average = sum.directionOrZero();
 
  const bool indeterminate = average.isZero();
  // Never "smooth" a normal so far that it points backwards
  const bool backFacing = original.dot(average) < 0;
  
  if (indeterminate || backFacing) {
  // Revert to the face normal
  smoothNormalArray[v] = original;
  } else {
  // Average available normals
  smoothNormalArray[v] = average;
  }
  }
 
  } else {
  // Non-zero vertex normal welding
 # ifdef VERBOSE
  debugPrintf("Taking slower weld path because vertexWeldRadius = %f\n",
  vertexWeldRadius);
 # endif
 
  // Compute a hash grid so that we can find neighbors quickly.
  alwaysAssertM(vertexWeldRadius > 0, "Cannot smooth with zero vertex weld radius");
  PointHashGrid<VN> grid(vertexWeldRadius, mm);
  for (int v = 0; v < normalArray.size(); ++v) {
  grid.insert(VN(vertexArray[v], normalArray[v]));
  }
  
  // OPT: this step could be done on multiple threads
  for (int v = 0; v < normalArray.size(); ++v) { 
  // Compute the sum of all nearby normals within the cutoff angle.
  // Search within the vertexWeldRadius, since those are the vertices
  // that will collapse to the same point.
  PointHashGrid<VN>::SphereIterator it = 
  grid.begin(Sphere(vertexArray[v], vertexWeldRadius));
  
  Vector3 sum;
  
  const Vector3& original = normalArray[v];
  while (it.isValid()) {
  const Vector3& N = it->normal;
  const float cosAngle = N.dot(original);
  
  if (cosAngle > cosThresholdAngle) {
  // This normal is close enough to consider. Avoid underflow by scaling up
  sum += (N * 256.0f);
  }
  ++it;
  }
  
  const Vector3& average = sum.directionOrZero();
  
  const bool indeterminate = average.isZero();
  // Never "smooth" a normal so far that it points backwards
  const bool backFacing = original.dot(average) < 0;
  
  if (indeterminate || backFacing) {
  // Revert to the face normal
  smoothNormalArray[v] = original;
  } else {
  // Average available normals
  smoothNormalArray[v] = average;
  }
  }
  }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

void G3D::_internal::WeldHelper::unroll	(	const Array< Array< int > * > &	indexArrayArray,
		const Array< Vector3 > &	vertexArray,
		const Array< Vector2 > &	texCoordArray,
		Array< Vector3 > &	unrolledVertexArray,
		Array< Vector2 > &	unrolledTexCoordArray
	)

inlineprivate

Expands the indexed triangle lists into a triangle list.

Called from process()

  {
 
 # ifdef VERBOSE
  debugPrintf("WeldHelper::unroll\n");
 # endif
  
  int numTriLists = indexArrayArray.size();
  for (int t = 0; t < numTriLists; ++t) {
  if (indexArrayArray[t] != NULL) {
  const Array<int>& triList = *(indexArrayArray[t]);
  for (int v = 0; v < triList.size(); ++v) {
  int i = triList[v];
  unrolledVertexArray.append(vertexArray[i]);
  unrolledTexCoordArray.append(texCoordArray[i]);
  }
  }
  }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

void G3D::_internal::WeldHelper::updateTriLists	(	Array< Array< int > * > &	indexArrayArray,
		const Array< Vector3 > &	vertexArray,
		const Array< Vector3 > &	normalArray,
		const Array< Vector2 > &	texCoordArray
	)

inlineprivate

Updates each indexArray to refer to vertices in the outputVertexArray.

Called from process()

  {
  
 # ifdef VERBOSE
  debugPrintf("WeldHelper::updateTriLists\n");
 # endif
  
  // Compute a hash grid so that we can find neighbors quickly.
  // It begins empty and is extended as the tri lists are iterated
  // through.
  weldGrid.clear();
 
  // Process all triLists
  int numTriLists = indexArrayArray.size();
  int u = 0;
  for (int t = 0; t < numTriLists; ++t) {
  if (indexArrayArray[t] != NULL) {
  Array<int>& triList = *(indexArrayArray[t]);
 
  // For all vertices in this list
  for (int v = 0; v < triList.size(); ++v) {
  // This vertex mapped to u in the flatVertexArray
  triList[v] = getIndex(vertexArray[u], normalArray[u], texCoordArray[u]);
 
  /*
  # ifdef G3D_DEBUG
  {
  int i = triList[v];
  Vector3 N = normalArray[i];
  debugAssertM(N.length() > 0.9f, "Produced non-unit normal");
  }
  # endif
  */
  ++u;
  }
  }
  }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

float G3D::_internal::WeldHelper::normalSmoothingAngle

private

float G3D::_internal::WeldHelper::normalWeldRadius2

private

Squared radius allowed for welding similar normals.

Array<Vector3>* G3D::_internal::WeldHelper::outputNormalArray

private

Array<Vector2>* G3D::_internal::WeldHelper::outputTexCoordArray

private

Array<Vector3>* G3D::_internal::WeldHelper::outputVertexArray

private

float G3D::_internal::WeldHelper::texCoordWeldRadius2

private

float G3D::_internal::WeldHelper::vertexWeldRadius

private

PointHashGrid<VNTi> G3D::_internal::WeldHelper::weldGrid

private

Used by getIndex and updateTriLists. Deallocating this is slow.

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

dep/g3dlite/source/Welder.cpp

Public Member Functions

Private Member Functions

Private Attributes

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation