0

I have a triangle with 3 vertices,namely: (x1,y1,z1); (x2,y2,z2) and (x3,y3,z3).

I am using Bresenhams 3D Line algorithm,currently for generating 3D Points between two vertices of the triangle,depending on the resolution size(resSize).

void Bresenham3Algo(float x0, float y0, float z0, float x1, float y1, float z1)
        {
            float dx = Math.Abs(x1 - x0);
            float sx = x0 < x1 ? resSize : -resSize;
            float dy = Math.Abs(y1 - y0);
            float sy = y0 < y1 ? resSize : -resSize;
            float dz = Math.Abs(z1 - z0);
            float sz = z0 < z1 ? resSize : -resSize;
            float dm = Math.Max(dx, Math.Max(dy, dz)), i = dm;
            x1 = y1 = z1 = dm / 2;

            for (; ; )
            {
                Console.WriteLine(x0,y0,z0); //Printing points here
                if (i <= 0) break;
                x1 -= dx; if (x1 < 0) { x1 += dm; x0 += sx; }
                y1 -= dy; if (y1 < 0) { y1 += dm; y0 += sy; }
                z1 -= dz; if (z1 < 0) { z1 += dm; z0 += sz; }
                i -= resSize;
            }
        }

So, As of now,I am calling the above function three times to generate 3D Sampling points on the boundary of the three Triangular edges.

Bresenham3Algo(x1,y1,z1,x2,y2,z2);
Bresenham3Algo(x2,y2,z2,x3,y3,z3);
Bresenham3Algo(x3,y3,z3,x1,y1,z1);

I am finding it difficult to find the internal sampling points lying inside the triangle.

For example,If I have the vertices (0,0,0); (5,0,0) and (3,3,0), With the help of the above function, I find 3D Points on the three triangular edges i.e.

(0,0,0),(1,0,0),(2,0,0),(3,0,0),(4,0,0),(5,0,0) -> first Edge

(3,3,0),(4,1,0),(4,2,0),(5,0,0) ->Second Edge

(0,0,0),(1,1,0),(2,2,0),(3,3,0) -> Third Edge

Now,I need to find the internal 3D Sampling points,lying inside the triangle i.e. (2,1,0) , (3,1,0), (3,2,0)

I would be glad,if someone can help me with this algo.

Thanks in Advance!

Exploring_Programming
  • 81
  • 1
  • 8
  • If it is not strictly necessary for you to use a scanline algorithm, then the *very* straightforward method on [this post](https://math.stackexchange.com/questions/538458/triangle-point-picking-in-3d) might be what you need. – meowgoesthedog Jan 05 '18 at 01:59
  • use the duplicate I linked and add z coordinate. If you want volumetric render than the only difference is that you do not need the Zbuffer `if` condition and instead of `pixel[y][x]=col; depth[y][x]=z;` should use `voxel[z][y][x]=col;` – Spektre Jan 17 '18 at 14:13

1 Answers1

0

Assuming you aren't constrained to a regular grid, you do the following:

  1. Rotate the triangle onto the x-y plane.
  2. Draw and fill the triangle using your favourite algorithm in 2D (e.g. Bresenham).
  3. Add z-values (all zero) to the points drawn
  4. Rotate back to the original orientation.
Adam Brown
  • 1,667
  • 7
  • 9
  • just edited my post..please look at the example,I have written above. I just need something like straightforward sampling inorder to find interior points. – Exploring_Programming Jan 04 '18 at 15:28
  • Again, this will only generally work if your triangle is aligned with one of the 3 axes. Is this guaranteed to be the case? – Adam Brown Jan 04 '18 at 15:56
  • No,In my post,I just gave an example.There may be a case,where my triangle may not align with any of the axes. – Exploring_Programming Jan 04 '18 at 15:58
  • Hi. In your post, your triangle is aligned with the x-y plane (all z-coordinates are zero). – Adam Brown Jan 04 '18 at 16:05
  • Hi,I just gave an example.I may also have a triangle with vertices (3,0,0) ; (0,3,0) and (0,0,3). In that case,please explain some algorithm inorder to generate internal points of a particular resolution – Exploring_Programming Jan 04 '18 at 16:07
  • You can't do this in the general case. From what I understand, you want integer coordinates "inside" your triangle. But that won't work for (3, 0, 0.5) (0, 0, 0.5) (0, 3, 0.75), for instance - there are no z-value integers in the range of the triangle, so any points will be an approximation. even if the vertices are constrained to be integers, there are no choices you can make for intermediate points that aren't an approximation. So again, do you really need to have integer-valued points? – Adam Brown Jan 04 '18 at 16:22
  • Hi,its not about having integer valued points. After finding out the sampling points on any two edges using Bresenhams algorithm,I need to find points inside my triangle too.Do you think,it is possible to join lines between two points (point on one edge and another point on second edge) and generate points inside the triangle? – Exploring_Programming Jan 04 '18 at 20:44
  • Hi @AdamBrown again, I am finding out sampling points on all the three edges of triangle..then,I am finding out the cubes,on which each of these sampling point lie.After finding out these cubes,how can I fill the inside area? I dont want to generate sampling points inside anymore..Please help! – Exploring_Programming Jan 07 '18 at 11:31