HOWZAT

The two then went about designing the world that their story would inhabit. "The great thing about Paris is that it imparted a medieval look to the story. We kept the costumes in the 1930s and let the background do the work. We used as a reference the work of photographer Eugène Atget, who took pictures of old cramped and dirty Paris before much of it was knocked down and redeveloped in the late 19th century.

"We started in 2000 and we actually self-published something, a black and white version of the first two issues combined into one, which we spent a year producing. There's probably a few copies still floating around from the people who bought it out of pity. After it came out, we took a hard look at it and it didn't look very professional, so we took a deep breath, threw the whole thing out and started over again. We produced 3,000 copies of that dummy first issue, which was probably 2,999 too many. Knowing how hard it had been to self-publish, we tried to find a publisher to help us. When Rex Mundi first came out it was basically a murder mystery about Jesus. The Da Vinci Code hadn't been published yet and everyone was scratching their heads at the concept. We took it to Image comics and the guys there took a chance on us. I'm totally grateful to everyone there."

The pressures of producing a complicated comic put a strain on Nelson's relationship with EricJ and in 2004 they parted ways, citing the industry standard "creative differences". Not long after Nelson's partnership with Image also ended, with the writer taking Rex Mundi to rival publisher Dark Horse, where he works with Ferreyra. "EricJ and I worked on Rex Mundi for five years. When we started out we had absolutely know idea what we were doing. The pressure kept mounting the more success we had. The relationship a comic book writer has with an artist is difficult sometimes, like a marriage, and marriages can sometimes go bad and it's not one person's fault. So when we parted ways I think we both realised it was for the best."

At the time of his departure from the comic EricJ sent a touching note to fans: "There are differences and it seems that they are too deep, at this point, to mend. I know that sounds like the old 'creative differences' line that gets thrown out so much, but now I can see why it get used so often. It is very literally the only 'clean' and accurate way to express something that is not 'clean,' but rather very complex. Make no mistake, though, my love for this book is not diminished! Arvid has told me that he plans to continue the book with another artist, and I hope that he does so. I know where this story is going, and I very much want to see it finished, so, please, show Arvid some love and push him onward."

After ten years and almost 40 issues the end is in sight for Nelson. Rex Mundi is near completion, with the final secret of the Grail to be revealed in an issue out this week and the final chapter to be published in August. "People often feel depressed when they've finished their work. I didn't - I felt relieved. I've always thought of Rex Mundi as a television miniseries and I think that a lot of television shows suffer because they go on to long. So I always had a very definite ending in mind. We wanted to end it strong and well as opposed to it being cancelled because we ran out of juice."

But the end is never the end in fantasy and Nelson's original dream of a big screen Rex Mundi is nearing reality. Johnny Depp has been developing a movie adaptation of the comic and has commissioned Fight Club screenwriter Jim Uhls to pen the screenplay. "Having Johnny Depp interested in Rex Mundi is immensely gratifying because he is one of my favourite actors. He understands what the story is about and is smart enough to see that it's not another Da Vinci Code. The second draft of the screenplay has been written and Jim Uhls has been very respectful of the material. As far as directors go, I like so many of the people Johnny has worked with - Gore Verbinski, Tim Burton and Terry Gilliam. I hope something will happen in the next couple of years but so much of these things are in the hands of the gods. Johnny Depp is definitely a very busy person."

One person Depp's production company, Infinitum, is looking at is Watchmen director Zack Snyder. Sam Sarkar, Infinitum's director development, recently told MTV news: "We really need to find a guy who has that kind of visual style — not unlike Zack Snyder. You need a guy that’s that kind of visionary to do Rex, because it's a really visually complex world."

This is not the first time Rex Mundi has been in Hollywood's orbit, which brings us to Nelson's second problem with The Da Vinci Code. "Johnny Depp came on board after we had been scrounging around for a few years. We had been working on a Hollywood adaptation and The Da Vinci Code made that more difficult. Why? Who can fathom the radioactive, mutant mind of Hollywood? My guess is that people took a look at Rex Mundi and concluded 'Da Vinci Clone'. Of course, there's a lot more to Rex Mundi than that. The Grail is only a small part of the story, a starting point, really. All told, it turned out to be a positive. Rex Mundi would be awful if it were shoehorned into a middling Da Vinci Code rip-off. We're aiming a little higher than that."

Arvid Nelson

Dream job "Doing the voice for Kermit the Frog."

Dream city "Paris. The French have a deep passion for art and culture - any kind of culture, whether it be paintings or heavy metal music or comic books. It doesn't have to be high art. The very first person I spoke to when I visited France was a customs officer and we ended up having a 20-minute conversation about pornographic Japanese animation."

What's next after Rex Mundi? "I'm working on Kull the Conqueror. He's a character by Conan creator Robert E. Howard and is actually Howard's first attempt at a loin-cloth-wearing barbarian.Kull is a lesser known entity than Conan so I get to bring a lot of my creativity to it. Conan is invincible and confident and there's nothing he can't accomplish whereas Kull is a darker, more tortured character. He has a history and a purpose whereas you get the feeling that Conan just bounces about. I'm also writing a novel that takes in trolls, wizards and Nordic heavy metal music."

Explore Books

• Book Extracts

• Book Reviews

• Books Group

• Audio Books

Times Recommends

• The 100 Best Books of the Decade
• The Times picks the 50 best paperbacks of 2009
• The conversation: James Ellroy