fork download
copy 
  1. #include <cstdio>
  2. #include <cmath>
  3.  
  4. // vec2 definition:
  5. //==============================================================================
  6.  
  7. template<typename T>
  8. class vec2
  9. {
  10. public:
  11.     vec2()=default;
  12.     vec2(const T &x,const T &y):r{x,y} {};
  13.     explicit vec2(const T *src):r{src[0],src[1]} {};
  14.     vec2(const vec2 &src)=default;
  15.  
  16.     vec2<T> &operator=(const vec2 &src)=default;
  17.  
  18.     vec2<T> &operator+=(const vec2 &src)
  19.     {
  20.         for(int i=0;i<2;++i) r[i]+=src.r[i];
  21.         return *this;
  22.     };
  23.     vec2<T> &operator-=(const vec2 &src)
  24.     {
  25.         for(int i=0;i<2;++i) r[i]-=src.r[i];
  26.         return *this;
  27.     };
  28.     vec2<T> &operator*=(const T &s)
  29.     {
  30.         for(int i=0;i<2;++i) r[i]*=s;
  31.         return *this;
  32.     };
  33.     vec2<T> &operator/=(const T &s)
  34.     {
  35.         for(int i=0;i<2;++i) r[i]/=s;
  36.         return *this;
  37.     };
  38.  
  39.     const vec2<T> operator+() const {return {+r[0],+r[1]};};
  40.     const vec2<T> operator-() const {return {-r[0],-r[1]};};
  41.  
  42.     friend const vec2<T> operator+(const vec2<T> &l,const vec2<T> &r)
  43.     {
  44.         return {l.r[0]+r.r[0],l.r[1]+r.r[1]};
  45.     };
  46.     friend const vec2<T> operator-(const vec2<T> &l,const vec2<T> &r)
  47.     {
  48.         return {l.r[0]-r.r[0],l.r[1]-r.r[1]};
  49.     };
  50.  
  51.     friend const vec2<T> operator*(const vec2<T> &l,const T &r)
  52.     {
  53.         return {l.r[0]*r,l.r[1]*r};
  54.     };
  55.     friend const vec2<T> operator*(const T &l,const vec2<T> &r)
  56.     {
  57.         return {l*r.r[0],l*r.r[1]};
  58.     };
  59.     friend const vec2<T> operator/(const vec2<T> &l,const T &r)
  60.     {
  61.         return {l.r[0]/r,l.r[1]/r};
  62.     };
  63.  
  64.     friend const T operator*(const vec2<T> &l,const vec2<T> &r)
  65.     {
  66.         return l.r[0]*r.r[0]+l.r[1]*r.r[1];
  67.     };
  68.     friend const T operator%(const vec2<T> &l,const vec2<T> &r)
  69.     {
  70.         return l.r[0]*r.r[1]-l.r[1]*r.r[0];
  71.     };
  72.  
  73.     friend bool operator==(const vec2<T> &l,const vec2<T> &r)
  74.     {
  75.         return (l.r[0]==r.r[0]&&l.r[1]==r.r[1]);
  76.     };
  77.     friend bool operator!=(const vec2<T> &l,const vec2<T> &r)
  78.     {
  79.         return (l.r[0]!=r.r[0]||l.r[1]!=r.r[1]);
  80.     };
  81.  
  82.     static const vec2<T> mul(const vec2<T> &l,const vec2<T> &r)
  83.     {
  84.         return {l[0]*r[0],l[1]*r[1]};
  85.     };
  86.  
  87.     T &operator[](int i) {return r[i];};
  88.     const T &operator[](int i) const {return r[i];};
  89.  
  90.     template<typename S>
  91.     const vec2<S> convert() const {return vec2<S>{S(r[0]),S(r[1])};};
  92.  
  93.     T *data() {return r;};
  94.     const T *data() const {return r;};
  95. private:
  96.     T r[2];
  97. };
  98.  
  99. //==============================================================================
  100. // End of vec2 definition.
  101.  
  102. typedef vec2<float> vec2f;
  103.  
  104. vec2f catmull_rom(
  105. 	const vec2f &p0,
  106. 	const vec2f &p1,
  107. 	const vec2f &m0,
  108. 	const vec2f &m1,
  109. 	float t
  110. 	)
  111. {
  112. 	return
  113. 		(2.0f*t*t*t-3.0f*t*t+1.0f)*p0+
  114. 		(t*t*t-2.0f*t*t+t)*m0+
  115. 		(-2.0f*t*t*t+3.0f*t*t)*p1+
  116. 		(t*t*t-t*t)*m1;
  117. }
  118.  
  119. vec2f catmull_rom_deriv(
  120. 	const vec2f &p0,
  121. 	const vec2f &p1,
  122. 	const vec2f &m0,
  123. 	const vec2f &m1,
  124. 	float t)
  125. {
  126. 	return
  127. 		(6.0f*t*t-6.0f*t)*p0+
  128. 		(3.0f*t*t-4.0f*t+1.0f)*m0+
  129. 		(-6.0f*t*t+6.0f*t)*p1+
  130. 		(3.0f*t*t-2.0f*t)*m1;
  131. }
  132.  
  133. float catmull_rom_length(
  134. 	const vec2f &p0,
  135. 	const vec2f &p1,
  136. 	const vec2f &m0,
  137. 	const vec2f &m1,
  138. 	float t0,
  139. 	float t1,
  140. 	float eps)
  141. {
  142. 	if(t1<t0)
  143. 		return -catmull_rom_length(p0,p1,m0,m1,t1,t0,eps);
  144. 	if(t1-t0>eps)
  145. 	{
  146. 		float tm=0.5f*(t0+t1);
  147. 		return
  148. 			catmull_rom_length(p0,p1,m0,m1,t0,tm,eps)+
  149. 			catmull_rom_length(p0,p1,m0,m1,tm,t1,eps);
  150. 	}
  151. 	else
  152. 	{
  153. 		vec2f d=
  154. 			catmull_rom(p0,p1,m0,m1,t1)-
  155. 			catmull_rom(p0,p1,m0,m1,t0);
  156. 		return std::sqrt(d*d);
  157. 	}
  158. }
  159.  
  160. //==============================================================================
  161.  
  162. float catmull_rom_dt_1(
  163. 	const vec2f &p0,
  164. 	const vec2f &p1,
  165. 	const vec2f &m0,
  166. 	const vec2f &m1,
  167. 	float t,
  168. 	float ds)
  169. {
  170. 	vec2f v=catmull_rom_deriv(p0,p1,m0,m1,t);
  171. 	return ds/std::sqrt(v*v);
  172. }
  173.  
  174. float catmull_rom_dt_2(
  175. 	const vec2f &p0,
  176. 	const vec2f &p1,
  177. 	const vec2f &m0,
  178. 	const vec2f &m1,
  179. 	float t,
  180. 	float ds)
  181. {
  182. 	vec2f v0=catmull_rom_deriv(p0,p1,m0,m1,t);
  183. 	float dt0=
  184. 		ds/std::sqrt(v0*v0);
  185. 	vec2f v1=catmull_rom_deriv(p0,p1,m0,m1,t+dt0);
  186. 	float
  187. 		a=0.5f*(std::sqrt(v1*v1)-std::sqrt(v0*v0))/dt0,
  188. 		b=std::sqrt(v0*v0),
  189. 		c=-ds;
  190. 	return -c/b-a*c*c/(b*b*b);
  191. }
  192.  
  193. //==============================================================================
  194.  
  195. void print_vec(const vec2f &v)
  196. {
  197. 	printf("{%f,%f}\n",v[0],v[1]);
  198. }
  199.  
  200. //==============================================================================
  201.  
  202. int main()
  203. {
  204. 	vec2f
  205. 		p0={0.0f,0.0f},
  206. 		p1={1.0f,0.0f},
  207. 		m0={1.0f,1.0f},
  208. 		m1={0.0f,-1.0f};
  209.  
  210. 	printf("Length measurement test:\n");
  211. 	for(int i=0;i<2;++i)
  212. 	{
  213. 		const float eps=
  214. 			i==0?
  215. 			1.0f/256.0f:
  216. 			1.0f/4096.0f;
  217. 		printf("  eps=%f:\n",eps);
  218. 		for(float t=0.0f;t<=1.0f;t+=0.125f)
  219. 			printf("    t=%f: length=%f\n",
  220. 				t,
  221. 				catmull_rom_length(
  222. 					p0,p1,m0,m1,
  223. 					0.0f,t,
  224. 					eps));
  225. 	}
  226. 	printf("\n");
  227. 	printf("Stepping test:\n");
  228. 	for(int i=0;i<2;++i)
  229. 	{
  230. 		const float ds=
  231. 			i==0?
  232. 			1.0f/64.0f:
  233. 			1.0f/5.0f;
  234. 		printf("  step=%f\n",ds);
  235. 		printf("Version 1:\n");
  236. 		for(float t=0.0f,s=0.0f;t<1.0f;)
  237. 		{
  238. 			printf("  s=%f: delta=%+f\n",
  239. 				s,
  240. 				catmull_rom_length(
  241. 					p0,p1,m0,m1,
  242. 					0.0f,t,
  243. 					1.0f/4096.0f)-s);
  244. 			t+=catmull_rom_dt_1(p0,p1,m0,m1,t,ds);
  245. 			s+=ds;
  246. 		}
  247. 		printf("Version 2:\n");
  248. 		for(float t=0.0f,s=0.0f;t<1.0f;)
  249. 		{
  250. 			printf("  s=%f: delta=%+f\n",
  251. 				s,
  252. 				catmull_rom_length(
  253. 					p0,p1,m0,m1,
  254. 					0.0f,t,
  255. 					1.0f/4096.0f)-s);
  256. 			t+=catmull_rom_dt_2(p0,p1,m0,m1,t,ds);
  257. 			s+=ds;
  258. 		}
  259. 		printf("\n");
  260. 	}
  261. 	return 0;
  262. }
Success #stdin #stdout 0.04s 3100KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Length measurement test:
  eps=0.003906:
    t=0.000000: length=0.000000
    t=0.125000: length=0.176997
    t=0.250000: length=0.353713
    t=0.375000: length=0.526446
    t=0.500000: length=0.689539
    t=0.625000: length=0.837171
    t=0.750000: length=0.965756
    t=0.875000: length=1.078702
    t=1.000000: length=1.193369
  eps=0.000244:
    t=0.000000: length=0.000000
    t=0.125000: length=0.176997
    t=0.250000: length=0.353714
    t=0.375000: length=0.526447
    t=0.500000: length=0.689540
    t=0.625000: length=0.837171
    t=0.750000: length=0.965757
    t=0.875000: length=1.078704
    t=1.000000: length=1.193373

Stepping test:
  step=0.015625
Version 1:
  s=0.000000: delta=+0.000000
  s=0.015625: delta=+0.000000
  s=0.031250: delta=+0.000001
  s=0.046875: delta=+0.000003
  s=0.062500: delta=+0.000005
  s=0.078125: delta=+0.000008
  s=0.093750: delta=+0.000010
  s=0.109375: delta=+0.000013
  s=0.125000: delta=+0.000015
  s=0.140625: delta=+0.000017
  s=0.156250: delta=+0.000018
  s=0.171875: delta=+0.000019
  s=0.187500: delta=+0.000020
  s=0.203125: delta=+0.000019
  s=0.218750: delta=+0.000017
  s=0.234375: delta=+0.000014
  s=0.250000: delta=+0.000011
  s=0.265625: delta=+0.000006
  s=0.281250: delta=-0.000001
  s=0.296875: delta=-0.000009
  s=0.312500: delta=-0.000018
  s=0.328125: delta=-0.000029
  s=0.343750: delta=-0.000042
  s=0.359375: delta=-0.000057
  s=0.375000: delta=-0.000073
  s=0.390625: delta=-0.000091
  s=0.406250: delta=-0.000112
  s=0.421875: delta=-0.000134
  s=0.437500: delta=-0.000159
  s=0.453125: delta=-0.000186
  s=0.468750: delta=-0.000216
  s=0.484375: delta=-0.000248
  s=0.500000: delta=-0.000282
  s=0.515625: delta=-0.000319
  s=0.531250: delta=-0.000359
  s=0.546875: delta=-0.000402
  s=0.562500: delta=-0.000448
  s=0.578125: delta=-0.000497
  s=0.593750: delta=-0.000549
  s=0.609375: delta=-0.000604
  s=0.625000: delta=-0.000663
  s=0.640625: delta=-0.000725
  s=0.656250: delta=-0.000792
  s=0.671875: delta=-0.000862
  s=0.687500: delta=-0.000936
  s=0.703125: delta=-0.001014
  s=0.718750: delta=-0.001096
  s=0.734375: delta=-0.001183
  s=0.750000: delta=-0.001275
  s=0.765625: delta=-0.001371
  s=0.781250: delta=-0.001473
  s=0.796875: delta=-0.001579
  s=0.812500: delta=-0.001690
  s=0.828125: delta=-0.001807
  s=0.843750: delta=-0.001929
  s=0.859375: delta=-0.002055
  s=0.875000: delta=-0.002187
  s=0.890625: delta=-0.002323
  s=0.906250: delta=-0.002463
  s=0.921875: delta=-0.002607
  s=0.937500: delta=-0.002752
  s=0.953125: delta=-0.002899
  s=0.968750: delta=-0.003044
  s=0.984375: delta=-0.003186
  s=1.000000: delta=-0.003321
  s=1.015625: delta=-0.003444
  s=1.031250: delta=-0.003553
  s=1.046875: delta=-0.003640
  s=1.062500: delta=-0.003701
  s=1.078125: delta=-0.003730
  s=1.093750: delta=-0.003723
  s=1.109375: delta=-0.003676
  s=1.125000: delta=-0.003588
  s=1.140625: delta=-0.003459
  s=1.156250: delta=-0.003293
  s=1.171875: delta=-0.003095
  s=1.187500: delta=-0.002870
Version 2:
  s=0.000000: delta=+0.000000
  s=0.015625: delta=-0.000000
  s=0.031250: delta=-0.000000
  s=0.046875: delta=-0.000000
  s=0.062500: delta=-0.000000
  s=0.078125: delta=-0.000000
  s=0.093750: delta=-0.000000
  s=0.109375: delta=-0.000000
  s=0.125000: delta=-0.000000
  s=0.140625: delta=-0.000000
  s=0.156250: delta=-0.000000
  s=0.171875: delta=-0.000000
  s=0.187500: delta=+0.000000
  s=0.203125: delta=+0.000000
  s=0.218750: delta=+0.000000
  s=0.234375: delta=+0.000001
  s=0.250000: delta=+0.000001
  s=0.265625: delta=+0.000001
  s=0.281250: delta=+0.000001
  s=0.296875: delta=+0.000001
  s=0.312500: delta=+0.000002
  s=0.328125: delta=+0.000002
  s=0.343750: delta=+0.000002
  s=0.359375: delta=+0.000002
  s=0.375000: delta=+0.000003
  s=0.390625: delta=+0.000003
  s=0.406250: delta=+0.000003
  s=0.421875: delta=+0.000004
  s=0.437500: delta=+0.000004
  s=0.453125: delta=+0.000004
  s=0.468750: delta=+0.000004
  s=0.484375: delta=+0.000005
  s=0.500000: delta=+0.000005
  s=0.515625: delta=+0.000005
  s=0.531250: delta=+0.000005
  s=0.546875: delta=+0.000005
  s=0.562500: delta=+0.000006
  s=0.578125: delta=+0.000006
  s=0.593750: delta=+0.000006
  s=0.609375: delta=+0.000006
  s=0.625000: delta=+0.000006
  s=0.640625: delta=+0.000006
  s=0.656250: delta=+0.000006
  s=0.671875: delta=+0.000005
  s=0.687500: delta=+0.000005
  s=0.703125: delta=+0.000005
  s=0.718750: delta=+0.000004
  s=0.734375: delta=+0.000004
  s=0.750000: delta=+0.000003
  s=0.765625: delta=+0.000002
  s=0.781250: delta=+0.000001
  s=0.796875: delta=+0.000000
  s=0.812500: delta=-0.000001
  s=0.828125: delta=-0.000002
  s=0.843750: delta=-0.000004
  s=0.859375: delta=-0.000006
  s=0.875000: delta=-0.000008
  s=0.890625: delta=-0.000011
  s=0.906250: delta=-0.000014
  s=0.921875: delta=-0.000017
  s=0.937500: delta=-0.000020
  s=0.953125: delta=-0.000024
  s=0.968750: delta=-0.000028
  s=0.984375: delta=-0.000033
  s=1.000000: delta=-0.000037
  s=1.015625: delta=-0.000042
  s=1.031250: delta=-0.000047
  s=1.046875: delta=-0.000053
  s=1.062500: delta=-0.000058
  s=1.078125: delta=-0.000064
  s=1.093750: delta=-0.000071
  s=1.109375: delta=-0.000079
  s=1.125000: delta=-0.000087
  s=1.140625: delta=-0.000097
  s=1.156250: delta=-0.000108
  s=1.171875: delta=-0.000120
  s=1.187500: delta=-0.000133

  step=0.200000
Version 1:
  s=0.000000: delta=+0.000000
  s=0.200000: delta=+0.000278
  s=0.400000: delta=-0.000781
  s=0.600000: delta=-0.005687
  s=0.800000: delta=-0.016406
  s=1.000000: delta=-0.034638
  s=1.200000: delta=-0.046015
Version 2:
  s=0.000000: delta=+0.000000
  s=0.200000: delta=+0.000036
  s=0.400000: delta=+0.000538
  s=0.600000: delta=+0.000971
  s=0.800000: delta=+0.000335
  s=1.000000: delta=-0.003630
  s=1.200000: delta=-0.016011
https://ideone.com/OHOTWh
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!