Saturday, November 20, 2021

Power Lines for Procedural Cities

I've made a lot of recent progress on 3DWorld's procedural cities, in particular the residential neighborhoods. They've definitely improved over the past few months as I've added fences, swimming pools, etc.

I walked around outside in my real life neighborhood to try and observe what objects I was missing in my scenes. One type item that stood out was telephone poles. I can add these as well as the wires that distribute power along the roads in my cities. Since I'm only going to create the power lines for now, and not the telephone wires, I'll call these "power poles" for the remainder of this post to match the name I use in the source code.

I started by adding wooden poles along one side of the road in both north-south and east-west directions. A single pole is placed halfway between each block/plot in each dimension, and a pole is placed in the corner of each intersection to connect the wires running in orthogonal directions. Then I added wooden cross beams to the tops of each pole to hold the wires. These are at different heights for each N-S/E-W direction at the corner pole to keep the wires from intersecting and shorting out.

Next, I added the wires themselves. A set of three high voltage wires run across the tops of the poles, while a stack of three low voltage wires are spaced vertically below them. I modeled wires as long thin black cubes. Making them pure black avoids having any shading that varies with lighting calculated from the vertex normals. This makes it impossible to tell that these are cubes rather than cylinders, unless you're looking into the square cross section of the end of the wire. Wires are attached to the pole and cross beams with white ceramic insulating standoffs. These are only drawn when the player is close as an optimization.

Power poles at intersections that connect wires running in the two directions have additional wires that connect the upper and lower set of three high voltage lines. They also have a transformer with connections between the high voltage and low voltage sets of wires. All of this produces a fully connected and electrically sound power grid. Real power grids don't have redundant connections that create loops, but this is close enough.

Finally, I connect houses and streetlights to the low voltage power lines with additional wires. Houses connect to points near the closest power pole. Streetlights connect to the closest low voltage wires, which are generally either the ones directly above the streetlight or directly across the street from it. The thinner wires connecting houses and streetlights to the low voltage power lines are drawn as a single wire rather than three separate wires to simplify the code. This effectively treats them as three bundled wires braided/wrapped around a steel support cable, as is common in residential areas. This multi-wire is connected to the three wires stretching between poles with a short vertical wire segment.

Here is an example of my power poles and power lines viewed at street level. I think I have the basic scales and styles pretty close to the reference images I used of real power lines.

Power lines connecting to houses and streetlights as viewed from the ground.
Everything is drawn with level of detail (LOD) based on a combination of object size and distance to the camera so that smaller objects are only drawn when the player is close by. In addition, cylinders and truncated cones are drawn with fewer vertices/divisions when further from the player. I use the bounding cubes of groups of wires and the poles themselves for view frustum culling to avoid drawing components that aren't visible to the player. The average draw time for all of these additional features is only around 1.5% of the total scene draw time.

One tricky problem was handling the power poles on the edges and corners of the grid. This can only happen for the poles placed at the corners of intersections as the remaining poles are placed on the interior of the city blocks. These power poles must be handled as special cases because the wires only connect in a subset of the directions and must be properly terminated at insulating standoffs. Poles on the edges connect with wires in three directions rather than four, while poles on the four corners of the grid only connect in two directions. In addition, the wires connecting to the transformer and between the upper and lower high voltage triplets must be moved to the direction of the pole facing the interior of the city. This allows the vertical connecting wires to connect properly to wires above and below.

Here's a second example, viewed from above with the camera in "flight" mode. Can you actually tell that these wires are cubes rather than cylinders? I can't.

Power line grid following roads, viewed from above.
This looks pretty good for now. I may add larger metal transmission lines connecting the different cities to each other at some point in the future. I don't have any generators or other sources of power to connect these to at this time. I haven't decided what to do about commercial cities with office buildings yet because the power lines are more likely to intersect with the larger buildings. Maybe it's okay to assume these cities use underground power lines and omit the poles.

Thursday, November 4, 2021


I showed some images of new clothing and hanger models in closets in the last post. While I was looking for clothing models, I came across a monarch butterfly model created by Paul Spooner and decided to add that to 3DWorld. This somewhat fits with my "animals" module, which previously included only birds and fish. So, surprise! This isn't another update on buildings or cities. I'm going back and working on procedural generation in nature.

Butterflies, like birds, are flying animals. Flying and swimming animals such as fish are easier to implement than animals walking on the ground in some ways, and more difficult in other ways. Their physics tends to be more complex because it's all in 3D with a vertical elevation component. On the other hand, collision detection is easier since there aren't as many objects to collide with in the air and water. In fact, the probability of two animals colliding is low enough that I can basically ignore it.

Butterflies inherit from my animal C++ class and share some of the code with birds and fish. For example, they share code for random spawning within a terrain tile, logic to allow them to cross between tiles, per-frame physics updates, visibility queries, and drawing. What else can I share with the existing code? Let's see, I can reuse the 3D model drawing code with all of the orientation transform code from fish. (Birds are drawn as three flattened spheres rather than 3D models.) I can reuse the simple wing animation logic from birds. The steering behavior can be somewhat reused from the random walk of both fish and birds, though I certainly have to extend this system. I suppose I need logic to choose destinations and fly to them as well, because butterflies tend to land on plants and other objects. I don't have any code for that in the fish or birds system, but I can use a similar model to cars and pedestrians. So it looks like all the major components are there. I just have to copy/paste the right pieces and/or factor out the reusable parts.

The first task was to list all of the features I planned to add, in the order I planned to add them:

  • Loading and drawing of butterfly 3D model
  • Spawning in appropriate areas of tiles (over grass, avoiding water/rock/snow/cities)
  • Flight logic with random walk
  • Collision detection with scene objects (terrain, trees, plants, buildings, etc.)
  • Wing animation (model split into body + two rotating wings)
  • Choice of destination and logic to fly to destination
  • Optimizations
  • Color and wing pattern variations

Loading the model, drawing, and setting spawn points was pretty easy. Of course I had the size scale way off on my first attempt:

My first attempt: The Attack of the Giant Butterflies

At least the butterflies aren't hard to find! One side effect was that it was pretty easy to tune the model drawing and animation code when they're this large and easy to see.

It took me a few attempts to animate these models. I eventually decided to use a sine wave to rotate the wings 45 degrees about the body in opposite directions for each side. This isn't perfect as the wings clip slightly through each other and through the body. I watched a video showing butterflies moving in slow motion for reference. It seems like their wings don't quite rotate about a point as a rigid body as I was attempting to imitate. Instead, they flop around and bend like stiff cloth or paper. While my solution doesn't look great when viewing a stationary butterfly close up, it's actually difficult to spot the self intersections once the butterfly is small and moving in erratic patterns.

Flight logic was an interesting topic, and probably the one I spent the most total time on. Real butterflies don't fly in straight lines; their paths are much more random. This applies to their altitude as well as their heading. I decided to keep the butterfly model level with the ground and split the movement into an XY component parallel to the ground and a vertical (Z) altitude component. The variables controlling motion are:

  • Speed (affects movement speed, turn rate, and wing flap rate; tied to realtime)
  • Rotation angle about vertical/Z axis / in XY plane to control direction
  • Vertical acceleration to change altitude

I wanted to ensure very smooth movement, so I chose to add a random value to an accumulator for each of these variables each frame. The accumulator is then integrated over time to calculate an acceleration, which is then multiplied by time to get velocity, which is then multiplied by time again to update the position and direction of the butterfly. This should guarantee the path is second order continuous. All variables are clamped to a reasonable value at the end of a physics update. This includes caps for min and max altitude, max speed, max turn rate, etc. There are lots of constants I had to keep adjusting to get reasonable behavior, and now butterflies fly around in crazy random paths in an unpredictable way. Just like in real life!

Then I added code to choose destination points. I have flowers in the grass, but there are thousands of them per tile. Flowers are drawn using instancing and aren't actual game objects. This means I can't easily choose them as destinations. I went with using the tops of various types of plants as destinations instead, since butterflies often land on leaves. Butterflies in cities will choose to land on the grass in parks, if there's a park nearby. Otherwise they simply fly around randomly and try to avoid the buildings.

Their behavior finite state machine actually has four states: explore, find destination, approach, and rest. Butterflies start out in the "explore" state. After some time has elapsed, they will enter the "find destination" state and every so often will consider a random plant or park. If they find one that's close by and visible, they will enter the "approach" state. After landing at their destination they enter the "rest" state for a few seconds, then take off with a vertical ascent and transition back to the "explore" state. This logic results in butterflies moving from plant to plant in a slow, winding path.

Choosing destinations was easy; actually getting them to fly there was much more difficult. How exactly is this crazy random flight path supposed to end the butterfly at a particular location? After some experimenting, I decided to use the distance to the destination to blend between "explore" and "approach" behaviors. The approach force increases as the distance to the destination decreases. At first, when they're far away, there will be a weak force pulling them toward the destination. The random behavior will mostly override this force, but they will slowly drift toward the destination over time. As they get closer, the approach force will increase in strength, allowing them to eventually home in on their target. They may take a very roundabout path, but they do eventually get there. It could be in tens of seconds or a few minutes. It took many attempts to avoid the oscillation behavior during these state transitions, especially when they're very close to the destination but have the wrong altitude.

When I first implemented this I had no idea why the butterflies [mis-]behaved the way they did. I had to add debug visualization to show their flight path as a string of spheres, their destination point, and the line to their destination. The line color reflects the magnitude of the approach force: blue for weak, red for strong. These debug visuals also helped me find the butterflies in the scene, which are super tiny compared to the mountains, buildings, and trees. Here's an example where I have the debug visualization turned on but the trees and grass turned off.

Butterfly path and destination debug visualizations helped me get the logic right. It's obvious how their paths are nowhere near a straight line.

You can see just how wavy some of those paths are. This debug mode definitely helped, and I was eventually able to get everything working. Here's a video where I follow a butterfly around for a minute or so as it lands on a plant and takes off again.

I had to add a LOD (level of detail) optimization where the body and legs weren't draw unless the butterfly was close to the player. The only other optimization that was needed was better early rejection of trees and plants during collision detection. I reused the code I had for player sphere collisions, and it was never optimized for use with a thousand actors.

The final step was adding wing color and texture variation. The initial texture had the wing colors baked into the same texture atlas as the body. Paul sent me a texture with white wings that I was able to recolor in my code by overriding the model's material color per butterfly instance. I added a mix of monarchs and butterflies with white, yellow, orange, blue, and violet wing markings. These single colors don't look as nice as the multiple colors in the monarchs, but at least they add more color variety. I've taken a screenshot of a three butterflies here: monarch, yellow, and violet.

I added some other butterfly colors mixed in with the monarchs. Do you see the violet one on the right?

I created a second video with a large number of butterflies. There are thousands in this scene. The player is free to move anywhere in the world and new tiles with new butterflies will be generated around them.

I'm pretty happy with how this mini project turned out. It was a week well spent. Is it time to add other animals or insects, or time to get back to cities and buildings? I don't know, I guess we'll have to wait and see.

If I do decide to continue with butterflies, I might add a mating dance between males and females. I'm sure that getting the motion correct for a pair of them should be trivial. Right?

The source code for butterflies can be found here if you're interested.