CSG / WebGL / simplification / intersection / polygonalization / tesselation

[jonathanolson]

Related snippets from the TODO file.

Intersection:

• see http://cagd.cs.byu.edu/~557/text/ch7.pdf
• Sweep-line handling: http://www.lems.brown.edu/~wq/projects/cs252.html

CSG:

• Will rely on region support + clipping algorithms
• Union / difference / intersection / XOR. consider a NOTHING and EVERYTHING shape like bounds?
• As a stop-gap, http://sourceforge.net/p/jsclipper/wiki/Home/ will handle polygons (but shapes will have many more segments)

Polygonalization

• Needed for WebGL, in addition to tesselation

Simplification

• Collapse "close" points
• Handling or removal of degenerate segments
• Remove self-intersection, group regions?
• Normalize winding order so it can be combined with other shape fills

WebGL support? Probably just export a discretization with vertices. Region handling is important for this.

Region support:

• Edge cases (literally):
  • Multiple curves intersect at same point with same tangent, but have different curvatures
  • Overlapping segments (like a circle and a circular arc)
• Break into regions that can test for nonzero/evenodd, then combine adjacent ones so we can have efficient segments without the 'stroked region' overlap
• Fixes self-intersection in 'stroked' path
• Allows Constructive Solid Geometry
  • Intersection of each type of segment - how to handle endpoint intersections in general

[jonathanolson]

For CSG, we should include nonzero/evenodd support

[jonathanolson]

Had a few more thoughts about how to simplify the shape/region processing for this, and was able to break it up into conceptual chunks that are all pretty well defined and fairly simple. I'm quite a bit more confident that this is fully do-able in a more reasonable amount of time. What follows is basically a brain-dump about the plan.

Goals:

1. CAG (https://github.com/phetsims/kite/issues/30). Union, difference, intersection, etc. between shapes. Will include "inverted" shapes that include the outside but not the inside (e.g. to intersect an array of Shapes, start with an "everything" shape). Should not require discretization into line segments (hurts Scenery hit-testing performance).
2. WebGL display with triangles.
3. WebGL display with Loop-Blinn. Trickier than with triangles, but should be much faster.
4. General simplification (combination of overlapping segments, overlapping points, handling self-intersection, combine collinear adjacent line segments, etc.). Important for getting stroked shapes that are simpler, for dilation/offset shapes, etc.

Detailed "steps" below. Basically we convert to a graph (segments are edges), process intersections and simplify, compute what faces are filled, construct regions out of filled faces, and turn them into Shapes with outside borders and holes. For WebGL display, we then triangulate based on the type of display. Discretization (adaptive) and triangulation would both benefit from using 3rd party libraries, particularly since we've processed it into a more usable state.

Step 1 (Graph conversion): Convert to edge-segment form (a mathematical graph where edges are segments). Each subpath becomes a loop of edges with vertices (simple). At this point, subpaths are not connected. For future processing, store metadata about each subpath along the edges.

Step 2 (Simplification/intersection): (Iterated?) intersection and simplification. Detect self-intersection and intersection between components. Splits edges at intersections (handling T-intersections or overlapping endpoints), combines overlapping edges, collapses vertices, and removes vertices with order 1 (represents something with no filled area). Each vertex should maintain an ORDERED list of outgoing edges, and to which end of the segment each edge is, ordered counter-clockwise. If the vertex has edges going out at the same angle, use the derivative. If they also have the same derivative, use the 2nd derivative (curvature), etc. For all of this, maintain subpath metadata, so that each subpath is essentially an ordered list of edges, each of which stores which "direction" it follows along the edge (from start to end, or end to start).

Step 3 (Face extraction): From the graph, compute the faces (CCW for all interior ones, and CW for the outside "face"). This can be done by following each edge in both directions, always turning CCW at a vertex (thus why they have ordered edges).

Step 4 (Face fill): Compute winding number of each face for each shape. Then using the nonzero/evenodd fill rules, determine which faces are "filled" and which aren't. It's possible for the "outside" face to be filled.

Optional Step 5 (CAG Operation): For multiple shapes, apply binary operations for each face, depending on whether it should be "filled" for each shape (XOR, etc.).

Step 6 (Regions): Traverse the faces to combine all faces that are "filled" and adjacent together into "regions". Regions basically have an outer path boundary, and zero or more inner hole boundaries. Optionally, this step may break regions into hole-less regions, as this may be helpful for triangulation.

Step 7 (Edge combination): Combine together segments along the boundaries into one segment if possible (e.g. collinear lines that are adjacent). Important, since we may have split them in the simplification/intersection step.

Optional Step 8 (Shape Output): For CAG or simplification, we now have non-self-intersecting Shapes with clearly defined holes.

Step 9 (Discretization): For triangulation, we turn curved segments into multiple line segments. For loop-blinn, we split segments until their nets will not overlap, and treat them somewhat similarly to line segments.

Step 10 (Triangulation):

• (a) for Loop-blinn, we use constrained Delunay triangulation, resulting in curved segments having their own triangle that they will be contained in.
• (b) for full triangulation, we do a line-sweep to process into triangles/trapezoids and then monotone polygons, which then can be triangulated on their own.

[jonathanolson]

Lack of implementation causing problems for https://github.com/phetsims/proportion-playground/issues/58.

Furthermore, it looks like the Loop-Blinn method would be the best.

The initial steps for an EdgeGraph would be to

1. Determine if segments overlap continuously. If so, record and split where necessary.
2. Determine if segments intersect. If so, record & split.
3. Determine if the new segment crosses through a point.

This would allow an incrementally-built data structure with the above properties. Cubic/Quadratic/Line overlap computation is done, Arc/EllipticalArc would be needed (ordering the 4 potential points to determine overlap), and checks to determine if segments contain a point would be needed.

[jonathanolson]

Mostly complete, but triangulation and Loop-Blinn are not implemented (leaving open).

[jonathanolson]

IMPORTANT NOTE: Loop-Blinn is patent-encumbered (2007), so it's a no-go. A viable option (that wouldn't be using the implicit bezier forms for the shaders) would be to break them into piecewise-elliptical-arc segments based on the start/end tangents (which should look smooth enough for general use), and the implicit equation for ellipses is trivial.

[jonathanolson]

https://github.com/phetsims/scenery/issues/323 is related.