Re: [Flightgear-devel] HEADS UP: Scenery regeneration
-BEGIN PGP SIGNED MESSAGE- Hash: SHA256 Hi Ralf, Ralf Gerlich schrieb: [...] The actual problem lies within TriangleJRS, the triangulation code of TerraGear, [...] Fixing TriangleJRS was not possible for me as I am clearly not a computational geometry man. if the triangulation code causes trouble, you could try CGAL (http://www.cgal.org/). They have very robust and well designed computational geometry codes. If you are using the triangulation not with a normal kernel (that uses e.g. double) but with an filtered kernel (or even an exact one...) you'll get reliable results that a guaranteed to be stable. CU, Christian -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.6 (GNU/Linux) iD8DBQFInWRPoWM1JLkHou0RCAJ5AJkBtpSXmdN8PTTmmCg/5zB75rJ5RgCcDBKf lq8NPQstVnSIhA+5fZ5//zA= =1hbo -END PGP SIGNATURE- - This SF.Net email is sponsored by the Moblin Your Move Developer's challenge Build the coolest Linux based applications with Moblin SDK win great prizes Grand prize is a trip for two to an Open Source event anywhere in the world http://moblin-contest.org/redirect.php?banner_id=100url=/ ___ Flightgear-devel mailing list Flightgear-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/flightgear-devel
Re: [Flightgear-devel] HEADS UP: Scenery regeneration
Hi Christian! Christian Mayer wrote: if the triangulation code causes trouble, you could try CGAL (http://www.cgal.org/). They have very robust and well designed computational geometry codes. Thank you for the hint. In the meantime I have found out that it is not TriangleJRS that causes the problems, but rather TerraGear itself in that it does some further processing before triangulation but after calculation of the point-in-polygon. I know that CGAL is used by Frederic Bouvier's FlightGear Scenery Designer and maybe using that is an option in case of a TerraGear rewrite ;-) (Note that I do think that the FGSD is a very good thing (TM), we just need something that can do batches of work on a headless machine - such as regenerating World Scenery on some high-performance machine nearly on the other side of the globe ;-) ) Currently, I am working on a fix that involves doing the point-in-polygon calculations _after_ the creation of the vertex and edge lists. This way the points-in-polygon should be consistent with the constrained edges TriangleJRS sees. Cheers, Ralf - This SF.Net email is sponsored by the Moblin Your Move Developer's challenge Build the coolest Linux based applications with Moblin SDK win great prizes Grand prize is a trip for two to an Open Source event anywhere in the world http://moblin-contest.org/redirect.php?banner_id=100url=/ ___ Flightgear-devel mailing list Flightgear-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/flightgear-devel
Re: [Flightgear-devel] HEADS UP: Scenery regeneration
Hi! Ralf Gerlich wrote: While it seems to me that the workaround should work, due to previous experience with TerraGear and its subtleties I would not want to bet on it. ...and I see that I was right not to bet: The workaround doesn't work. TerraGear failed on the first try building the EDDF-area. The actual problem lies within TriangleJRS, the triangulation code of TerraGear, which - as several checks have shown - is not as robust as advertised regarding computational geometry predicates. The point-in-triangle-detection-code does seem to have problems if the respective point is pretty near to the contour of the triangle. While the point is perfectly inside the triangle, TriangleJRS cannot detect that. Nope, that's not it... I have just checked once more and found that triangles for the extremely small triangle parts simply do not exist. They are not generated by TriangleJRS. This could have one of two reasons: 1) TerraGear does some specific edge-splitting when preparing the list of nodes and constrained edges for TriangleJRS. This is sensible, but may move the nodes of the slivers in a co-linear fashion, i.e. the sliver parts completely vanish. 2) TriangleJRS removes the triangles for these parts as it thinks they are too small. After some checking it seems that 1) is the case. I'm at it and I hope to still be able to do a rebuild as announced with a new solution. However, don't count on it. The call for submissions to the static scenery objects database is left as is ;-) Cheers, Ralf - This SF.Net email is sponsored by the Moblin Your Move Developer's challenge Build the coolest Linux based applications with Moblin SDK win great prizes Grand prize is a trip for two to an Open Source event anywhere in the world http://moblin-contest.org/redirect.php?banner_id=100url=/ ___ Flightgear-devel mailing list Flightgear-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/flightgear-devel
Re: [Flightgear-devel] HEADS UP: Scenery regeneration
On Thu, Aug 7, 2008 at 7:08 AM, Ralf Gerlich wrote: I have just checked once more and found that triangles for the extremely small triangle parts simply do not exist. They are not generated by TriangleJRS. Hi Ralf, As far as I know, terragear doesn't do extra edge splitting before handing data to TriangleJRS. However at some point in the pipeline there is a routine that attempts to identify slivers and merge them with neighboring areas. The heuristics for identifying a sliver are pretty loose and weren't designed with high detail, high polygon count scenery in mind. You may want to greatly constrain the area/angle checks, or remove the sliver check entirely. This goes back a long time, but I think the sliver checking was originally an attempt to work around numerical problems when letting TriangleJRS subdivide triangles to get an ideal Delauney triangulation. We've since given up on that because it generates way too many unneeded triangles so the sliver check could probably go away without hurting anything. I don't know if this will help your specific situation, but I don't think it will hurt. Curt. -- Curtis Olson: http://baron.flightgear.org/~curt/ - This SF.Net email is sponsored by the Moblin Your Move Developer's challenge Build the coolest Linux based applications with Moblin SDK win great prizes Grand prize is a trip for two to an Open Source event anywhere in the world http://moblin-contest.org/redirect.php?banner_id=100url=/___ Flightgear-devel mailing list Flightgear-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/flightgear-devel
Re: [Flightgear-devel] HEADS UP: Scenery regeneration
- Curtis Olson a écrit : On Thu, Aug 7, 2008 at 7:08 AM, Ralf Gerlich wrote: I have just checked once more and found that triangles for the extremely small triangle parts simply do not exist. They are not generated by TriangleJRS. Hi Ralf, As far as I know, terragear doesn't do extra edge splitting before handing data to TriangleJRS. However at some point in the pipeline there is a routine that attempts to identify slivers and merge them with neighboring areas. The heuristics for identifying a sliver are pretty loose and weren't designed with high detail, high polygon count scenery in mind. You may want to greatly constrain the area/angle checks, or remove the sliver check entirely. This goes back a long time, but I think the sliver checking was originally an attempt to work around numerical problems when letting TriangleJRS subdivide triangles to get an ideal Delauney triangulation. We've since given up on that because it generates way too many unneeded triangles so the sliver check could probably go away without hurting anything. Hi Curt, Hi Ralf, maybe I don't recall correctly, but I thing long edges are split to avoid having, for example, long road segments cutting mountains or making banks when crossing valleys. -Fred -- Frédéric Bouvier http://my.fotolia.com/frfoto/ Photo gallery - album photo http://fgsd.sourceforge.net/ FlightGear Scenery Designer - This SF.Net email is sponsored by the Moblin Your Move Developer's challenge Build the coolest Linux based applications with Moblin SDK win great prizes Grand prize is a trip for two to an Open Source event anywhere in the world http://moblin-contest.org/redirect.php?banner_id=100url=/ ___ Flightgear-devel mailing list Flightgear-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/flightgear-devel
Re: [Flightgear-devel] HEADS UP: Scenery regeneration
On Thu, Aug 7, 2008 at 9:55 AM, Ralf Gerlich wrote: Sorry to correct you, but in Triangle::build() the segment lists are built using TGTriSegments::unique_divide_and_add(), which does segment splitting if TerraGear thinks that one of the end-nodes lies on an already known edge. These checks seem to be less exact than the predicates used by TriangleJRS ;-) Hi Ralf and Fred, Both of you have helped refresh my memory. :-) Yes, there is code to split long features of polygons so they can more naturally follow the underlying terrain features. A single mile long edge across varying terrain looks extremely ugly whereas splitting this up into 200m or 400m segments allows the feature to more naturally follow the underlying terrain. However, this is on a very large scale so shouldn't cause any numerical accuracy problems. As Ralf points out, there is code that attempts to find stray nodes that lie on existing edges and split the edge at that point. When this situation exists, it can lead to degenerate behavior. As I understand it, the terragear check should be more ambitious than the TriangleJRS check in order to prevent problems down stream. You can tune the thresholds for detection of this situation, but the looser you make the constraints, the more you are likely to alter the original geometry which will create artifacts in the final result. Regards, Curt. -- Curtis Olson: http://baron.flightgear.org/~curt/ - This SF.Net email is sponsored by the Moblin Your Move Developer's challenge Build the coolest Linux based applications with Moblin SDK win great prizes Grand prize is a trip for two to an Open Source event anywhere in the world http://moblin-contest.org/redirect.php?banner_id=100url=/___ Flightgear-devel mailing list Flightgear-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/flightgear-devel
Re: [Flightgear-devel] HEADS UP: Scenery regeneration
Hi! I have uploaded a picture showing the situation in the example of VHHH to http://www.custom-scenery.org/fileadmin/people/rgerlich/vhhh.png This is an export from QGIS, using shapefiles I generate from test printouts of TerraGear. I forgot to color this properly, but actually the textures and colors don't matter. What we have is a blue polygon, which should be of material type IrrCropPastureCover. This lies inside an Ocean polygon, which extends on the east side of the blue polygon in pink. The blue IrrCropPastureCover is also adjacent to a light-blue GrassCover polygon. What you see at the bottom are two circles, representing the point in polygon for these polygons. They have the material type attached to them. In the small cutout on the right side you see that the blue polygon continues in a very slim sliver to the south, the width of which is about 4 to 8 times SG_EPSILON and which becomes more slim towards the south. The calc_point_inside() algorithm I implemented places the inside point perfectly within this sliver, which I have checked by appropriately scaling the part in QGIS. Unfortunately in preparation to the triangulation step, the vertices of the right border of the sliver are merged onto the left border of the sliver, so that the sliver essentially vanishes. Curtis Olson wrote: As Ralf points out, there is code that attempts to find stray nodes that lie on existing edges and split the edge at that point. When this situation exists, it can lead to degenerate behavior. As I understand it, the terragear check should be more ambitious than the TriangleJRS check in order to prevent problems down stream. Not necessarily _more_ ambitious, but at least as exact. As far as I have understood, Jonathan Shewchuk uses what he calls Adaptive Precision Floating-Point Arithmetic for the geometric predicates, so this is quite different from the epsilon-approach. You can tune the thresholds for detection of this situation, but the looser you make the constraints, the more you are likely to alter the original geometry which will create artifacts in the final result. I have tried, but for some reason TriangleJRS then has problems with colinear edges, which is - as far as I understand - exactly the thing which should be avoided by splitting. And it is curious, as it seems to contradict the adaptive precision idea expressed above... In general, what TerraGear is doing currently - eliminiating the slivers - actually is the right thing performance-wise, as we really do not want these slivers to take up valuable triangles in the scenery files. What we might have to change is the point were the point inside polygon is calculate to after the creation of the edge and vertex lists for triangulation. It should be possible to keep the information about the edges belonging to a polygon resp. contour, so that the point-inside-calculation could use these instead of the original polygons. Cheers, Ralf - This SF.Net email is sponsored by the Moblin Your Move Developer's challenge Build the coolest Linux based applications with Moblin SDK win great prizes Grand prize is a trip for two to an Open Source event anywhere in the world http://moblin-contest.org/redirect.php?banner_id=100url=/ ___ Flightgear-devel mailing list Flightgear-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/flightgear-devel
[Flightgear-devel] HEADS UP: Scenery regeneration
Hello again! It seems that I finally have a somewhat dependable workaround for the TerraGear coastline bug reported shortly after the release of the 1.0.0 scenery. I have reviewed the algorithm thoroughly - together with Martin - and checked some of the tiles reported as faulty beginning of this year and they seem to be generated correctly now. Martin and I plan to start a new generation job on the weekend of the 16th/17th of August. We would like to include the current state of the static scenery database with this release. In case anybody has any objects intended for submission but not yet submitted, this is the time to submit them to the database, if you want to have your contributions included in the new scenery. As this scenery is to replace the faulty scenery which was released together with FlightGear v1.0.0, we will have to use the airport database included with that release for consistency reasons. Updates as found in the apt.dat in CVS will therefore unfortunately not be included. (As a sidenote: This is one reason why the apt.dat or at least the parts thereof used for airport generation as well as the AI ground networks should reside with the scenery, not with the base package...) We intend to tag the generated scenery unstable for obvious reasons before making it an official release. While it seems to me that the workaround should work, due to previous experience with TerraGear and its subtleties I would not want to bet on it. As it seems, some mirror providers may not be able to carry the load of two scenery releases - the official one and the unstable version -, so we will not publish the alpha release via the normal distribution channels, where mirrors normally pick it up. Possibly, we will publish a location were interested mirror providers can also pick up the unstable version, and we would appreciate any support from mirror providers in that direction. I am not that much thrilled about the kind of solution I found as it doesn't solve the actual problem but rather enhances a perfectly working part of the code with some special cases. The actual problem lies within TriangleJRS, the triangulation code of TerraGear, which - as several checks have shown - is not as robust as advertised regarding computational geometry predicates. The point-in-triangle-detection-code does seem to have problems if the respective point is pretty near to the contour of the triangle. While the point is perfectly inside the triangle, TriangleJRS cannot detect that. The points are used to mark polygons and their associated triangles with associated attributes, including texture. As TriangleJRS does associate some of the points with adjacent triangles, texture attributes spill out into adjacent polygon areas. This is most noticeable in places where sea/ocean area is transferred into land this way. Fixing TriangleJRS was not possible for me as I am clearly not a computational geometry man. I will try to contact Jonathan R. Shewchuk on this issue, after some further analysis. The triangle package should be based on arbitrary precision predicates, as far as the documentation goes, but maybe I misunderstood what is meant by this ... or the predicates don't actually deliver to this promise. I have modified the algorithm to ensure that the selected points are at least a given distance away from the contours. Unfortunately, the new algorithm is less robust than the old one and might outright deny working on some specific valid, but degenerate polygons. Further, the distance used had to be selected arbitrarily according to the results of the scenery generation, but should be a safe estimate. The new algorithm has the advantage that instead of silently delivering points inside the polygon which TriangleJRS cannot handle, it will either deliver a good point or fail completely, resulting in an abnormal exit of the building process for the respective tile. I would appreciate if anybody wants to review my changes. The current version is available via git from http://mapserver.flightgear.org/git/terragear-cs/ Look into src/Lib/Geometry/poly_support.cxx, function calc_point_inside() (around line 447). Cheers, Ralf - This SF.Net email is sponsored by the Moblin Your Move Developer's challenge Build the coolest Linux based applications with Moblin SDK win great prizes Grand prize is a trip for two to an Open Source event anywhere in the world http://moblin-contest.org/redirect.php?banner_id=100url=/ ___ Flightgear-devel mailing list Flightgear-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/flightgear-devel
