msnkd's profilePoor programmer's BlogPhotosBlogListsMore  |  Tools Help |
Poor programmer's BlogTo all fellow programmers |
|||||
|
October 07 Octree based engine , First impressionI just completed a basic framework of my engine , which uses octree for occlusion culling and coliision,
You can get the exe file from this link http://cid-a0be50c9af3cc73e.skydrive.live.com/self.aspx/Public/engine%20test/test!.rar
It can render indoor as well as outdoor scenes, Now i think octree are good for suporting coliision detection system , beacuse it can isolate a geomoetry from a complex scene quickly . For occlusion culling octree is ok , but i think it is not enough. The recursion may take longer time than actually drawing the entire area.
I am looking for some other space partioning systems. October 06 Graphics Engine : collision detection using SATCurrently 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 };
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.
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.
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() ;
{
// 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;
}
September 20 3DS file renderingI 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 ]
September 19 Back to school , 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
September 13 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.
July 23 Checking a point inside Quadratic curveIn 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 ).
July 17 Quadratic curve InterpolationWhile 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 equatiion (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
June 18 BSP Portal generation some thoughts
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. 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 The next thing is to generate portals . I am stopping now . i will update this page soon (i have no idea ), 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.. January 29 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.. December 26 Global objects and CRT startup.Did you ever noticed about the initialization of your global objects ? Like who calls constructor and destructor of your global objects ?
It is CRT does the job. Try changing the startup routine ( Linker settings in VS). You can see default it is blank . No startup routine is selcted. Infact it calls the __tmainCRTStartup in crt , and from the main get called.
So try changing the startup routine to main ( not __tmainCRTStartup) , so you can see that the global objects
constructors/Destructor are not get called.
So you can make application more faster by removing startup rouinte to our main. But all other things we have to handle , anyway it is not generalized.
you can also set crt functions as startup routine. for example try setting malloc as startup routine ( you might get your pc hang).
|
Thanks for visiting!
No namewrote:
Hi Krishna,
Nice blog, keep it up.. :)
By the way, I have added two more draings to my blog http://mind-never-mind.blogspot.com :)
Dhanan
June 27
Marciawrote:
I'm a media specialist at a school in Wisconsin, USA. Traveled to India two years ago. Where in India are you?
June 12
Egbert BLISSwrote:
Just call me Herbert :)
May 11
Egbert BLISSwrote:
Hello, thanks for visiting my space. We will have examinations next 2 weeks and I must study harder now. After these examinations I can work in the company light-heartedly. Good luck!
May 11
|
|||
Send a private message
Subscribe to RSS feed
Tell a friend
Add to My MSN
Add to your network
Sign up for alerts|
|
