Bresenham 3d Ellipsoid problems

Go To StackoverFlow.com

1

I'm making an ellipsoid out of voxels, and I have an implementation, but it's not working correctly, for the past few hours I've been trying things with no success.

Here's how it works:

  • It draws 2D ellipses down the Z axis using the Bresenham circle algorithm
  • It calculates the coordinates of a circle going forward and one going side to side
  • It uses those coordinates as radii for X and Y

Here's what works:

  • Spheres are perfect
  • Ellipsoids are perfect when
    • z > x and z > y
    • x == y

Here's what doesn't:

I'm guessing its because I'm drawing the slices from center to front every time, but I don't know. Below is my implementation, it's a mess. I quickly cleaned it up a bit so it's understandable to some degree. Also I'm saving optimisations for later, I just want it working now.

I won't show my implementation of the circle algorithm itself, because I KNOW that it works and it would just make this question longer. So I'll explain the two functions for it instead.

private List<Integer> getSlice(int rx, int ry) gets the raw result from a run of the Bresenham circle algorithm, no symmetry needed. It returns the result as a list of the x, y results in that order.

public void generateEllipse(int z, int cx, int cy, int cz, int rx, int ry) generates an ellipse with the given information and plots down the coordinates using symmetry, these will be rendered on the screen.

ArrayList<Integer> s = getSlice(rz, rx);
ArrayList<Integer> s2 = getSlice(rz, ry);

int cap = Math.max(s2.size(), s.size());

while (s.size() > 1)
{
    int x = 0;
    int z = 0;
    int z2 = 0;
    int y2 = 0;

    int i = cap - 2;

    if (s.size() > i)
    {
        z = s.get(i);
        x = s.get(i + 1);

        s.remove(i + 1);
        s.remove(i);
    }

    if (s2.size() > i)
    {
        z2 = s2.get(i);
        y2 = s2.get(i + 1);

        s2.remove(i + 1);
        s2.remove(i);
    }

    if (x != 0 && y2 != 0)
        generateEllipse(z, cx, cy, cz, x, y2);

    cap = Math.max(s2.size(), s.size());

I asked a similar question a week or two back (yeah I've been having problems for that long :() and got an answer, I implemented it and it worked, but I wasn't satisfied, I want to avoid floating point numbers all together. See 3D Ellipsoid out of discrete units.

With that I was having problems with rounding off the numbers and getting uneven slices, so spheres were impossible. Ironically, now spheres are the only thing possible (other than front to back ellipses).

EDIT:

I got x > y working by adding

else if (y2 < x && ry - y2 != 0)
    generateEllipse(z, cx, cy, cz, x, ry - y2);

and || r - y2 == 0 to the first test at the bottom.

I'm not too sure why that worked, I'm figuring that out now. But I'm still having problems with y > x. Anyone?

EDIT2:

Now that I look at it, it's different than the y = x ellipsoid, back to the drawing board.

EDIT3:

Last night I was thinking about this and I think I've figured it out, this isn't an answer to my own question, but I guess pointing out what I'm seeing to be wrong. I'm testing for the first list and drawing coordinates decrementally from the size of the largest list.

That's badness because the two lists aren't guaranteed equal lengths, that's a failure on my part for trying to rush an algorithm.

In the picture, you can't see, but the little ellipse is actually a few blocks away from the big ellipse. This is caused when from ellipses not being drawn, which is caused by lists not having data. The actual little ellipse big ellipse is caused because the algorithm draws two octants, both of which are stored into the list from getSlice(...).

So how can I fix this problem? I haven't implemented anything yet and probably won't for a while (it's early) but this is what my brain cranked out. Again, this is not an answer to the question, just thoughts.

I iterate for while(!s.isEmpty()) and define two new values outside the loop: incX = s.size and incY = s1.size I test to see if their z values match, if not, then I correct it. I'm thinking I'll get the values, test the largest list and if they don't match then decrement the inc value of the smallest list by two and get the old values.

I test for !s.isEmpty() because the two lists will be empty at the same time. Also drawing ellipses, I'll use whichever one z value, because, again, they both should be equal.

If that's wrong, then I guess I have this document I found to go through: http://www.cs.sunysb.edu/vislab/wordpress/pdf/398.pdf.

2012-04-04 17:08
by SpaceFace


2

Thank you for anyone who viewed this (even though I didn't get any replies :(), I'm setting this answer because the problem is solved, the code is as follows:

    ArrayList<Integer> s = getSlice(rz, rx);
    ArrayList<Integer> s2 = getSlice(rz, ry);

    boolean yMax = Math.max(s2.size(), s.size()) == s2.size();

    int decX = s.size() - 1;
    int decY = s2.size() - 1;

    boolean done = false;

    while (!done)
    {

        int x = 0;
        int z = 0;
        int z2 = 0;
        int y = 0;

        y = s2.get(decY--);
        z2 = s2.get(decY--);

        x = s.get(decX--);
        z = s.get(decX--);

        if (z != z2)
        {
            if (yMax)
            {
                decX += 2;
                x = s.get(decX);

                s2.remove(decY + 2);
                s2.remove(decY + 1);    
            }
            else
            {
                decY += 2;
                y = s2.get(decY);

                s.remove(decX + 2);
                s.remove(decX + 1); 
            }

            z = z < z2 ? z : z2;
        }
        else
        {
            s.remove(decX + 2);
            s.remove(decX + 1);             

            s2.remove(decY + 2);
            s2.remove(decY + 1);    
        }

        if (y != 0 && x != 0)
            generateEllipse(z, cx, cy, cz, x, y);

        done = yMax ? s2.isEmpty() : s.isEmpty();
    }

All that needs to be done now is optimisation. I'm still going to read that paper, it covers other topics that are interesting and useful for my program :).

The issue was that I was not accounting for the different sizes of each list, if a curve is less steep than the other it will have more coordinates. Z will always be the same when rx == ry. This allowed me to draw spheres and forward to back ellipsoids.

When they are not the same the z will change because the curve will be faster / slower. When this happened while I was testing for the first list it would ignore those because iteration would stop before it got to them.

The big ellipse, little ellipse was caused because they were drawn backwards, so the outer octant was drawn first which happens to have less total values.

In the near future I will put up a much more detailed answer and a much more elegant implementation. I'm just putting up this answer to let any passersby know that the problem is resolved. I want no one to ever go through the frustration I did trying to figure this whole thing out! It's amazing how the most difficult problems are caused by the silliest things.

2012-04-05 14:26
by SpaceFace
Quick note, do your ellipsoid's voxels need to be aligned to a 3D grid? You seem to be implying this limitation - Michael Slade 2012-04-05 19:17
@MichaelSlade Yes, there is a grid. This is visible in my picture. Also on a side note, I wanted to mention the test for done only exists because unexpectedly the lists are not equal when one is done. I'm sure it's a simple fix, but I noticed this is a problem when rz is larger than either rx or ry and rx != ry. I'll do more playing around, I think the fix is simple - SpaceFace 2012-04-05 19:27
Prupel - I've been trying to find a way to get in contact with you. You seem to have done a whole load of awesome work on this for minecraft and I'd like to use your algorithms in an open source mod.. Get in contact with me if you think you wouldn't mind me if you wouldn't mind sharing these with me. Cheers man! espernet irc: mike - Mikee 2013-07-20 23:06
Ads