Thursday, October 13, 2016

Fun with Stacking Spheres and Cubes

This is more of a fun post compared to some of my previous technical posts. I'll be sure to add a lot of YouTube videos below and a few static images at the end. This is my first interactive scene editor feature, but is more for fun and amusement rather than real level editing. I don't imagine I could create any useful level by placing various one meter cubes and spheres one at a time in front of the player's camera.

The following videos show my progress on dynamic object placement. I've made huge improvements in my workflow and "artistic quality" over the past week. There are many additional improvements to be done and features to add. I believe that eventually this system can be made into a full level editor, but it has a long way to go before it's useful for this purpose.

None of these videos were recorded with sound. I still only have two options for video recording: Fraps with sound, limited to 30 seconds; and ffmpeg with unlimited length but no sound. I'm sure I'll figure it out eventually.

The first video shows a stack of 1 meter cubes of a variety of different materials that I slowly placed one on top of each other. It was more fun to push the stack down than it was to build it. Note that I didn't have dynamic shadows working for the cubes at this point. I later added the ability to destroy cubes with weapons instead of only being able to push them around and knock them down.

After a while I grew tired of placing blocks one-by-one, so I made the placement delay another in-game user editable parameter. I found it was much easier to create large piles of cubes and spheres with the delay set to 0. In reality it's one per frame, or 16ms delay for a framerate of 60 FPS.

This next videos shows how I can create large stacks of cubes. I still hadn't added shadows. The cubes are created so that they stack but don't intersect each other. If I have collision detection turned on, I'll quickly wall myself into a corner. But if I disable collision detection I can just insert the cubes into one place and they'll form a stack as the bottom cube is inserted at the bottom and will push all the other cubes up... or maybe the new cube is inserted and pops up to the top of the stack. I'm really not sure - the code is pretty complex, and it all happens within a single frame. At least the cubes don't intersect with anything, which is the most important property. Oh, and if I made the cubes small enough, I could probably walk up them like stairs. I really should try that and record a video if it works.

I had the material editing menu up for much of the video so that I could easily change the materials. It would be nice to hide the menu somehow in the future while still having a way to change the textures. The material itself can be selected with a hotkey from a user-created list of predefined materials that is read with the scene data, but it doesn't have the variety of textures I wanted to use for this video.

There is a small yellow number printed near the center of the screen that counts the number of objects placed. Here I've placed 1533 cubes and spheres. This was added to track how many objects can be created within reasonable performance constraints.

I finally enabled shadows for the cubes and spheres. I spent some time creating high stacks and then knocked them down in this next video. It was pretty fun! All of the weapons push the cubes around, but the rocket launcher has the most force per unit time. The seek-and-destroy has about twice the force, but fires too slowly. If I make the cubes small enough, around 0.4m on a side, I can push them out of the stack with a rocket or two. All the cubes above the one that was pushed out will fall in quick succession. The system is very stable, but this many cubes hurts the frame rate at this stage of development.

I tried to stack spheres next. At first it didn't work because the collision detection for this case wasn't fully implemented, and the spheres just sat there overlapping each other, forming a giant blob of spheres. My attempted fix had a surprising an unexpected effect, shown in the video below. Groups of spheres stuck together in a quivering unstable ball, then floated off on a random path toward the sky. Sometimes the sphere clusters got stuck on static level geometry and pulsated there. What's going on here? I recorded the video, but I hadn't enabled a lower screen resolution and the video compression couldn't keep up well. The frame rate dropped, leading to a laggy recording where some parts ran at up to 2x realtime. Sorry. I've reduced the sphere drawing time by 5-10x since recording this so it shouldn't be as much of a problem in the future.

What was causing this bug? I had the collision response vector sign backwards, and colliding spheres were being pulled together like magnets rather than pushed apart. They would overshoot and separate slightly, only to be pulled back together in the other direction. Some instability (floating-point error?) caused the clusters of attracted spheres to drift off in random directions with a random walk. Some sank into the floor/ground, some floated off into the sky, and some got stuck in the static level geometry such as the lamp posts and building walls. If I had come across this bug without just having rewritten the sphere intersection code, I would have never figured it out. The effect was pretty funny though. I might even add an option to enable it from within the material editor. Magnetic materials? Negative gravity materials? I'll have a hard time justifying this as anything resembling real physics!

I later got spheres working without much trouble. They stick to each other like masses of fish eggs. This actually reminds me of the little colored sticky foam balls that my daughter used for building sculptures and got spread all over the house. The user can disable player collision detection and float around creating sculptures of 1 meter spheres that fill the level. I'm not sure what use this is in real gameplay, but you can get a few thousand spheres scattered about before the framerate starts to drop.

Maybe it's unrealistic to stick brick spheres together like this. What should really happen when placing spheres this way in a sane world? I guess they would all fall down and roll around until they covered the ground - but that's no fun! Maybe I can make another option to control this later.

The final video of this post shows the exploding cube effect. I can mark objects as exploding in the material editor, and then fill the scene with them. Any hit from a weapon will detonate the object and also destroy the surrounding objects within the blast radius. One explosion takes out several cubes at a time, which allows me to destroy them all much more quickly. This clears space for placing even more stacks. I call it the "undo" feature. If you need more precision, there's also a "shatterable" material mode that will only destroy the object that was directly hit with weapon fire.

I spent some time stacking cubes and pushing them down, but it's not too much different from what I've shown in the previous videos. Here are two images of my "artwork". The first image shows a few thousand stacked cubes of various sizes and materials. This was earlier in the development when the framerate was too low to add more, and shadows still weren't enabled.

Thousands of stacked cubes of various materials and sizes litter the courtyard. The office workers are hiding in fear.

Imagine having this stack of cubes outside a real office building! Would anyone want to walk anywhere near it? In a real environment, the wind would probably push these stacks over, and one falling stack would bring all of the others down like dominoes. This stuff is fun to build due to the pure absurdity of the whole system. But, keep in mind, this is just a prototype of the level editor that in the future will be used to construct structures such as the office building itself. It's in no way meant to represent physically correct physics or real gameplay. I'm not creating another Minecraft clone here.

This next image shows a scene that took quite a while to create, even with one cube placed per frame. There are over 10,000 cubes here, in stacks that reach hundreds of feet into the sky. Some of them go above the cloud layer and beyond the far clipping plane so that the boxes at the top aren't even visible to the player. The stacks take up to 10s to fall if you remove a block near the bottom and watch the rest of them drop one by one. However, they do still completely fall. Shadows and indirect lighting from the lamps in the courtyard are enabled.

More than 10,000 cubes stack to the sky. This artwork took me a while to create and was a shame to lose when I realized I hadn't completed the "Save Level" feature yet.

It was a shame to create this wonderful bit of cube insanity and then throw it all away when I quit 3DWorld. See, I didn't implement a "Save Level" feature until after creating this scene. On the plus side, this problem encouraged me to finish the save feature in a hurry. Now the save system is complete, and I can save, load, and modify all of my cube and sphere creations as much as I want.

This post is short on technical details, so I should probably talk about why the performance was poor in the beginning, how I improved it, and how the physics works.

There are two types of user placeable objects in 3DWorld: dynamic objects and movable static objects. There are various other object types, but they can't be created by the player. The previous post on sphere and cube materials was all about dynamic objects. These include weapons, ammo, projectile effects, smiley body parts, etc. Anything that has free movement physics is a dynamic object. These objects support Newtonian physics with gravity, elastic and inelastic collisions, momentum, friction, air resistance, buoyancy, etc. Basically, all of the physical parameters that are normally modeled in games and physics engines, plus a few obscure ones that have little impact on the physics but were fun or challenging (= fun) to add.

There are three problems associated with building using dynamic objects:
  1. The physics really only works correctly for spheres (as implemented in 3DWorld).
  2. This system is too expensive for simulating thousands of interacting objects.
  3. There are problems with stability when creating stacks of objects.
The solution to these problems is to use a different physics system that solves for static constraints rather than realtime dynamics. I've extended my framework for movable (player pushable) static objects to work with user-placed material cubes and spheres. It works better with cubes since they have flat surfaces and the constraints are simpler, but it's acceptable for spheres. I could in theory add support for other 3DWorld shapes: cylinder, cone, capsule, torus, polygon, extruded polygon. However, that's a lot more work, and these other more complex shapes have more parameters that need to be set by the user. Cubes and spheres only have one parameter: size/radius.

When I say static objects, I really mean persistent objects that are created once and last forever, and will remain in place if no dynamic forces act on them. Static movable objects have a more limited set of physical parameters and a simpler physics model. There is no momentum, torque, friction, or elasticity. All collision responses other than gravity are resolved statically within a single frame. They can be pushed around by the player, stacked, and dropped - but that's about it. As I've shown in previous posts, buoyancy in water works, as do some other minor effects. Since there is no torque or friction, and materials are infinitely hard/rigid, they can be placed in stable stacks of unlimited height. As long as there is an object below supporting the objects above, everything stays in place. Remove one object (cube) from the bottom, and the cubes above will fall one-by-one until the entire stack has fallen down to the next supporting block (or the ground). Since static cubes don't rotate when stacked, any contact point on the bottom of the cube will support it, even if it's just a tiny corner of another cube. At least this simplifies the math.

Static objects are faster to simulate than dynamic objects, but they're still not free. My 10K blocks scene was dropping the frame rate all the way down to 40 FPS. Almost all the time (maybe 80%) was in querying the scene bounding volume hierarchy (BVH) for adjacent objects that were either supporting or resting on the current query object. The BVH was built incrementally while the objects were added, so it may not be optimal, in particular for these dense stacks.

The important observation here is that most of the time, an object is not moving at all. In fact, the majority of the game frames observe no block motion. The blocks only move when dropped, pushed, or shot at by the player, and there's a limit to how many blocks a player can get moving at the same time. The fix is to track which objects are moving vs. "sleeping" and not simulate the sleeping objects every frame. I used an active counter to track how many frames it's been since each object was last updated/moved. If an object goes for 8 consecutive frames without moving, it's marked as sleeping and only checked for collision once every 16 frames. This cuts the simulation time down by a factor of 16 in mostly static scenes. To avoid large delays with falling objects, every active object wakes up all other objects within a certain distance of it when it moves. If the player fires a rocket at a cube, the collision/explosion will wake up the cube, which will wake up the cubes above and below it as it falls. The chain effect will incrementally wake up the entire stack (but just that one stack), and make all of the blocks fall in quick succession.

This change improved the framerate from 40FPS to 90FPS. Good enough for now. I think the framerate is currently limited by actually drawing all of the cubes, or maybe the occlusion culling. I should be able to create 15K+ cubes while still hitting a solid 60 FPS. Spheres are more expensive to draw, so I can only have about 2000 of them in the scene.