Hairy Triangles

[Dana-Ferguson]

I'm working on an SVG parser (I'm gonna open source it). In order to support triangulating shapes with holes in them, I ported over Triangle.Net (I hope this isn't the part where you tell me I could of done that with StageXL). I'm still testing a lot of things, but it appears that if I just make a path-based-triangles, vertexes with small angles extend passed their intended target. To throttle up the effect (but not too crazy, like the finger print material light icon) I created a circle (standard from svg arc commands) and I just had the arc command run through 160 steps each (for a 320 vertex circle).

With the shape being a circle, I was able to math the points out to make sure they were where they should be. The path points and the triangle points were good. Well.. the triangle points where within half a pixel of correct (the C# library was using the decimal type for precision for small angles).

And to really make it crazy, here is a 20 pixel radius circle (all the points where within 0.05 pixels of their correct spots this time ( woot! ).

And then, after that, I added a triangle that should be bounded within the box it's in; which then I realized I could of started there, and skipped the story and the mathing of the circles (whoops). But, I also wanted to ask if there was a more efficient interface in StageXL for getting an array of triangles into the canvas?

    var tx = 275;
    var ty = 50;
    graphics.moveTo(tx, ty);
    graphics.lineTo(tx + 1, ty);
    graphics.lineTo(tx +0.5, 100 + ty);
    graphics.closePath();
    graphics.strokeColor(Color.Black);

    graphics.beginPath();
    graphics.rect(tx-10, ty, 20, 100);
    graphics.closePath();
    graphics.strokeColor(Color.Black);
    addChild(new Sprite()..graphics = graphics);

[Dana-Ferguson]

Now, that I'm thinking more about it, I guess I'd need away to overload hit detection too, or just let it be a box (but that wouldn't work as well for SVG in games I suppose).

[Dana-Ferguson]

I thought I'd poke around and take a look at stageXL's insides. PFM. I can't figure out how the path segments go from vertices to triangles (I originally thought you were using PolyK, but that appears to not be the case).

I found RenderProgramTriangle and renderTriangle, but I've been unable to figure out how to use it so far (I suppose the next step is to verify its not some weird WebGL issue, so I'm trying to route around some of the stageXL stuffs).

I tested in Chrome & IE so its not a dartium issue.

[Dana-Ferguson]

Good news.... after fumbling through WebGL, I learned that its not a problem with WebGL. Looking nice:

(the test circle, triangle filled \ wireframed, and the fingerprint icon from MDL)

(I have the pathing turned up to generate a lot of triangles atm, for testing)

[bp74]

Hi Joshua! This is really great, i got quite a few requests for SVG support in the past so there is definitely need for such a library. I will answer all your questions a little bit later today. Just wanted to give a quick feedback that i'm excited about your work.

[nilsdoehring]

Hi Joshua,

great initiative, I will definitely make use of this! I just wanted to share with you some AS3 SVG libraries, that might serve as inspiration and should be easy to port (at least in parts). https://github.com/millermedeiros/SVGParser <-- also exports to html5 canvas https://github.com/LucasLorentz/AS3SVGRenderer (there might be more)

Looking forward to use this! Nils

2016-03-11 9:09 GMT+01:00 Bernhard notifications@github.com:

Hi Joshua! This is really great, i got quite a few requests for SVG support in the past so there is definitely need for such a library. I will answer all your questions a little bit later today. Just wanted to give a quick feedback that i'm excited about your work.

— Reply to this email directly or view it on GitHub https://github.com/bp74/StageXL/issues/231#issuecomment-195246913.

[Dana-Ferguson]

Cool! I will definitely take a look at those links.

I got simple holes up and going (now I got to go pay bills).

[bp74]

The thing with the holes is very cool. StageXL currently does not support holes with the WebGL renderer because it is hard to calculate those holes. Is the triangulation done with the port of Triangle.Net? In StageXL we use a very simple ear clipping algorithm which can't calculate holes but the complexity is very low and it's pretty fast for most use cases (except there is a huge number of vertices).

[Dana-Ferguson]

Yeap, I did that with the port. I do worry about performance, but so far, its been fast enough that I haven't noticed it being slow. But as long as its one and done calculations (for SVG's that aren't changing scale), I can't imagine it becoming a problem. I'm sure the library I'm using is definitely slower ( designed for C, ported to C#, ported to Dart ... its got some baggage ).

It has some other cool features too that allow it to further refine the mesh.

[Dana-Ferguson]

So, I looked up ear clipping. It looks like that shouldn't move any vertices around (since it uses what's already there), so that makes me more confused about the hairy triangle bug.

[bp74]

Okay it's time to answer some of your questions. I don't know exactly what questions are still relevant, so i will start by talking a little bit about drawing triangles :)

The way how a Graphics objects is rendered in StageXL depends very much on the renderer that is used. There are two renderer - the Canvas2D renderer and the WebGL renderer. If you use the Canvas2D renderer all the graphics commands are translated to native HTML5 canvas render commands and the browser figures out how to draw the fills and strokes. But if you use the WebGL renderer (which is the default) StageXL has to calculate lots of vertices and triangles which can be rendered with WebGL.

A Graphics object in StageXL consists of a list of GraphicsCommands. Every time you call a method like moveTo, lineTo, arcTo a graphics command is created and added to the GraphicsCommand list. This way the Graphics object remembers all the commands and uses those commands to do hit-testing and drawing. The user can even change the parameters of those GraphicsCommand to change the shape after the Graphics object was created.

Under the hood all the GraphicsCommands are calling methods on the GraphicsContext. There are different implementations of the GraphicsContext interface - one for bounds calculations, one for hit test, one for the Canvas2D renderer and one for the WebGL renderer. You could even create a custom GraphicsCommand implementation which may look like this:

var shape = new Shape();
var customGraphicsCommand = new CustomGraphicsCommand();
shape.graphics.addCommand(customGraphicsCommand);
shape.addTo(stage);

class CustomGraphicsCommand extends GraphicsCommand {
  void updateContext(GraphicsContext context) {
    context.moveTo(0.0, 0.0);
    context.lineTo(100.0, 0.0);
    context.lineTo(100.0 ,100.0);
    context.lineTo(0.0, 100.0);
    context.fillColor(Color.Red);
  }
}

The GraphicsContext class has similar methods as the Graphics class. The difference is that the methods of Graphics will creates GraphicsCommands and the methods of GraphicsContext are creating vertices (or triangulations) directly. In your use case you could create a custom GraphicsCommand which calls the methods on GraphicsContext instead of Graphics, which improves performance because you don't create tons of standard GraphicsCommand instances for moveTo, lineTo, arcTo, etc. (see lib/drawing/commands/...)

If you look at the "lib/drawing/internal" classes you will find "graphics_path" and "graphics_stroke" classes. The difference is this: Vertices are added to the graphics_path by calling lineTo, moveTo, arcTo, etc. on the GraphicsContext class. The graphics_path is triangulated to do fills. But if you want to do strokes, new vertices are calculated from the vertices in the graphics_path. A graphics path may consist of several segments. Once a stroke is drawn, a stroke segment is calculated for each path segment. Let's look at this example:

graphics.moveTo(0,0);  // create a vertex (0,0) in the first graphics path segment
graphics.lineTo(100,100); // create a vertex (100,100) in the first graphics path segment
graphics.moveTo(200,0); // will create a new vertext but als a new graphics path segment
graphics.lineTo(200,200); // adds a vertex to the second graphics path segment
graphics.stroke(Color.Red); // creates 2 graphics stroke segments (from the 2 path segments)

Wow this is getting long and i know it's a little bit tricky to understand. Let's stop here and i will write a second reply talking about something different ....

[bp74]

Let's talk about something completely different now: If you do your own triangulations for your fills, you don't need the graphics implementation at all. In fact you will get better performance if you don't use the graphics classes for this use case. You could create your own DisplayObject and draw the triangles directly!

class Star extends DisplayObject {

  @override  
  void render(RenderState renderState) {
    Int16List ixList = [0,1,2,1,2,3, ...]
    Float32List vxList = [x1,y1,x2,y2,x3,y3,x4,y4, ....]
    renderState.renderTriangleMesh(ixList, vxList, Color.Red);
  }
}

This display object will render triangles - lots of triangles and very fast! All you have to do is provide an index-list (ixList) and a vertex-list (vxList). If your code does all the triangulation you can render it directly without using the graphics class at all. The only drawback is that you don't have strokes (lines) since your triangulation probably only does fills. But a stroke is not so different. A stroke are just more vertices calculated based on the path vertices.

[Dana-Ferguson]

I definitely like the idea of extending the GraphicsCommand. And I like extending DisplayObject even more.

[Dana-Ferguson]

Is there a way I can include the color information in the vxList so I can do the SVG gradients?

[bp74]

Hmmm .. that's a good question. No there isn't but it would be easy to add this feature to the WebGL renderer. If you want to do the same thing with the Canvas2D renderer it would be more difficult.

If you look at the RenderProgramTriangle class (in the engine folder) you see that we apply the same color to all vertices. This could be changed to add a different color to the vertices. Your display Object would look like this:

class Star extends DisplayObject {

  void render(RenderState renderState) {
    var renderContext = renderState.renderContext;
    if (renderContext is RenderContextWebGL) {
      var rp = renderContext.renderProgramTriangle;
      renderContext.activateBlendMode(renderState.globalBlendMode);
      renderContext.activateRenderProgram(rp);
      rp.renderTriangleMeshWithColors(renderState, ixList, vxList);
    } else {
      // TOOD: something for the Canvas2D renderer
    }
  }
}

This will activate the right BlendMode (how the new pixels are blended with the existing pixels) and the render program that is used by the WebGL renderer. Once the render program is activated you call the renderTriangleMeshWithColors (which is a new method that does not exist today) that renders the triangles with custom colors.

The renderTriangleMeshWithColors would pretty much look like the renderTriangleMesh method that is already in place today.

[bp74]

Of course you could create a clone of the RenderProgramTriangle class in your library too. This way you could start without the change in StageXL (which is prefered because we are planning to get closer to StageXL 1.0 and i don't want to add new features right now).

[Dana-Ferguson]

I can do that. I think a lot of people (myself included) want to see StageXL 1.0.

[Dana-Ferguson]

What you've given me so far, is going to be very helpful. It really helped fill in some of my knowledge gaps (or lack of creativity???? I didn't even think about the extends you just showed me), I just started learning Dart last month, so I'm spending half my time in the Dart docs.

[bp74]

You are welcome! Don't hesitate to ask more questions.

Btw. this is a best practice to create new instances of custom render programs:

if (renderContext is RenderContextWebGL) {
  var rpIdentifier = "RenderProgramTriangleEx";
  var rp = renderContext.getRenderProgram(rpIdentifier, () => new RenderProgramTriangleEx());
  renderContext.activateBlendMode(renderState.globalBlendMode);
  renderContext.activateRenderProgram(rp);
  rp.renderTriangleMeshWithColors(renderState, ixList, vxList);
}

This way only one instance of a RenderProgram is created for each renderContext (you can have more than one renderContext if the application is using two Stages with two canvas elements).

[Dana-Ferguson]

I used the overriding render in a DisplayObject extension. No hairy triangles. (although the original problem still lingers)

[bp74]

Sorry i have to ask a stupid question, what exactly is wrong with this rendering? Probably the thing on the right side. Where does the rectangle and line come from?

[Dana-Ferguson]

The triangle in the rectangle (drawn through graphics commands) is the same height as the rectangle itself. The skinnier the triangle is the worse it gets, but if you look at the 'sun' in the first image, its actually a circle made of triangles. It just looks 'fuzzy' (or hairy) when rendered at a regular size. This effect gets a lot worse when rending an SVG icon with any beziers or arcs in it, since they'll likely to have very skinny triangles in them (I'm gonna trim those later when I start worrying more about optimizing .. vs functionality).

    var tx = 275;
    var ty = 50;
    graphics.moveTo(tx, ty);
    graphics.lineTo(tx + 1, ty);
    graphics.lineTo(tx +0.5, 100 + ty);
    graphics.closePath();
    graphics.strokeColor(Color.Black);

    graphics.beginPath();
    graphics.rect(tx-10, ty, 20, 100);
    graphics.closePath();
    graphics.strokeColor(Color.Black);

(this is the code rendering the triangle and box)

[Dana-Ferguson]

This is a 10 pixel wide 100 pixel tall triangle. (The effect basically goes to zero as you approach an equilateral triangle)

[bp74]

I think it's the stroke that get's infinitely long.

Test 1: how does the triangle look with the Canvas2D renderer. This will cause problems with the renderTriangleMesh in the DisplayObject.render method, since Canvas2D does not render with WebGL render programs.

// please set this at the start of the program. 
StageXL.stageOptions.renderEngine = RenderEngine.Canvas2D;

Test 2: How does the triangle look like with JointStyle BEVEL instead of MITER?

graphics.strokeColor(Color.Black, 1.0, JointStyle.BEVEL);

[bp74]

Another question: The hairy stroke of the circle in the very first image - do you draw the complete path of the circle with ONE strokeColor command, or do you use multiple strokeColor commands?

[Dana-Ferguson]

Multiple.

[bp74]

Okay i think this is the problem. If the joint style is "MITER" and the angle is very small, the lines are getting very long. In the Canvas2D they use a miter limit of 10 (i think) and the WebGL renderer currently has no miter limit at all. The miter limit is the maximum length of the joint in relation to the line with.

http://help.adobe.com/en_US/FlashPlatform/reference/actionscript/3/flash/display/JointStyle.html

[Dana-Ferguson]

You are correct. I'd of been able to get to that quicker. But I was re-arranging my file structure (trying to move it closer to Dart idiomatic? folder style, instead of throwing around files randomly)

[Dana-Ferguson]

Setting to Canvas changed nothing, setting to Bevel eliminated the issue.

[bp74]

This image was stolen from the internet :)

This shows that the MITER joint is getting longer as the angle get's smaller. An angle of 0 would give you an infinite miter length (it's limited to 10 with the Canvas2D renderer and it is currently not limited with the WebGL renderer). If you use the BEVEL joint you won't get this problem but you will get more vertices and more triangles.

If you draw the circle with 160 lineTo commands, followed by a closePath and a strokeColor it should work fine - even with JointStyle.MITER (which is the most efficent)

[Dana-Ferguson]

It makes a lot of sense, now that I know about it, but I'd of never guessed that miter would do that (even a miter limit of 10 on canvas seems pretty high to me).

Yeah, I stole this one. (googled it when I saw the Bevel magic) http://i.stack.imgur.com/AMFuU.png

[Dana-Ferguson]

Oh yeah, the test with the circle was because I wasn't sure what was causing the problem, so I just wanted a simple shape so I could take a look what was happening to my svg shapes (that finger print icon looked inhuman -- too messy to see what was up).

If I had thought about going fill only and turning lines off, I'd of figured it out sooner. I thought I did do that (but there was also a bug in my port earlier, I must of fixed it, and then not gone back and retried fill-only)

[Dana-Ferguson]

Well, best outcome for a dumb question, now I'm able to draw the triangles directly and my svg class can act as a display object, which is a lot nicer than its original svg.GetSprite() function.

Thx!

[bp74]

Great! I'm happy that everything works now. Your questions regarding the graphics class were absolutely justified. I also have to admit that there are corner cases where the graphics class (especially with the WebGL renderer) will render unexpected results. Most of those corner cases will be improved in the future but the graphics class may never be perfect. The reason is that StageXL's main focus isn't vector graphics but drawing pixels as fast as possible. To add perfect graphics we would need to add much more code like your triangle.net port. So i think your library could fill a space where people need rich vector graphics features. Thanks for your great work!