Sign in to follow this  
gohkgohk

how to create this data structure?

Recommended Posts

for an BOOL 7x7x7 array called "base_array":

...
...
base_array[3][5][4]=0 ~> NULL
base_array[3][5][5]=1 ~> triangle[0] = {100,250,300}
                         triangle[1] = {200,100,219}
                         triangle[2] = {600,140,110}
                         triangle[3] = {800,120,410}
                         triangle[4] = {200,110,312}
base_array[3][5][6]=0 ~> NULL
...
...
base_array[4][1][3]=0 ~> NULL
base_array[4][1][4]=1 ~> triangle[12] = {500,200,350}
                         triangle[13] = {600,140,110}
                         triangle[14] = {800,120,410}
                         triangle[15] = {200,110,312}
base_array[4][1][5]=0 ~> NULL
...
...
...




At the end, the program will draw all the point in array "triangle" from [0] to end. If i modify base_array[4][1][3] to 1 , a part of triangle array will create for it to store the corresponding point. If i modify base_array[4][1][4] to 0 , the corresponding part of triangle array will be deleted. At the end, again, the program will draw all the point in array "triangle" from [0] to end. _____________________________________________ In this structure ,the array "triangle" need to be dynamic allocated. or create a new array for each element of base_array. so how to create this data structure? thx:) [Edited by - gohkgohk on January 30, 2008 7:27:26 AM]

Share this post


Link to post
Share on other sites
Uhhh.... what? What language is this? I really have absolutely no idea what you're trying to do. Why is your bool array 3D? What does it have to do with triangles? What does each index represent?

Share this post


Link to post
Share on other sites
i am doing a 3d modeling software using voxel and marching cube
each unit cube can point to an array if it is a part of object,
i do this , because if i only modify a part of object,
i only need to create or delete some triangles,
and do not need to update for the whole mesh

base_array[0][1][0] represent the following position

Thx~


voxel

After this ,
i will draw the whole triangle array again

Share this post


Link to post
Share on other sites
Isn't this going to consume a lot of memory? Especially for those cubes inside the actual object whom you may not get to ever modify (or see for that matter).

I don't really understand voxel or marching cube however. Perhaps you're onto something.

If you are using BOOL values to accelerate finding the modified portion of your surface, that could be a good technique. You will however face a challenge in determining the actual vertices/triangles to work on. One thing you can do is to keep the surface of your object into a separate vertex buffer of some kind and determine which vertices belong to which cube by intersecting with the cube volume in 3D and then storing indices to those vertices along with the BOOL value or in another 3dimensional array. (If the Vertex(x,y,z) is within all 6 planes that make the cube, then it belongs to that cube).

[SOURCE]
#define MAX_A 100
#define MAX_B 13
#define MAX_C 666

typedef struct
{
int *indexes;
int index_count;
} Baluba;


Baluba VertIndex[MAX_A][MAX_B][MAX_C]; // points to a list of indices for each cube
BOOL Accelerator[MAX_A][MAX_B][MAX_C];
[/SOURCE]

Share this post


Link to post
Share on other sites
Quote:
Original post by ttdeath
Isn't this going to consume a lot of memory? Especially for those cubes inside the actual object whom you may not get to ever modify (or see for that matter).

I don't really understand voxel or marching cube however. Perhaps you're onto something.

If you are using BOOL values to accelerate finding the modified portion of your surface, that could be a good technique. You will however face a challenge in determining the actual vertices/triangles to work on. One thing you can do is to keep the surface of your object into a separate vertex buffer of some kind and determine which vertices belong to which cube by intersecting with the cube volume in 3D and then storing indices to those vertices along with the BOOL value or in another 3dimensional array. (If the Vertex(x,y,z) is within all 6 planes that make the cube, then it belongs to that cube).

*** Source Snippet Removed ***[/source]


but the array size of each unit cube is not fixed.
Also, how can i get(draw) all the triangle again?

Share this post


Link to post
Share on other sites
As I said, I don't really get what you are trying to do.

My solution was for an arbitrary number of cubes of same size that occupy the same space as a 3D Model (convex model). In this case each cube contains a part of the model's volume.

What do you mean by "but the array size of each unit cube is not fixed" ?

If you need a variable number of triangles to "fit" in a cube, that's covered by the implementation by the pointer to a list of indexes.

[SOURCE]
int *p;
p = (int*) malloc(sizeof(int) * max_index_count_per_cube);

VertIndex[i][j][k].indexes = p;
VertIndex[i][j][k].index_count = 34;// actual number of indexes in this particular cube (i, j, k), and upto max_index_count_per_cube constant;
[/SOURCE]

Share this post


Link to post
Share on other sites
A basic approach (not tested):


struct coordinate {
int x, y, z; // ranging 0..6 each in base array, anything in triangles
coordinate(int x, int y, int z): x(x), y(y), z(z) {}
};

typedef std::vector<coordinate> triangle_list;
typedef std::map<coordinate, triangle_list> space_mapping;
space_mapping base_array;

// set up
triangle_list& t = base_array[coordinate(3, 5, 5)];
t.push_back(coordinate(100, 250, 300));
t.push_back(coordinate(200, 100, 219));

// don't need to do anything special to start adding triangles to an empty location

// remove everything from a location:
base_array.erase(coordinate(4, 1, 4));

// Copy all triangles in order to a single vector:
triangle_list all_triangles;
for (space_mapping::iterator it = base_array.begin(); it != base_array.end(); ++it) {
triangle_list& current_triangles = it->second;
std::copy(current_triangles.begin(), current_triangles.end(), std::back_inserter(all_triangles));
}

// Or if you just want to draw them in order, and you don't have to copy them to
// a vertex buffer or anything, you could use std::for_each instead of std::copy
// to call some function on each coordinate.


Or, just have one triangle list, and store indices in the map instead of triangle coordinates. But then you are responsible for updating everything if you try to insert an index in the middle. It will probably get very messy :)

Share this post


Link to post
Share on other sites
triangle *cubes[7][7][7];


If cubes[x][y][z] is NULL, there is no mesh, if it's not NULL, it contains array of triangles.

Why the bool array, NULL/non-NULL is an implicit boolean condition.

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
triangle *cubes[7][7][7];


If cubes[x][y][z] is NULL, there is no mesh, if it's not NULL, it points to an array of triangles.


Fixed; let's please be very careful about memory and object-ownership semantics if we are going to write code like this. :)

There is also the option of using boost::optional.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
A basic approach (not tested):


struct coordinate {
int x, y, z; // ranging 0..6 each in base array, anything in triangles
coordinate(int x, int y, int z): x(x), y(y), z(z) {}
};

typedef std::vector<coordinate> triangle_list;
typedef std::map<coordinate, triangle_list> space_mapping;
space_mapping base_array;

// set up
triangle_list& t = base_array[coordinate(3, 5, 5)];
t.push_back(coordinate(100, 250, 300));
t.push_back(coordinate(200, 100, 219));

// don't need to do anything special to start adding triangles to an empty location

// remove everything from a location:
base_array.erase(coordinate(4, 1, 4));

// Copy all triangles in order to a single vector:
triangle_list all_triangles;
for (space_mapping::iterator it = base_array.begin(); it != base_array.end(); ++it) {
triangle_list& current_triangles = it->second;
std::copy(current_triangles.begin(), current_triangles.end(), std::back_inserter(all_triangles));
}

// Or if you just want to draw them in order, and you don't have to copy them to
// a vertex buffer or anything, you could use std::for_each instead of std::copy
// to call some function on each coordinate.


Or, just have one triangle list, and store indices in the map instead of triangle coordinates. But then you are responsible for updating everything if you try to insert an index in the middle. It will probably get very messy :)

sorry...
i only know a bit about std::map
what is the meaning of "triangle_list& t = base_array[coordinate(3, 5, 5)];"????
thx

Share this post


Link to post
Share on other sites
Quote:
Original post by gohkgohk
sorry...
i only know a bit about std::map
what is the meaning of "triangle_list& t = base_array[coordinate(3, 5, 5)];"????
thx


"Let t be a reference to the value in the base_array map which is keyed by the coordinate (3, 5, 5)".

std::map is an associative array; it "maps" from keys to values. In this code, the keys are coordinate objects. You use keys like array indices, and the values are like array elements (although the internal storage is not really an ordinary array). I make a reference so that the following code will change the triangle_list that is stored within the map, instead of making a copy and changing the copy.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
Quote:
Original post by gohkgohk
sorry...
i only know a bit about std::map
what is the meaning of "triangle_list& t = base_array[coordinate(3, 5, 5)];"????
thx


"Let t be a reference to the value in the base_array map which is keyed by the coordinate (3, 5, 5)".

std::map is an associative array; it "maps" from keys to values. In this code, the keys are coordinate objects. You use keys like array indices, and the values are like array elements (although the internal storage is not really an ordinary array). I make a reference so that the following code will change the triangle_list that is stored within the map, instead of making a copy and changing the copy.


thx~

[Edited by - gohkgohk on February 4, 2008 10:57:17 AM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this