# 3d engine design, want comments

This topic is 4611 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello, I'd liek to write my first 3d engine. Here are a few specs I can think of Direct3D 9, just basic lighting & textures (no shaders, just the fixed pipeline), basic keyframe animation, camera, hierarchy system. Would also like to implement some sort of kd-trees. the idea... create a hierarchy, each node would be a a class derived from some baseclass (say CSceneNode) so that rendering of various types of meshes/billboards etc could be done. Each node would contain a transformation matrix and it's children would be transformed relatively to their parent. Cameras and Lights would be nodes too, so that they can be "attached". The scene manager would keep track of the active camera. Each node would have a AABB so that it can easily be classified as in-frustum or out-of-frustum (since frustum is basically 4 line segments, that would only take 4 box-line intersections, which is pretty fast. A node type that would further divide itself (kd-tree, or an octree) would also be present for some complex geometry. what do you think? I've never done anything, but let myself be a bit inspired by the IrrLicht design.

##### Share on other sites
The design sounds good, not ground breaking but should be functional ;).

Quote:
 Original post by CaesarEach node would have a AABB so that it can easily be classified as in-frustum or out-of-frustum (since frustum is basically 4 line segments, that would only take 4 box-line intersections, which is pretty fast. A node type that would further divide itself (kd-tree, or an octree) would also be present for some complex geometry.

Take care here. A frustrum is usually made of 6 planes (up, down, left, right, near, far), not 4 lines.

##### Share on other sites
Quote:
 Original post by CaesarHello, I'd liek to write my first 3d engine. Here are a few specs I can think ofDirect3D 9, just basic lighting & textures (no shaders, just the fixed pipeline), basic keyframe animation, camera, hierarchy system. Would also like to implement some sort of kd-trees.the idea...create a hierarchy, each node would be a a class derived from some baseclass (say CSceneNode) so that rendering of various types of meshes/billboards etc could be done. Each node would contain a transformation matrix and it's children would be transformed relatively to their parent. Cameras and Lights would be nodes too, so that they can be "attached". The scene manager would keep track of the active camera.Each node would have a AABB so that it can easily be classified as in-frustum or out-of-frustum (since frustum is basically 4 line segments, that would only take 4 box-line intersections, which is pretty fast. A node type that would further divide itself (kd-tree, or an octree) would also be present for some complex geometry.what do you think? I've never done anything, but let myself be a bit inspired by the IrrLicht design.

So you basicly have a bounding volume- & transform hierarchy. Sounds like basic scene graph design. Nothing wrong with your ideas, although as b34r said the frustum can't be represented by 4 line segments.

##### Share on other sites
I agree with those above. A very good project; to get a scene graph up an running with some basic culling.

Using that you can then continue to expand/modify it as time goes. Adding whatever you want.

One thing that I think is good if you want to develop an engine is to use it in a real project. That is after you have some basic functionality you use it for something real (not just a tech demo). I always gets surprised when my elaborate engine designs turn out to be completely unnecessary and overly complex :P

Regards and good luck!
/hObbE

##### Share on other sites
You seems to point out that there are also other ways to take in designing a 3d engine. Like what kinds of?

Yeah, I was wrong with the lines. I was imagining the 4 lines that connect the near and far plane... somehow, the other 8 or the possiblity it need not intersect any of the lines and still intersect the frustum came on my mind. How should I do it then? Check plane/box collisions or is there a completely different way?

Also, would my design allow shadows later (no idea what kind of shadows I'd do, probably any would be good enough) or would it be hard to implement them?

##### Share on other sites
Quote:
 Original post by CaesarYou seems to point out that there are also other ways to take in designing a 3d engine. Like what kinds of?

There are no rules on how to design a 3d engine. BTW, when you say 3d engine I assume you mean the stuff you need to be able to represent a 3d scene and render it efficiently.

You should be able to organize scene objects spatially in order to make various spatial operations such as frustum culling and collision detection more efficient. This was my approach when designing my 3d engine, so I designed a generic datastructure that took care of this. I'll worry about transform- & render-state hierarchies later. I'll find out soon enough if this was a terrible mistake or not.

Anyway, I can recommend that you try immitating the design every other engine uses and find out for yourself what you want to improve (if anything). Immitate then innovate is a good expression that also applies to 3d engine design.

Quote:
 Yeah, I was wrong with the lines. I was imagining the 4 lines that connect the near and far plane... somehow, the other 8 or the possiblity it need not intersect any of the lines and still intersect the frustum came on my mind. How should I do it then? Check plane/box collisions or is there a completely different way?

Yes you do intersection tests on the box and the 6 clipping planes that represent the frustum. If the box is behind any of the clipping planes then the box is definately outside the frustum. Otherwize the box intersect or is inside the frustum.

Quote:
 Also, would my design allow shadows later (no idea what kind of shadows I'd do, probably any would be good enough) or would it be hard to implement them?

I don't know shadowing works so I can't comment on this.

##### Share on other sites
Thanks you all. I'll try to implement it the way I've described then. You've been very helpful

##### Share on other sites
Also, you'd need to define the scene structure for your engine.

Scene graph nodes don't cover all aspects of an 3D engine, as objects interactions, neighboring, physics, collision detection and visiblity culling.

At first think about if you want to implement large outdoor landscapes, or an indoor complex like Quake buildings. How you might distribute sceneary for help your virtual characters walk through?

Keep a Sector-Portal structure is an strategic option, not only for rendering, but also for Collision detection and AI. Virtual characters will be wise when you provide them paths for navigating through the world, and they will be able to find doors and windows for move between rooms.

##### Share on other sites
Quote:
 Scene graph nodes don't cover all aspects of an 3D engine, as objects interactions, neighboring, physics, collision detection and visiblity culling.At first think about if you want to implement large outdoor landscapes, or an indoor complex like Quake buildings. How you might distribute sceneary for help your virtual characters walk through?

I was thinking I'd keep a separate copy of the geometry in memory for collisions, since accessing it from vertex buffers might be expansive. Although this is going to be memory-expansive, but have no better idea.

Quote:
 Keep a Sector-Portal structure is an strategic option, not only for rendering, but also for Collision detection and AI. Virtual characters will be wise when you provide them paths for navigating through the world, and they will be able to find doors and windows for move between rooms.

haven't thought about that yet. Sector-portal: do you mean having each "room" as a polygons and doors marked by a sort of waypoints? Or just waypoints? Wouldn't that make them even dumber then, why 3d at all when they only move on lines between waypoints...

I was primarily thinking of doing it just for rendering. But this is an aspect I should keep in mind, I agree. That's why I haven't decided yet if it's going to be used for outdoor or indoor scenes... and haven't thought about AI yet.

##### Share on other sites
Sector can viewed as an island where objects are treated separatelly from another island (sector).
A sector can be conformed by a group of objects that are render together. They can be organized in a KD-Tree structure if you want, but it isn't necessary.

That sector have doors or portals that give a view to more sectors, and you can implement a occlusion test for check objects visibility. That helps if you want to draw a large world.

##### Share on other sites
Also don't forget check Humus 3D's portal demo, at http://www.humus.ca/index.php?page=3D&&start=16

##### Share on other sites
Well, the question still is how to prepare for AI or store geometry for collision detection. Since I'll have to transform the geometry for collision detection, I'm becoming quite sceptic about the idea of keeping a separate copy in memory.

thanks for the link, looks great, will look at it when I get some sleep.

##### Share on other sites
Quote:
 Original post by Caesarcreate a hierarchy, each node would be a a class derived from some baseclass (say CSceneNode) so that rendering of various types of meshes/billboards etc could be done. Each node would contain a transformation matrix and it's children would be transformed relatively to their parent.

Your approach seems to be like WildMagic.
I have adopted a renderware-style approach: each scenenode has a pointer to a Frame that is a transformation entity of the elements of the scene.
I like it; but is only a different point of view of the same things ;)
The other part is very similar of your solution.

bye,
Davide

##### Share on other sites
Quote:
 Well, the question still is how to prepare for AI or store geometry for collision detection. Since I'll have to transform the geometry for collision detection, I'm becoming quite sceptic about the idea of keeping a separate copy in memory.

You can use the Direct3D equivalent to Vertex Buffer Objects to store the rendered geometry in graphics card memory (video/agp RAM), and keep a separate copy for collision detection in system RAM. The copy kept in system RAM is also more compact because polygons can share vertices, which AFAIK isn't possible with vertex arrays anyway.

This is what I'm doing currently and it works quite well.

##### Share on other sites
Quote:
 Original post by ZiMThe copy kept in system RAM is also more compact because polygons can share vertices, which AFAIK isn't possible with vertex arrays anyway.

No, it's totally possible with vertex arrays (at least, it is under D3D) - just use indexed primitives. (Or weld your buffer into one great big triangle strip, but that's a bad idea).

Keeping a seperate copy for collision detection is what I'd recommend too. It'll allow you to manipulate it into a form more efficient for coldet without worrying about breaking rendering (e.g. you could set up a tight octree without worrying about the effect of the split polygons on rendering).

##### Share on other sites
a clarification: I'd like my geometry to be index buffered. So indices into vertex buffers.

Keeping a seperate copy for collision detection is what I'd recommend too. It'll allow you to manipulate it into a form more efficient for coldet without worrying about breaking rendering (e.g. you could set up a tight octree without worrying about the effect of the split polygons on rendering).[/qutoe]

wouldn't that make me transform everything twice (it would be transformed once by the pipeline itself and once by me, right there in the source code, for collision detection. Is there a workaround?

in pseudo
//set the world transformation matrixworld_matrix = some_matrix;//the pipeline would render the mesh. it also needs to transform it//into world space in order to be able to draw the meshDrawPrimitive(index_buffer, vertex_buffer);//here, I need to transform for the second time in odred to able to do//collision detectionTransform(vertex_buffer, world_matrix);Collision(vertex_buffer, other_buffers);

##### Share on other sites
First, you don't (in most cases) need to transform your vertex buffers used for rendering manually - OpenGL / Direct3D can do it.

Second, for collision detection you'll never transform all of your geometry, but rather a small piece of it. For example, when doing single ray-tracing (used for detecting whether you hit a monster with a bullet) you don't need to transform your geometry at all. Instead you transform the ray into monster's space and then perform the test with untransformed monster's geometry (not to mention a bounding box/sphere test first).

Besides, what modern game engines do nowadays is to use some physics middleware (e.g. ODE, Havok) to do all physics related stuff. These libraries have their own structures designed for most optimal physics simulation / collision detection focused usage.

##### Share on other sites
Quote:
 Original post by ZiMThe copy kept in system RAM is also more compact because polygons can share vertices, which AFAIK isn't possible with vertex arrays anyway.

As superpig said, it is possible to share verts with vertex arrays, the main case where you can't is when you have vertices with the same position but different texture coordinates, which is usually what people trip up on.

-Mezz

##### Share on other sites
Quote:
 As superpig said, it is possible to share verts with vertex arrays, the main case where you can't is when you have vertices with the same position but different texture coordinates, which is usually what people trip up on.

Yup, multiple texture coordinates per vertex makes it really difficult to use triangle strips or indexed primitives. I don't think indexed primitives are much faster than using normal vertex arrays, as long as data is in both cases stored in graphics card memory. Only memory constumption is smaller.

[Edited by - ZiM on July 6, 2005 4:35:37 AM]

##### Share on other sites
Quote:
Original post by ZiM
Quote:
 As superpig said, it is possible to share verts with vertex arrays, the main case where you can't is when you have vertices with the same position but different texture coordinates, which is usually what people trip up on.

Yup, multiple texture coordinates per vertex makes it really difficult to use triangle strips or indexed primitives.
No it doesn't. You just duplicate the position/normal/colour data to go with each set of texture coordinates, having three or four unique vertices in the same spot.

Quote:
 I don't think indexed primitives are much faster than using normal vertex arrays, as long as data is in both cases stored in graphics card memory. Only memory constumption is smaller.
Post-transform cache usage is very much affected.