Arc drawing routine

The Partridge Family were neither partridges nor a family. Discuss.
albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Arc drawing routine

Post by albinopapa » March 30th, 2019, 4:59 am

Well, I'm not sure about using slopes, but I think I can use some vector math. If you want to use chili's method, you can watch this. The formula used finds the distance to the line from a point ( which I'm going to say is going to be the closest ), but doesn't take into account a point not intersecting within a line segment.

Similarly, using vectors, you can use the dot product to find the closest point on a line, but will have to do more to determine if the point is between the start and end points.

Code: Select all

JC_Point2d ClosesPoint(const JC_Point2d & P, const JC_Point2d & Q, const JC_Point2d & R)
{
	// Calculate direction of line
	const auto line_direction = normalize( Q - P );

	// Calculate distance to nearest point on line from p
	const auto len = dot_product( R - P, line_direction );

	// Scale the direction by the length returned by the dot product, then add back to the start point.
	return P + ( len * line_direction );
}
If you want to, you can probably clamp the return value to either the start point or the end point of the segment.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Arc drawing routine

Post by albinopapa » March 30th, 2019, 3:54 pm

Damn you Jezierro!!!

I stopped programming for 3 months because it started affecting my sleep and now that I wanted to slowly get back into it, you got my head working overtime on these math problems lol. Ever since I looked into your line intersection issue, I've been trying to visualize the problem, because I don't know the formula/algorithm off the top of my head. I went back and watched the video that I linked in the previous post, and I remember thinking back then when it came out that I had issues visualizing the formula.

Your approach using the inverse slope of the line from the test point seemed really close, but there is something missing, but I couldn't figure it out. I almost thought you needed to use the distance from R to P to find your 'b' for the inverted line, but once you use the inverted slope, you end up going the wrong direction. The method chili found on the internet is different than yours and both are different to the one I used. I did however find a forum thread asking the same question and one of the posts used the method I used using vectors and if you really need the closest point on the segment and not just testing if the the point intersects or not, you can clamp the projection length of the point onto the line to between 0 and projection length.

Code: Select all

JC_Point2d ClosesPoint(const JC_Point2d & P, const JC_Point2d & Q, const JC_Point2d & R)
{
	// Calculate direction of line
	const auto line_delta = Q - P;
	const auto line_direction = normalize( line_delta );
	const auto line_length = dot_product( line_delta, line_direction );

	// Calculate distance to nearest point on line from p
	auto projected_len = dot_product( R - P, line_direction );
	projected_len = std::clamp( projected_len, 0.0, line_length );

	// Scale the direction by the length returned by the dot product, then add back to the start point.
	return P + ( projected_len * line_direction );
}
If the projected_len is negative or greater than the line_length, then the clamp function will clamp it to the range 0 to line length. Once you add that back to P, you'll get P, Q or another point that is on the line between P and Q.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

Jezierro
Posts: 36
Joined: March 11th, 2018, 6:02 pm

Re: Arc drawing routine

Post by Jezierro » March 30th, 2019, 8:30 pm

YOU ARE MY GOOD :mrgreen:

Thank you (i have forgot about this vid)

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Arc drawing routine

Post by albinopapa » March 31st, 2019, 6:16 am

Welcome.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Arc drawing routine

Post by albinopapa » April 2nd, 2019, 8:05 pm

Speaking of a Bezier class, thought I'd give it a go and see if I could come up with something more flexible.

Code: Select all

#pragma once

#include <initializer_list>
#include <vector>

template<typename T>
class AnchorPoints
{
public:
	AnchorPoints() = default;
	AnchorPoints( std::initializer_list<T> _points )
		:
		points( std::move( _points ) )
	{

	}
	void AddPoint( const T& _point )noexcept
	{
		points.push_back( _point );
	}

	template<typename...Data> void AddPoint( Data&&... data )
	{
		points.emplace_back( std::forward<Data>( data )... );
	}

	T& operator[]( std::size_t i )
	{
		return points[ i ];
	}

	const T& operator[]( std::size_t i )const
	{
		return points[ i ];
	}

	std::size_t Count()const noexcept
	{
		return points.size();
	}

	std::vector<T>& GetPoints()noexcept
	{
		return points;
	}

	const std::vector<T>& GetPoints()const noexcept
	{
		return points;
	}

private:
	std::vector<T> points;
};

template<typename T>
class Bezier
{
public:
	Bezier() = default;

	Bezier( std::uint32_t numSections, AnchorPoints<T> _anchors )
		:
		sections( numSections ),
		anchors( std::move( _anchors ) )
	{
		points.reserve( sections );

		for( std::uint32_t i = 0u; i <= sections; ++i )
		{
			const auto t = static_cast< float >( i ) / static_cast< float >( sections );
			points.push_back( PlotControlPoint( t ) );
		}
	}

	void SetSectionCount( std::uint32_t numSections )
	{
		( *this ) = Bezier( numSections, std::move( anchors ) );
	}

	void SetAnchorPoints( AnchorPoints<T> _anchors )
	{
		( *this ) = Bezier( sections, std::move( _anchors ) );
	}

	const T& GetControlPoint( std::uint32_t i )const
	{
		return points[ i ];
	}

	std::size_t Count()const noexcept
	{
		return points.size();
	}

	const std::vector<T>& GetControlPoints()const noexcept
	{
		return points;
	}
private:
	
	T PlotControlPoint( float _t )const noexcept
	{
		switch( anchors.Count() )
		{
			case 0: return { 0.f, 0.f };
			case 1: return anchors[ 0 ];
			case 3: return PlotQuadratic( _t );
			case 4: return PlotCubic( _t );
			default: return PlotUknown( _t );	// Also handles linear interpolation of two points
		}
	}

	T PlotQuadratic( float _t )const noexcept
	{
		const auto range0 = ( anchors[ 1 ] - anchors[ 0 ] );
		const auto range1 = ( anchors[ 2 ] - anchors[ 1 ] );
		const auto range2 = ( range1 - range0 );
		const auto doubleRange0 = ( range0 * 2.f );

		
		return anchors[ 0 ] + ( doubleRange0 * _t ) + ( range2 * _t * _t );
	}
	T PlotCubic( float _t )const noexcept
	{
		const auto range10 = anchors[ 1 ] - anchors[ 0 ];
		const auto range21 = anchors[ 2 ] - anchors[ 1 ];
		const auto range32 = anchors[ 3 ] - anchors[ 2 ];

		//( ( p2 - p1 ) - ( p1 - p0 ) )
		const auto range2110 = range21 - range10;

		//( ( p3 - p2 ) - ( p2 - p1 ) )
		const auto range3221 = range32 - range21;

		//( p1 - p0 ) * 3.f
		const auto range10x3 = range10 * 3.f;

		//( ( p2 - p1 ) - ( p1 - p0 ) ) * 3.f
		const auto range2110x3 = range2110 * 3.f;

		//( ( p3 - p2 ) - ( p2 - p1 ) ) - ( ( p2 - p1 ) - ( p1 - p0 ) )
		const auto range3221_2110 = range3221 - range2110;

		const auto t2 = _t * _t;
		const auto t3 = _t * _t * _t;

		return ( anchors[ 0 ] + ( range10x3 * _t ) + ( range2110x3 * t2 ) + ( range3221_2110 * t3 ) );
	}
	T PlotUknown( float _t )const noexcept
	{
		const float it = 1.f - _t;

		auto lerp = [ = ]( const auto& p0, const auto& p1 ) { return ( ( p0 * it ) + ( p1 * _t ) ); };

		std::vector<T> results;
		results.reserve( anchors.Count() );

		// First round, use anchors as source
		for( int i = 0, j = 1; j < anchors.Count(); ++i, ++j )
		{
			results.push_back( lerp( anchors[ i ], anchors[ j ] ) );
		}

		// Remaining rounds, just overwrite results vector, 
		// popping last element off each pass until only one remains
		while( results.size() > std::size_t( 1 ) )
		{
			for( int i = 0, j = 1; j < results.size(); ++i, ++j )
			{
				results[ i ] = lerp( results[ i ], results[ j ] );
			}

			results.pop_back();
		}

		return results.front();
	}


private:
	AnchorPoints<T> anchors;
	std::vector<T> points;
	std::uint32_t sections = 1u;
};

template<typename T> AnchorPoints( std::initializer_list<T> )->AnchorPoints<T>;
template<typename T> Bezier( AnchorPoints<T> )->Bezier<T>;

To create a Bezier instance, you first create an AnchorPoints object and fill it with data

Code: Select all

// Using JC_Point2d as control points
AnchorPoints<JC_Point2d> anchors;
To add anchor points

Code: Select all

// Using JC_Point2d and an initializer list
AnchorPoints<JC_Point2d> anchors = 
	{
		JC_Point2d( -100.0, -100.0 ),
		JC_Point2d( 100.0, -100.0 ),
		JC_Point2d( 100.0, 100.0 ),
		JC_Point2d( -100.0, 100.0 )
	};

// Using JC_Point2d and the AddPoint() function
anchors.AddPoint( -100.0, -100.0  );
anchors.AddPoint( 100.0, -100.0 );
anchors.AddPoint( 100.0,  100.0 );
anchors.AddPoint( -100.0,  100.0 );

// You can also explicitly use std::initializer_list and have AnchorPoints type be deduced:
AnchorPoints anchors = std::initializer_list<JC_Point2d>{
		JC_Point2d( -100.0, -100.0 ),
		JC_Point2d( 100.0, -100.0 ),
		JC_Point2d( 100.0, 100.0 ),
		JC_Point2d( -100.0, 100.0 )
	};

To create the Bezier class instance

Code: Select all

	// Since this constructor takes an AnchorPoints object, the type of 
	// Bezier object can be deduced, so no need for the template parameter
	Bezier curve( 20, anchors );

	// If you create a Bezier object using the default constructor, you must 
	// provide the template parameter and then use the SetAnchorPoints() AND
	// the SetSectionCount() functions.
	Bezier<double> dCurve;
	dCurve.SetSectionCount( 20 );
	dCurve.SetAnchorPoints( std::move( dAnchors ) );

	//or just copy assign a new instance, which is more efficient.
	dCurve = Bezier( 20, std::move( dAnchors ) );
Getting the control points

Code: Select all

	// Get all control points
	const auto& points = curve.GetControlPoints();

	// Get individual control point
	const auto& point = curve.GetControlPoint( 0 );
So, say you wanted to use it to animate an Entity along a path, you would have a check to see if the object was near the control point, if it is, increment a counter to have the object go to the next control point.

Code: Select all

class Entity
{
public:
	void Update( float _dt )noexcept
	{
		// update velocity
		const auto delta = path.GetControlPoint( counter ) - position;
		const auto heading = normalize( delta );
		velocity = heading * ( _dt * speed );
		
		if( dot_product( delta, heading ) <= minRange )
		{
			++counter;
		}
		
		if( counter >= path.Count();
		{
			velocity = {0.f, 0.f}
			counter = 0;
		}
		
		position += velocity;
	}
private:
	static constexpr int maxPathPoints = 20;
	static constexpr float speed = 180.f;
	static constexpr float minRange = 3.f;
	Bezier<JC_Point2d> path;
	JC_Point2f position = {0.f, 0.f};
	JC_Vector2f velocity = {0.f, 0.f};
	int counter = 0;
};
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

Post Reply