freenode/#clim - IRC Chatlog
Search
18:23:18
ck_
jackdaniel: could you link me to your winding number test please? We will probably want that for polygon simplification
19:28:43
ck_
the url in the comment to region-c-p-p mentions a speedup figure I just read in that book it referenced ;)
19:36:55
jackdaniel
I saw this photo and I've found it very funny, there is nothing deep in this remark really https://proxy.duckduckgo.com/iu/?u=https%3A%2F%2Ftse3.mm.bing.net%2Fth%3Fid%3DOIP.fM_mB_WnSYBssfbec_ZCcQHaIw%26pid%3DApi&f=1
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