Okay, I see you understand basic principles. Now let’s move to the more complex things. I can’t share exact UD algorithm (you must understand me, I’ve spent years mastering it) but I can express in a code what I have already said in the interviews. The thing I want to say is: you must use sorting and eliminate raycasting.
Sorting algorithm I introduce here is very VERY simple. You can optimize it a lot using octrees and more elegant heuristics than that. But keep it simple.
You’ve mentioned this http://rghost.net/48541594 dataset, I had some problems downloading it, but I did it that and can say it is good for testing, you may use it with my program.
Here is the code I am talking about. If you’re smart enough, you’ll get benefit from it.
Question: why does it work?
UPDATE: It’s not clear if it really works, it’s unknown the quantitative improvement given by the random permutation trick. If you care, the BruceRDell thing is a prank.
I would like to understand the following:
- what is the role of the random permutation?
- why does the main loop work?
- is this already done? (send links to papers, if any)
So, let’s have a polite and informative discussion in the comments, if you agree. We all write in some variant of broken english, therefore I don’t see why anybody can’t participate.
Not interested in: is the real Bruce Dell? Is the real UD algorithm? Only interested to understand the guts of it.
I finish with the video from b@b’s comment: