This is an automated email from the ASF dual-hosted git repository. bchapuis pushed a commit to branch geotiff-martini in repository https://gitbox.apache.org/repos/asf/incubator-baremaps.git
commit bdca2b02c852ee2695e2c133a5b2a5fca0502ffe Author: Bertil Chapuis <[email protected]> AuthorDate: Tue Jun 11 11:12:54 2024 +0200 Port the MARTINI algorithm to java --- baremaps-martini/pom.xml | 17 ++ .../java/org/apache/baremaps/martini/Martini.java | 214 +++++++++++++++++++++ .../org/apache/baremaps/martini/MartiniTest.java | 63 ++++++ .../org/apache/baremaps/martini/MartiniUtils.java | 51 +++++ baremaps-martini/src/test/resources/fuji.png | Bin 0 -> 578765 bytes pom.xml | 1 + 6 files changed, 346 insertions(+) diff --git a/baremaps-martini/pom.xml b/baremaps-martini/pom.xml new file mode 100644 index 00000000..5b363fa9 --- /dev/null +++ b/baremaps-martini/pom.xml @@ -0,0 +1,17 @@ +<?xml version="1.0" encoding="UTF-8"?> +<project xmlns="http://maven.apache.org/POM/4.0.0"; xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"; xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd";> + <modelVersion>4.0.0</modelVersion> + <parent> + <groupId>org.apache.baremaps</groupId> + <artifactId>baremaps</artifactId> + <version>0.7.4-SNAPSHOT</version> + </parent> + <artifactId>baremaps-martini</artifactId> + <dependencies> + <dependency> + <groupId>com.twelvemonkeys.imageio</groupId> + <artifactId>imageio-tiff</artifactId> + <version>3.11.0</version> + </dependency> + </dependencies> +</project> diff --git a/baremaps-martini/src/main/java/org/apache/baremaps/martini/Martini.java b/baremaps-martini/src/main/java/org/apache/baremaps/martini/Martini.java new file mode 100644 index 00000000..703f5e1f --- /dev/null +++ b/baremaps-martini/src/main/java/org/apache/baremaps/martini/Martini.java @@ -0,0 +1,214 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to you under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.baremaps.martini; + +/** + * The {@code Martini} class is a port of the MARTINI algorithm for generating 3D terrain meshes from + * height data. + * <p> + * @see <a href="https://github.com/mapbox/martini";>Martini GitHub + */ +public class Martini { + + private final int gridSize; + private final int numTriangles; + private final int numParentTriangles; + + private final int[] baseCoords; + + public Martini(int gridSize) { + this.gridSize = gridSize; + + int tileSize = gridSize - 1; + if ((tileSize & (tileSize - 1)) != 0) { + throw new IllegalArgumentException("Expected grid size to be 2^n+1, got " + gridSize + "."); + } + + this.numTriangles = tileSize * tileSize * 2 - 2; + this.numParentTriangles = this.numTriangles - tileSize * tileSize; + + this.baseCoords = new int[this.numTriangles * 4]; + for (int i = 0; i < this.numTriangles; i++) { + int id = i + 2; + int ax = 0, ay = 0, bx = 0, by = 0, cx = 0, cy = 0; + if ((id & 1) != 0) { + bx = by = cx = tileSize; + } else { + ax = ay = cy = tileSize; + } + while ((id >>= 1) > 1) { + int mx = (ax + bx) >> 1; + int my = (ay + by) >> 1; + + if ((id & 1) != 0) { + bx = ax; + by = ay; + ax = cx; + ay = cy; + } else { + ax = bx; + ay = by; + bx = cx; + by = cy; + } + cx = mx; + cy = my; + } + int k = i * 4; + this.baseCoords[k] = ax; + this.baseCoords[k + 1] = ay; + this.baseCoords[k + 2] = bx; + this.baseCoords[k + 3] = by; + } + } + + public Tile createTile(float[] terrain) { + return new Tile(terrain, gridSize, numTriangles, numParentTriangles, baseCoords); + } + + public static class Tile { + + private final int gridSize; + private final int[] indices; + private final float[] errors; + + private int numVertices; + private int numTriangles; + + private int[] vertices; + private int[] triangles; + private int triIndex = 0; + + private Tile(float[] terrain, int gridSize, int numTriangles, int numParentTriangles, + int[] coords) { + if (terrain.length != gridSize * gridSize) { + throw new IllegalArgumentException( + "Expected terrain data of length " + (gridSize * gridSize) + " (" + gridSize + " x " + + gridSize + "), got " + terrain.length + "."); + } + + this.gridSize = gridSize; + this.indices = new int[this.gridSize * this.gridSize]; + + this.errors = new float[terrain.length]; + for (int i = numTriangles - 1; i >= 0; i--) { + int k = i * 4; + int ax = coords[k]; + int ay = coords[k + 1]; + int bx = coords[k + 2]; + int by = coords[k + 3]; + int mx = (ax + bx) >> 1; + int my = (ay + by) >> 1; + int cx = mx + my - ay; + int cy = my + ax - mx; + + float interpolatedHeight = (terrain[ay * gridSize + ax] + terrain[by * gridSize + bx]) / 2; + int middleIndex = my * gridSize + mx; + float middleError = Math.abs(interpolatedHeight - terrain[middleIndex]); + + errors[middleIndex] = Math.max(errors[middleIndex], middleError); + + if (i < numParentTriangles) { + int leftChildIndex = ((ay + cy) >> 1) * gridSize + ((ax + cx) >> 1); + int rightChildIndex = ((by + cy) >> 1) * gridSize + ((bx + cx) >> 1); + errors[middleIndex] = Math.max(errors[middleIndex], + Math.max(errors[leftChildIndex], errors[rightChildIndex])); + } + } + } + + public Mesh getMesh(float maxError) { + int max = gridSize - 1; + + numVertices = 0; + numTriangles = 0; + countElements(0, 0, max, max, max, 0, maxError); + countElements(max, max, 0, 0, 0, max, maxError); + + vertices = new int[numVertices * 2]; + triangles = new int[numTriangles * 3]; + triIndex = 0; + processTriangle(0, 0, max, max, max, 0, maxError); + processTriangle(max, max, 0, 0, 0, max, maxError); + + return new Mesh(vertices, triangles); + } + + private void countElements(int ax, int ay, int bx, int by, int cx, int cy, float maxError) { + int mx = (ax + bx) >> 1; + int my = (ay + by) >> 1; + + if (Math.abs(ax - cx) + Math.abs(ay - cy) > 1 && errors[my * gridSize + mx] > maxError) { + countElements(cx, cy, ax, ay, mx, my, maxError); + countElements(bx, by, cx, cy, mx, my, maxError); + } else { + indices[ay * gridSize + ax] = + indices[ay * gridSize + ax] != 0 ? indices[ay * gridSize + ax] : ++numVertices; + indices[by * gridSize + bx] = + indices[by * gridSize + bx] != 0 ? indices[by * gridSize + bx] : ++numVertices; + indices[cy * gridSize + cx] = + indices[cy * gridSize + cx] != 0 ? indices[cy * gridSize + cx] : ++numVertices; + numTriangles++; + } + } + + private void processTriangle(int ax, int ay, int bx, int by, int cx, int cy, float maxError) { + int mx = (ax + bx) >> 1; + int my = (ay + by) >> 1; + + if (Math.abs(ax - cx) + Math.abs(ay - cy) > 1 && errors[my * gridSize + mx] > maxError) { + processTriangle(cx, cy, ax, ay, mx, my, maxError); + processTriangle(bx, by, cx, cy, mx, my, maxError); + } else { + int a = indices[ay * gridSize + ax] - 1; + int b = indices[by * gridSize + bx] - 1; + int c = indices[cy * gridSize + cx] - 1; + + vertices[2 * a] = ax; + vertices[2 * a + 1] = ay; + vertices[2 * b] = bx; + vertices[2 * b + 1] = by; + vertices[2 * c] = cx; + vertices[2 * c + 1] = cy; + + triangles[triIndex++] = a; + triangles[triIndex++] = b; + triangles[triIndex++] = c; + } + } + } + + public static class Mesh { + + private final int[] vertices; + private final int[] triangles; + + public Mesh(int[] vertices, int[] triangles) { + this.vertices = vertices; + this.triangles = triangles; + } + + public int[] getVertices() { + return vertices; + } + + public int[] getTriangles() { + return triangles; + } + } +} diff --git a/baremaps-martini/src/test/java/org/apache/baremaps/martini/MartiniTest.java b/baremaps-martini/src/test/java/org/apache/baremaps/martini/MartiniTest.java new file mode 100644 index 00000000..9177bd4a --- /dev/null +++ b/baremaps-martini/src/test/java/org/apache/baremaps/martini/MartiniTest.java @@ -0,0 +1,63 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to you under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.baremaps.martini; + +import static org.junit.jupiter.api.Assertions.assertArrayEquals; + +import java.awt.image.BufferedImage; +import java.io.IOException; +import java.nio.file.Path; +import javax.imageio.ImageIO; +import org.junit.jupiter.api.Test; + +public class MartiniTest { + + @Test + public void generateAMesh() throws IOException { + BufferedImage png = ImageIO.read( + Path.of("") + .toAbsolutePath() + .resolveSibling("baremaps-geotiff/src/test/resources/fuji.png") + .toAbsolutePath().toFile()); + float[] terrainGrid = MartiniUtils.mapboxTerrainToGrid(png); + var martini = new Martini(png.getWidth() + 1); + var tile = martini.createTile(terrainGrid); + var mesh = tile.getMesh(500); + + assertArrayEquals(new int[] { + 320, 64, 256, 128, 320, 128, 384, 128, 256, 0, 288, 160, 256, 192, 288, 192, 320, 192, 304, + 176, 256, 256, 288, 224, 352, 160, 320, 160, 512, 0, 384, 0, 128, 128, 128, 0, 64, 64, 64, + 0, 0, 0, 32, 32, 192, 192, 384, 384, 512, 256, 384, 256, 320, 320, 320, 256, 512, 512, 512, + 128, 448, 192, 384, 192, 128, 384, 256, 512, 256, 384, 0, 512, 128, 256, 64, 192, 0, 256, + 64, 128, 32, 96, 0, 128, 32, 64, 16, 48, 0, 64, 0, 32 + }, mesh.getVertices()); + + assertArrayEquals(new int[] { + 0, 1, 2, 3, 0, 2, 4, 1, 0, 5, 6, 7, 7, 8, 9, 5, 7, 9, 1, 6, 5, 6, 10, 11, 11, 8, 7, 6, 11, + 7, 12, 2, 13, 8, 12, 13, 3, 2, 12, 2, 1, 5, 13, 5, 9, 8, 13, 9, 2, 5, 13, 3, 14, 15, 15, 4, + 0, 3, 15, 0, 16, 4, 17, 18, 17, 19, 19, 20, 21, 18, 19, 21, 16, 17, 18, 1, 16, 22, 22, 10, + 6, 1, 22, 6, 4, 16, 1, 23, 24, 25, 26, 25, 27, 10, 26, 27, 23, 25, 26, 28, 24, 23, 29, 3, + 30, 24, 29, 30, 14, 3, 29, 8, 25, 31, 31, 3, 12, 8, 31, 12, 27, 8, 11, 10, 27, 11, 25, 8, + 27, 25, 24, 30, 30, 3, 31, 25, 30, 31, 32, 33, 34, 10, 32, 34, 35, 33, 32, 33, 28, 23, 34, + 23, 26, 10, 34, 26, 33, 23, 34, 36, 16, 37, 38, 36, 37, 36, 10, 22, 16, 36, 22, 39, 18, 40, + 41, 39, 40, 16, 18, 39, 42, 21, 43, 44, 42, 43, 18, 21, 42, 21, 20, 45, 45, 44, 43, 21, 45, + 43, 44, 41, 40, 40, 18, 42, 44, 40, 42, 41, 38, 37, 37, 16, 39, 41, 37, 39, 38, 35, 32, 32, + 10, 36, 38, 32, 36 + }, mesh.getTriangles()); + } +} diff --git a/baremaps-martini/src/test/java/org/apache/baremaps/martini/MartiniUtils.java b/baremaps-martini/src/test/java/org/apache/baremaps/martini/MartiniUtils.java new file mode 100644 index 00000000..bfae6c7a --- /dev/null +++ b/baremaps-martini/src/test/java/org/apache/baremaps/martini/MartiniUtils.java @@ -0,0 +1,51 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to you under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.baremaps.martini; + +import java.awt.image.BufferedImage; + +public class MartiniUtils { + + public static float[] mapboxTerrainToGrid(BufferedImage png) { + int gridSize = png.getWidth() + 1; + float[] terrain = new float[gridSize * gridSize]; + + int tileSize = png.getWidth(); + + // decode terrain values + for (int y = 0; y < tileSize; y++) { + for (int x = 0; x < tileSize; x++) { + int k = (y * tileSize + x) * 4; + int r = (png.getRGB(x, y) >> 16) & 0xFF; + int g = (png.getRGB(x, y) >> 8) & 0xFF; + int b = png.getRGB(x, y) & 0xFF; + terrain[y * gridSize + x] = (r * 256 * 256 + g * 256.0f + b) / 10.0f - 10000.0f; + } + } + + // backfill right and bottom borders + for (int x = 0; x < gridSize - 1; x++) { + terrain[gridSize * (gridSize - 1) + x] = terrain[gridSize * (gridSize - 2) + x]; + } + for (int y = 0; y < gridSize; y++) { + terrain[gridSize * y + gridSize - 1] = terrain[gridSize * y + gridSize - 2]; + } + + return terrain; + } +} diff --git a/baremaps-martini/src/test/resources/fuji.png b/baremaps-martini/src/test/resources/fuji.png new file mode 100644 index 00000000..9e4e8b76 Binary files /dev/null and b/baremaps-martini/src/test/resources/fuji.png differ diff --git a/pom.xml b/pom.xml index eb1e3bd5..d3c42a91 100644 --- a/pom.xml +++ b/pom.xml @@ -54,6 +54,7 @@ limitations under the License. <module>baremaps-data</module> <module>baremaps-geoparquet</module> <module>baremaps-maplibre</module> + <module>baremaps-martini</module> <module>baremaps-openstreetmap</module> <module>baremaps-pmtiles</module> <module>baremaps-server</module>
