Detour/Source/DetourCommon.cpp
void dtRandomPointInConvexPoly(const float* pts, const int npts, float* areas,
							   const float s, const float t, float* out)
{
	// Calc triangle araes
	float areasum = 0.0f;
	for (int i = 2; i < npts; i++) {
		areas[i] = dtTriArea2D(&pts[0], &pts[(i-1)*3], &pts[i*3]);
		areasum += dtMax(0.001f, areas[i]);
	}
	// Find sub triangle weighted by area.
	const float thr = s*areasum;
	float acc = 0.0f;
	float u = 1.0f;
	int tri = npts - 1;
	for (int i = 2; i < npts; i++) {
		const float dacc = areas[i];
		if (thr >= acc && thr < (acc+dacc))
		{
			u = (thr - acc) / dacc;
			tri = i;
			break;
		}
		acc += dacc;
	}
	
	float v = dtMathSqrtf(t);
	
	const float a = 1 - v;
	const float b = (1 - u) * v;
	const float c = u * v;
	const float* pa = &pts[0];
	const float* pb = &pts[(tri-1)*3];
	const float* pc = &pts[tri*3];
	
	out[0] = a*pa[0] + b*pb[0] + c*pc[0];
	out[1] = a*pa[1] + b*pb[1] + c*pc[1];
	out[2] = a*pa[2] + b*pb[2] + c*pc[2];
}
// Returns a random point in a convex polygon.
// Adapted from Graphics Gems article.
Returns a random point in a convex polygon.
Adapted from Graphics Gems article.
Returns a random point in a convex polygon . Adapted from Graphics Gems article .
void dtRandomPointInConvexPoly(const float* pts, const int npts, float* areas,
							   const float s, const float t, float* out)
{
	float areasum = 0.0f;
	for (int i = 2; i < npts; i++) {
		areas[i] = dtTriArea2D(&pts[0], &pts[(i-1)*3], &pts[i*3]);
		areasum += dtMax(0.001f, areas[i]);
	}
	const float thr = s*areasum;
	float acc = 0.0f;
	float u = 1.0f;
	int tri = npts - 1;
	for (int i = 2; i < npts; i++) {
		const float dacc = areas[i];
		if (thr >= acc && thr < (acc+dacc))
		{
			u = (thr - acc) / dacc;
			tri = i;
			break;
		}
		acc += dacc;
	}
	float v = dtMathSqrtf(t);
	const float a = 1 - v;
	const float b = (1 - u) * v;
	const float c = u * v;
	const float* pa = &pts[0];
	const float* pb = &pts[(tri-1)*3];
	const float* pc = &pts[tri*3];
	out[0] = a*pa[0] + b*pb[0] + c*pc[0];
	out[1] = a*pa[1] + b*pb[1] + c*pc[1];
	out[2] = a*pa[2] + b*pb[2] + c*pc[2];
}
void dtRandomPointInConvexPoly ( const float * pts , const int npts , float * areas , const float s , const float t , float * out ) { float areasum = 0.0f ; for ( int i = 2 ; i < npts ; i ++ ) { areas [ i ] = dtTriArea2D ( & pts [ 0 ] , & pts [ ( i - 1 ) * 3 ] , & pts [ i * 3 ] ) ; areasum += dtMax ( 0.001f , areas [ i ] ) ; } const float thr = s * areasum ; float acc = 0.0f ; float u = 1.0f ; int tri = npts - 1 ; for ( int i = 2 ; i < npts ; i ++ ) { const float dacc = areas [ i ] ; if ( thr >= acc && thr < ( acc + dacc ) ) { u = ( thr - acc ) / dacc ; tri = i ; break ; } acc += dacc ; } float v = dtMathSqrtf ( t ) ; const float a = 1 - v ; const float b = ( 1 - u ) * v ; const float c = u * v ; const float * pa = & pts [ 0 ] ; const float * pb = & pts [ ( tri - 1 ) * 3 ] ; const float * pc = & pts [ tri * 3 ] ; out [ 0 ] = a * pa [ 0 ] + b * pb [ 0 ] + c * pc [ 0 ] ; out [ 1 ] = a * pa [ 1 ] + b * pb [ 1 ] + c * pc [ 1 ] ; out [ 2 ] = a * pa [ 2 ] + b * pb [ 2 ] + c * pc [ 2 ] ; }
Returns a random point in a convex polygon.
Returns a random point in a convex polygon .
// Calc triangle araes // Find sub triangle weighted by area.