0

I have a Triangle,with vertices (x1,y1,z1); (x2,y2,z2), (x3,y3,z3). Now,I find the bounding box of my triangle in the following way:

->Loop through all the vertices of my triangle and find xmin, xmax,ymin, ymax and also zmin, zmax.

->Now,my bounding box will be a cube of length = Maximum(xmax-xmin, ymax-ymin,zmax-zmin).

I now discretize my whole bounding box into small grids with some resolution(h). For example,if my bounding box is of length 10,I have 1000(10*10*10) small cubes(grids) of size 1. Now,I want to find some sampling points inside my triangle,such that inside region of my triangle is completely filled(without any voids) with grids(small cubes).

I would be really glad,if someone can explain an efficient algorithm.

Thanks in Advance.

Exploring_Programming
  • 81
  • 1
  • 8
  • This sounds for me as if you are looking for something like [Bresenham Algorithm](https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm) but extended to 3D. – Scheff's Cat Jan 13 '18 at 12:57
  • @Scheff: but,Bresenham 3D Algorithm finds intermediate points between any two points inorder to fit cubes of a particular resolution. How do I that to find internal sampling points?? – Exploring_Programming Jan 13 '18 at 12:59
  • May be, I didn't understand your question. For me, it sounds like you want to resample the triangle by something like [Voxel](https://en.wikipedia.org/wiki/Voxel)s. Hence, my idea to "spy" in graphics rasterization and try to extend to 3d. Filling the triangle (in 2D) is described e.g. here: [Software Rasterization Algorithms for Filling Triangles](http://www.sunshine2k.de/coding/java/TriangleRasterization/TriangleRasterization.html) – Scheff's Cat Jan 13 '18 at 13:04
  • @Scheff: Yes,I had a look into the link,which you have shared. But,I am completely clueless,for extending it to 3D.Could you please let me know regarding this. – Exploring_Programming Jan 13 '18 at 13:07
  • I guess combining "Bresenham" and "Voxel" is a good start for research. (There were already guys who did it.) :-) I googled "voxel bresenham" and found this (as first hit): [SO: Walk a line between two points in a 3D voxel space visiting all cells](https://stackoverflow.com/q/16505905/7478597). – Scheff's Cat Jan 13 '18 at 13:10
  • @Scheff,thanks for that. I still have many queries. Say,for suppose ,I use the above algorithm(the one given in the link). Should I apply that algorithm first to my edges like, ApplyAlgrithm(edge1,edge2) and ApplyAlgorithm(edge1,edge3). Then I get some intermediate 3D Points.I can then loop through each of these 3D Point and find out the voxel in which the 3D Point lies.This will fill all my boundary voxels. What would be the approach for filling inside the triangular region?? – Exploring_Programming Jan 13 '18 at 13:20
  • Yepp, something like this I had in mind. I wrote down but then I realized you probably may get voxel holes and deleted the text. Hence my suggestions for research: Without deeper knowledge I'm sure there must be ready code for this somewhere in the Web. I heard about voxel models the first time 20 years ago... (E.g. medical visualization is using them for a very long time.) – Scheff's Cat Jan 13 '18 at 13:25
  • @Scheff: I would be really glad,if you can provide any link, with already available code. I had been searching it from past 3 weeks,but all I could find is only a "Simple Collision Box test,which is not at all effective algorithm". – Exploring_Programming Jan 13 '18 at 13:30
  • Do you want to do voxel rendering or collision detection? For the latter, one AABB is sufficient for the first rough test. The fine test is done on triangle directly. What should be tested against the triangle? Another triangle? A point? A sphere? The intersection of triangles is usally done by 1.) check whether intersection with _plane_ of triangle. 2.) If there is intersection then check whether intersection point is inside of triangle. – Scheff's Cat Jan 13 '18 at 13:40
  • @Scheff: No,I want to do voxel rendering. I would be glad,if you can help me with this. – Exploring_Programming Jan 13 '18 at 13:42
  • Unfortunately I can't - no experience. Just heard about it. – Scheff's Cat Jan 13 '18 at 13:43
  • I found this code https://de.mathworks.com/matlabcentral/fileexchange/27390-mesh-voxelisation?requestedDomain=true&nocookie=true. I would be really glad,if you can go through this link once. – Exploring_Programming Jan 13 '18 at 13:46
  • Heavy stuff. I tried google "voxel bresenham triangle". This brings better results. I added "c++" which might help. Btw. in the first ten hits, somebody in gamedev described exactly the problem I was afraid of. :-) – Scheff's Cat Jan 13 '18 at 13:54
  • @Scheff; so,u mean to say,there is no code which is already available? – Exploring_Programming Jan 13 '18 at 14:02
  • I admitted that I don't know rather anything about your problem. Just googled. Scanned (for key words). Googled again. and so on... This is something you really must learn if you want to become a software developer. My last hint: google "github triangle voxel marching cube c++". A general note: Often I googled and learned how to solve a specific problem. Sometimes I googled and had to admit that I'm not _able_ to solve the problem due to lacking too much basic knowledge. This hurts but everything you can do: put this aside and do something else you _can_ solve. Imagine what we did before... – Scheff's Cat Jan 13 '18 at 14:18
  • ...google was invented. Imagine what we did before even the Web and search engines were invented. (We went to the library to look for a book or a paper.) Today, with _everything_ in the Web and google - it's sooo easy. Even if you are not willing to pay for contents - there is so much open source software. Just find it... – Scheff's Cat Jan 13 '18 at 14:20

0 Answers0