1

I have a grid map in 3D. and created a triangle with three vertex points. I want to know which of the grids in the grid map the triangle intersects with. A 2D example of this would be:

2D Example

But with a square instead. As you can see, the grids where the square intercepts turn red. I want the same, but in a 3D grid map and using triangles. It would look something like this: enter image description here

Bredosen
  • 46
  • 4
  • 1
    What have you tried so far? Using a search engine you should be able to determine which calculations you need to run. Hint: There are a number of ways to do this, but you could break it down into a simple line problem and check if each edge of the triangle intersects each grid square then fill in the middle once you know the boundary of the intersect. For something a bit more optimized you could just check the 3 points of the triangle and fill in the between grid squares, but it all depends on how you represent the data in code and how you need to use it to work out what is most efficient. – sorifiend Jul 05 '22 at 21:45
  • @sorifiend I have no code since I do not know where to begin, I have the grid map and the triangle, but the calculation for finding the grids the triangle interest does not exist. I have tried to google it all day, but I cannot find a solution for it (or I do not know how to ask the question probably); now I have thought about outlining and then filling, but how would I go about filling a triangle plane in a 3d space? I know how to flood fill in a 2D space, but not in 3D – Bredosen Jul 05 '22 at 22:12
  • add googling "filling a 2D triangle in a 3D grid" or "filling a 2D polygon in a 3D grid" does not give many valuable results. – Bredosen Jul 05 '22 at 22:28
  • Without code we can only make suggestions like the one above. Do you know how to draw shapes and lines in Java? Do you know how to calculate an intersection between two lines? What library are you using (if any) to draw the geometry? How are you storing the shape/triangle data? There is no one size fits calculation that will do all this for you. Break the problem down into smaller steps, create some helper methods that can do things like finding line intersections, and how to check if a line passes through a 3d space, with those two methods alone you will be half way there. – sorifiend Jul 05 '22 at 22:30
  • @sorifiend I am not using any libraries and do not want to display anything; I only have the grid map as an int array (0 = nothing, 1 = triangle). Also, I have the triangle as three vertexes. Each vertex has an x, y, and z float value. – Bredosen Jul 05 '22 at 22:37
  • 1
    see [convex polygon rasterization](https://stackoverflow.com/a/19078088/2521214) and [DDA with subpixel precision](https://stackoverflow.com/a/24682318/2521214) – Spektre Jul 06 '22 at 06:05
  • I will look at that, that you @Spektre – Bredosen Jul 06 '22 at 08:09

0 Answers0