freenode/#clim - IRC Chatlog
Search
4:00:10
loke
Yes. That's why I can't use the CLIM rule when drawing that. But yes, when drawing CLIM desgins, I need to follow the clim rule, which means whatever algorithm I choose, needs to be able to handle both.
4:03:06
beach
To me, it looks like compounding problems. We use a library that gives the wrong result, so we need to use an algorithm that can handle self-intersecting polygons, and we need to use the wrong algorithm so that the end result is what we expect.
4:05:49
loke
But is there a library that does it right? I'm not in a position to implement this stuff myself.
4:07:09
loke
cl-vectors is designed to be a rasteriser though, and it does that job decently. Also, it's not very maintained anymore.
4:07:54
loke
So a reimplementation of the path drawing is probably a correct solution. But who wants to implement that?
4:10:12
beach
I don't have time right now because I am very busy with SICL, but I do remember looking at the technique used by cl-vectors and deciding that it is very wrong.
4:36:44
beach
A Metafont thing. You can use a pen with some shape like a slanted ellipse, and draw a curve with it. It gives you calligraphic effects.
4:39:04
loke
I only need to support the caps and joints that CLIM supports (butt/bound and miter/point)
4:39:07
beach
The computations involved in order to turn that stuff into a path are non trivial. Which is probably why cl-vectors gets it wrong.
4:40:34
loke
beach: If we do it from scratch, there is no need to turn it into a path. We can just convert the joints and caps directly into triangles. That's much easier. HOWEVER, that still doesn't solve the problem of drawing arbitrary polgygons in CLIM (I believe CLIM also support splines here?)
4:41:01
loke
The end goal here is to replace all of the existing CLX primitive graphics operations with Xrender.
4:44:29
beach
So here is what I think. I think that CLIM does not support splines, but I think McCLIM does and maybe some vendor-version of CLIM as well. And I thin we do want that stuff. The question, then, is how much do we want? I am thinking that if we need to do the same computations for the simple cases as we need to do for (say) arbitrary pen shapes, we might as well consider the general case.
4:45:25
loke
I want to do line drawing first. That means support for caps and joints. Other features are not immediately needed.
4:46:47
loke
Beach: I can also do plain line drawing with Xrender. Look at the beautiful antialiasing :-) https://photos.app.goo.gl/Vh8TeKjNJYyKpBFy5
4:47:05
ck_
beach has already said this, but my literature research yesterday conforms it as well -- there are pretty much no algorithms that want non-simple polygons as input
4:48:18
ck_
so we should concentrate on that as a first step: complex point removal, which should not be too hard
4:49:24
ck_
because I'd really like to not run into 'the gameboy problem' because of a wrong choice at the start
4:50:36
ck_
I just invented that, but if you remember oder game systems, they were usually made with a certain complexity on the screen in mind. If you created situations in which there were more than the couple of sprites to be animated on the screen, the program slowed down
4:52:23
ck_
The Chapter on Triangulation in de Berg's book has a couple of references to papers. The executive summary is: Best complexity is O(n log(*) n), using randomized algorithms, and those lead to simpler implementations than the classical approach as well
4:52:51
loke
beach: Don't you like the antialiasing? (the problem is that I can't do endcaps at the moment)
4:56:42
loke
beach: It's just an image. Are we looking at the same one? What aspect of it is it you don't like?
4:57:55
ck_
Here's the n log(*) n papers that were referenced: Tarjan and von Wyk, A fast Las Vegas Algorithm for triangulating a simple polygon: https://link.springer.com/content/pdf/10.1007/BF02187741.pdf
5:18:54
ck_
I could be wrong about my last point though, depends on whether you want to remove overlappings or not
5:19:48
ck_
it's very simple as you can see, but will suffer from the numerical instability beach has already talked about
5:20:18
ck_
and I totally agree that this gets swept under the rug pretty much every time edge cases in omputer graphics are discussed (or not discussed) in any meeting that touches on it
5:28:54
beach
loke: For the simple case of circular line caps, can't you just draw a circle at the end of the line?
5:29:39
ck_
I believe the issue is that while yes, we could do that, it doesn't really help for the general case
5:30:34
ck_
I suggested that as well; but my understanding of lokes position is that if we start with custom triangulation of clim primitives we will row into rough waters because of our own set of special cases
5:31:41
loke
there is a case to be made for the simple implementation in the case of lines, since it's much faster. But that's an optimisation.
5:32:38
beach
Then we really really need to define what the general case is. Can I draw a translucent polyline that intersects itself and expect the intersection to be less translucent?>
5:34:38
ck_
the reduction in translucency would be the result of drawing the triangles on top of each other
5:34:52
beach
How does the output of the triangulation algorithm look so that there is a hint that the intersection is apparent?
5:38:56
ck_
triangulation algorithms in general don't do that, you're right. We'd still run into special case handling for a chain of line segments
5:40:25
beach
As I recall, neither Xrender nor GL does the triangulation. It is assumed that you already have triangles.
5:41:34
ck_
by "special case for a chain of line segments" I meant subpolygons subdivided with respect to the mitering (is this the correct term?) and so on
5:42:06
ck_
I don't see a different solution for the problem of translucency which I hadn't thought about before, thank you for bringing it up
6:04:33
beach
I accidentally entered some comments in the #clasp channel. Can you look there, or should I retype them here?
6:09:53
ck_
I don't think there should be only a triangular hole with :NONE as joints, because the segments would be connected at their endpoints -- which is the middle of the stroke, right? not the corner
6:17:04
ck_
you're right. I was somehow picturing different widths for the two segments, with an overhang at the other side
6:20:09
beach
I am thinking two things: 1. Since the CLIM specification says that this stuff is optional, we should feel free to do it right. 2. For each case (line style, polyline, polygon, filled, not filled) we should decide on a shape defined by paths (possibly Bezier splines) that defines the "meaning" of that case.
6:20:17
ck_
loke: if I whip up a naive triangulator for those cl-vector polygons, can you try it out sometime? Just for fun
6:23:49
beach
Like in the case of :NONE, is the overlap drawn less translucent if the ink is translucent?
6:25:20
ck_
from the perspective of a user, let's say an artist, who wants to put some art on the screen: I don't think so
6:26:40
ck_
but no, I don't think so. Maybe there is some more ink on the parts of a stroke with a fountain pen where you stay longer, but that _definitely_ shouldn't be in the shape of parts of overlapping polygonal geometry
6:27:53
ck_
so, if you want to draw overlapping parts, use separate strokes -- that produces separate triangulations which will then blend inside the rendering framework
6:37:07
beach
I am not going to argue with you or agree with you, because I don't have a preference. My point is just that all this has to be decided.
6:41:24
beach
Though, I maintain that, for each case, we should decide what shape(s) the case corresponds to. Then we can generate that shape, triangulate it, and then render it.
6:49:02
beach
I mean, if we take loke's example, there should be semicircle -- straight line -- whatever join curve -- straight line -- semicircle -- straight line -- straight line -- back to start.
6:54:23
beach
I have no strong preference, other than that it is probably best to make a decision so that everyone knows what is being worked on.
6:54:31
ck_
like I said, I'll write some demo code for that when I get around to it, then we can decide
6:58:52
ck_
Not that it's required for a decision of course, don't get me wrong ;) but right now I have to go do something else.
7:36:37
loke
ck_: yes of course. I have the overall infrastructure implemented already, and it should be a simple thing to plug it in
7:43:05
ck_
loke: okay I'll get back to you with that then. Probably your tomorrow though, at the earliest
12:45:15
jackdaniel
(branch in which I'll try to make backends work without any notion of frame, requires only few changes)
12:46:13
jackdaniel
as far as I can see in various "Liberation Front" names, the subject being liberated goes first
12:54:28
ck_
I think I did everything you asked (except for the case/cond thing) in #792 but one of the commit comments does not show as outdated even though it is -- I don't understand
12:54:52
ck_
maybe github is too advanced for me and I should go back to mailing lists and patch files
13:01:49
jackdaniel
yes, I was about to say that (but I've decided on the liberation front joke), that I have a feeling that we are gaining mass
13:54:54
ck_
I had hoped for something a little over the top, you know, with the python humor still reverberating in the background
13:55:29
ck_
Yes people -- with progress like this, I think that sometime in the year two-thousand... we'll be able to totally reduce the list of issues to maybe one or two .. pages
13:55:55
ck_
especially with commits like the other day, from that guy, with all the parentheses in it.. that was awesome
13:58:17
jackdaniel
over the top you say? with our speedup we'll reach the level of technology from 1988 in about 5y \o/