Ideas on how to approach this C problem...

[aCynic2]

I'll try to make this as concise as possible.

I have a 3D model defined by a list of triangles. Each triangle is defined with it's own set of three vertices. I need to optimize this down to just a single list of vertices with no duplication for future calculations with the vertices of each triangle now holding an index into the vertex list.

I've pretty much have something, but it seems rather kludgy. This is pseudo code, but it conveys the message clearly.

The function attempts to insert the vertex into the array sorted by x, y, z because I'll need to search quickly later to verify the existance of a pre-existing vertex and for later on. There's three possible return states, one being major failure (memory allocation), two not.

If it can add it, it does and needs to return an index in the array where the vertex was added and an indicator of that state.

The state indicator signals to the calling function that the list was modified and all index values in the index based triangle list of equal or greater value need to be incremented and the new surface index value assigned after.

If the vertex exists, it needs to signal this state to the calling function, because it means that the new surface index value can be assigned straight away.

This function returns:

1 for vertex added, thus array modification.
0 for memory allocation failure.
-1 for vertex exists and no array modification was made.

v_idx = the place where the vertex was added or found, depending on the returned state.

uStatus = insert_vertex (v_list, sl->surface[ss].v[sv], &v_idx));

Can anyone else see a better way to get the values I'm needing?

as an aside, if the array runs out of space, the function reallocs with space for 50 more vertices (though I may decide to make it a doubling) and at the end of all processing will realloc to trim it down to essential and no more.

 

[exdeath]

Be sure you use a EPSILON value comparison to account for floating point rounding so that x==3.12345==3.12346 when you determine if a vertex is the same.

ie: if( fabs(vertex.x - vertices[ i].x) < 0.0005 && ... or whatever epsilon value works for you.

Other than that, I'd do another pass to sort the triangle and index order to take maximum advantage of hardware vertex caches by putting triangles with shared indices next to each other. Maybe go a step further and strip/fan the index list, but stripping/fanning is a whole topic by itself.

Not sure why you are having to modify existing indices. Either you are returning an index that already exists if there is a matching vertex, or you are appending a new vertex and returning a new index. You shouldn't have to modify an existing index just because a new vertex was inserted.

Break up the 'findvertex' and 'appendvertex' into two separate functions, and if 'findvertex' finds the vertex in the existing vertex list, it returns an index, otherwise, if it returns -1 you append a new index, something like:

if( (index = findvertex(vertex, vertexlist)) == -1)
{index = appendvertex(vertex, vertexlist);}

add index to output;

A good general rule of thumb is that when you have multiple return values for a function, the function is too big and trying to do too much and should be broken down into smaller more specific functions each with discrete return values.

 

[sao123]

Originally posted by: exdeath
Be sure you use a EPSILON value comparison to account for floating point rounding so that x==3.12345==3.12346 when you determine if a vertex is the same.

ie: if( fabs(vertex.x - vertices[ i].x) < 0.0005 && ... or whatever epsilon value works for you.

Other than that, I'd do another pass to sort the triangle and index order to take maximum advantage of hardware vertex caches by putting triangles with shared indices next to each other. Maybe go a step further and strip/fan the index list, but stripping/fanning is a whole topic by itself.

Not sure why you are having to modify existing indices. Either you are returning an index that already exists if there is a matching vertex, or you are appending a new vertex and returning a new index. You shouldn't have to modify an existing index just because a new vertex was inserted.

Break up the 'findvertex' and 'appendvertex' into two separate functions, and if 'findvertex' finds the vertex in the existing vertex list, it returns an index, otherwise, if it returns -1 you append a new index, something like:

if( (index = findvertex(vertex, vertexlist)) == -1)
{index = appendvertex(vertex, vertexlist);}

add index to output;

A good general rule of thumb is that when you have multiple return values for a function, the function is too big and trying to do too much and should be broken down into smaller more specific functions each with discrete return values.

if I read correctly, his insert is not really an append, it is a search & insert... IE insert into middle. A list sequenced in some way for easier searching.
But I agree with the bolded statement.

 

[sao123]

Originally posted by: aCynic2
I'll try to make this as concise as possible.

I have a 3D model defined by a list of triangles. Each triangle is defined with it's own set of three vertices. I need to optimize this down to just a single list of vertices with no duplication for future calculations with the vertices of each triangle now holding an index into the vertex list.

I've pretty much have something, but it seems rather kludgy. This is pseudo code, but it conveys the message clearly.

The function attempts to insert the vertex into the array sorted by x, y, z because I'll need to search quickly later to verify the existance of a pre-existing vertex and for later on. There's three possible return states, one being major failure (memory allocation), two not.

If it can add it, it does and needs to return an index in the array where the vertex was added and an indicator of that state.

The state indicator signals to the calling function that the list was modified and all index values in the index based triangle list of equal or greater value need to be incremented and the new surface index value assigned after.

If the vertex exists, it needs to signal this state to the calling function, because it means that the new surface index value can be assigned straight away.

This function returns:

1 for vertex added, thus array modification.
0 for memory allocation failure.
-1 for vertex exists and no array modification was made.

v_idx = the place where the vertex was added or found, depending on the returned state.

uStatus = insert_vertex (v_list, sl->surface[ss].v[sv], &v_idx));

Can anyone else see a better way to get the values I'm needing?

as an aside, if the array runs out of space, the function reallocs with space for 50 more vertices (though I may decide to make it a doubling) and at the end of all processing will realloc to trim it down to essential and no more.

A multi-child tree structure might benefit you more than a linear array...
They are completely dynamically allocated, and Most Tree structures are easier for building, searching, and insertions than a linear array. Consider this tree for some PA area codes... (814) (724) (412) (717)... obviously it will look somewhat different as more nodes are added... but the tree is only 3 levesl deep, and a traversal can be turned into an area at any given time for simple random access.


Grrr... dam coding window still not working.

http://pics.bbzzdd.com/users/sao123/tree.JPG


Then to answer your question...
The way I would code this is:

Node* Vertex = insert_vertex (Node& Head_ptr, sl->surface[ss].v[sv], Bool& uStatus);

(Node* Vertex) would be a return pointer to the vertex either existed or inserted. NULL would indicate a failure to insert due to memory error. (typically) you would have a halt, or failure message here)

Bool& uStatus would be optional... which would tell you if the node pre-existed or not. (not sure why you would even need to know this)

 

[sao123]

my bad... I just saw you said C... and ?I realized there is no ++...
What kind of evil are you?

OOP would so much greatly help your efforts.

 

[aCynic2]

Originally posted by: sao123

Originally posted by: exdeath
A good general rule of thumb is that when you have multiple return values for a function, the function is too big and trying to do too much and should be broken down into smaller more specific functions each with discrete return values.

if I read correctly, his insert is not really an append, it is a search & insert... IE insert into middle. A list sequenced in some way for easier searching.
But I agree with the bolded statement.

Yes, it's inserting in sorted order because I will need to search it for doing other geometry work later on.

Sao, I'm not really sold on OOP too much. I do it when I have to, and I will not touch "managed" code. I see no reason why faster computers should mean we're allowed to write sloppier, less performance driven code.

Don't get me wrong, I like operator overloading. I think that's an awesome feature. I also like templates and polymorphism. However, while I understand the last two concepts, I don't have enough experience to implement them to great effectiveness. I'm familiar with C. I fully grok function driven code and can easily develop in it.

OOP has it's benefit in the development cycle, but for me, that xlates to business apps. I suppose since this app is peripheral to my main goal, I could use it for this app, but the main game will be function driven.

Oh, and I never really understood the implementation of trees. I understand the concept, but my problem in understanding it is largely where to divide. Say I insert the number 0. Next comes 3. That would go to the right. Next 1, goes to the right of the head, left of 3. Next 10, to the right, of head, right of three...the tree is getting lopsided.

I never could follow the code to understand what was going on.

I'm going back to my U in the spring, but I'm looking at math and science, calc->linear algebra->vector analysis->etc and physics->mechanics->thermodynamics->etc.

I may take a programming class here and there. I may try to get a class on structures and such. But I'm not sure how well I'll do.

 

[sao123]

Originally posted by: aCynic2

Originally posted by: sao123

Originally posted by: exdeath
A good general rule of thumb is that when you have multiple return values for a function, the function is too big and trying to do too much and should be broken down into smaller more specific functions each with discrete return values.

if I read correctly, his insert is not really an append, it is a search & insert... IE insert into middle. A list sequenced in some way for easier searching.
But I agree with the bolded statement.

Yes, it's inserting in sorted order because I will need to search it for doing other geometry work later on.

Sao, I'm not really sold on OOP too much. I do it when I have to, and I will not touch "managed" code. I see no reason why faster computers should mean we're allowed to write sloppier, less performance driven code.

Don't get me wrong, I like operator overloading. I think that's an awesome feature. I also like templates and polymorphism. However, while I understand the last two concepts, I don't have enough experience to implement them to great effectiveness. I'm familiar with C. I fully grok function driven code and can easily develop in it.

OOP has it's benefit in the development cycle, but for me, that xlates to business apps. I suppose since this app is peripheral to my main goal, I could use it for this app, but the main game will be function driven.

Oh, and I never really understood the implementation of trees. I understand the concept, but my problem in understanding it is largely where to divide. Say I insert the number 0. Next comes 3. That would go to the right. Next 1, goes to the right of the head, left of 3. Next 10, to the right, of head, right of three...the tree is getting lopsided.

I never could follow the code to understand what was going on.

I'm going back to my U in the spring, but I'm looking at math and science, calc->linear algebra->vector analysis->etc and physics->mechanics->thermodynamics->etc.

I may take a programming class here and there. I may try to get a class on structures and such. But I'm not sure how well I'll do.

I agree with you to a point... I will never write managed code... and I dont like operator overloading and such...im not even really a fan of inheritance and such...
but simple structs and classes will make every programming project easier, because it allows you to model your data, and that translates directly into code.


... im used to trees because I taught data structures before... there is no rule which dictates that you use the exact tree you have seen or even a tree at all... the point is to develop a structure which will fit the needs of your data... not make your data fit a textbook structure.

 

[aCynic2]

Originally posted by: sao123
... im used to trees because I taught data structures before... there is no rule which dictates that you use the exact tree you have seen or even a tree at all... the point is to develop a structure which will fit the needs of your data... not make your data fit a textbook structure.

I'll make another attempt at learning trees, but I can't allow myself to be sidetracked by my lack of knowledge of tree structures.

I've been wanting to make this game since I was 18 and programming Atari 400s and C-64s in BASIC and ASM. I'm 42 now.

My first directed effort 10 years ago failed because the task was too huge for just me and I couldn't get support. I tried to do too much.

Now, I'm more organized and I intend to do this in managable phases. The end result of the first phase should help me to gauge player interest.

 

[sao123]

if there is something i can do to assist, let me know.

Just curious... this list of vertexes...
What type of values are they in your already built code?
Int Float Double Short Long

 

[aCynic2]

They are four byte floats.

 

[hans007]

hwo could you not be a fan of operator overloading or inhertance..


that said... just define a struct, and return a pointer to it. oro just make a function that puts the output into the parameters "a procedure"' (as it would be called in pascal)

 

[aCynic2]

Originally posted by: hans007
hwo could you not be a fan of operator overloading or inhertance..


that said... just define a struct, and return a pointer to it. oro just make a function that puts the output into the parameters "a procedure"' (as it would be called in pascal)

I decided to break up the function.

It's now three.

vertex_find - finds a vertex in the array using binary search, returns -1 if not found.
vertex_findpos - finds the best fit. Always returns an idx into the array.
vertex_add - adds the vertex, adjusts the array.

I'm not a big fan of the microsoft method of passing a struct with the parameters. If I have to pass a lot, then I would, but when I can and space and time are not tight, I'll break it up and pass as individual parameters.

 

[exdeath]

Originally posted by: aCynic2

Originally posted by: hans007
hwo could you not be a fan of operator overloading or inhertance..


that said... just define a struct, and return a pointer to it. oro just make a function that puts the output into the parameters "a procedure"' (as it would be called in pascal)

I decided to break up the function.

It's now three.

vertex_find - finds a vertex in the array using binary search, returns -1 if not found.
vertex_findpos - finds the best fit. Always returns an idx into the array.
vertex_add - adds the vertex, adjusts the array.

I'm not a big fan of the microsoft method of passing a struct with the parameters. If I have to pass a lot, then I would, but when I can and space and time are not tight, I'll break it up and pass as individual parameters.

All you need for each function there is a list pointer and a vertex pointer, and all of them return an int for the index. In fact all of them could have the same signature except for the function name itself for a nice clean 'vertex' API.

int vertex_find(vertex * v, vertex_list * vlist); /* returns index if v is found in list */
int vertex_add(vertex * v, vertex_list * vlist); /* returns index if v is successfully added to list */

etc. STL is really helpful with this kind of stuff if you can use C++. In fact 95% of what you want is already there; a list<your_vector> and an operator overload for comparing your_vector equality and you're done.

Check out the q3bsp source for some API structuring ideas on related topics. There is a lot of this kind of sorting, splitting, merging, indexing, consolidating, etc, of vertices and stuff in there.

 

[aCynic2]

Originally posted by: exdeath
int vertex_find(vertex * v, vertex_list * vlist); /* returns index if v is found in list */
int vertex_add(vertex * v, vertex_list * vlist); /* returns index if v is successfully added to list */

etc. STL is really helpful with this kind of stuff if you can use C++. In fact 95% of what you want is already there; a list<your_vector> and an operator overload for comparing your_vector equality and you're done.

Check out the q3bsp source for some API structuring ideas on related topics. There is a lot of this kind of sorting, splitting, merging, indexing, consolidating, etc, of vertices and stuff in there.

My vertex add is similar, but my find takes the list, the vertex and the beginning and end of the list, since it's a binary search, though in truth, I should eliminate the beginning, since it's always 0 on entry.

My vertex_list doesn't include the number of vertices. The model structure holds that:

[pre]

The data structures:
// The vertex proper, unodorned, no frills.
typedef struct _vertex
{
float x, y, z, w;
} VERTEX, VECTOR, POINT, PVERTEX *, PVECTOR *, PPOINT *;

typedef struct _surface
{
void *vertex[3]; // Reference to a VRL structure. This is the vertices that define the triangle that is this surface.
VECTOR normal; // The normal to this surface. With this and one point above, we can define the plane
// on which this surface lies.
} SURFACE;

typedef struct _vertex_ref
{
VERTEX v;
UINT num_refs;
SURFACE **surf_refs; // Reference to SURFACE. This is the list of surfaces that refer to this vertex.
} VRL;

typedef struct _mdl
{
UINT num_vertices;
void **vertex_list;
UINT num_surfaces;
SURFACE *surface_list;
} MDL;
[/pre]

The void *vertex allows me to store a pointer to the vertex there w/o having to define it first. Same for the **vertex_list in the model structure. It holds an array of pointers to vertex structures.

I've coded it, but haven't had time to compile and debug. I suspect I'll make minor changes, but not many. This is pretty much doing what I need it to do.

There is a single vertex list, a single surface list and each base structure can reference the other.