locked
Access Violation only in 32bit-Release with Optimization=on

    Question

  • Hi!

    I started to develop a Game for Windows Store, which worked out quite fine until I implemented a QuadTree.

    My game has the following structure (each point is a project):

    - App (Frontend, Pages): C#

    - GameLogic: C#

    - Interfaces (between GameLogic and Engine): C#

    - Engine&Renderer: C++

    It was developed for Windows 8 using Visual Studio 2012 (Ultimate), and ran without Problems until I added a QuadTree:

    PhysicEngine.hpp:

    #pragma once
    
    #include "BoundingVolume.hpp"
    
    namespace Windows8
    {
    	namespace Renderer
    	{
    		struct Collision
    		{
    			ICollidableObject^ otherObject;
    			float			   t;		
    
    			bool operator < (Windows8::Renderer::Collision const & c2) const
    			{
    				return t > c2.t;
    			}
    		};
    		struct BoundingSphereCollisionObject
    		{
    			ICollidableObject^			obj;
    			BoundingSphereData const *  bounding;					
    		};
    
    		enum class QuadTreeNodeType : int
    		{
    			UR = 0,
    			UL = 1,
    			LL = 2,
    			LR = 3,
    			None = 4
    		};
    
    		XMVECTOR QuadTreeNodeTypeDirection(QuadTreeNodeType type);
    
    		class QuadTree;
    		class QuadTreeNode
    		{
    			private:
    				QuadTree* const										m_tree;
    				QuadTreeNodeType const								m_type;
    
    				XMVECTOR const										m_center;
    				float const	 										m_extent;
    
    				QuadTreeNode* const									m_root;
    				QuadTreeNode* const									m_parent;
    
    				unique_ptr<QuadTreeNode>							m_children[4];
    					
    				set<BoundingSphereCollisionObject*>					m_attachedObjects;
    
    
    
    					
    				bool			hasChildren	()							const	{ return m_children[0u] != nullptr; }
    				QuadTreeNode*	getChild	(int nodeType)						{ return m_children[     nodeType].get(); }
    				QuadTreeNode*	getChild	(QuadTreeNodeType nodeType)			{ return m_children[(int)nodeType].get(); }
    
    				bool isObjectInNode(BoundingSphereCollisionObject const * obj);
    				void findCollisions(BoundingSphereCollisionObject const * collObj, XMVECTOR const & move, OUT vector<Collision> & collisions);
    				void findCollision (BoundingSphereCollisionObject const * collObj, XMVECTOR const & move, BoundingSphereCollisionObject const * otherCollObj, OUT vector<Collision> & collisions);
    					
    			public:
    
    						QuadTreeNode	(QuadTree* tree);
    						QuadTreeNode	(QuadTreeNode* parent, QuadTreeNodeType type);
    
    				void	add				(BoundingSphereCollisionObject* obj);
    				void	remove			(BoundingSphereCollisionObject* obj);
    
    				void	updateCollisions(float time, float timeDelta);
    				void	update			();
    				void	split			();
    				void	merge			();
    		};
    
    		class QuadTree
    		{
    			private:
    				IdCache<UINT> 										m_idCache;
    				map<UINT, BoundingSphereCollisionObject>			m_allObjects;
    
    				XMVECTOR											m_center;
    				float												m_extent;
    
    				UINT												m_minAttachedObjectsPerNode;
    				UINT												m_maxAttachedObjectsPerNode;
    					
    				unique_ptr<QuadTreeNode>							m_root;
    
    					
    				void rebuild();
    
    			public:		
    				QuadTree(	XMVECTOR const &	center						= XMVectorSet(0,0,0,1), 
    							float				extent						= 200.0f, 
    							UINT				maxAttachedObjectsPerNode	= 10u,
    							UINT				minAttachedObjectsPerNode	= 5u);
    
    
    				XMVECTOR const &	getCenter()									const	{ return m_center; }
    				float				getExtent()									const	{ return m_extent; }
    				UINT				getMinAttachedObjectsPerNode()				const	{ return m_minAttachedObjectsPerNode; }
    				UINT				getMaxAttachedObjectsPerNode()				const	{ return m_maxAttachedObjectsPerNode; }
    										
    				void				setMinAttachedObjectsPerNode(UINT value)			{ m_minAttachedObjectsPerNode = value; }
    				void				setMaxAttachedObjectsPerNode(UINT value)			{ m_maxAttachedObjectsPerNode = value; }
    
    					
    
    
    				void	rebuild	(XMVECTOR const & center, float entent);
    				void	add		(ICollidableObject^ collObj);
    				void	remove	(ICollidableObject^ collObj);
    				void	animate	(float time, float timeDelta);
    		};
    
    		public ref class PhysicEngine sealed : public IPhysicEngine
    		{
    			private:
    				QuadTree m_tree;
    
    			public:
    				property Vector3^		Center						{ Vector3^		get() { return ref new Vector3(XMVectorGetX(m_tree.getCenter()), XMVectorGetY(m_tree.getCenter()), XMVectorGetZ(m_tree.getCenter())); } }
    				property float			Extent						{ float			get() { return m_tree.getExtent(); } }
    				property UINT			MinAttachedObjectsPerNode	{ UINT			get() { return m_tree.getMinAttachedObjectsPerNode(); }	void set(UINT value)	{ m_tree.setMinAttachedObjectsPerNode( value ); } }
    				property UINT			MaxAttachedObjectsPerNode	{ UINT			get() { return m_tree.getMaxAttachedObjectsPerNode(); }	void set(UINT value)	{ m_tree.setMaxAttachedObjectsPerNode( value ); } }
    
    				PhysicEngine();
    				virtual ~PhysicEngine();
    
    				virtual void Register  (ICollidableObject^ collObj);
    				virtual void Unregister(ICollidableObject^ collObj);
    				virtual void Animate   (float time, float timeDelta);
    		};
    	};
    };


    PhysicEngine.cpp:

    #include "PhysicEngine.hpp"
    
    
    Windows8::Renderer::QuadTree::QuadTree(XMVECTOR const & center, float extent, UINT maxAttachedObjectsPerNode, UINT minAttachedObjectsPerNode)
    	: m_center						(center),
    	  m_extent						(extent),
    	  m_maxAttachedObjectsPerNode	(maxAttachedObjectsPerNode),
    	  m_minAttachedObjectsPerNode	(minAttachedObjectsPerNode),
    	  m_root						(new QuadTreeNode(this)),
    	  m_allObjects					(),
    	  m_idCache						()
    { }
    void Windows8::Renderer::QuadTree::add(ICollidableObject^ collObj)
    {	
    	auto id = m_idCache.createId();
    	collObj->PhysicId = id;
    
    	auto boundingSphere = dynamic_cast<BoundingSphere^>(collObj->BoundingVolume);
    	if (boundingSphere != nullptr)
    	{
    		BoundingSphereCollisionObject& obj = m_allObjects[id];
    		obj.obj = collObj;
    		obj.bounding = &(boundingSphere->getData());
    		m_root->add(&obj);
    	}	
    }
    void Windows8::Renderer::QuadTree::remove(ICollidableObject^ collObj)
    {
    	if ( collObj->PhysicId == nullptr ) return;
    	auto id = collObj->PhysicId->Value;
    
    	auto found = m_allObjects.find(id);
    	if ( found != m_allObjects.end() )
    	{
    		m_root->remove(&(found->second));
    		m_allObjects.erase(found);
    	}
    	
    	m_idCache.deleteId(id);
    	collObj->PhysicId = nullptr;
    }
    void Windows8::Renderer::QuadTree::animate(float time, float timeDelta)
    {	
    	// update the tree
    	m_root->update();
    	
    	// find collisions
    	m_root->updateCollisions(time, timeDelta);
    }
    void Windows8::Renderer::QuadTree::rebuild(XMVECTOR const & center, float entent)
    {
    	m_center = center;
    	m_extent = entent;
    
    	rebuild();
    }
    
    void Windows8::Renderer::QuadTree::rebuild()
    {
    	m_root.reset(new QuadTreeNode(this));
    
    	foreach(itr,m_allObjects)
    		m_root->add( &(itr->second) );
    }
    
    
    
    
    
    
    XMVECTOR Windows8::Renderer::QuadTreeNodeTypeDirection(QuadTreeNodeType type)
    {
    	switch (type)
    	{
    		case QuadTreeNodeType::LL: return XMVectorSet(-1.0f, 0, -1.0f, 0);
    		case QuadTreeNodeType::LR: return XMVectorSet( 1.0f, 0, -1.0f, 0);
    		case QuadTreeNodeType::UL: return XMVectorSet(-1.0f, 0,  1.0f, 0);
    		default:
    		case QuadTreeNodeType::UR: return XMVectorSet( 1.0f, 0,  1.0f, 0);
    	}
    }
    
    
    
    
    
    
    Windows8::Renderer::QuadTreeNode::QuadTreeNode(QuadTree* tree)
    	: m_root	(this),
    	  m_tree	(tree),
    	  m_parent	(nullptr),
    	  m_extent	(tree->getExtent()),
    	  m_center	(tree->getCenter()),
    	  m_type	(QuadTreeNodeType::None)
    { }
    Windows8::Renderer::QuadTreeNode::QuadTreeNode(QuadTreeNode* parent, QuadTreeNodeType type)
    	: m_root	(parent->m_root),
    	  m_tree	(parent->m_tree),
    	  m_parent	(parent),
    	  m_extent	(parent->m_extent * 0.5f),
    	  m_center	(XMVectorSubtract(parent->m_center, QuadTreeNodeTypeDirection(type) * (parent->m_extent * 0.25f))),
    	  m_type	(type)
    { }
    void Windows8::Renderer::QuadTreeNode::add(BoundingSphereCollisionObject* obj)
    {	
    	if (isObjectInNode(obj))
    	{
    		if (hasChildren())
    		{
    			for(auto& child : m_children) 
    			{
    				child->add(obj);
    			}
    		}
    		else
    			m_attachedObjects.insert(obj);
    	}
    }
    void Windows8::Renderer::QuadTreeNode::remove(BoundingSphereCollisionObject* obj)
    {
    	if (hasChildren())
    	{
    		for(auto& child : m_children) 
    		{
    			child->remove(obj);
    		}
    	}
    
    	m_attachedObjects.erase(obj);
    }
    void Windows8::Renderer::QuadTreeNode::update()
    {
    	// check if the attached objects still belong to this node
    	vector<BoundingSphereCollisionObject*> deleted;
    	for (auto itr = m_attachedObjects.begin(); itr != m_attachedObjects.end(); )
    	{
    		auto obj = *itr;
    		if (! isObjectInNode(obj) )
    		{
    			// if it does not belong to this node, remove it from here and later reattach it at the root
    			deleted.push_back(obj);
    			m_attachedObjects.erase( itr++ );
    		}
    		else
    			itr++;
    	}
    	foreach (itr, deleted)
    	{
    		auto obj = *itr;
    		m_root->add(obj);
    	}
    	
    	// update the children
    	auto numChildObjects = 0u;
    	if (hasChildren())
    	{
    		for(auto& child : m_children) 
    		{
    			child->update();
    			numChildObjects += static_cast<UINT>(child->m_attachedObjects.size());
    		}
    	}
    	
    
    	// check if we need to split or merge
    	auto numObjects = m_attachedObjects.size();
    	if (numObjects > m_tree->getMaxAttachedObjectsPerNode())
    	{
    		split();
    	}
    	else if (numChildObjects > 0 && numChildObjects < m_tree->getMinAttachedObjectsPerNode())
    	{
    		merge();
    	}
    }
    void Windows8::Renderer::QuadTreeNode::split()
    {
    	// if node is already split, return immediately
    	if (hasChildren()) return;
    	
    	// otherwise, continue and create all child elements
    	for (auto i = 0; i < 4; i++)
    	{
    		// allocate new node
    		m_children[i].reset(new QuadTreeNode(this, (QuadTreeNodeType)i));
    	}
    	
    	
    	// add objects
    	foreach (itr, m_attachedObjects)
    	{
    		auto obj = *itr;
    		add(obj);
    	}
    	m_attachedObjects.clear();
    }
    void Windows8::Renderer::QuadTreeNode::merge()
    {
    	// if node has no children, return immediately
    	if (!hasChildren()) return;
    
    	// otherwise add all child-objects to the their parent's list
    	for(auto& child : m_children) 
    	{
    		child->merge();
    
    		// copy child-entries to own list. double entries are discarded, since the collection is a set.
    		m_attachedObjects.insert(child->m_attachedObjects.begin(),child->m_attachedObjects.end());
    
    		child.reset(nullptr);
    	}
    }
    void Windows8::Renderer::QuadTreeNode::updateCollisions(float time, float timeDelta)
    {
    	if (hasChildren())
    	{
    		for(auto& child : m_children) 
    		{
    			child->updateCollisions(time, timeDelta);
    		}
    	}
    
    	if (m_attachedObjects.size() > 0)
    	{
    		vector<Collision> collisions;
    		foreach(itr, m_attachedObjects)
    		{
    			auto collObj = *itr;
    			auto obj = collObj->obj;
    			auto moveVec = obj->PopMoveVector();
    			auto move = XMVectorSet(moveVec->X, moveVec->Y, moveVec->Z, 0.0f);
    		
    			if ( XMVector3Equal(move, nullvec) ) continue;
    		
    			collisions.clear();
    			collisions.reserve(50);
    
    			findCollisions(collObj, move, OUT collisions);
    		
    			sort(collisions.begin(), collisions.end());
    
    			float t = 1.0f;
    			foreach(itrColl, collisions)
    			{
    				auto coll = *itrColl;
    
    				if (obj->OnCollision(time, timeDelta, coll.otherObject) )
    				{
    					t = 0.0f;
    					break;
    				}
    
    				if (coll.otherObject->IsBlocking && obj->IsBlocking)
    				{
    					t = coll.t;
    					break;
    				}
    			}
    		
    			if (t != 0.0f)
    			{
    				move *= t;
    				obj->Move(ref new Vector3(XMVectorGetX(move), XMVectorGetY(move), XMVectorGetZ(move)));
    			}
    		}
    	}
    }
    void Windows8::Renderer::QuadTreeNode::findCollisions(BoundingSphereCollisionObject const * collObj, XMVECTOR const & move, OUT vector<Collision> & collisions)
    {
    	foreach(itr, m_attachedObjects)
    	{
    		auto otherObj = *itr;
    		if (otherObj->obj == collObj->obj) continue;
    
    		findCollision(collObj, move, otherObj, collisions);
    	}
    }
    void Windows8::Renderer::QuadTreeNode::findCollision(BoundingSphereCollisionObject const * collObj, XMVECTOR const & move, BoundingSphereCollisionObject const * otherCollObj, OUT vector<Collision> & collisions)
    {
    	Collision coll;
    	coll.otherObject = otherCollObj->obj;
    	
    	XMVECTOR const m1 = collObj->bounding->center;
    	XMVECTOR const m2 = otherCollObj->bounding->center;
    	float const r1 = collObj->bounding->radius;
    	float const r2 = otherCollObj->bounding->radius;
    		
        XMVECTOR const m1_sub_m2 = XMVectorSubtract(m1, m2);
        float const r1_add_r2 = r1 + r2;
    
    	if (XMVectorGetX(XMVector3LengthSq(m1_sub_m2)) <= (r1_add_r2*r1_add_r2)) // if is already colliding
    	{
    		if ( XMVectorGetX(XMVector3Dot(move,m1_sub_m2)) <= 0.0f ) // if existing collision is blocking move-vector
    		{
    			coll.t = 0.0f;
    			collisions.push_back(coll);
    			return;
    		}
    	}
    
    	float const a = XMVectorGetX(XMVector3LengthSq(move));
    	float const b = 2.0f * XMVectorGetX(XMVector3Dot(move, m1_sub_m2));
    	float const c = XMVectorGetX(XMVector3LengthSq(m1_sub_m2)) - r1_add_r2*r1_add_r2;
    
        float sq = b*b - 4.0f*a*c;
        if (sq < 0.0f) // no collision detected along move vector (without boundaries)
    		return;
        sq = sqrt(sq);
    
    
    	float const t[2] =
    	{
            (-b + sq) / (2.0f*a),
            (-b - sq) / (2.0f*a)
    	};
    	bool const valid[2] = 
    	{
            t[0] > 0.0f && t[0] <= 1.0f,
            t[1] > 0.0f && t[1] <= 1.0f
    	};
    
        if (!valid[0] && !valid[1])  // no collision detected along move vector (in vector range)
    		return;
    
        if (valid[0] && valid[1])	coll.t = min(t[0],t[1]); // two collisions detected, take first
    	else if (valid[0])			coll.t = t[0];
    	else						coll.t = t[1];
    					
    	collisions.push_back(coll);
    }
    bool Windows8::Renderer::QuadTreeNode::isObjectInNode(BoundingSphereCollisionObject const * obj)
    {
    	auto bounding = obj->bounding;
    	XMVECTOR const & objCenter = bounding->center;
    	float const & objRadius = bounding->radius;
    	float const epsilon = 0.002f;
    		
    	// get node and it's center and extent
    	QuadTreeNode* node = this;
    	XMVECTOR const & nodeCenter = node->m_center;
    	float const & nodeExtent = node->m_extent / 2.0f;
    
    	// calculate the distance between the node's center and the object's center
    	XMVECTOR const dist = XMVectorAbs(XMVectorSubtract(objCenter, nodeCenter));
    	float const distY = XMVectorGetY(dist);
    	// if the circle is far enough away from the quad, move on to the next child-quad
    	if (XMComparisonAnyTrue(XMVector3GreaterR(dist, XMVectorSet(nodeExtent + objRadius, distY, nodeExtent + objRadius, 0))))
    	{
    		return false;
    	}
    	// if the circle-center is within the quad, add it to this child-quad
    	if (XMComparisonAnyTrue(XMVector3GreaterR(XMVectorSet(nodeExtent + epsilon, distY + epsilon, nodeExtent + epsilon, 0), dist)))
    	{
    		return true;
    	}
    	// if the circle intersects the corner of the quad, add it to this child-quad
    	return (XMVectorGetX(XMVector3LengthSq(XMVectorSubtract(dist, XMVectorSet(nodeExtent, distY, nodeExtent, 0)))) <= objRadius * objRadius);
    }
    
    
    
    Windows8::Renderer::PhysicEngine::PhysicEngine()
    	: m_tree()
    { }
    Windows8::Renderer::PhysicEngine::~PhysicEngine()
    { }
    void Windows8::Renderer::PhysicEngine::Register(ICollidableObject^ collObj)
    {
    	m_tree.add(collObj);
    }
    void Windows8::Renderer::PhysicEngine::Unregister(ICollidableObject^ collObj)
    {
    	m_tree.remove(collObj);
    }
    void Windows8::Renderer::PhysicEngine::Animate   (float time, float timeDelta)
    {
    	m_tree.animate(time, timeDelta);
    }

    And even so far I had no Problems when using Debug/x64, Release/x64, Debug/x32.

    Even when I was using Release/x32 it worked perfectly when I turned off optimization (/Od).

    As soon as I turned on optimization in any form (/O1, /O2, /Ox) it crashes.

    I was able to locate the point of crash: Sometimes it crashes when the QuadTree is created (using the new-operator), sometimes it crashes when the QuadTree is split (allocating child-nodes, using the new-operator).

    In both cases the new-operator calls malloc. After the execution of malloc (debugging malloc is difficult, using optimization, so I can't tell you where exactly in the malloc-function) the this-pointer of the calling-method is messed up (somtimes it points to nullptr, sometimes to 0x3, ....). Of course the next access of this pointer then results in an access-voilation(-exception)

    The only thing I additionaly changed (in C++- & Linker-options) since creating the program was to disable precompiled header files.

    I'm suspecting heap corruption, but since the program runs perfectly, if I don't use the quad-tree or if I turn off optimization, or if I switch to x64, ..., and I am using the new-operator in other places as well, I really have no idea where to start looking.



    Monday, November 18, 2013 3:29 PM

Answers