Timeline for How to gain accurate results with Painter's algorithm?
Current License: CC BY-SA 3.0
25 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 11, 2018 at 9:03 | answer | added | bishopnator | timeline score: 1 | |
| S Feb 13, 2013 at 8:13 | history | bounty ended | CommunityBot | ||
| S Feb 13, 2013 at 8:13 | history | notice removed | CommunityBot | ||
| Feb 5, 2013 at 11:16 | comment | added | bummzack | @msell Well, then you should ask this as a separate question. The question here is about the painters algorithm and you're obviously looking for something else. There's also a reason that the painters algorithm isn't used on modern hardware. Using a z-buffer provides accurate z-sorting per-pixel and doesn't suffer from the problems that the painter algorithm does. | |
| Feb 5, 2013 at 11:04 | comment | added | msell | @bummzack A human could quite easily correctly sort the faces of this and many other cases where a distance to center sorting would fail. I'm looking for an algorithm that could do the same. | |
| Feb 5, 2013 at 8:04 | comment | added | bummzack | @msell Center is the most commonly used sorting criteria. Sure, you can use any other criteria (as the OP did), but that won't fix the flaws in painter's algorithm. You might fix one specific case but get an issue at another location. The OP clearly has problems with polygon overlap (it comes with the perspective). It doesn't have to be a scenario as in the school-books where there are piercing and cyclic overlaps of polygons.. these are the very extreme cases and just there to illustrate the issue properly. | |
| Feb 5, 2013 at 7:36 | comment | added | msell | @bummzack At least Wikipedia doesn't say anything about the polygon center. The problem is deciding which polygons are in front of which ones, and distance to polygon centers is just one possible sorting criteria. Original poster tried many different ways and couldn't find a generic one even though his example doesn't fall into either of the special cases that needs cutting (cyclic overlapping or piercing polygons). | |
| Feb 5, 2013 at 7:12 | comment | added | bummzack | @msell The questions specifically asks how to gain accurate results with the painters algorithm. Painters algorithm sorts by the distance of the polygon center to the camera. This is fast and easy to implement, but it's flawed unless you can ensure no edge cases will arise (which will really frequent if you have large polygons and changing perspective eg. rotating scenes). I don't understand why you're putting a bounty on this; if you can ensure there's no need to cut polygons, just sort them with the painter's algorithm? | |
| S Feb 5, 2013 at 6:20 | history | bounty started | msell | ||
| S Feb 5, 2013 at 6:20 | history | notice added | msell | Draw attention | |
| Feb 4, 2013 at 5:57 | comment | added | msell | This is an excellent question I have not found a good answer yet. Suggesting Painter's algorithm as the solution is insufficient, as it doesn't explain how to achieve it. Then the discussion always starts to talk about the unsolvable cases. What if we could assume that a sorting order always exist without the need for cutting the polygons as in the given example image? How to find out the dependency graph for topological sorting for the faces in such cases? | |
| Jul 1, 2011 at 13:59 | vote | accept | pimvdb | ||
| Jul 1, 2011 at 12:56 | history | edited | pimvdb | CC BY-SA 3.0 | added 26 characters in body |
| Jul 1, 2011 at 12:41 | comment | added | pimvdb | @CiscolPPhone: They're all cubes/cuboids like in the image. They should be able to be animated smoothly though, so they're not always at discrete grid fields. | |
| Jul 1, 2011 at 12:40 | answer | added | bummzack | timeline score: 15 | |
| Jul 1, 2011 at 12:39 | comment | added | pimvdb | I'm drawing 2D shapes with 4 vertexes and I cannot work on a per-pixel basis because it's too slow. I'm not utilizing the best drawing framework, so Z-buffering is not a choice. I'm just calculating the projected 2D points and draw 2D shapes. | |
| Jul 1, 2011 at 12:37 | history | edited | pimvdb | CC BY-SA 3.0 | added 510 characters in body |
| Jul 1, 2011 at 12:26 | history | tweeted | twitter.com/#!/StackGameDev/status/86772565728698368 | ||
| Jul 1, 2011 at 12:23 | comment | added | Jonathan Connell | @pimvdb Can you put that image in your original question? :) It may help if you provided more information, like a specific example; It could be that your calculations are wrong. I can't quite understand "a face might have a closer distance but is still further away" also. Would it be possible for you to try implementing a Z-buffer? | |
| Jul 1, 2011 at 12:19 | comment | added | CiscoIPPhone | Are all your polygons on a regular grid like that? If so there may be grid specific things you can do to improve this. | |
| Jul 1, 2011 at 11:13 | comment | added | pimvdb | @3nixios: You're completely correct, but the problem I'm facing is calculating the distance. As I stated, I've tried several distance methods but they're all not perfect. This order results from midpoint distance sorting: i.imgur.com/AcfCm.png. | |
| Jul 1, 2011 at 11:05 | comment | added | Jonathan Connell | All your objects, triangles or vertices will be a certain distance away from the camera when you start drawing. Implementing the basic algorithm (have you succeded?) would be to determine this distance from the camera for each triangle and draw them in the order furthest to nearest. Once that is done, you need to start looking for intersections and cutting up your triangles, which is a whole different ball game. Why can't you use Z-Buffer already? :P | |
| Jul 1, 2011 at 10:58 | comment | added | pimvdb | @3nixios: Yes, obviously, but in what way can I determine the order of 'back to front'? | |
| Jul 1, 2011 at 10:57 | comment | added | Jonathan Connell | The painters algorithm is just drawing from back to front. | |
| Jul 1, 2011 at 10:47 | history | asked | pimvdb | CC BY-SA 3.0 |