tag:blogger.com,1999:blog-1272803659321539598.post561673051536523114..comments2018-10-09T04:44:33.945-07:00Comments on Digesting Duck: Simple Stupid Funnel AlgorithmMikko Mononenhttp://www.blogger.com/profile/11900996590678707801noreply@blogger.comBlogger57125tag:blogger.com,1999:blog-1272803659321539598.post-56267190498881051872014-09-01T23:25:24.552-07:002014-09-01T23:25:24.552-07:00thanx for this detail
Plastic Manufacturersthanx for this detail<br /><a href="http://www.plasticlabwareindia.com" rel="nofollow">Plastic Manufacturers</a>alina bratehttps://www.blogger.com/profile/04118156962601070996noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-41750356109341253902013-12-25T09:23:59.469-08:002013-12-25T09:23:59.469-08:00The algorithm is quite confusing to try to explain...The algorithm is quite confusing to try to explain in words. I think in the point 3/3 I have mixed left and right, so it probably should read:<br /><br />If the new right end point is over left funnel edge (F), we add the left funnel as a corner in the path and place the apex of the funnel at the left funnel point location and restart the algorithm from there (G). Mikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-57303875888060650472013-12-23T16:46:57.709-08:002013-12-23T16:46:57.709-08:00Which one is the left and right edges? Blue or Ora...Which one is the left and right edges? Blue or Orange?<br /><br />Its really confusing because in the given demo, you first say<br /><br />If the new left endpoint is outside the funnel, the funnel is not update (E-F)<br />(indicating that orange is left)<br /><br />and then you say:<br /><br />If the new left end point is over right funnel edge (F), we add the right funnel as a corner in the path and place the apex of the funnel at the right funnel point location and restart the algorithm from there (G).<br />(indicating blue is left)<br /><br />I've been trying to link the demo with the code for hours but it isn't making sense...lurkingdevilhttps://www.blogger.com/profile/04038191655911717129noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-6250449482984551562012-12-08T08:28:58.456-08:002012-12-08T08:28:58.456-08:00So, I've been working on my own implementation...So, I've been working on my own implementation of the funnel algorithm and I realized what sacrifice you're making with this (as you called it) "simple stupid funnel algorithm". The "sleeve" you've shown in the illustration is clearly taken from the Lee and Preparata paper. However, it works because the funnel's extents get contracted by each successive portal/edge. Your funnel doesn't cut through the center of portals. If it were to, you'd get an unhappy path. It is for these cases that the whole double-ended queue is used. Did you want to comment on that at all?Seanhttps://www.blogger.com/profile/03002139848836152175noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-81328011325517589512012-10-16T10:37:25.712-07:002012-10-16T10:37:25.712-07:00Thank you for the swift reply Mikko. That makes se...Thank you for the swift reply Mikko. That makes sense, I think I was over complicating it. Thanks again for the great write up!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-25129325770205143272012-10-16T09:08:28.838-07:002012-10-16T09:08:28.838-07:00@Cameron, in my code and the pictures above, I cal...@Cameron, in my code and the pictures above, I call the yellow dashed edges portals. If you're polygons are wound counter clockwise, then it should be as simple as using the two consecutive vertices if the current polygon as the portal.<br /><br />For example:<br />if pidx=current polygon, eidx=corrent polygon edges index (that is the edge that leads o the next polygon), then the portal is:<br /><br />p = polygons[pidx];<br />left = vertices[p.verts[eidx];<br />right = vertices[p.verts[(eidx+1)%p.nverts];<br /><br />(I may have left and right mixed up in the code, or the code may actually assume clockwise polygon, I tend to mix these up sometimes).Mikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-23475668211701029262012-10-16T08:38:24.267-07:002012-10-16T08:38:24.267-07:00Hi Mikko, can you suggest an algorithm or referenc...Hi Mikko, can you suggest an algorithm or reference for constructing the portals (or channels as some white papers call them)? I think I'm constructing them mostly correctly but missing a few edge cases. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-46181470664472475952012-06-28T07:29:30.934-07:002012-06-28T07:29:30.934-07:00I did a test using pretty much a copy of your code...I did a test using pretty much a copy of your code. For me, the end point gets added twice to the result path in some cases.<br /><br />More specifically this happens if the left or right vertex of the last actual portal is not part of the result path.<br /><br />Not 100% sure if it's bug in the code or maybe something to do with the input data, but with a quick investigation my input data looked to be sane.Ollikhttps://www.blogger.com/profile/16741605519851315032noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-83873326151382904022012-06-20T11:24:17.721-07:002012-06-20T11:24:17.721-07:00Thanks a lot, Mikko.
As you have suggested, I st...Thanks a lot, Mikko. <br /><br />As you have suggested, I stored polygons in CCW and did some pre-processing including:<br /><br />- calculating adjacent polygons for each polygon<br />- finding the mutual edge between each two polygons<br /><br />Now the program is much faster than triangle-based one. Thank you.<br /><br />Cheers,<br />ShawnXiaohttps://www.blogger.com/profile/01706441295327752242noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-81200606236607176952012-05-30T22:30:24.034-07:002012-05-30T22:30:24.034-07:00You're thinking too complicated. If an edge in...You're thinking too complicated. If an edge in a CCW triangle/polygon is defined as two consecutive vertices, then the first of those vertices is right and second vertex left. No need to calculate anything at all! :)Mikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-85286325278984496802012-05-30T22:22:15.074-07:002012-05-30T22:22:15.074-07:00Yes, you are right. Finding a portal edge between ...Yes, you are right. Finding a portal edge between two adjacent polygons is not a big issue. But we have to determine which point is left and right before we can process the portal.<br /><br />I thought my program spent too much time on determining the left and right points (because each time I have to cycle through the whole polygon so as to determine which is left or right point based on previous left and right points). Do you have better idea?<br /><br />Many thanks,<br />ShawnXiaohttps://www.blogger.com/profile/01706441295327752242noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-61787448029337503342012-05-30T06:39:02.167-07:002012-05-30T06:39:02.167-07:00Finding portal between two polygons should not be ...Finding portal between two polygons should not be a speed issue. Each edge stores an index/reference to neighbour polygon, so it is just few integer compares.<br /><br />One advantage triangles have is that they are really easy to store, as each triangle takes the same amount of memory. Detour stores polygons in similar manner too to keep random access fast (i.e. all polygons have 6 vertices), but in the process you loose some memory. The amount of memory is usually insignificant.Mikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-63732754678886935662012-05-30T06:34:36.271-07:002012-05-30T06:34:36.271-07:00Thanks a lot, Mikko. Your comment is quite helpful...Thanks a lot, Mikko. Your comment is quite helpful. <br /><br />I thought the problem could be how to find the left and right points. In a triangle-based mesh, if we know a point is on one side, the other point is clearly on the opposite side. Cycling through the triangles is much faster than the polygons as we have to decide the left and right points by cycling through all the end-points in the polygon. <br /><br />For example, to determine whether a point on a portal, we have to cycle through the polygon from that point in two directions until finding a previous left or right point or another endpoint of that portal.<br /><br />I thought this process takes more time than it in triangles. Do you have any suggestion to improve it? <br /><br />And do you have any idea why many game engines still choose a tri-mesh based pathfinding? Does it imply that in the context of geometry, generating a triangle-based mesh (splitting a map into a set of triangles) is much easier or faster than generating a polygon-based mesh?<br /><br />Many thanks again.<br /><br />Cheers,<br />ShawnXiaohttps://www.blogger.com/profile/01706441295327752242noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-70134117277070575842012-05-23T11:03:35.402-07:002012-05-23T11:03:35.402-07:00Polygons are indeed usually favored since they res...Polygons are indeed usually favored since they result less A* nodes. That is the reason Detour uses them too. The memory usage is usually similar.<br /><br />What are those dev's reasons for tri meshes being better?<br /><br />What parts of code are slower when you use polygon based methods?Mikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-64464625259486921902012-05-23T10:56:46.437-07:002012-05-23T10:56:46.437-07:00hi Mikko,
some game developers pointed out that n...hi Mikko,<br /><br />some game developers pointed out that n-sided convex polygon mesh is not ideal for pathfinding. They thought tri-mesh is better. but i thought the search can be faster in a poly-based mesh as less nodes are examined when you treat them as A* nodes. what do you think? do you think the poly-based mesh is still worth studying?<br /><br />I just implemented your methods on a polygon-based mesh. Compared with triangle-based mesh, I found the running time even slower. So I am confused now.<br /><br />cheers,<br />Shawnshawnhttps://www.blogger.com/profile/11207078423806439345noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-88035244478744958542012-01-02T06:36:56.711-08:002012-01-02T06:36:56.711-08:00Does anyone know the problem in this case?
http://...Does anyone know the problem in this case?<br />http://www.gamedev.net/topic/617458-doug-demyens-funnel-algorithm/Unknownhttps://www.blogger.com/profile/02156280264897864977noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-76021377521916375852012-01-02T06:35:48.612-08:002012-01-02T06:35:48.612-08:00This comment has been removed by the author.Unknownhttps://www.blogger.com/profile/02156280264897864977noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-49594591555649169192012-01-02T06:35:31.174-08:002012-01-02T06:35:31.174-08:00This comment has been removed by the author.Unknownhttps://www.blogger.com/profile/02156280264897864977noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-467557634281549402011-12-08T19:05:58.180-08:002011-12-08T19:05:58.180-08:00Thanks a lot. What happen if triarea = 0 ?? The po...Thanks a lot. What happen if triarea = 0 ?? The point tested goes through both if conditions?Unknownhttps://www.blogger.com/profile/02156280264897864977noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-90865156647546285862011-11-27T23:28:28.852-08:002011-11-27T23:28:28.852-08:00@Unknown, you don't need to compare angles. Yo...@Unknown, you don't need to compare angles. You just need to check if a point is on a certain side of a segment. This can be done by calculating the winding of a triangle which is formet by the two points of the segment and the third point you want to check. The sign of the triangle area will tell you on which way the triangle is would, that is, on which side of the segment the third point is.Mikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-27717760880695447022011-11-27T12:54:29.588-08:002011-11-27T12:54:29.588-08:00When checking the left portion do we have to compa...When checking the left portion do we have to compare angles counterclockwise?<br />And when it's the right portion is it clockwise?Unknownhttps://www.blogger.com/profile/02156280264897864977noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-19829599555671515652011-10-12T12:21:37.301-07:002011-10-12T12:21:37.301-07:00Maybe, but I'm having a hard time finding anyt...Maybe, but I'm having a hard time finding anything and most of the stuff you write on this site is over my head.chttps://www.blogger.com/profile/16587168742111723848noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-86059493883641699952011-10-12T11:15:33.625-07:002011-10-12T11:15:33.625-07:00c, this is your lucky day! Look around this blog, ...c, this is your lucky day! Look around this blog, it's all about automatic navmesh generation.Mikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-76138206002171772052011-10-12T11:11:15.798-07:002011-10-12T11:11:15.798-07:00Even though I'm working in 2D and not 3D, I th...Even though I'm working in 2D and not 3D, I think automatic navmesh generation is a little beyond my abilities, especially since I cannot find anything on the subject on the internet.chttps://www.blogger.com/profile/16587168742111723848noreply@blogger.comtag:blogger.com,1999:blog-1272803659321539598.post-56944613734596118312011-10-12T05:21:29.210-07:002011-10-12T05:21:29.210-07:00c, that's true. I recommend automatic navmesh ...c, that's true. I recommend automatic navmesh building :)Mikko Mononenhttps://www.blogger.com/profile/11900996590678707801noreply@blogger.com