Sunday, October 11, 2009

Connected Networks, Shaping Points, and WED

I implemented connected networks in WED and I'm about to go rip the code out and try again. What went wrong?

Well, first, to be clear:
• A "curve" in computational geometry terms is just a line you could draw without lifting your pen. So a line segment, a bezier curve, a circle, or a Z shape, those are all "curves".
• A connected network is a series of curves where each curve ends in a node. Two curves starting/ending at the same point share the node at that point. (In other words, two curves may cross without a node, but if two curves end at a node, the node is always shared.)
• A shaping point is a point on a curve used to define the curve (like a sharp corner in our "Z" shape) that is not a node. Conceptually the lines on both sides of the shaping point are part of the same curve.
This concept is already used in X-Plane - it is the foundation for the road grid system. (Nodes represent the real junctions where a car can make a decision.) One note from the X-Plane road system: since shaping points don't define a break between two curves, but rather the shape of one big curve, we need to insert a node if the road is going to change types at a point. In other words, we need a node to start/end a road, have an intersection with another road, or change types. Otherwise a shaping point is fine.

I was working on connected networks support in WED. WED has an underlying set of geometric primitives. Putting new editing features in is trivially easy when the geometric primitives exist. (For example, overlay editing uses the same geometry as airports, so it was an easy feature.) But WED does not yet have connected network support. We need it to edit road grids and we will probably need it to define the taxi paths of AI airplanes in the future.

The Naive Approach

So the first thing I did was define an "edge" type. Its interface is a point sequence, but it had the special property that its end nodes were shared points, while its internal (shape) points were "contained" inside the primitive.

This worked and I can edit using this type, but it turns out it doesn't really work very well. Here are all of the reasons why this turned out to be a poor design choice:
• The user interface doesn't make obvious distinctions between nodes and shaping points, but the data model does. This means that a lot of operations have to convert nodes to shape points or vice versa. Thus the editing logic spends a lot of time trying to 'maintain' the rules about nodes vs. shape points.
• To make it worse, since nodes are not part of a curve but shape points are, it means our points are constantly appearing and disappearing from the hierarchy of editing primitives as a shape point becomes a node (which can have a real name) or not. Furthermore, the number of edges is constantly changing. The change in the hierarchy presented to the user makes sense if you are familiar with topology theory...which is to say, it doesn't make much sense at all.
• The internal code for the edge itself has a lot of special cases because the end nodes and internal nodes are different. This starts to matter when we consider several bezier curves ending at a single point. Normally WED keeps the curve control handle with the point, but if a point is shared, this doesn't work, so this information has to belong to the edge.
Take 2

So the new design will try a different assumption: no shape points. Every point will split a curve into two parts whether it's a shaping point or not. The good:
• All nodes are handled the same, and no rules have to be enforced. Every point is a node, and we're done. Every segment is a bezier curve, with the control handles owned by the edge.