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.
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?
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.
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.
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.
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. ;)
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: http://www.cosy.sbg.ac.at/~held/projects/triang/spiral_01.gif
). Thus, my idea is to perform the following:
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.
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:
iTriangulator ^ | | ------------------------------- | | 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
|<< <||Current||> >>|