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.broadphase; 25 26 import java.util.Arrays; 27 28 import org.jbox2d.callbacks.DebugDraw; 29 import org.jbox2d.callbacks.PairCallback; 30 import org.jbox2d.callbacks.TreeCallback; 31 import org.jbox2d.callbacks.TreeRayCastCallback; 32 import org.jbox2d.collision.AABB; 33 import org.jbox2d.collision.RayCastInput; 34 import org.jbox2d.common.Vec2; 35 36 /** 37 * The broad-phase is used for computing pairs and performing volume queries and ray casts. This 38 * broad-phase does not persist pairs. Instead, this reports potentially new pairs. It is up to the 39 * client to consume the new pairs and to track subsequent overlap. 40 * 41 * @author Daniel Murphy 42 */ 43 public class DefaultBroadPhaseBuffer implements TreeCallback, BroadPhase { 44 45 private final BroadPhaseStrategy m_tree; 46 47 private int m_proxyCount; 48 49 private int[] m_moveBuffer; 50 private int m_moveCapacity; 51 private int m_moveCount; 52 53 private Pair[] m_pairBuffer; 54 private int m_pairCapacity; 55 private int m_pairCount; 56 57 private int m_queryProxyId; 58 59 public DefaultBroadPhaseBuffer(BroadPhaseStrategy strategy) { 60 m_proxyCount = 0; 61 62 m_pairCapacity = 16; 63 m_pairCount = 0; 64 m_pairBuffer = new Pair[m_pairCapacity]; 65 for (int i = 0; i < m_pairCapacity; i++) { 66 m_pairBuffer[i] = new Pair(); 67 } 68 69 m_moveCapacity = 16; 70 m_moveCount = 0; 71 m_moveBuffer = new int[m_moveCapacity]; 72 73 m_tree = strategy; 74 m_queryProxyId = NULL_PROXY; 75 } 76 77 @Override 78 public final int createProxy(final AABB aabb, Object userData) { 79 int proxyId = m_tree.createProxy(aabb, userData); 80 ++m_proxyCount; 81 bufferMove(proxyId); 82 return proxyId; 83 } 84 85 @Override 86 public final void destroyProxy(int proxyId) { 87 unbufferMove(proxyId); 88 --m_proxyCount; 89 m_tree.destroyProxy(proxyId); 90 } 91 92 @Override 93 public final void moveProxy(int proxyId, final AABB aabb, final Vec2 displacement) { 94 boolean buffer = m_tree.moveProxy(proxyId, aabb, displacement); 95 if (buffer) { 96 bufferMove(proxyId); 97 } 98 } 99 100 @Override 101 public void touchProxy(int proxyId) { 102 bufferMove(proxyId); 103 } 104 105 @Override 106 public Object getUserData(int proxyId) { 107 return m_tree.getUserData(proxyId); 108 } 109 110 @Override 111 public AABB getFatAABB(int proxyId) { 112 return m_tree.getFatAABB(proxyId); 113 } 114 115 @Override 116 public boolean testOverlap(int proxyIdA, int proxyIdB) { 117 // return AABB.testOverlap(proxyA.aabb, proxyB.aabb); 118 // return m_tree.overlap(proxyIdA, proxyIdB); 119 final AABB a = m_tree.getFatAABB(proxyIdA); 120 final AABB b = m_tree.getFatAABB(proxyIdB); 121 if (b.lowerBound.x - a.upperBound.x > 0.0f || b.lowerBound.y - a.upperBound.y > 0.0f) { 122 return false; 123 } 124 125 if (a.lowerBound.x - b.upperBound.x > 0.0f || a.lowerBound.y - b.upperBound.y > 0.0f) { 126 return false; 127 } 128 129 return true; 130 } 131 132 @Override 133 public final int getProxyCount() { 134 return m_proxyCount; 135 } 136 137 @Override 138 public void drawTree(DebugDraw argDraw) { 139 m_tree.drawTree(argDraw); 140 } 141 142 @Override 143 public final void updatePairs(PairCallback callback) { 144 // Reset pair buffer 145 m_pairCount = 0; 146 147 // Perform tree queries for all moving proxies. 148 for (int i = 0; i < m_moveCount; ++i) { 149 m_queryProxyId = m_moveBuffer[i]; 150 if (m_queryProxyId == NULL_PROXY) { 151 continue; 152 } 153 154 // We have to query the tree with the fat AABB so that 155 // we don't fail to create a pair that may touch later. 156 final AABB fatAABB = m_tree.getFatAABB(m_queryProxyId); 157 158 // Query tree, create pairs and add them pair buffer. 159 // log.debug("quering aabb: "+m_queryProxy.aabb); 160 m_tree.query(this, fatAABB); 161 } 162 // log.debug("Number of pairs found: "+m_pairCount); 163 164 // Reset move buffer 165 m_moveCount = 0; 166 167 // Sort the pair buffer to expose duplicates. 168 Arrays.sort(m_pairBuffer, 0, m_pairCount); 169 170 // Send the pairs back to the client. 171 int i = 0; 172 while (i < m_pairCount) { 173 Pair primaryPair = m_pairBuffer[i]; 174 Object userDataA = m_tree.getUserData(primaryPair.proxyIdA); 175 Object userDataB = m_tree.getUserData(primaryPair.proxyIdB); 176 177 // log.debug("returning pair: "+userDataA+", "+userDataB); 178 callback.addPair(userDataA, userDataB); 179 ++i; 180 181 // Skip any duplicate pairs. 182 while (i < m_pairCount) { 183 Pair pair = m_pairBuffer[i]; 184 if (pair.proxyIdA != primaryPair.proxyIdA || pair.proxyIdB != primaryPair.proxyIdB) { 185 break; 186 } 187 ++i; 188 } 189 } 190 } 191 192 @Override 193 public final void query(final TreeCallback callback, final AABB aabb) { 194 m_tree.query(callback, aabb); 195 } 196 197 @Override 198 public final void raycast(final TreeRayCastCallback callback, final RayCastInput input) { 199 m_tree.raycast(callback, input); 200 } 201 202 @Override 203 public final int getTreeHeight() { 204 return m_tree.getHeight(); 205 } 206 207 @Override 208 public int getTreeBalance() { 209 return m_tree.getMaxBalance(); 210 } 211 212 @Override 213 public float getTreeQuality() { 214 return m_tree.getAreaRatio(); 215 } 216 217 protected final void bufferMove(int proxyId) { 218 if (m_moveCount == m_moveCapacity) { 219 int[] old = m_moveBuffer; 220 m_moveCapacity *= 2; 221 m_moveBuffer = new int[m_moveCapacity]; 222 System.arraycopy(old, 0, m_moveBuffer, 0, old.length); 223 } 224 225 m_moveBuffer[m_moveCount] = proxyId; 226 ++m_moveCount; 227 } 228 229 protected final void unbufferMove(int proxyId) { 230 for (int i = 0; i < m_moveCount; i++) { 231 if (m_moveBuffer[i] == proxyId) { 232 m_moveBuffer[i] = NULL_PROXY; 233 } 234 } 235 } 236 237 /** 238 * This is called from DynamicTree::query when we are gathering pairs. 239 */ 240 public final boolean treeCallback(int proxyId) { 241 // A proxy cannot form a pair with itself. 242 if (proxyId == m_queryProxyId) { 243 return true; 244 } 245 246 // Grow the pair buffer as needed. 247 if (m_pairCount == m_pairCapacity) { 248 Pair[] oldBuffer = m_pairBuffer; 249 m_pairCapacity *= 2; 250 m_pairBuffer = new Pair[m_pairCapacity]; 251 System.arraycopy(oldBuffer, 0, m_pairBuffer, 0, oldBuffer.length); 252 for (int i = oldBuffer.length; i < m_pairCapacity; i++) { 253 m_pairBuffer[i] = new Pair(); 254 } 255 } 256 257 if (proxyId < m_queryProxyId) { 258 m_pairBuffer[m_pairCount].proxyIdA = proxyId; 259 m_pairBuffer[m_pairCount].proxyIdB = m_queryProxyId; 260 } else { 261 m_pairBuffer[m_pairCount].proxyIdA = m_queryProxyId; 262 m_pairBuffer[m_pairCount].proxyIdB = proxyId; 263 } 264 265 ++m_pairCount; 266 return true; 267 } 268 } 269