tag:blogger.com,1999:blog-1272803659321539598.post8098607810045086847..comments2023-12-01T20:38:27.999-08:00Comments on Digesting Duck: Computational Geometry Sucks!Mikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-1272803659321539598.post-79201432354429134982021-06-16T19:39:25.505-07:002021-06-16T19:39:25.505-07:00google 1089
google 1090
google 1091
google 1092
go...<a href="https://funsilo.date/wiki/Want_To_Enjoy_Football_Sound_Advice_To_Help_You_Get_Started" rel="nofollow">google 1089</a><br /><a href="http://aarth-codex.com/index.php?title=Enjoy_Soccer_Like_A_Expert__Methods_To_Increase_Your_Activity" rel="nofollow">google 1090</a><br /><a href="http://plantdatabases.org/resources/wiki/index.php?title=Wish_To_Play_Football_Superb_Advice_To_Help_You_Started_off" rel="nofollow">google 1091</a><br /><a href="http://wiki.psxdigital.com/index.php?title=Wish_To_Enjoy_Soccer_Sound_Advice_To_Help_You_Started_off" rel="nofollow">google 1092</a><br /><a href="http://blakesector.scumvv.ca/index.php?title=Enjoy_Football_Such_As_A_Master__Techniques_To_Up_Your_Online_game" rel="nofollow">google 1093</a><br /><a href="https://backforgood.faith/wiki/Would_Like_To_Engage_in_Soccer_Great_Tips_To_Get_You_Started_out" rel="nofollow">google 1094</a><br /><a href="https://italentos.win/wiki/Enjoy_Soccer_Like_A_Expert_Methods_To_The_Game" rel="nofollow">google 1095</a>adminhttps://www.blogger.com/profile/13328975220076167046noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-7189718454962413142012-06-16T10:27:13.910-07:002012-06-16T10:27:13.910-07:00@Pavel - It took me ages to figure this out! Your ...@Pavel - It took me ages to figure this out! Your points A, B, C and E are all exactly on a straight line, so your first onPlane test is not meaningful. The 'modern hardware' and precision issues raised in the Shewchuck paper are really not a problem on x86 or x64 processors, as long as the FPU precision is not changed from the 64-bit (53-bit significand) default. I'll have a carefully checked .NET port of the Shewchuck predicates posted soon - look for it on github: https://github.com/govert/RobustGeometry.NET.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-54743991309836151702011-09-16T05:51:55.127-07:002011-09-16T05:51:55.127-07:00Shewchuk predicates are not completely stable, at ...Shewchuk predicates are not completely stable, at least I wasn't able to make it stable on new HW:<br /><br />double pointA[3] = {0.12539999f, 0.0016452915f, -0.019413333f};<br /> double pointB[3] = {0.12539999f, 0.0017933375f, -0.019214222f};<br /> double pointC[3] = {0.12539999f, 0.0017933375f, -0.017919999f};<br /> double pointD[3] = {0.11700000f, 0.0017933375f, -0.018710587f};<br /> double pointE[3] = {0.12539999f, 0.0017933375f, -0.019413333f};<br /><br /> std::cout << "On plane: A, C, B, E: " << onPlane(pointA, pointC, pointB, pointE) << std::endl;<br /> std::cout << "On plane: B, C, D, E: " << onPlane(pointB, pointC, pointD, pointE) << std::endl;<br /> std::cout << "On plane: B, C, D, A: " << onPlane(pointB, pointC, pointD, pointA) << std::endl; <br /><br />This three tests ultimately fail telling you that first 2 tests are true and the last one is false, which is logically impossible and therefore predicates are not working correctly on modern HW at least.Pavel Celbahttps://www.blogger.com/profile/05198646264582371431noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-14994488869175071352011-03-25T06:22:36.950-07:002011-03-25T06:22:36.950-07:00Needs a 100% public domain C version! Sadly, can&#...Needs a 100% public domain C version! Sadly, can't get there from here (if I tried to paraphrase the Bullet one, then it wouldn't be legimitate to public domainify it; and I don't have the time/energy/interest to figure it out from scratch).Sean Barretthttps://www.blogger.com/profile/14465498859800664552noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-57494555000479371222011-03-22T06:35:44.169-07:002011-03-22T06:35:44.169-07:00Unlike CGAL, the Bullet library keeps dependencies...Unlike CGAL, the Bullet library keeps dependencies low, this snippet depends only on a handful of files. Distibuting such gems as snippet/standalone is a good idea.Erwinhttps://www.blogger.com/profile/09056479728093157309noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-33561290054533436492011-03-22T00:23:44.579-07:002011-03-22T00:23:44.579-07:00Erwin, great! I'd like to make a simple standa...Erwin, great! I'd like to make a simple standalone library from the code, but I have been swamped with my other projects.Mikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-79010508937320093902011-03-21T17:58:41.839-07:002011-03-21T17:58:41.839-07:00Finally added this convex hull computation to the ...Finally added this convex hull computation to the Bullet library:<br /><br />http://code.google.com/p/bullet/source/browse/trunk/src/LinearMath/btConvexHullComputer.cpp<br /><br />The implementation has been tested in production, and is part of MAXON Cinema4D package.Erwinhttps://www.blogger.com/profile/09056479728093157309noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-89244773562783933172011-01-27T12:25:47.539-08:002011-01-27T12:25:47.539-08:00Let me recommend CGAL as the go-to library for com...Let me recommend CGAL as the go-to library for computational geometry. It's pretty heavyweight to get started, but well worth the effort. There might be licensing issues for you, check to make sure before you get carried away.<br /><br />For doing geometric tests ("are these four points coplanar?") you might be interested in Shewchuk's robust geometric predicates -- Google "shewchuk predicates.c" If you're not interested, either you've thought extremely carefully and you have formal proofs that it's OK to be inexact, or you're writing bugs. You've already hit this fact with the tesselated cube.<br /><br />Shewchuk's approach is pretty fast: compared to using doubles, it's a factor of two for the incircle test, and about 20% overall for a 2d Delaunay triangulation algorithm. You could also use an exact arithmetic package like GMP but then you lose an order of magnitude overall.<br /><br />This makes is so that all your tests are exact; no more issues there! But of course when you do a construction ("add a point on the plane defined by these three points") it's still a tough life we live, with these computers that can't handle real numbers. When constructions are involved, you're stuck either praying or doing higher math.<br /><br />For books, de Berg et al ("Computational Geometry") is great for 2d geometry. I don't have a great text to recommend for 3d.<br /><br />Cheers!Benoithttps://www.blogger.com/profile/04713089900964656656noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-84229577040805871142010-12-11T00:58:53.514-08:002010-12-11T00:58:53.514-08:00You're probably referring to the incremental a...You're probably referring to the incremental algorithm. It is simple to implement, but does not handle coplanar faces well (i.e. That tesselated cube i mentioned).Mikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-34224440609484585332010-12-10T13:36:30.912-08:002010-12-10T13:36:30.912-08:00Been five years since I studied computational geom...Been five years since I studied computational geometry, but if I remember, there were some very simple, elegant, fast randomized algorithms which sacrificed absolute complexity for expected complexity (i.e., runtime is O(n^4) but *expected* runtime depending on random processes is O(n log n)). Don't remember how robust they were w/r/t non-general position.Glowing Face Manhttps://www.blogger.com/profile/07717328290680086281noreply@blogger.com