ArrayIndexOutOfBounds bug in QuadMeshFactory

Found a bug? Post here.
Post Reply
STRESS
Posts: 141
Joined: Mon 19. Jan 2009, 12:10

ArrayIndexOutOfBounds bug in QuadMeshFactory

Post by STRESS » Fri 15. Jan 2010, 12:06

Try this:

Code: Select all

public static IndexedFaceSet createSurface( int x, int y ) {
// generate the coordinates for the surface as a 2D array of 3-vectors
// QuadMeshFactory is the only factory which accepts such a data structure
// as the argument of its setVertexCoordinates() method!

    double [][][] coords = new double [x][y][3];
    for( int i=0; i<x; i++) {
        double v = -.4 + .8*(i/(y-1.0));
        for (int j = 0; j<y; ++j) {
            double u = -.3 + .6*(j/(x-1.0));
	 coords[i][j][0] = 10*(u-v*v);
	 coords[i][j][1]= 10*u*v;
	 coords[i][j][2]= 10*(u*u-4*u*v*v);
        }
     }
		
    // QuadMeshFactory knows how to build an IndexedFaceSet from a rectangular array
    // of vectors.  
    QuadMeshFactory factory = new QuadMeshFactory();
    factory.setVLineCount(x);		// important: the v-direction is the left-most index
    factory.setULineCount(y);		// and the u-direction the next-left-most index
    factory.setClosedInUDirection(false);	
    factory.setClosedInVDirection(false);	
    factory.setVertexCoordinates(coords);	
    factory.setGenerateFaceNormals(true);
    factory.setGenerateTextureCoordinates(true);
    factory.setGenerateEdgesFromFaces(true);
    factory.setEdgeFromQuadMesh(true);	// generate "long" edges: one for each u-, v- parameter curve		
    factory.update();
    // now swap x and y around
    coords = new double [y][x][3];
    for( int i=0; i<y; i++) {
        double v = -.4 + .8*(i/(y-1.0));
        for (int j = 0; j<x; ++j)	{
            double u = -.3 + .6*(j/(x-1.0));
	 coords[i][j][0] = 10*(u-v*v);
	 coords[i][j][1]= 10*u*v;
	 coords[i][j][2]= 10*(u*u-4*u*v*v);
        }
     }
     factory.setVLineCount(y);		// important: the v-direction is the left-most index
     factory.setULineCount(x);		// and the u-direction the next-left-most index
     factory.setClosedInUDirection(false);	
     factory.setClosedInVDirection(false);	
     factory.setVertexCoordinates(coords);	
     factory.setGenerateFaceNormals(true);
     factory.setGenerateTextureCoordinates(true);
     factory.setGenerateEdgesFromFaces(true);
     factory.setEdgeFromQuadMesh(true);	// generate "long" edges: one for each u-, v- parameter curve		
     factory.update(); // <--- CRASH ON THIS LINE
     return factory.getIndexedFaceSet();
}
You'll get this

Code: Select all

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10
        at de.jreality.scene.data.IntArrayStorage.copy(IntArrayStorage.java:104)

        at de.jreality.scene.data.StorageModel$ArrayOf.copy(StorageModel.java:61
1)
        at de.jreality.scene.data.StorageModel.copy(StorageModel.java:161)
        at de.jreality.scene.data.DataItem.copyTo(DataItem.java:155)
        at de.jreality.scene.Geometry.setAttrImpl(Geometry.java:164)
        at de.jreality.scene.Geometry.setAttributes(Geometry.java:281)
        at de.jreality.scene.Geometry.setAttributes(Geometry.java:343)
        at de.jreality.geometry.AbstractGeometryFactory.updateNode(AbstractGeome
tryFactory.java:156)
        at de.jreality.geometry.AbstractPointSetFactory$AttributeGenerator.updat
eArray(AbstractPointSetFactory.java:282)
        at de.jreality.geometry.AbstractIndexedFaceSetFactory.updateImpl(Abstrac
tIndexedFaceSetFactory.java:557)
        at de.jreality.geometry.AbstractQuadMeshFactory.updateImpl(AbstractQuadM
eshFactory.java:287)
        at de.jreality.geometry.AbstractGeometryFactory$1.run(AbstractGeometryFa
ctory.java:107)
        at de.jreality.scene.Scene.executeWriter(Scene.java:113)
        at de.jreality.geometry.AbstractGeometryFactory.update(AbstractGeometryF
actory.java:103)
        at de.jreality.tutorial.geom.QuadMeshExample.createSurface(QuadMeshExamp
le.java:71)
        at de.jreality.tutorial.geom.QuadMeshExample.main(QuadMeshExample.java:7
8)

User avatar
gunn
Posts: 323
Joined: Thu 14. Dec 2006, 09:56
Location: TU Berlin
Contact:

Re: ArrayIndexOutOfBounds bug in QuadMeshFactory

Post by gunn » Fri 15. Jan 2010, 13:52

This bug is due to the fact that the quadmesh factory is automatically generating the index arrays for the indexed face set, based on the u and v line counts. Unfortunately, the code is quite tricky, and the second call to update() results in a chicken-and-egg problem. That is, the super.update() method (on the class IndexedFaceSetFactory) is invoked first before the new edge and face indices for the swapped u,v line counts have been generated. This results in the index out-of-bounds exception, since it's working with the OLD index arrays but the new u- and v- line counts. When I naively attempted to reverse the order of the calls, so the edge and face indices in the QuadMeshFactory get updated BEFORE the call to super.update(), then there are null pointers on the FIRST call to update() in the posted code. So... for the short term, the best solution is to allocate a new QuadMeshFactory whenever you need one, that is, don't attempt to redefine u and v line counts on the same QuadMeshFactory. That's not a good solution, but until a better solution is found, that's all I know to recommend. Is that possible in your situation? The original author of these factories is no longer active, so IMHO it's not clear when the problem will be resolved.
jReality core developer

User avatar
gunn
Posts: 323
Joined: Thu 14. Dec 2006, 09:56
Location: TU Berlin
Contact:

Re: ArrayIndexOutOfBounds bug in QuadMeshFactory

Post by gunn » Fri 15. Jan 2010, 14:27

One more detail I've discovered: the problem only appears if the total number of vertices stays unchanged, as it does in this case. If one uses x-1 instead of x (in the second half of the posted code) then things work correctly, while then the super.update() correctly notices that something has changed and resets itself. However, when the total number of vertices remains the same, then the super.update() does NOT notice anything has changed.

The code does provide the hooks to register dependencies among various attributes and update other attributes accordingly. In this case, I've attempted in my playing around today to register that if uLineCount or vLineCount changes, then the face indices (and by existing dependency the edge indices) need to be updated. But it doesn't have the intended effect. That's because I don't quite understand yet how the dependency tree is evaluated when update() is called.

Anybody understand it better than I do?
jReality core developer

STRESS
Posts: 141
Joined: Mon 19. Jan 2009, 12:10

Re: ArrayIndexOutOfBounds bug in QuadMeshFactory

Post by STRESS » Mon 18. Jan 2010, 11:20

gunn wrote: So... for the short term, the best solution is to allocate a new QuadMeshFactory whenever you need one, that is, don't attempt to redefine u and v line counts on the same QuadMeshFactory.
Thanks gunn that's what I'm doing now. Thanks for confirming that there is a problem.

paul peters
Posts: 17
Joined: Thu 6. Mar 2008, 15:18
Location: TU Berlin, Germany
Contact:

Re: [Solved] Re: ArrayIndexOutOfBounds bug in QuadMeshFactory

Post by paul peters » Mon 8. Feb 2010, 12:20

The bug is now fixed in QuadMeshFactory. I also added a JUnit test

Code: Select all

de.jreality.geometry.QuadMeshTest.testSwapDimensions()
Thanks STRESS for the nice report.

I would like to take the opportunity to explain the root of this bug, which is a source of many ArrayOutOfBound exceptions caused by the use of the geometry factories (gunn's analysis was only partially correct), e.g., the JUnit test

Code: Select all

de.jreality.geometry.IndexedLineSetFactoryTest.testIndexedLineSet()

failed since its introduction back in 2007.

The geometry factories are designed (!) to make many updates of the target geometry possible, and to do this effectively and thread save. But one design decision, which apparently has performance reasons, introduces at least confusion, even for the designer of the geometry factories.

The arrays containing the geometry attributes for edges, faces, and vertices are reused as long as the number of edges, faces, and vertices does not change (in STRESS's example the QuadMeshFactory fails because the sum of ULineCount and VLineCount, which is the number of generated edges, stays the same). Furthermore if the data associated to an edge, face, or vertex is an array, this array is reused and lengths are NOT checked (performance reasons??, the problem is deep in de.jreality.scene.data.StorageModel.ArrayOf.copy).

So the factories who provide setter or generating methods for such attributes need to remove the corresponding geometry attribute from the target method at the latest in their recompute() method triggering the allocation of a brand new array, whenever they cannot be sure that the associated data arrays have the same length (in STRESS's example some edges have length x and some length y). Many of these factory methods fail to do so.

Thats not such a bad problem as the only attributes affected by this - correct me if I'm wrong - are edge and face indices. Their change constitute such a major update to a geometry that the use of a new factory seems appropriate. Still the bug introduces confusion in an important part of the jReality API (I was also confused by this). If I am correct that the only attribute affected by this problem is Attribute.INDICES than a solution would be to replace

Code: Select all

if(w==null) w=target.addWritable(a, d.getStorageModel());
by

Code: Select all

if(w==null  || a == Attribute.INDICES) w=target.addWritable(a, d.getStorageModel());
in

Code: Select all

de.jreality.scene.Geometry.setAttrImpl
I tried and all JUnit tests run fine (including both tests that test the problem, also when I remove my bug fix in the QuadMeshFactory). But as our test coverage is not complete, and the proposed change is at the bases of jReality's geometry generation, I would like to ask for opinions of others first.
Paul Peters

User avatar
gunn
Posts: 323
Joined: Thu 14. Dec 2006, 09:56
Location: TU Berlin
Contact:

Re: ArrayIndexOutOfBounds bug in QuadMeshFactory

Post by gunn » Mon 8. Feb 2010, 15:32

I would personally prefer if a way could be found to use the dependency mechanism structure in the QuadMesh factory (via OoNode) to remove the edge and face indices, forcing a clean re-create, whenever the uline and vline counts are changed. A second alternative would be to correct the copy() routine to detect when the old array structure is incompatible with the new one, and reallocate accordingly.

The proposed solution does the job, but it naturally costs more, since now every call to update() from every factory will recreate these index arrays. But it appears that there is no one among the current developer community who understands the factories (or regarding the alternative proposal, the StorageModel+DataList code) well enough to do this. A similar fix has been in place in GeometryAttributeListSet.setAttribute() for some months now, exactly for the same reason (though it appears it didn't catch all the problems). Let's hope the two fixes together fix the problem.
jReality core developer

paul peters
Posts: 17
Joined: Thu 6. Mar 2008, 15:18
Location: TU Berlin, Germany
Contact:

Re: ArrayIndexOutOfBounds bug in QuadMeshFactory

Post by paul peters » Mon 8. Feb 2010, 16:18

gunn wrote: I would personally prefer if a way could be found to use the dependency mechanism structure in the QuadMesh factory (via OoNode) to remove the edge and face indices, forcing a clean re-create, whenever the uline and vline counts are changed.
Thats what the current fix does. It sets the edge indices to null, when new edge indices are generated (which is triggered by changes in ULineCount and VLineCount).
gunn wrote:The proposed solution does the job, but it naturally costs more, since now every call to update() from every factory will recreate these index arrays.
Thats not true. The attribute is only updated, when the indices change (the AttributeGenerator.updateArray() checks whether the node was updated). So the only difference would be that in addition to a deep copy of arrays of indices a new array would be allocated. I think the cost is very low compared to the deep copy.
gunn wrote: But it appears that there is no one among the current developer community who understands the factories (or regarding the alternative proposal, the StorageModel+DataList code) well enough to do this.
I agree with that, but I doubt that the cost would be lower, because then all attributes were affected by bound checks (one check for each vertex, edge, or, face).
gunn wrote: A similar fix has been in place in GeometryAttributeListSet.setAttribute() for some months now, exactly for the same reason (though it appears it didn't catch all the problems). Let's hope the two fixes together fix the problem.
As mentioned above there is a test (checked in by Markus in 2007) which fails for the same reason. And I'm sure there are many more places.
Paul Peters

User avatar
gunn
Posts: 323
Joined: Thu 14. Dec 2006, 09:56
Location: TU Berlin
Contact:

Re: ArrayIndexOutOfBounds bug in QuadMeshFactory

Post by gunn » Mon 8. Feb 2010, 18:18

OK. Gradually I begin to understand how this works. It appears then that this is a good solution, and I would not object to having it checked into SVN.
jReality core developer

Post Reply