OcTree algorithm

LiuFeng · October 15, 2007, 10:41:02 AM

I try to write my own OcTree to Check collistion
but when set OcTree to Object, this Object was broken!
Because i use an array of vertices , and partition it!
Add each element to a group befor add all group to group root

What my error??

Have ,or not solution that make an OcTree and don't need partition primitive vertices???

EgonOlsen · October 15, 2007, 12:38:22 PM

I'm sorry, but how should i know what you error is? Bascially, you take an object's polygons and partition them according to your partition approach. How you are going to store them in your data structures is totally up to you. If you are doing it wrong, how should i know?

LiuFeng · October 15, 2007, 02:30:30 PM

This code i try to write in java3d:
import java.awt.Color;

import java.util.List;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Collection;

import javax.media.j3d.BranchGroup;
import javax.media.j3d.PointAttributes;
import javax.media.j3d.ColoringAttributes;
import javax.media.j3d.TransparencyAttributes;
import javax.media.j3d.LineAttributes;
import javax.media.j3d.PolygonAttributes;
import javax.media.j3d.Material;
import javax.media.j3d.Appearance;
import javax.media.j3d.BoundingBox;
import javax.media.j3d.Bounds;
import javax.media.j3d.RenderingAttributes;
import javax.media.j3d.RenderingAttributes;
import javax.media.j3d.Shape3D;
import javax.media.j3d.GeometryArray;
import javax.media.j3d.QuadArray;
import javax.media.j3d.TriangleArray;

import javax.vecmath.Vector3d;
import javax.vecmath.Point3d;
import javax.vecmath.Point3f;
import javax.vecmath.Color3f;

public class OcTree
{
private List<Vector3d> normals;
private ArrayList<Point3f> vertices;
private HashMap nodeElementMapping;
private int maxDepth = 6;
private int maxElementsPerNode = 1;

private BranchGroup root;
private BranchGroup bg[];
private int geometryArrayType;
private PointAttributes pointAttributes;
private LineAttributes lineAttributes;
private PolygonAttributes polygonAttributes;
private ColoringAttributes colouringAttributes;
private TransparencyAttributes transparencyAttributes;
private RenderingAttributes renderingAttributes;
private Material material;
private Appearance appearance;
private GeometryArrayType geomType;
private int countElements;
private int[] indices;

   public OcTree(int geometryArrayType, ArrayList<Point3f> vertices/*, List<Vector3d> normals*/)
   {
   this.geometryArrayType = geometryArrayType;
   this.vertices = vertices;
//   this.normals = normals;

System.out.println(vertices.size());

   geomType=new GeometryArrayType();

   setNumVertex(vertices);

   pointAttributes = new PointAttributes(1.0f, true);
pointAttributes.setCapability(PointAttributes.ALLOW_SIZE_READ);
pointAttributes.setCapability(PointAttributes.ALLOW_SIZE_WRITE);

lineAttributes = new LineAttributes(1.0f, LineAttributes.PATTERN_SOLID, true);
lineAttributes.setCapability(LineAttributes.ALLOW_WIDTH_READ);
lineAttributes.setCapability(LineAttributes.ALLOW_WIDTH_WRITE);
lineAttributes.setCapability(LineAttributes.ALLOW_PATTERN_READ);
lineAttributes.setCapability(LineAttributes.ALLOW_PATTERN_WRITE);

polygonAttributes = new PolygonAttributes(PolygonAttributes.POLYGON_FILL, PolygonAttributes.CULL_NONE, 0.0f, true);
polygonAttributes.setCapability(PolygonAttributes.ALLOW_MODE_READ);
polygonAttributes.setCapability(PolygonAttributes.ALLOW_MODE_WRITE);
polygonAttributes.setCapability(PolygonAttributes.ALLOW_CULL_FACE_READ);
polygonAttributes.setCapability(PolygonAttributes.ALLOW_CULL_FACE_WRITE);
polygonAttributes.setCapability(PolygonAttributes.ALLOW_NORMAL_FLIP_READ);
polygonAttributes.setCapability(PolygonAttributes.ALLOW_NORMAL_FLIP_WRITE);

colouringAttributes = new ColoringAttributes(new Color3f(Color.GRAY), ColoringAttributes.NICEST);
colouringAttributes.setCapability(ColoringAttributes.ALLOW_COLOR_READ);
colouringAttributes.setCapability(ColoringAttributes.ALLOW_COLOR_WRITE);

transparencyAttributes = new TransparencyAttributes(TransparencyAttributes.NONE, 0.0f);
transparencyAttributes.setCapability(TransparencyAttributes.ALLOW_MODE_READ);
transparencyAttributes.setCapability(TransparencyAttributes.ALLOW_MODE_WRITE);
transparencyAttributes.setCapability(TransparencyAttributes.ALLOW_VALUE_READ);
transparencyAttributes.setCapability(TransparencyAttributes.ALLOW_VALUE_WRITE);

material = new Material();
material.setSpecularColor(0.1f, 0.1f, 0.1f);
material.setCapability(Material.ALLOW_COMPONENT_READ);
material.setCapability(Material.ALLOW_COMPONENT_WRITE);

renderingAttributes = new RenderingAttributes();
renderingAttributes.setCapability(RenderingAttributes.ALLOW_VISIBLE_READ);
renderingAttributes.setCapability(RenderingAttributes.ALLOW_VISIBLE_WRITE);
renderingAttributes.setCapability(RenderingAttributes.ALLOW_DEPTH_ENABLE_READ);
renderingAttributes.setCapability(RenderingAttributes.ALLOW_DEPTH_ENABLE_WRITE);

appearance = new Appearance();
appearance.setPointAttributes(pointAttributes);
appearance.setLineAttributes(lineAttributes);
appearance.setPolygonAttributes(polygonAttributes);
appearance.setColoringAttributes(colouringAttributes);
appearance.setTransparencyAttributes(transparencyAttributes);
appearance.setRenderingAttributes(renderingAttributes);
appearance.setMaterial(material);

root = new BranchGroup();
root.setCapability(BranchGroup.ALLOW_DETACH);
root.setCapability(BranchGroup.ALLOW_BOUNDS_READ);
root.setCapability(BranchGroup.ALLOW_BOUNDS_WRITE);
root.setCapability(BranchGroup.ALLOW_PICKABLE_READ);
root.setCapability(BranchGroup.ALLOW_PICKABLE_WRITE);

BoundingBox bounds = new BoundingBox((Bounds)null);

for (int elementIndex=0;elementIndex<countElements;elementIndex++)
{
int startVertexIndex = (elementIndex*geomType.getNumVerticesPerElement());
for (int i = 0; i < geomType.getNumVerticesPerElement(); i++)
{
Point3d vertex = new Point3d((int)(vertices.get(startVertexIndex + i).x),
(int)(vertices.get(startVertexIndex + i).y),(int)(vertices.get(startVertexIndex + i).z));
bounds.combine(vertex);
}
}

Point3d lower = new Point3d();
bounds.getLower(lower);

Point3d upper = new Point3d();
bounds.getUpper(upper);

Point3d centroid = new Point3d();
centroid.add(lower);
centroid.add(upper);
centroid.scale(0.5);

double scale = Math.max(upper.z - centroid.z, Math.max(upper.y - centroid.y, upper.x - centroid.x));
lower.set(centroid.x - scale, centroid.y - scale, centroid.z - scale);
upper.set(centroid.x + scale, centroid.y + scale, centroid.z + scale);

createAllElements();
BranchGroup [] BG=new BranchGroup[bg.length/2];
createSubtree(root, bg ,BG,1);
root.compile();

   }

   private void setNumVertex(ArrayList<Point3f> verticesCount)
   {
      int count=verticesCount.size();

      for(int i=0;i<maxDepth;i++)
      {
         count=count/2;
      }

      geomType.setNumVerticesPerElement(count);

      countElements=1;

      for(int i=0;i<maxDepth;i++)
      {
         countElements*=2;
      }

      indices=new int[countElements];
      for(int i=0;i<indices.length;i++)
      {
         indices=i*count;
      }
   }


private void createSubtree(BranchGroup parentBranchGroup,BranchGroup[] BG,BranchGroup[] BGDis,int depth)
   {

      if(depth<maxDepth)
      {
         int j=-1;
      for(int i=0;i<BG.length/2;i++)
      {

         BGDis=new BranchGroup();
         ++j;
         BGDis.addChild(BG[j]);

         ++j;
         BGDis.addChild(BG[j]);

      }

      BranchGroup BGDis2[]=new BranchGroup[BGDis.length/2];
      createSubtree(parentBranchGroup,BGDis,BGDis2,depth+1);
      }
      else
      {
         for(int i=0;i<BG.length;i++)
         parentBranchGroup.addChild(BG);


      }
   }

private void createAllElements()
{
   bg=new BranchGroup[countElements];


   for(int i=0;i<countElements;i++)
   {
      ArrayList array=new ArrayList();
      bg=new BranchGroup();
      Point3f center = new Point3f();

      for(int elementIndex=i*geomType.getNumVerticesPerElement();
      elementIndex<(i+1)*geomType.getNumVerticesPerElement();elementIndex++)
         {
         //   center.set(0,0,0);
         //   center.add(vertices.get(elementIndex));
            array.add(vertices.get(elementIndex));
         }
      bg.addChild(createShape(array));
   }
}

private Shape3D createShape(ArrayList<Point3f> array)
{

   Point3f[] points=new Point3f[array.size()];
   for(int i=0;i<points.length;i++)
   {
      points=(Point3f)(array.get(i));
      //System.out.println();
   }

GeometryArray   geom=null;

   if(points.length%4==0)
   {
      geom=new QuadArray(array.size(),GeometryArray.COORDINATES|
                              GeometryArray.NORMALS);
      geom.setCoordinates(0,points);
   }

   if(points.length%4==1)
   {
      geom=new QuadArray(array.size()+3,GeometryArray.COORDINATES|
                              GeometryArray.NORMALS);
      geom.setCoordinates(0,points);
      geom.setCoordinate(1,points[points.length-3]);
      geom.setCoordinate(2,points[points.length-2]);
      geom.setCoordinate(3,points[points.length-1]);
   }

   if(points.length%4==2)
   {
      geom=new QuadArray(array.size()+2,GeometryArray.COORDINATES|
                              GeometryArray.NORMALS);
      geom.setCoordinates(0,points);
      geom.setCoordinate(1,points[points.length-2]);
      geom.setCoordinate(2,points[points.length-1]);
   }

   if(points.length%4==3)
   {
      geom=new QuadArray(array.size()+1,GeometryArray.COORDINATES|
                              GeometryArray.NORMALS);
      geom.setCoordinates(0,points);
      geom.setCoordinate(1,points[points.length-1]);
   }

   Shape3D shape=null;

   if(geom!=null)
   {

      shape=new Shape3D();

      shape.setGeometry(geom);
      shape.setAppearance(new Appearance());
   }

   return shape;
}

public BranchGroup getBG()
{
   return root;
}

}

And this result:

EgonOlsen · October 15, 2007, 05:36:59 PM

This is not a Java3D-forum. If you have got a question regarding Java3d, i suggest to visit a Java3D-forum instead and ask your question there.

OcTree algorithm

LiuFeng

EgonOlsen

LiuFeng

EgonOlsen