• Advertisement
  • Popular Tags

  • Popular Now

  • Advertisement
  • Similar Content

    • By Octane_Test
      I am developing a mini golf game in Scenekit. I have applied dynamic physics body to the ball and static physics body to the grass surface and the brick walls show in this image.
      Issue:
      When I apply the force to the ball, the ball’s linear and angular speeds change as shown in the graphs.  The ball’s speeds don’t reduce to zero (so that the ball can stop) but remains constant after certain value.
      Ball linear speed graph
      Ball angular speed graph
      Analysis Tests:
      When I increase the values to both the rolling friction and the friction, the ball speed is reduced quickly but remains constant after certain value (similar to the above graphs). When I increase the values of the linear damping and the angular damping, the ball speed behavior is same as the point #1. When I set the gravity value to -9.8 m/s2, the ball’s linear speed remains constant after 0.1 m/s. If I reduce the gravity value to -5 m/s2, the ball’s linear speed remains constant after 0.05 m/s. The friction, linear friction, linear damping and angular damping are same throughout the motion of the ball.
      There is 1 millimeter overlapping between the ball and the surface of the golf course.
      Questions:
      From the analysis test #3, I think the gravity is causing the constant ball speed issue. Is my assumption correct? If yes, how can I fix the issue? I can’t remove the gravity field as without the gravity field the ball will not roll along the grass and it will slide. Why the friction and the damping properties are not affecting the ball speed after certain value?
      Are there any other physics properties can cause such issue?
      From the analysis test #5, are there any chances that the ball is receiving upward push to correct the position of the ball?
      Solutions:
      If I increase the physics timestep from 60 FPS to 200 FPS, the issue is resolved. I am not able to understand how this change can fix this issue? After reducing the gravity value to -1 m/s2 and physics simulation speed to 4 (4 times fast physics simulation), the issue is fixed. Again, I am not able to understand how this change fix the issue? I would appreciate any suggestions and thoughts on this topic. Thank you.
    • By akshayMore
      Hello,
      I am trying to make a GeometryUtil class that has methods to draw point,line ,polygon etc. I am trying to make a method to draw circle.  
      There are many ways to draw a circle.  I have found two ways, 
      The one way:
      public static void drawBresenhamCircle(PolygonSpriteBatch batch, int centerX, int centerY, int radius, ColorRGBA color) { int x = 0, y = radius; int d = 3 - 2 * radius; while (y >= x) { drawCirclePoints(batch, centerX, centerY, x, y, color); if (d <= 0) { d = d + 4 * x + 6; } else { y--; d = d + 4 * (x - y) + 10; } x++; //drawCirclePoints(batch,centerX,centerY,x,y,color); } } private static void drawCirclePoints(PolygonSpriteBatch batch, int centerX, int centerY, int x, int y, ColorRGBA color) { drawPoint(batch, centerX + x, centerY + y, color); drawPoint(batch, centerX - x, centerY + y, color); drawPoint(batch, centerX + x, centerY - y, color); drawPoint(batch, centerX - x, centerY - y, color); drawPoint(batch, centerX + y, centerY + x, color); drawPoint(batch, centerX - y, centerY + x, color); drawPoint(batch, centerX + y, centerY - x, color); drawPoint(batch, centerX - y, centerY - x, color); } The other way:
      public static void drawCircle(PolygonSpriteBatch target, Vector2 center, float radius, int lineWidth, int segments, int tintColorR, int tintColorG, int tintColorB, int tintColorA) { Vector2[] vertices = new Vector2[segments]; double increment = Math.PI * 2.0 / segments; double theta = 0.0; for (int i = 0; i < segments; i++) { vertices[i] = new Vector2((float) Math.cos(theta) * radius + center.x, (float) Math.sin(theta) * radius + center.y); theta += increment; } drawPolygon(target, vertices, lineWidth, segments, tintColorR, tintColorG, tintColorB, tintColorA); } In the render loop:
      polygonSpriteBatch.begin(); Bitmap.drawBresenhamCircle(polygonSpriteBatch,500,300,200,ColorRGBA.Blue); Bitmap.drawCircle(polygonSpriteBatch,new Vector2(500,300),200,5,50,255,0,0,255); polygonSpriteBatch.end(); I am trying to choose one of them. So I thought that I should go with the one that does not involve heavy calculations and is efficient and faster.  It is said that the use of floating point numbers , trigonometric operations etc. slows down things a bit.  What do you think would be the best method to use?  When I compared the code by observing the time taken by the flow from start of the method to the end, it shows that the second one is faster. (I think I am doing something wrong here ).
      Please help!  
      Thank you.  
    • By Sandman Academy
      Downloadable at:
      https://virva.itch.io/sandman-academy
      https://gamejolt.com/games/sandmanacademy/329088
      https://www.indiexpo.net/en/games/sandman-academy
      https://www.gamefront.com/@sandmanacademy
      http://www.indiedb.com/games/sandman-academy
    • By Sandman Academy
      Downloadable at:
      https://virva.itch.io/sandman-academy
      https://gamejolt.com/games/sandmanacademy/329088
      https://www.indiexpo.net/en/games/sandman-academy
      https://www.gamefront.com/@sandmanacademy
      http://www.indiedb.com/games/sandman-academy
    • By Sandman Academy
      Downloadable at:
      https://virva.itch.io/sandman-academy
      https://gamejolt.com/games/sandmanacademy/329088
      https://www.indiexpo.net/en/games/sandman-academy
      https://www.gamefront.com/@sandmanacademy
      http://www.indiedb.com/games/sandman-academy
  • Advertisement
  • Advertisement
Sign in to follow this  

Algorithm Collision detection algorithm for sphere tree (static)

Recommended Posts

I am programming boolean operations on 3D meshes which are described by sphere trees. They do not deform, nor change in time anyhow. However to generate the environments I need to perform boolean operations on them as fast as possible. I need to find all the collisions between polygons (triangles). What is the best approach / algorithm for that purpose? I haven't found anything particularly useful via Google.

In detail: I am in need for an algorithm that will take two sphere trees and return the buffer of all collisions. I do not have much experience in using sphere trees so my idea is to check every polygon from the first mesh with the second mesh sphere tree and vice versa.  Somehow I feel that is a waste of CPU power. Could anyone give me a description of better approach or some useful links?

 

Share this post


Link to post
Share on other sites
Advertisement

A sphere can be represented precisely using a simple equation. Storing a bounding volume as a polygon mesh is kind of defeating the purpose of a bounding volume, which is to be easier to operate on than the geometry inside it.

You can do some simple fast math to get sphere-sphere intersections, and thereby compute the exact set of space that overlaps between two hierarchies.

https://en.m.wikipedia.org/wiki/Sphere#Equations_in_three-dimensional_space

https://en.m.wikipedia.org/wiki/Bounding_volume_hierarchy

 

http://mathworld.wolfram.com/Sphere-SphereIntersection.html

 

If you specifically want to do collision e.g. for physics, the area to research is broadphase algorithms such as:

https://en.m.wikipedia.org/wiki/Sweep_and_prune

 

 

Share this post


Link to post
Share on other sites
2 hours ago, Misery said:

my idea is to check every polygon from the first mesh with the second mesh sphere tree and vice versa.

That's the usual way to do it, and i'd recommend doing so and focus on the larger problem of the boolean operations first. (People say this hard due to limited floating point precision if you need robust results that keeps a closed surface. Read here how libigl warps two libraries: Cork which probably works like you intend, and another (maybe from CGAL) using exact arithmetic to guarantee robustness but being slow: http://libigl.github.io/libigl/tutorial/tutorial.html#booleanoperationsonmeshes)

Back on the tree topic: You could change the algorithm to find potential overlaps by going wider and using much more memory, somehow (but not exactly!) like this:

 

For each tree level starting from the root

{

For each node store a list of intersecting nodes of the same tree level.

for each child go over parents intersection list and refine to their children.

}

 

At the end you have for each node a list of intersecting neighbours.

Advantage is that you do not start at root again and again for each triangle, and you do not everything twice. But code complexity is higher - usually worth only for realtime work and it may need too much memory to store all lists for high poly models. Consider it as a optimization you might do later.

 

Edit: Thinking more if it, did you consider just using a regular grid? High memory needs as well but much less work.

 

Edited by JoeJ

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Advertisement