This project is read-only.

Test if point is inside model (and more)

Feb 20, 2011 at 5:12 PM
Edited Feb 20, 2011 at 10:42 PM


I want create a game similar to minecraft (for learning) and because I'm not that experienced I want to ask a few things.

1.) Now how can I test if a point (Vector3) is inside the Model?

I have a Block class containing a BatchModelInstance, a Matrix (WorldMatrix). But the BatchModelInstance has no method to test if a point is inside it's geometry. Or in general, how can I get the face( the side of a cube for example) or the triangle the player is pointing on?

2.) How can I render so many blocks like in minecraft or like in this video ( ) ?

I created a 200x200x200 cube from a "cube" model. My first attempt was to draw every block with a drawing predicate and add the predicates to a Depth draw sorter. But this only helped a bit because I had to many Drawcalls, so now I'm drawing every cubemodel with a BatchModelInstance and a BatchModel class, but I don't know how i can combine this technique with the the draw predicate to occlude the blocks i can't see.

Also, if i draw each visible face, won't i have to many draw-calls again? What's the trick here?


3.) Is it more efficient to draw the block from a model, or to draw the blocks(or block sides) from a geometry drawer?

I heard it's best to generate the map and then testing each block-side if it is touching a nonsolid block. Is this true? Or is there another more efficient technique to do this?


4.)  Lighting

What is the technique called to get a lighting like this ( ) ?

And what's the algorithm called that calculates if a light (ray?) is blocked by something


5.) ProjectFromScreen

Where is that function located, in what class ? I've read about it on this site but I cannot find it anywhere (using XNA4 and XEN2.0). There's only ProjectFromTarget and ProjectToTarget in the camerastack.


6.) Player colliding with world

When I have ~200.000 blocks, I can't possibly test each of them if they collide with the player.

I thought about creating a list with the blocks that are in a fixed distance around the player in each frame.  I think if I create groups of 10x10x10 blocks and determine their common center, I might be able to reduce the number of blocks that the player might collide with. But i think there must be a better solution to sort out the blocks that aren't in range. Any suggestions?



Feb 20, 2011 at 11:26 PM
Edited Feb 20, 2011 at 11:28 PM

The thing is, minecraft - despite it's intentionally simplistic art style - is a very complex game (data and algorithm wise). The datasets involved will be enormous, and it'll be using some very advanced compression and data traversal schemes.

The simple example is to consider your 200^3 blocks. That's 8 million blocks, or 96 million triangles. Typically your upper limit for brute force triangle rendering should be around 250k.

The GPU is great at rendering triangles, but only if you give it loads of them. This may sound counter intuitive, but typically you want to be drawing at least 5,000 triangles per draw call (depending a bit on a number of factors). More than 100 draw calls and you start to fall over on the CPU side. You clearly can't draw cubes one at a time - but on top of that, you can't instance them dynamically either, the CPU load for instancing them alone (with 8 million!) would be crippling. That'd be about a gigabyte of bandwidth. Per frame.

For collision detection, clearly you can't test every box either. That's pretty obvious.

The same goes for lighting, but lighting is even more complex. The impressive nature of the video is that blocks shadow each other.
If you were to test the visibility of every block against one another, you'd have 64 trillion (yes, trillion) tests to do.

So, I can't really help you in the context of xen, what you are attempting is something that would require significant planning and great care to manage the data and algorithms. The rendering isn't so much the problem - it's working out what to render and doing it quickly. It's actually pretty trivial compared to the data management.

Sorry if this hasn't been the answer you were expecting, but I don't believe what you are attempting is feasible given your experience. I'm just trying to convey why I think that is the case. :-)
However I wouldn't suggest giving up, I'd just suggest looking at the core problems that minecraft deals with so well - not the visible end result.

Good luck :-)

Feb 20, 2011 at 11:37 PM

Ohh, and ProjectToTarget is ProjectToScreen. It's just ProjectToTarget takes in a DrawTarget, which can be either the screen or a texture.

The name didn't make sense otherwise.

Feb 21, 2011 at 1:09 AM
Edited Feb 22, 2011 at 12:53 PM

First of all, thank you so much for still answering, even although you have so little time!

I know that Minecraft is a very complex game (or I should say, I became aware of its complexity while working on this small project). But it's relatively simple graphics combined with the complex algorithms, is what makes the game interesting for me (programming-wise).

In the meantime (since opening this thread) I've already worked something to counter the problem with having so many individual blocks:

Instead of drawing blocks (Cubes) I will only draw the visible sides of the blocks. In the loading screen i can calculate what blockfaces are visible, and which are not. If a block gets destroyed, i just have to recalculate the surrounding 6 adjacent block surfaces. I think it doesn't get any more efficient.

Just for clarifiaction: I have an array[16,16,16] that contains the block types, I then generate the mesh for the whole volume of blocks, only creating the visible faces. But how can I "occlude" other chunks with this mesh now? And: How would I go about texturing this single mesh with different textures for each blockface?? Is there a technique to do those things? Or do I have to take a whole different approach?

When someone builds a large platform above the "earth", everything that is above the platform gets rendered, even though it should be occluded by the platform(made out of blocks too of course). So my question is: Is it possible to combine my idea of single big meshes, that contain 4096 different blocks, with occlusion? (like in your draw-predicate example) How would I go about this?


About the second video and the lighting: I meant the effect you can see in the video at 3:03. Where the lava emits a light.

How is this technique called if you don't have a single "point" light source but a "light emitting area" ? In the comments the creator said it would be a "flood fill algorithm for a whole area". How can you "flood fill" your scene with light? How is this done? Even if he adds a "color" value for each block, he would still have to interpolate the brightness between the blockfaces!

Thanks again for your answer!