Egg Octree

[raytaller]

@ynjh_jo

Well, if only using <=, it wouldn’t help much. Try cellsize (1,1,1), or (1,1,1.5) or (1,1,2), still the maze. The problem remains.
The only working way is enlarging the depthZ about 4 times . But I’m sure there must be duplicated vertices if I go that way.

In fact, it seems the optimization with depth tests is algorithmically wrong.
I don’t want to hack the code and adding odd constants that come from nowhere, and I admit I can’t really see why it don’t works that way, but taking a sheet of paper and a pencil should solve the problem.

I updated the code with a slower but safer algorithm.

@ynjh_jo :
How do you make the this work with the maze egg file ? The need to pass a single eggnode with a VertexPool followed by Polygons is quite restrictive. Do you run the split as many times as there are vertexpools ? Since it’s not possible to recursively search an eggnode, I can’t see the best way to do.

[Liquid7800]

I had the same problem with unpacking on WinXP. 7zip, the command line version, can handle the compression algorithm:

7-zip.org/download.html

Thanks enn0x, I had the same problem but I was on win 2000. But I used the GUI version as well and it extracted. Thanks for the tip.

[ynjh_jo]

GREAT update !

How do you make the this work with the maze egg file ? The need to pass a single eggnode with a VertexPool followed by Polygons is quite restrictive. Do you run the split as many times as there are vertexpools ? Since it’s not possible to recursively search an eggnode, I can’t see the best way to do.

Nothing , I simply dropped the .egg to my modeler (using mayaeggimportXX.mll) and removed everything except the single maze mesh, set new material w/o texture to it, and export.

[raytaller]

Does anyone know if the visible nodes are Z-sorted before being sent to the graphic card ? Because if so, it would allow the graphic card to eliminate a lot of vertices when splitting large meshes into octrees (i’m not talking about occlusion culling)

[chombee]

I found this Python octree implementation in the Python cookbook: aspn.activestate.com/ASPN/Cookbo … ipe/498121

Your code looks very good. So could I integrate it with my terrain generation code? Like I could just generate my terrain and collision models with no thought to efficiency, save them to an Egg, and then run the Egg through your code to get efficient terrain?

[raytaller]

Of course, this distributed is under the WTFPL license.
I wish we could create a great library of extensions for Panda !

[neighborlee]

@raytaller

Of course, this distributed is under the WTFPL license.
I wish we could create a great library of extensions for Panda !

The ease of use of panda makes it accessible for less able programmer types, so in the future would you maybe add a tiny explanation of sometype as to why a given code is being offered ( not a bad idea for all of us ). I went through this twice and still was not sure why this was needed, given that panda already has such mechanisms built in to its engine.

Thanks again for optimizing ( as I understand it ) and helping make panda better

cheers
nl

[raytaller]

Is it better now ?

[neighborlee]

@raytaller

Is it better now ?

Thats great, thx very much for updating it.

cheers

[treeform]

for some reason using this in my code does not work with collisions. it only works after flatten strong … but would that revers the effect of octreed eggs?

[mysticdream]

is it possible to explain it in easier terms?
i’m still new with panda and i dun understand what this whole code means tho it seems useful

[ditus]

great

[Icycal]

hello, im working on a c++ panda3d school proj and im really interested in using this oct tree to ‘split’ up my map model.

but i dont really know how to use it. do i need to complile the python code and run the python exe, or do i have to rewrite the eggoctree code into c++ and run it using c++?

im actually not too sure how the octree works, and i dont know much about using python it will be great if someone can give some hints

[ThomasEgi]

example of the useage are on page 1 of this thread.

about the code. it loads an egg file. optimizes it. and saves it out again.
so basically it’s yourmap.egg->optimisation->yourmap.egg
so there is no need to port it to c++ or anything. it simply modifies your model-internal structure completely outside your application.

octrees can be imagined as a cube which is divided in 8 small cubes. each of them is divided in 8 cubes again and so on and so on. the idea behind this is: get rid of all model-data you dont need right now. for collision that would mean. to check collision against 10 cubes and 5 triangles or so. instead of testing against 200000 triangles. 2000000 vs 15 checks makes a big performance difference

[ditus]

a picture say mostly more than 1000 words

[Icycal]

oh i see. thanks for the pictures, i got the idea of the octree now.

hmm i tried to do the python code (im totally new to python ), but i need some guidance on how to use the eggoctree correctly.

correct me if im wrong (i dont think im right )
this is how i did: i placed the class EggOctree into a python file called EggOctree.py, and then i created a new python file called OctreeBuilder, which i imported the EggOctree class (from EggOctree import EggOctree).

then i tried to run the ‘use’ code, something like this:

[size=75]

from pandac.PandaModules import *
import direct.directbase.DirectStart
from pandac.PandaModules import CollisionTraverser,CollisionNode
from pandac.PandaModules import CollisionHandlerQueue,CollisionRay
from pandac.PandaModules import Filename
from pandac.PandaModules import PandaNode,NodePath,Camera,TextNode
from pandac.PandaModules import Vec3,Vec4,BitMask32
from direct.gui.OnscreenText import OnscreenText
from direct.actor.Actor import Actor
from direct.task.Task import Task
from direct.showbase.DirectObject import DirectObject
import random, sys, os, math
import thread

from EggOctree import EggOctree

import math 

class World(DirectObject):
   def __init__(self):
      self.config()

   def config(self):
      self.np = render.attachNewNode('np')
      egg = EggData() 
      egg.read(Filename('Map_Tutorial_Level.egg'))       
      egg.getFirstChild() 
      sourceNode = egg.getNextChild() # the sourcenode must contain a VertexPool and a list of Polygons 
      if self.np != None : 
         self.np.removeNode() 
         self.np = None
      
   def mainloop(self, task):

      ed = EggData() 
      ed.setCoordinateSystem(egg.getCoordinateSystem())
      print 'Been Here'

      # Here, it's a quadtree since there will be only 1 leaf along the Y axis 
      self.octree.build(sourceNode, ed, Vec3D(3, 100, 3))


      ed.writeEgg(Filename('Map_Tutorial_Level_octree.egg')) 
      ed = None 

      self.np = loader.loadModel('Map_Tutorial_Level_octree.egg') 
      self.np.reparentTo(render) 
      return task.cont
   
w = World()
run()

[/size]

i referenced most of the stuff from roaming ralph & the octree demo, but im not sure how to apply it in python correctly, so i will need some help on this. thanks in advance

[Icycal]

i managed to generate a octree file, but the collision with the octree model doesnt seem to be working.

my file looks like this:

<CoordinateSystem> { Z-Up }

<Collide> { Polyset keep descend }  <VertexPool> walkingground.verts {
  <Vertex> 0 {
    -24.83 -1.13694 -20.0926
    <UV> { 0.25 0 }
    <Normal> { 0 0 1 }
  }
  <Vertex> 1 {
    -24.83 -0.533698 -20.0926
    <UV> { 0.25 0.25 }
    <Normal> { 0 0 1 }
  }
  <Vertex> 2 {
    -25.2058 -0.533698 -20.0926
    <UV> { 0.234263 0.25 }
    <Normal> { 0 0 1 }
  }
  <Vertex> 3 {
    -25.2063 -1.13694 -20.0926
    <UV> { 0.234244 0 }
    <Normal> { 0 0 1 }
  }
  <Vertex> 4 {
    -14.7407 -1.13486 -20.0926
    <UV> { 0.672425 0.000859034 }
    <Normal> { 0 0 1 }
  }
  <Vertex> 5 {
    -15.4454 -1.13694 -20.0926
    <UV> { 0.642919 0 }
    <Normal> { 0 0 1 }
  }
.
.
.
.
<Group> {
  <Group> {
    <Group> {
      <Group> {
        <Group> leaf_0_0_0 {
        }
        <Group> leaf_1_0_0 {
        }
        <Group> leaf_0_0_1 {
        }
        <Group> leaf_1_0_1 {
        }
      }
      <Group> {
        <Group> leaf_2_0_0 {
        }
        <Group> leaf_3_0_0 {
        }
        <Group> leaf_2_0_1 {
        }
        <Group> leaf_3_0_1 {
        }
      }
.
.
.

does this octree file look correct?

and also, if i want to use the octree.egg in c++, do i just include the model file and do it like the normal “roaming ralph in c++” example?
please help… thanks

[birukoff]

I read through this thread quite a few times and tried to code it but I still don’t understand how to use this octree…
How to generate egg with octree? How to use it later? Could you be so kind as to modify the Roaming Ralph sample to use octree for collisions? This won’t take a lot of your time I am sure, and such tutorial will be very, very helpful for those who just start using Panda and Python, like me

[ynjh_jo]

Icycal :
I don’t think tag has any use outside .
You must not generated it with collide=1, did you ?
If you generated it with collide=1, the 's would have ‘barrier’ object type, which during loading time will be converted to collision polyset contained in collision node.

birukoff :
the author created that code only for collision, so he must strips all entries after until the with 1 huge bulk of .
So, what raytaller did with this :

egg.getFirstChild()
sourceNode = egg.getNextChild() # the sourcenode must contain a VertexPool and a list of Polygons

is :
egg.getFirstChild() is used to step on the , to reach the by using egg.getNextChild().
Yes, the children must be grabbed sequentially. To my eyes, that’s the limitation by reading the .egg using EggData.
If you want to use that code, the model must be exported as a single huge geometry, then remove all entries before , except and , eg. :

<CoordinateSystem> { Z-Up }

<Comment> {
  "comment comment comment"
}
<Group> whatever {
   <VertexPool> vpool {
     <Vertex> 0 {
       0.024505 0.004868 -0.002914
       <UV> { 0.535007 0.506954 }
       <Normal> { 0.191266 0.0336759 0.98096 }
       <RGBA> { 1 1 1 1 }
     }
.
.
.
}

If the is not inside , you must create the in order to triangulate it.

I hate that limitation, so I dropped the .egg reading using EggData. Instead, I used GeomVertexData directly to fetch the vertices and triangles.
The bonuses are :

1. I can load any format, not only .egg
2. I can select only the needed parts of the model to be processed, not the whole bulk

Addition :

1. I created adjustible cell size visualizer
2. randomly colored each resulting geom to easily distinguish them
   so I only need to run the code once, and keep splitting the model until satisfied with the result.
3. added collide toggle, so when I have the desired result, I just need to toggle it and split the model once again to generate the collision mesh
   The output :
4. the splitted .egg and .bam
5. (if collide=0) 2 .bam’s, 1 is the randomly colored one, and 1 is white
   NOTE :
   it’s still only for collision, I don’t preserve any UV set and texture reference, only the vertex normal is preserved.
   Here it is :
   [EDIT] : see my next post

[birukoff]

Wow, that’s great, sir! Thank you very much.

Although, I must say there is something wrong with this code. I have tried it on smaller meshes, and it works fine. But when I try to convert the bigger mesh (few hundred thousand vertices), it crashes right after generating the first file (soon after “writing egg…” appears, before “Done”), without trying to make bam files. The first generated egg seems to be corrupt also: when trying to load it into Panda, Panda crashes without any warnings…

I am going to test it with Roaming Ralph’s world.egg, and let you know (it can take quite some time, since I don’t understand how to use generated models for collisions while have original world.egg for rendering… Just learning…)