Archives for: July 2007


Permalink 08:48:48 pm, Categories: Design Log  

Design Log

I apologize for my lack of updates over the last week or two. Having completely finished geometry conversion, I decided to continue the project with COLLADA effects (FX). However, the problem was that the FX section of COLLADA is specifically designed to utilize a shader model, which is still in heavy development in Crystal Space. As such, I have decided (with the advice of res2k and thebolt) that the initial COLLADA conversion system will convert the <library_materials> section, and only convert <effect> elements which utilize <blinn> or <phong> elements - which will be converted to normal surface colorings. Shaders and other effects will be saved for a subsequent release of the COLLADA conversion system. Up to this point, textures are intended to be included in this first release.

Additionally, I have taken another look at the Triangulate3D class. After speaking with Martin Held (author of the FIST algorithm), I was informed that triangulation of polyhedral surfaces is, in some cases, an NP-complete problem. This I didn't realize. However, all is not lost, as he instructed me in ways to utilize heuristics to project 3D polygons onto planar surfaces, thereby converting a 3D polygon triangulation problem into a set of 2D triangulation problems, each of which can be solved in at worst, O(n^2) time, using an ear-clipping approach. I intend to implement this in the coming few days.

Finally, I suspect there are a few minor bugs in the geometry conversion, which I will address as soon as I have time. It is possible, however, that I may not get to them until after the scene conversion is finished. I am, as of yet, still unable to see the exported cs library files using viewmesh. I will post an example cs file output from the collada conversion system in the next day or so, so that others can have a look at it, and perhaps tell me what I am doing wrong that it doesn't appear in viewmesh. The syntax and whatnot appear correct, but perhaps something is just messed up. The viewmesh program doesn't spit out an error - it does seem to load the mesh, it just doesn't appear in the scene.

That's all for today. I'll keep you all posted on further progress as I make it.


Permalink 10:33:31 pm, Categories: Artificial Intelligence Module  

Graph Loading!

Hello there!

I've been working lately mostly in fixing bugs.

Pcsteer, PcPathfinder and Celgraph are finished but they do have some bugs yet to be fixed. Some of these are:

- celgraph crashes if you call A* with the same node as initial and goal.
- Pursue in pcsteer calculates wrong velocity some times. I have not find a pattern which describes when this happens.
- FollowTwoWayPath and FollowCyclicPath in celgraph are not working correctly.
- This not actually a bug, but there still some upgrades to be made to A* to achieve better time performance.

I expect to finished doccummenting my code and fixing bugs by the end of the week. I have also been studying for a final test tomorrow, then Ill be completely free.

I have already started looking for a good method to load graphs in an application. By the moment the only way you can do this
is coding a LoadGraph Function inside your behaviours file. I will start working on monday on a loading method through the cel.addons utility.

Finally I'll be working in adding formations to pcsteer and, thats all for now =)


Permalink 04:08:08 am, Categories: Coding Log  

Coding Log

After some arduous coding this afternoon and evening, I was able to get started on the materials section of the code. I was also able to finish writing the implementation of the general polygon conversion case (the triangulate method doesn't work still, but the code is in place for when it does work correctly).

I added a method to csTriangleMesh called AddTriangleMesh(const csTriangleMesh&), which merges an existing triangle mesh with the current one. Essentially, what it does is add all of the vertices of the parameter mesh, as well as all of the triangles to the current csTriangleMesh. This was necessary for the polygon implementation, as I had a bunch of csTriangleMeshes floating around, and I wanted exactly one of them. I figured this fit best inside the csTriangleMesh class itself, although this is open for debate. Also open for debate is whether the name of the function should be something more descriptive, such as "MergeInto()" or the like.

I haven't made a commit today, because there are still things that I want to test before committing it to the branch. (e.g. I haven't fully tested the AddTriangleMesh() function yet, and I don't want to commit without knowing it works 100%).

Finally, I want to state that I have been placing warning messages into the code for items in the collada convertor which aren't implemented yet. (e.g. the general polygon case, as well as polygons with holes, triangle strips, and triangle fans). It will now warn a user if a case is encountered that isn't fully implemented yet. Also, I'm not sure how to handle the <lines> element, because as we have moved fully to triangles, how are lines displayed in CS?


Permalink 08:14:37 pm, Categories: Coding Log  

Coding Log

After finishing the triangle geometry conversion, I have restarted looking at the Triangulate3D function. For some crazy reason, I still can't figure out why IsConvex() doesn't work quite right. Or rather, I know why it doesn't work right, but I am unsure how to fix it. The problem lies in the situation where when I am inserting consecutive points into a csPlane3 object, sometimes the resulting plane is defined counter clockwise, and sometimes it is defined clockwise. e.g. if one considers the polygon defined by the points:

(0, 10, 10)
(0, -10, 10)
(0, -10, -10)
(20, 5, -10)
(10, 0, -10)
(0, 10, -10)

Point number 4 (that is (10, 0, -10)) should be convex. However, what happens is that since the polygon loops back around, the plane defined by points 4, 5, and 3 is defined counter-clockwise, resulting in an incorrect result for the IsConvex() test. I am not quite sure how to fix this. Anyone who thinks they can provide some insight, feel free to look at my code. It's available in the libcrystalspace project (in MSVC) under the files triangulate3d.h and triangulate3d.cpp. It's been placed in the csgeom file, if you are not using msvc.

As a result of this problem, I am going to continue with the collada conversion by next moving to materials conversion. The fact that the collada conversion system doesn't currently support any polygons other than triangles isn't immediately a problem, since COLLADA exporting from Blender allows the user to export only triangles, which can then be used to test the collada system. I will look into the materials conversion today, and hopefully have it coded in the next few days, at which time I will re-investigate the triangulation function.


Permalink 11:19:12 pm, Categories: Coding Log  

Coding Log Supplemental

I edited the code to make sure that xml tag parameters were all lowercase (e.g. 'meshfact' instead of 'meshFact'). Also, I added a plugin tag so that it could be viewable in a scene once exported. It appears that the viewability still isn't there, though, as exported XML files can be imported into viewmesh using 'Import Lib', but the triangles don't show up. There aren't any errors, just no triangles. I wonder if there are other things that I need in the XML file (e.g. materials) before it will display.

Permalink 09:22:28 pm, Categories: Coding Log  

Coding Log

I was able to get the triangle conversion working completely today. It doesn't yet convert vertex normals from COLLADA format to CS. What it *does* do, however, is read in all of the vertices from the COLLADA file, add them to a triangle mesh, then construct triangles from the given vertices, and index the vertices accordingly. Once completed, the triangles are retrieved from the csTriangleMesh object, and written to the CS XML document in the correct format.

For the remainder of the day, I am going to be working on Triangulate3D(), as this is still not completed. Tomorrow, I hope to be finishing general polygon conversion.


Permalink 09:00:55 am, Categories: Coding Log  

Coding Log

I've redesigned the triangulation routine, at the recommendation of thebolt, to utilize an ear clipping algorithm. As of right now, I have got the function working, but there are a few bugs still left in the code. Namely, the triangulation routine is returning a triangle for each vertex in the polygon, which of course is not correct. I'm fairly certain I know where in the code the bug lies.

I intend to have this bug fixed tomorrow, at which time I will extend the code to work with polygons that have holes.

I am going to postpone testing of the triangulation function until after I have the rest of the geometry code finished. I feel like I am slipping further and further behind, and I need to make sure I get the XML conversion completed, as the convertor will be near useless without it. ;)


Permalink 10:59:46 am, Categories: World Editor  


I implemented reparenting and renaming since last time.
Reparenting was rather annoying as I had to write my own function to recursively copy the node and its children to the new location. But it seems to work smoothly and it's the first "cool" feature of the editor.

I spent the beginning of this week working on the action system (aka undo system).
Here's how it works.

Actions derive from iAction but have their own Initialize function taking their needed parameters.

How to create an action and use it:

  • Create a new instance of your action (new SomeAction(), or through scfCreateInstance, more on that later)
  • Query for the action's interface (iSomeAction),
  • Call someAction->Initialize (params),
  • Call actionmgr->Do (someAction);

Plugins can implement their own actions. To allow something to instantiate an action implemented in another module, the class should be added to the plugin's metadata. Then it should call scfCreateInstance<Interface> ("crystalspace.editor.action.someaction").

As it stands, the action system should be fully functional, including the undo/redo menu items. Reparenting is not undoable yet though.

One current problem is that when you rename something and then undo it, the tree view doesn't update to reflect the old name. I think the best method to get it to update is to have the tree view listen for each iEditorObject's name change. That is to say, I should add a general iEditorObjectChangeListener, that will signal when an object has changed so that interested views can update themselves. This applies to things like properties too, which will come later.

Future thoughts:

I'm going to implement a drawer which will draw a bounding box around the current selection in the 3D view as well as little billboard icons for lights (and later, camera positions). Ideally this will have a settings page where you can toggle whether to draw this stuff, or tweak the bbox colors. Settings is another thing I haven't gotten to, although it is not essential yet.

I'm still thinking about the best way to implement tools in general, and in particular the transform tools, as these are core tools that will be used all the time.

Other random Q&A's with myself
Should object select tool be undoable? No, would get quite annoying.
Should selecting something in scene browser select it in the 3d view (e.g. actually select it)? This seems like a good idea.

A little reflection:
GUI work has been interesting. I'm glad I got the chance to do it. In the GUI world, the little things count. Like the status bar/progress bar, or the edit menu telling you what action you're going to undo or redo, or dragging the nodes around in the scene browser to reparent them, or being able to customize your panel layout due to the flexible wxAUI. I've been trying to implement things in a way that is as intuitive as possible. I hope I can continue to find ideas to make things nicer.


Permalink 07:33:51 pm, Categories: Design Log  

Design Log

My intention today was to get the triangulate3d code written, but unfortunately, it looks like that isn't going to happen. Things have just been going really slow today. Thus, to adapt the schedule, I think I am going to combine the Triangulation and Finishing of Geometry conversion into a single stage. The combination of these two should be done by the time I laid out for Convert Geometry to be done.

The concept I have for the triangulation code is fairly straightforward. I intend to utilize the MakeMonotone algorithm given in deBerg et. al.'s computational geometry book. (I originally intended to use a Delaunay Triangulation, but I don't think that it's necessary to do all that work - we are given a polygon in 3D, so that makes the problem a little easier than a point cloud). Now, the problem I see is that the MakeMonotone algorithm (that is, break the polygon into y-monotone pieces, then triangulate each of these and combine) works on a 2D polygon. Normally, I thought it would be easiest simply to project the 3D polygon onto a 2D plane, but this doesn't work if the polygon wraps over on itself (consider a polygon like the following:
). Thus, my idea is to perform the following:

  1. Map from 3D to 2D in some manner

  2. Break polygon with holes into separate polygons without holes

  3. Triangulate each polygon according to algorithm in deBerg et. al.

  4. Re-construct original 2D polygon with holes

  5. Revert to original 3D polygon by un-doing mapping

The problem will be to determine the mapping (Note: The removal of holes isn't trivial, but I have an algorithm for it somewhere... I just can't remember where it is at the moment. I will find it. So, I'm going to do everything else first, then add it in later.) I thought about an LSCM-unwrap type of algorithm, but that relies on user cuts. The thing is, that if the polygon is some kind of wierd 3D shape that loops back on itself, then it's no longer a polygon, and I probably can just ignore that case.

The code I have been working on today has been mostly to add a test application, so I can visualize the two versions of a polygon. Ideally, I want to create a split window. The top has the un-triangulated polygon, and the bottom has the triangulated one. To begin with, what I want to do is show the polygon in 3D in the top (the original polygon), then show the polygon in 2D after the mapping in the bottom. I am working on this application, which will be called apptri3dtest, as this is being written.


Permalink 03:43:12 pm, Categories: Pathfinding  

Pathfinder propclass!

Hello there,

I know I have not written for a while, but thats basically because I had nothing new to say =P.

CelGraph is finished and it appears to be working correctly, however there are still some tests to be made.
Now, when I was testing it in a graph application I noticed how hard it was to create a path, call the graph, then call
pcsteer to follow that path and... you get the point.

So i created PcPathfinder, this class has similar functions to pcsteer (in fact it behaves very similar):


Seek will seek a position in the world using the graph, this way entities will be smarter to use certain paths instead of crashing against walls.

Pursue will do the same except that it will continue running A* in case the target has modified its position (as you can see this costs a lot)

Wander will use a function call RandomPath(int distance) in CelGraph which will create a random path of deepness distance ie: a random path with distance nodes.

Follow Cyclic Path will follow the indicated path and it will start over again once it reaches the end.

Follow One way Path will follow the indicated path and it will stop at the end.

Follow Two Way Path will follow the indicated path and it will follow it backwards once it reaches the end.

I thought these three functions may be useful for developers in case they want to set certain paths for there entities (guards for example may use this).

Finally I am thinging of adding a multiplier (float) property to edges.


Well, for the moment the cost between two edges is always the euclidean distance between them. But this will cause serious problems in games where you move slower in the mud or grass, etc. So, I will add this property, it will be 1.0 by default and it could be changed by the user with a SetMultiplier function.

Well, this is all for now, pcPathFinder still have bugs so Ill be working in this during the next week or so =)

Permalink 03:47:18 am, Categories: Personal Log  

Personal Log

I have been mulling over the concept of Triangulations, and I feel that I have come up with a good solution to the triangulation problem. First, I think that the class csTriangulate2 will suffice for most of what I need in the COLLADA conversion. However, I will need to adapt it to handle general polygons, including those with holes. I figured since I will be performing this, it might be a good idea to make sure that the triangulation class conforms to the SCF system, and give it an interface - say something like iTriangulator. Thus, the inheritance will look like:

      |                               |
csTriangulate2                csTriangulate3 (new)

I realize that my schedule has slipped a little bit, but in order to get things back on track, I plan the following re-vamped schedule for the remainder of the summer:

Triangulation: July 2 - July 3
Finish Geometry Conversion: July 4 - July 13
Materials and Texture Conversion: July 14 - July 28
Lighting/Scene Conversion: July 29 - July 31
Physics Conversion: August 1 - August 10
Animation/Rigging Conversion: August 11 - August 20

July 2007
Mon Tue Wed Thu Fri Sat Sun
 << < Current> >>
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31          

Blog All Title

This is the long description for the blog named 'Blog All'.

This blog (blog #1) is actually a very special blog! It automatically aggregates all posts from all other blogs. This allows you to easily track everything that is posted on this system. You can hide this blog from the public by unchecking 'Include in public blog list' in the blogs admin.



XML Feeds

What is this?

powered by