Jump to content
  • Advertisement
Sign in to follow this  
andy82

Rotating ellipse around arbitrary point

This topic is 3254 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I'm trying to rotate an ellipse using an arbitrary point inside the bounding rectangle of the ellipse as the anchor point of the rotation. The anchor point shall range from 0.0/0.0 (i.e. top left corner) to 1.0/1.0 (bottom right corner). The anchor point for rotating around the center would thus be 0.5/0.5. Specifically, I'm trying to adapt some code from Intel's OpenCV library to support this feature. Currently, the ellipse routine in OpenCV only supports rotation around the center of the ellipse, i.e. 0.5/0.5 Here's an excerpt of the code from OpenCV that generates a rotated ellipse as a series of poly lines. The rotation is applied via a 2x2 transformation matrix but it always rotates around the center.
#define  XY_SHIFT  16
#define  XY_ONE    (1 << XY_SHIFT)

// inputs:
// p: array to receive poly vertices
// cx: x center point of ellipse
// cy: y center point of ellipse
// size_a: radius a
// size_b: radius b
// m: 2x2 matrix to apply to vertices
// arc_start: starting angle
// arc_end: ending angle

int ellipse2poly(struct point *p, double cx, double cy, double size_a, double size_b, struct matrix *m, int arc_start, int arc_end, int delta)
{
    	struct point *p_origin = p;
    	int i;

    	for(i = arc_start; i < arc_end + delta; i += delta) {

		double x, y;
		int angle = i;

		if(angle > arc_end) angle = arc_end;
	        if(angle < 0) angle += 360;

		x = (size_a * costab[angle]); 
		y = (size_b * -sintab[angle]); 
			
		p->x = (lrint(cx + x * m->sx - y * m->ry) >> XY_SHIFT);
		p->y = (lrint(cy - x * -m->rx - y * m->sy) >> XY_SHIFT);		
				
		p += i == arc_start || p->x != p[-1].x || p->y != p[-1].y;
	}

    	i = (int)(p - p_origin);
    	for( ; i < 2; i++ ) p_origin = p_origin[i-1];
		
    	return i;
}

int arc(struct point *p, double cx, double cy, double rx, double ry, struct matrix *m)
{
	int delta;

	cx <<= XY_SHIFT;
	cy <<= XY_SHIFT;
	rx <<= XY_SHIFT;
	ry <<= XY_SHIFT;

    	delta = (max(rx,ry)+(XY_ONE>>1))>>XY_SHIFT;
    	delta = delta < 3 ? 90 : delta < 10 ? 30 : delta < 15 ? 18 : 5;

    	return ellipse2poly(p, cx, cy, rx, ry, m, 0, 360, delta);
}
Does anyone have an idea how to tweak this code to allow rotation around a different anchor point than the center point? I already tried several things but so far I haven't got it right so any help is very appreciated. Thanks, Andy

Share this post


Link to post
Share on other sites
Advertisement
The standard way to rotate about a point P. If X is the input point, subtract P so that it becomes the new "origin". The input point becomes X-P. Now rotate about the origin. The input point becomes R*(X-P), where R is your rotation matrix. Translate back to the original coordinates by adding P. The output point of the operation is Y = R*(X-P) + P. You would apply this transformation to all the vertices of the polygon that approximates the ellipse.

Share this post


Link to post
Share on other sites
Thanks, I know of course how to apply transformations to polygons with arbitrary anchor points but it doesn't help in this case because if transformation is applied _after_ generating the ellipse poly it just doesn't look as good as when it is applied during the routine I posted.

For example: Imagine I want to rotate the ellipse by an arbitrary degrees. If I do this with the following call:

	
m.sx = cos(angle);
m.rx = sin(angle);
m.ry = -sin(angle);
m.sy = cos(angle);

arc(p, cx, cy, 150, 100, &m);


Then the result looks much better than doing the following:

	
// identity matrix
m.sx = 1;
m.rx = 0;
m.ry = 0;
m.sy = 1;

// create an untransformed ellipse
arc(p, cx, cy, 150, 100, &m);

// and now apply the transformation afterwards
transformpoly(p, ...);


That's the problem here. Of course, I could generate an untransformed polygon and then apply the transformation using an arbitrary anchor point afterwards. That's very easy but it just doesn't look as good as when the transformation is applied _directly_ by ellipse2poly(). But ellipse2poly() always assumes 0.5/0.5 as the anchor point for the transformation. That's why I'm searching for a way to adapt ellipse2poly() to support any arbitrary anchor point ranging from 0.0 to 1.0. I've already tried several things but I don't seem to get it right :(

Share this post


Link to post
Share on other sites
The argument comes down to modifying the two lines of code that set p->x and p->y (in your original post). Skipping the conversion to integer,

x = a * cos(theta);
y = -b * sin(theta);
p->x = cx + x * m->sx - y * m->ry;
p->y = cy - x * -m->rx - y * m->sy;


I use a instead of size_a, b instead of size_b, cos(theta) instead of costab[angle], and sin(theta) instead of sintab[angle]. Given your examples with matrix m, the equations for p->x and p->y does not look right. Did you modify the code? To support your examples, I will use

p->x = cx + x * m->sx + y * m->ry
p->y = cy + x * m->rx + y * m->sy



An axis-aligned ellipse centered at the origin is (x/a)^2 + (y/b)^2 = 1. I believe the code generates the polygon by sampling x and y. Specifically, for angles theta in [0,2*pi], the samples are generated by x = a*cos(theta) and y = -b*sin(theta). Why the code writers chose -b*sin(theta) instead of b*sin(theta) is anyone's guess. For an increasing sequence of theta, you get a polyline that approximates the ellipse. The more samples, the better the approximation. The code guarantees you connect the sample from the last angle to the sample for the first angle (so you get a polygon). In this scenario, m->sx = 1, m->rx = 0, m->sy = 0, and m->ry = 1.

Now consider a rotation of the axis-aligned ellipse about the origin by an angle phi; that is, m->sx = cos(phi), m->rx = sin(phi), m->ry = -sin(phi), and m->sy = cos(phi). The transformation is px = cx + x*cos(phi) - y*sin(phi) and py = cy + x*sin(phi) + y*cos(phi). This is an ellipse whose axes have directions (cos(phi),sin(phi)) and (-sin(phi),cos(phi)) and whose center is (cx,cy). The (x,y) values are sampled as before using x = a*cos(theta) and y = -b*sin(theta).

I believe what you want is a rotation of the axis-aligned ellipse about a point other than the origin, and then you want the origin translated to (cx,cy). Let (ax,ay) be the point about which the rotation should occur. The transformation to rotate is x' = ax + (x-ax)*cos(phi) - (y-ay)*sin(phi) and y' = ay + (x-ax)*sin(phi) + (y-ay)*cos(phi). Additionally, you want to translate the origin (not the ellipse center) to (cx,cy), so you get px = (cx+ax) + (x-ax)*cos(phi) - (y-ay)*sin(phi) and py = (cy+ay) + (x-ax)*sin(phi) + (y-ay)*cos(phi).

Share this post


Link to post
Share on other sites
Yes, I did some modifications to the original code because I made some changes concerning the sine/cosine lookup table (OpenCV used a statically linked table while I want to use a table that is created at runtime). But AFAICS, I've not broken anything because it has always worked fine... nevertheless, here's the original version:


for(i = arc_start; i < arc_end + delta; i += delta) {

double x, y;

angle = i;

if(angle > arc_end) angle = arc_end;
if(angle < 0) angle += 360;

x = size_a * icvSinTable[450-angle];
y = size_b * icvSinTable[angle];
p->x = (lrint(cx + x * alpha - y * beta) >> XY_SHIFT);
p->y = (lrint(cy - x * beta - y * alpha) >> XY_SHIFT);
p += i == arc_start || p->x != p[-1].x || p->y != p[-1].y;
}


Thanks for your suggestions but unfortunately, it still doesn't work. Even rotating round the center (i.e. let ax:=cx and ay:=cy) doesn't work. Here's how I adapted your suggestions:


// let rotate center x/y be between 0 and 1
// size_a/b got already left-shifted by XY_SHIFT so this is okay
double ax = (size_a * 2 * rotate_center_x);
double ay = (size_b * 2 * rotate_center_y);

for(i = arc_start; i < arc_end + delta; i += delta) {

double x, y;
int angle = i;

if(angle > arc_end) angle = arc_end;
if(angle < 0) angle += 360;

x = (size_a * costab[angle]);
y = (-size_b * sintab[angle]);

p->x = lrint((cx+ax) + (x-ax) * m->sx - (y-ay) * m->ry) >> XY_SHIFT;
p->y = lrint((cy+ay) + (x-ax) * m->rx + (y-ay) * m->sy) >> XY_SHIFT;

p += i == arc_start || p->x != p[-1].x || p->y != p[-1].y;
}


Maybe I should add that cx/cy shall always be the center of the ellipse, i.e. cx is always equal to size_a and cy is always equal to size_b. The only thing that varies is the ax & ay points which shall specify the center point for the transformation.

Share this post


Link to post
Share on other sites
Quote:
Original post by andy82
Yes, I did some modifications to the original code because I made some changes concerning the sine/cosine lookup table (OpenCV used a statically linked table while I want to use a table that is created at runtime). But AFAICS, I've not broken anything because it has always worked fine.


Using the identity sin(450 - angle) = cos(angle), the OpenCV table lookups lead to x = size_a*cos(angle) and y = size_b*sin(angle). Your modified code has y = -size_b*sin(angle), which is already a difference from the original.

Also, the OpenCV code has the following (ignoring the lrint, whatever that is, and the shift), p->x = cx + x*alpha - y*beta and p->y = cy - x*beta - y*alpha. The 2x2 matrix is {{alpha,-beta},{-beta,-alpha}} and has determinant -(alpha*alpha+beta*beta), which is negative. If you choose alpha = cos(phi) and beta = sin(phi), you get a reflection, not a rotation. You made the replacement p->x = cx + x*m->sx - y*m->ry and p->y = cy - x*-m->rx - y*m->sy (notice the minus sign on m->rx after the multiplication). In a post you mention m->sx = cos(angle), m->rx = sin(angle), m->ry = -sin(angle), and m->sy = cos(angle). Your 2x2 matrix is {{cos(angle),sin(angle)},{sin(angle),-cos(angle)}}, which is also a reflection (not a rotation). So there really are some issues about what both the OpenCV code and your modifications are doing. To make changes to code that supposedly "rotates" but apparently "reflects" means you need to figure out "why" first before formulating the changes.


// let rotate center x/y be between 0 and 1
// size_a/b got already left-shifted by XY_SHIFT so this is okay
double ax = (size_a * 2 * rotate_center_x);
double ay = (size_b * 2 * rotate_center_y);




Part of the problem is that you mention "bounding rectangle of the ellipse", which I assumed was that of the axis-aligned ellipse centered at the origin. In fact, you did mention that the "anchor point" for rotation is the ellipse center at (0.5,0.5). The issue now is what "bounding rectangle" really means. It appears that OpenCV starts with a circle inscribed in a square with vertices (0,0), (1,0), (1,1), and (0,1), in which case the center is (0.5,0.5). The size_a and size_b parameters are the 'a' and 'b' of (x/a)^2 + (y/b)^2 = 1. If you scale the square, you get a rectangle with vertices (0,0), (2*size_a,0), (2*size_a,2*size_b), and (0,2*size_b). The center is (size_a,size_b), ***BUT*** the (cx,cy) passed to the function is still (0.5,0.5).

The mathematics I presented apply to an axis-aligned ellipse centered at the origin (0,0) *in actual coordinates*, not the square coordinate system. (ax,ay) is the center of rotation, *in actual coordinates*. My translation (cx,cy) is *in actual coordinates*, which is not the same thing as the square coordinate system.

Another point of confusion. Your comment says that "size_a/b got already left-shifted by XY_SHIFT so this is okay". I imagine the shifting and conversion to integer is simply for drawing purposes. The shifting/conversion is not part of the transformation you are trying to derive.

So let's start over...

You have an ellipse bounded by the rectangle with vertices (0,0), (2*a,0), (2*a,2*b), and (0,2*b). The center is (0.5,0.5), say, in "square coordinates" for the square with vertices (0,0), (1,0), (1,1), and (0,1). In "actual coordinates", the center is (a,b). The equation of the axis-aligned ellipse in "actual coordinates" is ((x-a)/a)^2 + ((y-b)/b)^2 = 1. The parameterization by angle theta is x = a + a*cos(theta) and y = b + b*sin(theta). If you specify the rotation center (rx,ry) in "square coordinates", then the "actual coordinates" are (kx,ky) = (2*a*rx,2*b*ry). Rotation about this center in "actual coordinates" is x' = kx + cos(phi)*(x-kx) - sin(phi)*(y-ky) and y' = ky + sin(phi)*(x-kx) + cos(phi)*(y-ky).

To convert this back to "square coordinates", you need to divide the x-equation by 2*a and the y-equation by 2*b:

px = x'/(2*a) = rx + cos(phi)*((1+cos(theta))/2 - rx)
- sin(phi)*(b/a)*((1+sin(theta))/2 - ry)

py = y'/(2*b) = ry + sin(phi)*(a/b)*((1+cos(theta))/2 - rx)
+ cos(phi)*((1+sin(theta))/2 - ry)





[Edited by - Dave Eberly on October 28, 2009 7:14:36 AM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!