Guest User

Untitled

a guest
Jan 22nd, 2019
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.27 KB | None | 0 0
  1. /*
  2. * Convex Separator for Box2D Flash
  3. *
  4. * This class has been written by Antoan Angelov.
  5. * It is designed to work with Erin Catto's Box2D physics library.
  6. *
  7. * Everybody can use this software for any purpose, under two restrictions:
  8. * 1. You cannot claim that you wrote this software.
  9. * 2. You can not remove or alter this notice.
  10. *
  11. */
  12.  
  13. package Box2DSeparator{
  14. import Box2D.Collision.Shapes.b2PolygonShape;
  15. import Box2D.Common.Math.b2Vec2;
  16. import Box2D.Dynamics.b2Body;
  17. import Box2D.Dynamics.b2FixtureDef;
  18.  
  19. public class b2Separator;
  20. {
  21. public function b2Separator() {
  22. }
  23.  
  24. /**
  25. * Separates a non-convex polygon into convex polygons and adds them as fixtures to the <code>body</code> parameter.<br/>
  26. * There are some rules you should follow (otherwise you might get unexpected results) :
  27. * <ul>
  28. * <li>This class is specifically for non-convex polygons. If you want to create a convex polygon, you don't need to use this class - Box2D's <code>b2PolygonShape</code> class allows you to create convex shapes with the <code>setAsArray()</code>/<code>setAsVector()</code> method.</li>
  29. * <li>The vertices must be in clockwise order.</li>
  30. * <li>No three neighbouring points should lie on the same line segment.</li>
  31. * <li>There must be no overlapping segments and no "holes".</li>
  32. * </ul> <p/>
  33. * @param body The b2Body, in which the new fixtures will be stored.
  34. * @param fixtureDef A b2FixtureDef, containing all the properties (friction, density, etc.) which the new fixtures will inherit.
  35. * @param verticesVec The vertices of the non-convex polygon, in clockwise order.
  36. * @param scale <code>[optional]</code> The scale which you use to draw shapes in Box2D. The bigger the scale, the better the precision. The default value is 30.
  37. * @see b2PolygonShape
  38. * @see b2PolygonShape.SetAsArray()
  39. * @see b2PolygonShape.SetAsVector()
  40. * @see b2Fixture
  41. * */
  42.  
  43. public function Separate(body:b2Body,fixtureDef:b2FixtureDef,verticesVec:Vector.<b2Vec2>,scale:Number=30):void {
  44. var i:int,n:int=verticesVec.length,j:int,m:int;
  45. var vec:Vector.<b2Vec2>=new Vector.<b2Vec2> ,figsVec:Array;
  46. var polyShape:b2PolygonShape;
  47.  
  48. for (i=0; i<n; i++) {
  49. vec.push(new b2Vec2(verticesVec[i].x*scale,verticesVec[i].y*scale));
  50. }
  51.  
  52. figsVec=calcShapes(vec);
  53. n=figsVec.length;
  54.  
  55. for (i=0; i<n; i++) {
  56. verticesVec=new Vector.<b2Vec2> ;
  57. vec=figsVec[i];
  58. m=vec.length;
  59. for (j=0; j<m; j++) {
  60. verticesVec.push(new b2Vec2(vec[j].x/scale,vec[j].y/scale));
  61. }
  62.  
  63. polyShape=new b2PolygonShape ;
  64. polyShape.SetAsVector(verticesVec);
  65. fixtureDef.shape=polyShape;
  66. body.CreateFixture(fixtureDef);
  67. }
  68. }
  69.  
  70. /**
  71. * Checks whether the vertices in <code>verticesVec</code> can be properly distributed into the new fixtures (more specifically, it makes sure there are no overlapping segments and the vertices are in clockwise order).
  72. * It is recommended that you use this method for debugging only, because it may cost more CPU usage.
  73. * <p/>
  74. * @param verticesVec The vertices to be validated.
  75. * @return An integer which can have the following values:
  76. * <ul>
  77. * <li>0 if the vertices can be properly processed.</li>
  78. * <li>1 If there are overlapping lines.</li>
  79. * <li>2 if the points are <b>not</b> in clockwise order.</li>
  80. * <li>3 if there are overlapping lines <b>and</b> the points are <b>not</b> in clockwise order.</li>
  81. * </ul>
  82. * */
  83.  
  84. public function Validate(verticesVec:Vector.<b2Vec2>):int {
  85. var i:int,n:int=verticesVec.length,j:int,j2:int,i2:int,i3:int,d:Number,ret:int=0;
  86. var fl:Boolean,fl2:Boolean=false;
  87.  
  88. for (i=0; i<n; i++) {
  89. i2=(i<n-1)?i+1:0;
  90. i3=(i>0)?i-1:n-1;
  91.  
  92. fl=false;
  93. for (j=0; j<n; j++) {
  94. if (((j!=i)&&j!=i2)) {
  95. if (! fl) {
  96. d=det(verticesVec[i].x,verticesVec[i].y,verticesVec[i2].x,verticesVec[i2].y,verticesVec[j].x,verticesVec[j].y);
  97. if ((d>0)) {
  98. fl=true;
  99. }
  100. }
  101.  
  102. if ((j!=i3)) {
  103. j2=(j<n-1)?j+1:0;
  104. if (hitSegment(verticesVec[i].x,verticesVec[i].y,verticesVec[i2].x,verticesVec[i2].y,verticesVec[j].x,verticesVec[j].y,verticesVec[j2].x,verticesVec[j2].y)) {
  105. ret=1;
  106. }
  107. }
  108. }
  109. }
  110.  
  111. if (! fl) {
  112. fl2=true;
  113. }
  114. }
  115.  
  116. if (fl2) {
  117. if ((ret==1)) {
  118. ret=3;
  119. }
  120. else {
  121. ret=2;
  122. }
  123.  
  124. }
  125. return ret;
  126. }
  127.  
  128. private function calcShapes(verticesVec:Vector.<b2Vec2>):Array {
  129. var vec:Vector.<b2Vec2>;
  130. var i:int,n:int,j:int;
  131. var d:Number,t:Number,dx:Number,dy:Number,minLen:Number;
  132. var i1:int,i2:int,i3:int,p1:b2Vec2,p2:b2Vec2,p3:b2Vec2;
  133. var j1:int,j2:int,v1:b2Vec2,v2:b2Vec2,k:int,h:int;
  134. var vec1:Vector.<b2Vec2>,vec2:Vector.<b2Vec2>;
  135. var v:b2Vec2,hitV:b2Vec2;
  136. var isConvex:Boolean;
  137. var figsVec:Array=[],queue:Array=[];
  138.  
  139. queue.push(verticesVec);
  140.  
  141. while (queue.length) {
  142. vec=queue[0];
  143. n=vec.length;
  144. isConvex=true;
  145.  
  146. for (i=0; i<n; i++) {
  147. i1=i;
  148. i2=(i<n-1)?i+1:i+1-n;
  149. i3=(i<n-2)?i+2:i+2-n;
  150.  
  151. p1=vec[i1];
  152. p2=vec[i2];
  153. p3=vec[i3];
  154.  
  155. d=det(p1.x,p1.y,p2.x,p2.y,p3.x,p3.y);
  156. if ((d<0)) {
  157. isConvex=false;
  158. minLen=Number.MAX_VALUE;
  159.  
  160. for (j=0; j<n; j++) {
  161. if (((j!=i1)&&j!=i2)) {
  162. j1=j;
  163. j2=(j<n-1)?j+1:0;
  164.  
  165. v1=vec[j1];
  166. v2=vec[j2];
  167.  
  168. v=hitRay(p1.x,p1.y,p2.x,p2.y,v1.x,v1.y,v2.x,v2.y);
  169.  
  170. if (v) {
  171. dx=p2.x-v.x;
  172. dy=p2.y-v.y;
  173. t=dx*dx+dy*dy;
  174.  
  175. if ((t<minLen)) {
  176. h=j1;
  177. k=j2;
  178. hitV=v;
  179. minLen=t;
  180. }
  181. }
  182. }
  183. }
  184.  
  185. if ((minLen==Number.MAX_VALUE)) {
  186. err();
  187. }
  188.  
  189. vec1=new Vector.<b2Vec2> ;
  190. vec2=new Vector.<b2Vec2> ;
  191.  
  192. j1=h;
  193. j2=k;
  194. v1=vec[j1];
  195. v2=vec[j2];
  196.  
  197. if (! pointsMatch(hitV.x,hitV.y,v2.x,v2.y)) {
  198. vec1.push(hitV);
  199. }
  200. if (! pointsMatch(hitV.x,hitV.y,v1.x,v1.y)) {
  201. vec2.push(hitV);
  202. }
  203.  
  204. h=-1;
  205. k=i1;
  206. while (true) {
  207. if ((k!=j2)) {
  208. vec1.push(vec[k]);
  209. }
  210. else {
  211. if (((h<0)||h>=n)) {
  212. err();
  213. }
  214. if (! this.isOnSegment(v2.x,v2.y,vec[h].x,vec[h].y,p1.x,p1.y)) {
  215. vec1.push(vec[k]);
  216. }
  217. break;
  218. }
  219.  
  220. h=k;
  221. if (((k-1)<0)) {
  222. k=n-1;
  223. }
  224. else {
  225. k--;
  226. }
  227. }
  228.  
  229. vec1=vec1.reverse();
  230.  
  231. h=-1;
  232. k=i2;
  233. while (true) {
  234. if ((k!=j1)) {
  235. vec2.push(vec[k]);
  236. }
  237. else {
  238. if (((h<0)||h>=n)) {
  239. err();
  240. }
  241. if (((k==j1)&&! this.isOnSegment(v1.x,v1.y,vec[h].x,vec[h].y,p2.x,p2.y))) {
  242. vec2.push(vec[k]);
  243. }
  244. break;
  245. }
  246.  
  247. h=k;
  248. if (((k+1)>n-1)) {
  249. k=0;
  250. }
  251. else {
  252. k++;
  253. }
  254. }
  255.  
  256. queue.push(vec1,vec2);
  257. queue.shift();
  258.  
  259. break;
  260. }
  261. }
  262.  
  263. if (isConvex) {
  264. figsVec.push(queue.shift());
  265. }
  266. }
  267.  
  268. return figsVec;
  269. }
  270.  
  271. private function hitRay(x1:Number,y1:Number,x2:Number,y2:Number,x3:Number,y3:Number,x4:Number,y4:Number):b2Vec2 {
  272. var t1:Number=x3-x1,t2:Number=y3-y1,t3:Number=x2-x1,t4:Number=y2-y1,t5:Number=x4-x3,t6:Number=y4-y3,t7:Number=t4*t5-t3*t6,a:Number;
  273.  
  274. a=(((t5*t2)-t6*t1)/t7);
  275. var px:Number=x1+a*t3,py:Number=y1+a*t4;
  276. var b1:Boolean=isOnSegment(x2,y2,x1,y1,px,py);
  277. var b2:Boolean=isOnSegment(px,py,x3,y3,x4,y4);
  278.  
  279. if ((b1&&b2)) {
  280. return new b2Vec2(px,py);
  281. }
  282.  
  283. return null;
  284. }
  285.  
  286. private function hitSegment(x1:Number,y1:Number,x2:Number,y2:Number,x3:Number,y3:Number,x4:Number,y4:Number):b2Vec2 {
  287. var t1:Number=x3-x1,t2:Number=y3-y1,t3:Number=x2-x1,t4:Number=y2-y1,t5:Number=x4-x3,t6:Number=y4-y3,t7:Number=t4*t5-t3*t6,a:Number;
  288.  
  289. a=(((t5*t2)-t6*t1)/t7);
  290. var px:Number=x1+a*t3,py:Number=y1+a*t4;
  291. var b1:Boolean=isOnSegment(px,py,x1,y1,x2,y2);
  292. var b2:Boolean=isOnSegment(px,py,x3,y3,x4,y4);
  293.  
  294. if ((b1&&b2)) {
  295. return new b2Vec2(px,py);
  296. }
  297.  
  298. return null;
  299. }
  300.  
  301. private function isOnSegment(px:Number,py:Number,x1:Number,y1:Number,x2:Number,y2:Number):Boolean {
  302. var b1:Boolean=((((x1+0.1)>=px)&&px>=x2-0.1)||(((x1-0.1)<=px)&&px<=x2+0.1));
  303. var b2:Boolean=((((y1+0.1)>=py)&&py>=y2-0.1)||(((y1-0.1)<=py)&&py<=y2+0.1));
  304. return ((b1&&b2)&&isOnLine(px,py,x1,y1,x2,y2));
  305. }
  306.  
  307. private function pointsMatch(x1:Number,y1:Number,x2:Number,y2:Number):Boolean {
  308. var dx:Number=(x2>=x1)?x2-x1:x1-x2,dy:Number=(y2>=y1)?y2-y1:y1-y2;
  309. return ((dx<0.1)&&dy<0.1);
  310. }
  311.  
  312. private function isOnLine(px:Number,py:Number,x1:Number,y1:Number,x2:Number,y2:Number):Boolean {
  313. if ((((x2-x1)>0.1)||x1-x2>0.1)) {
  314. var a:Number=(y2-y1)/(x2-x1),possibleY:Number=a*(px-x1)+y1,diff:Number=(possibleY>py)?possibleY-py:py-possibleY;
  315. return (diff<0.1);
  316. }
  317.  
  318. return (((px-x1)<0.1)||x1-px<0.1);
  319. }
  320.  
  321. private function det(x1:Number,y1:Number,x2:Number,y2:Number,x3:Number,y3:Number):Number {
  322. return x1*y2+x2*y3+x3*y1-y1*x2-y2*x3-y3*x1;
  323. }
  324.  
  325. private function err():void {
  326. throw new Error("A problem has occurred. Use the Validate() method to see where the problem is.");
  327. }
  328. }
  329. }
Add Comment
Please, Sign In to add comment