Metaball-terrain collision
Here comes the first milestone where the metaballs are actually animated! Adding gravity to the metaballs was easy as pie, simply looping through them and updating their velocity by the gravity acceleration 9.82 m/s^2 every frame is not expensive, nor is it difficult. The hard part of this milestone has been the collision detection.
The collision detection is fuelled by ray-triangle intersections. Each frame, each metaball's previous position is recorded, then the metaball is moved according to its velocity (after the velocity has been update in accordance with acceleration). The new position and the old position form a line between them. This line can be thought of as a ray originating in the previous position and having the direction face toward the current position. The terrain is a triangle mesh, and so it is made up of a collection of triangles. Each frame, going through each triangle for each ball and testing whether there was an intersection between the ray and the triangle is the basic idea of the collision detection. Setting the new velocity and position after the collision is simple, assuming the ground absorbs some energy and otherwise reflects the ball's velocity.
This collision detection technique is naive and extremely slow, especially for larger terrain meshes. Therefore, I implemented a axis-aligned bounding-box (AABB) tree to speed it up. Associating each leaf of the tree with 8 triangles, the computation time is significantly decreased. Below is a comparison of the amount of computation per frame over time, recorded during runtime using Unity's profiler. As can be seen in the figure, the naive approach is about 60 times more expensive.
A problem, however, that haunts all collision detection between points and triangles is the problem of precision in floating point numbers. No matter what technique is used, there is a risk that a point will fall between two triangles that are supposed to stick together. With more points and a long time, the risk grows boundlessly, so it is guaranteed to happen. With the AABB approach, there were more points falling through, so a hybrid approach was used, to minimize both fallthrough rate and computation time. The hybrid approach meant first doing the AABB approach, but if no intersection was found, the naive approach was done. The performance of the hybrid approach is seen below. The naive approach is about two times as expensive, judging solely from the figure, and by observation, the fallthrough rate was significantly decreased.
Even using the naive approach, the fallthrough was too great. To solve this, every time there is an intersection, the ball is moved upward by a constant amount. This avoids having the balls roll toward a triangle seam and fall. This reduced the fallthrough rate without any computational cost, and without much loss of realism in the simulation. Additionally, when balls eventually fall through, they are moved to a new random location on the terrain. This could be interpreted as the water draining into the ground, and later, when water spawns from a single location, relocating a ball after fallthrough will not look as unrealistic.
Further, some materials were changed, and a short demo was recorded. The demo video is presented below.
Also, a playable WebGL build was created as a snapshot of the progress. It is available here, and should be playable in most browsers: https://geodropstudios.github.io/misc/metawaterDemos/first/index.html
Github commit for this progress: 40c675c03cd90d517ab98cc0d59e1c89ae09a0f6
The collision detection is fuelled by ray-triangle intersections. Each frame, each metaball's previous position is recorded, then the metaball is moved according to its velocity (after the velocity has been update in accordance with acceleration). The new position and the old position form a line between them. This line can be thought of as a ray originating in the previous position and having the direction face toward the current position. The terrain is a triangle mesh, and so it is made up of a collection of triangles. Each frame, going through each triangle for each ball and testing whether there was an intersection between the ray and the triangle is the basic idea of the collision detection. Setting the new velocity and position after the collision is simple, assuming the ground absorbs some energy and otherwise reflects the ball's velocity.
This collision detection technique is naive and extremely slow, especially for larger terrain meshes. Therefore, I implemented a axis-aligned bounding-box (AABB) tree to speed it up. Associating each leaf of the tree with 8 triangles, the computation time is significantly decreased. Below is a comparison of the amount of computation per frame over time, recorded during runtime using Unity's profiler. As can be seen in the figure, the naive approach is about 60 times more expensive.
A problem, however, that haunts all collision detection between points and triangles is the problem of precision in floating point numbers. No matter what technique is used, there is a risk that a point will fall between two triangles that are supposed to stick together. With more points and a long time, the risk grows boundlessly, so it is guaranteed to happen. With the AABB approach, there were more points falling through, so a hybrid approach was used, to minimize both fallthrough rate and computation time. The hybrid approach meant first doing the AABB approach, but if no intersection was found, the naive approach was done. The performance of the hybrid approach is seen below. The naive approach is about two times as expensive, judging solely from the figure, and by observation, the fallthrough rate was significantly decreased.
Even using the naive approach, the fallthrough was too great. To solve this, every time there is an intersection, the ball is moved upward by a constant amount. This avoids having the balls roll toward a triangle seam and fall. This reduced the fallthrough rate without any computational cost, and without much loss of realism in the simulation. Additionally, when balls eventually fall through, they are moved to a new random location on the terrain. This could be interpreted as the water draining into the ground, and later, when water spawns from a single location, relocating a ball after fallthrough will not look as unrealistic.
Further, some materials were changed, and a short demo was recorded. The demo video is presented below.
Also, a playable WebGL build was created as a snapshot of the progress. It is available here, and should be playable in most browsers: https://geodropstudios.github.io/misc/metawaterDemos/first/index.html
Github commit for this progress: 40c675c03cd90d517ab98cc0d59e1c89ae09a0f6
Kommentarer
Skicka en kommentar