Click here to Skip to main content
15,867,308 members
Articles / Multimedia / GDI

Curve representation by ICAS (Inner Centered Arcs)

Rate me:
Please Sign up or sign in to vote.
4.80/5 (13 votes)
13 Nov 2011CPOL7 min read 30.1K   1.7K   25   2
Suggestion about another curve representation

Introduction

What do you think is important for curve drawing?

Please compare it with your special.

  1. It passes through the input points.
  2. It needs less control points, less restrictions.
  3. It has continuity as high as possible. (class Cn )
  4. It has flexible density of generating points.
  5. It supports accurate circle.

In my sample program, above five properties are:

  1. It passes through the input points.
  2. It makes one control point automatically corresponding to a pair of input points.
  3. It has class C1 continuity at arcs connecting points.
  4. It has flexible density of generating points.
  5. It supports accurate circle.

For quick start, please begin from “How to use it?” We are so busy everyday, anytime…

Background

Last year, suddenly I got a penetrating short flash and incubated it to “Inner Centered Arcs”. I tried it more than a year, and I was determined to report it to you, ladies and gentlemen from The Code Project. About new technique, please read another document “Inner Centered Arcs (ICAS)”. I might graduate from Read Only Member at last.

How does ICAS Work?

It connects your inputting points to a series of circular arcs, producing one control point a pair of your points. Let's suppose you have three points (P1, P2, P3). They create two ICAS to have C1 continuity at the mid point (P2). Two ICAS data △P1C1P2 where C1 is corresponding to P1, P2 and △P2C2P3 where C2 is corresponding to P2, P3. Fig.1.

Series of arcs

Of course, you can edit the control points later. Control points are linked to edit in my sample program. They keep C1 continuity at the mid point (P2). Fig. 2.

Editing control points

But that is not natural ICAS feature. One ICAS data consists of three points, Start point (P1), Control point (C1) and End point (P2). It is basically triangle information, because its inner center is essential. (Inner center means the origin of inscribed circle.) One ICAS generates two circular arcs inside the triangle and the arcs have class C1 continuity at its inner center. A certain process generates tessellated triangles and its inner centers. We will see that every inner center stays on the arcs. Fig.3. I am sorry for my repetition, please read “ICAS” for the detail. I want no expanding topics here. That is the origin of “Inner Centered Arcs”, and this is the first time I explain the topic to the Open Society like The Code Project.

Basis of ICAS

Now I mention to the flexible density of generating points and the accurate circle. In the figures, they have identical points (P1, P2, P3). Fig. 4. Open curves consist of two ICAS only which tessellation degree (or suffix) differs from each other, on the other hand closed curves consist of three ICAS.

The closed curve will be a circle, if the triangle is regular and three control points is in homogenous condition. (This case control points make regular triangle too.) Add to say, each regular polygon can make a circumscribed circle.

Attribution makes difference

When you input points in Z shape, my sample program interpolates mid point (M) between your two points. (P2, P3) Fig. 5. Thus whole S curve is smooth at all connecting points, and has no crisp corners. Note that interpolation is not ICAS feature. It is just an implementing example.

Interpolation M

If you want a mixture of curves and straight lines, you need to plot the mid point (P4) on the straight line. Fig.6. My sample program forces the curve to be tangent with the three-pointed straight line (P3P4P5) at both terminals (P3, P5). As your consideration, it is not ICAS feature but an implementing example.

Mixture line&curve

What is Implemented in the Sample Program?

My concepts are quite simple:

  1. Examine ICAS features
  2. Search for effective ICAS input-edit method

I have been trying these concepts on my accustomed environment, MFC/View Document architecture. Simply I wrote main functions in C, triangle tessellation, calculation for inner center and control points, separating from the GUI stuffs (IcasBase.h, c). And I used them in CIcas class (IcasFig.h, cpp). You may expect a bit of portability, though I can’t owe my words…

Here, I explain the calculation for a control point. It needs four points, start point (S), end point (E), pre-start point (SS) and post-end point (EE). Fig.7. Control point (C) is the cross point on line <overline>C-PreC and line <overline>C-PostC. Positions of SS, S and E determine the direction of line <overline>C-PreC. Similarly positions of EE, E and S determine the direction of line <overline>C-PostC.

Note that accurate locations of PreC and PostC are not necessary. Only one passing point (S or E) and the line direction complete the calculation.

If the four points form Z shape, we need an interpolated point (M) between mid two points (S, E). Fig. 8. S curve causes two control points (C1, C2) simultaneously.

Mixture line&curve

C++
//
//calculate control point
int GetCntl(ICASWORK *SS, ICASWORK *S,
            ICASWORK *E,  ICASWORK *EE,
            ICASPOINT *C1, ICASPOINT *C2, ICASPOINT *M )
{
	double Vx,Vy,Sx,Sy,Ex,Ey,s,t,u;

	int sts = ChkCntl(SS, S, E, EE, C1, M );//set M
	if (0 > sts) return sts;//MULTIPLE check valid

	Work2Vector(SS,S);//A
	Work2Vector(S,E); //B
	Work2Vector(E,EE);//C

	//vector product
	//S-SS(A) vs S-E(B)
	s = S->vx * E->vy  - S->vy * E->vx;
	if (fabs(s) < EPS) {//M = SE middle point
		return -1;//S-SS and S-E are the identical line
	}
	//S-E(B)  vs E-EE(C)
	t = E->vx * EE->vy - E->vy * EE->vx;
	if (fabs(t) < EPS) {//M = SE middle point
		return -2;//S-E and E-EE are the identical line
	}
	//E-EE(C) vs S-SS(A)
	u = S->vx * EE->vy - S->vy * EE->vx;

	Sx = S->ex + E->ex; //A.ex + B.ex;//unit vector
	Sy = S->ey + E->ey; //A.ey + B.ey;
	Ex = E->ex + EE->ex;//B.ex + C.ex;
	Ey = E->ey + EE->ey;//B.ey + C.ey;
	Vx = E->vx;
	Vy = E->vy;

	if (L_PARALLEL == SS->typ) {//point SS on the identical line
		Sx = S->ex; //A.ex;
		Sy = S->ey; //A.ey;
	}
	if (L_PARALLEL == EE->typ) {//point EE on the identical line
		Ex = EE->ex;//C.ex;
		Ey = EE->ey;//C.ey;
	}
	//identical turning direction
	if (s*t > 0)
	{
		if (fabs(u) < EPS && (L_PARALLEL == SS->typ && L_PARALLEL == EE->typ)) {
			double l = E->l * 0.5;
			C1->x = S->x + S->ex * l; //A.ex * l;
			C1->y = S->y + S->ey * l; //A.ey * l;
			C2->x = E->x - EE->ex * l;//C.ex * l;
			C2->y = E->y - EE->ey * l;//C.ey * l;
			//boxy
			M->x = (C1->x + C2->x)*0.5;//C1C2 middle point
			M->y = (C1->y + C2->y)*0.5;
			return 2;
		}
		s  = (Ey*Vx - Ex*Vy)/(Sx*Ey - Ex*Sy);
		C1->x = S->x + (Sx*s);
		C1->y = S->y + (Sy*s);
		return 1;
	}
	//vector SS-S || vector E-EE (|| = parallel)
	else if (fabs(u) < EPS) {
		double l = E->l * 0.5;
		C1->x = S->x + S->ex * l; //Ax * l;
		C1->y = S->y + S->ey * l; //Ay * l;
		C2->x = E->x - EE->ex * l;//Cx * l;
		C2->y = E->y - EE->ey * l;//Cy * l;
		//Z fold//M = SE middle point
		return 2;
	}
	//Z fold
	else {
		double Ax,Ay,Cx,Cy;
		double C12x,C12y,w,v;
		double l = E->l * 0.5;
		w = sqrt(Sx*Sx + Sy*Sy);
		v = sqrt(Ex*Ex + Ey*Ey);
		Ax = Sx / w;
		Ay = Sy / w;
		Cx = Ex / v;
		Cy = Ey / v;
		C1->x = S->x + Ax * l;
		C1->y = S->y + Ay * l;
		C2->x = E->x - Cx * l;
		C2->y = E->y - Cy * l;
		C12x = C2->x - C1->x;
		C12y = C2->y - C1->y;
		u = Vx * C12y - Vy * C12x;

		if (fabs(u) < EPS) {//fail safe//M = SE middle point
		}
		//cross point SE and C1C2
		else {
			s = ((S->y - C1->y)*C12x - C12y*(S->x - C1->x))/u;
			M->x = S->x + (Vx*s);
			M->y = S->y + (Vy*s);
		}
		return 2;
	}
}
...

How to Use It?

Build ICAS.exe

My environment is Visual Studio 2008 Japanese edition. Plus, VS 6.0J is OK only some warnings with it. I rewrote comments in English. But main menu labels, pull-down menus remain in Japanese. I am sorry.

Start ICAS.exe

Click right button on the VIEW. The first menu appears.

“ICAS Input” and “ICAS Attribute”

“ICAS Input” guides you to input points, to finish inputting, you need “double click”. “ICAS Attribute” guides you to set usual properties.

First menu

Input Curve Points

Click “ICAS Input”. Mouse cursor changes from Arrow to Cross-hair. As you click singly at point location, it follows your points tracing with red poly-line. Simultaneously, it shows control points with blue poly-line. Brown poly-line is the curve, and it has initial attribution (radio button “0” means raw poly-line). Fig. 9. To finish inputting, you need double click at last point location. It closes figure by initial attribution. Fig. 10.

You can choose your inputting style from “ICAS Attribute”, that is merely my testing environment. Fig. 11.

Input curve point

Third degree density

Note Lattice means Grid guiding. At hex-like FRINGE area, it tends to miss the grid, Ph.D. W. Bishop reported to me. Walter, I am sorry for the bug.

Edit ICAS attribution

Click left button inside your figure. It shows your selection as a red polygon. Then click right button inside it. The second menu appears. “Icas Information”, “Move Icas Data” and “Delete Icas Data”.

Edit ICAS atribution

Click “Icas Information” to edit selected ICAS attribution. For example, if you want an open curve and third degree density of vertices, you should select like under, then “APPLY”.

Open & Third Density

Note fifth degree radio button means that we use minimum distance of neighboring two points. The right-sided edit-box takes its pixel number. The left-sided text-box shows whole logical length of the curve (closed figure). This case, 4.0 in the middle edit-box shows you just half-length of the curve with red-grid, please check “Param” and “APPLY”.

If you feel something wrong, please try “ReCalculation” from “ICAS attribute edit” dialog. This function cleans ICAS data, and calculates again from your inputted points. This allows me to avoid the mess, complicated input-edit GUI debugging. I am sorry for my easy corner cutting.

Edit ICAS triangle

To examine ICAS features, I had to try various situations. So I wrote “ICAS Triangle” dialog. It corresponds to each triangle. It allows you independent control points, lines & curves mixtures, changing tangent directions, etc. Click left button inside the aimed triangle. It shows your selection as a blue triangle. Then click right button inside it. The third menu appears. “Triangle information” and “Insert Segment Point”.

Edit ICAS triangle

Click “Triangle Information” to edit selected ICAS triangle. If you check “0x10 LEFT_TAN”, it changes the start tangent vector. Some flags do not change immediately after “OK” button. They need moving control point to change shape. Anyway, try it. And remember “ReCalculation” button.

LEFT_TAN checked

Concluding Remarks

I have been familiar with Bézier curve a long time. Sometimes, I was pissed off with series of Bézier curves, or coexistence with circles, or complicated application design for it. Of couse, NURBS is beyond the scope of my project.

We are so busy everyday, anytime.

So I could not believe it, when I got the idea of ICAS. I examined it carefully, and confirmed its validity. And I had one question. "Am I first? Another great person missed this?” Then I rushed to the Google site, searched everything about “inner center”, “biarc”, “curve passes through” and so on, but I got nothing. Next I got very doubtful. "Everyone knows it, but me” I questioned my colleague. “It’s a nasty trivia, isn’t it?” He said, “I don’t know!”

Frankly speaking, it is an alpha version, I think. There still remain some miner bugs. Anyway, please try it. I felt it would be a very useful technique. If you sent me some suggestions, I would appreciate them entirely. Thank you very much.

History

  • 12th November, 2011: Initial version

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Japan Japan
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionUsefulness? Pin
Stefan_Lang14-Nov-11 22:41
Stefan_Lang14-Nov-11 22:41 
AnswerRe: Usefulness? Pin
T.Kojima15-Nov-11 4:22
T.Kojima15-Nov-11 4:22 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.