Refactor vertex functions to enable composite paths

[GregStanton]

Increasing Access

This enhancement will provide greater access to individuals in multiple circumstances.

Code contributors:
For volunteers who have less experience with large codebases or less free time to navigate them, it will become feasible to contribute to vertex-related features. For example, there is community support for a new arcVertex() function, but the complexity of the current codebase has impeded progress.

Users:
For users who want to make composite shapes, the existing p5 API will work as they expect it to, so they will face less confusion. A knowledge barrier will also be removed, since they won't need to learn the native canvas API or SVG in order to make composite shapes.

Most appropriate sub-area of p5.js?

• Accessibility
• Color
• Core/Environment/Rendering
• Data
• DOM
• Events
• Image
• IO
• Math
• Typography
• Utilities
• WebGL
• Build Process
• Unit Testing
• Internalization
• Friendly Errors
• Other (specify if possible)

Feature enhancement details

Problem

Mixing path primitives

Users expect to be able to create composite paths with a mix of path primitives (line segments, quadratic Bézier curves, cubic Bézier curves, and Catmull-Rom splines). The p5 reference does not indicate that general mixing is not possible, and it's already possible with native canvas paths and SVG paths.

However, the current p5 implementation assumes shapes include at most one type of nonlinear path. For example, see the 2D renderer's endShape() method. This limitation leads to unexpected behavior in a range of cases. A couple of these are illustrated below.

	Expected shape	Actual result
Quadratic and cubic Béziers
Lines and Catmull-Rom splines

Complexity of the codebase

With the current implementation, it will be difficult to support mixing vertex types (e.g. #906), to track down bugs (e.g. #6555), and to implement new features (e.g. #6459). The difficulty arises from specific functions as well as broader code organization:

• The 2D renderer's endShape() method is an example of a specific function with room for improvement. It has too many responsibilities, as it contains rendering code for all vertex types. It also directly includes a mathematical conversion from Catmull-Rom splines to Bezier curves that partly duplicates work done by a separate function in p5.Font.js, and it contains dead code (it repeatedly checks if shapeKind is equal to constants.POLYGON, but no such constant is defined in constants.js).
• The way code is divided across the codebase is an example of an organizational challenge. This makes it difficult to determine where new drawing code should go.

Solution

Separation of concerns

We can solve many of these problems at once by separating concerns. The idea is to create classes for the different vertex types, each with their own data and their own methods that add them to the canvas. Then vertex(), quadraticVertex(), etc. just push vertex instances of the appropriate type into a path array. When endShape() is called, it simply loops over the vertex objects, and they add themselves to the canvas; endShape() doesn't need to know that curveVertex() requires special logic, for example. By refactoring in this way, mixing path primitives is essentially automatic, with no change to the public p5 API.

Proof of concept

I put together a proof of concept in the p5 Web Editor; it includes an implementation of arcVertex() as proposed in issue #6459. A separate sketch shows how it fixes unexpected mixing behavior. With these two enhancements together (arcVertex() and composite paths), p5's beginShape()/endShape() will be able to produce composite paths with all the basic primitives of the native canvas API and SVG, plus Catmull-Rom splines. Based on some discussion, it looks like it will also help with the bug observed in issue #6555. Although the proof of concept focuses on the 2D case, the goal is to accommodate the 3D case as well, with some adjustments.

Update: Task list

Calling all volunteers!

@davepagurek, @limzykenneth, @xanderjl, @Gaurav-1306, @Jaivignesh-afk, @sudhanshuv1, @capGoblin, @lindapaiste

Based on discussions here, in the online meeting, and on Discord, we're going to use this comment as an overall implementation guide, and we've decided to organize the work according to the following tasks:

• Update reference to explicitly describe the new behaviors
• Create snapshots of existing behavior, for the visual tests
• Decide how to refactor normal()*
• Decide whether to rename default contour kind to SEGMENTS or leave it as null*
• Increase consistency in usage and documentation of default values
• Decide on the file structure*
• Implement Shape, Contour, and primitive shape classes
• Implement creator functions*
  • Decide if we want wrappers (e.g. createPoint() for () => new Point(\*data*\))
  • Implement wrappers or do nothing if we decide to omit them
• Implement PrimitiveShapeCreators (a JavaScript Map object)*
• Implement 2D and 3D output visitor classes
• Implement drawShape() on 2D and 3D renderers and refactor user-facing functions
• Develop PointAtLengthGetter**
• Consider new primitives based on existing combinations of vertex and shape kinds**

*: A separate GitHub Issue does not need to be created.
**: A separate GitHub Issue should be created, but not yet.

For all the unmarked tasks, I'll set up separate issues with more details as soon as I get a chance, and the task list will link to them. Any code should be committed to the new vertex-refactor branch @davepagurek set up, and we'll merge it into the main branch once the time is right. For right now, we can get started by discussing the tasks marked with a single asterisk!

[Gaurav-1306]

I would like to work on this issue.

Just a little hiccup, i can start in the next 2 weeks, so if someone wants to do it before that they can, but after that i would like to work on this issue.
@GregStanton thanks again for the update 😃

[GregStanton]

Hi @Gaurav-1306! It's great that you want to work on this! We may want to break this up into smaller tasks that multiple people can work on. Maybe the first thing is to make a list of people who are interested. Maybe one person can take the lead by dividing up tasks. When I get a chance, I can think more about that, but I'd love to hear from others on this.

[Jaivignesh-afk]

I would like work on this as well!!

[limzykenneth]

Great write up @GregStanton! I like the idea of having internal classes for each type of vertices and it also makes it possible for addon libraries to implement their own unique vertices that can work with beginShape() and endShape().

As a start can we work out a common interface that each of the classes should adhere to? ie. What properties and methods should they all have? What are the signatures of the methods?

After that or at the same time we can figure out how the internals call the methods/interface. For anyone interested in working on this, please work out a proposal in this issue first. You can test out code implementation in the web editor as @GregStanton has done with the proof of concept. Thanks!

[GregStanton]

Thanks for the kind words @limzykenneth, and for helping to direct the effort! I'm really glad you like the idea.

I'm not sure if you noticed, but the code that makes my proof of concept work is all located in shape.js, inside the project's file directory. I think it may provide initial answers to your questions. For example, the vertex classes all have the following interface:

• data property
  • description: array holding the vertex and other data (e.g. control points) passed to the associated p5 function
  • usage: in the case of CurveVertex objects, this property holds data from consecutive calls to curveVertex()
• type property
  • description: type of vertex (possible values are constants.VERTEX, constants.QUADRATIC_VERTEX, etc.)
  • usage: curveVertex() function checks type to see if it needs to push data into an existing CurveVertex object
• coordinates getter
  • description: returns vertex coordinates from data (e.g. in CurveVertex, this is the second-to-last data point)
  • usage: endShape() uses it to keep track of the current point on the path, for use by ArcVertex
• addToCanvasPath() method
  • description: takes no parameters; adds the corresponding subpath to the canvas
  • usage: called by endShape()

Possible next steps/questions

1. Does anyone want to extend my proof of concept to the 3D case? This might mean adding a method or getter analogous to addToCanvasPath(), but it would output vertices; @davepagurek mentioned something along these lines on Discord.
2. Does anyone want to extend my proof of concept so that it supports contours? I think Dave also suggested a nested array that starts with _path as in shape.js and holds additional arrays for the contours after that.
3. I'm glad you mentioned extensibility; that's a good point to keep in mind. I guess we'd need to expose something like shape.js's _path array in order to allow add-on libraries to create new vertex types? Maybe there's another way.

Edit: Maybe @Gaurav-1306 or @Jaivignesh-afk can divide up points 1. and 2. above, regarding the 3D case and contours?

[limzykenneth]

I'm glad you mentioned extensibility; that's a good point to keep in mind. I guess we'd need to expose something like shape.js's _path array in order to allow add-on libraries to create new vertex types? Maybe there's another way.

We don't necessarily have to to figure this out at this point. Once we have the implementation working with the flexibility we want, we can revisit at a later point. That is to say it's a nice to have but not must have.

[davepagurek]

For 3D support: in WebGL, each path/contour ends up just as an array of vertices, so each segment would need to be able to convert itself into a polyline. This will also depend on the level of detail, so its interface for WebGL would have to look something like:

interface Segment {
  first: boolean
  addToCanvasPath(ctx: CanvasRenderingContext2D): void
  addToPolyline(polyline: Array<p5.Vector>, curveDetail: number): void
}

Here I've also made this a void function that mutates the array to be consistent with the way the 2D one works, but outputting an array of vertices which we then concatenate to a big list would also work.

I've also added a first property here because I assume for 2D mode, each vertex may need to know if it needs to moveTo or if it needs to lineTo based on whether it's the start of a path/contour.

To support contours, if we have:

type CompositePath = Array<Segment>

...then a full shape would be:

type Shape = Array<CompositePath>

where beginShape() starts off the shape as [[]] (just one composite path, initially empty), and each beginContour call pushes a new empty array to the shape to add a new contour. (The main shape and contours can be treated the same.)

[GregStanton]

Replying to #6560 (comment) by @davepagurek:

Thanks! This is very helpful. There's some tension between the idea of vertex classes and segment classes; I think you were right to switch over to segment classes. The deciding factor for me is that it seems natural to put all the Catmull-Rom vertices in a single object, and it doesn't make sense to think of that as a singular "vertex" object.

Below, I propose a few tweaks that combine (and hopefully refine) the interfaces we each suggested. I'm using a TypeScript-like syntax as an informal shorthand (e.g. get doesn't actually work in TypeScript interfaces, as far as I know).

Proposed interfaces

If these sound good, we can test them by incorporating them into a new version of the proof of concept. (That's good because I don't have the extra time right now to think this through completely! I think it makes sense, though.)

interface PathSegment {
  data: Array<number | string>;
  type: string;
  get endVertex(): p5.Vector;
  addToCanvasPath(ctx: CanvasRenderingContext2D): void;
  addToVertexPath(shape: Shape, curveDetail: number): void;
}

interface Path = {
  segments: Array<PathSegment>;
  currentVertex: p5.Vector;
}

interface Shape {
  boundary: Path;
  vertexBoundary: Array<p5.Vector>;
  contours: Array<Path>;
  vertexContours: Array<Array<p5.Vector>>;
  currentPath: Path;
}

Notes

• PathSegment
  • first: I omitted this because I think it may be unnecessary? When endShape() loops over the segments in a new path, it knows which of the segments is first, so I think it can call moveTo() before it calls addToCanvasPath(). That's what the proof of concept does without contours, but it seems like it should work for those too.
  • data: Includes everything needed to specify the segment including supporting data (control points, extra vertices for Catmull-Rom splines, ellipse parameters for an arc, etc.) and an ending vertex. The starting vertex doesn't need to be stored, since that can be pulled from the currentVertex property of the relevant Path object.
  • type: May equal LINE, QUADRATIC, BEZIER, or CURVE (later, we can add ARC to the list). An example use is that curveVertex(x, y) can check the current segment's type, and if it's a curve, it can push x and y into its data property instead of starting a new segment.
  • endVertex: Can be pulled from the data property. In a Catmull-Rom spline, it's the second-to-last vertex.
  • addToVertexPath(): Adds vertices to shape.vertexBoundary or shape.vertexContours.
• Path:
  • Why have a property for the current vertex? In general, it should be helpful to keep track of the ending vertex of the last segment that's been added to the canvas or vertex path; ArcSegment will definitely need it for internal calculations.
  • How can the current vertex be updated? The current vertex can be updated by endShape() after it calls addToCanvasPath() or addToVertexPath().
• Shape
  • Why separate boundary from contours? Since p5 publicly distinguishes between these, separating them in the implementation has certain advantages. For example, the user can create the boundary and contours in any order, and internally, it will still be easy to distinguish the boundary from the contours.
  • How it might work: Internally, we can create one Shape instance. Then beginShape() can reset the shape's boundary and contours array, and it can set its currentPath to the boundary; beginContour() can push an empty path into the contours array and set currentPath to that. Then, the vertex functions don't need to know what kind of path they're working on; they just push to the current path. Once segments have been pushed to a contour or the boundary, either endContour() or endShape() will loop over them, adding them to a canvas or vertex path; these end functions can also set the currentPath to boundary, in case the user creates the boundary after creating one or more contours.

[sudhanshuv1]

I would also like to work om this issue!

[davepagurek]

Thanks @GregStanton! I took some time to think through the implementation some more and have some more refinement to propose (or at least spelling out some of the separation of concerns more explicitly for implementers.) Ideally p5.Renderer just acts as an adapter between the p5 public API and Shape. Then, when the shape is complete, p5.RendererGL and p5.Renderer2D only need to extract the data from Shape in the format they need.

For easier testing and to keep the code clean, I'd ideally like to keep Shape/Path/PathSegment as decoupled as possible. There's a bit of mixing right now between what the data of these classes contain, and the algorithm of how they get constructed. Both are important, but I'd ideally like to have some invariants so that there's less confusing state management. How do you feel about these as some things to try to keep true during construction/drawing:

• Each class doesn't need to reach "up" to its parent to get info, it is all provided during construction. This is to make testing easier and so there's less for contributors to learn when fixing a bug at one level
• The data structure is the same during construction and during drawing (meaning we'd dynamically derive what part we're working on, e.g. with a getCurrentPath() that returns the last path in an array rather than storing it separately, so that there are less states we have to consider)

With that in mind, here are some more thoughts for public interfaces (omitting internal state for now as an implementation detail).

interface Shape {
  // To be called by `p5.Renderer` from public drawing API methods:
  addVertex(v: VertexInfo)
  addCurveVertex(v: VertexInfo)
  addArcVertex(v: VertexInfo, options: ArcVertexOptions)
  addQuadraticVertex(v1: VertexInfo, v2: VertexInfo)
  addBezierVertex(v1: VertexInfo, v2: VertexInfo, v3: VertexInfo)
  startPath()
  endPath()
  closePath()

  // To be called from `p5.RendererGL` and `p5.Renderer2D` to draw to the screen
  toVertices(curveDetail: number): Array<Array<VertexInfo>> // Array of arrays for each contour
  drawToCanvas(ctx: CanvasRenderingContext2D)
}

interface VertexInfo {
  position: p5.Vector

  // WebGL-specific data per vertex or control point:
  texCoord?: [number, number]
  fill?: [number, number, number, number]
}

Not necessary for a proof-of-concept, but just as a heads up, WebGL mode has more info than just position data for vertices, so I've made an interface for everything that might include. I think you can generally substitute VertexInfo everywhere we previously only had p5.Vector so it's not too hard of a switch when implementing things for real.

I've also only opted to include startPath and endPath here, still treating paths/contours uniformly, because while it's potentially easier for people to understand contours as being separate things from the boundary, there actually is no underlying distinction in the data: if you want to draw a venn diagram shape, you need to draw two circles, and it doesn't matter which circle is the "contour" or the "boundary": both paths contribute to both at different times, so there's not really a reason for users to add a boundary later. For that reason I feel like it makes more sense in the renderer implementation to match how the rendering works rather than how the public API is set up. (The public API's insistence of there being one boundary if you have contours can get in the way sometimes, especially when using non-p5 data. I'd love the ability to draw shapes where you only have contours so that if you want to draw a font glyph from its source path information, you don't have to special-case the first contour in the glyph, and can instead treat all contours in the glyph uniformly.)

So then Shape has to make calls to construct the paths, and to "export" them to the canvas or to a vertex array. I imagine that means Shape makes new paths in the start/endPath methods, and otherwise forwards the vertex methods on to the paths themselves.

interface Path {
  addVertex(v: VertexInfo)
  addCurveVertex(v: VertexInfo)
  addArcVertex(v: VertexInfo, options: ArcVertexOptions)
  addQuadraticVertex(v1: VertexInfo, v2: VertexInfo)
  addBezierVertex(v1: VertexInfo, v2: VertexInfo, v3: VertexInfo)
  closePath()

  toVertices(curveDetail: number): Array<VertexInfo> // Just one array now at this level
  drawToCanvas(ctx: CanvasRenderingContext2D)

  firstVertex(): VertexInfo // For segments, if needed
}

The vertex adder methods on Path will do a lot of the heavy lifting of figuring out when to construct new segments and of what type. The idea is that that's Path's responsibility, and then Segment is just responsible for translating that data into actual drawing commands or vertices.

Since I'm just documenting the public API, I've omitted things like the current vertex. The idea is that the path should know its own current vertex (or can be derived by getting the last vertex of its last segment), but nothing externally needs to know that.

Following @GregStanton's idea, if segments don't know their index, paths would create an array containing the first vertex of the first segment, and then calling addToVertexPath on each segment adds everything except the first vertex of the segment to the path since that will be covered by the array already. I've added a startVertex getter to facilitate that.

interface PathSegment {
  type: string
  index: number
  startVertex(): VertexInfo
  endVertex(): VertexInfo
  drawToCanvas(ctx: CanvasRenderingContext2D)
  addToVertexPath(shape: Shape, curveDetail: number)
}

[GregStanton]

Replying to #6560 (comment) by @davepagurek:

Thank you for all this work! One of my favorite things about software development is iterating like this. My previous proposal needed to be adjusted to improve encapsulation, and it looks like you've taken the next steps. Instead of state changes coming from anywhere, we now have objects being responsible for modifying themselves. I see how removing internal state from the interfaces (like the data property in my last proposal) expresses this intent more clearly.

Eventually, we may want to specify the interfaces, the internal state for classes that implement them, and as @limzykenneth suggested, the expected call sites for the various methods. That could be a guide for implementers.

But first, I think I'll be able to provide better feedback on the interface details after I have a few questions answered.

Questions

2D vs. 3D

I'm now thinking we really have two shape models:

• In the 2D case, we have a segment-based model: shape → paths → path segments. The path segments are added directly to the canvas, e.g. with the native quadraticCurveTo() function.
• In the 3D case, we have a vertex-based model: shape → paths → vertices. The vertices are connected by line segments in the canvas.

If we follow the single-responsibility principle, it seems like these should be implemented in separate classes. People interested in the 2D functionality may think the vertex-related code is relevant to them, when in fact it's not.

Maybe we could specify a common Shape interface that abstracts out anything common to the two cases, and then we could extend it with Shape2D and Shape3D interfaces? I'd need to spend more time to figure out what this would look like, so I figure it's good to float the general idea first.

Did I break it up too much?

Conceptually, our shapes are built from paths, and our paths are built from segments or vertices. It seems nice to organize our code to reflect this. On the other hand, breaking it up means a single function call turns into three. If we want to draw a shape, we now call a drawing method on the shape, and that calls a drawing method on a path, and that calls a drawing method on a segment.

It's not currently clear to me if this is a step backward or a step forward. Maybe we should focus on breaking up the code horizontally (between 2D and 3D cases) rather than vertically (shapes, paths, and path segments)? Is it possible that doing both would mean breaking things up too much? Maybe we could just use a Path type in our specification, rather than a full interface, like you had originally?

Boundary vs. contours

I'd love the ability to draw shapes where you only have contours...

I think you're right about combining "boundary" and "contours." The original idea is to make beginShape()/endShape() as flexible as the native canvas API by supporting composite paths; since p5 already supports moveTo() operations via beginContour()/endContour(), it seems reasonable to take advantage of the full generality there as well.

Do you see any reason why we couldn't treat beginContour()/endContour() as a general way to create the paths that make up a shape, without requiring a separate boundary to be created first? It seems like this could be done without breaking existing sketches.