1 /******************************************************************************* 2 * Copyright (c) 2013, Daniel Murphy 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without modification, 6 * are permitted provided that the following conditions are met: 7 * * Redistributions of source code must retain the above copyright notice, 8 * this list of conditions and the following disclaimer. 9 * * Redistributions in binary form must reproduce the above copyright notice, 10 * this list of conditions and the following disclaimer in the documentation 11 * and/or other materials provided with the distribution. 12 * 13 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND 14 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 15 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 16 * IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 17 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 18 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 19 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 20 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 21 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 22 * POSSIBILITY OF SUCH DAMAGE. 23 ******************************************************************************/ 24 package org.jbox2d.collision.shapes; 25 26 import org.jbox2d.collision.AABB; 27 import org.jbox2d.collision.RayCastInput; 28 import org.jbox2d.collision.RayCastOutput; 29 import org.jbox2d.common.MathUtils; 30 import org.jbox2d.common.Rot; 31 import org.jbox2d.common.Settings; 32 import org.jbox2d.common.Transform; 33 import org.jbox2d.common.Vec2; 34 import org.jbox2d.pooling.arrays.IntArray; 35 import org.jbox2d.pooling.arrays.Vec2Array; 36 37 /** 38 * A convex polygon shape. Polygons have a maximum number of vertices equal to _maxPolygonVertices. 39 * In most cases you should not need many vertices for a convex polygon. 40 */ 41 public class PolygonShape extends Shape { 42 /** Dump lots of debug information. */ 43 private final static boolean m_debug = false; 44 45 /** 46 * Local position of the shape centroid in parent body frame. 47 */ 48 public final Vec2 m_centroid = new Vec2(); 49 50 /** 51 * The vertices of the shape. Note: use getVertexCount(), not m_vertices.length, to get number of 52 * active vertices. 53 */ 54 public final Vec2 m_vertices[]; 55 56 /** 57 * The normals of the shape. Note: use getVertexCount(), not m_normals.length, to get number of 58 * active normals. 59 */ 60 public final Vec2 m_normals[]; 61 62 /** 63 * Number of active vertices in the shape. 64 */ 65 public int m_count; 66 67 // pooling 68 private final Vec2 pool1 = new Vec2(); 69 private final Vec2 pool2 = new Vec2(); 70 private final Vec2 pool3 = new Vec2(); 71 private final Vec2 pool4 = new Vec2(); 72 private Transform poolt1 = new Transform(); 73 74 public PolygonShape() { 75 super(ShapeType.POLYGON); 76 77 m_count = 0; 78 m_vertices = new Vec2[Settings.maxPolygonVertices]; 79 for (int i = 0; i < m_vertices.length; i++) { 80 m_vertices[i] = new Vec2(); 81 } 82 m_normals = new Vec2[Settings.maxPolygonVertices]; 83 for (int i = 0; i < m_normals.length; i++) { 84 m_normals[i] = new Vec2(); 85 } 86 setRadius(Settings.polygonRadius); 87 m_centroid.setZero(); 88 } 89 90 public final Shape clone() { 91 PolygonShape shape = new PolygonShape(); 92 shape.m_centroid.set(this.m_centroid); 93 for (int i = 0; i < shape.m_normals.length; i++) { 94 shape.m_normals[i].set(m_normals[i]); 95 shape.m_vertices[i].set(m_vertices[i]); 96 } 97 shape.setRadius(this.getRadius()); 98 shape.m_count = this.m_count; 99 return shape; 100 } 101 102 /** 103 * Create a convex hull from the given array of points. The count must be in the range [3, 104 * Settings.maxPolygonVertices]. 105 * 106 * @warning the points may be re-ordered, even if they form a convex polygon. 107 * @warning collinear points are removed. 108 */ 109 public final void set(final Vec2[] vertices, final int count) { 110 set(vertices, count, null, null); 111 } 112 113 /** 114 * Create a convex hull from the given array of points. The count must be in the range [3, 115 * Settings.maxPolygonVertices]. This method takes an arraypool for pooling. 116 * 117 * @warning the points may be re-ordered, even if they form a convex polygon. 118 * @warning collinear points are removed. 119 */ 120 public final void set(final Vec2[] verts, final int num, final Vec2Array vecPool, 121 final IntArray intPool) { 122 assert (3 <= num && num <= Settings.maxPolygonVertices); 123 if (num < 3) { 124 setAsBox(1.0f, 1.0f); 125 return; 126 } 127 128 int n = MathUtils.min(num, Settings.maxPolygonVertices); 129 130 // Perform welding and copy vertices into local buffer. 131 Vec2[] ps = 132 (vecPool != null) 133 ? vecPool.get(Settings.maxPolygonVertices) 134 : new Vec2[Settings.maxPolygonVertices]; 135 int tempCount = 0; 136 for (int i = 0; i < n; ++i) { 137 Vec2 v = verts[i]; 138 boolean unique = true; 139 for (int j = 0; j < tempCount; ++j) { 140 if (MathUtils.distanceSquared(v, ps[j]) < 0.5f * Settings.linearSlop) { 141 unique = false; 142 break; 143 } 144 } 145 146 if (unique) { 147 ps[tempCount++] = v; 148 } 149 } 150 151 n = tempCount; 152 if (n < 3) { 153 // Polygon is degenerate. 154 assert (false); 155 setAsBox(1.0f, 1.0f); 156 return; 157 } 158 159 // Create the convex hull using the Gift wrapping algorithm 160 // http://en.wikipedia.org/wiki/Gift_wrapping_algorithm 161 162 // Find the right most point on the hull 163 int i0 = 0; 164 float x0 = ps[0].x; 165 for (int i = 1; i < n; ++i) { 166 float x = ps[i].x; 167 if (x > x0 || (x == x0 && ps[i].y < ps[i0].y)) { 168 i0 = i; 169 x0 = x; 170 } 171 } 172 173 int[] hull = 174 (intPool != null) 175 ? intPool.get(Settings.maxPolygonVertices) 176 : new int[Settings.maxPolygonVertices]; 177 int m = 0; 178 int ih = i0; 179 180 while (true) { 181 hull[m] = ih; 182 183 int ie = 0; 184 for (int j = 1; j < n; ++j) { 185 if (ie == ih) { 186 ie = j; 187 continue; 188 } 189 190 Vec2 r = pool1.set(ps[ie]).subLocal(ps[hull[m]]); 191 Vec2 v = pool2.set(ps[j]).subLocal(ps[hull[m]]); 192 float c = Vec2.cross(r, v); 193 if (c < 0.0f) { 194 ie = j; 195 } 196 197 // Collinearity check 198 if (c == 0.0f && v.lengthSquared() > r.lengthSquared()) { 199 ie = j; 200 } 201 } 202 203 ++m; 204 ih = ie; 205 206 if (ie == i0) { 207 break; 208 } 209 } 210 211 this.m_count = m; 212 213 // Copy vertices. 214 for (int i = 0; i < m_count; ++i) { 215 if (m_vertices[i] == null) { 216 m_vertices[i] = new Vec2(); 217 } 218 m_vertices[i].set(ps[hull[i]]); 219 } 220 221 final Vec2 edge = pool1; 222 223 // Compute normals. Ensure the edges have non-zero length. 224 for (int i = 0; i < m_count; ++i) { 225 final int i1 = i; 226 final int i2 = i + 1 < m_count ? i + 1 : 0; 227 edge.set(m_vertices[i2]).subLocal(m_vertices[i1]); 228 229 assert (edge.lengthSquared() > Settings.EPSILON * Settings.EPSILON); 230 Vec2.crossToOutUnsafe(edge, 1f, m_normals[i]); 231 m_normals[i].normalize(); 232 } 233 234 // Compute the polygon centroid. 235 computeCentroidToOut(m_vertices, m_count, m_centroid); 236 } 237 238 /** 239 * Build vertices to represent an axis-aligned box. 240 * 241 * @param hx the half-width. 242 * @param hy the half-height. 243 */ 244 public final void setAsBox(final float hx, final float hy) { 245 m_count = 4; 246 m_vertices[0].set(-hx, -hy); 247 m_vertices[1].set(hx, -hy); 248 m_vertices[2].set(hx, hy); 249 m_vertices[3].set(-hx, hy); 250 m_normals[0].set(0.0f, -1.0f); 251 m_normals[1].set(1.0f, 0.0f); 252 m_normals[2].set(0.0f, 1.0f); 253 m_normals[3].set(-1.0f, 0.0f); 254 m_centroid.setZero(); 255 } 256 257 /** 258 * Build vertices to represent an oriented box. 259 * 260 * @param hx the half-width. 261 * @param hy the half-height. 262 * @param center the center of the box in local coordinates. 263 * @param angle the rotation of the box in local coordinates. 264 */ 265 public final void setAsBox(final float hx, final float hy, final Vec2 center, final float angle) { 266 m_count = 4; 267 m_vertices[0].set(-hx, -hy); 268 m_vertices[1].set(hx, -hy); 269 m_vertices[2].set(hx, hy); 270 m_vertices[3].set(-hx, hy); 271 m_normals[0].set(0.0f, -1.0f); 272 m_normals[1].set(1.0f, 0.0f); 273 m_normals[2].set(0.0f, 1.0f); 274 m_normals[3].set(-1.0f, 0.0f); 275 m_centroid.set(center); 276 277 final Transform xf = poolt1; 278 xf.p.set(center); 279 xf.q.set(angle); 280 281 // Transform vertices and normals. 282 for (int i = 0; i < m_count; ++i) { 283 Transform.mulToOut(xf, m_vertices[i], m_vertices[i]); 284 Rot.mulToOut(xf.q, m_normals[i], m_normals[i]); 285 } 286 } 287 288 public int getChildCount() { 289 return 1; 290 } 291 292 @Override 293 public final boolean testPoint(final Transform xf, final Vec2 p) { 294 float tempx, tempy; 295 final Rot xfq = xf.q; 296 297 tempx = p.x - xf.p.x; 298 tempy = p.y - xf.p.y; 299 final float pLocalx = xfq.c * tempx + xfq.s * tempy; 300 final float pLocaly = -xfq.s * tempx + xfq.c * tempy; 301 302 if (m_debug) { 303 System.out.println("--testPoint debug--"); 304 System.out.println("Vertices: "); 305 for (int i = 0; i < m_count; ++i) { 306 System.out.println(m_vertices[i]); 307 } 308 System.out.println("pLocal: " + pLocalx + ", " + pLocaly); 309 } 310 311 for (int i = 0; i < m_count; ++i) { 312 Vec2 vertex = m_vertices[i]; 313 Vec2 normal = m_normals[i]; 314 tempx = pLocalx - vertex.x; 315 tempy = pLocaly - vertex.y; 316 final float dot = normal.x * tempx + normal.y * tempy; 317 if (dot > 0.0f) { 318 return false; 319 } 320 } 321 322 return true; 323 } 324 325 @Override 326 public final void computeAABB(final AABB aabb, final Transform xf, int childIndex) { 327 final Vec2 lower = aabb.lowerBound; 328 final Vec2 upper = aabb.upperBound; 329 final Vec2 v1 = m_vertices[0]; 330 final float xfqc = xf.q.c; 331 final float xfqs = xf.q.s; 332 final float xfpx = xf.p.x; 333 final float xfpy = xf.p.y; 334 lower.x = (xfqc * v1.x - xfqs * v1.y) + xfpx; 335 lower.y = (xfqs * v1.x + xfqc * v1.y) + xfpy; 336 upper.x = lower.x; 337 upper.y = lower.y; 338 339 for (int i = 1; i < m_count; ++i) { 340 Vec2 v2 = m_vertices[i]; 341 // Vec2 v = Mul(xf, m_vertices[i]); 342 float vx = (xfqc * v2.x - xfqs * v2.y) + xfpx; 343 float vy = (xfqs * v2.x + xfqc * v2.y) + xfpy; 344 lower.x = lower.x < vx ? lower.x : vx; 345 lower.y = lower.y < vy ? lower.y : vy; 346 upper.x = upper.x > vx ? upper.x : vx; 347 upper.y = upper.y > vy ? upper.y : vy; 348 } 349 350 lower.x -= m_radius; 351 lower.y -= m_radius; 352 upper.x += m_radius; 353 upper.y += m_radius; 354 } 355 356 /** 357 * Get the vertex count. 358 * 359 * @return 360 */ 361 public final int getVertexCount() { 362 return m_count; 363 } 364 365 /** 366 * Get a vertex by index. 367 * 368 * @param index 369 * @return 370 */ 371 public final Vec2 getVertex(final int index) { 372 assert (0 <= index && index < m_count); 373 return m_vertices[index]; 374 } 375 376 @Override 377 public float computeDistanceToOut(Transform xf, Vec2 p, int childIndex, Vec2 normalOut) { 378 float xfqc = xf.q.c; 379 float xfqs = xf.q.s; 380 float tx = p.x - xf.p.x; 381 float ty = p.y - xf.p.y; 382 float pLocalx = xfqc * tx + xfqs * ty; 383 float pLocaly = -xfqs * tx + xfqc * ty; 384 385 float maxDistance = -Float.MAX_VALUE; 386 float normalForMaxDistanceX = pLocalx; 387 float normalForMaxDistanceY = pLocaly; 388 389 for (int i = 0; i < m_count; ++i) { 390 Vec2 vertex = m_vertices[i]; 391 Vec2 normal = m_normals[i]; 392 tx = pLocalx - vertex.x; 393 ty = pLocaly - vertex.y; 394 float dot = normal.x * tx + normal.y * ty; 395 if (dot > maxDistance) { 396 maxDistance = dot; 397 normalForMaxDistanceX = normal.x; 398 normalForMaxDistanceY = normal.y; 399 } 400 } 401 402 float distance; 403 if (maxDistance > 0) { 404 float minDistanceX = normalForMaxDistanceX; 405 float minDistanceY = normalForMaxDistanceY; 406 float minDistance2 = maxDistance * maxDistance; 407 for (int i = 0; i < m_count; ++i) { 408 Vec2 vertex = m_vertices[i]; 409 float distanceVecX = pLocalx - vertex.x; 410 float distanceVecY = pLocaly - vertex.y; 411 float distance2 = (distanceVecX * distanceVecX + distanceVecY * distanceVecY); 412 if (minDistance2 > distance2) { 413 minDistanceX = distanceVecX; 414 minDistanceY = distanceVecY; 415 minDistance2 = distance2; 416 } 417 } 418 distance = MathUtils.sqrt(minDistance2); 419 normalOut.x = xfqc * minDistanceX - xfqs * minDistanceY; 420 normalOut.y = xfqs * minDistanceX + xfqc * minDistanceY; 421 normalOut.normalize(); 422 } else { 423 distance = maxDistance; 424 normalOut.x = xfqc * normalForMaxDistanceX - xfqs * normalForMaxDistanceY; 425 normalOut.y = xfqs * normalForMaxDistanceX + xfqc * normalForMaxDistanceY; 426 } 427 428 return distance; 429 } 430 431 @Override 432 public final boolean raycast(RayCastOutput output, RayCastInput input, Transform xf, 433 int childIndex) { 434 final float xfqc = xf.q.c; 435 final float xfqs = xf.q.s; 436 final Vec2 xfp = xf.p; 437 float tempx, tempy; 438 // b2Vec2 p1 = b2MulT(xf.q, input.p1 - xf.p); 439 // b2Vec2 p2 = b2MulT(xf.q, input.p2 - xf.p); 440 tempx = input.p1.x - xfp.x; 441 tempy = input.p1.y - xfp.y; 442 final float p1x = xfqc * tempx + xfqs * tempy; 443 final float p1y = -xfqs * tempx + xfqc * tempy; 444 445 tempx = input.p2.x - xfp.x; 446 tempy = input.p2.y - xfp.y; 447 final float p2x = xfqc * tempx + xfqs * tempy; 448 final float p2y = -xfqs * tempx + xfqc * tempy; 449 450 final float dx = p2x - p1x; 451 final float dy = p2y - p1y; 452 453 float lower = 0, upper = input.maxFraction; 454 455 int index = -1; 456 457 for (int i = 0; i < m_count; ++i) { 458 Vec2 normal = m_normals[i]; 459 Vec2 vertex = m_vertices[i]; 460 // p = p1 + a * d 461 // dot(normal, p - v) = 0 462 // dot(normal, p1 - v) + a * dot(normal, d) = 0 463 float tempxn = vertex.x - p1x; 464 float tempyn = vertex.y - p1y; 465 final float numerator = normal.x * tempxn + normal.y * tempyn; 466 final float denominator = normal.x * dx + normal.y * dy; 467 468 if (denominator == 0.0f) { 469 if (numerator < 0.0f) { 470 return false; 471 } 472 } else { 473 // Note: we want this predicate without division: 474 // lower < numerator / denominator, where denominator < 0 475 // Since denominator < 0, we have to flip the inequality: 476 // lower < numerator / denominator <==> denominator * lower > 477 // numerator. 478 if (denominator < 0.0f && numerator < lower * denominator) { 479 // Increase lower. 480 // The segment enters this half-space. 481 lower = numerator / denominator; 482 index = i; 483 } else if (denominator > 0.0f && numerator < upper * denominator) { 484 // Decrease upper. 485 // The segment exits this half-space. 486 upper = numerator / denominator; 487 } 488 } 489 490 if (upper < lower) { 491 return false; 492 } 493 } 494 495 assert (0.0f <= lower && lower <= input.maxFraction); 496 497 if (index >= 0) { 498 output.fraction = lower; 499 // normal = Mul(xf.R, m_normals[index]); 500 Vec2 normal = m_normals[index]; 501 Vec2 out = output.normal; 502 out.x = xfqc * normal.x - xfqs * normal.y; 503 out.y = xfqs * normal.x + xfqc * normal.y; 504 return true; 505 } 506 return false; 507 } 508 509 public final void computeCentroidToOut(final Vec2[] vs, final int count, final Vec2 out) { 510 assert (count >= 3); 511 512 out.set(0.0f, 0.0f); 513 float area = 0.0f; 514 515 // pRef is the reference point for forming triangles. 516 // It's location doesn't change the result (except for rounding error). 517 final Vec2 pRef = pool1; 518 pRef.setZero(); 519 520 final Vec2 e1 = pool2; 521 final Vec2 e2 = pool3; 522 523 final float inv3 = 1.0f / 3.0f; 524 525 for (int i = 0; i < count; ++i) { 526 // Triangle vertices. 527 final Vec2 p1 = pRef; 528 final Vec2 p2 = vs[i]; 529 final Vec2 p3 = i + 1 < count ? vs[i + 1] : vs[0]; 530 531 e1.set(p2).subLocal(p1); 532 e2.set(p3).subLocal(p1); 533 534 final float D = Vec2.cross(e1, e2); 535 536 final float triangleArea = 0.5f * D; 537 area += triangleArea; 538 539 // Area weighted centroid 540 e1.set(p1).addLocal(p2).addLocal(p3).mulLocal(triangleArea * inv3); 541 out.addLocal(e1); 542 } 543 544 // Centroid 545 assert (area > Settings.EPSILON); 546 out.mulLocal(1.0f / area); 547 } 548 549 public void computeMass(final MassData massData, float density) { 550 // Polygon mass, centroid, and inertia. 551 // Let rho be the polygon density in mass per unit area. 552 // Then: 553 // mass = rho * int(dA) 554 // centroid.x = (1/mass) * rho * int(x * dA) 555 // centroid.y = (1/mass) * rho * int(y * dA) 556 // I = rho * int((x*x + y*y) * dA) 557 // 558 // We can compute these integrals by summing all the integrals 559 // for each triangle of the polygon. To evaluate the integral 560 // for a single triangle, we make a change of variables to 561 // the (u,v) coordinates of the triangle: 562 // x = x0 + e1x * u + e2x * v 563 // y = y0 + e1y * u + e2y * v 564 // where 0 <= u && 0 <= v && u + v <= 1. 565 // 566 // We integrate u from [0,1-v] and then v from [0,1]. 567 // We also need to use the Jacobian of the transformation: 568 // D = cross(e1, e2) 569 // 570 // Simplification: triangle centroid = (1/3) * (p1 + p2 + p3) 571 // 572 // The rest of the derivation is handled by computer algebra. 573 574 assert (m_count >= 3); 575 576 final Vec2 center = pool1; 577 center.setZero(); 578 float area = 0.0f; 579 float I = 0.0f; 580 581 // pRef is the reference point for forming triangles. 582 // It's location doesn't change the result (except for rounding error). 583 final Vec2 s = pool2; 584 s.setZero(); 585 // This code would put the reference point inside the polygon. 586 for (int i = 0; i < m_count; ++i) { 587 s.addLocal(m_vertices[i]); 588 } 589 s.mulLocal(1.0f / m_count); 590 591 final float k_inv3 = 1.0f / 3.0f; 592 593 final Vec2 e1 = pool3; 594 final Vec2 e2 = pool4; 595 596 for (int i = 0; i < m_count; ++i) { 597 // Triangle vertices. 598 e1.set(m_vertices[i]).subLocal(s); 599 e2.set(s).negateLocal().addLocal(i + 1 < m_count ? m_vertices[i + 1] : m_vertices[0]); 600 601 final float D = Vec2.cross(e1, e2); 602 603 final float triangleArea = 0.5f * D; 604 area += triangleArea; 605 606 // Area weighted centroid 607 center.x += triangleArea * k_inv3 * (e1.x + e2.x); 608 center.y += triangleArea * k_inv3 * (e1.y + e2.y); 609 610 final float ex1 = e1.x, ey1 = e1.y; 611 final float ex2 = e2.x, ey2 = e2.y; 612 613 float intx2 = ex1 * ex1 + ex2 * ex1 + ex2 * ex2; 614 float inty2 = ey1 * ey1 + ey2 * ey1 + ey2 * ey2; 615 616 I += (0.25f * k_inv3 * D) * (intx2 + inty2); 617 } 618 619 // Total mass 620 massData.mass = density * area; 621 622 // Center of mass 623 assert (area > Settings.EPSILON); 624 center.mulLocal(1.0f / area); 625 massData.center.set(center).addLocal(s); 626 627 // Inertia tensor relative to the local origin (point s) 628 massData.I = I * density; 629 630 // Shift to center of mass then to original body origin. 631 massData.I += massData.mass * (Vec2.dot(massData.center, massData.center)); 632 } 633 634 /** 635 * Validate convexity. This is a very time consuming operation. 636 * 637 * @return 638 */ 639 public boolean validate() { 640 for (int i = 0; i < m_count; ++i) { 641 int i1 = i; 642 int i2 = i < m_count - 1 ? i1 + 1 : 0; 643 Vec2 p = m_vertices[i1]; 644 Vec2 e = pool1.set(m_vertices[i2]).subLocal(p); 645 646 for (int j = 0; j < m_count; ++j) { 647 if (j == i1 || j == i2) { 648 continue; 649 } 650 651 Vec2 v = pool2.set(m_vertices[j]).subLocal(p); 652 float c = Vec2.cross(e, v); 653 if (c < 0.0f) { 654 return false; 655 } 656 } 657 } 658 659 return true; 660 } 661 662 /** Get the vertices in local coordinates. */ 663 public Vec2[] getVertices() { 664 return m_vertices; 665 } 666 667 /** Get the edge normal vectors. There is one for each vertex. */ 668 public Vec2[] getNormals() { 669 return m_normals; 670 } 671 672 /** Get the centroid and apply the supplied transform. */ 673 public Vec2 centroid(final Transform xf) { 674 return Transform.mul(xf, m_centroid); 675 } 676 677 /** Get the centroid and apply the supplied transform. */ 678 public Vec2 centroidToOut(final Transform xf, final Vec2 out) { 679 Transform.mulToOutUnsafe(xf, m_centroid, out); 680 return out; 681 } 682 } 683