# Solved Pyramid block iteration

Discussion in 'Spigot Plugin Development' started by Photon, Jun 14, 2018 at 11:40 PM.

1. ### Photon Supporter

I would like ask for the best ideas/algorithms on how to iterate through all blocks that are inside a 3-dimensional pyramid in order to decrease iterations and optimize a few calculations.

You may assume that
• the base is a rectangle
• (due to the application) the pyramid's base is parallel to one plane of the minecraft world (xz, xy, yz)
• you know the exact locations of all corners (and thus the vectors between them)
• blocks that are only partially inside the pyramid are supposed to be included in the iteration
• the top of the pyramid might be somewhere (in the same world) and is not restricted to any location unless that location implies a volume of 0
~Photon

2. ### NathanWolf

These two points sound a little confusing. The first point implies you want to support uneven (in terms of block boundaries) pyramids, which I think would just end up looking weird.

The second point... I honestly don't understand at all. The top of the pyramid is pretty much determined by the base.. isn't it?

If I were to ignore those two bullet points I could provide an extremely simple solution. Basically find the min/max corners of your base, call them x1,z1 and x2,z2

Code (Text):

Set y to y1 (the y location of your base rectangle)
while x1 != x2 or z1 != z2
Iterate x from x1 to x2
Iterate z from z1 to z2
fill block at x,y,z
Increase y
If x1 != x2, increase x1
If x1 != x2, decrease x2
If z1 != z2, increase z1
If z1 != z2, decrease z2
If I'm not missing something that's the basic algorithm for a pyramid.

3. ### Photon Supporter

Those two points, especially the latter are exactly why I need help with the algorithm. I need to support oblique pyramids, not only right pyramids, so the apex might be anywhere in the world. The only exception to this is if that location of the apex would imply a volume of 0, meaning the apex is in the plane of the rectangle (and thus no 3-dimensional object).

4. ### NathanWolf

Ah, ok, sorry! Well .... sounds hard, good luck!

• Funny x 1
5. ### GreatThane

I don't think most of the people on this platform have a high enough education to replicate what you want, as that would require a significant understanding of three dimensional graphing. However, because of how you're doing this, you can completely remove the "minecraft" element entirely and view each block as a point on a graph. As such, you can broaden your search from just the spigot forums to all of the internet. I'd look into CAD forums and source code if I were you, as they need a deep understanding of these kinds of simulations.

6. ### basicmark

I'm not clear, do you know the location of the apex?

If so this doesn't seem too hard as you can get the vectors between each corner and the apex and work out the "corners" for each layer of the pyramid.

If not then you would need to scan any blocks which _could_ be in a layer, once you've done this for a few layers and you have the "corner" for each layer you should be able to project vectors from each corner and see where they intersect which would be the apex.

7. ### HungryDev

You have the 4 points of the rectangle of the pyramid and can get get higest points by getting the middle location of the rectangle.
Then use middle.getWorld().getHigestPointAt(middle)
Then you have the higest block of the pyramid.

You can take 4 points of each lower rectancle of each cube that is in the beam of the pyramid and create a vector that goes straigth up using the upper points. Then you see if that vector goes through only 1 triangle or rectangle. If so, then it is inside the pyramid, if it goes through none or through both, then it is outside. You can look ray tracing up, since it is very similar.

This might also be useful: https://stackoverflow.com/questions...point-inside-convex-polyhedron-square-pyramid

8. ### basicmark

That doesn't work for oblique pyramids as their apex is not in the middle.

9. ### Esmorall

One way could be by getting the blocks from one surface of the pyramid, and then the blocks from the opposite surface. once having both surfaces, the fact that the base is rectangular will allow counting the blocks only in one direction, you can count one by one adding a block in the direction until it coincides with the opposite surface. I am sorry for my bad english.

10. ### BillyGalbreath

I would just make a BlockIterator from the top point to each point of the base and add each iteration to a Set (or any Collection that doesnt allow duplicates). Not the most efficient thing in the world, but it's the easiest implementation I can think of right now.

And by points of the base I mean all points, not just the corners. So, if you have a 5x5 square base, you will have 25 BlockIterators. etc

11. ### Photon Supporter

Thanks for all the input so far.
I think I should share my current approach:

As the base of the rectangle is parallel to a plane I can use this plane to break the pyramid down into parts of equal length divided by a parallel plane.
The distance between two of these parallel planes shall be referenced as a length unit (LE).

Now I can use a bit of vector maths to get the length of a side of the inner rectangle after one LE from the peak:

edgeLength = 1 LE * (tan(a + b) - tan(b))

with a being the angle between the two vectors of the pyramid defining a side of it and b being the angle between a vector orthogonal to the base plane and the vector of this side with a smaller angle to that orthogonal vector.
As this is a 2-dimensional approach you need to do this two times to get both side lengths of the inner rectangle after one LE.

Due to the intercept theorem that is valid in this problem due to the parallel planes I can now use the proportions that I have just calculated to get fixed iteration boundaries which are proportional to the input LEs and thus only need to do these trigonometric calculations once (this can also be seen in the formula above as (tan(a + b) - tan(b)) is a constant, which results in x LE * c, c element of R => edgeLength ~ x)

I will mark this as solved for now as I think this algorithm provides both good performance and a certain simplicity of the maths behind it.
Feel free to share your thoughts if you think you have any improvements!

#11
Last edited: Jun 15, 2018 at 7:14 PM