As with all projects, this has ground to a halt, owing to the start of my last year at the Uni, and crushing my MacBook Pro's lid and monitor under a toppling 50 kilo portable car stereo rig. Ever the presence of Death.
I'll be back as soon as I sort things out with the insurance company.
Tuesday, September 2, 2008
Thursday, August 7, 2008
Desperation, fear and a hack
This is starting to get ridiculous. Three days later, I can still find edge (ha ha ha) cases where the triangulator either produces mis-triangulated polygons or just plain locks up. The problem is detection of reflex vertices, characterized by having an internal angle larger than pi. I found a ready-made implementation that takes the inverse cosine of the dot product between its two edges. The problem with that implementation is that it only detects reflexes in one direction (since the dot product does not differ clockwise or counter-clockwise). I implemented my own test that calculates proper angles, but for some reason the triangulator hangs at times (it starts classifying all vertices as reflexes).
I don't know what to do about this, and I'm slowly starting to grow desperate. Once again, I should have written this by TDD, which would have ensured consistent checks for every step.
I'm currently on an airplane over Germany, fending off a slight fear of flying by writing unit tests. I've ensured that my angle-between-vectors test is reliable, which is something I doubted. Next up, a separate test for finding reflex vertices in CCW-winded polygons.
The reflex finder is asserted by a unit test, works fine. Now the only problem is that the triangulator hangs if the polygon self-intersects. The hang occurrs because it continuosly finds reflex points around the same index. […] No, it finds three reflexes, and then does not find an ear anywhere in the polygon. I wonder why... Even if the self-intersection is pathological, it should be able to traverse past that and find ears that are further down the path.
Ah, there we have it. It clips off all ears, and is left with only the self-intersection, which a triangle consisting of only three reflex points. I guess that one spiffy solution would be to just take the three last points and force them into a triangle, regardless. […] No, wait... If the user is evil enough to create multiple self-intersections, I have to detect the case where there are six remaining reflex points and so on. It's probably better to wait until there are only reflex points left, and then create triangles out of them. (Or just plain ignore them, I really don't care about rendering broken polygons correctly).
Ah, it works! Finally, after three days of head-bonking! I now flag self-intersecting polygons as unhealthy, so that I can render them in a sickly red color. Wonderful!
I don't know what to do about this, and I'm slowly starting to grow desperate. Once again, I should have written this by TDD, which would have ensured consistent checks for every step.
I'm currently on an airplane over Germany, fending off a slight fear of flying by writing unit tests. I've ensured that my angle-between-vectors test is reliable, which is something I doubted. Next up, a separate test for finding reflex vertices in CCW-winded polygons.
The reflex finder is asserted by a unit test, works fine. Now the only problem is that the triangulator hangs if the polygon self-intersects. The hang occurrs because it continuosly finds reflex points around the same index. […] No, it finds three reflexes, and then does not find an ear anywhere in the polygon. I wonder why... Even if the self-intersection is pathological, it should be able to traverse past that and find ears that are further down the path.
Ah, there we have it. It clips off all ears, and is left with only the self-intersection, which a triangle consisting of only three reflex points. I guess that one spiffy solution would be to just take the three last points and force them into a triangle, regardless. […] No, wait... If the user is evil enough to create multiple self-intersections, I have to detect the case where there are six remaining reflex points and so on. It's probably better to wait until there are only reflex points left, and then create triangles out of them. (Or just plain ignore them, I really don't care about rendering broken polygons correctly).
Ah, it works! Finally, after three days of head-bonking! I now flag self-intersecting polygons as unhealthy, so that I can render them in a sickly red color. Wonderful!
Wednesday, August 6, 2008
Close, but no tessellation
Had a strange run-in with the point-in-poly test that apparently broke for a while. I reverted the SVN and it started to work again, but I can't see the difference between the two. Oh well, never question a good thing, eh?
Now I need to start reworking the picking code. The way it works now is that when I select, say, an edge and move it, I just pass the edge's movement commands on to its vertices. However, it is very much possible to select an edge and one of its vertices at the moment, and when dragging that selection, one of the vertices will be moved twice. So, instead of allowing movement of edges, I will only allow vertices to be moved. When selecting an edge, it will be selected, but it will also select its vertices. Movement commands sent to edges and polygons will be ignored.
Check! Selection and dragging working perfectly! Final step is to call the triangulator when moving vertices. The plan there is to take the intersection of "all selected objects" and "all vertices" to find "all selected vertices"; that set will be passed to the polygon soup to see which polygons contain any of the vertices. That set of polygons are added to an "affected by edit" list, that will be re-triangulated as I move vertices or edges around.
Well, hacking that in revealed that the triangulator almost worked – the last triangle was not part of the calculation. Two hours of fiddling revealed little bugs here and there, which in turn prompted a complete rewrite for O(n^2) complexity, which is a nice touch. It's still not anywhere near fast, but definitely good enough.
Nope, still not robust.
Now I need to start reworking the picking code. The way it works now is that when I select, say, an edge and move it, I just pass the edge's movement commands on to its vertices. However, it is very much possible to select an edge and one of its vertices at the moment, and when dragging that selection, one of the vertices will be moved twice. So, instead of allowing movement of edges, I will only allow vertices to be moved. When selecting an edge, it will be selected, but it will also select its vertices. Movement commands sent to edges and polygons will be ignored.
Check! Selection and dragging working perfectly! Final step is to call the triangulator when moving vertices. The plan there is to take the intersection of "all selected objects" and "all vertices" to find "all selected vertices"; that set will be passed to the polygon soup to see which polygons contain any of the vertices. That set of polygons are added to an "affected by edit" list, that will be re-triangulated as I move vertices or edges around.
Well, hacking that in revealed that the triangulator almost worked – the last triangle was not part of the calculation. Two hours of fiddling revealed little bugs here and there, which in turn prompted a complete rewrite for O(n^2) complexity, which is a nice touch. It's still not anywhere near fast, but definitely good enough.
Nope, still not robust.
Tuesday, August 5, 2008
Broken triangulator
For one thing, the triangulator contains a point-in-poly test that I've implemented, so polygon selection works fine.
I messed up the XNA triangulator implementation, so I've scale back and implemented a stupid simple ear clipping triangulator. It's O(n^3) instead of O(n^2), but I'll see if I can clean it out later on. Cubic complexity isn't really OK here, since I might have to call this one pretty often...
Seems to work, at least. I just have to hook it up so that the polygon is re-triangulated when I edit it.
I messed up the XNA triangulator implementation, so I've scale back and implemented a stupid simple ear clipping triangulator. It's O(n^3) instead of O(n^2), but I'll see if I can clean it out later on. Cubic complexity isn't really OK here, since I might have to call this one pretty often...
Seems to work, at least. I just have to hook it up so that the polygon is re-triangulated when I edit it.
Reworked editing model
It's too darn hot in here to keep a straight mind, but I'm trundling forwards, if slowly. I have the N-sided polygon tool running, but I'm not adding the polygons properly yet, as I'm reworking that mechanism totally. […] Working fine, and as if by magic, edge selection kicked in as well.
I've got most of the polygon editing working except triangulation and selection, which are pretty intertwined. Before hacking that in, I'd like to have an SVN commit, but the server's down. Once it comes back up, I'll port the triangulator to Obj-C, and let the PolygonProxy object keep a rendering/selection triangle soup around behind the scenes. If I can get down along with vertex linking tonight, I've done extremely well. (And it's actually pretty likely, since I got out of bed ridiculously late today...)
I've got most of the polygon editing working except triangulation and selection, which are pretty intertwined. Before hacking that in, I'd like to have an SVN commit, but the server's down. Once it comes back up, I'll port the triangulator to Obj-C, and let the PolygonProxy object keep a rendering/selection triangle soup around behind the scenes. If I can get down along with vertex linking tonight, I've done extremely well. (And it's actually pretty likely, since I got out of bed ridiculously late today...)
Monday, August 4, 2008
A change of tools
I'm half-finished with adding dragging/selection for edges, but I noticed that level panning has broke. I'll throw in a test for that and try to fix it. […] OK, that was not easy to figure out. The panner changes the view center, which is used to calculate the delta, so between two delta calculations, the frame of reference has changed completely. I fixed it by caching the "last view center" as well as the last mouse position, and then moving both points to their respective frames of reference before taking the delta of them. Works fine.
Now, I have a bit of refactoring to do, to accommodate the new edge and polygon proxies. Right now, there is no way to create a free vertex or a free edge. When the first vertex is constructed, I also create a temporary "working polygon" in the background which I add vertices to. There is no concept of an edge anywhere. When the polygon is closed, it is inserted in the polygon list, and that's it. This is broken, and will be re-worked.
What I want to do is insert a vertex where I click, and then insert another vertex linked to the cursor. I also insert an edge between them. This is repeated until I (a) hit the starting vertex for this face in which case I create a polygon from the vertices and add the edges; or (b) double-click, in which case I add all the edges. To support this setup, I need a way to see if an edge between two given vertices already exists.
I've also found a simple way to triangulate 2D polygons (ear cutting) with a ready-made implementation that I'll try to hack into the editor. (http://xnawiki.com/index.php?title=Polygon_Triangulation)
Hm, I played around with my modeller-of-choice, and realized that freehand vertex placement is really isn't necessary. Dropping in n-cornered polygons and allowing linking and extrusion should be a much better way to work. Perhaps simple lofting could be useful...
Right, so my new plan of action is to add in the n-sided poly tool since I want it anyway. Given that, I'll see if it makes sense to keep the freehand tool, or just bury that part of the editor. One possible conundrum is that an poly with more than three vertices can be made concave, but I can easily keep it triangulated behind the scenes for rendering, and present it as arbitrary to the user.
Now, I have a bit of refactoring to do, to accommodate the new edge and polygon proxies. Right now, there is no way to create a free vertex or a free edge. When the first vertex is constructed, I also create a temporary "working polygon" in the background which I add vertices to. There is no concept of an edge anywhere. When the polygon is closed, it is inserted in the polygon list, and that's it. This is broken, and will be re-worked.
What I want to do is insert a vertex where I click, and then insert another vertex linked to the cursor. I also insert an edge between them. This is repeated until I (a) hit the starting vertex for this face in which case I create a polygon from the vertices and add the edges; or (b) double-click, in which case I add all the edges. To support this setup, I need a way to see if an edge between two given vertices already exists.
I've also found a simple way to triangulate 2D polygons (ear cutting) with a ready-made implementation that I'll try to hack into the editor. (http://xnawiki.com/index.php?title=Polygon_Triangulation)
Hm, I played around with my modeller-of-choice, and realized that freehand vertex placement is really isn't necessary. Dropping in n-cornered polygons and allowing linking and extrusion should be a much better way to work. Perhaps simple lofting could be useful...
Right, so my new plan of action is to add in the n-sided poly tool since I want it anyway. Given that, I'll see if it makes sense to keep the freehand tool, or just bury that part of the editor. One possible conundrum is that an poly with more than three vertices can be made concave, but I can easily keep it triangulated behind the scenes for rendering, and present it as arbitrary to the user.
Sunday, August 3, 2008
Where to go from here?
Not entirely sure where to go from here. I can either keep extending the editor and the geometry tools, beef up the renderer, start to investigate Python scripting, add support for static objects, start to subclass the different game modes...
I suppose that it would make sense to write some rudimentary camera tracking, so that I can play larger levels. Then again, perhaps a bout of planning would do well here, since I have obviously run out of direction on the project.
A Brief History of Stuff-to-plan:
- Geometry partitioning (BSP, quadtrees...)
- Texturing
- Requirements for the different game modes
- Jumping/multi-floored levels
Hm, this does not do. I need a more long-term project plan, one that I will have to mull over tomorrow or so.
Mkay, so after half a day of meditation I think that the proper direction is to get one of the game modes to near-completion. That way, I should be able to wring out the details on most levels of development and get into a tiered plan, instead of getting hung up on the little stuff this early.
So, here's the plan for going forward: do a proper spec for the Fortress mode, add edge/polygon proxy objects to the editor so that I can edit them better, add extrude/split/link tools to the editor, detect pucks that fall off the level, add jumping, add camera movement and an AI enemy. Let's get to it!
I suppose that it would make sense to write some rudimentary camera tracking, so that I can play larger levels. Then again, perhaps a bout of planning would do well here, since I have obviously run out of direction on the project.
A Brief History of Stuff-to-plan:
- Geometry partitioning (BSP, quadtrees...)
- Texturing
- Requirements for the different game modes
- Jumping/multi-floored levels
Hm, this does not do. I need a more long-term project plan, one that I will have to mull over tomorrow or so.
Mkay, so after half a day of meditation I think that the proper direction is to get one of the game modes to near-completion. That way, I should be able to wring out the details on most levels of development and get into a tiered plan, instead of getting hung up on the little stuff this early.
So, here's the plan for going forward: do a proper spec for the Fortress mode, add edge/polygon proxy objects to the editor so that I can edit them better, add extrude/split/link tools to the editor, detect pucks that fall off the level, add jumping, add camera movement and an AI enemy. Let's get to it!
Subscribe to:
Posts (Atom)