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:

• Ellipsoids when x != y
  • Example when y > x http://postimage.org/image/gslvykrgd/
  • The same thing happens when x > y only flipped

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.

• java
• algorithm
• math

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.