0

I have voxel maps of 1024 x 1024 x 1024, over a billion voxels, and i am traversing them from XYZ axes to find the outline of a scan within them.

Every time I hit a voxel boundary, I want to create a quad reference for the face encountered, which consists of 4 vertices and and a triangle/quad reference index.

Because the result is 50-60 million quads, I don't think that I can write arrays to memory and merge vertices using loops, it would be too much memory and I can use Meshlab to delete duplicate vertices.

So it's simple to just write 4 vertices and a reference to them every time i find I traverse a boundary.

A/ Can I use another methodology?

B/ What file format allows me to filestream lines like:

FORMAT= .EASY

vtxA: (2.0 , 5.0, 2,0)    nml(-1,0,0)
vtxB: (2.0 , 6.0, 2,0)    nml(-1,0,0)
vtxC: (2.0 , 5.0, 3,0)    nml(-1,0,0)
vtxD: (2.0 , 6.0, 3,0)    nml(-1,0,0)
QUAD: ABCD

vtxC: (1002.0 , 5.0, 2,0)    nml(1,0,0)
vtxD: (1002.0 , 6.0, 2,0)    nml(1,0,0)
vtxE: (1002.0 , 5.0, 3,0)    nml(1,0,0)
vtxF: (1002.0 , 6.0, 3,0)    nml(1,0,0)
QUAD: CDEF
bandybabboon
  • 2,210
  • 1
  • 23
  • 33
  • why not doing your mesh from slices. you need to remember last and actual slice circumference polygons. When slice `i-th` polygon done then find the matches in `(i-1)-th` polygon to form your QUADs and add them to your mesh. You can store vertexes and indices in separate files and when whole mesh finished merge/pack them and save into 3D format you are supporting ... Possibly better would be use TRIANGLE_STRIP per slice instead of QUADs for this purpose – Spektre Jan 17 '17 at 20:13
  • Hi Specktre, that's a very good idea, i was leaning towards that logical outcome it's definitely simpler. – bandybabboon Jan 18 '17 at 06:02
  • Take a look at related QA [How can I connect two parallel 2d polygons to create a seamless 3d mesh?](http://stackoverflow.com/q/25070206/2521214) your slices should be very similar so the solution will be probably much simpler then that. – Spektre Jan 18 '17 at 08:32

3 Answers3

0

I've been researching obj,ply and stl file formats, the easiest one to write quads straight to disk seems to be stl even though it's triangles, because you can write stram write to disk, no need for arrays, good for a fast fix at the lab.

here is a cube example:

solid cube
  facet normal 0 0 0
    outer loop
      vertex 0 0 0
      vertex 0 1 0
      vertex 1 1 0
    endloop
  endfacet
  facet normal 0 0 0
    outer loop
      vertex 0 0 0
      vertex 1 1 0
      vertex 1 0 0
    endloop
  endfacet
  facet normal 0 0 0
    outer loop
      vertex 0 0 0
      vertex 0 0 1
      vertex 0 1 1
    endloop
  endfacet
  facet normal 0 0 0
    outer loop
      vertex 0 0 0
      vertex 0 1 1
      vertex 0 1 0
    endloop
  endfacet
  facet normal 0 0 0
    outer loop
      vertex 0 0 0
      vertex 1 0 0
      vertex 1 0 1
    endloop
  endfacet
  facet normal 0 0 0
    outer loop
      vertex 0 0 0
      vertex 1 0 1
      vertex 0 0 1
    endloop
  endfacet
  facet normal 0 0 0
    outer loop
      vertex 0 0 1
      vertex 1 0 1
      vertex 1 1 1
    endloop
  endfacet
  facet normal 0 0 0
    outer loop
      vertex 0 0 1
      vertex 1 1 1
      vertex 0 1 1
    endloop
  endfacet
  facet normal 0 0 0
    outer loop
      vertex 1 0 0
      vertex 1 1 0
      vertex 1 1 1
    endloop
  endfacet
  facet normal 0 0 0
    outer loop
      vertex 1 0 0
      vertex 1 1 1
      vertex 1 0 1
    endloop
  endfacet
  facet normal 0 0 0
    outer loop
      vertex 0 1 0
      vertex 0 1 1
      vertex 1 1 1
    endloop
  endfacet
  facet normal 0 0 0
    outer loop
      vertex 0 1 0
      vertex 1 1 1
      vertex 1 1 0
    endloop
  endfacet
endsolid cube

c type code to write above code:

function Xquad( X:float , Y:float , Z:float , cnt:float){

//based on stl cube

  qstr+="facet normal " +"0 0 0"+ "\n"+
    "outer loop\n"+
      "vertex "+st(X)  +" "+ st(Y)   +" "+  st(Z)+   "\n"+
      "vertex "+st(X)  +" "+ st(Y+1) +" "+  st(Z)+   "\n"+
      "vertex "+st(X)  +" "+ st(Y+1) +" "+  st(Z+1)+ "\n"+
    "endloop\n" +
 "endfacet\n"+
  "facet normal " +"0 0 0"+ "\n"+
    "outer loop\n"+
      "vertex "+st(X)  +" "+   st(Y)  +" "+  st(Z)+   "\n"+
      "vertex "+st(X)  +" "+   st(Y+1)+" "+  st(Z+1)+ "\n"+
      "vertex "+st(X)  +" "+   st(Y)  +" "+  st(Z+1)+ "\n"+
    "endloop\n"+
  "endfacet\n";

}
function Yquad( X:float , Y:float , Z:float , cnt:float){

  qstr+="facet normal " +"0 0 0"+ "\n"+
    "outer loop\n"+
      "vertex "+st(X)  +" "+ st(Y) +" "+  st(Z)+   "\n"+
      "vertex "+st(X+1)+" "+ st(Y) +" "+  st(Z)+   "\n"+
      "vertex "+st(X+1)+" "+ st(Y) +" "+  st(Z+1)+ "\n"+
    "endloop\n" +
 "endfacet\n"+
  "facet normal " +"0 0 0"+ "\n"+
    "outer loop\n"+
      "vertex "+st(X)  +" "+ st(Y) +" "+  st(Z)+   "\n"+
      "vertex "+st(X+1)+" "+ st(Y) +" "+  st(Z+1)+ "\n"+
      "vertex "+st(X)  +" "+ st(Y) +" "+  st(Z+1)+ "\n"+
    "endloop\n"+
  "endfacet\n";

}
function Zquad( X:float , Y:float , Z:float , cnt:float){

  qstr+="facet normal " +"0 0 0"+ "\n"+
    "outer loop\n"+
      "vertex "+st(X)  +" "+ st(Y)   +" "+  st(Z)+ "\n"+
      "vertex "+st(X)  +" "+ st(Y+1) +" "+  st(Z)+ "\n"+
      "vertex "+st(X+1)+" "+ st(Y+1) +" "+  st(Z)+ "\n"+
    "endloop\n" +
 "endfacet\n"+
  "facet normal " +"0 0 0"+ "\n"+
    "outer loop\n"+
      "vertex "+st(X)    +" "+ st(Y)   +" "+  st(Z)+   "\n"+
      "vertex "+st(X+1)  +" "+ st(Y+1) +" "+  st(Z)+ "\n"+
      "vertex "+st(X+1)  +" "+ st(Y)   +" "+  st(Z)+ "\n"+
    "endloop\n"+
  "endfacet\n";

}
bandybabboon
  • 2,210
  • 1
  • 23
  • 33
  • 1
    may be winding rule... if by `fn` you mean the last `f 5 1 4 8` try to change it to `f 8 4 1 5` if it helps ... btw not sure if all wavefront obj loaders support mixed `v` and `f` lines but you can always post-process to separate the two when all is finished ... but I would create two files from the begining one for `f` and one for `v` and when whole mesh done merge the two together – Spektre Jan 18 '17 at 11:10
0

I would use binary STL, two tringles per quad. More info here: https://en.m.wikipedia.org/wiki/STL_(file_format)

abenci
  • 8,422
  • 19
  • 69
  • 134
  • STL does not use indices making the huge mesh even bigger ... on the other hand binary STL version could load faster (if not too big of coarse) – Spektre Jan 19 '17 at 09:03
0

Probably it is possible to store needed information. For your approach it is only needed to store info for vertices used in some previous quad. It is not needed to store quads in memory since they can be write in a file.

There are 1025x1025x1025 (~= 1G) vertices in a grid, and vertex can be identified with triplet of grid coordinates (x, y, z), where 0 <= x, y, z <= 1024. If vertex is used than it gets vertex index in array of vertices (which is written to a file.)

Standard ways to store info are:

  • map that maps vertex coordinate (x, y, z) to vertex index. Map pair requires 6 bytes of memory for coordinate (3 x int16), and 4 bytes for vertex index (<=1G). Map requires 'few pointers' per one mapping for storage. I think that map can be implemented to use less than 30 bytes for each vertex which is < 2GB memory for your need.

  • 3D array of vertex grid size (1025^3) which stores vertex index for all possible vertices. If vertex was used than it is real vertex index, and -1 (or some other flag) if vertex wasn't used. Simpler implementation than a map. Requires ~4GB memory, which shouldn't be a problem.

Ante
  • 5,350
  • 6
  • 23
  • 46