The shoutbox is currently out of service. Join us on Discord instead.
You can help CodeWalrus stay online by donating here.

X3D - A 3D engine for TI68k & Nspire Calculators

Started by catastropher, June 27, 2015, 02:37:43 am

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

TheMachine02

Quote from: ben_g on January 17, 2016, 01:06:11 pm
From your explanation, I think you always clip against a polygon defined as a set of vertices, right? While this probably is no problem at all for computers and more powerfull calculators, I wonder if filling that polygon on a seperate 'clipping' buffer and then drawing lines using a modified OR-logic could speed the engine up on z80 calculators, especially if you limit all portals to squares, since the calculations required for clipping tend to be quite slow on that platform.

Since drawing filled polygons is also quite slow on that platform, it may be a stupid idea though.


Actually, it is possible. Filling the portal onto a buffer, and use and logic to draw line is pretty much fast. It is only one poly/portal that need to be filled, altough a fast clear buffer is also need. It also take care of recursive portal with drawing the new portal taking into account the old portal with and logic too. I had played with this quite a bit, and this may the only possible solution to hace portal on z80. Standard clipping is just out of question, it is muchhhhhh too slow.

Btw, X3D is pretty much impressive. Keep up the good work !

catastropher

Quote from: DJ Omnimaga on January 17, 2016, 08:11:10 am
I don't understand 3D but looking at this screenshot, I like visualizing how the 3D is rendered line by line :) . Also good move to make such screenshot after explaining, since some people are more visual and understand better with animations and pictures. :)

Thanks! I tried explaining it with just text at first and it was impossible haha

Quote from: Vogtinator on January 17, 2016, 11:21:19 am
Does that mean that "freestanding" polygons aren't possible with X3D?

No, they are possible using one of two methods. You can either clear the portal polygon before rendering or you can first use the portal as an "anti portal" and clip the lines already processed so that parts inside the portal are removed (this may generate an extra line). Depending on how many lines are being drawn and how big the portal polygon is, either may be faster. Neither is currently implemented, but they will be in the future :)

Quote from: Vogtinator on January 17, 2016, 11:21:19 am
Hm, doesn't that mean that you convert back and forth between a array of points and an array of scanlines?

Yes, but only for the portal polygons. The conversion algorithm is very fast (it's the filling that is slow). The main reason for using this though, is that polygon-polygon intersections can be done really really fast. At first, I used sutherland-hodgman clipping algorithm, but for every portal in the scene that had a complexity of O(n^4). I came up with an algorithm in the summer that got it down to O(n^3). The new algorithm can do the intersection in O(n + log n) for each polygon, for a total of O(n^2) for the entire scene. Also, since it's convex we don't have to split it into triangles: we can generate one clipping region because of the polyline property.

Quote from: Vogtinator on January 17, 2016, 11:21:19 am
Why two rotations and dotproducts? As I see that you're basically copying the room the target portal is in behind the view portal, isn't one rotation and one translation enough,
so one matrix multiplication/rotation and one addition/translation?

This one is ever harder to explain without a picture. I'll draw a picture a bit later to show why this is.

Quote from: Vogtinator on January 17, 2016, 11:21:19 am
How are matrices implemented? Using proper 32-bit floats, 32-bit fixed-point or entirely different?

Matrices are 3x3 0.16 fixed-point numbers (1 is approximated as 0.9999). This is because the 68k only has native multiplication for two 16 bit numbers.

Quote from: Vogtinator on January 17, 2016, 11:21:19 am
Yep, it does! Thanks :)

Glad I could help! :D

Quote from: ben_g on January 17, 2016, 01:06:11 pm
From your explanation, I think you always clip against a polygon defined as a set of vertices, right? While this probably is no problem at all for computers and more powerfull calculators, I wonder if filling that polygon on a seperate 'clipping' buffer and then drawing lines using a modified OR-logic could speed the engine up on z80 calculators, especially if you limit all portals to squares, since the calculations required for clipping tend to be quite slow on that platform.

The problem is, 3D projection can give you lines that are thousands of pixels long when they are close to the camera. So, no matter what you're going to have to clip the line to the screen. Normal clipping requires multiplication and possibly division for the clipping, whereas my clipping algorithm does a binary search by calculating the midpoint of the line (two additions and two right shifts by 1). This requires the x_left and x_right position for each scanline though. For such a small screen, this should be pretty fast to calculate. I have experience with Z80 assembly, so maybe one day I'll give it a try.

Quote from: TheMachine02 on January 17, 2016, 02:34:43 pm
Actually, it is possible. Filling the portal onto a buffer, and use and logic to draw line is pretty much fast. It is only one poly/portal that need to be filled, altough a fast clear buffer is also need. It also take care of recursive portal with drawing the new portal taking into account the old portal with and logic too. I had played with this quite a bit, and this may the only possible solution to hace portal on z80. Standard clipping is just out of question, it is muchhhhhh too slow.

Do you actually fill the portal polygon though? Using the method I described, you don't need to actually draw the portal.

Quote from: TheMachine02 on January 17, 2016, 02:34:43 pm
Btw, X3D is pretty much impressive. Keep up the good work !

Thanks! :D

By the way, I'm not sure if this is clear, but X3D never actually tries to draw lines that are invisible, nor does it ever fill in the portals. There were just part of the visualization :)
Creator of X3D, a 3D portal rendering game engine for Nspire, 68k, and PC

DJ Omnimaga

That's good I guess about not drawing lines that are invisible. I assume it would be a waste of CPU resources. :P

TheMachine02

Quote from: catastropher on January 17, 2016, 03:54:28 pm
Do you actually fill the portal polygon though? Using the method I described, you don't need to actually draw the portal.


Yeah, there is filling. But of course the method you described with scanlin clip without drawing can works too. The only thing is that on z80, scanline conversion is what take the most of time. The pur fulling part may only be 50% of the whole triangle filling routine.

Quote from: catastropher on January 17, 2016, 03:54:28 pm
The problem is, 3D projection can give you lines that are thousands of pixels long when they are close to the camera. So, no matter what you're going to have to clip the line to the screen. Normal clipping requires multiplication and possibly division for the clipping, whereas my clipping algorithm does a binary search by calculating the midpoint of the line (two additions and two right shifts by 1). This requires the x_left and x_right position for each scanline though. For such a small screen, this should be pretty fast to calculate. I have experience with Z80 assembly, so maybe one day I'll give it a try.


However, 3D projection on z80 tend to overflow quite a bit. Do you handle overflow at all ? And yup, binary search is quite efficient in numerous case for 3D.

catastropher

Quote from: TheMachine02 on January 18, 2016, 06:14:03 pm
However, 3D projection on z80 tend to overflow quite a bit. Do you handle overflow at all ? And yup, binary search is quite efficient in numerous case for 3D.

Currently not, clipping against the near plane and having points as 16-bit ints seems to not cause any trouble.

So, there have been numerous changes to X3D since I last posted, but one of the most visible changes is the ability to add fog (ignore the graphical glitches :P):

X3D Fog: ShowHide


This will come in handy when we make Portal, as there tends to be a lot of deep chasms :)
Creator of X3D, a 3D portal rendering game engine for Nspire, 68k, and PC

DJ Omnimaga

Wait... how is that even possible? O.O Great job on that fog effect. Looks pretty smooth too. Does this allow you to not have to draw stuff far away and thus, increase speed? Also are you able to make the fog a different color than the rest of the screen or is that out of the question?

Also for which platform is that screenshot from?

pimathbrainiac

Looks really nice! How are you calculating render distance/fog, if I may ask? I've been trying to work that out for a while on an old project of mine.
Well, I'm bach here too!

alexgt

Nice, like the fog a lot. How did you do that btw

ben_g

Quote from: DJ Omnimaga on January 26, 2016, 07:04:23 am
Wait... how is that even possible? O.O Great job on that fog effect. Looks pretty smooth too. Does this allow you to not have to draw stuff far away and thus, increase speed? Also are you able to make the fog a different color than the rest of the screen or is that out of the question?

Also for which platform is that screenshot from?

My guess would be that he calculates the depth of the line and uses  that as an opacity value. Having fog that has a different colour than the walls would only work when you either fill the walls or have a way to render the fog as a volume, both of which would be way more heavy.

Ivoah

How is the screenshot in color? Aren't all of the 68k calcs b/w?

catastropher

Hey thanks for the encouragement everyone! Since a bunch of people asked, I'll just answer all at once. As @ben_g speculated, I did something similar to alpha blending. The current implementation of "fog" only works for black though. It works as follows:

  • Define a min_dist and max_dist. At min_dist, a color at full brightness and by max_dist, it is completely black

  • Using linear interpolation, assign a color to each vertex by scaling the color based on its depth (the Z value after points have been translated/rotated to the camera)

  • Call a modified line drawing routine that interpolates between the vertex colors as it draws the line


This gives the illusion of fog/darkness, though it isn't "true" fog. The idea is really that things become darker as their depth increases; thus, it really isn't suitable for other colors.

Now, on to other questions!

Quote from: DJ Omnimaga on January 26, 2016, 07:04:23 am
Great job on that fog effect. Looks pretty smooth too. Does this allow you to not have to draw stuff far away and thus, increase speed?

Indeed! This is one of the few cool visual effects that actually decreases the amount of work done by the renderer haha

Quote from: DJ Omnimaga on January 26, 2016, 07:04:23 am
Also for which platform is that screenshot from?

It's still running on PC, but I'm hopefully going to get the NSpire port up and running pretty soon. All of the algorithms have been designed to be really fast, all math is done without floating point,  and obviously, most of what's drawn is lines :)

Quote from: Ivoah on January 27, 2016, 04:08:09 pm
How is the screenshot in color? Aren't all of the 68k calcs b/w?

Indeed, the name "X3D-68k" has become a bit of a misnomer as the library is now being designed to be cross-platform. I'll post some screenshots from other platforms as I get the engine ported :)

Oh, and surprise, X3D has its first solid object! :D

X3D Solid Object: ShowHide
Creator of X3D, a 3D portal rendering game engine for Nspire, 68k, and PC

DJ Omnimaga

This looks cool. Didn't it have solid moving cubes a while ago, though? Or were they just part of the map?

I would definitively like screenshots of the engine running on a TI-Nspire and TI-84 Plus CE. :) Also the CE supports multiple color depths apparently.

catastropher

Quote from: DJ Omnimaga on January 28, 2016, 04:01:08 am
This looks cool. Didn't it have solid moving cubes a while ago, though? Or were they just part of the map?

Thanks! Actually, the bouncing cubes in previous versions were wireframe. This is the first solid thing that can move :D
Creator of X3D, a 3D portal rendering game engine for Nspire, 68k, and PC

DJ Omnimaga

Ah, right. If you ever make a small game (eg a puzzle platformer) using this engine to showcase it, then there should be a puzzle with moving platforms and if you fall down you die in the pit :P

catastropher

Quote from: DJ Omnimaga on January 28, 2016, 04:55:51 am
Ah, right. If you ever make a small game (eg a puzzle platformer) using this engine to showcase it, then there should be a puzzle with moving platforms and if you fall down you die in the pit :P

Sounds like a good idea! I have several plans for games that will use the engine once it's done :)

I know I've been posting updates quite a bit, but it helps keep me motivated... so here's another update  ;D

Latest changes include:

  • The ability to actually walk between rooms

  • Numerous bugfixes for the renderer

  • Functionality to create more complex level geometry (e.g. the "pipe" in the ceiling of the screenshot)

  • The ability to create wall line art that's attached to the wall (the 'X' in the screenshot is an example)

  • Ability to have multiple solid objects in the same room (though this needs to be optimized)


Here's a (bug filled) demo. Note that the dimming of the lines in the pipe is due to a clipping bug:

X3D Update: ShowHide


As always, thanks for the support guys! If you have any feature requests, let me know!
Creator of X3D, a 3D portal rendering game engine for Nspire, 68k, and PC

Powered by EzPortal