Checking a point inside Quadratic curve

In the last post I had written about qudratic equation. After that one thought came to my mind is How to check a point inside the curve ?. 

Below shows the qudratic curve equation from our 3 points. t^2(p1-p0'-p0) + p0' * t + p0 = P.  P is a point on the curve corresponding to t.

That is  a*t^2 + b* t + c = p, where a,b,c ,p are vectors. p yields the points on the curve accoding to the 't'.

So how can we check a point is in curve or not ?  we have 'p' and equation of the curve.As you guess this can be done by equation solving.But here a,b,c, are vectors.

So there must be some way to produce scalar values from these vetors , like taking magnitude of vectors in the equation like 

     |a|*t^2 + |b|*t + |c| = |p|.

This equation has some problmes , because it is just looking the magnitude of the vectors , direction is missing.A More wiser solution may be to solve for X,Y (Z in 3D)independently,like

a.x* t^2 + b.x *t + c.x = p.x --------> (1)

a.y* t^2 + b.y *t + c.y = p.y --------> (2)

As we know when we draw curve from p0 to p1 the t will vary from 0 -1 , We can check a point is inside the curve by solving one equation ( example : equation 1 ) and substitute that value of t in other equation ( here in equation2 ) . If you got the correct result as that of the input point (res == p.y) you can say the point is in the curve. Otherwise not.

When you solving the above equation you will get two values of t , so take the value which is inbetween 0 and 1 , and susbstitue it in other equation. 

To solve linear equation in computer you can use gauss elimination method ( you can try the above method in matheamtica easily ). 

Quadratic curve Interpolation

While reading a  book which explain different type of curves I couldn't see any description about qudratic curves( eventhough it is a good book) . Hence i decided to solve it by myself. That is what is shown below. :) . If you are looking for a simple curve this may be suffient . Qudratic curve offers only one control point (tangent)to control the shpae.

The simple Quadratic equation can be used to connect two point in space by a curve. The qudratic equation is simple and has the generic form at^2 + bt + C. Where a ,b,c can be any suitable quantity. Here i am taking it as a vector , and t is time( or any scalar).

we have two points in space , p0 and p1 , we want to draw a curve to connect these two points. So the question may arise how to control the curve position/direction. Okay , So you may be waiting for that third parameter .

So what is said earlier is f(t) = at^2 + bt + c. -------- (1)

While interpolating what we need is f(0) should give p0 (starting point) and f(1) should give p1 (end point).

f(0)  = p0 and f(1) = p1.

Thus putting 0 in equation (1) gives f(0) ->  c =  p0.

and 1 in equation (1) gives f(1) -> a+b+c = p1   --------(2)

 If we differentiate the equation (1) we will get   2at + b . As before we are assuming when t= 0 output is p0'

 ie f '(0) = p0' , which is 2a* 0 + b = p0' , thus we will get b = p0'

So just now we have solved two unknowns b and c,which is equal to p0' and p0 respectievly.
substituting b and c in Equation (2) gives

                                 a+ p0' + p0 = p1 , So a = p1 - p0' - p0

Holy cow! You just solved that equation , now you can smoothly interpoltate it by changing the paramter "t".
The final equation becomes t^2(p1-p0'-p0) + p0' * t + p0 .
At t = 0 it will give p0 and at t=1 it will give p1 as output. You can change p0' to change the shape of the curve. p0' is a vector , if its direction is same as p1-p0 vector the result will be straight line connectin p0 and p1 . Try changing t and p0' to get the desired results.

The below picture shows the curve drawn by this technique... The picture is unclear actually curve is smooth ( i don't know how to correct it ).

  
 Good luck

BSP Portal generation some thoughts

Recently i started to learn something more about portal and PVS (potential visible set) , and decided to write a my own engine. Everyone who are going to write a BSP tree and portal generation system would get some pain in their eyes . I am sure about it.  It is not as easy as we think , BSP tree is ok , but an efficient automatic Portal generation is algorithm is difficult .

I am looking some methods to do it . BSP tree helps to divide the input geometry data in to convex polygons , that means the leaf of the node will contain the convex polygons. If the input data is not a suitable one the bsp will be an unbalanced one , and also cause to split many polygons. So an efficient BSP tree algorithm is needed ,
Which should do the following things.
1. It should select the best splitter polygon from the given polygon set
2. The criteria may be the ratio between the split count and balanced leaf count  ( Right leaf Poly count/Left leaf poly count , if it is 1 this is ideal , and you are lucky).
The next thing is to generate portals . I am stopping now .   i will update this page soon (i have no idea ),
I am thinking about an algorithm currently which can generate portals efficiently. ..
Contd...

4-7-2008
I started BSP tree works , it is not much complicated,  i need to avoid recursion to avoid stack overflow during the creation of tree.. In case of small low poly models the triangle count are normally less and i can use recursion to create tree.. anyway it is not a big problem.. The Big problem is generating the portals , it may be impossible to 100% generate correct portals automatically.. hmm..Let me see.. I want to keep the current momentum.
I just completed BSP tree works.. It works!!... I have some few problems now , like calculating the texture coordinates when triangles got cut . My friend decided to implement Sutherland-Hodgman clipping algorithm for creating portals. Now I am waiting for his results..