and…devs can(should 
) submit code but not enter the contest…
…but…but…but…maybe I don't want to be a developer anymore. :o
@Mr.Coder: if I "submit code" do I get the "I crushed Mr. Coder" t-shirt anyway?
darkfrog
we have our internal competition froggy…if you crush my submission, you'll get the t-shirt! 
(i'll post two vegetation versions i've done to help people with getting ideas on solutions)
ok, here are two vegetationclasses i've whipped up to help you get some ideas…they are not very clean yet but they get the job done ok…
HashMapVegetation - simply puts the objects into buckets(of size viewDistance) based on their x and z coordinates. when rendering simply take the bucket the camera is on and the eight buckets around it and draw…
QuadTreeVegetation - makes a quadtree representation(building a hierarchy where each new level splits the parent into 4 quads) of the world down to a defined level(7 seems to work ok in this test). when rendering I start from the top quad in the quadtree and test it's bounding box against a fake camera instance that has it's farplane set to viewDistance. if a bounding box is inside, simply draw all objects underneath, if it is intersecting, go down a quadtree level and test it's children the same way…
i have also modified the usual quadtree representation to handle bounding box size on the y-axis…
the quadtree performs in the range somewhat better up to much better than the hashmap version depending on what's in view(compared to NaiveVegetation they perform alooot better)…
here they are:
HashMapVegetation.java
import com.jme.bounding.BoundingBox;
import com.jme.bounding.BoundingVolume;
import com.jme.math.Quaternion;
import com.jme.math.Vector3f;
import com.jme.renderer.Camera;
import com.jme.renderer.Renderer;
import com.jme.scene.Spatial;
import com.jme.scene.TriMesh;
import java.util.ArrayList;
import java.util.HashMap;
/**
* MrCoder
*/
public class HashMapVegetation extends AbstractVegetation {
private class HashMapTargetData {
public Spatial target;
public Spatial lodTarget;
public BoundingVolume bounding = new BoundingBox( new Vector3f( 0, 0, 0 ), 1.0f, 1.0f, 1.0f );
public int nrObjects = 0;
public ArrayList<HashMapSpatialData> targetPosition = new ArrayList<HashMapSpatialData>();
public HashMap<String, ArrayList<HashMapSpatialData>> buckets = new HashMap<String, ArrayList<HashMapSpatialData>>();
}
private class HashMapSpatialData {
public Vector3f targetTranslation;
public Vector3f targetScale;
public Quaternion targetRotation;
}
private ArrayList<HashMapTargetData> targetSpatials = new ArrayList<HashMapTargetData>();
private int totalNrObjects = 0;
private Vector3f tmpVec = new Vector3f();
private int xoffsets[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
private int zoffsets[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
public HashMapVegetation( String string, Camera cam, float viewDistance ) {
super( string, cam, viewDistance );
}
private HashMapTargetData addTarget( Spatial target, Spatial lodTarget ) {
target.setCullMode( Spatial.CULL_NEVER );
HashMapTargetData hashMapTargetData = new HashMapTargetData();
hashMapTargetData.target = target;
attachChild( target );
if ( target instanceof TriMesh ) {
TriMesh mesh = ( TriMesh ) target;
hashMapTargetData.bounding.computeFromPoints( mesh.getVertexBuffer( 0 ) );
}
if ( lodTarget != null ) {
hashMapTargetData.lodTarget = lodTarget;
attachChild( lodTarget );
}
targetSpatials.add( hashMapTargetData );
return hashMapTargetData;
}
public void addVegetationObject( Spatial target, Vector3f translation, Vector3f scale, Quaternion rotation ) {
HashMapTargetData hashMapTargetData = null;
for ( int i = 0; i < targetSpatials.size(); i++ ) {
Spatial spatialTarget = targetSpatials.get( i ).target;
if ( spatialTarget.equals( target ) ) {
hashMapTargetData = targetSpatials.get( i );
break;
}
}
if ( hashMapTargetData == null ) {
hashMapTargetData = addTarget( target, null );
}
HashMapSpatialData hashMapSpatialData = new HashMapSpatialData();
hashMapSpatialData.targetTranslation = translation;
hashMapSpatialData.targetScale = scale;
hashMapSpatialData.targetRotation = rotation;
hashMapTargetData.targetPosition.add( hashMapSpatialData );
hashMapTargetData.nrObjects++;
totalNrObjects++;
}
public void setup() {
sortBuckets();
System.out.println( "Vegetation count: " + getTotalNrObjects() );
updateRenderState();
updateGeometricState( 0.0f, true );
setRenderQueueMode( com.jme.renderer.Renderer.QUEUE_SKIP );
lockMeshes();
lockShadows();
}
public void sortBuckets() {
for ( int index = 0; index < targetSpatials.size(); index++ ) {
HashMapTargetData hashMapTargetData = targetSpatials.get( index );
ArrayList<HashMapSpatialData> targetPosition = hashMapTargetData.targetPosition;
int nrObjects = hashMapTargetData.nrObjects;
for ( int i = nrObjects - 1; i >= 0; i-- ) {
HashMapSpatialData hashMapSpatialData = targetPosition.remove( i );
Vector3f translation = hashMapSpatialData.targetTranslation;
int x = Math.round( translation.x / viewDistance );
int z = Math.round( translation.z / viewDistance );
String key = x + "_" + z;
if ( hashMapTargetData.buckets.containsKey( key ) ) {
ArrayList<HashMapSpatialData> positions = hashMapTargetData.buckets.get( key );
positions.add( hashMapSpatialData );
}
else {
ArrayList<HashMapSpatialData> positions = new ArrayList<HashMapSpatialData>();
positions.add( hashMapSpatialData );
hashMapTargetData.buckets.put( key, positions );
}
}
}
}
public void draw( Renderer r ) {
r.renderQueue();
drawBuckets( r );
}
public void drawBuckets( Renderer r ) {
int savedPlaneState = cam.getPlaneState();
Vector3f camLocation = cam.getLocation();
for ( int index = 0; index < targetSpatials.size(); index++ ) {
HashMapTargetData hashMapTargetData = targetSpatials.get( index );
Spatial target = hashMapTargetData.target;
BoundingVolume bounding = hashMapTargetData.bounding;
int x = Math.round( camLocation.x / viewDistance );
int z = Math.round( camLocation.z / viewDistance );
for ( int bucketCount = 0; bucketCount < 9; bucketCount++ ) {
int xx = x + xoffsets[bucketCount];
int zz = z + zoffsets[bucketCount];
String key = xx + "_" + zz;
if ( !hashMapTargetData.buckets.containsKey( key ) ) {
continue;
}
ArrayList<HashMapSpatialData> targetPosition = hashMapTargetData.buckets.get( key );
int nrObjects = targetPosition.size();
for ( int i = 0; i < nrObjects; i++ ) {
Vector3f translation = targetPosition.get( i ).targetTranslation;
float distSquared = tmpVec.set( camLocation ).subtractLocal( translation ).lengthSquared();
if ( distSquared > viewDistance * viewDistance ) {
continue;
}
cam.setPlaneState( 0 );
bounding.getCenter().set( translation );
if ( cam.contains( bounding ) != Camera.OUTSIDE_FRUSTUM ) {
target.getWorldTranslation().set( translation );
target.getWorldScale().set( targetPosition.get( i ).targetScale );
target.getWorldRotation().set( targetPosition.get( i ).targetRotation );
target.draw( r );
}
}
}
}
cam.setPlaneState( savedPlaneState );
}
public void updateWorldBound() {
// super.updateWorldBound();
}
public void onDraw( Renderer r ) {
int cm = getCullMode();
if ( cm == CULL_ALWAYS ) {
return;
}
draw( r );
}
public int getTotalNrObjects() {
return totalNrObjects;
}
}
QuadTreeVegetation.java
import com.jme.bounding.BoundingBox;
import com.jme.bounding.BoundingVolume;
import com.jme.math.Matrix4f;
import com.jme.math.Quaternion;
import com.jme.math.Vector3f;
import com.jme.renderer.AbstractCamera;
import com.jme.renderer.Camera;
import com.jme.renderer.Renderer;
import com.jme.scene.Spatial;
import com.jme.scene.TriMesh;
import com.jme.system.DisplaySystem;
import java.util.ArrayList;
import java.util.HashMap;
/**
* MrCoder
*/
public class QuadTreeVegetation extends AbstractVegetation {
private class QuadTreeTargetData {
public Spatial target;
public Spatial lodTarget;
public BoundingVolume bounding = new BoundingBox( new Vector3f( 0, 0, 0 ), 1.0f, 1.0f, 1.0f );
public int nrObjects = 0;
public ArrayList<QuadTreeSpatialData> targetPosition = new ArrayList<QuadTreeSpatialData>();
public HashMap<String, ArrayList<QuadTreeSpatialData>> buckets = new HashMap<String, ArrayList<QuadTreeSpatialData>>();
public QuadTreeNode topNode;
}
private class QuadTreeSpatialData {
public Vector3f targetTranslation;
public Vector3f targetScale;
public Quaternion targetRotation;
}
private class QuadTreeNode {
public static final int TYPE_NODE = 0;
public static final int TYPE_LEAF = 1;
public int quadTreeType = QuadTreeNode.TYPE_NODE;
public BoundingBox bounding;
public ArrayList<QuadTreeSpatialData> positions;
public QuadTreeNode parent;
public QuadTreeNode[] children = new QuadTreeNode[4];
public float minY;
public float maxY;
}
private final int QUADTREE_DEPTH = 7;
private ArrayList<QuadTreeTargetData> targetSpatials = new ArrayList<QuadTreeTargetData>();
private int totalNrObjects = 0;
private Camera frustumCamera;
private Vector3f tmpVec = new Vector3f();
public QuadTreeVegetation( String string, Camera cam, float viewDistance ) {
super( string, cam, viewDistance );
DisplaySystem display = DisplaySystem.getDisplaySystem();
frustumCamera = new CheckCam( display.getWidth(), display.getHeight() );
frustumCamera.setFrustumPerspective( 45.0f,
( float ) display.getWidth() / ( float ) display.getHeight(),
1f, this.viewDistance );
frustumCamera.setParallelProjection( false );
frustumCamera.update();
}
private QuadTreeTargetData addTarget( Spatial target, Spatial lodTarget ) {
target.setCullMode( Spatial.CULL_NEVER );
QuadTreeTargetData quadTreeTargetData = new QuadTreeTargetData();
quadTreeTargetData.target = target;
attachChild( target );
if ( target instanceof TriMesh ) {
TriMesh mesh = ( TriMesh ) target;
quadTreeTargetData.bounding.computeFromPoints( mesh.getVertexBuffer( 0 ) );
}
if ( lodTarget != null ) {
quadTreeTargetData.lodTarget = lodTarget;
attachChild( lodTarget );
}
targetSpatials.add( quadTreeTargetData );
return quadTreeTargetData;
}
public void addVegetationObject( Spatial target, Vector3f translation, Vector3f scale, Quaternion rotation ) {
QuadTreeTargetData quadTreeTargetData = null;
for ( int i = 0; i < targetSpatials.size(); i++ ) {
Spatial spatialTarget = targetSpatials.get( i ).target;
if ( spatialTarget.equals( target ) ) {
quadTreeTargetData = targetSpatials.get( i );
break;
}
}
if ( quadTreeTargetData == null ) {
quadTreeTargetData = addTarget( target, null );
}
QuadTreeSpatialData quadTreeSpatialData = new QuadTreeSpatialData();
quadTreeSpatialData.targetTranslation = translation;
quadTreeSpatialData.targetScale = scale;
quadTreeSpatialData.targetRotation = rotation;
quadTreeTargetData.targetPosition.add( quadTreeSpatialData );
quadTreeTargetData.nrObjects++;
totalNrObjects++;
}
public void setup() {
createQuadTrees();
System.out.println( "Vegetation count: " + getTotalNrObjects() );
updateRenderState();
updateGeometricState( 0.0f, true );
setRenderQueueMode( com.jme.renderer.Renderer.QUEUE_SKIP );
lockMeshes();
lockShadows();
}
public void createQuadTrees() {
for ( int index = 0; index < targetSpatials.size(); index++ ) {
QuadTreeTargetData quadTreeTargetData = targetSpatials.get( index );
ArrayList<QuadTreeSpatialData> targetPosition = quadTreeTargetData.targetPosition;
int nrObjects = quadTreeTargetData.nrObjects;
//find outer bounds
float minX = Float.MAX_VALUE;
float maxX = Float.MIN_VALUE;
float minY = Float.MAX_VALUE;
float maxY = Float.MIN_VALUE;
float minZ = Float.MAX_VALUE;
float maxZ = Float.MIN_VALUE;
for ( int i = 0; i < nrObjects; i++ ) {
QuadTreeSpatialData quadTreeSpatialData = targetPosition.get( i );
Vector3f translation = quadTreeSpatialData.targetTranslation;
if ( translation.x < minX ) {
minX = translation.x;
}
else if ( translation.x > maxX ) {
maxX = translation.x;
}
if ( translation.y < minY ) {
minY = translation.y;
}
else if ( translation.y > maxY ) {
maxY = translation.y;
}
if ( translation.z < minZ ) {
minZ = translation.z;
}
else if ( translation.z > maxZ ) {
maxZ = translation.z;
}
}
//sort into quadtree
Vector3f boundingExtents = new Vector3f( ( maxX - minX ) / 2.0f + 1.0f,
( maxY - minY ) / 2.0f + 1.0f,
( maxZ - minZ ) / 2.0f + 1.0f );
Vector3f boundingOrigin = new Vector3f( ( maxX + minX ) / 2.0f,
( maxY + minY ) / 2.0f,
( maxZ + minZ ) / 2.0f );
quadTreeTargetData.topNode = new QuadTreeNode();
quadTreeTargetData.topNode.bounding = new BoundingBox( boundingOrigin,
boundingExtents.x, boundingExtents.y, boundingExtents.z );
for ( int i = nrObjects - 1; i >= 0; i-- ) {
QuadTreeSpatialData quadTreeSpatialData = targetPosition.remove( i );
sortIntoQuad( quadTreeTargetData.topNode, quadTreeSpatialData, QUADTREE_DEPTH - 1 );
}
}
}
private void sortIntoQuad( QuadTreeNode parentNode, QuadTreeSpatialData quadTreeSpatialData, int depth ) {
for ( int i = 0; i < 2; i++ ) {
for ( int j = 0; j < 2; j++ ) {
BoundingBox parentBounding = parentNode.bounding;
Vector3f parentCenter = parentBounding.getCenter();
float xCenter = parentCenter.x + ( parentBounding.xExtent * i * 2 - parentBounding.xExtent ) / 2.0f;
float zCenter = parentCenter.z + ( parentBounding.zExtent * j * 2 - parentBounding.zExtent ) / 2.0f;
float xExtent = parentBounding.xExtent / 2.0f;
float zExtent = parentBounding.zExtent / 2.0f;
if ( isInside( xCenter, zCenter,
xExtent, zExtent,
quadTreeSpatialData.targetTranslation ) ) {
QuadTreeNode childNode = parentNode.children[j * 2 + i];
if ( childNode == null ) {
childNode = new QuadTreeNode();
Vector3f boundingOrigin = new Vector3f( xCenter, 0, zCenter );
childNode.bounding = new BoundingBox( boundingOrigin,
xExtent,
0,
zExtent );
parentNode.children[j * 2 + i] = childNode;
childNode.minY = childNode.maxY = quadTreeSpatialData.targetTranslation.y;
}
else {
if ( quadTreeSpatialData.targetTranslation.y < childNode.minY ) {
childNode.minY = quadTreeSpatialData.targetTranslation.y;
}
else if ( quadTreeSpatialData.targetTranslation.y > childNode.maxY ) {
childNode.maxY = quadTreeSpatialData.targetTranslation.y;
}
childNode.bounding.getCenter().y = ( childNode.maxY + childNode.minY ) / 2.0f;
childNode.bounding.yExtent = ( childNode.maxY - childNode.minY ) / 2.0f;
}
if ( depth > 0 ) {
sortIntoQuad( childNode, quadTreeSpatialData, depth - 1 );
}
else {
if ( childNode.positions == null ) {
childNode.positions = new ArrayList<QuadTreeSpatialData>();
childNode.bounding.getCenter().y = quadTreeSpatialData.targetTranslation.y;
childNode.bounding.yExtent = 1;
childNode.minY = childNode.maxY = quadTreeSpatialData.targetTranslation.y;
}
else {
if ( quadTreeSpatialData.targetTranslation.y < childNode.minY ) {
childNode.minY = quadTreeSpatialData.targetTranslation.y;
}
else if ( quadTreeSpatialData.targetTranslation.y > childNode.maxY ) {
childNode.maxY = quadTreeSpatialData.targetTranslation.y;
}
childNode.bounding.getCenter().y = ( childNode.maxY + childNode.minY ) / 2.0f;
childNode.bounding.yExtent = ( childNode.maxY - childNode.minY ) / 2.0f;
}
childNode.positions.add( quadTreeSpatialData );
childNode.quadTreeType = QuadTreeNode.TYPE_LEAF;
}
return;
}
}
}
}
private boolean isInside( float xCenter, float zCenter,
float xExtent, float zExtent,
Vector3f position ) {
return position.x >= xCenter - xExtent &&
position.x < xCenter + xExtent &&
position.z >= zCenter - zExtent &&
position.z < zCenter + zExtent;
}
public void draw( Renderer r ) {
r.renderQueue();
frustumCamera.getLocation().set( cam.getLocation() );
frustumCamera.getLeft().set( cam.getLeft() );
frustumCamera.getUp().set( cam.getUp() );
frustumCamera.getDirection().set( cam.getDirection() );
frustumCamera.update();
drawQuadTree( r );
}
public void drawQuadTree( Renderer r ) {
int savedPlaneState = cam.getPlaneState();
for ( int index = 0; index < targetSpatials.size(); index++ ) {
QuadTreeTargetData quadTreeTargetData = targetSpatials.get( index );
Spatial target = quadTreeTargetData.target;
checkQuadTreeAndDraw( quadTreeTargetData.topNode, target, r );
}
cam.setPlaneState( savedPlaneState );
}
private void checkQuadTreeAndDraw( QuadTreeNode parentNode, Spatial target, Renderer r ) {
frustumCamera.setPlaneState( 0 );
parentNode.bounding.setCheckPlane( 0 );
int checkState = frustumCamera.contains( parentNode.bounding );
if ( checkState == Camera.OUTSIDE_FRUSTUM ) {
return;
}
else if ( checkState == Camera.INSIDE_FRUSTUM ||
parentNode.quadTreeType == QuadTreeNode.TYPE_LEAF ) {
Vector3f camLocation = frustumCamera.getLocation();
drawSubQuadTree( parentNode, camLocation, target, r );
}
else if ( checkState == Camera.INTERSECTS_FRUSTUM &&
parentNode.quadTreeType == QuadTreeNode.TYPE_NODE ) {
for ( int i = 0; i < 4; i++ ) {
QuadTreeNode childNode = parentNode.children[i];
if ( childNode != null ) {
checkQuadTreeAndDraw( childNode, target, r );
}
}
}
}
private BoundingVolume tmpBounding = new BoundingBox( new Vector3f( 0, 0, 0 ), 1.0f, 1.0f, 1.0f );
private void drawSubQuadTree( QuadTreeNode parentNode, Vector3f camLocation, Spatial target, Renderer r ) {
if ( parentNode.quadTreeType == QuadTreeNode.TYPE_NODE ) {
for ( int i = 0; i < 4; i++ ) {
QuadTreeNode childNode = parentNode.children[i];
if ( childNode != null ) {
drawSubQuadTree( childNode, camLocation, target, r );
}
}
return;
}
ArrayList<QuadTreeSpatialData> targetPosition = parentNode.positions;
int nrObjects = targetPosition.size();
for ( int i = 0; i < nrObjects; i++ ) {
Vector3f translation = targetPosition.get( i ).targetTranslation;
float distSquared = tmpVec.set( camLocation ).subtractLocal( translation ).lengthSquared();
if ( distSquared > viewDistance * viewDistance ) {
continue;
}
frustumCamera.setPlaneState( 0 );
tmpBounding.getCenter().set( translation );
if ( frustumCamera.contains( tmpBounding ) != Camera.OUTSIDE_FRUSTUM ) {
target.getWorldTranslation().set( translation );
target.getWorldScale().set( targetPosition.get( i ).targetScale );
target.getWorldRotation().set( targetPosition.get( i ).targetRotation );
target.draw( r );
}
}
}
public void updateWorldBound() {
// super.updateWorldBound();
}
public void onDraw( Renderer r ) {
int cm = getCullMode();
if ( cm == CULL_ALWAYS ) {
return;
}
draw( r );
}
public int getTotalNrObjects() {
return totalNrObjects;
}
private class CheckCam extends AbstractCamera {
private int width;
private int height;
public CheckCam( int width, int height ) {
this.width = width;
this.height = height;
}
public Matrix4f getProjectionMatrix() {
return null;
}
public Matrix4f getModelViewMatrix() {
return null;
}
public int getHeight() {
return height;
}
public int getWidth() {
return width;
}
public void onViewPortChange() {
}
public void resize( int width, int height ) {
}
}
}
We are all very lucky… Mojo almost ordered a jME branded thong as part of the prize but he thankfully decided against it… :-o
It was going to be part of the whole Darkfrog dinner thing… but way to ruin it.
Couldn't help myself… My eyes were tearing up at the thought and I couldn't get any work done. :LOL:
Badmi said:
for the record
With the difference being that this is a narrowly defined task... rather than a "build the best game" vague type task.
Hopefully that means this will encourage greater participation since no one participated last time.
maybe it's the dinner with darkfrog that will scare people off this time S
as usual im a bit slow in comprehending :?
Is object of challenge to load objects faster or higher fps or both?
how about memory usage im not sure how to see exactly how much memory a program usues but i did have to increase the heap space to get one million objects to load.
high fps is the main objective…memory is only a worry if it goes scarily high…after all the framework itself loads a million*2 vector3f plus a million quaternions…
So now I have to wear a dress AND a thong with a monkey on it? :-o
I'm feeling rather objectified right now… 
you know, even I draw a line somewhere…you guys paint me like a cross-dressing whore…with warts! :-p
@MrCoder: I don't know, I'm starting to get scared myself. :roll:
darkfrog
@MrCoder:
In both of your implementations I got an error:
hashMapTargetData.bounding.computeFromPoints(mesh.getVertexBuffer(0));
quadTreeTargetData.bounding.computeFromPoints(mesh.getVertexBuffer(0));
I read the documentation of the jME and changed it to:
mesh.getVertexBuffer()
Did the implementation of jME change over night, or what went wrong?
Nico
BTW: My Java-Heap-Size didn't love your 1000*1000 trees
it didn't change over night, just since release .10 :) He's using the cvs version.
I guess I should get newest release too.
Otherwise I am not "compatible".
It should be noted that the tests will be evaluated using the latest CVS version at any given time, so keep that into account while working on the contest. Update often to insure that something in CVS hasn't broken your entry (and yell at us if it has).
sorry for not mentioning anything about that i was using the latest cvs version…and the heapsize has to be upped a bit yes (-Xmx256m for example)
running the latest cvs version would be neat to have as a rule, since it's allways good for us to get extra testing on that version…