Screenshot instructions:
Windows
Mac
Red Hat Linux
Ubuntu
Click URL instructions:
Rightclick on ad, choose "Copy Link", then paste here →
(This may not be possible with some types of ads)
From: <pierloic@fr...>  20050531 15:50:03

Thanks for your contributions. I think i did progress a bit since the initial post as i managed to list = two main pathological cases and i *feel* like i have a solution for the first= one :). I still cant find anything for the second case and that is the bad news..= . I did a page to explain where i am, you might have a look if you whish : http://pierloic.free.fr/clip/clip.html I dont have precision problems for the moment. I simply use fabs(ab)<eps= ilon. That's allright for now and i dont get equality test problems. It may bec= ome an issue later... I do some strong states check with asserts. Mainly on even count of intersections and the alternates but that is after the graph is built. So: 1) If anyone can think of something about those cases, that's *cool* !!! 2) Reading your posts, it sounds like i should give up with this... Is there any other algorithm for the same specifications:  concave with holes polygon clipped with concave with holes polygon  the algorithm outputs 2 lists: inside polygons and outside polygons  ability to use results as inputs for several passes Thanks  Pierre Loic 
From: Bretton Wade <brettonw@mi...>  20050531 08:45:12

(Despite my experience in this area, I continue to believe that object space algorithms like this can be made to work. It's my masochistic tendencies showing through.) As a general rule, clipping algorithms on complex geometry are not robust and accurate with floating point math.=20 In any large enough data set, you will find at least one unexpected special case that you must solve. The last two assertions you claim to have trouble with (types of intersections will alternate and the number will always be even) are implications of the Jordan curve theorem (Any continuous simple closed curve in the plane separates the plane into two disjoint regions: the inside and the outside.) You have to make these work in order to be sure the clipper is correct. If this is for offline processing, use arbitrary precision arithmetic to eliminate a major source of accuracy errors. It will be slow, but the alternative is manually examining thousands of failure cases. BSP based clipping is no better than the WeilerAtherton algorithm in the long run; it's just easier to code the operations. Unfortunately it will also give you more polygons, meaning more opportunities for error. I implemented the Sutherland and Hodgman algorithm a few years back for offline processing of water polygons in Flight Simulator. Polys with holes were clipped only to quads, and I had a @$%$ of a time getting that robust across the entire world.=20 Here are a few suggestions: 1) Be careful about testing for equality. This comes up in the collocation and collinear testing a lot. Epsilon testing is a generally accepted method for comparison of floats [abs(ab)<epsilon], but breaks down if epsilon is meaningless in the range of numbers you are working in. A better test is looking for least significant bits of deviation (typecast the floats to ints, and compare the result to less than some small enough integer tolerance). 2) Error check your input religiously. You want polygon chains that are simple, have no collinear or collocated vertices, have area greater than 0, etc., etc. Do all this conditioning before you feed the clipper, not while you feed it. Punt on any polygon that isn't well conditioned. 3) Skip the alternative winding order hole polygon approach if you can. I inserted the hole polygon into the source polygons and updated the test for simpleness to allow collinear edges in the polygon. This removes one major source of complexity from the algorithm. 4) Isolate your intersection routines so that they always order line segments the same way. This ensures that you get the same intersection point whether you are considering AB intersects CD, or CD intersects AB (or DC intersects BA...) 5) To make the Jordan curve theorem hold, I found that I had to sort the intersections along the clipping plane and fudge it if I got multiple intersection points that appeared to be collocated. Basically the sort routine had to enforce the alternating nature of the intersection points. If you keep going down this road... Good luck and please report back on your results. Original Message From: gdalgorithmslistadmin@... [mailto:gdalgorithmslistadmin@...] On Behalf Of Andrew Willmott Sent: Monday, May 30, 2005 12:51 PM To: gdalgorithmslist@... Subject: Re: [Algorithms] Weiler Atherton Implementation (2D polygon clipping) The short version: WA is not a practical, robust algorithm. This is not=20 a problem you can solve. The long version: a friend of mine was working on 2D clipping algorithms for his Master's thesis. He ran into exactly the same problems you=20 describe, and spent a lot of time trying to fix them. He eventually got=20 in touch with one of the paper authors, and established that their code=20 had the same set of problems. It was a nice algorithm in theory, but it=20 inevitably ran into robustness issues in practice. He went on to write=20 his own, which was based off a BSP tree approach, I think. (I might be=20 wrong about that  this was all over ten years ago, and I can't find=20 his thesis online. It was "Objectprecision methods for visible surface=20 determination", J. Williams, University of Auckland..) Andrew pierloic@... wrote: >Hello, > >I am implementing the Weiler Atherton algorithm as it really matches my needs >for some physic dev: > concave with holes polygon clipped with concave with holes polygon > the algorithm outputs 2 lists: inside polygons and outside polygons > ability to use results as inputs for several passes > >You can find the original article here : >http://www.cs.drexel.edu/~david/Classes/CS430/HWs/p214weiler.pdf > > >The general cases works really good but it is getting harder with the >pathological cases when some intersections points happens to be the same as >some polygon points: > 2 non parallel edges intersect on one end of one edge > 2 non parallel edges intersect on one end of one edge which is also an end of >the other edge > 2 parallel edges intersect on two points which are end of edges > >I tried different ways to treat them (insert intersection nodes or not) but >nothing really works for the moment. > >The paper is quite "vague" about it : >"If care is taken in placement of intersections where the subject and clip >polygon contours are identical in the xy plane, no degenerate polygons will be >produced by the clipping process" > >Then the text makes two assertions : >"These two types of intersections will be found to alternate along any given >contour and the number of intersections will always be even" > >I cant satisfy these two assertions with the different approaches i tried for >the pathological cases... > >Anyone has experimented these issues ? Any help is welcome. > >Thanks, > >Pierre Loic Herve > > > >SF.Net email is sponsored by: GoToMeeting  the easiest way to collaborate >online with coworkers and clients while avoiding the high cost of travel and >communications. There is no equipment to buy and you can meet as often as >you want. Try it free.http://ads.osdn.com/?ad_idt02&alloc_id=16135&op=3Dclick >_______________________________________________ >GDAlgorithmslist mailing list >GDAlgorithmslist@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_ida88 > =20 >  This SF.Net email is sponsored by Yahoo. Introducing Yahoo! Search Developer Network  Create apps using Yahoo! Search APIs Find out how you can build Yahoo! directly into your own Applications  visit http://developer.yahoo.net/?fr=3Doffadysdnostgq22005 _______________________________________________ GDAlgorithmslist mailing list GDAlgorithmslist@... https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188 
From: Willem de Boer <wdeboer@pl...>  20050531 09:34:59

I recently had to implement a polygon scene clipper algorithm. I used a beamtree to speed up poly clipping, and a BSP tree to feed the beamtree a fronttoback ordered list of polygons. My findings were that you _do not_ want to convert to triangles during your beamtree and BSP tree constructions, as this will i) result in an exponential increase of tree nodes and ii) will entice a lot of roundingerror creepiness. Bretton Wade wrote: "As a general rule, clipping algorithms on complex=20 geometry are not robust and accurate with floating=20 point math. " I can also confirm this. Cheers, Willem 
From: Gino van den Bergen <gvandenbergen@pl...>  20050531 10:03:42

=20 > Original Message > From: gdalgorithmslistadmin@...=20 > [mailto:gdalgorithmslistadmin@...] On=20 > Behalf Of Bretton Wade > Sent: Tuesday, May 31, 2005 10:45 AM > To: gdalgorithmslist@... > Subject: RE: [Algorithms] Weiler Atherton Implementation (2D=20 > polygon clipping) >=20 <snip> >=20 > 1) Be careful about testing for equality. This comes up in=20 > the collocation and collinear testing a lot. Epsilon testing=20 > is a generally accepted method for comparison of floats=20 > [abs(ab)<epsilon], but breaks down if epsilon is meaningless=20 > in the range of numbers you are working in. A better test is=20 > looking for least significant bits of deviation (typecast the=20 > floats to ints, and compare the result to less than some=20 > small enough integer tolerance). >=20 I would like to add that you should try to relate your epsilon to the actual input data. For instance, my (hyper)plane object maintains a noise value that is used to determine whether a point lies on the plane. Given a normal, an offset, and a noise value, a point p lies on the plane if dot(normal, p)  offset <=3D noise. The noise value is not an absolute epsilon. Rather, it is computed from the vertices that are known to lie on the plane. Computed normals are usually not perfectly orthogonal to the support plane of a polygon. Therefore, for these vertices, the signed distance dot(normal, p)  offset will not be exactly zero. The noise value is the maximum absolute signed distance of a vertex that is known to lie on the plane. Furthermore, I add an epsilon to this noise value that is related to the offset in order to catch rounding errors. This espilon is taken to be offset * std::numeric_limits<float>::epsilon() * C, where C is a small positive constant (e.g. 10). In this way, planes that are further away from the origin will have a larger noise value. You should be careful comparing floats by casting them to integers. You would like the float values 1.0 * 2^exp and 1.11111111111111111111111 * 2^(exp1) (in base2 representation) to be classified as equal. However, a direct cast to integer (through *reinterpret_cast<int*>(&value)) will show different values after masking away the least significant bits. It is better to get rid of the N least significant bits by adding a bias value that is 1.0 * 2^(exp + N) (2^N times the absolute maximum of the two) to both values and compare their 32bit float values. For N =3D 8, adding the bias results in 1.00000001000000000000000 * 2^(exp + N) for both values after rounding. (In order to make sure that you're testing only 32 bits and not the 80bit internal representation you could cast them to integers using the pointer cast, or use the floatconsistency compiler option Op.)=20 Gino 
From: <pierloic@fr...>  20050531 15:50:03

Thanks for your contributions. I think i did progress a bit since the initial post as i managed to list = two main pathological cases and i *feel* like i have a solution for the first= one :). I still cant find anything for the second case and that is the bad news..= . I did a page to explain where i am, you might have a look if you whish : http://pierloic.free.fr/clip/clip.html I dont have precision problems for the moment. I simply use fabs(ab)<eps= ilon. That's allright for now and i dont get equality test problems. It may bec= ome an issue later... I do some strong states check with asserts. Mainly on even count of intersections and the alternates but that is after the graph is built. So: 1) If anyone can think of something about those cases, that's *cool* !!! 2) Reading your posts, it sounds like i should give up with this... Is there any other algorithm for the same specifications:  concave with holes polygon clipped with concave with holes polygon  the algorithm outputs 2 lists: inside polygons and outside polygons  ability to use results as inputs for several passes Thanks  Pierre Loic 
From: Willem de Boer <wdeboer@pl...>  20050601 06:52:50

"Is there any other algorithm for the same specifications:" A modified polygon beamtree with a BSP tree for fronttoback ordering of polygons would do. I say modified because you want to keep the polygons that are fully clipped by the beamtree, whereas with the original beamtree algorithm you'd throw those away.  Willem H. de Boer Homepage: http://www.whdeboer.com=20 > Original Message > From: gdalgorithmslistadmin@...=20 > [mailto:gdalgorithmslistadmin@...] On=20 > Behalf Of pierloic@... > Sent: Tuesday, May 31, 2005 5:48 PM > To: gdalgorithmslist@... > Subject: RE: [Algorithms] Weiler Atherton Implementation (2D=20 > polygon clipping) >=20 > Thanks for your contributions. >=20 > I think i did progress a bit since the initial post as i=20 > managed to list two main pathological cases and i *feel* like=20 > i have a solution for the first one :). > I still cant find anything for the second case and that is=20 > the bad news... >=20 > I did a page to explain where i am, you might have a look if=20 > you whish : > http://pierloic.free.fr/clip/clip.html >=20 >=20 > I dont have precision problems for the moment. I simply use=20 > fabs(ab)<epsilon. > That's allright for now and i dont get equality test=20 > problems. It may become an issue later... >=20 > I do some strong states check with asserts. Mainly on even=20 > count of intersections and the alternates but that is after=20 > the graph is built. >=20 >=20 > So: >=20 > 1) If anyone can think of something about those cases, that's=20 > *cool* !!! >=20 > 2) Reading your posts, it sounds like i should give up with this... > Is there any other algorithm for the same specifications: >  concave with holes polygon clipped with concave with holes polygon >  the algorithm outputs 2 lists: inside polygons and outside polygons >  ability to use results as inputs for several passes >=20 > Thanks >  > Pierre Loic >=20 >=20 >=20 >=20 >  > This SF.Net email is sponsored by Yahoo. > Introducing Yahoo! Search Developer Network  Create apps using Yahoo! > Search APIs Find out how you can build Yahoo! directly into=20 > your own Applications  visit=20 > http://developer.yahoo.net/?fr=3Dfadysdnostgq22005 > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 >=20 
From: Sam Martin <sammartin@ho...>  20050601 09:18:36

Hi, I've also yet to see a float implementation of an algorithm that involves line segment intersection that won't fail given sufficiently challenging data. There are a few things I can suggest: Try your best to ignore it if it's offline. The alternatives are all pretty nasty. Try the brain dead approach of tweaking your epsilons and even adding noise until you can get it to converge. If it works it'll save you a lot of effort. I haven't had much luck with arbitrary arithmetic purely because I haven't seen a scheme that's efficient enough to use all the time. I may not be the best authority on this, but I've found it to be something of an all or nothing approach. If you intend to take the result of an arbitrary arithmeticclipped shape and cast it back to regular floats you can still suffer from topological changes, face collapses, intersecting edges, etc. If anyone knows any way round this I'd be very interested to hear about it. I have used the GPC library for clipping and csg operations before (http://www.cs.man.ac.uk/aig/staff/alan/software/). However, it's another float implementation and therefore also suffers from numerical precision problems. The upside is it doesn't fail very often and it's fairly easy to hack so it doesn't crash when it fails and still returns something half sensible. That may sound like a tremendous copout but it's at least a usable solution! However, if you really need something that is rock solid under any configuration and efficient enough to use at runtime I can suggest you look up snap rounding: i.e. http://citeseer.csail.mit.edu/guibas95rounding.html. It's purely a solution for calculating line segment intersections, but it does so completely robustly and I feel there's some scope in adapting this work into more complex algorithms. For my purposes I managed to marry snap rounding with constrained delaunay triangulations (similar in style to: http://ligwww.epfl.ch/Publications/pdf/Kallmann_and_al_Geometric_Modeling_03.pdf). The result is entirely robust and not a mile away from a general clipping or csg implementation, but it wasn't a light undertaking by any means. Hope that helps! Regards, Sam >Message: 5 >Date: Tue, 31 May 2005 17:47:56 +0200 >From: pierloic@... >To: gdalgorithmslist@... >Subject: RE: [Algorithms] Weiler Atherton Implementation (2D polygon >clipping) >ReplyTo: gdalgorithmslist@... > >Thanks for your contributions. > >I think i did progress a bit since the initial post as i managed to list = >two >main pathological cases and i *feel* like i have a solution for the first= > one >:). >I still cant find anything for the second case and that is the bad news..= >. > >I did a page to explain where i am, you might have a look if you whish : >http://pierloic.free.fr/clip/clip.html > > >I dont have precision problems for the moment. I simply use fabs(ab)<eps= >ilon. >That's allright for now and i dont get equality test problems. It may bec= >ome an >issue later... > >I do some strong states check with asserts. Mainly on even count of >intersections and the alternates but that is after the graph is built. > > >So: > >1) If anyone can think of something about those cases, that's *cool* !!! > >2) Reading your posts, it sounds like i should give up with this... >Is there any other algorithm for the same specifications: > concave with holes polygon clipped with concave with holes polygon > the algorithm outputs 2 lists: inside polygons and outside polygons > ability to use results as inputs for several passes > >Thanks > >Pierre Loic > > > > > >____ > >_______________________________________________ >GDAlgorithmslist mailing list >GDAlgorithmslist@... >https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > > >End of GDAlgorithmslist Digest 
From: Gino van den Bergen <gvandenbergen@pl...>  20050601 09:21:37

I'm using the BSP tree approach, so I'm clipping convex polygons against (hyper)planes, which is easier than your case. However, in my case it helped to treat edges (actually halfedges) as halfopen. That is, the edge connecting points p and q is the set { (1  t) * p + t * q : 0 < t <=3D 1 }. A single iteration of the clipper does something like this=20 =20 if (bottomSign * topSign <=3D 0 && bottomSign !=3D 0)=20 { if (topSign =3D=3D 0) { // Degenerate case: top vertex lies on the plane if (bottomSign * topSignOfNextVertex < 0) { // Add top vertex =20 } } else { // Edge intersects at interior. Add intersection point. =09 } } In this way, there is only one degenerate case, and I always end up with zero or two intersection points. NB: This only works for convex polygons. Using finiteprecision numbers, a polygon having more than three vertices has a very slim chance of being absolutely convex. (Each internal edge has a slight crease.) In order to deal with this issue, my planes are fattened by a noise factor, so a sign of zero actually means distance(point, plane) <=3D = plane.noise. =20 > Original Message > From: gdalgorithmslistadmin@...=20 > [mailto:gdalgorithmslistadmin@...] On=20 > Behalf Of pierloic@... > Sent: Tuesday, May 31, 2005 5:48 PM > To: gdalgorithmslist@... > Subject: RE: [Algorithms] Weiler Atherton Implementation (2D=20 > polygon clipping) >=20 > Thanks for your contributions. >=20 > I think i did progress a bit since the initial post as i=20 > managed to list two main pathological cases and i *feel* like=20 > i have a solution for the first one :). > I still cant find anything for the second case and that is=20 > the bad news... >=20 > I did a page to explain where i am, you might have a look if=20 > you whish : > http://pierloic.free.fr/clip/clip.html >=20 >=20 > I dont have precision problems for the moment. I simply use=20 > fabs(ab)<epsilon. > That's allright for now and i dont get equality test=20 > problems. It may become an issue later... >=20 > I do some strong states check with asserts. Mainly on even=20 > count of intersections and the alternates but that is after=20 > the graph is built. >=20 >=20 > So: >=20 > 1) If anyone can think of something about those cases, that's=20 > *cool* !!! >=20 > 2) Reading your posts, it sounds like i should give up with this... > Is there any other algorithm for the same specifications: >  concave with holes polygon clipped with concave with holes polygon >  the algorithm outputs 2 lists: inside polygons and outside polygons >  ability to use results as inputs for several passes >=20 > Thanks >  > Pierre Loic >=20 >=20 >=20 >=20 >  > This SF.Net email is sponsored by Yahoo. > Introducing Yahoo! Search Developer Network  Create apps using Yahoo! > Search APIs Find out how you can build Yahoo! directly into=20 > your own Applications  visit=20 > http://developer.yahoo.net/?fr=3Dfadysdnostgq22005 > _______________________________________________ > GDAlgorithmslist mailing list > GDAlgorithmslist@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_ida88 >=20 
From: <pierloic@fr...>  20050613 08:11:54

Hi again, I must say I stoped to play with this because I dont have so much time an= d i have to go further in the app ! But the experience was not bad and I think I did a little step forward. I= n a previous post I explained that i was hurting myself with two pathological cases. I have found a way to handle theses cases. (I updated the web page= if interested http://pierloic.free.fr/). So I have now an implementation tha= t handle all cases of subject/clipping poly... unless someone finds a desig= n bug... And now guess what ? I have some precisions problems (when I classify entering/leaving intersections for example) I suspect there will be lots of them and I suspect it is not easy... so I= leave it here for the moment... I have the ability to use a 3D modelling package with boolean operators s= o I will use this as a replacement. This makes me thing of that :  They seem to make some intersections graph for 3D boolean op like in WA clipping and it works. I begin to think that it should be doable to get a reliable and robust code for 2D WA clipping.  To solve the problem of finding a good algo for WA, the better is to ha= ve some serious background on boolean techniques which is not my case... some answers: > Is HodgmanSutherland clipping not satisfying you requirements ? I need the inside and outside polygon lists. HS clipping will just give y= ou the inside polygons (the clipped ones) if I understood correctly. > Did you consider the LiamBarsky algorithm also? Dont know about that one but I feel like I have to stick to an intersecti= on graph if I want inside and outside polys as results. > Are you familiar with "topological sorting" ? No I am not. But what's the difference between the unique IDs and node in= stances in a graph ? More or less the same , no ? It seems that you use them later in the process (on some 3D geometry)... = I am just doing 2D clipping !!! Thanks  Pierre Loic Herve 
Sign up for the SourceForge newsletter:
No, thanks