freenode/#clim - IRC Chatlog
Search
17:25:48
pouar
ping jackdaniel I kinda missed the live stream, but if you do implement theming, can you make sure it is not limited to just Material Design, as I kinda find flat themes ugly
17:39:18
jackdaniel
pouar: thanks. theming is a matter of implementing a frame manager which /does the thing/, so adding material design won't limit other possibilities (it won't make them easier neither, maybe except that there will be an example of how to do that)
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.