2D algorithms

[albinopapa]

Motivation
I'm lazy, or just tired of writing the same shizz over and over anyway. So, I figured why not create some algorithms that loosely mimic the STL.

Copying one 2d array to another

Code: Select all

template<typename Cont1, typename Cont2, typename RectType>
void copy2d( const RectType& _bounds, const Cont1& _source, Cont2& _dest )
{
	using type_1 = typename Cont1::value_type;
	using type_2 = typename Cont2::value_type;
	static_assert( std::is_same_v<type_1,type_2>,
		"Container::value_type must be the same for both containers."
		);
	
	const auto width = _bounds.Width();

	for( int y = _bounds.Top(); y < _bounds.Bottom(); ++y )
	{
		if constexpr( std::is_trivially_copyable_v<type_1> )
		{
			memcpy( std::addressof( _dest( 0, y ) ), std::addressof( _source( 0, y ) ), sizeof( type_1 ) * width );
		}
		else
		{
			for( int x = _bounds.Left(); x < _bounds.Right(); ++x )
			{
				_dest( x, y ) = _source( x, y );
			}
		}
	}
}

Copy regions of one 2D array to another

Code: Select all

template<typename Cont1, typename Cont2, typename RectType>
void copy2d( const RectType& _srcBounds, const RectType& _dstBounds, const Cont1& _source, Cont2& _dest )
{
	using type_1 = typename Cont1::value_type;
	using type_2 = typename Cont2::value_type;
	static_assert( std::is_same_v<type_1, type_2>,
		"Container::value_type must be the same for both containers."
		);

	assert(
		_srcBounds.Width() == _dstBounds.Width() &&
		_srcBounds.Height() == _dstBounds.Height() &&
		"Source and destination RectTypes must be same dimensions." );

	const auto stride = sizeof( type_1 ) * _srcBounds.Width();
	for( int y = _srcBounds.Top(); y < _srcBounds.Bottom(); ++y )
	{
		const auto srcy = y + _srcBounds.Top();
		const auto dsty = y + _dstBounds.Top();
		if constexpr( std::is_trivially_copyable_v<type_1> )
		{
			auto* dst = std::addressof( _dest( _dstBounds.Left(), dsty ) );
			auto const* src = std::addressof( _source( _srcBounds.Left(), srcy ) );
			memcpy( dst, src, stride );
		}
		else
		{
			for( int x = _srcBounds.Left(); x < _srcBounds.Right(); ++x )
			{
				for( int x = 0; x < _srcBounds.Width(); ++x )
				{
					const auto srcx = x + _srcBounds.Left();
					const auto dstx = x + _dstBounds.Left();

					_dest( dstx, dsty ) = _source( srcx, srcy );
				}
			}
		}
	}
}

Conditionally copy regions

Code: Select all

template<typename Cont1, typename Cont2, typename RectType, typename Pred>
void copy2d_if(
	const RectType& _srcBounds, const RectType& _dstBounds, const Cont1& _source, Cont2& _dest,
	Pred&& _pred )
{
	using type_1 = typename Cont1::value_type;
	using type_2 = typename Cont2::value_type;
	static_assert( std::is_same_v<type_1, type_2>,
		"Container::value_type must be the same for both containers."
		);

	assert(
		_srcBounds.Width() == _dstBounds.Width() &&
		_srcBounds.Height() == _dstBounds.Height() &&
		"Source and destination RectTypes must be same dimensions." );

	for( int y = 0; y < _srcBounds.Height(); ++y )
	{
		const auto srcy = y + _srcBounds.Top();
		const auto dsty = y + _dstBounds.Top();
		
		for( int x = 0; x < _srcBounds.Width(); ++x )
		{
			const auto srcx = x + _srcBounds.Left();
			const auto dstx = x + _dstBounds.Left();

			if( const auto& elem = _source( srcx, srcy ); _pred( elem ) )
				_dest( dstx, dsty ) = elem;
		}
	}
}

Generic iterate over region

Code: Select all

template<typename Cont, typename RectType, typename Func>
void for_each2d( const RectType& _bounds, Cont& _container, Func&& _func )
{
	for( std::int32_t y = _bounds.Top(); y < _bounds.Bottom(); ++y )
	{
		for( std::int32_t x = _bounds.Left(); x < _bounds.Right(); ++x )
		{
			_func( _container( x, y ) );
		}
	}
}

Fill a region with a single value

Code: Select all

template<typename Cont, typename RectType>
void fill2d( const typename Cont::value_type& _value, const RectType& _bounds, Cont& _container )
{
	for( int y = _bounds.Top(); y < _bounds.Bottom(); ++y )
	{
		for( int x = _bounds.Left(); x < _bounds.Right(); ++x )
		{
			_container( x, y ) = _value;
		}
	}
}

Generate result from some function

Code: Select all

template<typename Cont, typename RectType, typename Generator>
void generate2d( const RectType& _bounds, Cont& _cont, Generator&& _generate )
{
	for( int y = _bounds.Top(); y < _bounds.Bottom(); ++y )
	{
		for( int x = _bounds.Left(); x < _bounds.Right(); ++x )
		{
			_cont( x, y ) = _generate();
		}
	}
}

Replace specified value with a different value

Code: Select all

template<typename Cont1, typename Cont2, typename RectType>
void replace2d(
	const typename Cont1::value_type& _replace_value, 
	const typename Cont2::value_type& _with_value, 
	const RectType& _srcBounds, 
	const RectType& _dstBounds, 
	const Cont1& _src,
	Cont2& _dst)
{
	using type_1 = typename Cont1::value_type;
	using type_2 = typename Cont2::value_type;
	static_assert( std::is_same_v<type_1, type_2>,
		"Container::value_type must be the same for both containers."
		);

	assert(
		_srcBounds.Width() == _dstBounds.Width() &&
		_srcBounds.Height() == _dstBounds.Height() &&
		"Source and destination RectTypes must be same dimensions." );

	for( int y = 0; y < _srcBounds.height; ++y )
	{
		const auto srcy = y + _srcBounds.Top();
		const auto dsty = y + _dstBounds.Top();

		for( int x = 0; x < _srcBounds.width; ++x )
		{
			const auto srcx = x + _srcBounds.Left();
			const auto dstx = x + _dstBounds.Left();

			if( _src( srcx, srcy ) == _replace_value )
				_dst( dstx, dsty ) = _with_value;
		}
	}
}

Replace values in destination with source depending on result of call to Pred

Code: Select all

template<typename Cont1, typename Cont2, typename RectType, typename Pred>
void replace2d_if(
	const typename Cont1::value_type& _new_value,
	const RectType& _srcBounds,
	const RectType& _dstBounds,
	const Cont1& _src, 
	Cont2& _dst,
	Pred&& _pred )
{
	assert(
		_srcBounds.Width() == _dstBounds.Width() &&
		_srcBounds.Height() == _dstBounds.Height() &&
		"Source and destination RectTypes must be same dimensions." );

	for( int y = 0; y < _srcBounds.height; ++y )
	{
		const auto srcy = y + _srcBounds.Top();
		const auto dsty = y + _dstBounds.Top();

		for( int x = 0; x < _srcBounds.width; ++x )
		{
			const auto srcx = x + _srcBounds.Left();
			const auto dstx = x + _dstBounds.Left();

			const auto& srcElement = _src( srcx, srcy );
			auto& dstElement = _dst( dstx, dsty );

			if( _pred( srcElement, dstElement ) )
			{
				dstElement = _new_value;
			}
		}
	}
}

Transform source element and assign to destination element

Code: Select all

template<typename Cont1, typename Cont2, typename RectType, typename Func>
void transform2d(
	const RectType& _srcBounds, const RectType& _dstBounds,
	const Cont1& _src, Cont2& _dst, Func&& _func )
{
	using type_1 = typename Cont1::value_type;
	using type_2 = typename Cont2::value_type;
	static_assert( std::is_same_v<type_1, type_2>,
		"Container::value_type must be the same for both containers."
		);

	assert(
		_srcBounds.Width() == _dstBounds.Width() &&
		_srcBounds.Height() == _dstBounds.Height() &&
		"Source and destination RectTypes must be same dimensions." );

	for( int y = 0; y < _srcBounds.height; ++y )
	{
		const auto srcy = y + _srcBounds.Top();
		const auto dsty = y + _dstBounds.Top();

		for( int x = 0; x < _srcBounds.width; ++x )
		{
			const auto srcx = x + _srcBounds.Left();
			const auto dstx = x + _dstBounds.Left();

			_dst( dstx, dsty ) = _func( _src( srcx, srcy ) );
		}
	}
}

Transform using two source pixels and assigning the result to destination element

Code: Select all

template<typename Cont1, typename Cont2, typename Cont3, typename RectType, typename Func>
void transform2d(
	const RectType& _srcBounds1, const RectType& _srcBounds2, const RectType& _dstBounds,
	const Cont1& _src1, const Cont1& _src2, Cont2& _dst, Func&& _func )
{
	using type_1 = typename Cont1::value_type;
	using type_2 = typename Cont2::value_type;
	using type_3 = typename Cont3::value_type;
	static_assert( std::conjunction_v<std::is_same<type_1, type_2>,std::is_same<type_2, type_3>>,
		"Container::value_type must be the same for all three containers."
		);

	assert(
		_srcBounds1.Width() ==  _dstBounds.Width() &&
		_srcBounds1.Height() == _dstBounds.Height() &&
		_srcBounds2.Width() == _srcBounds1.Width() && 
		_srcBounds2.Height() == _srcBounds1.Height() &&
		"Source and destination RectTypes must be same dimensions." );

	for( int y = 0; y < _srcBounds.height; ++y )
	{
		const auto srcy1 = y + _srcBounds1.Top();
		const auto srcy2 = y + _srcBounds2.Top();
		const auto dsty = y + _dstBounds.Top();

		for( int x = 0; x < _srcBounds.width; ++x )
		{
			const auto srcx1 = x + _srcBounds1.Left();
			const auto srcx2 = x + _srcBounds2.Left();
			const auto dstx = x + _dstBounds.Left();

			_dst( dstx, dsty ) = _func( _src1( srcx1, srcy1 ), _src2( srcx2, srcy2 ) );
		}
	}
}

[albinopapa]

To use these algorithms, some conditions must be met.

You must have a Rect class/struct with Left(), Top(), Right(), Bottom(), Width() and Height() member functions. You can define your Rect class however you like as long as those functions are there and return values that are associated with those names.

You must create containers ( Texture class, Sprite class, Surface class, etc ) with the call operator overloaded ( operator() ). One non-const version is used for setting values, and a const version for getting values. It must take an X and Y parameter which you will use to flatten into a 1D index and return back a value.

Your container must have a value_type alias, this helps the algorithms to detect of you are trying to assign mismatched values.

Example container

Code: Select all

class Array2D
{
public:
   using value_type = int;
public:
   value_type& operator()( int x, int y )noexcept
   {
      assert( x >= 0 );
      assert( x < width );
      assert( y >= 0 );
      assert( y < height );
      return buffer[x + ( y * width )];
   }
   const value_type& operator()( int x, int y )const noexcept
   {
      assert( x >= 0 );
      assert( x < width );
      assert( y >= 0 );
      assert( y < height );
      return buffer[x + ( y * width )];
   }

private:
   int width = 0, height = 0;
   std::unique_ptr<value_type[]> buffer;
};

[albinopapa]

Now, really I can only think of image processing that uses two dimensions that would benefit from these algorithms, so here's a few examples using them in that way.

Code: Select all

void D3DGraphics::BeginFrame()noexcept
{
	fill2d( Colors::black, RectI{ 0,0,ScreenWidth,ScreenHeight }, surface );
}

Code: Select all

void D3DGraphics::EndFrame()
{
	{
		// Custom wrapper for locking/unlocking the back buffer
		// as well as copying pixels to the back buffer
		D3D9RenderTarget target( pBackBuffer.Get() );
		copy2d( RectI{ 0, 0, ScreenWidth, ScreenHeight }, surface, target );
	}

	const auto result = pDevice->Present( nullptr, nullptr, nullptr, nullptr );
	assert( !FAILED( result ) );
}

Code: Select all

void D3DGraphics::DrawSprite( int xoff, int yoff, const Sprite& sprite )noexcept
{	
	auto notIsAlpha = [ & ]( const Color& _color ) { return !sprite.IsKey( _color ); };

	const auto srcRect = RectI{ 0,0,int( sprite.Width() ),int( sprite.Height() ) };
	const auto dstRect = RectI{ xoff,yoff,int( sprite.Width() ),int( sprite.Height() ) };

	copy2d_if( srcRect, dstRect, sprite, surface, notIsAlpha );
}

Code: Select all

void D3DGraphics::DrawChar( char c, int xoff, int yoff, const Font& font, Color color )noexcept
{
	const auto srcRect = font.CharRect( c );
	const auto dstRect = RectI{ 
		xoff,
		yoff,
		srcRect.width,
		srcRect.height 
	};

	replace2d( Colors::black, color, srcRect, dstRect, font, surface );
}

Code: Select all

void D3DGraphics::DrawDisc( int cx, int cy, int r, Color color )noexcept
{
	auto Square = []( auto _value ) {return _value * _value; };

	const auto rSq = Square( r );
	const auto dstRect = RectI{ cx - r,cy - r,r * 2,r * 2 };
	int index = 0;

	auto generate_disc = [ & ]()
	{
		const auto y = ( index / dstRect.width ) - r;
		const auto x = ( index % dstRect.width ) - r;

		++index;

		const auto distSq = Square( x ) + Square( y );

		return ( distSq < rSq ) ? color : surface( x + cx, y + cy );
	};

	generate2d( dstRect, surface, generate_disc );
}

Code: Select all

void D3DGraphics::DrawCircle( int cx, int cy, int radius, Color color )noexcept
{
	if( radius == 0 )return;

	const auto iRadSq = sq( radius - 1 );
	const auto oRadSq = sq( radius );
	const auto bounds =
		ClipToScreen( cx - radius, cy - radius, radius * 2, radius * 2 ) + Vec2i( cx, cy );

	int i = 0;
	for_each2d( bounds, surface, [ & ]( Color& dest )
	{
		const int x = ( i % bounds.width ) - radius;
		const int y = ( i / bounds.width ) - radius;
		const auto distSq = sq( x ) + sq( y );

		++i;
		if( distSq >= iRadSq && distSq < oRadSq )
		{
			dest = color;
		}
	} );
}

Code: Select all

void D3DGraphics::DrawRectangle( const RectI& _rect, Color color )noexcept
{
	fill2d( color, _rect, surface );
}

Code: Select all

void D3DGraphics::DrawSpriteAlphaBlend( int x, int y, const Sprite & sprite ) noexcept
{
	auto AlphaBlend = []( const Color src1, const Color src2 )
	{
		const auto alpha = src1.GetA();
		const auto iAlpha = 255u - alpha;

		return Color(
			( ( src1.GetR() * alpha ) + ( src2.GetR() * iAlpha ) ) >> 8u,
			( ( src1.GetG() * alpha ) + ( src2.GetG() * iAlpha ) ) >> 8u,
			( ( src1.GetB() * alpha ) + ( src2.GetB() * iAlpha ) ) >> 8u
		);
	};

	const auto srcRect = RectI( 0, 0, sprite.Width(), sprite.Height() );
	const auto dstRect = RectI( x, y, sprite.Width(), sprite.Height() );
	transform2d(
		srcRect, dstRect, dstRect,
		sprite, surface, surface,
		AlphaBlend );
}

[albinopapa]

You'll have to clip the bounding rectangles to the screen as to not draw off screen. Here's a good function that will return you back a clipped to screen rectangle.

Code: Select all

RectI D3DGraphics::ClipToScreen( const RectI & rect ) const noexcept
{
	return {
		std::max( -rect.Left(), 0 ),						
		std::max( -rect.Top(), 0 ),						
		std::min( ScreenWidth - rect.Left(),rect.Width() ),	
		std::min( ScreenHeight - rect.Top(),rect.Height() )	
	};
}

I just found myself using in every draw function, so I just put it in a function in itself.

A more generalized one for other uses:

Code: Select all

template<typename RectType>
RectType ClipRectToRect( const RectType& rect, const RectType& bounds )
{
	assert( bounds.Width() > rect.Width() );
	assert( bounds.Height() > rect.Height() );

	return RectType{
		std::max( -rect.Left(), bounds.Left() ),
		std::max( -rect.Top(), bounds.Top() ),
		std::min( bounds.Width() - rect.Left(), rect.Width() ),
		std::min( bounds.Height() - rect.Top(), rect.Height() )
	};
}

[chili]

These generic functions look like they would come in handy in a bunch of places

[albinopapa]

Yeah, am testing them out in another scenario besides graphics right now actually, well sort of. Remember the maze project I made a few years back? Well, I never really could figure out a good way of procedurally generating collision tiles. It's been coming up in the back of my mind every so often and I think I have a plan.