- Forum
- General C++ Programming
- 3D Fill Algorithm
3D Fill Algorithm
There needs to be a "Random Questions that don't deserve a thread" section for me I think.
Was playing Antichamber (amazing game, go play it) and couldn't figure out an easy algorithm for creating a 3D paint fill type thing with small cubes the way the game does it. Basically you can create a 'hollow' convex polygon made out of squares on 1 axis and it will fill in the rest for you. Seen here http://www.youtube.com/watch?v=JGEonUjDRwI (45 seconds in).
I don't really plan to program this so can't really show "what I have so far" but my thought process is.
-Start at square you just placed and do a recursive sequence to find if it is a closed shape (Eventually it will get back to square you started at).
-Find which side is the inside of the closed polygon...raycasting I suppose?
-Use another recursive function to find all of the squares inside the shape, but how do you know which axis to use? (You can only create shapes on 1 axis at a time).
Any thoughts on an easy way to accomplish this?
Was playing Antichamber (amazing game, go play it) and couldn't figure out an easy algorithm for creating a 3D paint fill type thing with small cubes the way the game does it. Basically you can create a 'hollow' convex polygon made out of squares on 1 axis and it will fill in the rest for you. Seen here http://www.youtube.com/watch?v=JGEonUjDRwI (45 seconds in).
I don't really plan to program this so can't really show "what I have so far" but my thought process is.
-Start at square you just placed and do a recursive sequence to find if it is a closed shape (Eventually it will get back to square you started at).
-Find which side is the inside of the closed polygon...raycasting I suppose?
-Use another recursive function to find all of the squares inside the shape, but how do you know which axis to use? (You can only create shapes on 1 axis at a time).
Any thoughts on an easy way to accomplish this?
| how do you know which axis to use? |
Here's a solution for the problem in two dimensions:
* Start with a tristate (Empty, Marked, Filled) bitmap. Set everything to the Empty state.
* Let the user change the state of some pixels, only to Empty or Filled.
* Starting from a pixel which the user can't possibly modify, do a simple fill (http://en.wikipedia.org/wiki/Flood_fill ) with the Marked state.
* Change any pixels still in the Empty state to the Filled state.
* Change any pixels in the Marked state to the Empty state.
To extend to 3D, first do
| -Start at square you just placed and do a recursive sequence to find if it is a closed shape (Eventually it will get back to square you started at). |
Right, I understand that on an axis-aligned plane there will always be 1 coordinate that is constant. If the shape is always a rectangle with no extra lines it is fairly easy to solve.
However what happens when you have a shape like this?
http://puu.sh/8jygO.jpg
If I placed a block in that final corner the recursive function would pass as it is a closed shape (on the x-z dimensions, with the y staying constant) but all of those other blocks would be included in the list. Now in this case I can visually see the y coordinate can be ignored so those blocks can be removed but how would the code manage to find that out?
I feel like I am missing something really simple but just can't see it.
However what happens when you have a shape like this?
http://puu.sh/8jygO.jpg
If I placed a block in that final corner the recursive function would pass as it is a closed shape (on the x-z dimensions, with the y staying constant) but all of those other blocks would be included in the list. Now in this case I can visually see the y coordinate can be ignored so those blocks can be removed but how would the code manage to find that out?
I feel like I am missing something really simple but just can't see it.
For example, suppose
where visited contains the pixels visited by the current call stack (pixels are popped when backtracking). If initial == current && visited.size() > 0, then the shape is closed, and visited contains a closed path. chosen_axis lets the function ignore filled pixels outside the plane, since such pixels would never yield a useful result except when right next to initial.
EDIT:
One thing I notice from your screenshot: It's impossible to create a closed shape without corners (a center pixel with two adjacent pixels on non-parallel axes). You can exploit this by keeping track of corners and joined corners (corners where all the pixels in between are filled). If you encounter a set of corners that form a closed shape (this is easier and faster to check than at the pixel level), you can easily find the inside:
1. Stand on any corner and face in any direction. Walk in that direction.
2. Every time you turn right, add 1. Every time you turn left, subtract 1.
3. Once you're back at the start, if you have 4, the inside is to your right. If you have -4, the inside is to your left.
bool is_pixel_of_closed_shape(const pixel &initial, const pixel ¤t, std::vector<pixel *> &visited, const axis &chosen_axis);where visited contains the pixels visited by the current call stack (pixels are popped when backtracking). If initial == current && visited.size() > 0, then the shape is closed, and visited contains a closed path. chosen_axis lets the function ignore filled pixels outside the plane, since such pixels would never yield a useful result except when right next to initial.
EDIT:
One thing I notice from your screenshot: It's impossible to create a closed shape without corners (a center pixel with two adjacent pixels on non-parallel axes). You can exploit this by keeping track of corners and joined corners (corners where all the pixels in between are filled). If you encounter a set of corners that form a closed shape (this is easier and faster to check than at the pixel level), you can easily find the inside:
1. Stand on any corner and face in any direction. Walk in that direction.
2. Every time you turn right, add 1. Every time you turn left, subtract 1.
3. Once you're back at the start, if you have 4, the inside is to your right. If you have -4, the inside is to your left.
Last edited on
Ahhh I think I see (that function was almost exactly what I pictured apart from last parameter).
Was trying too hard to picture the x/y/z location instead of the plane they all sit on.
Just to make sure I understand, when you place a block you would have to initially call that function 3 times (1 for each axis the plane could lay on) correct? Seeing as it has no way to tell which axis to use when it starts.
Was trying too hard to picture the x/y/z location instead of the plane they all sit on.
Just to make sure I understand, when you place a block you would have to initially call that function 3 times (1 for each axis the plane could lay on) correct? Seeing as it has no way to tell which axis to use when it starts.
| Just to make sure I understand, when you place a block you would have to initially call that function 3 times (1 for each axis the plane could lay on) correct? Seeing as it has no way to tell which axis to use when it starts. |
See my edit, also. I found another solution.
That corner idea is interesting, seems like it would save a lot of memory/CPU power (and is probably how the game does it).
I think I understand all of the theory now (hey maybe I will do it for fun some time), thanks for all of the insight! Hopefully my random questions don't annoy forum users too much :P
I think I understand all of the theory now (hey maybe I will do it for fun some time), thanks for all of the insight! Hopefully my random questions don't annoy forum users too much :P
Topic archived. No new replies allowed.