Convert triangles into an integer array

[eatrawmeat391]

Convert triangles to an integer array

We have this array of integer:

Code: Select all

integer_array = [27, 68, 72, 74, 76, 96, 114, 113, 64, 9, 98, 0, 20, 106, 1, 128, 86, 32, 131, 53, 58, 1, 121, 49, 143, 99, 62, 28, 26, 7, 76, 71, 44, 146, 18, 68, 42, 135, 154, 156, 70, 24, 5]

Using code we can transfer it into array of triangles:

Code: Select all

triangle_array = [[27, 68, 72], [68, 72, 74], [72, 74, 76], [74, 76, 96], [76, 96, 114], [96, 114, 113], [114, 113, 64], [113, 64, 9], [64, 9, 98], [9, 98, 0], [98, 0, 20], [0, 20, 106], [20, 106, 1], [106, 1, 128], [1, 128, 86], [128, 86, 32], [86, 32, 131], [32, 131, 53], [131, 53, 58], [53, 58, 1], [58, 1, 121], [1, 121, 49], [121, 49, 143], [49, 143, 99], [143, 99, 62], [99, 62, 28], [62, 28, 26], [28, 26, 7], [26, 7, 76], [7, 76, 71], [76, 71, 44], [71, 44, 146], [44, 146, 18], [146, 18, 68], [18, 68, 42], [68, 42, 135], [42, 135, 154], [135, 154, 156], [154, 156, 70], [156, 70, 24], [70, 24, 5]]

- The code works like this:
+ Item 0: The first 3 items are in
[27,68,72]
f1 = 27, f2=68,f3=72

Everytime
f1 = f2 = 68
f2 = f3 = 72
+ Item 1: Replace f3 with the next item of the integer list
f1 = 68, f2=72,f3=74
[[27, 68, 72], [68, 72, 74]
f1 = f2 = 72
f2 = f3 = 74
+ Item 2 and on: Just replace f3 with the next item of the integer list, and shift f2 to f1 and f3 to f2

*** What we want is to convert the triangle array back into an integer array
*** However, Blender gives us the triangle array that might not follow the rule of the integer unpacking, user might edit and alert the triangle array so we can't depend on the unpacking rule of the array and we need to convert that triangle array to integer array.
*** If not possible, split them in group
For example
[[4,5,9], [5,9,6], [3,8,2]]
the third items cannot be fit into the integer array, so they will be move into another group
we will get 2 group
group 0: [4,5,9,6]
group 1: [3,8,2]
My current algorithm is like this:
Turn the 3D array into a dict with 2D keys
{4: [[5,9]], 5: [[4,9] , [9,6]], 6: [[5,9]], 9: [[4,5], [5,6]], 3: [[8,2]], 8: [3,2], 2:[[8,3]]}

We will get the first key 4 and write out the 3 items in position 0
[4, 5, 9]
next we will decide if we want to use 5 or 9, this part I don't know how to efficient pick choose the next key to follow.
+ Path 1: In this sitation I will go first with 5
[[4,9], [9,6]], since 4 and 9 is already in the list we will skip it, we get [9,6] , 9 is already in so we pick 6
our output will be
[4,5,9,6]
+ Path 2: I will go with 9
in 9 we get [[4,5], [5,6]]
Using the same procedure we will get
[4,5,9,6]
* In this case we can choose either one, my algorithm is programmed to select the list with the highest length

Problem with my algorithm:
- It is dependent on the position, it has to be exactly unpacked the way I said above.
- It cannot work on the integer array which has duplicates since I have coded it to ignore duplicate
[27, 68, 72, 74, 76, 96, 114, 113, 64, 9, 98, 0, 20, 106, 1, 128, 86, 32, 131, 53, 58, 1, 121, 49, 143, 99, 62, 28, 26, 7, 76, 71, 44, 146, 18, 68, 42, 135, 154, 156, 70, 24, 5]
You can see in this array the number 1 appears in 2 places. - I don't know how to specify the end condition, I would go on until I meet a key with only 1 element of 2D arrays. However not all situation works with this condition. Especially when multiple groups are involved
- It seems wasteful and redundant way to use data structure.
Example Blender data:

Code: Select all

[[1, 59, 0], [59, 60, 0], [0, 60, 9], [60, 66, 9], [9, 66, 41], [66, 42, 41], [41, 42, 43], [42, 107, 43], [43, 107, 48], [107, 104, 48], [48, 104, 51], [104, 40, 51], [51, 40, 54], [40, 38, 54], [1, 0, 4], [0, 5, 4], [4, 5, 14], [5, 26, 14], [14, 26, 27], [26, 28, 27], [27, 28, 45], [28, 44, 45], [45, 44, 47], [44, 48, 47], [47, 48, 50], [48, 51, 50], [50, 51, 53], [51, 54, 53], [62, 2, 7], [2, 6, 7], [7, 6, 25], [6, 10, 25], [25, 10, 18], [10, 12, 18], [18, 12, 16], [12, 13, 16], [16, 13, 17], [13, 15, 17], [17, 15, 22], [15, 55, 22], [22, 55, 46], [55, 45, 46], [22, 73, 17], [73, 72, 17], [17, 72, 16], [72, 71, 16], [16, 71, 19], [71, 74, 19], [19, 74, 20], [74, 75, 20]]]

If anyone can help me or can tell me what this problem is called and how can I search for it I would be appreciated.

[PredatorCZ]

What you are talking is converting stripped indices into a triangle array and back.
Converting stripped triangles to triangles is easy, but it's much harder to do the other way.

Here is a theory behind it: http://www.learnopengles.com/tag/triangle-strips/
And here is a library written in C++ that I use: https://github.com/spoonless/tristripper

Also you didn't wrote, what format are you using to store these values.
int is 32bit, and is never used to store index data, unless its an very old non-standard format.
API's supports int index buffers, however this does not mean it should be used.

[eatrawmeat391]

I sort of solved the problem.
It turns out that Blender sorts the triangles in the right order that I want for converting it back into an integer array
For example:
[0]: 0,1, 2,
[1]: 1,2,3
[2]: 4,2,3,
[3]: 4,6,7
[4]: 6,7,9
I take the first 3 items 0,1,2 into the list
list = [0,1,2]
So
last_f1 = 0
last_f2 = 1
last_f3 = 2
Now for the next items, we will see if it contains at least 2 vertices of the last processed , so
if at least 2 items in (f1,f2,f3) is in (last_f1,last_f2, last_f3)
so 0,1,2 we see 1 = last_f2, 2 = last_f3 so list = [0,1,2,3]
then
last_f1 = 1
last_f2 = 2
last_f3 = 3
...
Keep doing that we get
[0,1,2,3,4] after processing index 2
So the algorithm keeps running in a loop and now the same process but the function will starts at index 3
So the function returns new_int_array, next_index
If there is no more items to read,next_index = -1 and specify the stop condition

So I got
[0,1,2,3,4]
[4,6,7,9]
as output

And about data type, I have been using to python so it is not necessary to define a type for that. But it uses 32bit integer. The game I am working for pack the triangles as integer array , and each integer in the array also comes with 2D UV coordinate. It uses non-standard format for sure but I have solved that problem as well.