Accelerated 3D rendering.

Following screen shots are from my rendering engine. It uses octree and occluion culling to accelerate the rendering process. It took almost 1 month to complete. Still some optimaization works are pending like use SIMD instructions etc.

In first image you can see some buildings(of course the building are not realistic, but it doesn't matter )  and the camera is placed near a wall 

 When we move camera a little downwards , the camera got occluded totaly by that wall . This cause to cull a lot of polygons in the scene. The second image shows that scene (scene is a bit zoomed out to get a clear picture). Also you can see the frame rate in title bar(for the second image it is 360). Frame rate is increased by a great amount.

Now I have plan to write a tool for manually selecting occluder polygons for a scene. 

Projecting vectors

Sometimes we need to project one vector over another. See the picture below , we can see a vector u. Now we need to project this u on to x axis, .






This can be done with this equation : p = x * u . (x / Norm[x] ) . p is the result

"." means Dot product. What that equation means is we need to normalize x first ( in general to which we are projecting u vector ) and find the dot product between u and normalized x , and mulitply our x(destingation ) vector by this scalar value. Now we will get the result.

Finding rotation axis of a rotation matrix.

A rotation matrix can be represented as

x1 x2 x3
y1 y2 y3
z1 z2 z3

Where (x1, y1, z1) are the first vector (x2, y2, z2), (x3, y3, z3) are the second and third vectors.
Note this matrix is column major oriented.

When you multiply this matrix by an arbitrary vector in space you will get the rotated vector coordinates.

In some situations it is important to know the axis of rotation. Here I am going to present one method to get the rotation axis from rotation matrix.

Consider this matrix which represents a rotation around axis ( 0.7017,0.7017,0 ) , this actually a vector in x-y plane rotated by 45 degree, Like this

The rotation matrix for rotating around this vector by 45 degree is shown below (which I calculated using quaternion)

0.8536 0.146 0.500
0.1460 0.850 -0.500
-0.500 0.500 0.707

When we multiply a arbitrary vector (x,y,z) by this matrix we gets the vector function F as below

(X 0.8536 + y 0.146 + z 0.5) i + ( x 0.146 + y 0.85 – z 0.5 ) j + ( -x 0.5 + y 0.5 + y 0.707 ) k

I,j,k are the base vectors.

Taking curl of this vector function F, we get the axis of rotation.

I calculated the curl of that function and it is (1,-1, 0). After normalizing this vector we can see the result as (.707,-.707, 0),. Earlier we had created the rotation matrix to rotate around the axis ( .707,.707,0). Our answer curl is in the opposite direction of (.707,.707,0) , but it is still correct.

Only problem is with the direction of rotation that is clockwise or anti clock wise..

Finding area of Circle.

A few months back i decided to study calculas. I don't want to solve equations. But understanding the concept like infinitily small things and how we can use that in practical purposes. I got a book , which explains very basically the concepts..

As a start of the study i decided to find the area of circle. Everyone knows it .. It is Pi * r ^2.
How it came ? Old people know it . Old indian mathematicians , egyptions all know that.. But calculas is developed after that.. By Sir Newtorn & Sir Lebnitz.

I decided to use caluclas to find the area of circle. We know the cirlcle can be divided in to many triangles see the follwing picture



you can see that a cirlcle containing a triangle. Suppose if we could divide the circle with very small tiny ! triangle , the area will be equal to that of the sum of all area of the triangles.

Okay this is how Infinitely small items can be useful for practical purpose. Here the area of the one Infinitely small triangle is this ( based on radius r )
Area = 1/2 * r cos(theta) * r sin(theta)
Integrating this to 0-2Pi gives the result , see below for the idea

Collision detection using Separating Axis Theorem

Currently i am working on a graphics engine , which uses loose octree for occlusion culling as well as collision detection..

It works as i am expected. I have implemented  the SAT algoritham to test BOX-Triangle intersection test. It works well..Currently i am checking all the triangles inside the current camera node, It doesn't seems practical with detailes scene.

I need to add support for collision mesh( These mesh  are not rendered,they are just used for collision detection).Hmm.I can see the need for a level editor. Before that i am would like to respond my camera accoring to the geometry in the scene.

---

Following is the SAT code for triangle - Box intersection , I couldn't find any c++ code in internet ( Muller's is there , it is cryptic for me as well as it is not c++)

 template

<typename T>

Interfaces3D::InterSection CBBox<T>::IsInsideBox(

const Triangle<T>& refTri ) const

{

// If three points are inside the box, definitily the triangle is inside the ABBBox.

if( IsInsideBox( refTri.m_Pt1 ) && IsInsideBox( refTri.m_Pt2 ) && IsInsideBox( refTri.m_Pt3 ) )
   return Interfaces3D::InterSectionIn;

Math3D::vector<T> xAxis(1,0,0);

Math3D::vector<T> yAxis(0,1,0);

Math3D::vector<T> zAxis(0,0,1);

//..............................................................

// Intersection test using SAT (separating Axis test) algorithm.

//..............................................................

float fMin,fMax;

float fBoxMin,fBoxMax;

float fProjTri[3] = { 0,0,0 };

float fProjBox[2] = { 0,0 };

// First test is agnist the AABBox's cardianl axis.

fProjTri[0] = refTri.m_Pt1.x;

fProjTri[1] = refTri.m_Pt2.x;

fProjTri[2] = refTri.m_Pt3.x;

FindMinMax( fProjTri,3,fMin,fMax );

if( (fMin < m_XL && fMax < m_XL ) || (fMin > m_XR && fMax > m_XR ) )

return Interfaces3D::InterSectionOut; // the triangle is outside.

fProjTri[0] = refTri.m_Pt1.y;

fProjTri[1] = refTri.m_Pt2.y;

fProjTri[2] = refTri.m_Pt3.y;

FindMinMax( fProjTri,3,fMin,fMax );

if( (fMin < m_YB && fMax < m_YB ) || (fMin > m_YT && fMax > m_YT ) )

return Interfaces3D::InterSectionOut; // the triangle is outside.

fProjTri[0] = refTri.m_Pt1.z;

fProjTri[1] = refTri.m_Pt2.z;

fProjTri[2] = refTri.m_Pt3.z;

FindMinMax( fProjTri,3,fMin,fMax );

if( (fMin < m_ZF && fMax < m_ZF ) || (fMin > m_ZN && fMax > m_ZN ) )

return Interfaces3D::InterSectionOut; // the triangle is outside.

// Second test is agnist triangles normal.

Math3D::vector<T> vtNormal = refTri.m_Normal;

// project the triangle coordinates on this normal as well as the AABB corners.

// projecting Box's coordinates

Math3D::vector<T> vtRadius = GetTopLeftNear() - GetPosition();

float fExtent = vtNormal.Dot( vtRadius );

float fCenterBox = vtNormal.Dot( GetPosition() );

fProjBox[0] = fCenterBox + fExtent;

fProjBox[1] = fCenterBox - fExtent;

FindMinMax( fProjBox, 2,fBoxMin,fBoxMax );

// projecting triangle coordinates

fProjTri[0] = vtNormal.Dot( refTri.m_Pt1 );

fProjTri[1] = vtNormal.Dot( refTri.m_Pt2 );

fProjTri[2] = vtNormal.Dot( refTri.m_Pt3 );

FindMinMax( fProjTri, 3,fMin,fMax );

// Check for overlapping between pronected coordinates.

// if not overlapping , no intersection.

if( (fMin < fBoxMin && fMax < fBoxMin ) || (fMin > fBoxMax && fMax > fBoxMax ) )

return Interfaces3D::InterSectionOut; // the triangle is outside.

// Next possible SAT axis are the Cross product of each tri edges with

// box's cardinal axis.

Math3D::vector<T> satAxis[9];

Math3D::vector<T> vTmp = (refTri.m_Pt1 - refTri.m_Pt2);

// edge 0 and X,Y,Z axis

satAxis[0] = vTmp.Cross( xAxis).normalize() ;

satAxis[1] = vTmp.Cross( yAxis).normalize() ;

satAxis[2] = vTmp.Cross( zAxis).normalize() ;

// edge 1 and X,Y,Z axis

vTmp = (refTri.m_Pt3 - refTri.m_Pt2);

satAxis[3] = vTmp.Cross( xAxis).normalize() ;

satAxis[4] = vTmp.Cross( yAxis).normalize() ;

satAxis[5] = vTmp.Cross( zAxis).normalize() ;

// edge 2 and X,Y,Z axis

vTmp = (refTri.m_Pt1 - refTri.m_Pt3);

satAxis[6] = vTmp.Cross( xAxis).normalize() ;

satAxis[7] = vTmp.Cross( yAxis).normalize() ;

satAxis[8] = vTmp.Cross( zAxis).normalize() ;

for( int i = 0; i < 9 ; i ++ )

    {

fExtent = satAxis[i].Dot( vtRadius );
fCenterBox = satAxis[i].Dot( GetPosition() );
fProjBox[0] = fCenterBox + fExtent;
fProjBox[1] = fCenterBox - fExtent;
FindMinMax( fProjBox, 2,fBoxMin,fBoxMax );
 // projecting triangle coordinates
fProjTri[0] = satAxis[i].Dot( refTri.m_Pt1 );
fProjTri[1] = satAxis[i].Dot( refTri.m_Pt2 );
fProjTri[2] = satAxis[i].Dot( refTri.m_Pt3 );
FindMinMax( fProjTri, 3,fMin,fMax );
// check for overlapping on the SAT axis 
if( (fMin < fBoxMin && fMax < fBoxMin ) || (fMin > fBoxMax && fMax > fBoxMax ) ) 
        return Interfaces3D::InterSectionOut; // the triangle is outside. 

   } 

return Interfaces3D::InterSectionIntersect; 

}

Collision detection using SAT

Following is the SAT code for triangle - Box intersection , I couldn't find any c++ code in internet ( Muller's is there , it is cryptic for me as well as it is not c++)

template

<typename T>

Interfaces3D::InterSection CBBox<T>::IsInsideBox(

const Triangle<T>& refTri ) const

{

// If three points are inside the box, definitily the triangle is inside the ABBBox.

   if( IsInsideBox( refTri.m_Pt1 ) &&  IsInsideBox( refTri.m_Pt2 ) &&  IsInsideBox( refTri.m_Pt3 ) )
   return Interfaces3D::InterSectionIn;

   Math3D::vector<T> xAxis(1,0,0);

   Math3D::vector<T> yAxis(0,1,0);

   Math3D::vector<T> zAxis(0,0,1);

  //..............................................................

  // Intersection test using SAT (separating Axis test) algorithm.

  //..............................................................

  float fMin,fMax;

  float fBoxMin,fBoxMax;

  float fProjTri[3] = { 0,0,0 };

  float fProjBox[2] = { 0,0 };

   

 // First test is agnist the AABBox's cardianl axis.

 fProjTri[0] = refTri.m_Pt1.x;

 fProjTri[1] = refTri.m_Pt2.x;

 fProjTri[2] = refTri.m_Pt3.x; 

 FindMinMax( fProjTri,3,fMin,fMax );

 if( (fMin < m_XL && fMax < m_XL ) || (fMin > m_XR && fMax > m_XR ) )

     return Interfaces3D::InterSectionOut; // the triangle is outside.

 fProjTri[0] = refTri.m_Pt1.y;

 fProjTri[1] = refTri.m_Pt2.y;

 fProjTri[2] = refTri.m_Pt3.y;

 FindMinMax( fProjTri,3,fMin,fMax );

 if( (fMin < m_YB && fMax < m_YB ) || (fMin > m_YT && fMax > m_YT ) )

    return Interfaces3D::InterSectionOut; // the triangle is outside.

 fProjTri[0] = refTri.m_Pt1.z;

 fProjTri[1] = refTri.m_Pt2.z;

 fProjTri[2] = refTri.m_Pt3.z;

 FindMinMax( fProjTri,3,fMin,fMax );

 if( (fMin < m_ZF && fMax < m_ZF ) || (fMin > m_ZN && fMax > m_ZN ) )

    return Interfaces3D::InterSectionOut; // the triangle is outside.

 // Second test is agnist triangles normal. 

 Math3D::vector<T> vtNormal = refTri.m_Normal;

 // project the triangle coordinates on this normal as well as the AABB corners.

 // projecting Box's coordinates

 Math3D::vector<T> vtRadius = GetTopLeftNear() - GetPosition();

 float fExtent = vtNormal.Dot( vtRadius );

 float fCenterBox = vtNormal.Dot( GetPosition() );

 fProjBox[0] = fCenterBox + fExtent;

 fProjBox[1] = fCenterBox - fExtent; 

 FindMinMax( fProjBox, 2,fBoxMin,fBoxMax );

 // projecting triangle coordinates

 fProjTri[0] = vtNormal.Dot( refTri.m_Pt1 );

 fProjTri[1] = vtNormal.Dot( refTri.m_Pt2 );

 fProjTri[2] = vtNormal.Dot( refTri.m_Pt3 );

 FindMinMax( fProjTri, 3,fMin,fMax );

 // Check for overlapping between pronected coordinates.

 // if not overlapping , no intersection.

 if( (fMin < fBoxMin && fMax < fBoxMin ) || (fMin > fBoxMax && fMax > fBoxMax ) )

    return Interfaces3D::InterSectionOut; // the triangle is outside.

  

 // Next possible SAT axis are the Cross product of each tri edges with

 // box's cardinal axis.

 Math3D::vector<T> satAxis[9];

 Math3D::vector<T> vTmp = (refTri.m_Pt1 - refTri.m_Pt2);

 // edge 0 and X,Y,Z axis 

 satAxis[0] = vTmp.Cross( xAxis).normalize() ; 

 satAxis[1] = vTmp.Cross( yAxis).normalize() ;

 satAxis[2] = vTmp.Cross( zAxis).normalize() ;

 // edge 1 and X,Y,Z axis 

 vTmp = (refTri.m_Pt3 - refTri.m_Pt2);

 satAxis[3] = vTmp.Cross( xAxis).normalize() ;

 satAxis[4] = vTmp.Cross( yAxis).normalize() ;

 satAxis[5] = vTmp.Cross( zAxis).normalize() ;

 //  edge 2 and X,Y,Z axis

 vTmp = (refTri.m_Pt1 - refTri.m_Pt3);

 satAxis[6] = vTmp.Cross( xAxis).normalize() ;

 satAxis[7] = vTmp.Cross( yAxis).normalize() ;

 satAxis[8] = vTmp.Cross( zAxis).normalize() ;

 for( int i = 0; i < 9 ; i ++ )

  {

fExtent = satAxis[i].Dot( vtRadius );

fCenterBox = satAxis[i].Dot( GetPosition() );

fProjBox[0] = fCenterBox + fExtent;

fProjBox[1] = fCenterBox - fExtent;

FindMinMax( fProjBox, 2,fBoxMin,fBoxMax ); 

 // projecting triangle coordinates

            fProjTri[0] = satAxis[i].Dot( refTri.m_Pt1 );

            fProjTri[1] = satAxis[i].Dot( refTri.m_Pt2 );

            fProjTri[2] = satAxis[i].Dot( refTri.m_Pt3 );

            FindMinMax( fProjTri, 3,fMin,fMax );

           // check for overlapping on the SAT axis

           if( (fMin < fBoxMin && fMax < fBoxMin ) || (fMin > fBoxMax && fMax > fBoxMax ) )

               return Interfaces3D::InterSectionOut; // the triangle is outside.

  } 

return Interfaces3D::InterSectionIntersect;

}

3DS file rendering

I have completed my 3ds scene rednering a few weeks before.  Below picture show it..

I could perfectly handle almost all 3ds related information and transparency. Now i have plan to do ray tracing to produce good quality image .

[ Thanks to artist-3d.com and max-realsms for their models ]

std::vector and pointers.

STL vector is nice class , which allows us to randomly access any location in the vector.

But if you use pointers to reference memory inside the vector , it can be dangerous depends upon the situation.

Consider this example, I have declared a std::vector object for storing some objects of "SomeClass".

std::vector<SomeClass> Objects;
// i am feeding the vector here... like Objects.push_back( .. )

 After feeding the vector i just took the address of first object in the vector.

like SomeClass* pThink = &Objects[0];

This is fine and has no problems at all. But the problems will come if you keep feeding the vector or removing elements .. Because std::vector will always reorganizing memory .It make sure that the memory allocated for objects will be continous.

So if we refer the pointer 'pThink' after push/ remove functions , it can cause expcetion similar to pointing incorrect memory location etc.

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..

C++ overloading operator& ( Or Find the addess of a object)

Recently a friend of mine ( name : rejeesh ) asked me "how to find the address of an object if the & operator is  overloaded" ?

Example class is like this

class AddressBlocker

{

public:

  AddressBlocker*

  operator &()  {  return 0;  }

};

so if you try to execute a code like this

AddressBlocker op;

AddressBlocker* Pt = &op;

Pt will be NULL. Pt =  &op will not pass the  real address of op to Pt. Because the operator is overloaded.

So how to get the address ??

When he asked me it, i found two solutions with templates .  One deriving a new class from the required class , and the second one is
more tricky. I will explain ( by showing the code) here both two methods.

Method 1.

template<typename T>
class Addressfinder : public T
{
public:
    Addressfinder* operator&() { return this; }
};

and you use it like this
AddressBlocker
blockMe;
Addressfinder<AddressBlocker>& finder = static_cast<Addressfinder<AddressBlocker>&> ( blockMe );


and address can be retrieved by simple  "AddressBlocker* pValid = &finder;" . This will work since i overloaded the &operator in Addressfinder class.
Method 2.

I think this is more good compared to the above. Since it is not creating any more relationships with the classes. and also no need for casting to use it.

template <typename T>
class AddressfinderII
{
    T& tOb;
public:
    AddressfinderII(T& t): tOb(t){}
    T * operator&()
    {
        return reinterpret_cast<T*> ( *reinterpret_cast<int *>( this ) );
    }
};

usage is like this

AddressBlocker blocker;
AddressfinderII<AddressBlocker> finderII(blocker);AddressBlocker * pAddress = &finderII;
if you look the size of this class , it just 4 bytes. because storing reference is same as pointer.
The class object's memory will have just the real address of object. And i extracted that value in operator& and returned.

Ok.. There is a more convenient way , he told me . and it is used in boost libraries. anyway i could find some alternatives 

Method 3

template<typename T>
T* addessof(T& t)
{
    return reinterpret_cast<T*>(& reinterpret_cast<int&> ( t ) );
}
and can be use like addressof( blocker); it is more convenient. it has similarities with method 1. So now no more address hiding..