多边形编辑器

建立BVH

为多边形构建 BVH

BVHNode* Game::BuildBVH( std::vector indexes, int maxObjectsPerNode ) 
{
	if (indexes.empty()) return nullptr;

	// Create BVH node
	BVHNode* node = new BVHNode();
	node->m_aabb.m_mins = Vec2( FLT_MAX, FLT_MAX );
	node->m_aabb.m_maxs = Vec2( -FLT_MAX, -FLT_MAX );
	// Compute AABB, enclosing all ConvexSceneObjects
	for (int index : indexes) 
	{
		node->m_aabb.StretchToIncludePoint( m_convexes[index].m_boundingAABB.m_mins );
		node->m_aabb.StretchToIncludePoint( m_convexes[index].m_boundingAABB.m_maxs );
	}

	// Leaf node termination condition
	if (indexes.size() <= maxObjectsPerNode) 
	{
		node->m_objectIndexes = indexes;  // Leaf node stores object indices
		return node;
	}

	// Non-leaf node does not store object indexes
	node->m_objectIndexes.clear();

	// Choose splitting axis (longest axis)
	bool splitByX = (node->m_aabb.GetDimensions().x >= node->m_aabb.GetDimensions().y);

	// Sort objects by center position
	std::sort( indexes.begin(), indexes.end(), [&]( int a, int b ) 
		{
		return splitByX ? m_convexes[a].m_boundingAABB.GetCenter().x < m_convexes[b].m_boundingAABB.GetCenter().x
			: m_convexes[a].m_boundingAABB.GetCenter().y < m_convexes[b].m_boundingAABB.GetCenter().y;
		} );

	// Split at the median
	size_t mid = indexes.size() / 2;
	std::vector leftIndexes( indexes.begin(), indexes.begin() + mid );
	std::vector rightIndexes( indexes.begin() + mid, indexes.end() );

	// Recursively create child nodes
	BVHNode* leftChild = BuildBVH( leftIndexes, maxObjectsPerNode );
	BVHNode* rightChild = BuildBVH( rightIndexes, maxObjectsPerNode );

	// Recalculate AABB for each child node
	if (leftChild) 
	{
		leftChild->m_aabb = AABB2(Vec2( FLT_MAX, FLT_MAX ), Vec2( -FLT_MAX, -FLT_MAX ));  // Reset AABB
		for (int index : leftIndexes) 
		{
			leftChild->m_aabb.StretchToIncludePoint( m_convexes[index].m_boundingAABB.m_mins );
			leftChild->m_aabb.StretchToIncludePoint( m_convexes[index].m_boundingAABB.m_maxs );
		}
		node->m_childNode.push_back( leftChild );
	}

	if (rightChild) 
	{
		rightChild->m_aabb = AABB2(Vec2( FLT_MAX, FLT_MAX ), Vec2( -FLT_MAX, -FLT_MAX ));  // Reset AABB
		for (int index : rightIndexes) 
		{
			rightChild->m_aabb.StretchToIncludePoint( m_convexes[index].m_boundingAABB.m_mins );
			rightChild->m_aabb.StretchToIncludePoint( m_convexes[index].m_boundingAABB.m_maxs );
		}
		node->m_childNode.push_back( rightChild );
	}

	return node;
}

递归构建 BVH 的代码

在我的场景中，使用 BVH至少比不使用 BVH 快 3 倍。如果修改随机光线的散步范围，性能提升会更大。130k条光线与 8 个多边形相比仅需13 毫秒。

通过BVH 加速求交过程

​射线与多边形求交

红点表示向内点，绿点表示向外点。只有当最后一个红点和第一个绿点的中点位于多边形时，射线才会击中多边形。

射线与多边形求交以及Debug Draw

bool isRaycastVSConvex2D( RaycastResult2D& result, ConvexHull const& convex )
{
	bool isStartOutward = false;
	Vec2 lastInwardIntersection;
	Vec2 firstOutwardIntersection;
	float maxInwardIntersectionDist = 0.f;
	float minOutwardIntersectionDist = FLT_MAX;
	int maxInwardIndex = 0;
	bool hasAnyIntersection = false;
	bool hasAnyInwardIntersection = false;
	bool hasAnyOutwardIntersection = false;

	for (int i = 0; i < convex.m_boundingPlanes.size(); i++)
	{
		Vec2 intersection;
		float intersectionDist = 0.f;
		if (convex.m_boundingPlanes[i].GetIntersection( intersection, result.m_rayStartPosition, result.m_rayDirection, result.m_rayLength, intersectionDist ))
		{
			hasAnyIntersection = true;
			if (!isStartOutward)
			{
				if (convex.m_boundingPlanes[i].isRayInward( result.m_rayDirection ))
				{
					hasAnyInwardIntersection = true;
					if (intersectionDist > maxInwardIntersectionDist)
					{
						maxInwardIntersectionDist = intersectionDist;
						lastInwardIntersection = intersection;
						maxInwardIndex = i;
					}
				}
				else
				{
					hasAnyOutwardIntersection = true;
					if (intersectionDist < minOutwardIntersectionDist)
					{
						minOutwardIntersectionDist = intersectionDist;
						firstOutwardIntersection = intersection;
					}
				}
			}
		}
	}

	if (!hasAnyIntersection)
	{
		result.m_didImpact = false;
		return false;
	}

	//If start point in convex
	if (IsPointInsideConvex( convex, result.m_rayStartPosition ))
	{
		result.m_impactPoint = result.m_rayStartPosition;
		result.m_impactDist = 0.f;
		result.m_impactNormal = -result.m_rayDirection;
		result.m_didImpact = true;
		return true;
	}

	//Use midpoint to check special case
	if (!hasAnyOutwardIntersection)
	{
		firstOutwardIntersection = result.m_rayStartPosition + result.m_rayDirection * result.m_rayLength;
	}
	if (!hasAnyInwardIntersection)
	{
		result.m_didImpact = false;
		return false;
	}
	Vec2 midPoint = (lastInwardIntersection + firstOutwardIntersection) / 2.f;
	if (!IsPointInsideConvex( convex, midPoint ))
	{
		result.m_didImpact = false;
		return false;
	}

	result.m_impactPoint = lastInwardIntersection;
	result.m_impactDist = maxInwardIntersectionDist;
	result.m_impactNormal = convex.m_boundingPlanes[maxInwardIndex].m_normal;
	result.m_didImpact = true;
	return true;
}

射线与多边形求交的代码

截图