Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon.

Pages: 1-4041-

Quad-Tree

Name: Anonymous 2011-11-14 20:12

I've been searching around for the logic behind QuadTrees, and trying to implement my own QuadTree algorithm.  What's the basic logic behind QuadTrees?

Name: Anonymous 2011-11-14 20:18

smoke trees errday

Name: Anonymous 2011-11-14 20:20

It's like any tree, except instead of k number of children at non-leaf nodes, there are 4 children. So you use the same algorithms for traversing trees in general. In graphics or physics simulations, where it is used to partition space into a tree structure for logarithmic searches and culling, each non-leaf node in a tree represents the axis-aligned bounding volume of it's 4 children, in a recursive manner. That's all there is to it.

Name: Anonymous 2011-11-14 21:58

ya, ya just take your space and cut it into four pieces, and store each quadrant under your current node. One method is to pick an object on your map that is near the middle, and represent the object as a node. Doing this, you can quickly find objects that are close to each other, which will help for efficient collision detection when there are many objects on your map. If every object is stuck inside of every other object it'll still be n squared checks, but hopefully that doesn't happen. It isn't that difficult to create, but keeping it valid as the objects move around, and keeping it balanced could be something. I want to learn more about this myself.

Name: Anonymous 2011-11-14 22:45

first binary trees now quad trees?

what the fuck? what about ternary trees?

Name: Anonymous 2011-11-15 1:11

Interestingly, quad trees can be implemented as binary trees, just as octrees can

Name: Anonymous 2011-11-15 2:53

>>3
I'm not familiar with the current existing algorithms.  I'm most confused at deciding what needs to be rendered without processing my data each time to determine what's inside of the rectangle.

Name: FrozenVoid !!mJCwdV5J0Xy2A21 2011-11-15 3:15

Name: Anonymous 2011-11-15 3:21

You have your choice of depth-first or breadth-first searching. This isn't new stuff, Dijkstra was doing this shit back in the 50s. At each node, check to see if the bounding volume of the node (and thus all of its children) intersects with the camera's view frustrum. If it does not, you do not need to traverse any further on that branch of the tree and you do not need to render any of the geometry located within the leaf nodes of that branch.

Name: Anonymous 2011-11-15 7:43

oh no - not this old chestnut again
some twat will start harping on any minute now about how you can render infinite graphical complexity with sparse voxel trees

Name: Anonymous 2011-11-15 8:56

That's easy. A Quadtree is like an Octree but with only 2 dimensions.

Name: FrozenVoid !!mJCwdV5J0Xy2A21 2011-11-15 9:08

>>10
If you want infinite graphical complexity you have to generate the data procedurally, and voxels store the most data(they're basically 3D bitmaps) compared to polygons(geometry defined with filled vectors) which require much more than raw vectors(used in old games like Elite).
i.e. using voxels is the worst choice for complexity, meshes and polygons also require a fair bit of memory,
but procedurally generated objects can be as complex as design of an algorithm creating them, and they can be discarded and regenerated as often as desired(typically they're cached for reuse).

Name: Anonymous 2011-11-15 10:40

>>9
Doesn't that only work if you were searching from the origin of the octree?

If you're looking towards the origin from the outside alone one of the major axes, it would render 1/2 the entire tree until you got to the final leaf nodes, then it would discard all of it.

Rendering with voxels is always going to be worse than polies, for the simple fact that voxels must be converted to surfaces before attempting to collision detect, and polies don't.

I'm saging because you're a retarded trolling faggot, but fuck, at least try next time.

Name: Anonymous 2011-11-15 14:14

>>13
Doesn't that only work if you were searching from the origin of the octree?

No. And this is a quad tree we're talking about. For a 2D game, or a 3D game where the world is mostly flat on the XZ axes.

If you're looking towards the origin from the outside alone one of the major axes, it would render 1/2 the entire tree until you got to the final leaf nodes, then it would discard all of it.

No. The bounding volumes of the nodes are hierarchical. Everything behind you and outside of your field of vision would be culled, often without needing to traverse all of the way down to the leaf nodes. That's why a tree structure is used in the first place, it provides O(log n) time complexity for spatial lookups.

I'll assume the rest of your response was for >>12

Name: Anonymous 2011-11-15 19:40

The cool thing about octrees and quadtrees is if you keep the size of your leaf-nodes the exact same so that they form a uniform grid, you don't need to store the tree structure at all, you can generate array indices and bounding volumes into the leaf node grid on the fly as you traverse your tree hierarchically.

Name: Anonymous 2011-11-15 21:35

Quality->Voxels
Speed->Polygons
Speed&Quality->Meshes
Scaling->Vectors
Scaling&Quality->NURBS
Autism->Procedurally generating everything

Name: FrozenVoid !!mJCwdV5J0Xy2A21 2011-11-15 21:43

>>16
You can generate Meshes/Voxels/Polygons/Vectors procedurally too.

Name: HAXUS THE GREAT 2011-11-15 21:56

this thread is [b][i][o]ENTERPRISE WIKIPEDIA QUALITY[/b][/i][/o]

Name: Anonymous 2011-11-15 22:14

>>16
Autism->Procedurally generating everything

http://www.youtube.com/watch?v=2NBG-sKFaB0&feature=related

Name: Anonymous 2011-11-15 23:51

AVTISMVS MAXIMVS

Name: Anonymous 2011-11-17 0:48

>5

You will love 2-3-4 trees.

Name: Anonymous 2011-11-17 2:00

>>19
Everything in this is procedurally generated:

http://www.youtube.com/watch?v=h7eREddMjt4

Name: Anonymous 2011-11-17 3:54

Name: Anonymous 2011-11-17 5:48

>>22
Really? Even the ships? That's quite a feat.

Name: Anonymous 2011-11-17 15:45

>>10
http://www.pcper.com/reviews/Editorial/John-Carmack-Interview-GPU-Race-Intel-Graphics-Ray-Tracing-Voxels-and-more/Transcr
John Carmack: Okay, for one thing, I think it’s important to separate the notion of infinite detail and Voxels. You can have Voxels [that are not infinitely detailed] because many of the Voxel engines that I’ve written have been at finite coarse levels of detail. The fact that you can instance detail in [Voxels]... in may ways it sounds awesomely cool: “infinite detail,” but if we look at all of the trends that we’ve been doing and Rage epitomizes in many ways, procedurally generated detail is usually not what you want. This has been an argument going back decades: “now is the year of procedurally generated textures and geometry.” We’ve heard that for a decade and it never has come true. What has won is being able to manage the real data that we want. Procedural-ism is really just a truly crappy form of data compression. You know, you have the data that you really want, and procedural-ism makes you something that might resemble what you really want, but it’s a form of extraordinarily lossy data compression that lets you produce something there.

Name: Anonymous 2011-11-17 18:37

>>25
Twat!

Name: Anonymous 2011-11-17 23:16

>>25

Video games will never realize their true potential until they allow you to throw julia sets at people.

Name: Anonymous 2011-11-17 23:18

>>27
set theory is pseudoscience.
julia was jewish.

Name: Anonymous 2011-11-17 23:27

>>25
Procedural-ism is really just a truly crappy form of data compression.
Carmack is as retarded as always. Procedural generation is good when you want to eleminate bias: for example, one could randomize chess pieces or randomly generate map for an online game. It has nothing to do with curve fitting math pseudoscience.

Name: Anonymous 2011-11-17 23:31

>>28
You will call anything you don't understand pseudoscience. You do realize that you could limit your sets to finite and computable objects right? Even if a fractal could be described by a non-halting (by definition infinite) process, you only need to compute a part of it for most practical uses.

Name: Anonymous 2011-11-17 23:33

>>30
Then there will be no "infinite detail". Your filthy marketing buzz fails you, jew.

Name: Anonymous 2011-11-17 23:34

>>27
I'd love to trap somebody within a julia set then search the set to find that person.

>>29
In the days when Sussman was a novice, Minsky once came to him as he sat hacking at the PDP-6.
"What are you doing?", asked Minsky.
"I am training a randomly wired neural net to play Tic-tac-toe", Sussman replied.
"Why is the net wired randomly?", asked Minsky.
"I do not want it to have any preconceptions of how to play", Sussman said.
Minsky then shut his eyes.
"Why do you close your eyes?" Sussman asked his teacher.
"So that the room will be empty."
At that moment, Sussman was enlightened.

Name: Anonymous 2011-11-17 23:35

>>31
Why is non-halting recursive patterns not infinite detail?

Name: Anonymous 2011-11-17 23:42

>>31
I haven't read this thread, so I don't know what this 'infinite detail' is, but I do think non-halting processes are fine, our universe may very well be one (and if not, by induction, an universe with a next state will always exist).
Given some fractal computing process, you can render it up to detail 'k' (some particular resolution). Given more time, you can render it up to k+1, and so on. I refuse to accept that the next step cannot exist when one models the process abstractly. (I also refuse to accept that there is such a time t which is the final state and no states follow after it. Of course, no conscious artifact (such as ourselves) will ever be able to say that a time t is final, or that t+1 doesn't exist, as our own illusion of continuity of consciousness requires us to assume t+1 always exist - and since I think living for this illusion is perfectly fine(no reason to live if you don't care about your own conscious state), I will always assume t+1 exists for any t and also the existence of a mathematical or computational multiverse, but that's a discussion for another day).

Name: Anonymous 2011-11-17 23:45

>>33
Because the Universe will eventually halt once all protons have decayed and entropy has reached maximum, and thus no more work can be performed. Thus, any computational process being simulated inside of the Universe will also be forcibly stopped.

Name: Anonymous 2011-11-17 23:47

>>32

Could you imagine the pain of getting cut by a knife with a serrated koche snowflake at the end? The knife would have finite area, and an edge with infinite length, yielding INFINITE PAIN

Name: Anonymous 2011-11-17 23:47

>>33

0xFFFFFFFF+1 = 0;

Name: Anonymous 2011-11-17 23:49

>>35
Why do you so fervently believe that this particular universe is unique and is the only computational process that can exist? It's a baseless assumption. Most people assuming the physical church turing thesis also assume a computational multiverse at minimum (see: http://arxiv.org/abs/quant-ph/0011122 for one view, although fairly incomplete. the one I personally subscribe to actually shows that quantum mechanics results very naturally from observing such a computational multiverse from the inside and getting away from it is very difficult).

Name: Anonymous 2011-11-17 23:51

>>34
an universe with a next state will always exist
Yes, that may be true, perhaps the Universe can restart/reset itself (Penrose's Conformal Cyclic Cosmology), or maybe the holographic membrane of the universe evaporates and is recycled by external/adjacent universes in some sort of Multiverse theory.

But here's the thing, it doesn't matter. All prior information is lost at the point when maximal entropy is achieved, including any macroscopic computational processes.

Name: Anonymous 2011-11-17 23:55

>>39 here, just want to clarify one thing. I shouldn't say information is lost, as that's not true (conservation of energy). Rather, what happens at maximum entropy is that all information is sufficiently randomized.

Name: Anonymous 2011-11-18 0:11

>>38
See >>39,40, I'm the same poster.

Name: Anonymous 2011-11-18 0:26

>>41
That may be true for this particular Universe/multiverse. The class of multiverse that I'm talking about is a bit wider, read the linked paper for a (classical) finitist version or http://arxiv.org/abs/gr-qc/9704009 / http://arxiv.org/abs/0704.0646 for a more general version (actually, it can be shown that the 2 versions cannot be really distinguished by a finite self-aware substructure (such as ourselves) and one recursively generates the other). In what way is it wider? In your case, you're looking at a structure which allows varying particular constants or individual states, while in my case, I'm looking at the variance of rules/metarules describing the structure in the same way you're looking at the variance of constants/states. I have no reason to assume a particular universal law is the only possible thing.
Either way, there is a way of experimentally testing my hypothesis (read "Permutation City" for an example), but it's outside the realm of popperian scientific falsifiability even if it can be experienced from the first person (by one individual or any number of individuals, however experimenter = experiment and there can not be a third party observer that doesn't participate in the experiment itself, thus this makes it unfalsifiable). It's also the most probable (class of) hypothesis that one can reach given various formalizations of Occam's Razor (such as Solomonoff induction), but as with most inductive processes, some will see it as begging the question - the only way to know is to perform the  experiment by yourself when the particular technology exists (same requirements as testing if computationalism is a valid philosophy of mind).

Name: Anonymous 2011-11-18 1:31

>>42
I've read the abstracts, going to read the full papers, but I believe I agree with them. Although I'm the poster who strongly believes that mathematics is emergent from computation, and so it doesn't really exist (we've discussed this matter before). So Max Tegmark's ``The Mathematical Universe'' should ideally be retitled.

Incidentally, I happened to have watched Max's recent talk at the last Singularity Summit, and he appears to have come around to a more strict computational viewpoint himself since writing that. Unfortunately, his talk is mostly popular physics and philosophy for the layman, so it's not really worth the bother.

http://www.youtube.com/watch?v=GctnYAYcMhI

(Pan-)computationalism is obviously the only valid philosophy of mind to anyone who has worked in computation. Drawing that conclusion might be premature, but the evidence is all around us, and the evidence to the contrary is fallacious at best. It's merely the normals who don't know of the fundamentals of how computers work, and therefore lack the necessary mindset and language in understanding the universe itself who are unable to come to terms with the one true philoshophy.

Maybe it's possible to shield a volume of our Universe from its eventual death so that it may survive into or direct/influence the birth of another or continuation of our own by harvesting external Universes. That would allow macroscopic computational processes to continue.

But until we understand the nature of what lies beyond computation within our universe looks strongly as if it will come to a screeching halt.

In other words, our ``paper tape'' got cut short.

Name: Anonymous 2011-11-18 2:20

>>43
he appears to have come around to a more strict computational viewpoint himself
Yes, in the latest version of his paper, CUH(Computational Universe Hypothesis) is the one he thinks is most likely, which is no wonder given the strange mess that happens when you look at all those uncountable ordinals in most infinitary set theories (and then you have independence results of various axioms, which makes things even more complicated). One particular problem is that even if we find ourselves a potential hypercomputational oracle (such as doing funky things around black holes), there is no way to know for sure wether we truly have oursleves a hypercomputational oracle (for we are only capable of arithmetic/computation). It's also possible that traces of complex-enough computations would give us the illusion of a hypercomputational oracle, without actually having one.

Some thoughts on wether physics based on uncountable entities makes sense or not (beyond computation):
http://arxiv.org/abs/math/0411418 http://arxiv.org/abs/math/0404335
Some thoughts on how QM (MWI-like) appears too naturally when considering a computational multiverse and why there may be no need to assume more than that:
http://iridia.ulb.ac.be/~marchal/publications/CC&Q.pdf
http://arxiv.org/abs/physics/0001020

Some interesting thought experiments on how CUH could (appear to) fail:
http://lesswrong.com/lw/55e/a_potential_problem_with_using_solomonoff/
http://lesswrong.com/lw/4iy/does_solomonoff_always_win/

Name: Anonymous 2011-11-18 2:49

>>44
Thanks for the links.

Name: Anonymous 2011-11-18 8:00

>>44
Thank you.

Name: Anonymous 2011-11-18 8:26

>>42
Either way, there is a way of experimentally testing my hypothesis (read "Permutation City" for an example) [..] the only way to know is to perform the  experiment by yourself when the particular technology exists

Forgive me for being blunt, but the particular technology already exists, it's called "soaped rope", if you catch my drift. Applying razors to wrists (remember, along the road, not across the street!) or jumping off a sufficiently high building or other landmark should work too.

I'm curious to hear any justification to the idea that doing basically the same thing but in a tad fancier way could possibly result in a different outcome.

Name: Anonymous 2011-11-18 9:53

>>47
Suicide would just give highly unreliable results. You could of course perform quantum suicide experiments (if you think MWI is true), but since you are supported by your brain and body, it's likely that the most probable outcome would be just having you survive in unusual ways or merely somehow end up in worlds where you chose not to kill yourself (also 'natural' worlds such as our own might be a lot more numerous than any 'artificial'-like worlds as given in the example in that novel).

Do you think that a digital abstraction created by scanning one's brain and accurattely rebuilding a model of it (and the body, and the environment) would give a conscious substructure, a substrate independent mind(SIM)? If computationalism is true, then it would be as conscious as you are now. If you think it's false, you would die during the scanning process and never attain consciousness.

I don't think this is a trivial question. The only way to know if the abstraction is conscious, is to experience it (be the abstraction). If I didn't acknowledge my own consciousness internally, I would not think humans (or any other being implementing a brain in any way) could be conscious (or possibly, it would reduce to something as trivial as having internal state in a particular reflective manner). I don't believe in continuity of consciousness as an intrinsic property, so I don't treat the procedure as anything different from someone going under anesthesia, assuming that the scanning/conversion process is done as accurately as possible.

The particular experiment described in Permutation City is more or less the same kind as the one that first tests if a computational abstraction would be conscious (the only one that could have any right to claim that would be the abstraction, it cannot be tested in any scientific manner, except of course, in making sure the brain/body abstraction behaves as close as possible as the original brain/body). In that experiment, the substrate independent mind (and its model-of-body/environment + OS) is placed in a self-contained mathematical/computational object whose time evolution can be described entirely by its initial state and future possible states. In that book, the reason for possibility of existence of uncomputed states is explained by first showing that consciousness is not spatially or temporally located, and not represented as anything, except that particular abstraction. A similar (but considerably more rigorous) thought experiment is shown in Marchal's papers (I've linked one before), or if you want it in a simpler form: http://groups.google.com/group/everything-list/msg/e422b8cef00b3aa6 .
The main difference between 'Dust Theory' (PC) and UDA (see link above) is that 'Dust Theory' depends on our particular physical universe existing (so states could be found anywhere in it), while UDA shows that this requirement is unnecessary (instead a form of Arithmetical Realism (basically CUH) ends up being used after it's shown to be a much simpler alternative). I should probably add that the model used in PC for the structure of their universe is not really ideal and there are some much better choices that could have been used (although probably wouldn't have made as entertaining fiction if there's really no problems to solve; I could elaborate on what I would propose to be used instead, but I think I'd be getting way offtopic by going into that here).

To sum it up, a conscious substructure existing as a computational abstraction (for example running on a real computer/hardware in this world) means computationalism is true. If computationalism is true, CUH is also very likely true (as shown by UDA). If CUH is true, any such self-contained world would also exist and self-aware substructures within it would exist independently of our universe, yet by performing such an experiment, you could have such a substructure which thinks it came from this particular universe (of course, including whatever was in the new universe's initial state). I should also note that there are various potential failure modes (the one described in PC would be highly improbable, but as quantum mechanical-like worlds are likely to be observed, violation of the laws that were set in the initial state are likely to occur, at least as long as one's consciousness is still supported by the physics(Anthropic Principle); there are some ways one could mitigate these risks and end up in a stable world by the way the actual universe's laws are selected, but this is again outside the scope of this post...).
You might also ask yourself why would such a SIM find itself in the particular universe you've coded for? Maybe there's no reason for this and they would find themselves (different copies) in different universes, as long as they support the SIM's existence (Anthropic Principle). On the other hand, there are various ways to minimize the risk of ending up in an universe where you don't want to exist. It may be that our consciousness is so stable because in our current (MWI) world, that the number of copies of oneself increases exponentially, or maybe it has to do with our universe being of low complexity and thus more probable to experience (both views have their proponents).

Either way, if you don't believe computationalism can work, you think mind uploading is equivalent to killing yourself and copies won't be conscious. If you think they can, then there is a good chance the experiment in "Permutation City" would work.

Name: >>48 2011-11-18 10:03

I should have probably added that there are also some strange things one can think of. If an experiment like that succeeds, it might be worth considering that someone could run AIXItl to predict the laws of our universe (using Solomonoff induction) and then proceed to simulate it and try to extract self-aware substructures such as ourselves from it. This could for example result in weird continuations after your ``soaped rope'' experiment. Or it may be that this wouldn't be too likely as particular data that was given as input would be Kolmogorov random (or merely not resulting in the input being our universe's initial state + laws-of-physics + local address (particular state, regarded as quantum randomness here)).

As strange as all these conclusions are (independence, all the implications of CUH), the uncomputable variant seems even less likely and more far-fetched (and still not solving anything in particular, just trying to hide the 'white rabbit'(see linked papers) behind untractable problems).

Assuming computationalism is false does even more violence to my intuitions than its wild implications do.

Either way, we can philosophize about these unfalsifiable ideas all we want, but we may one day get to see if we were right (cannot find out if wrong ;_;) about them when/if SIM becomes feasible in our future. Your idea seem does not seem too useful, except maybe to test MWI as it lacks any fine control about future states (while the experiment in PC allows one a lot more fine control, but not as much as described in the novel - actually preventing ending in undesirable universes takes a bit of clever design work and modelling, at least if you assume UD or CUH).

Name: VIPPER 2011-11-18 14:39

What the hell am i reading?

Name: Anonymous 2011-11-19 1:10

>>50
[b]MY THOUGHTS EXACTLY![b]
I had to recheck the post dates to make sure this wasn't shit from 4 years ago The Golden Era being dug up.

Name: Anonymous 2011-11-20 22:13

>>48-49
Why do you sage your posts, crazy motherfucker? I have to dig to find them again after only 24 hours.

Name: Anonymous 2011-11-20 22:28

>>52
I find no need to bump the thread if it's already on the front page.

Don't change these.
Name: Email:
Entire Thread Thread List