Thread: Appropriate data structure

  1. #1
    Registered User gazsux's Avatar
    Join Date
    Mar 2002
    Posts
    72

    Appropriate data structure

    I am making a 3d world in which i am not allowed to use an api (except to plot points and handle the window). So i have to setup and maintain all the data and transformations etc myself. So ive been thinking about data structures and which one would be best. And i figured, since you guys are the masters i'd ask you for your opinions.

    The data will be coordinates read in from a text file. These coordinates will make up an object (cube, pyramid etc). Of which there will be a varying amount in the scene. Each vertex point will have x, y, z coordinates, r, g, b colour values and u and v texture coords. And again the number of vertices is not necesarily known or rather changes from object to object. So as you can see theres a large amount of data needed to be passed around. It also needs to be fast to access as it needs to be rendered quickly but easy to maintain and dynamic in its structure. So what are your thoughts as to which would be best?

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    My philosophy is that you learn by doing. Start off with what you know in order to meet the basic requirements. If you design everything first, it is much easier to identify design improvements in terms of more appropriate data structures and optimizations that can be made.
    Just based on what you've posted, an initial data structure may look like this:
    Code:
    typedef struct _vertex_t
    {
       coord_t x,y,z,u,v;
       color_t r,g,b;
    
       struct _vertex_t *next;
    } vertex_t;
    gg

  3. #3
    Registered User gazsux's Avatar
    Join Date
    Mar 2002
    Posts
    72
    yeh i have something similar at the moment. I have designed a linked list system, but i end up with a list of lists of lists if you get me. And its just a bit... crap. I spose if i made a dynamic array of your proposed structure that could be good. But ideally i wanted to get something in place before i got into it. As i tried improving as i went along on another recent project and ended up getting into a bit of a mess with it. But cheers, i'll play about with that one
    Last edited by gazsux; 03-18-2003 at 09:25 AM.

  4. #4
    Banned
    Join Date
    Jan 2003
    Posts
    1,708
    I'm not entirely sure what you were getting at. I think you mean you have a list system where one triangle's vertex points to the next vertex of the triangle. That's ok, but I've got an idea for another system (commonly known as vertex arrays). A lot of file formats implement this.

    Keep your vertex structure the same, but have an array of vertices. No two vertices should be the same, this is very very important. Then, instead of each triangle (or any other data type) having its own vertices, instead it has indices into the heap of vertices.

    Something like this:

    //your vertex structure, this is somewhat arbitrary, add/change whatever you need
    typedef struct {
    float x, y, z;
    } vertex_t3d;
    //just so you know what is going on, I'm including this before the other type definitions
    vertex_t3d * HeapOfVertices; //this is read in from the file and holds all of the different vertices that exist. No two vertices are the same, for that would defeat the purpose of vertex arrays
    //then your other higher level data structures will hold indices into the giant heap of vertices
    typedef struct {
    int IndexVertex1;
    int IndexVertex2;
    int IndexVertex3;
    } triangle_t3d;

    Do you get what I'm saying? This system is good for the following reasons:
    1) it is low on memory
    2) it is fast (when you render you are just indexing into arrays)
    3) it provides a way to not have to use triangle_strips but is also efficient on memory usage because even adjacent triangles that make up a quad will not take up more memory than needed i.e although each triangle is made up of 3 different vertices, only 4 different vertices ever actually get used, if each triangle owned its own vertices 6 vertices would be used, so this system is effectively 33% better on memory than having each triangle own its own vertices. Not using triangle_strips is a good thing in my opinion, because if you did use triangle_strips you have to add another item that must be read in from the file format (in this case the drawing mode. You are no longer drawing with triangles, you may have to draw with triangles or triangle strips, and keeping track of that is a pain).

    You can then create even larger data structures, this is a model class header file which resembles the milkshape3d (.ms3d) file format. It demonstrates everything I've tried explaining here.
    Last edited by Silvercord; 03-19-2003 at 01:29 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Include GTK+ just for a data structure?
    By Jesdisciple in forum C Programming
    Replies: 0
    Last Post: 04-12-2009, 07:19 PM
  2. pthread question how would I init this data structure?
    By mr_coffee in forum C Programming
    Replies: 2
    Last Post: 02-23-2009, 12:42 PM
  3. Data structure implementation
    By fkheng in forum C Programming
    Replies: 3
    Last Post: 07-31-2003, 07:44 AM
  4. can't insert data into my B-Tree class structure
    By daluu in forum C++ Programming
    Replies: 0
    Last Post: 12-05-2002, 06:03 PM
  5. Tab Controls - API
    By -KEN- in forum Windows Programming
    Replies: 7
    Last Post: 06-02-2002, 09:44 AM