This is quite an advanced topic so I hope answers will be serious and involve a good explanation. Thank you!

I've created a wireframe 3D engine (does not fill in, I think that will be too laggy and difficult to implement) for rendering complex 3D objects. Essentially the program reads .obj files and draws them on Scratch. I have everything all set except for one thing:

I want to hide lines that are underneath another face.

For example, consider the two 3D cube renderings
http://unisci24.com/data_images/wlls/13/215273-cube.jpg
and
https://upload.wikimedia.org/wikipedia/commons/thumb/e/e7/Necker_cube.svg/220px-Necker_cube.svg.png
In one, you can see the lines on the “other side” of the cube. In another, you don't. Those lines are hidden.

I want to make my program draw the lines and stop them when needed so that it creates what looks like image 1. I haven't released my program yet and I probably won't till I get this fixed.

It would be nice to get some pseudo-code/explanations of how this can be done. Thank you for your time.

If there's a moderator listening could you move this to the AT forum? - more chance of a substantive reply…

Here is a hacky way to do it… draw from back to front (painter's algorithm) and when you draw a face, as well as drawing the outline, draw the face itself solid in background colour. It'll look like wire frame from the way you draw the edges but things drawn behind a face will be hidden by the fill-in.

I'll leave it to others to describe non-hacky ways to do this.

gtoal wrote:

Here is a hacky way to do it… draw from back to front (painter's algorithm) and when you draw a face, as well as drawing the outline, draw the face itself solid in background colour. It'll look like wire frame from the way you draw the edges but things drawn behind a face will be hidden by the fill-in.

I'll leave it to others to describe non-hacky ways to do this.

But that requires a filler, which is quite laggy for n-sided polygons?

gtoal wrote:

If there's a moderator listening could you move this to the AT forum? - more chance of a substantive reply…

Requested

AiyanMind wrote:

But that requires a filler, which is quite laggy for n-sided polygons?

No, you should be able to fill most shapes reasonably efficiently. There are a lot of really fast fill projects on Scratch that you can borrow. If your polygons are all regular polygons then it's trivial using a triangle filler like DadofMrLog's. If they include concave sides it's trickier but I think there are some examples in the Graphics101 studio.

How does the painter's algorithm which faces to “paint” first? Equations?

AiyanMind wrote:

How does the painter's algorithm which faces to “paint” first? Equations?

you'll need your face information to be sorted in depth order - farthest away first. with luck you already have it in a data structure that supports this - if not, you'll need an intermediate stage where you pretend to display all the faces in whatever order you have them in, but instead of drawing them, you save the face data to an array and then you sort the array. It may be simpler to save the data from after you've decomposed the faces into, say, triangles, rather than as the basic faces - if there are multiple types of faces. That way your array is of all one type of object and is easier to sort.

gtoal wrote:

AiyanMind wrote:

How does the painter's algorithm which faces to “paint” first? Equations?

you'll need your face information to be sorted in depth order - farthest away first. with luck you already have it in a data structure that supports this - if not, you'll need an intermediate stage where you pretend to display all the faces in whatever order you have them in, but instead of drawing them, you save the face data to an array and then you sort the array. It may be simpler to save the data from after you've decomposed the faces into, say, triangles, rather than as the basic faces - if there are multiple types of faces. That way your array is of all one type of object and is easier to sort.

Hmm you say sort the array. What algorithm do I need to use to order them?

I would suggest that you start by implementing back-face culling (if you haven't already). That will reduce the number of surfaces that you need to worry about (i.e. for both sorting and drawing) and so make it significantly quicker. –Though this does assume that your objects are closed (i.e. you cannot see ‘inside’ to the ‘reverse’ side of the faces).

Also, if all of your objects are closed convex polyhedra then you don't need to order the faces at all. Instead, you only need to order the drawing of the individual, distinct (i.e. separate) objects (assuming that there is always a possible way to order them so that you can draw them with the correct overlap – in particular, that the objects don't intersect each other).

Even if your objects are not convex polyhedra (but still closed), you may be able do a decent job using above method (i.e. just back-face culling and object-ordering) by splitting such polyhedra into multiple convex polyhedra (and ignoring the fact that they are no longer closed, since they still remain closed once all joined up, so you should never get to see ‘inside’ to the reverse sides of the faces).

If your objects are not closed convex polyhedra, and they will never intersect, nor have large enough dimensions compared to the gaps between them to overlap in ways that make it impossible to find an order for the drawing, then I would still recommend that you start by ordering the objects, and then order the faces within each (non-convex/non-closed) object.

If the objects do have large enough dimensions compared to gaps between that cause your distance-sorting algorithm to not always give the correct drawing order (which may be the case if you're splitting non-convex polyhedra into several convex), then you can often ‘help’ the distance algorithm by adding some ‘ghost nodes’ (as I call them) – these are nodes which are not part of any face of the object, but they do count towards the distance calculation (e.g. if you're taking the distance to the centroid of the object's nodes), so allowing you to ‘weight’ it in some direction(s).

If you have the worst case of objects that intersect then that's where it starts to get truly difficult…

DadOfMrLog wrote:

I would suggest that you start by implementing back-face culling (if you haven't already). That will reduce the number of surfaces that you need to worry about (i.e. for both sorting and drawing) and so make it significantly quicker. –Though this does assume that your objects are closed (i.e. you cannot see ‘inside’ to the ‘reverse’ side of the faces).

Also, if all of your objects are closed convex polyhedra then you don't need to order the faces at all. Instead, you only need to order the drawing of the individual, distinct (i.e. separate) objects (assuming that there is always a possible way to order them so that you can draw them with the correct overlap – in particular, that the objects don't intersect each other).

Even if your objects are not convex polyhedra (but still closed), you may be able do a decent job using above method (i.e. just back-face culling and object-ordering) by splitting such polyhedra into multiple convex polyhedra (and ignoring the fact that they are no longer closed, since they still remain closed once all joined up, so you should never get to see ‘inside’ to the reverse sides of the faces).

If your objects are not closed convex polyhedra, and they will never intersect, nor have large enough dimensions compared to the gaps between them to overlap in ways that make it impossible to find an order for the drawing, then I would still recommend that you start by ordering the objects, and then order the faces within each (non-convex/non-closed) object.

If the objects do have large enough dimensions compared to gaps between that cause your distance-sorting algorithm to not always give the correct drawing order (which may be the case if you're splitting non-convex polyhedra into several convex), then you can often ‘help’ the distance algorithm by adding some ‘ghost nodes’ (as I call them) – these are nodes which are not part of any face of the object, but they do count towards the distance calculation (e.g. if you're taking the distance to the centroid of the object's nodes), so allowing you to ‘weight’ it in some direction(s).

If you have the worst case of objects that intersect then that's where it starts to get truly difficult…

Here is my project. https://scratch.mit.edu/projects/158258509/
Any specific ideas? A bit laggy right now

AiyanMind wrote:

Here is my project. https://scratch.mit.edu/projects/158258509/
Any specific ideas? A bit laggy right now

Yeah… first thing would be to fix the “set y to tpz” bug you have (twice) in the “process into 2D coords” custom block script – that certainly causes some really odd behaviour as points move towards top/bottom of screen.


After that, you should probably include some kind of clipping for points that go behind the viewer (otherwise it'll create a mess when lines pass behind the viewer).

With the current wireframe system that's easy – you just need to define a minimum projected point cutoff plane (z=1, say), and then check if a line has both points behind that (in which case don't show any of it), or has just one point behind it (in which case, find where that line intersects the cutoff plane, and just draw from the frontmost point to that intersection point).

Once you start filling polygonal surfaces (which you will need to do for the hidden-line-removal in an object as ‘complex’ as the one you currently have), clipping becomes more complicated, since it means that you have to work out the part of the polygon that's on the far side of the clipping plane from the viewer (i.e. you chop off the part that's on the same side of the cutoff plane as the viewer, thus creating a different polygon that may even have one point more than the original polygon had).


More generally, though, I'm wondering what it is that you plan to do with the project..?

Do you intend to allow only a single object to be imported into a scene, or potentially multiple independent objects?

Also, when the user uses the keys and mouse, what do you think they are controlling? –Is it the object itself (i.e. rotating it with the mouse, and moving it with the keys), or is the user controlling their viewing position and angle? Or maybe it's a mixture of both at the moment? (So WASD controls the viewer's position, while cursor rotates the object – and you could then add cursor keys to control the viewer's azimuth and tilt angles?)

If the mouse is rotating the object (which is certainly how it feels to me at the moment), how are you intending to define the rotation point for an imported object (currently it is hardwired as the point x=y=z=300)? –Maybe you could have an extra unused point at the start of the .obj file, or maybe you could work out the centroid of the imported object's points, or maybe you could assume it's meant to be the origin (which means you have to shift your current model)…?


There are all sorts of other questions that are likely to come up, but that's enough for now…

I made an OBJ file renderer too!: https://scratch.mit.edu/projects/78830546/

I never got around to back-face-culling, since I assumed (perhaps incorrectly?) that the calculations would take more time than simply drawing the vertices anyway.

novice27b wrote:

I made an OBJ file renderer too!: https://scratch.mit.edu/projects/78830546/

I never got around to back-face-culling, since I assumed (perhaps incorrectly?) that the calculations would take more time than simply drawing the vertices anyway.

If you're only doing wireframe then it may not make a huge difference (though could well be still worth doing, since the fewer lines could make it much easier for the user to grasp what's happening on the screen). But if you're filling the surfaces, then it'll be way quicker to do the BF-culling (assuming the polyhedra are closed, but you can't properly rely on BFC if they're not, so…)

Drawing with the pen is relatively expensive in Scratch, and the more pen strokes you draw within a refresh, the longer and longer it takes for Flash to commit those pen strokes to the pen canvas at the next refresh – especially (for some unknown reason) if you end up overlapping parts that you've already drawn with pen (which you inevitably will do if you draw a backward-facing surface, since there must be a surface in front of it that you would also draw, since we're assuming the reversed face is part of a closed polyhedron).

The calculation for the orientation of the surface only involves a couple of multiplies and an add (once you have the 2d projected points, which you probably will if you're sensible and cache the rotated co-ordinates rather than applying the rotation to the same point multiple times when it is shared by multiple surfaces – AiyanMind, take note!), followed by a comparison that allows you to likely skip a significant proportion of the pen drawing.

TheLogFather wrote:

AiyanMind wrote:

Here is my project. https://scratch.mit.edu/projects/158258509/
Any specific ideas? A bit laggy right now

Yeah… first thing would be to fix the “set y to tpz” bug you have (twice) in the “process into 2D coords” custom block script – that certainly causes some really odd behaviour as points move towards top/bottom of screen.


After that, you should probably include some kind of clipping for points that go behind the viewer (otherwise it'll create a mess when lines pass behind the viewer).

With the current wireframe system that's easy – you just need to define a minimum projected point cutoff plane (z=1, say), and then check if a line has both points behind that (in which case don't show any of it), or has just one point behind it (in which case, find where that line intersects the cutoff plane, and just draw from the frontmost point to that intersection point).

Once you start filling polygonal surfaces (which you will need to do for the hidden-line-removal in an object as ‘complex’ as the one you currently have), clipping becomes more complicated, since it means that you have to work out the part of the polygon that's on the far side of the clipping plane from the viewer (i.e. you chop off the part that's on the same side of the cutoff plane as the viewer, thus creating a different polygon that may even have one point more than the original polygon had).


More generally, though, I'm wondering what it is that you plan to do with the project..?

Do you intend to allow only a single object to be imported into a scene, or potentially multiple independent objects?

Also, when the user uses the keys and mouse, what do you think they are controlling? –Is it the object itself (i.e. rotating it with the mouse, and moving it with the keys), or is the user controlling their viewing position and angle? Or maybe it's a mixture of both at the moment? (So WASD controls the viewer's position, while cursor rotates the object – and you could then add cursor keys to control the viewer's azimuth and tilt angles?)

If the mouse is rotating the object (which is certainly how it feels to me at the moment), how are you intending to define the rotation point for an imported object (currently it is hardwired as the point x=y=z=300)? –Maybe you could have an extra unused point at the start of the .obj file, or maybe you could work out the centroid of the imported object's points, or maybe you could assume it's meant to be the origin (which means you have to shift your current model)…?


There are all sorts of other questions that are likely to come up, but that's enough for now…

Many good questions, but I'm afraid I don't have many answers. I've set the rotation point at (300,300,300) because the model itself is built around that point. I'm not planning to make a program where others can import their own obj files (but then again, maybe I will). But there are way too many complications in .obj files such as vt, g (groups), s, etc. The program itself can handle at max 10,000 elements at extreme lag. Right now, I'm just doing this because I've never done it before. Haha.
When the user controls the mouse, they are rotating the object on the x and z axis. As for the extra controls, I've never thought of that much until now. I mostly want this project to be some sort of a 3d model viewer filled and shaded accordingly with no lag. It would be great if you could show me a way to get that to do that for this project.

Anyways, I've changed the “set y to tpz” bug in my main project. As for the clipping, so you want me to not render any lines with a z coordinate less than 1? Or is it greater than? Won't that render only a portion of the aircraft? Or is the back of it covered? I'm interested and I will see what happens.

Thank you very much for your time, it is precious.

Also, let's say my light source is my head and I am looking at my model. What is a good equation involving x,y,or z to set the pen shade. For example, right now I have “set pen shade to 60-(abs(z))/2”

Lastly, how would I go about shading in this project? How should I split a polygon into triangles, if I should use a tri-filler?

AiyanMind wrote:

As for the clipping, so you want me to not render any lines with a z coordinate less than 1? Or is it greater than? Won't that render only a portion of the aircraft? Or is the back of it covered? I'm interested and I will see what happens.

What I mean by “z” is the z co-ordinate of the rotated point relative to the viewer. At the moment you have your “z” variable worked out to be the z co-ordinate of the rotated point relative to the rotation point (plus TZ).

What you've done for your projection is 300-z, so I guess that's what you should be clipping. (I.e. if 300-z<1 then the point is too close, so you should start to clip in some way.)

Personally, I would forget the 300-z and consider using TX/Y/Z as either the viewer co-ordinates (if the viewer is moving when pressing the WASD keys), or else the object's rotation point co-ordinates (if you're going to assume the viewer remains at the origin while the object moves when pressing the WASD keys).

At the moment, you have it so it feels like the WASD keys are conflicting. Pressing A makes the plane move left (and D moves right), so it feels like you are controlling the plane's position. But pressing W makes the plane move down (and S moves up), so that makes it feel like you might be controlling your own position.


Sticking nearer to what you have at the moment, I'd get rid of the 300-z, just dividing by z, and start with TZ set to 300 or 400ish. Your depth shading will then become simpler too (since it should be based on that 300-z at the moment).


I would actually recommend that you make a custom block script which takes a 3d point and rotates it and shifts relative to the viewer.

It'd look something like this (hopefully got this right…)

(Note how I've reduced the use of temporary variables, and the number of operations, to help reduce the potential for lag. Also note that I've used variables for the sines and cosines of the angles, which you would recalculate whenever the actual angles get changed when dragging with mouse. That's because the angles are fixed for any given frame, so the sines and cosines are also fixed, and it's much quicker for Scratch to get the values of the variables than to perform the sine & cosine operations all the time.)

Your “process … into 2d coords” custom block could then be simplified to something like this:

With more work, this could be improved such that if only one of the two points is (almost) behind the viewer (i.e. only one of the 3dz's is less than 1) then it finds the intersection point of the line with the 3dz=1 plane, and so draw only that part of the line that's in front of the viewer (instead of not drawing anything for such a line).


TBH, though, I would suggest you apply the “rotate and shift” to all the co-ords in the “v x/y/z” lists just once, adding their rotated and shifted co-ords into lists (rather than putting into 3dx/y/z vars). Then you can reference those pre-computed co-ords directly when drawing the lines, rather than having to do the rotation+shift multiple times for a point that's shared by several surfaces.


As for splitting into tris, if you know that your imported object only has quadrilateral (and tri) surfaces, then it's easy (just cut a quad along one of its diagonals). –Having said that, if you implement clipping of surfaces by the 3dz=1 plane, then it's possible a quad surface can become a pentagon, so you have to split that too (but it's not hard if you draw it on paper, and keep track of the points of the three resulting tris). OTOH, if you split a quad into two tris, then you could split first and then apply the clip to the tris (and so only get a quad – which you could then split again into two tris knowing you don't need to clip those, since the quad was already clipped…)


For the filling, gtoal already mentioned my tri-fill project. It's here: https://scratch.mit.edu/projects/55619918/

As for shading, I'd recommend you have it based on angle of the surface normal relative to the direction to the viewer (from the surface's centroid). I think that's the quickest calculation that actually gives a decent-looking shading. Once you have the rotated+shifted point co-ords for the surface vertices (i.e. the ones I suggested you pre-compute into lists), all you need to do is to work out the z-component of the vector cross-product of normalised vectors along two sides of the surface (assuming they are not parallel). Then use something like “50+45*nz” for the pen shade, where nz is that z-component.


Hope all that lot makes some sense!

TheLogFather wrote:

AiyanMind wrote:

As for the clipping, so you want me to not render any lines with a z coordinate less than 1? Or is it greater than? Won't that render only a portion of the aircraft? Or is the back of it covered? I'm interested and I will see what happens.

What I mean by “z” is the z co-ordinate of the rotated point relative to the viewer. At the moment you have your “z” variable worked out to be the z co-ordinate of the rotated point relative to the rotation point (plus TZ).

What you've done for your projection is 300-z, so I guess that's what you should be clipping. (I.e. if 300-z<1 then the point is too close, so you should start to clip in some way.)

Personally, I would forget the 300-z and consider using TX/Y/Z as either the viewer co-ordinates (if the viewer is moving when pressing the WASD keys), or else the object's rotation point co-ordinates (if you're going to assume the viewer remains at the origin while the object moves when pressing the WASD keys).

At the moment, you have it so it feels like the WASD keys are conflicting. Pressing A makes the plane move left (and D moves right), so it feels like you are controlling the plane's position. But pressing W makes the plane move down (and S moves up), so that makes it feel like you might be controlling your own position.


Sticking nearer to what you have at the moment, I'd get rid of the 300-z, just dividing by z, and start with TZ set to 300 or 400ish. Your depth shading will then become simpler too (since it should be based on that 300-z at the moment).


I would actually recommend that you make a custom block script which takes a 3d point and rotates it and shifts relative to the viewer.

It'd look something like this (hopefully got this right…)

(Note how I've reduced the use of temporary variables, and the number of operations, to help reduce the potential for lag. Also note that I've used variables for the sines and cosines of the angles, which you would recalculate whenever the actual angles get changed when dragging with mouse. That's because the angles are fixed for any given frame, so the sines and cosines are also fixed, and it's much quicker for Scratch to get the values of the variables than to perform the sine & cosine operations all the time.)

Your “process … into 2d coords” custom block could then be simplified to something like this:

With more work, this could be improved such that if only one of the two points is (almost) behind the viewer (i.e. only one of the 3dz's is less than 1) then it finds the intersection point of the line with the 3dz=1 plane, and so draw only that part of the line that's in front of the viewer (instead of not drawing anything for such a line).


TBH, though, I would suggest you apply the “rotate and shift” to all the co-ords in the “v x/y/z” lists just once, adding their rotated and shifted co-ords into lists (rather than putting into 3dx/y/z vars). Then you can reference those pre-computed co-ords directly when drawing the lines, rather than having to do the rotation+shift multiple times for a point that's shared by several surfaces.


As for splitting into tris, if you know that your imported object only has quadrilateral (and tri) surfaces, then it's easy (just cut a quad along one of its diagonals). –Having said that, if you implement clipping of surfaces by the 3dz=1 plane, then it's possible a quad surface can become a pentagon, so you have to split that too (but it's not hard if you draw it on paper, and keep track of the points of the three resulting tris). OTOH, if you split a quad into two tris, then you could split first and then apply the clip to the tris (and so only get a quad – which you could then split again into two tris knowing you don't need to clip those, since the quad was already clipped…)


For the filling, gtoal already mentioned my tri-fill project. It's here: https://scratch.mit.edu/projects/55619918/

As for shading, I'd recommend you have it based on angle of the surface normal relative to the direction to the viewer (from the surface's centroid). I think that's the quickest calculation that actually gives a decent-looking shading. Once you have the rotated+shifted point co-ords for the surface vertices (i.e. the ones I suggested you pre-compute into lists), all you need to do is to work out the z-component of the vector cross-product of normalised vectors along two sides of the surface (assuming they are not parallel). Then use something like “50+45*nz” for the pen shade, where nz is that z-component.


Hope all that lot makes some sense!

Thank you. It will take some time for me to absorb this