Jump to content

  • Log In with Google      Sign In   
  • Create Account


Aressera

Member Since 25 Mar 2007
Offline Last Active Yesterday, 06:15 PM

#5165085 Bone parent indices to linked list

Posted by Aressera on 06 July 2014 - 11:58 AM

I don't think it is necessary to store any explicit hierarchy of the bones - In my animation system I just have a list of bones, and each bone has an associated parent bone index (in the list). This stores the hierarchy implicitly. Then, when computing the final matrices for each bone, I just iterate through the list and lazily compute the concatenated object-space matrices of each bone (and any parent bones, if they have not yet been computed). There doesn't seem to be any reason to store the skeleton hierarchy in a traditional tree structure.




#5163493 The doubt of a bounding sphere as the bounding volume

Posted by Aressera on 28 June 2014 - 02:38 PM

There is rarely one bounding volume to fit them all. You should probably have separate bounding volumes for physics and graphics, since the needs for both are different. The graphics bounding volume can be a little looser because it's only used for culling, while the physics BV should tightly bound the visual representation. You may also use a series of progressively more detailed representations: first test against a bounding sphere, then versus convex hull of the mesh, then versus the actual mesh itself. This avoids checking the detailed representation more often than necessary.




#5153228 High Speed Quadric Mesh Simplification without problems (Resolved)

Posted by Aressera on 13 May 2014 - 12:01 AM

That's why you need to update the error for neighboring edges after each collapse and re-sort the edge collapse list at each iteration after adding newly created edges - there are collapses that you could still make but you don't know about them because they're not at the top of the heap, or they correspond to new edges that weren't in the original mesh, and therefore don't even exist in the collapse list.

 

Here's my working edge collapse code (won't compile as-is), but it's well-commented and should give you an idea of how to handle the resorting efficiently.


class FatVertex
{
	public:
		
		inline FatVertex( const Vector3& newPosition )
			:	position( newPosition ),
				finalIndex( 0 ),
				collapsed( false ),
				checked( false )
		{
		}
		
		Vector3 position;
		
		/// A list of the indices of the vertices that share an edge with vertex.
		ShortArrayList<Index,4> vertexNeighbors;
		
		/// A list of the indices of the triangles that use this vertex.
		ShortArrayList<Index,6> triangleNeighbors;
		
		/// The final index of this vertex in the output list.
		Index finalIndex;
		
		/// A boolean value indicating whether or not this vertex has been collapsed.
		Bool collapsed;
		
		/// A boolean value indicating whether or not this vertex has been collapsed.
		Bool checked;
		
};




class FatTriangle
{
	public:
		
		inline FatTriangle( Index newV0, Index newV1, Index newV2, const Plane3& newPlane )
			:	plane( newPlane ),
				finalIndex( 0 ),
				collapsed( false )
		{
			v[0] = newV0;
			v[1] = newV1;
			v[2] = newV2;
		}
		
		inline Bool hasVertex( const Index vertexIndex ) const
		{
			return v[0] == vertexIndex || v[1] == vertexIndex || v[2] == vertexIndex;
		}
		
		inline Bool getVertexIndex( const Index vertexIndex, Index& index ) const
		{
			for ( Index i = 0; i < 3; i++ )
			{
				if ( v[i] == vertexIndex )
				{
					index = i;
					return true;
				}
			}
			return false;
		}
		
		inline Bool replaceVertex( Index replaceIndex, Index newIndex )
		{
			if ( v[0] == replaceIndex )
				v[0] = newIndex;
			else if ( v[1] == replaceIndex )
				v[1] = newIndex;
			else if ( v[2] == replaceIndex )
				v[2] = newIndex;
			else
				return false;
			
			return true;
		}
		
		
		/// The indices of the vertices of this triangle.
		Index v[3];
		
		/// The plane equation for this triangle.
		Plane3 plane;
		
		/// The final index of this triangle in the output list.
		Index finalIndex;
		
		/// A boolean value indicating whether or not this triangle has been collapsed.
		Bool collapsed;
		
		
};




class EdgeCollapse
{
	public:
		
		inline EdgeCollapse( Index newV1, Index newV2, const Vector3& newTarget, Real newCost )
			:	v1( newV1 ),
				v2( newV2 ),
				target( newTarget ),
				cost( newCost ),
				queueIndex( math::max<Index>() )
		{
		}
		
		/// Return whether or not this edge collapse is the same as another.
		inline Bool operator == ( const EdgeCollapse& other ) const
		{
			return (v1 == other.v1 && v2 == other.v2) || (v1 == other.v2 && v2 == other.v1);
		}
		
		Index v1;
		Index v2;
		
		Vector3 target;
		Real cost;
		
		/// The index position of this edge collapse in the edge collapse queue.
		Index queueIndex;
		
};




class EdgeCollapseReference
{
	public:
		
		inline EdgeCollapseReference( EdgeCollapse* newCollapse )
			:	collapse( newCollapse )
		{
		}
		
		/// Return whether or not this edge collapse is the same as another.
		inline Bool operator == ( const EdgeCollapseReference& other ) const
		{
			return collapse == other.collapse;
		}
		
		/// Return whether or not this edge collapse has a lower cost than another.
		inline Bool operator < ( const EdgeCollapseReference& other ) const
		{
			return collapse->cost > other.collapse->cost;
		}
		
		inline Real getCost() const
		{
			return collapse->cost;
		}
		
		EdgeCollapse* collapse;
		
		
};




class EdgeCollapseQueue
{
	public:
		
		inline EdgeCollapseQueue( Size newCapacity )
			:	array( util::allocate<EdgeCollapseReference>( newCapacity ) ),
				capacity( newCapacity ),
				numCollapses( 0 )
		{
		}
		
		
		inline ~EdgeCollapseQueue()
		{
			this->clear();
			util::deallocate( array );
		}
		
		
		inline void add( const EdgeCollapseReference& newCollapse )
		{
			if ( numCollapses == capacity )
				doubleCapacity();
			
			Index i = numCollapses;
			Index parent = getParentIndex(i);
			
			new (array + numCollapses) EdgeCollapseReference( newCollapse );
			array[i].collapse->queueIndex = i;
			numCollapses++;
			
			// reorder the queue's heap so that the new element is in the correct place.
			while ( array[parent] < array[i] )
			{
				swap( parent, i );
				
				i = parent;
				parent = getParentIndex(i);
			}
		}
		
		
		inline void remove()
		{
			// Decrement the number of elements in the queue.
			numCollapses--;
			
			// Copy the last element in the queue's array into the largest element's location.
			array[0] = array[numCollapses];
			array[0].collapse->queueIndex = 0;
			
			// Call the destructor for the old last element.
			array[numCollapses].~EdgeCollapseReference();
			
			// Convert the new array into a heap, starting at the first element.
			this->heapify( 0 );
		}
		
		/// Ensure that the heap is propery ordered after the specified element was changed.
		inline void update( Index i )
		{
			if ( i > 0 )
			{
				Index parent = getParentIndex(i);
				
				// Did the entry increase its value?
				if ( array[parent] < array[i] )
				{
					do
					{
						swap( parent, i );
						
						i = parent;
						parent = getParentIndex(i);
					}
					while ( i > 0 && array[parent] < array[i] );
					
					return;
				}
			}
			
			this->heapify( i );
		}
		
		
		inline const EdgeCollapseReference& getFirst() const
		{
			return *array;
		}
		
		
		inline Size getSize() const
		{
			return numCollapses;
		}
		
		
		inline void clear()
		{
			if ( array != NULL )
				callDestructors( array, numCollapses );
			
			numCollapses = Size(0);
		}
		
		
	private:
		
		/// Get the index of a child elements's parent element given the child element's index.
		/**
		  * If the child index is zero, the method returns 0 because this child element is
		  * at the top of the heap and has no parent by definition.
		  */
		inline static Index getParentIndex( Index child )
		{
			if ( child == Index(0) )
				return Index(0);
			
			return (child - Index(1))/Index(2);
		}
		
		
		/// Get the index of the left child element given the parent element's index.
		inline static Index getChildIndex1( Index parent )
		{
			return (parent << 1) + Index(1);
		}
		
		
		/// Get the index of the right child element given the parent element's index.
		inline static Index getChildIndex2( Index parent )
		{
			return (parent << 1) + Index(2);
		}
		
		
		/// Convert the specified sub-heap, with root at index i, into a heap.
		inline void heapify( Index i )
		{
			while ( i < numCollapses )
			{
				Index childIndex1 = getChildIndex1(i);
				Index childIndex2 = getChildIndex2(i);
				Index max;
				
				if ( childIndex1 < numCollapses && array[i] < array[childIndex1] )
					max = childIndex1;
				else
					max = i;
				
				if ( childIndex2 < numCollapses && array[max] < array[childIndex2] )
					max = childIndex2;
				
				if ( max == i )
					break;
				
				swap( max, i );
				i = max;
			}
		}
		
		// Swap two elements in the heap.
		GSOUND_FORCE_INLINE void swap( Index index1, Index index2 )
		{
			EdgeCollapseReference temp = array[index1];
			array[index1] = array[index2];
			array[index2] = temp;
			
			// Update the indices for the swapped elements.
			array[index1].collapse->queueIndex = index1;
			array[index2].collapse->queueIndex = index2;
		}
		
		
		inline void doubleCapacity()
		{
			// check to see if the array has not yet been allocated.
			if ( capacity == 0 )
			{
				// allocate the array to hold elements.
				capacity = 8;
				array = util::allocate<EdgeCollapseReference>( capacity );
			}
			else
				resize( capacity << 1 );
		}
		
		
		/// Double the size of the element array to increase the capacity of the priority queue.
		/**
		  * This method deallocates the previously used array, and then allocates
		  * a new block of memory with a size equal to double the previous size.
		  * It then copies over all of the previous elements into the new array.
		  */
		void resize( Size newCapacity )
		{
			// Update the capacity and allocate a new array.
			capacity = newCapacity;
			EdgeCollapseReference* oldArray = array;
			array = util::allocate<EdgeCollapseReference>( capacity );
			
			// copy the elements from the old array to the new array.
			moveObjects( array, oldArray, numCollapses );
			
			// deallocate the old array.
			util::deallocate( oldArray );
		}
		
		
		inline static void moveObjects( EdgeCollapseReference* destination,
												const EdgeCollapseReference* source, Size number )
		{
			const EdgeCollapseReference* const sourceEnd = source + number;
			
			while ( source != sourceEnd )
			{
				// copy the object from the source to destination
				new (destination) EdgeCollapseReference(*source);
				
				// call the destructors on the source
				source->~EdgeCollapseReference();
				
				destination++;
				source++;
			}
		}
		
		inline static void callDestructors( EdgeCollapseReference* array, Size number )
		{
			const EdgeCollapseReference* const arrayEnd = array + number;
			
			while ( array != arrayEnd )
			{
				array->~EdgeCollapseReference();
				array++;
			}
		}
		
		
		EdgeCollapseReference* array;
		
		Size capacity;
		
		
		Size numCollapses;
		
		
		
};




class QEMVertex
{
	public:
		
		inline QEMVertex( const Matrix4& newQ )
			:	Q( newQ )
		{
		}
		
		
		/// The quadric error metric matrix Q for this vertex.
		Matrix4 Q;
		
		
		/// A list of the edge collapses that include this vertex.
		ShortArrayList<EdgeCollapseReference,4> collapses;
		
		
};




Bool MeshPreprocessor:: collapseEdges( ArrayList<FatVertex>& vertices, ArrayList<FatTriangle>& triangles, Real maxCost )
{
	//***************************************************************************
	// Compute the error matrix for each vertex in the mesh.
	
	const Size numVertices = vertices.getSize();
	ArrayList<QEMVertex> qemVertices( numVertices );
	
	for ( Index i = 0; i < numVertices; i++ )
	{
		FatVertex& vertex = vertices[i];
		vertex.checked = false;
		qemVertices.add( computeQ( vertex, triangles ) );
	}
	
	//***************************************************************************
	// Compute the target vertices and initial costs for all edges in the mesh.
	
	ArrayList<EdgeCollapse> edgeCollapses;
	
	for ( Index i = 0; i < numVertices; i++ )
	{
		FatVertex& vertex = vertices[i];
		QEMVertex& qemVertex = qemVertices[i];
		const Size numNeighbors = vertex.vertexNeighbors.getSize();
		
		// Skip previously collapsed vertices.
		if ( vertex.collapsed )
			continue;
		
		for ( Index n = 0; n < numNeighbors; n++ )
		{
			const Index neighborIndex = vertex.vertexNeighbors[n];
			FatVertex& vertex2 = vertices[neighborIndex];
			
			// Skip neighbors that have already been checked.
			if ( vertex2.checked || vertex2.collapsed )
				continue;
			
			const QEMVertex& qemVertex2 = qemVertices[neighborIndex];
			
			// Compute the combined error matrix for these vertices.
			Matrix4 Q12 = qemVertex.Q + qemVertex2.Q;
	
			// Compute the optimal collapse vertex and the cost for this edge collapse.
			Vector3 target = computeCollapseVertex( Q12, vertex.position, vertex2.position );
			
			// Compute the error for this target vertex.
			Real cost = computeQError( Q12, target );
			
			// Add this edge collapse to the edge collapse list.
			edgeCollapses.add( EdgeCollapse( i, neighborIndex, target, cost ) );
		}
		
		vertex.checked = true;
	}
	
	EdgeCollapseQueue edgeCollapseQueue( edgeCollapses.getSize() );
	
	for ( Index i = 0; i < edgeCollapses.getSize(); i++ )
	{
		EdgeCollapse& collapse = edgeCollapses[i];
		QEMVertex& qemV1 = qemVertices[collapse.v1];
		QEMVertex& qemV2 = qemVertices[collapse.v2];
		
		qemV1.collapses.add( &collapse );
		qemV2.collapses.add( &collapse );
		edgeCollapseQueue.add( &collapse );
	}
	
	//***************************************************************************
	// Collapse edges until the maximum cost is reached.
	
	nextEdgeCollapse:
	
	while ( edgeCollapseQueue.getSize() > 0 )
	{
		// Get the next edge collapse, then remove it from the queue.
		EdgeCollapseReference collapseReference = edgeCollapseQueue.getFirst();
		edgeCollapseQueue.remove();
		
		// Check to see if all further collapses exceed the maximum cost parameter.
		// If so, we are done collapsing edges.
		if ( collapseReference.getCost() > maxCost )
			break;
		
		EdgeCollapse& collapse = *collapseReference.collapse;
		
		// Skip degenerate edge collapses.
		if ( collapse.v1 == collapse.v2 )
			continue;
		
		const Index fromIndex = collapse.v1;
		FatVertex& fromVertex = vertices[fromIndex];
		
		const Index toIndex = collapse.v2;
		FatVertex& toVertex = vertices[toIndex];
		
		// Skip 'from' or 'to' vertices that have already been collapsed.
		if ( fromVertex.collapsed || toVertex.collapsed )
			continue;
		
		if ( vertexIsBorder( fromVertex, triangles ) || vertexIsBorder( toVertex, triangles ) )
			continue;
		
		//***************************************************************************
		// Check to make sure this edge collapse won't invert any triangles.
		
		for ( Index t = 0; t < fromVertex.triangleNeighbors.getSize(); t++ )
		{
			const Index triangleIndex = fromVertex.triangleNeighbors[t];
			const FatTriangle& triangle = triangles[triangleIndex];
			
			// Check only triangles that aren't removed.
			if ( !triangle.hasVertex( toIndex ) )
			{
				// Recompute the triangle plane equation.
				Plane3 newPlane( triangle.v[0] == fromIndex ? collapse.target : vertices[triangle.v[0]].position,
								triangle.v[1] == fromIndex ? collapse.target : vertices[triangle.v[1]].position,
								triangle.v[2] == fromIndex ? collapse.target : vertices[triangle.v[2]].position );
				
				// If the normals don't point in the same direction, then the triangle
				// would be reversed by this collapse and the mesh would fold over.
				// Don't do this edge collapse because it makes the model degenerate.
				if ( math::dot( triangle.plane.normal, newPlane.normal ) < Real(0.0) )
					goto nextEdgeCollapse;
			}
		}
		
		for ( Index t = 0; t < toVertex.triangleNeighbors.getSize(); t++ )
		{
			const Index triangleIndex = toVertex.triangleNeighbors[t];
			const FatTriangle& triangle = triangles[triangleIndex];
			
			// Check only triangles that aren't removed.
			if ( !triangle.hasVertex( fromIndex ) )
			{
				// Recompute the triangle plane equation.
				Plane3 newPlane( triangle.v[0] == toIndex ? collapse.target : vertices[triangle.v[0]].position,
								triangle.v[1] == toIndex ? collapse.target : vertices[triangle.v[1]].position,
								triangle.v[2] == toIndex ? collapse.target : vertices[triangle.v[2]].position );
				
				// If the normals don't point in the same direction, then the triangle
				// would be reversed by this collapse and the mesh would fold over.
				// Don't do this edge collapse because it makes the model degenerate.
				if ( math::dot( triangle.plane.normal, newPlane.normal ) < Real(0.0) )
					goto nextEdgeCollapse;
			}
		}
		
		//***************************************************************************
		
		// Mark the 'from' vertex as collapsed.
		fromVertex.collapsed = true;
		
		// Update the 'to' vertex to have the optimal collapsed position.
		toVertex.position = collapse.target;
		
		
		// Update the triangles that shared the from vertex.
		for ( Index t = 0; t < fromVertex.triangleNeighbors.getSize(); t++ )
		{
			const Index triangleIndex = fromVertex.triangleNeighbors[t];
			FatTriangle& triangle = triangles[triangleIndex];
			
			if ( triangle.hasVertex( toIndex ) )
			{
				// This triangle becomes degenerate after the edge collapse.
				// Mark it as collapsed.
				triangle.collapsed = true;
				
				// Remove this triangle from the list of neighbors for its vertices.
				if ( triangle.v[0] != fromIndex )
					vertices[triangle.v[0]].triangleNeighbors.remove( triangleIndex );
				
				if ( triangle.v[1] != fromIndex )
					vertices[triangle.v[1]].triangleNeighbors.remove( triangleIndex );
				
				if ( triangle.v[2] != fromIndex )
					vertices[triangle.v[2]].triangleNeighbors.remove( triangleIndex );
			}
			else
			{
				// This triangle needs to be updated with the new vertex index.
				triangle.replaceVertex( fromIndex, toIndex );
				
				// Recompute the triangle plane equation.
				triangle.plane = Plane3( vertices[triangle.v[0]].position,
										vertices[triangle.v[1]].position,
										vertices[triangle.v[2]].position );
				
				// Make sure the to vertex has this triangle as its neighbor.
				toVertex.triangleNeighbors.add( triangleIndex );
			}
		}
		
		// Clear the triangle neighbor list for the 'from' vertex since it is no longer used.
		fromVertex.triangleNeighbors.clear();
		
		toVertex.vertexNeighbors.removeUnordered( fromIndex );
		
		for ( Index i = 0; i < fromVertex.vertexNeighbors.getSize(); i++ )
		{
			const Index neighborIndex = fromVertex.vertexNeighbors[i];
			
			if ( neighborIndex == toIndex )
				continue;
			
			// Add this neighbor of the 'from' vertex to the list of neighbors for the 'to' vertex.
			if ( !toVertex.vertexNeighbors.contains( neighborIndex ) )
			{
				// Update the 'to' vertex.
				toVertex.vertexNeighbors.add( neighborIndex );
				
				// Update the neighbor vertex.
				FatVertex& neighbor = vertices[neighborIndex];
				neighbor.vertexNeighbors.removeUnordered( fromIndex );
				neighbor.vertexNeighbors.add( toIndex );
			}
		}
		
		fromVertex.vertexNeighbors.clear();
		
		QEMVertex& fromQEMVertex = qemVertices[fromIndex];
		QEMVertex& toQEMVertex = qemVertices[toIndex];
		
		// Compute the error matrix for the collapsed vertex.
		toQEMVertex.Q += fromQEMVertex.Q;
		
		// Remove the current collapse from the 'to' vertex.
		toQEMVertex.collapses.remove( collapseReference );
		
		// Merge the collapses associated with the 'from' vertex with those from the 'to' vertex.
		for ( Index i = 0; i < fromQEMVertex.collapses.getSize(); i++ )
		{
			const EdgeCollapseReference& ref = fromQEMVertex.collapses[i];
			
			// Replace the 'from' vertex in the collapse structures.
			if ( ref.collapse->v1 == fromIndex )
				ref.collapse->v1 = toIndex;
			else if ( ref.collapse->v2 == fromIndex )
				ref.collapse->v2 = toIndex;
			
			if ( ref.collapse->v1 == ref.collapse->v2 )
				continue;
			
			// Add the collapse to the collapses for the 'to' vertex if it is not a duplicate.
			if ( !toQEMVertex.collapses.contains( ref ) )
				toQEMVertex.collapses.add( ref );
		}
		
		// Clear the collapses from the 'from' vertex.
		fromQEMVertex.collapses.clear();
		
		// Recompute the cost for all edge collapses that involve the 'to' vertex.
		for ( Index i = 0; i < toQEMVertex.collapses.getSize(); )
		{
			const EdgeCollapseReference& ref = toQEMVertex.collapses[i];
			EdgeCollapse& newCollapse = *ref.collapse;
			const Index v1Index = newCollapse.v1;
			const Index v2Index = newCollapse.v2;
			
			// Compute the combined error matrix for these vertices.
			Matrix4 Q12 = qemVertices[v1Index].Q + qemVertices[v2Index].Q;
			
			// Compute the new optimal collapse vertex and the cost for this edge collapse.
			newCollapse.target = computeCollapseVertex( Q12, vertices[v1Index].position, vertices[v2Index].position );
			
			// Compute the error for this target vertex.
			newCollapse.cost = computeQError( Q12, newCollapse.target );
			
			// Update the recomputed edge collapse in the heap.
			edgeCollapseQueue.update( newCollapse.queueIndex );
			
			i++;
		}
	}
	
	//***************************************************************************
	
	return true;
}




Matrix4 MeshPreprocessor:: computeQ( const FatVertex& vertex, const ArrayList<FatTriangle>& triangles )
{
	const Size numTriangleNeighbors = vertex.triangleNeighbors.getSize();
	Matrix4 Q;
	
	for ( Index i = 0; i < numTriangleNeighbors; i++ )
	{
		const Index triangleIndex = vertex.triangleNeighbors[i];
		const FatTriangle& triangle = triangles[triangleIndex];
		
		// Compute the error matrix for this triangle's plane.
		Vector4 p( triangle.plane.normal, triangle.plane.offset );
		Matrix4 Kp( p.x*p.x, p.y*p.x, p.z*p.x, p.w*p.x,
					p.x*p.y, p.y*p.y, p.z*p.y, p.w*p.y,
					p.x*p.z, p.y*p.z, p.z*p.z, p.w*p.z,
					p.x*p.w, p.y*p.w, p.z*p.w, p.w*p.w );
		
		// Accumulate the error matrix.
		Q += Kp;
	}
	
	return Q;
}





Real MeshPreprocessor:: computeQError( const Matrix4& Q, const Vector3& v )
{
	Vector4 v4( v, 1 );
	
	return math::abs( math::dot( v4, Q*v4 ) );
}




Vector3 MeshPreprocessor:: computeCollapseVertex( const Matrix4& Q12, const Vector3& v1, const Vector3& v2 )
{/*
	// Compute the matrix to solve for the optimal collapse location.
	Matrix4 q = Q12;
	q.x.w = q.y.w = q.z.w = 0;
	q.w.w = 1;
	
	// Try inverting the matrix Q to compute the minimum-cost collapsed vertex.
	Matrix4 qInverse;
	
	Vector3 midpoint = math::midpoint( v1, v2 );
	Real midpointCost = computeQError( Q12, midpoint );
	
	if ( q.invert( qInverse, 0.1 ) && computeQError( Q12, qInverse.w.getXYZ() ) < midpointCost )
	{
		return qInverse.w.getXYZ();
	}
	else*/
	{
		// Inversion failed so pick the vertex or midpoint with the lowest cost.
		Vector3 midpoint = math::midpoint( v1, v2 );
		Real midpointCost = computeQError( Q12, midpoint );
		Real v1Cost = computeQError( Q12, v1 );
		Real v2Cost = computeQError( Q12, v2 );
		
		// Return the vertex or midpoint with the least cost.
		if ( v1Cost < v2Cost )
		{
			if ( v1Cost < midpointCost )
				return v1;
			else
				return midpoint;
		}
		else
		{
			if ( v2Cost < midpointCost )
				return v2;
			else
				return midpoint;
		}
	}
}




Bool MeshPreprocessor:: vertexIsBorder( const FatVertex& vertex, const ArrayList<FatTriangle>& triangles )
{
	const Size numVertexNeighbors = vertex.vertexNeighbors.getSize();
	const Size numTriangleNeighbors = vertex.triangleNeighbors.getSize();
	
	for ( Index v = 0; v < numVertexNeighbors; v++ )
	{
		const Index neighborIndex = vertex.vertexNeighbors[v];
		Size numNeighborTriangles = 0;
		
		for ( Index t = 0; t < numTriangleNeighbors; t++ )
		{
			const FatTriangle& triangle = triangles[vertex.triangleNeighbors[t]];
			
			if ( triangle.hasVertex( neighborIndex ) )
				numNeighborTriangles++;
		}
		
		if ( numNeighborTriangles == Size(1) )
			return true;
	}
	
	return false;
}



#5152728 High Speed Quadric Mesh Simplification without problems (Resolved)

Posted by Aressera on 10 May 2014 - 01:09 PM

If you use a proper data structure (custom heap) for the edge list, you can get similar performance to your implementation, but with much better quality. This keeps the edge list sorted automatically, and if you store the position in the (array-based) heap along with the edge, you can get O(log(N)) updates/removals with each iteration. The problem with not updating the list of edges on each iteration is that the algorithm no longer optimally picks the edge with the least error, so your results will not be as good as the original quadric-error edge collapse algorithm.

 

The problem you're probably seeing is that triangles can flip over during an edge collapse, causing overlap of mostly coplanar triangles. You can fix this by checking each triangle that shares the edge vertices to make sure that its normal does not change sign (dot product with old normal < 0).




#5152369 Statistic algorithms for ECS

Posted by Aressera on 08 May 2014 - 01:42 PM

You could use a pool allocator for each type of component in order to guarantee (mostly) contiguous memory for components of the same type.




#5151025 Global illumination techniques

Posted by Aressera on 02 May 2014 - 06:22 PM

 


They explicitly state they support arbitraty BSDFs, and that includes glossy reflections.

 

Then why have they not demonstrated it. A picture is worth a thousand words.

 

 

See figure 6 of the paper, they show fresnel and specular reflections.




#5150799 Please help with Minkowski Difference and the Origin

Posted by Aressera on 01 May 2014 - 02:12 PM

The shapes are in collision if the origin of the Configuration Space is inside their Minkowski difference, not the coordinate system that the shapes themselves are defined in. You can think of the Minkowski difference as subtracting all of the points in shape B from all of the points in shape A. Therefore, if the shapes overlap, there should be some point in each original shape that corresponds to the origin (difference = 0) in configuration space.




#5149898 DSP. Reverb

Posted by Aressera on 27 April 2014 - 11:40 AM

Here is a really helpful master's thesis on reverberation.

 

Here is a presentation of different reverb algorithms.

 

Here is an interesting extension of the Schroeder reverberator you have implemented.




#5149073 Forward rendering light management

Posted by Aressera on 23 April 2014 - 04:54 PM

I get pretty good results by sorting lights based on how much they shine on each mesh being rendered, culling lights that don't intersect the mesh (at some threshold intensity, ~0.005). I compute the light intensity at the center of the bounding box, then sort the lights by decreasing intensity. I then use the first N lights in the sorted list to send to the shader for rendering that mesh. Unless your entire world mesh is rendered in 1 draw call (unlikely), there is usually enough granularity of the meshes in the scene to get by with 4-8 lights, since there can be many lights visible, but only a few can shine on each object. The number of lights per mesh is determined by the shader's inputs.




#5146141 Large matrix Inverse.

Posted by Aressera on 10 April 2014 - 07:29 PM

Do you really need a matrix inverse function? Most numerical linear algebra problems can be solved without explicitly computing the inverse.

 

LU decomposition is probably the most efficient way, but it is not as numerically stable as a QR matrix inversion, which is backwards-stable. I would avoid gaussian elimination because it is less stable.




#5140060 Assets for tech demos

Posted by Aressera on 18 March 2014 - 10:52 AM

http://graphics.cs.williams.edu/data/meshes.xml Has lots of the standard graphics models (sponza, sibenik, dragon, buddha, etc)




#5139625 Specular Highlights Disappear Up Close

Posted by Aressera on 16 March 2014 - 10:34 PM

Yes, I have made sure they are all normalized.

 

I rewrote my shader and I managed to fix the problem (even with per-pixel half vectors). The issue was how I was calculating the direction to the surface. I was using a 4D vector (x,y,z,w) to represent position, and neglecting the fact that the w component was non-zero. Therefore, the computed half vector wasn't correct.

// Old code
vec4 surfacePosition = interpolatedPosition;
vec4 surfaceDirection = normalize( surfacePosition );

// New code
vec4 surfacePosition = vec4( interpolatedPosition.xyz / interpolatedPosition.w, 1.0 );
vec4 surfaceDirection = vec4( normalize( surfacePosition.xyz ), 0.0 );



#5137374 Avoiding dark areas in ray tracing

Posted by Aressera on 08 March 2014 - 12:55 PM

It doesn't look like your ray tracing has any diffuse reflection component to it (i.e. global illumination). Without the scattering induced by surface roughness it may be impossible for certain areas to reflect back any light.




#5126778 Generating random points in a sphere

Posted by Aressera on 27 January 2014 - 01:30 PM

Here is the code that I use to generate uniform random points on a sphere (which is derived from the wolfram link posted above):

float u1 = randomRange( -1.0f, 1.0f );
float u2 = randomRange( 0.0f, 1.0f );
float r = sqrt( 1.0f - u1*u1 );
float theta = 2.0f*math::pi<float>()*u2;

return Vector3( r*cos( theta ), r*sin( theta ), u1 );



#5126262 Preventing repeating terrain textures.

Posted by Aressera on 25 January 2014 - 12:49 AM

In your image editor, use a high-pass filter (Photoshop: Filter->Other->High Pass) to remove the low frequencies from the textures. This will make the tiling less noticeable.






PARTNERS