Adventures in Learning How to Publish a Research Paper Part 1

So I’m in the process of trying to get a research paper published and wanted to share what I’ve learned so far. I’ll continue to write more beyond this post as I continue the process. Yes, I know my writing is terrible (grammar etc), please don’t take this as a representation of the final product ūüėõ

The world of published papers, journals and academia (not necessarily lumped into the same group) is a bit different than I expected. On the whole, I’ve found that it’s both more approachable than I expected, and less approachable than I expected, in different, unexpected ways.

Motivation

A handful of times in my life, I’ve come up with things, naiively thought that I had invented it, and then later found out that it already existed and was a known thing.

I’ve reached the point in my career and personal growth where I’m coming up with things that seem like finally, they may not actually yet be already known and exist.

A braver person may quit their job and start a software company and try to make it happen and then possibly fail 9 out of 10 attempts (hey look, im about to cite something that refutes that statement Washington Post: Do nine out of 10 new businesses fail, as Rand Paul claims?).

Maybe a more cunning, yet less adventurous person would try and patent their idea, then sell the patent, or wait for someone to intrude and then sue for damages. I don’t like the idea of patenting my ideas or techniques because honestly, I want other people to do things with them, I just want to be the first, and I want people to know I was the first (petty perhaps but at least I’m being honest haha).

I happen to be taking perhaps the least risky road, but seemingly most altruistic path (more info on that later), and am thinking about publishing my techniques in a research journal of an appropriate field. This way, everyone is free to use it, and I can see what other people do with it – if anything. I will be known as “the guy who came up with this”, but probably won’t ever actually get to use it in my actual job. Boo-hoo! (we’ll see I guess…)

You never know though… having published papers definitely ought to lead to better career advancement opportunities, and frankly, maybe some dream job will come along where I get to work on these topics I’m publishing about, and do some cutting edge research towards practical results, and push the envelope of what people think can be achieved with current technology. That would be pretty cool! If you are a game (or related) company that is heavy in research, and also practical results, working within the realm of real time raytracing, unorthodox graphics techniques, VR, and other cool tech, and interested in a dude such as myself, drop me a line. I’m happy where I am but never hurts to chat and network (;

Anyhow, with a 1 year old baby, a house payment, and the like, I need the stability. I can’t go starting a new company so a research paper it is!

A quick note to my son Loki, if he reads this in the future, a nice little time capsul for him ūüėõ

Hello Loki! I love you very much and I hope you are doing well. Your initials are LZW which is a compression algorithm, and your namesake is the norse god of mischief. Your mom is a super smart psychologist, so I hope we’ve taught you well and that you are now a Robot Psychologist AI developer who somehow furthered the works of chaos theory for AI and data compression. Or… you can play guitar at starbucks. Whatever makes you happy (: Talk to you later – dad. PS bring me a beer pls!!

Misconceptions Untangled

Once the decision of publishing in a journal was made… it was time to figure out what the heck academia / research papers were all about. As a near high school drop out with no degree, all I really know is what my near PHd wife (educational psychology) and more educated friends and family have told me.

Here were some of my misconceptions when I started out:

  • Publishing a paper is not for the likes of a mere mortal like me
  • When a paper makes a statement backed by a reference to something else that says so, that is irrefutable evidence that it is fact.
  • Publishing papers is all about advancing science, and perhaps a bit about one’s ego, but not at all about money
  • When you publish something, it has to be new. In fact, it has to be so novel that it can’t be like anything else written EVER.
  • Google ought to be great at helping me find other related work that i can reference!

Let’s address these points.

Publishing a paper is not for the likes of a mere mortal like me

Yes it is. Flat out, it is for anyone who wants to participate.

YOU have something to contribute to the world, but even moreso, writing and publishing a paper isn’t as impressive as it may sound. That thought will be continued below.

When a paper makes a statement backed by a reference to something else that says so, that is irrefutable evidence that it is fact

Wrong! At best, all that means is that someone else said the same thing. At worst, it means that they misinterpreted the thing they cited.

In either case, it’s through “peer review” that we hope mistakes and fallacies are found and corrected before publication, but it’s all humans involved, and humans are imperfect machines.

This is likely basic info for anyone who went to college, but for the rest of us simple folk, this translates to: Check your sources, and make sure you have multiple sources that are in agreement. Also try to understand and address any source that disagrees.

Publishing papers is all about advancing science, and perhaps a bit about one’s ego, but not at all about money

Sure it is about advancing science, and perhaps a bit about one’s ego, but there is more to it.

Certain professions are bound as part of their employment contract to fulfill a quota of published papers. Kind of surprising isn’t it?

Also, it costs MONEY to submit papers to journals. Like 5 grand or more. Where does that money go? You’d hope it would go to fund other research, but I’m not really sure where it goes in general. It also varies from journal to journal.

Furthermore, it costs money to READ papers in journals. Yes, seriously. Someone did science for the benefit of the world, and wanted to put it out there for the world to see and make use of, and the journals charge quite a bit of money to anyone who wants to read these papers. In practice, only academic institutions likely have access to these papers.

Are you an independent researcher with something to share with the world? Too bad! Good luck even finding related work to cite or improve upon jerk! ha ha ha!

Basically, academic journals are there for academic folk to publish in, get well known in academic circles, get better academic jobs and kinda stay in that realm.

Similarly, those folks aren’t likely to show things at E3.

It’s just a different world with it’s own rules and people in that system have different goals than us folk developing video games or graphics applications.

When you publish something, it has to be new. In fact, it has to be so novel that it can’t be like anything else written EVER.

Funny enough, it turns out this doesn’t have to be true at all.

If you are patenting an idea, you need to look like it came from NO WHERE and that it’s the first of it’s kind and is super amazing and standalone.

If you are publishing a paper, it’s kinda the reverse that is true. To gain credibility you need to show how your work is based on work other folks have done, and how you’ve improved them.

Alternately, you could also just do a paper that is a survey of various techniques to show the pros and cons of each.

Lastly, you can even write about something someone else already wrote about, but just explain it better, or maybe explore some of the implications of their work that they didn’t.

Yeah. YOU right now, could write a research paper about something. I guarantee you could. It just will take some time and effort (and possibly money), which may or may not be worth it to you.

Google ought to be great at helping me find other related work that i can reference!

This is still a bit strange to me. Google has been NO help in finding work related to what I’ve been working on.

On one hand, I can see that being true due to research almost always being behind a pay wall that google can’t see behind, but on the other hand, there is a lot of research that isn’t. Also, the “Abstract” of papers (a ~4 sentence summary) is almost always able to be read for free. Why does google not have knowledge of those?

But yeah… google has found NOTHING. The references I have are things that I accidentally stumbled on, or that other people RANDOMLY happened to put something on twitter about, or talk about in graphics mailing lists.

I search for exact terms that should find things I now know exist, and it finds nothing.

WTF Google?!

Is it Worth it?

As a (professional?) (game?) programmer, is publishing a paper worth it? It depends.

Is this something you have a desire to do? I have always wanted to be a scientist and contribute to human progress, so that makes it worth while to me.

Also, it can’t hurt the resume, but it can be expensive.

If interested, make sure and find out what your employer’s policies are though, and also what your rights are which may be different than what your company would like you to do!

Then, in the end, do whatever you think is best (:

It’s also a good idea to read the guidelines for submission from the journal, read the notes that they give to reviewers to help review your paper, and also you should read papers that have been published in that journal to get an idea of what qualities an accepted paper has.

Some Resources

Here are some nice resources I’ve found so far.

First and foremost is the journal I’m going to be trying to publish my first paper with. They have some sort of partnership with SIGGRAPH which is awesome (because SIGGRAPH is amazing!!), and also, it’s FREE to submit papers to, and FREE for people to read. It’s also aimed towards professional game / graphics programmers and focuses more on practicality and results, and less on purely theoretical things, or typical academic practices that don’t really have a place in the non academic world (IMO). Go right now and go read some of their articles!

http://jcgt.org/ – the Journal ofComputer Graphics Techniquespeer-reviewed, open access, and free to all

Next, I encourage you to read the notes that jcgt gives to reviewers to help them review papers. This ought to show you the mindset of both the journal and the reviewers. They are literally there to try and help you succeed as much as possible.

JCGT – Review Form

I also want to share this presentation with you, which is from Microsoft Research, Cambridge.

How to write a great research paper

If you are someone like me who wishes for greatness, but feels like a “mere mortal”, I really recomend reading the book “Masters of Doom” to see how John Carmack and related folk made such a splash in the world as game developers. JC is someone I respect a lot, and a lot of things he does and has done in the past are things that are beyond my wildest dreams of success, but things I’d like to aspire to. The path is a lot more humble than you might expect, and even a little bit shady at times. Masters of Doom: How Two Guys Created an Empire and Transformed Pop Culture.

Lastly, as I write my paper, I hope that this is the time that I finally have invented something that doesn’t yet exist (please???!!!). I’ve spent several months on doing experiments, writing code, doing research to help explain my results, and finding ways to work around problems encountered. I’ve finally finished that phase and have started in on actually writing the paper (abstract v1 is finished, outline is work in progress).

RANDOMLY, last friday, someone posted a link to a paper in a graphics mailing list I’m on. That paper had a title so similar to what I’m writing that i nearly fell out of my chair and started crying LOL (ok maybe exaggerating but i was scared). I read it in a few passes, each time peeking out from between my fingers as i was covering my eyes, afraid of what I’d see, and after about 4 or 5 of those passes I gave a sigh of relief. There are similarities, but it is a world of different-ness, and it’s applications are way different than my paper.

PHEW. That close call actually gave me the strongest reference I have to cite and actually gave me some references to other papers which explain some of the strange results I was getting in a specific situation, so solved a mystery for me. Turned out to be a good thing, but man was I scared.

Believe it or not, the academia stack exchange site has been a great help too in finding answers to specific questions that you can’t just ask google about:
https://academia.stackexchange.com/

More coming in the future as I learn more, until then, ta ta!

DAPSE Preview

Here’s a preview of something I’m working on. Details aren’t ready yet, but I’m going to try and write up a little research paper about it and try to get it published if I can. I’m going to try Journal of Computer Graphics Techniques first, and if that doesn’t work out, I’m going to try plosone.com.

After going through the process I think I’ll be writing up some other papers about some other things, including some real time raytracing techniques ūüėõ

I’ll probably also gather some notes and post them for other first time research paper writers looking to get their techniques out there.

Any guesses as to what DAPSE is all about? (:

As a very vague hint, this comic helped to inspire the name Saturday Morning Breakfast Cereal: Why We do Science

MoriRT: Pixel and Geometry Caching to Aid Real Time Raytracing

About half a year ago, some really intriguing ideas came to me out of the blue dealing with ways to speed up raytracing.  My plan was to create a couple games, showing off these techniques, and after some curiosity was piqued, write an article up talking about how it worked to share it with others in case they found it useful.

For those of you who don’t know what raytracing is, check out this wikipedia article:

http://en.wikipedia.org/wiki/Ray_tracing_(graphics)

Due to some distractions and technical setbacks unrelated to the raytracing itself, I’ve only gotten one small game working with these techniques. ¬†One of the distractions is that I implemented the game using google’s native client (NaCl) and for some reason so far unknown to me, it doesn’t work on some people’s machines which is very annoying! ¬†I plan to get a mac mini in the next couple months to try and repro / solve the problem.

Check out the game if you want to.  Open this link in google chrome to give it a play:

https://chrome.google.com/webstore/detail/kknobginfngkgcagcfhfpnnlflhkdmol?utm_source=chrome-ntp-icon

The sections of this article are:

  1. Limitations
  2. Geometry Caching
  3. Pixel Caching
  4. Future Work
  5. Compatible Game Ideas

Limitations

Admittedly, these techniques have some pretty big limitations. ¬†I’ve explained my techniques to quite a few fellow game devs and when I mention the limitations, the first reaction people give me is the same one you are probably going to have, which is “oh… well THAT’S dumb!”. ¬†Usually after explaining it a bit more, people perk up again, realizing that you can still work within the limitations to make some neat things.¬† ¬†So please hold off judgement until checking out the rest of the article! (:

The big fat, unashamed limitations are:

  • The camera can’t move (*)
  • Objects in the scene shouldn’t move too much, at least not all at the same time

(* there is a possible exception to the camera not moving limitation in the “Future Work” section)

So…. what the heck kind of games can you make with that? ¬†We’ll get to that later on, but here’s some things these techniques are good at:

  • Changing light color and intensity is relatively inexpensive
  • Changing object color and animating textures is inexpensive
  • These techniques don’t break the¬†parallel-izable¬†nature of raytracing. ¬†Use all those CPU and GPU cores to your heart’s content!

Seems a bit dodgy I’m sure, but read on.

Geometry Caching

The first technique is geometry caching.

The idea behind geometry caching is: ¬†If no objects have moved since the last frame, why should we test which objects each ray hits? ¬†It’s a costly part of the ray tracing, and we already KNOW that we are going to get the same results as last frame, so why even bother? ¬†Let’s just use the info we calculated last frame instead.

Also, if some objects HAVE moved, but we know that the moving objects don’t affect all rays, we can just¬†recalculate¬†the rays that have been affected, without needing to¬†recalculate¬†all rays.

Just because we know the collision points for rays doesn’t mean that we can just skip rendering¬†all together though. ¬†Several things that can make us still need to re-render a ray include: ¬†Animating textures, objects changing colors, lights dimming, lights changing color. ¬†When these things happen, we can re-render a ray much less expensively than normal (just recalculate lighting and shading and such), so they are¬†comparatively¬†inexpensive operations compared to objects actually moving around.

How I handle geometry caching is give each ray (primary and otherwise) a unique ID, and I have a dynamic array that holds the collision info for each ID.

In the part of the code that actually casts a single ray, i pass the ID and a flag saying whether it’s allowed to use the geometry cache. ¬†If it isn’t allowed to use the geometry cache, or there is no entry in the cache for the ID, the code calculates intersection info and puts it into the geometry cache.

It then uses the geometry cache information (whether it was re-calculated, or was usable as is) and applies phong shading, does texture lookups, recurses for ray refraction and reflection, and does the other things to figure out the color of the pixel.

In my first implementation of the geometry cache, it was very fast to render with once it was filled in, but it was really expensive to invalidate individual cache items.  If an object moved and a couple hundred geometry cache items needed to be marked as dirty, it was a really computationally expensive operation!

A better option, the one i use now, involves both a 2d grid (for the screen pixels) and a 3d grid (to hold the geometry of the world).

Breaking the screen into a grid, when each ray is cast into the world, I’m able to tell the ray what screen cell it belongs to. ¬† This way, as a ray traverses the 3d grid holding the world geometry, it’s able to add itself each world grid maintains to keep track of which rays pass through that 3d cell (keeping just the unique values of course!). ¬†Child rays know what screen cell they are in by getting that value from their parent.

If an object moves in the world, you can make a union of which world cells it occupied before it moved, and which world cells it occupies after the move. ¬†From there, you can make a union of which screen cells sent rays into that world cell. ¬†The last step is to mark all those screen cells as “geometry dirty” so that next frame, the rays in those cells are disallowed from using the geometry cache data, and instead will re-calculate new intersection info.

This method makes it so potentially a lot of rays re-calcuate their intersection data that don’t really need to, but by tuning the size of the screen and world grids, you can find a good happy medium for your use cases.

If you have an idea to better maintain the geometry cache, feel free to post a comment about it!

Pixel Caching

The second technique is pixel caching which is a fancy way of saying “don’t redraw pixels that we don’t have to”. ¬†The less rays you have to cast, the faster your scene will render.

The first challenge to tackle in this problem is how do you know which pixels will be affected when an object changes color?  That is solved by the same mechanism that tells us when geometry cache data is invalidated.

When an object changes color (or has some other non-geometry change), you just get the list of world cells the object resides in, and then get the union of screen cells that sent rays through those world cells.

When¬†you have that list, instead of marking the screen cell “geometry dirty”, you mark it as “pixel dirty”.

When rendering the screen cells, any screen cell that isn’t marked as dirty in either way can be completely skipped. ¬†Rendering it is a no-op because it would be the same pixels as last time! (:

This is the reason why you want to minimize geometry changes (objects moving, rotating, resizing, etc) and if you have to,  rely instead on animating textures, object colors, and lighting colors / intensities.

Future Work

Here’s a smattering of ideas for future work that I think ought to bear fruit:

  • Replace the screen and/or world grid with better performing data structures
  • Pre-compute (a pack time process) the primary rays and subsequent rays of static geometry and don’t store static geometry in the world grid, but store it in something else instead like perhaps a BSP tree. ¬†This way, at run time, if a ray misses all objects in the dynamic geometry world grid, it can just use the info from the pre-computed static geometry, no matter how complex the static geometry is. ¬†If something DOES hit a dynamic object however, you’ll have to test subsequent rays against both the dynamic object world grid, and the data structure holding the info about the static geometry but hopefully it’ll be a net win in general.
  • Investigate to see how to integrate this with photon mapping techniques and data structures. ¬†Photon mapping is essentially ray tracing from the opposite direction (from light to camera, instead of from camera to light). ¬†Going the opposite direction, there are some things it’s really good at – like caustics – which ray tracing alone just isn’t suited for:¬†http://en.wikipedia.org/wiki/Photon_mapping
  • In a real game, some things in the world will be obscured by the UI overlays. ¬†There might be an oportunity in some places to “early out” when rendering a single ray if it was obscured by UI. ¬†It would complicate caching those since an individual ray could remain dirty while the screen cell itself was marked as clean.
  • Orthographic camera: ¬†If the camera is orthographic, that means you could pan the camera without invalidating the pixel and geometry cache. ¬†This would allow the techniques to be used for a side scrolling game, overhead view game, and things of that nature – so long as orthographic projection looks good enough for the needs of the game. ¬†I think if you got creative, it could end up looking pretty nice.
  • Screen space effects: enhance the raytracing visuals with screen space particles and such. ¬†Could also keep a “Z-Buffer” by having a buffer that holds the time each ray took to hit the first object. ¬†This would allow more advanced effects.
  • Interlaced rendering: to halve the rendering time, every frame could render every other horizontal line. ¬†Un-dirtying a screen cell would take 2 frames but this ought to be a pretty straight forward and decent win if losing a little bit of quality is ok.
  • red/blue 3d glasses mode: ¬†This is actually a feature of my snake game but figured i’d call it out. ¬†It works by rendering the scene twice which is costly (each “camera” has it’s own geometry and pixel cache at least). ¬†If keeping the “Z-Buffer” as mentioned above, there might be a way to fake it more cheaply but not sure.

Compatible Game Ideas

Despite the limitations, I’ve been keeping a list of games that would be compatible with these ideas. ¬†Here’s the highlights of that list!

  • Pinball: ¬†Only flippers, and the area around the ball would actually have geometry changes, limiting geometry cache invalidating. ¬†Could do periodic, cycling color / lighting animations on other parts of the board to spice the board up in the “non active” areas.
  • Marble Madness Clone: Using an orthographic camera, to allow camera paning, a player could control a glass or mirrored ball through a maze with dangerous traps and time limits. ¬†Marble Madness had very few moving objects and was more about the static geometry so there’d probably be a lot of mileage here. ¬†You could also have animated textures for pools of acid so that they didn’t impact the geometry cache.
  • Zelda 1 and other overhead view type games: Using ortho camera to allow panning, or in the case of Zelda 1, have each “room” be a static camera. ¬†You’d have to keep re-rendering down somehow by minimizing enemy count, while still making it challenging. ¬†Could be difficult.
  • Metroidvania: side scroller with ortho camera to allow panning. ¬†Could walk behind glass pillars and waterfalls for cool refractive effects.
  • Monkey Island type game: LOTS of static geometry in a game like that which would be nice.
  • Arkanoid type game: static camera, make use of screen space effects for break bricking particles etc
  • Mystery game: Static scenes where you can use a magnifying glass to LITERALLY view things better (magnification due to refraction, just like in real life) to find clues and solve the mystery. ¬†Move from screen to screen to find new clues and find people to talk to, progress the storyline etc.
  • Puzzle Game: could possibly do a traditional “block based” puzzle game like puzzle fighters, tetris, etc.
  • Physics based puzzle game: You set up¬†pieces¬†on a board (only one object moves at once! your active¬†piece!) then press “play”. ¬†Hopefully it’d be something like a ball goes through your contraption which remains mostly motionless and you beat the level if you get the ball in the hole or something.
  • Somehow work optics into gameplay… maybe a puzzle game based on lasers and lights or something
  • Pool and board games: as always, gotta have a chess game with insane, state of the art graphics hehe
  • mini golf: A fixed camera when you are taking your shot, with a minimum of moving objects (windmills, the player, etc). ¬†When you hit the ball, it rolls, and when it stops, the camera teleports to the new location.
  • Security gaurd game: ¬†Have several raytraced viewports which are played up to be security camera feeds. ¬†Could have scenes unfold in one feed at a time to keep screen pixel redraw low.
  • Turn based overhead view game: ¬†Ortho camera for panning, and since it’s turn based, you can probably keep object movement down to one at a time.

Lastly, here’s a video describing this stuff in action. ¬†When you view the video, the orange squares are screen tiles that are completely clean (no rendering required, they are a no-op). ¬†Purple squares are screen tiles that were able to use the geometry cache. ¬† Where you don’t see any squares at all, it had to re-render the screen tile from scratch and wasn’t able to make use of either caching feature.

Feedback and comments welcomed! ¬†I’d be really interested too in hearing if anyone actually uses this for anything or tries to implement in on their own.