Scratch

Hardmath123 · 2012-04-22 06:59:26

Hey guys,

As some of you might know, I'm working on a OpenGL engine for Scratch. I've hit a roadblock, though: my depth testing is wrong. Depth testing is the algorithm used to decide which shape is in front, given two shapes in 3 dimensions. For example, if there is a tree in front of your house, and you are looking at your house, you will see the tree covering part of the house. If this was being drawn by OpenGL, the house would be draw first, then the tree, so that it would cover the house properly. My current algorithm takes the average Z position (depth) of each object and puts those in order. But it glitches often, so I need a better way.

Anybody have any ideas? Basically, I'm dealing with only triangles, as all polygons are broken up into triangles before rendering, and the triangles are rendered individually. The triangles are expressed as 3 coordinates, one per vertex, and a coordinate is in three dimensions. I don't care about triangles passing through other triangles, these can be ignored. The algorithm must be fast.

Thanks,
Hardmath

Last edited by Hardmath123 (2012-04-22 06:59:40)

DigiTechs · 2012-04-22 07:01:33

Tall order there.. Sadly I can't help since I'm not as advanced at scratch...

roijac · 2012-04-22 07:29:27

if you don't care about crossing triangles, maybe just take the deepest point?

Hardmath123 · 2012-04-22 08:04:30

No, see, that's why this is tricky: the deepest points could point to a different triangle than which one is in front in reality; and I can think of a counterexample right now.

EDIT: http://www.imgpaste.com/PZhF.png

Last edited by Hardmath123 (2012-04-22 08:07:59)

rookwood101 · 2012-04-22 08:36:51

I think maybe http://en.wikipedia.org/wiki/Z-buffering would be useful for you. What the article is trying to say (I think) is that you should save the z value for each pixel (or at least very small sections of the screen) and when drawing over each area, take the z value of the pixel and compare to see if it should be drawn over.

I'm not sure this would work though with the scratch method of doing 3D (although I do not know your method) but this seems to be what is done in the industry.

LS97 · 2012-04-22 08:52:37

I'll try to figure out some formula. Meanwhile, this project I made in a couple minutes could help you a bit while trying it out?

The formulae should be edited in the stage. The rest is just graphics.

Last edited by LS97 (2012-04-22 08:56:46)

LS97 · 2012-04-22 09:14:12

I think I may have got it! I didn't take into account all three dimensions but rather just a selected depth (which you could possibly obtain through another formula if needed).

What I did was calculate the point at which the triangle, from a bird's eye view, would intersect the z-axis (which is also the eye's direct horizontal view).

The one that intersected the axis at the closest point was put first in the order. You can see it in my latest project, http://scratch.mit.edu/projects/LS97/2487188.

The project uses a modified version of the point-slope formula: y - y1 = m (x - x1)
where x is always 0 (a.k.a. the axis).

Oh, and for the confused, these x and y are on a plane. In 3D, x would be x and y would be z. y isn't really taken into account smile

Last edited by LS97 (2012-04-22 09:14:34)

Hardmath123 · 2012-04-22 10:07:18

Thanks, it works! big_smile But how does it work if the triangle does not cut the z axis? Does it extend it? And if so, won't that change results? hmm

Hardmath123 · 2012-04-22 10:09:09

Yeah, it does, check this out: imgpaste.com/Teox.png. sad But your fundamental idea looks good, I'm sure it can be adapted.

LS97 · 2012-04-22 10:40:43

Hardmath123 wrote:
Yeah, it does, check this out: imgpaste.com/Teox.png. But your fundamental idea looks good, I'm sure it can be adapted.

True, I forgot to tell you that since it checks the slopes, it assumes the lines are continuous. To make the engine really perspectively accurate, it would need to repeat the same process many times for different axes of view. However since we do not have the resources to do so in Scratch, we'll just have to find a way to pretend wink

Hardmath123 · 2012-04-22 11:04:17

...
So I'm back where I started.

Another thing: You're ignoring the third vertex (with a third Z coordinate) completely. hmm

LS97 · 2012-04-22 11:59:43

Hardmath123 wrote:
...
So I'm back where I started.

Another thing: You're ignoring the third vertex (with a third Z coordinate) completely.

Yes I was aware of that. it would be ideal to get the depth of the point where the plane (the triangle) intersects the z-axis, but I would have to think about that one.

blob8108 · 2012-04-22 15:04:12

I have the equation for intersecting a line with a plane somewhere -- would that help?

Edit: darn, I don't think it would. This is a very difficult problem. tongue

Last edited by blob8108 (2012-04-23 05:36:33)

Hardmath123 · 2012-04-23 07:56:04

UPDATE: Right now I'm making do by breaking up triangles into smaller ones, but am still waiting for a good algorithm from someone.

nathanprocks · 2012-04-23 08:11:39

So if we use GL in Scratch, it makes it easier to make 3D games?

Hardmath123 · 2012-04-23 08:38:17

Here's what hapenned with LS97's method: www.imgpaste.com/Mo9r.png.

@nathanprocks: Well, it's a bit slow for a true-to-heart 3D game, but in theory, why not?

LS97 · 2012-04-23 11:45:38

Hardmath123 wrote:
Here's what hapenned with LS97's method: www.imgpaste.com/Mo9r.png.

Obviously figuring out a solution in 2 dimensions wasn't the right way to take. Maybe we could try applying something to planes, instead of lines and segments? The basic calculations should still be the same!

Hardmath123 · 2012-04-23 12:15:28

Yeah, and we also need to deal with the "if-you-extend-lines-stuff-goes-wrong" aspect. Just a thought experiment: can you think of a counterexample for the following algorithm: the triangle which has the closest (frontmost) vertex is in front?

EDIT: Yeah, I can... sad

Code:

    /
   /
  /
 / --
/
     *
(look from the *)

Last edited by Hardmath123 (2012-04-23 12:18:38)

blob8108 · 2012-04-23 13:46:15

Given a point on the same plane as the triangle, could you determine whether it was inside the triangle or not?

Hardmath123 · 2012-04-26 08:57:19

bump

ftf841 · 2012-04-26 09:26:29

this belongs in the help with scripts fourm.

Paddle2See · 2012-04-26 09:37:11

ftf841 wrote:
this belongs in the help with scripts fourm.

No, I don't think so. It's not a scripting problem, it's a math problem (and not an easy one).

Scratch

archived forums

#1 2012-04-22 06:59:26

I need math help (3D geometry)

#2 2012-04-22 07:01:33

Re: I need math help (3D geometry)

#3 2012-04-22 07:29:27

Re: I need math help (3D geometry)

#4 2012-04-22 08:04:30

Re: I need math help (3D geometry)

#5 2012-04-22 08:36:51

Re: I need math help (3D geometry)

#6 2012-04-22 08:52:37

Re: I need math help (3D geometry)

#7 2012-04-22 09:14:12

Re: I need math help (3D geometry)

#8 2012-04-22 10:07:18

Re: I need math help (3D geometry)

#9 2012-04-22 10:09:09

Re: I need math help (3D geometry)

#10 2012-04-22 10:40:43

Re: I need math help (3D geometry)

Hardmath123 wrote:

#11 2012-04-22 11:04:17

Re: I need math help (3D geometry)

#12 2012-04-22 11:59:43

Re: I need math help (3D geometry)

Hardmath123 wrote:

#13 2012-04-22 15:04:12

Re: I need math help (3D geometry)

#14 2012-04-23 07:56:04

Re: I need math help (3D geometry)

#15 2012-04-23 08:11:39

Re: I need math help (3D geometry)

#16 2012-04-23 08:38:17

Re: I need math help (3D geometry)

#17 2012-04-23 11:45:38

Re: I need math help (3D geometry)

Hardmath123 wrote:

#18 2012-04-23 12:15:28

Re: I need math help (3D geometry)

Code:

#19 2012-04-23 13:46:15

Re: I need math help (3D geometry)

#20 2012-04-26 08:57:19

Re: I need math help (3D geometry)

#21 2012-04-26 09:26:29

Re: I need math help (3D geometry)

#22 2012-04-26 09:37:11

Re: I need math help (3D geometry)

ftf841 wrote:

Board footer