Real-time collision

Normally you accelerate collision detection by placing your map (all the triangles that make it up) in some kind of scene graph such as an octree. Then you can check collision with only near objects without needing to go through every triangle in the map (basically complexity O(log n) instead of O(n)).

You can also simplify the scene first in a preprocessing step, i.e. transforming a rather complex wall which is made of several hundred triangles (for overhangs, windows, decorations, etc...) into a single cuboid (or maybe just four quads depending on how cheap you want to get), since there is no real benefit in testing the intersection of the player with every tiny feature of the wall (but what about bullets?).

If you can use a game engine that already supports that, it's probably best you use that, because fast and efficient collision detection is rather painful to implement. But there's nothing wrong with doing it yourself to learn.

Do i have to turn to game engine?

Well, you certainly could. Of course, this would trash all your work up to now. You probably want to look for a library instead. I suggest Bullet.

Normally you accelerate collision detection by placing your map (all the triangles that make it up) in some kind of scene graph such as an octree. Then you can check collision with only near objects without needing to go through every triangle in the map (basically complexity O(log n) instead of O(n)).

Let me elaborate. In the old days (CS 1.5 might be considered oldschool) graphics and collision representation were mostly the same thing. As time progressed, the two representations started to diverge. Personally I believe that the choice of an octree for this kind of data is odd at least: it appears to me that dataset complexity belongs to the realm where BSPs reign supreme... in the end this does not matter; so many things can go wrong with collisions and physics I strongly advice against coding it yourself, not even for learning purposes.
While I appreciate the recent trend of this forum in providing more and more theorical data with big-o notations, I must note that in the end, profiling and timings are kings.

since there is no real benefit in testing the intersection of the player with every tiny feature of the wall (but what about bullets?).

Very interesting point. As a matter of fact, the player expects its avatar to move much more freely than it appears. In some cases, the floor, or even the walls might be enclosed by collision hulls to smooth out movement. In some cases, this will also help navigation.
Bullets are pretty much of a different beast.
If they leave no marks, some divergence between graphics and physics is often tolerated.
When marks are required however, this becomes pretty much a different beast. It is now required to perform testing on the real graphic mesh. I'm not sure the old way of doing this is correct. New shader-driven technologies appear less limited and faster to implement.
Again, for CS1.5, it's probably easier to just use a single representation: there's enough perf to deal with it.

Thank you, [color="#284b72"]Bacterius and [color="#284b72"]Krohm.

So, what i need to do is getting all triangles from all meshes in the scene, and test collision between the character and the triangles, is it right?
Is there any simple sample for me to learn it ?

So, what i need to do is getting all triangles from all meshes in the scene, and test collision between the character and the triangles, is it right?
Is there any simple sample for me to learn it ?[/quote]
Well, not quite. That's the first step. If you did it like that it *would* work, but it would be quite slow and inefficient. The next step is to arrange your triangles in a spatial structure (BSP tree as Krohm says, which stands for Binary Space Partitioning tree), which basically allows you to say "this virtual box enclosing this bunch of triangles does not intersect the player, therefore none of the triangles inside it can intersect the player" thus allowing very fast intersection. But this is quite tricky to implement (along with the necessary maths and physics for actual collision detection) so unless you *really* want to learn how to do it you are better off using a library which abstracts all of that away from you so you can focus on the good stuff.

I want to implement it all by myself. So i think i need to get some information from some open source.
Any advice for the learning?

I suggest to look at a physics library. It's probably the best detailed source to learn from.

While I admit I have pointed at BSP trees, I suggest against using them as well as staying away from anything involving partitioning of graphics representations. BSPs are good, but they also demonstrated to be incredibly difficult.
There have been some rants about BSPs in the past. I remember this.
I am currently quite impressed by AABB trees. SAP (Sweep and Prune) algorithms are interesting but in the end, they ran at basically the same speed on my data sets.

But let me reiterate. Stable collision detection is hard. Are you sure?

I am busy in building the scene and other simple effect, so i have almost forget this .

My meaning is that, supposing, i get a stair model, through it the character can walk up to another floor. So how can i do the collision between stair and character?

Is it that I get all triangles from the stair model and then use each of them to do collision ?

That would be the simplest method, yes. But you will need to add some "tolerance" to height differences so that your character smoothly walks up the stairs without needing to jump. But that's the obvious method and there are several dozen possible improvements on this to improve performance, accuracy or both.

I will try it.