freenode/#clim - IRC Chatlog
Search
3:07:52
loke
http://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/time%20algorithm%20for%20triangulating.pdf
3:11:55
loke
Using the sweep-line method is simpler, but I still would like to see someone's code that implements it: https://en.wikipedia.org/wiki/Polygon_triangulation#Triangulating_a_Non-Monotone_Polygon
3:16:59
beach
There are several of them, and they have different properties, in particular for floating-point precision.
3:19:58
beach
I designed an algorithm for splitting a polygon into trapezoids with integer boundaries.
3:21:06
loke
beach: The implementation used by the fb backend returns a concave polygon that can be self-intersecting. I need to convert that to triangles, because that's what Xrender wants.
3:24:57
beach
Well, my algorithm was designed form a framebuffer backend, so it won't do in this case.
3:25:43
loke
Yeah. I'd like to use th eone in the first link, but it feels like a nightmare trying to implement it.
3:26:18
beach
Must algorithms in computational geometry are. There are just so many cases to consider.
3:26:38
beach
And then, you are never sure that all the cases have been covered, or properly tested for.
3:27:26
beach
So they often get the complexity wrong, because they fail to design the proper data structure.
3:28:43
beach
I can't tell you the number of times I had to debug the algorithms designed by my fellow PhD students.
3:31:17
beach
In fact, there was an article a few years back, encouraging the CG people to use rational arithmetic.
3:32:18
beach
So unless you are an expert in numerical methods and loss of precision, that might be your best solution.
3:38:45
beach
But yes, they haven't learned, because they still work as of Common Lisp doesn't exist.
3:39:27
beach
Still, my message is that I strongly encourage you to use rational arithmetic for those algorithms.
3:47:36
loke
beach: Well, that's half the problem. The other is that cl-vectors returns self-intersecting polygons
3:54:09
beach
3.2.2 If the boundary of a polygon intersects itself, the odd-even winding-rule defines the polygon: a point is inside the polygon if a ray from the point to infinity crosses the boundary an odd number of times.
3:58:59
loke
It works for what it's used for: Which is rasterising. But I agree. It's very much not ideal.
3:59:01
beach
And if you convert it according to the CLIM rule, you will have a hole in your figure.
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