Object Subdivision question

Page 1 of 1

12 Replies - 1341 Views - Last Post: 27 February 2011 - 12:24 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=217271&amp;s=f1925b8fa378c9707bed96318731fe5b&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 Kain6622

• D.I.C Regular

Reputation: 19
• Posts: 266
• Joined: 18-March 10

Object Subdivision question

Posted 19 February 2011 - 12:07 PM

Hi

I'm currently working with a recursive subdivision algorithm given in the opengl redbook and am trying to improve the method ( instead of it doing the calculations for the subdivision during the game loop, calculate it before and store it in an array ) the issue that i'm having at the moment is I can't get the relation between the number of subdivisions to do, the number of vertices and the number of triangles to make equations to get the required size for the array to store the subdivided mesh coordinates into, I've draw it out on paper to try get a better idea but the only thing I've learned out of this is the relations to the number of triangles after subdivision ( being 4^numsubs ) but I can't seem to figure out the relations to the number of vertices, nore can my friends... below is some figures from the first 4 subdivisions:
Triangle1:
subs = 0;
VertCount = 3;
TriCount = 1;  // 4^0 = 1

Triangle2:
subs = 1;
VertCount = 6;
TriCount = 4; // 4^1 = 4

Triangle3:
subs = 2;
VertCount = 15;
TriCount = 16;  // 4^2 = 16

Triangle4:
subs = 3;
VertCount = 45;
TriCount = 64;  // 4^3 = 64

The Subdivisional method is as follows:
void normalize( float v[3] )
{
GLfloat d = sqrt(v[0]*v[0]+v[1]*v[1]+v[2]*v[2]);
if( d == 0.0 )
{
}
v[0] /= d;
v[1] /= d;
v[2] /= d;
}

void normcrossprod( float v1[3], float v2[3], float out[3])
{
out[0] = v1[1]*v2[2] - v1[2]*v2[1];
out[1] = v1[2]*v2[0] - v1[0]*v2[2];
out[2] = v1[0]*v2[1] - v1[1]*v2[0];
normalize(out);
}

void DrawTriangle( float *v1, float *v2, float *v3 )
{
glBegin( GL_TRIANGLES );
glNormal3fv(v1);
glVertex3fv(v1);
glNormal3fv(v2);
glVertex3fv(v2);
glNormal3fv(v3);
glVertex3fv(v3);
glEnd();
}

void Subdivide( float *v1, float *v2, float *v3, long depth )
{
GLfloat v12[3], v23[3], v31[3];
GLint i;

if( depth == 0 )
{
DrawTriangle(v1, v2, v3 );
return;
}
for( i = 0; i < 3; ++i )
{
v12[i] = (v1[i]+v2[i])/2.0;
v23[i] = (v2[i]+v3[i])/2.0;
v31[i] = (v3[i]+v1[i])/2.0;
}
normalize(v12);
normalize(v23);
normalize(v31);
Subdivide( v1, v12, v31, depth-1 );
Subdivide( v2, v23, v12, depth-1 );
Subdivide( v3, v31, v23, depth-1 );
Subdivide( v12, v23, v31, depth-1 );
}

Please can someone help me figure our the relations between the number of subdivisions and the vertex count as I need this for getting the size of the new array storing the vertex data of the subdivided model.
Dave

Is This A Good Question/Topic? 0

Replies To: Object Subdivision question

#2 anonymous26

• D.I.C Lover

Reputation: 1
• Posts: 3,638
• Joined: 26-November 10

Re: Object Subdivision question

Posted 19 February 2011 - 03:12 PM

First of all you need to decide how you are going to be rendering your triangles, for example Triangle Strip or Triangle Fan and take it from there. At the very least you should be using these methods as a basis.

#3 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11792
• Posts: 44,315
• Joined: 27-December 08

Re: Object Subdivision question

Posted 19 February 2011 - 11:53 PM

Honestly, representing your object as a Graph rather than an array will make it much easier to break it down and determine which triangles share vertices. In Game Programming, representing directional or map-based data as a directional Graph, with the edges being Vectors, can greatly simplify a lot of your calculations.

#4 Kain6622

• D.I.C Regular

Reputation: 19
• Posts: 266
• Joined: 18-March 10

Re: Object Subdivision question

Posted 21 February 2011 - 06:02 AM

Thanks for the responces, ButchDean my triangles are going to rendered as GL_TRIANGLES easier to deal with than Triangle_fans or strips. macosxnerd101 Thanks, One of my friends did that but not as a graph, represented the problem on a speadsheet till he figured out the relation to the subdivisional value being: N = (2^subs)+1, where V = (N*(N+1))/2. There is only one problem left thats more to do with the coding side of this concept I'm trying to achieve, I'll explain the concept first:

As the code stands at the moment, the algorithm loops through each triangles and where depth is greater than zero a subdivision is applied ( producing 4 new triangles in replacement of the original 1 ) and selfcalls itself till depth is equal to zero.

The only problem I see within this algorithm as it stands is that all the subdivisions are calculated during runtime within the game loop ( possibly with a cost to performance ). So My concept to make this more efficient is to do all these calculations before the rendering loop from a premade array storing the new subdivided object ( which will also allow use of different rendering techniques of Vertex arrays and VBO's ). Firslty calculating the Required size of the array of vertices and indices as follow:
/* S = subdivision val, N = Number of vertices expected on the bottom of the triangle, T = tri count, V = vertice count */
N = (2^S)+1;   // Number of vertices expected on the bottom edge of the triangle
T = ( 3+1 )^S; // 3 vertices + one triangle to the power of the number of subdivision
V = (N*(N+1))/2;  // Calculation of the total number of vertices after the subdivision

I now have the sizes for the arrays where 'T' will the the array size of the number of indices to produce the object from the vertices, V is the new number of vertices for the object.

Instead of the subdivision function just producing the triangles and drawing them to screen with the GL_BEGIN()/GL_END() function calls, It should store the information into the array (maybe a list) to them have the pre calculated new object displayed on screen from this array ( saving the hassle of the subdivisional calculations being repeated every frame ).

My Question is How would be best to structure this to do this concept properly as with every subdivision one triangle will be made into 4, meaning the array or list would need to take this into account and remove the previous triangle before adding the new four triangles in it's place, but which method would be best to accomplish this?

#5 stayscrisp

• フカユ

Reputation: 1037
• Posts: 4,305
• Joined: 14-February 08

Re: Object Subdivision question

Posted 21 February 2011 - 06:05 AM

Could you not use a resizable data structure such as a vector? Then this would not be a problem.

#6 Kain6622

• D.I.C Regular

Reputation: 19
• Posts: 266
• Joined: 18-March 10

Re: Object Subdivision question

Posted 21 February 2011 - 06:21 AM

I might be able to, I was starting to think along those lines and looking into how the subdivision function works it deals with on triangle at a size till it's subdivided to the desired level, but I'm not fully used to recursive functions which brings me the question of when the function calls itself does it create a new instance of variables within that function or does it overwrite the first instance from the original call? ( thinking is that if it creates a new instance of any variables within the function each time it calls itself then this solves the issue of needing to remove one triangle when creating the next four as the final data ( depth == 0 is true ) only needs to be returned in this instance before moving onto the next triangle for subdivision.

#7 anonymous26

• D.I.C Lover

Reputation: 1
• Posts: 3,638
• Joined: 26-November 10

Re: Object Subdivision question

Posted 21 February 2011 - 10:55 AM

This is the very reason why you should be using the strip or the fan, as the points will be organized for you as per the respective algorithm. What you will then need is a structure that is able to store:

1. The triangle.
2. A set of references to its vertices.

The actual vertices used to store these triangle will be in a separate structure, probably in a vector as suggested by stayscrisp. So what you will have is:

Vertex structure
struct VERTEX
{
int x;
int y;
int z;
};

Triangle Structure
struct TRIANGLE
{
int ref;  // For triangle 1, 2, 3, etc...
VERTEX vert;
};

Then for you to build your triangle <regular/fan/strip> all the info can be placed in:

vector<TRIANGLE> tris;

And you have everything you need in a flexible structure. But! there is repeating data in this structure that I'll leave you to resolve.

#8 Kain6622

• D.I.C Regular

Reputation: 19
• Posts: 266
• Joined: 18-March 10

Re: Object Subdivision question

Posted 24 February 2011 - 04:04 AM

Thanks ButchDean and StayCrisp I'll look into both your concepts and ideas, they should resolve the issue that i'm having . thanks again.
Dave

#9 Kain6622

• D.I.C Regular

Reputation: 19
• Posts: 266
• Joined: 18-March 10

Re: Object Subdivision question

Posted 24 February 2011 - 05:20 AM

ok, I Structured my algorithm like you suggested ButchDean and used vectors as you and StayCrisp noted, The algorithm works fine for basic rendering but I run into problems when I try to use vertex array or VBO's as my struct goes like follows:
/* Structured data for each triangle */
struct VERTEX
{
VERTEX(){}
VERTEX( float _x, float _y, float _z ){ x = _x; y = _y; z = _z; }
float x;
float y;
float z;
};

struct TEXTURE
{
TEXTURE(){}
TEXTURE( float _u, float _v ){ u = _u; v = _v; }
float u;
float v;
};

struct COLOR
{
COLOR(){}
COLOR( float _r, float _g, float _b ){ r = _r; g = _g; b = _b; }
float r;
float g;
float b;
};

struct TRIANGLE
{
TRIANGLE(){}
int ref;
VERTEX vert[3];
VERTEX norm[3];
VERTEX indices[3];
COLOR  color;
TEXTURE uvCoords[3];
};

The Problem I'm having is not so much the structure but more to how I gain accest to them in vertex arrays and VBO's, my VBO codes is as follows:
for( int i = 0; i < 20; ++i )
{
/* We then need to subdivide the Template and store the new object in the temporary lists */
Subdivide( &vdata[tindices[i][0]][0], &vdata[tindices[i][1]][0], &vdata[tindices[i][2]][0], m_subs);
}

glGenBuffers( 1, &Icosahedon_VBO );
glBindBuffer(GL_ARRAY_BUFFER, Icosahedon_VBO); //Bind the vertex buffer
glBufferData(GL_ARRAY_BUFFER, m_Data.size()*20, &m_Data[0].vert, GL_STATIC_DRAW); //Send the data to OpenGL

glGenBuffers(1, &Icosahedon_CBO);
glBindBuffer(GL_ARRAY_BUFFER, Icosahedon_CBO);
glBufferData(GL_ARRAY_BUFFER, m_Data.size()*20, &m_Data[0].color, GL_STATIC_DRAW);

glGenBuffers(1, &Icosahedon_IBO);
glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, Icosahedon_IBO);
glBufferData(GL_ELEMENT_ARRAY_BUFFER, m_Data.size()*20, &m_Data[0].indices, GL_STATIC_DRAW);

/* And in the render function */
glBindBuffer(GL_ARRAY_BUFFER, Icosahedon_VBO);
glVertexPointer(3, GL_FLOAT, 0, BUFFER_OFFSET(0));

glBindBuffer( GL_ARRAY_BUFFER, Icosahedon_CBO );
glColorPointer( 3, GL_FLOAT, 0, BUFFER_OFFSET(0) );

//Bind the index array
glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, Icosahedon_IBO);

//Draw the triangles
glDrawElements(GL_TRIANGLES, sizeof(tindices), GL_UNSIGNED_BYTE, BUFFER_OFFSET(0));

/* in the main application I Enable the vertex array client state as well as any other that I wish to use */

Should I plan/Restructure the triangle structure or is there a method around this to get to the proper data?

Thanks again.
Dave

#10 stayscrisp

• フカユ

Reputation: 1037
• Posts: 4,305
• Joined: 14-February 08

Re: Object Subdivision question

Posted 24 February 2011 - 05:29 AM

Can you explain a little more what the problem is? I'm not sure I understand.

#11 Kain6622

• D.I.C Regular

Reputation: 19
• Posts: 266
• Joined: 18-March 10

Re: Object Subdivision question

Posted 24 February 2011 - 05:43 AM

The Problem is the vertex data is incorrect when trying to use VBO's, it draws some triangles onto screen but in the incorrect places (grouped together) and not the shape it should be ( a icosahedron sphere ) but the object displays fine using the basic glBegin function and using glVertex*, glNormal* etc which I'm putting down to that I have full acces the the data that way. but with VBO's all the data in the structure is an array of some sort to access as seen in the code above isn't quite as friendly to access? I'm not sure if I'm passing the data incorrectly or just the structure isn't VBO or VA friendly?

#12 anonymous26

• D.I.C Lover

Reputation: 1
• Posts: 3,638
• Joined: 26-November 10

Re: Object Subdivision question

Posted 24 February 2011 - 09:04 AM

I haven't run your code, but I'm prepared to bet that the reason why you are having these problems is due to the way you are referencing or indexing your vertices. This goes back yo my suggestion of using strips or fans, since you will be certain of your organization.

#13 Kain6622

• D.I.C Regular

Reputation: 19
• Posts: 266
• Joined: 18-March 10

Re: Object Subdivision question

Posted 27 February 2011 - 12:24 PM

I've Fiddled with my code for abit and found a few errors that wouldn't of helped but Still Having some issues, I have a question based around try TRIANGLE struct which is as follows:
struct TRIANGLE
{
VERTEX vert[3];
NORMAL norm[3];
COLOR  color[3];
INDICES index;
TEXCOORDS TexCoord[3];
}

My Question about this is how would I go about referencing the index information in the array TRIANGLE properly/ do I actually require this as the TRIANGLE struct holds 3 vertices for the triangle so the shouldn't be the need for this? But even with this solved how do i pass all the information from the vector<TRIANGES> correctly into the GPU via buffers? also You had a 'int ref' in your version of the struct is this supported to hold the value for the current triangle/index or something else? sorry for asking so many questions.
Thanks again for the help.
Dave