Return to Level1Techs.com

Porting a Raytracer to Rust - Devember Challenge

devember2k18

#1

I am already a pretty experienced dev, but have awful discipline with finishing projects, so this Devember challenge is to work for a solid month on one of the more bitter projects I bit off.

I am porting a 2D Raytracer called HQZ to rust, with the intention of then optimising it to be able to run in real time (given enough cores). This is an uphill battle as the aged C++ code base I am working on has not been maintained in years, and is single threaded, and not optimised for speed.

Aditionally as I am porting to rust I am working to restructure the program flow to be more functional in design and be clearer to follow execution, in an attempt to ease optimisation later.

Here is a sample of what the existing codebase can do: Video Link

I will be keeping the blogs short as my time is limited and I want to focus on the code.

For those wanting to follow along with my ramblings I will be making regular references to both my own repo and the source I am porting from.

The original HQZ can be found here

My Repo can be found here (not always up to date)


#2

Day 01:
Its Saturday, and I have 20 mins to myself, I think I should put some time into one of my projects. I pick up my HQZ implementation I haven’t touched in months cos its bugging me that its still just a skeleton. I start reading my code… the foundation models are sound, but the functions are a mess… This is gonna take a time investment.

“Thankfully” the night’s movie sucks, and I spend the next hour-fourty reading code instead of actually watching the movie on the TV… yes I am understanding where I was… why was I trying to solve algorithmic problems when so much of the foundation is missing? I keep reading, no code written tonight.


#3

Day 02:
Hey did you hear about this thing called Devember? Yea I actually learnt about Devember on day 2. Well if anything the challenge can serve as motivation.

With my existing codebase reunderstood, it was time to actually get to work…

Last time I was working on this I was trying to patch a quadtree library into my program to solve the actual ray collision problem. This is probably gonna work, but the work was premature. Before I can make decisions about that I need a framework to run the render from. So the evening was spent porting several rendering functions to rust, including implementing a Ray class.


#4

I was hoping you meant Rust the game. Oh well.


#5

Day 03:
What do I do about the IntersectionData class?..

So this thing has been a thorn in my side since the project started back in March. IntersectionData is a transient struct that contains a bunch of random variables that are passed around the existing C++ code, ultimately handling ray collision state. Needless to say this state-fullness is really un-functional, and doesn’t map neatly into rust. Heck it doesn’t map neatly in C++.

I could copy this verbatim from the original version, but I think I can do better. I think if done right collision state should be local to ray. Once a ray has collided it spawns a new ray… so why does this need a different struct?

I spent today’s coding time tinkering with a few ways of structuring this.

One of the conditions of Devember is publishing the code. For its entire life this project has lived in a private gitlab repo. I am not sure where I want to publish it, or if at all… but I will need to find a good way of allowing people to look at the code and follow along, else this is meaningless ramblings.


#6

I added the devember tag to your thread so it would show up in the list.

If you haven’t already, add yourself to the participant list in the second post of the #devember2k18 thread.

Thanks!


#7

Day 04:
It’s lunch time, uni is boring me, and I have made a decision, the intersection data is gonna cause more pain, I’m gonna drop it. Of course this means I need to restructure the program flow through the collision logic; but first I have to understand the program flow in the the collision logic.

RN I wish I had a notebook I could start sketching program flow into, to start with I think I want a printout of the functions. Does anyone know a good program for printing source code?


So post lunch I realised that I have a pretty good notebook for tearing apart the source and adding some notes. I have jupyter instance tucked away in my intranet, so I started dismantling renderer flow and splicing the relevant bits of code into a workbook.

Jupyter isn’t ideal for this sort of work, but its better than a paper version.


Unrelatedly, I am also thinking about dying my hair blue!


#8

Late on Day 04:
So pulling apart the old C++ source in jupyter bore fruit. I made a few discoveries that are starting to crack this wide open. I already knew that the objects in the scene are stored in a quadtree. With the help of my notbook I discovered:

  • Where the collision detection logic happens,
  • What the public interface of the quadtree is,
  • The “Quadtree” is actually a funky binary tree, where the orientation of each node flips from horizontal to vertical each time the tree descends a layer.

So far from my dismantling of the code I have found collision detection logic spanning across at least 5 files. This certainly isn’t the easiest to work with, and pulling functions all into one page of a notebook is a massive stress off my memory.

I am definitely putting more than an hour a day into this… does that by me credit for later? Similarly blogging about my findings is really motivating progress, even if no one is reading this.


#9

Lol I have been reading them all. I don’t understand any of it but I like the reading.


#10

I guess I need to be clearer in my ramblings.


#11

Not at all. I am not a programmer or anything close. I just like reading about people working out problems and what happens next.

And this had the added benefit to my brain of potentially yielding something visually pleasing at the end too.


#12

I am hoping for the same :wink:
The daily commitment is kind of hard. Usually I do things like this in like 6 hour blocks at a time and then wait for the next weekend.


#13

Day 05:
and I am stumbling in the dark… My server crashed and I lost access to my jupyter… But still I made some strong progress. My findings from last night meant I had open in my IDE the central collision detection algorithm. We can switch from disassembling back to building.

For those following along at home objects are defined in HQZ as a sequence of lines and arcs. each Object in the code is actually a single one of these arcs. With everything being defined as vectors calculating the hit is actually a pair of simultaneous equations.

y1 = ax1 + b
y2 = cx2 + d

therefore 
ax + b = cx + d 
and
(y - b)/a = (y - d)/c
solve for x and y

Boring math over

So the original HQZ source has a (very uncommented) implementation of the hit algorithm, given I am trying to recreate the original work not solve the problems from scratch, so I copied the algorithm verbatim.

I have a growing dread with every function I write that I am building an untestable mess. I am not well practiced at writing tests, and I have no idea how I am gonna debug this 300-odd line mass of simulation code.

If anyone has any strategies for designing unit tests please let me know.


#14

Good luck OP!


#15

Unfortunately I have no idea, but I would also like to know.
@AdminDev What is a good real world strategy for testing code? Do unit tests make sense?


#16

Integration testing might work better, unit testing is more for functions.

Why not both?

Also:

https://doc.rust-lang.org/book/second-edition/ch11-03-test-organization.html


#17

Thanks!

How best to go about that and at which point does it make sense to write tests? I have to admit I have never written tests before. Most of the time I write stuff, test it manually and never touch it again.


#18

Disclaimer, my current role, passion, and LOVE is about facilitating the environment and releasing the code after the tests have passed. With that said:

Agile methodology and, to an extent, DevOps philosophy implement testing during the development phase. QA, testing, security, etc. is all done during development. There are different approaches and opinions on exactly where, how, and why the testing is done, but it’s never too early to start thinking and writing tests.

So, how to go about that, read about testing in your language or framework and start small.

Second, what point does it make sense to write tests, as soon as you know you’re going to release this into a dynamic environment.


#19

I am not new to the DevOps mindset, and agree that testing is a core part of the development cycle.

Rust has a closely embedded testing framework written right into the compiler toolchain. Its great,

My question is less “how do I write tests” more “how do I design tests to test the code effectively” its more of a question of how to think about the problem effectively


#20

Ah, that is outside the scope of my expertise. In my (limited) experience writing tests, I typically write something to a file or database, and then read that content and make sure the data is correct, as one example.

An array of strings consisting of 20 names, write to a file, read from the file, is the length of the array 20? Great!

Server is listening on 3000, start the server, does localhost:3000 return 200 OK? Hooray!

Things like that are what I usually do when writing my own stuff. But, I am still a junior in that respect.