importing 3D scenes from Excel
Author
Hellos. I'm currently working on an importer procedure for my software renderer. I want to port triangle lists generated with programs such as excel or contained in files of the .scn format. If you can call it a format. This is to allow alternative ways of producing complex, appealing 3D scenes to using 3DS max or similar expensive software. In both cases data will be stored using text in the file instead of the actual bytes of the file. However, the renderer is also able to open its own dedicated format that stores data directly as file bytes.
Now. When importing from excel or .scn there are problems obviously. Organizing, indexing, removing colinear triangles or identical ones, etc need doing. These have all been dealt with. The procedure already reads the text file and fills different arrays with the appropriate, filtered data.
This is how I store my 3d scene and reference data after importing it from an excel list saved as a text file (or opening a dedicated format file):
triangle_array_A (3*integer set each) => edges (2*integer set each)=> points (3*float set each)
triangle_array_B (3*integer set each) => points (3*float set each)
There are some restrictions. For a maximum number of N vertexes there may be a maximum of (N-4)*3+6 triangle edges and a maximum of (N-4)*3+4 triangles. Because I use static allocation, for increased runtime speed and bug avoidance, N is fixed and determined precompilation by the programmer. This method of storage is aimed at sparing mainly the CPU with little regard for memory, altough it is not exactly wasted either. It's the next step I actually am having problems with. I want to fill these 3 arrays:
triangle_to_body_assignment_array (1*integer each). length is (N-4)*3+4.
edges_to_body_assignment_array (1*integer each). length is (N-4)*3+6.
vertex_to_body_assignment_array (1*integer each). length is N.
What I deem a body is a group of triangles that all share a trait: between whatever 2 vertexes of whatever 2 triangles that form a body, there exists a "route" of triangle edges, and vertexes implicitely, to connect the 2 vertexes. 2 sepparate bodies have no such routes between any of their respective vertexes regardless of possible planar intersections between their respective triangles.
On the basis of this I need to fill the 3 arrays above with numbers that show, for each position of the respective arrays, what body that respective triangle/vertex belongs to. Of course, these should be entirely related. You can't have a vertex that is indirectly listed to belong to a triangle in body 5, in the first array, be shown to also belong to body 7 in the second array. I'm trying to develop an efficient algorithm for this task on my own. It's pretty to solve tough, but I think this method of storing 3D data is much faster to use at runtime, altough perhaps more expensive memory wise and slower to load 3D data(or possibly noticeably faster?).
So. In clofing, any hints or links to existing algorithms for this application would be highly appreciated. And also thank you for the patience you showed reading this huge post.
[Edited by - sonyafterdark on March 30, 2006 7:05:45 AM]
if we're talking about microsoft excel (and not some fancy designer program i haven't heard of ;)) once i read about lionhead studios (peter molyneux' company) using excel spreadsheets as a datastore for game related information so that the game designers could just open the excel sheet and use excel as a design tool for tweaking knobs on the game (basically a more fancy ini file). molyneux mentioned the advantage of being able to prevent erroneous data to ripple into the game by using constraints in excel which a plain ini file cannot offer.
that said. if you can, i suggest making the excel exporter (or the converter) a managed .net tool. having a mixed mode assembly where only the parts interfacing with office are fully leveraging the CLR might be the best way to go. that way you can use the office primary interop assemblies. reading data from excel files is quite easy then. if you don't like this managed world you could consider java as an alternative managed world. i wouldn't normally suggest using java, but there are some neet libraries out there to access excel ;) data in a very simple way (simpler than primary interop assemblies, but not much).
cheers,
simon
that said. if you can, i suggest making the excel exporter (or the converter) a managed .net tool. having a mixed mode assembly where only the parts interfacing with office are fully leveraging the CLR might be the best way to go. that way you can use the office primary interop assemblies. reading data from excel files is quite easy then. if you don't like this managed world you could consider java as an alternative managed world. i wouldn't normally suggest using java, but there are some neet libraries out there to access excel ;) data in a very simple way (simpler than primary interop assemblies, but not much).
cheers,
simon
Quote:Original post by Anonymous PosterWe do the same here, and use a macro that executes an exporter to export the information to a custom file format.
if we're talking about microsoft excel (and not some fancy designer program i haven't heard of ;)) once i read about lionhead studios (peter molyneux' company) using excel spreadsheets as a datastore for game related information so that the game designers could just open the excel sheet and use excel as a design tool for tweaking knobs on the game (basically a more fancy ini file). molyneux mentioned the advantage of being able to prevent erroneous data to ripple into the game by using constraints in excel which a plain ini file cannot offer.
However, I still don't see why you're storing 3D models in an Excel spreadsheet. Surely you must be editing them in a modeling program then exporting them to a spreadsheet somehow, then exporting them again into your app. So why go through Excel?
i just realized that that was not what you asked *G* i'm sorry for that.. this is to be seen as a response to the previous poster then ;)
currently it sounds to me that you're trying to structure a pile of vertex data based on whether they belong to the same object or not (and have separate vertex/face lists etc).
could something like that be solved by searching for disconnected regions in a graph? that's just my first thought.. maybe i misunderstood your question, too.
simon
currently it sounds to me that you're trying to structure a pile of vertex data based on whether they belong to the same object or not (and have separate vertex/face lists etc).
could something like that be solved by searching for disconnected regions in a graph? that's just my first thought.. maybe i misunderstood your question, too.
simon
Author
Well. I don't use 3DS, Maya or the like. Game development is leisure time activity to me, not employment. What I do use is Valve's Hammer editor for Half-Life engine levels and the like of freeware. Unfortunately I can't port these from the .MAP format though. Awful bugs occur with the freeware I use to port from .MAP to .SCN (or other formats). But I really rather like how splines look. And the main purpose of this initially was to be able to load some sort of decent scene merely to test the renderer before even attempting (if ever) to write a complex loader (perhaps never perfect) aimed at established, complicated 3d formats for use with my renderer in the long run, formats that I might not like anyway. And even if I switch to some other way of importing data, I still need to solve this problem to be able to store the scene exactly as I want it for use by the (software) renderer.
Because I'm doing this for fun I don't have (any) deadlines to meet, and I can focus exclusively on research, development and test implementation rather than a quickly finished, working (if not bug free) game engine. I can implement all & only the features (actually come up with new features that don't exist) I wish, make all & only the optimisations I want, render the exact way I want (fish eye lens, orthogonal, perspective or other types of projections), etc. It gives much more freedom and control when coding than using existing APIs which also enjoy GPU hardware support, at the cost of that support.
I think using those 2 arrays to reference each triangle and vertex to the respective geometrical bodies they belong to is much more of an elegant and efficient solution than storing lots of handles (and lengths occupied in the array) everywhere to the first vertex/triangle of a body and aligning data in the vertex and triangle arrays so that I avoid mixing vertexes and triangles from different ones.
This way, I can take input for transforming each individual geometrical body in the scene, queue it in an array that remembers for each body what transformations need to be done before next frame is rendered and then go once through the vertex array (1 global array for all vertexes in the world space and 1 for camera space) and, depending which body each individual vertex belongs to, apply the appropriate transformations from the ones queued in the transform_instructions_and_parameters_array. Not one vertex is rotated, translated, scaled, etc. twice for the same frame or even stored twice in memory. Also all triangle edges are clipped ONCE each frame to the z=1 plane (viewplane), some other triangle's plane or the scanline. Perhaps I could even apply some sort of dynamic binary space partitioning, to be done in realtime? :)
Also, one thing I'll be able to do when I've found out how to reference all the vertexes, edges and triangles to their respective geometrical bodies is tell whether a particular body is closed or open by testing whether or not each of all it's edges is common to at least 2 of its triangles. If there's at least one edge that isn't there are certainly 2 more that aren't. This does not neccessarily mean that particular body is open but if it is closed then it is logically incorrect, with intersections between its own faces.
Oh, and I don't mean the excel spredsheet format itself as a format for my renderer, but more like a design tool for splines based scenes. I save the data as text files from which I extract(import) the mesh and structure it. And I thought about the graph regions too. This is KINDA the same style of problem, but with nowhere near as simple a solution.
Because I'm doing this for fun I don't have (any) deadlines to meet, and I can focus exclusively on research, development and test implementation rather than a quickly finished, working (if not bug free) game engine. I can implement all & only the features (actually come up with new features that don't exist) I wish, make all & only the optimisations I want, render the exact way I want (fish eye lens, orthogonal, perspective or other types of projections), etc. It gives much more freedom and control when coding than using existing APIs which also enjoy GPU hardware support, at the cost of that support.
I think using those 2 arrays to reference each triangle and vertex to the respective geometrical bodies they belong to is much more of an elegant and efficient solution than storing lots of handles (and lengths occupied in the array) everywhere to the first vertex/triangle of a body and aligning data in the vertex and triangle arrays so that I avoid mixing vertexes and triangles from different ones.
This way, I can take input for transforming each individual geometrical body in the scene, queue it in an array that remembers for each body what transformations need to be done before next frame is rendered and then go once through the vertex array (1 global array for all vertexes in the world space and 1 for camera space) and, depending which body each individual vertex belongs to, apply the appropriate transformations from the ones queued in the transform_instructions_and_parameters_array. Not one vertex is rotated, translated, scaled, etc. twice for the same frame or even stored twice in memory. Also all triangle edges are clipped ONCE each frame to the z=1 plane (viewplane), some other triangle's plane or the scanline. Perhaps I could even apply some sort of dynamic binary space partitioning, to be done in realtime? :)
Also, one thing I'll be able to do when I've found out how to reference all the vertexes, edges and triangles to their respective geometrical bodies is tell whether a particular body is closed or open by testing whether or not each of all it's edges is common to at least 2 of its triangles. If there's at least one edge that isn't there are certainly 2 more that aren't. This does not neccessarily mean that particular body is open but if it is closed then it is logically incorrect, with intersections between its own faces.
Oh, and I don't mean the excel spredsheet format itself as a format for my renderer, but more like a design tool for splines based scenes. I save the data as text files from which I extract(import) the mesh and structure it. And I thought about the graph regions too. This is KINDA the same style of problem, but with nowhere near as simple a solution.
This (hopefully I got it right) should generate the arrays:
// renamed for practical purposestA = triangle_array_A;tB = triangle_array_B;// also assuming, tA and tB contain same faces in same ordert2baa = triangle_to_body_assignment_array;v2baa = vertex_to_body_assignment_array;// structuresint[] stack;int stackSize;// helper methodsvoid push(int faceIndex){ stack[stackSize++] = tA[3 * faceIndex) ]; stack[stackSize++] = tA[3 * faceIndex) + 1]; stack[stackSize++] = tA[3 * faceIndex) + 2];}bool containsEdge(int faceIndex){ for (int i = 0; i < 3; i++) { for (int s = 0; s < stackSize; s++) if (stack == ta[<span class="cpp-number">3</span> * faceIndex + i]) {<br> <span class="cpp-comment">// if an edge can be shared between two and exactly two faces only</span><br> <span class="cpp-comment">// add this for a slight speed increase</span><br> <span class="cpp-comment">//</span><br> <span class="cpp-comment">// stack = stack[stackSize];</span><br> <span class="cpp-comment">// stackSize–;</span><br><br> <span class="cpp-keyword">return</span> <span class="cpp-keyword">true</span>;<br> }<br> }<br> }<br> <span class="cpp-keyword">return</span> <span class="cpp-keyword">false</span>;<br>}<br><br><span class="cpp-keyword">void</span> setBody(<span class="cpp-keyword">int</span> faceIndex, body);<br>{<br> <span class="cpp-comment">// eA is your array defining edges</span><br> t2baa[faceIndex] = body;<br> v2baa[eA[<span class="cpp-number">2</span>*tA[<span class="cpp-number">3</span>*faceIndex ] ]] = body;<br> v2baa[eA[<span class="cpp-number">2</span>*tA[<span class="cpp-number">3</span>*faceIndex ]+<span class="cpp-number">1</span>]] = body;<br> v2baa[eA[<span class="cpp-number">2</span>*tA[<span class="cpp-number">3</span>*faceIndex+<span class="cpp-number">1</span>] ]] = body;<br> v2baa[eA[<span class="cpp-number">2</span>*tA[<span class="cpp-number">3</span>*faceIndex+<span class="cpp-number">1</span>]+<span class="cpp-number">1</span>]] = body;<br> v2baa[eA[<span class="cpp-number">2</span>*tA[<span class="cpp-number">3</span>*faceIndex+<span class="cpp-number">2</span>] ]] = body;<br> v2baa[eA[<span class="cpp-number">2</span>*tA[<span class="cpp-number">3</span>*faceIndex+<span class="cpp-number">2</span>]+<span class="cpp-number">1</span>]] = body;<br>}<br><br><span class="cpp-keyword">int</span> firstUnprocessed()<br><span class="cpp-comment">// return index of first element in t2baa equal to -1</span><br><span class="cpp-comment">// return -1 if no such element</span><br><br><span class="cpp-comment">// algotithm</span><br><span class="cpp-keyword">void</span> process()<br>{<br> <span class="cpp-comment">// nFaces is number of triangles or length(tA) / 3</span><br> <span class="cpp-comment">// fill t2baa with -1</span><br> <span class="cpp-comment">// fill v2baa with -1</span><br> <span class="cpp-comment">// allocate stack to same size as nFaces * 3</span><br> <span class="cpp-keyword">int</span> faceIndex;<br> <span class="cpp-keyword">int</span> body = <span class="cpp-number">0</span>;<br> <span class="cpp-keyword">int</span> first = <span class="cpp-number">0</span>;<br><br> <span class="cpp-keyword">while</span> (first > -<span class="cpp-number">1</span>) {<br> stackSize = <span class="cpp-number">0</span>;<br><br> faceIndex = first;<br><br> push(faceIndex);<br> setBody(faceIndex, body);<br><br> <span class="cpp-keyword">while</span> (faceIndex < nFaces)<br> {<br> <span class="cpp-keyword">if</span> (t2baa[faceIndex] == -<span class="cpp-number">1</span>) {<br> <span class="cpp-keyword">if</span> (containsEdge(faceIndex)) {<br> push(faceIndex);<br> setBody(faceIndex, body);<br> <br> <span class="cpp-comment">// start from scratch, to find out-of-order edges</span><br> faceIndex = i;<br> }<br> }<br> faceIndex++;<br> }<br> body++; <br> first = firstUnprocessed();<br> }<br>}<br><br><br><br><br></pre></div><!–ENDSCRIPT–><br><br>The whole idea is to select a face, then keep going through face list, adding faces that share the edge. Once there are no more faces to add, you've completed defining a body. Then start again, this time defining a new body. Triangles, which belong to no body become a body in itself. There are no checks of any kind either for degenerate geometry, or validity of indices (you state those problems are solved already).<br><br>One thing to keep in mind, is that your 3D API will determine the speed of rendering. And that API also defines the structure you will use for best performance.Quote:Well. I don't use 3DS, Maya or the like.
i dont know if youre aware but there are also freeware modelling apps, eg blender.
Author
thanks for all the input everyone. especially the code. sorry but I'm not sure I'm going to use it. I think I'll try to write my own after all. I thought I could make it more efficient than this. I wanna make sure I can't. 10x anyway.
Quote:Original post by zedzeekQuote:Well. I don't use 3DS, Maya or the like.
i dont know if youre aware but there are also freeware modelling apps, eg blender.
ftw! Blender rocks big time, if you have the time to learn it! Its MS-DOS for 3D Modelling!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
